顺序表表
一、 设 n 个人围坐在一个圆桌周围，现在从第 s 个人开始报数，数到第 m 个人，让他出局；然后从出局的下一个人重新开始报数，数到第 m 个人，再让他出局，……，如此反复直到所有的人全部出局为止。下面要解决的 Josephus 问题是：对于任意给定的 n, s 和 m ，求出这 n 个人的出局序列。请以 n = 9, s = 1, m = 5 为例，人工模拟 Josephus 的求解过程以求得问题的解。
【解答】
二、设有一个线性表 (e 0 , e 1 , … , e n-2 , e n-1 ) 存放在一个一维数组 A[arraySize] 中的前 n 个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前 n 个原址内容置换为 (e n-1 , e n-2 , … , e 1 , e 0 ) 。
【解答】
三、顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下 , 对有 127 个元素的顺序表进行插入 , 平均需要移动多少个元素 ? 删除一个元素 , 又平均需要移动多少个元素 ?
【解答】
四、 利用顺序表的操作，实现以下的函数。
(1) 从顺序表中删除具有最小值的元素并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。
(2) 从顺序表中删除第 i 个元素并由函数返回被删元素的值。如果 i 不合理或顺序表为空则显示出错信息并退出运行。
(3) 向顺序表中第 i 个位置插入一个新的元素 x 。如果 i 不合理则显示出错信息并退出运行。
(4) 从顺序表中删除具有给定值 x 的所有元素。
【解答】
(1) 实现删除具有最小值元素的函数如下：
template<Type> Type SeqList< Type> :: DelMin ( ) {
}
(2) 实现删除第 i 个元素的函数如下 ( 设第 i 个元素在 data[i], i=0,1, ? ,last) ：
template<Type> Type SeqList< Type> :: DelNo#i ( int i ) {
}
(3) 实现向第 i 个位置插入一个新的元素 x 的函数如下 ( 设第 i 个元素在 data[i], i=0,1, ? ,last) ：
template<Type> void SeqList< Type> :: InsNo#i ( int i, Type& x ) {
}
(4) 从顺序表中删除具有给定值 x 的所有元素。
template<Type> void SeqList< Type> :: DelValue ( Type& x ) {
}
线性链表
单链表的结点类 (ListNode class ) 和链表类 (List class ) 的类定义。
template <class Type> class List ; // 前视的类定义
template <class Type> class ListNode { // 链表结点类的定义
friend class List <Type>; //List 类作为友元类定义
private:
Type data ; // 数据域
ListNode <Type> *link ; // 链指针域
public:
ListNode ( ) : link (NULL) { } // 仅初始化指针成员的构造函数
ListNode ( const Type& item ) : data (item) , link (NULL) { }
// 初始化数据与指针成员的构造函数
ListNode <Type> * getNode ( const Type& item , ListNode <Type> *next = NULL )
// 以 item 和 next 建立一个新结点
ListNode <Type> * getLink ( ) { return link ; } // 取得结点的下一结点地址
Type getData ( ) { return data ; } // 取得结点中的数据
void setLink ( ListNode <Type> * next ) { link = next ; } // 修改结点的 link 指针
void setData ( Type value ) { data = value ; } // 修改结点的 data 值
};
template <class Type> class List { // 单链表类定义
private:
ListNode <Type> *first , *current ; // 链表的表头指针和当前元素指针
public:
List ( const Type& value ) { first = current = new ListNode <Type> ( value ) ; }
// 构造函数
~List ( ) { MakeEmpty ( ) ; delete first ; } // 析构函数
void MakeEmpty ( ) ; // 将链表置为空表
int Length ( ) const; // 计算链表的长度
ListNode <Type> * Find ( Type value ) ; // 搜索含数据 value 的元素并成为当前元素
ListNode< Type > * Locate( int i ); // 搜索第 i 个元素的地址并置为当前元素
Type * GetData ( ) ; // 取出表中当前元素的值
int Insert ( Type value ) ; // 将 value 插在表当前位置之后并成为当前元素
Type *Remove ( ) ; // 将链表中的当前元素删去 , 填补者为当前元素
ListNode <Type> * Firster ( ) { current = first ; return first ; } // 当前指针定位于表头结点
Type *First ( ) ; // 当前指针定位于表中第一个元素并返回其值
Type *Next ( ) ; // 将当前指针进到表中下一个元素并返回其值
int NotNull ( ) { return current != NULL ; } // 表中当前元素空否？空返回 1, 不空返回 0
int NextNotNull ( ) { return current != NULL && current->link != NULL ; }
// 当前元素下一元素空否？空返回 1, 不空返回 0
};
一、线性表可用顺序表或链表存储。试问：
(1) 两种存储表示各有哪些主要优缺点 ?
(2) 如果有 n 个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？
(3) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？
【解答】
二、针对带表头结点的单链表，试编写下列函数。
(1) 定位函数 Locate ：在单链表中寻找第 i 个结点。若找到，则函数返回第 i 个结点的地址；若找不到，则函数返回 NULL 。
(2) 求最大值函数 max ：通过一趟遍历在单链表中确定值最大的结点。
(3) 统计函数 number ：统计单链表中具有给定值 x 的所有元素。
(4) 建立函数 create ：根据一维数组 a[n] 建立一个单链表，使单链表中各元素的次序与 a[n] 中各元素的次序相同，要求该程序的时间复杂性为 O(n) 。
【解答】
(1) 实现定位函数的算法如下：
template <class Type> ListNode <Type> * List <Type> :: Locate ( int i ) {
}
(2) 实现求最大值的函数如下：
template <class Type> ListNode <Type> * List <Type> :: Max ( ) {
}
(3) 实现统计单链表中具有给定值 x 的所有元素的函数如下：
template <class Type> int List <Type> :: Count ( Type& x ) {
}
(4) 实现从一维数组 A[n] 建立单链表的函数如下：
template<class Type>voidList<Type>::Create( Type A[ ], int n ) {
}
答案
>>返回 |
