顺序表表
2-1 设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，……，如此反复直到所有的人全部出局为止。下面要解决的Josephus问题是：对于任意给定的n,s和m，求出这n个人的出局序列。请以n = 9,s = 1,m = 5为例，人工模拟Josephus的求解过程以求得问题的解。
【解答】
出局人的顺序为5,1,7,4,3,6,9,2,8。
2-2 试编写一个求解Josephus问题的函数。用整数序列1,2,3,……,n表示顺序围坐在圆桌周围的人，并采用数组表示作为求解过程中使用的数据结构。然后使用n = 9,s = 1,m = 5，以及n = 9,s = 1,m = 0，或者n = 9,s = 1,m = 10作为输入数据，检查你的程序的正确性和健壮性。最后分析所完成算法的时间复杂度。
【解答】函数源程序清单如下：
void Josephus( int A[ ],int n,s,m ) {
int i,j,k,tmp;
if ( m == 0 ) {
cout << "m = 0是无效的参数！" << endl;
return;
}
for ( i = 0; i < n; i++ ) A[i] = i + 1; /*初始化，执行n次*/
i = s - 1; /*报名起始位置*/
for ( k = n; k > 1; i-- ) { /*逐个出局，执行n-1次*/
if ( i == k ) i = 0;
i = ( i + m - 1 ) % k; /*寻找出局位置*/
if ( i != k-1 ) {
tmp = A[i]; /*出局者交换到第k-1位置*/
for ( j = i; j < k-1; j++ ) A[j] = A[j+1];
A[k-1] = tmp;
}
}
for ( k = 0; k < n / 2; k++ ) { /*全部逆置,得到出局序列*/
tmp = A[k]; A[k] = A[n-k+1]; A[n-k+1] = tmp;
}
}
例：n = 9,s = 1,m = 5
0
1
2
3
4
5
6
7
8
k = 9
1
2
3
4
5
6
7
8
9
第5人出局,i = 4
k = 8
1
2
3
4
6
7
8
9
5
第1人出局,i = 0
k = 7
2
3
4
6
7
8
9
1
5
第7人出局,i = 4
k = 6
2
3
4
6
8
9
7
1
5
第4人出局,i = 2
k = 5
2
3
6
8
9
4
7
1
5
第3人出局,i = 1
k = 4
2
6
8
9
3
4
7
1
5
第6人出局,i = 1
k = 3
2
8
9
6
3
4
7
1
5
第9人出局,i = 2
k = 2
2
8
9
6
3
4
7
1
5
第2人出局,i = 0
8
2
9
6
3
4
7
1
5
第8人出局,i = 0
逆置
5
1
7
4
3
6
9
2
8
最终出局顺序
例：n = 9,s = 1,m = 0
报错信息 m = 0是无效的参数！
例：n = 9,s = 1,m = 10
0
1
2
3
4
5
6
7
8
k = 9
1
2
3
4
5
6
7
8
9
第1人出局,i = 0
k = 8
2
3
4
5
6
7
8
9
1
第3人出局,i = 1
k = 7
2
4
5
6
7
8
9
3
1
第6人出局,i = 3
k = 6
2
4
5
7
8
9
6
3
1
第2人出局,i = 0
k = 5
4
5
7
8
9
2
6
3
1
第9人出局,i = 4
k = 4
4
5
7
8
9
2
6
3
1
第5人出局,i = 1
k = 3
4
7
8
5
9
2
6
3
1
第7人出局,i = 1
k = 2
4
8
7
5
9
2
6
3
1
第4人出局,i = 0
8
4
7
5
9
2
6
3
1
第8人出局,i = 0
逆置
1
3
6
2
9
5
7
4
8
最终出局顺序
当m = 1时，时间代价最大。达到( n-1 ) + ( n-2 ) + + 1 = n(n-1)/2 ( O(n2)。
2-3 设有一个线性表 (e0,e1,…,en-2,en-1) 存放在一个一维数组A[arraySize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容置换为 (en-1,en-2,…,e1,e0)。
【解答】
template<class Type> void inverse ( Type A[ ],int n ) {
Type tmp;
for ( int i = 0; i <= ( n-1 ) / 2; i++ ) {
tmp = A[i]; A[i] = A[n-i-1]; A[n-i-1] = tmp;
}
}
2-4 顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下,对有127个元素的顺序表进行插入,平均需要移动多少个元素? 删除一个元素,又平均需要移动多少个元素?
【解答】
若设顺序表中已有n = last+1个元素，last是顺序表的数据成员，表明最后表项的位置。又设插入或删除表中各个元素的概率相等，则在插入时因有n+1个插入位置(可以在表中最后一个表项后面追加)，每个元素位置插入的概率为1/(n+1)，但在删除时只能在已有n个表项范围内删除，所以每个元素位置删除的概率为1/n。
插入时平均移动元素个数AMN(Averagy Moving Number )为
删除时平均移动元素个数AMN为
2-5 利用顺序表的操作，实现以下的函数。
(1) 从顺序表中删除具有最小值的元素并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。
(2) 从顺序表中删除第i个元素并由函数返回被删元素的值。如果i不合理或顺序表为空则显示出错信息并退出运行。
(3) 向顺序表中第i个位置插入一个新的元素x。如果i不合理则显示出错信息并退出运行。
(4) 从顺序表中删除具有给定值x的所有元素。
(5) 从顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素，如果s或t不合理或顺序表为空则显示出错信息并退出运行。
(6) 从有序顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素，如果s或t不合理或顺序表为空则显示出错信息并退出运行。
(7) 将两个有序顺序表合并成一个新的有序顺序表并由函数返回结果顺序表。
(8) 从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。
【解答】
(1) 实现删除具有最小值元素的函数如下：
template<Type> Type SeqList<Type>,,DelMin ( ) {
if ( last == -1 ) //表空,中止操作返回
{ cerr <<, List is Empty!, << endl; exit(1); }
int m = 0; //假定0号元素的值最小
for ( int i = 1; i <= last; i++ ) { //循环,寻找具有最小值的元素
if ( data[i] < data[m] ) m = i; //让m指向当前具最小值的元素
Type temp = data[m];
//空出位置由最后元素填补,表最后元素位置减1
data[m] = data[last]; last--;
return temp;
}
(2) 实现删除第i个元素的函数如下(设第i个元素在data[i],i=0,1,(,last)：
template<Type> Type SeqList<Type>,,DelNo#i ( int i ) {
if ( last == -1 || i < 0 || i > last ) //表空,或i不合理,中止操作返回
{ cerr <<, List is Empty or Parameter is out range!, << endl; exit(1); }
Type temp = data[i]; //暂存第i个元素的值
for ( int j = i; j < last; j++ ) //空出位置由后续元素顺次填补
data[j] = data[j+1];
last--; //表最后元素位置减1
return temp;
}
(3) 实现向第i个位置插入一个新的元素x的函数如下(设第i个元素在data[i],i=0,1,(,last)：
template<Type> void SeqList<Type>,,InsNo#i ( int i,Type& x ) {
//表满或参数i不合理,中止操作返回
if ( last == MaxSize-1|| i < 0 || i > last+1 )
{ cerr <<, List is Full or Parameter is out range!, << endl; exit(1); }
//空出位置以便插入,若i=last+1,此循环不做
for ( int j = last; j >= i; j-- )
data[j+1] = data[j];
data[i] = x; //插入
last++; //表最后元素位置加1
}
(4) 从顺序表中删除具有给定值x的所有元素。
template<Type> void SeqList<Type>,,DelValue ( Type& x ) {
int i = 0,j;
while ( i <= last ) //循环,寻找具有值x的元素并删除它
if ( data[i] == x ) { //删除具有值x的元素,后续元素前移
for ( j = i; j < last; j++ ) data[j] = data[j+1];
last--; //表最后元素位置减1
}
else i++;
}
(5) 实现删除其值在给定值s与t之间（要求s小于t）的所有元素的函数如下：
template<Type> void SeqList<Type>,,DelNo#sto#t ( Type& s,Type& t ) {
if ( last == -1 || s >= t )
{ cerr <<,List is empty or parameters are illegal!” << endl; exit(1); }
int i = 0,j;
while ( i <= last ) //循环,寻找具有值x的元素并删除它
//删除满足条件的元素,后续元素前移
if ( data[i] >= s && data[i] <= t ) {
for ( j = i; j < last; j++ ) data[j] = data[j+1];
last--; //表最后元素位置减1
}
else i++;
}
(6) 实现从有序顺序表中删除其值在给定值s与t之间的所有元素的函数如下：
template<Type> void SeqList<Type>,,DelNo#sto#t1 ( Type& s,Type& t ) {
if ( last == -1 || s >= t )
{ cerr <<,List is empty or parameters are illegal!” << endl; exit(1); }
for ( int i = 0; i <= last; i++ ) //循环,寻找值 ≥s 的第一个元素
if ( data[i] >= s ) break; //退出循环时,i指向该元素
if ( i <= last ) {
for ( int j = 1; i + j <= last; j++ )//循环,寻找值 > t 的第一个元素
if ( data[i+j] > t ) break; //退出循环时,i+j指向该元素
//删除满足条件的元素,后续元素前移
for ( int k = i+j; k <= last; k++ )
data[k-j] = data[k];
last-= j; //表最后元素位置减j
}
}
(7) 实现将两个有序顺序表合并成一个新的有序顺序表的函数如下：
template<Type> SeqList<Type>& SeqList<Type>,,Merge ( SeqList<Type>& A,SeqList<Type>& B ) {
//合并有序顺序表A与B成为一个新的有序顺序表并由函数返回
if ( A.Length() + B.Length() > MaxSize )
{ cerr <<,The summary of The length of Lists is out MaxSize!” << endl; exit(1); }
Type value1 = A.Fist ( ),value2 = B.Fisrt ( );
int i = 0,j = 0,k = 0;
//循环,两两比较,小者存入结果表
while ( i < A.length ( ) && j < B.length ( ) ) {
if ( value1 <= value2 )
{ data[k] = value1; value1 = A.Next ( ); i++; }
else { data[k] = value2; value2 = B.Next ( ); j++; }
k++;
}
while ( i < A.Length ( ) ) //当A表未检测完,继续向结果表传送
{ data[k] = value1; value1 = A.Next ( ); i++; k++; }
while ( j < B.Length ( ) ) //当B表未检测完,继续向结果表传送
{ data[k] = value2; value2 = B.Next ( ); j++; k++; }
last = k – 1;
return *this;
}
(8) 实现从表中删除所有其值重复的元素的函数如下：
template<Type> void SeqList<Type>,,DelDouble ( ) {
if ( last == -1 )
{ cerr <<,List is empty!” << endl; exit(1); }
int i = 0,j,k; Type temp;
while ( i <= last ) { //循环检测
j = i + 1; temp = data[i];
while ( j <= last ) { //对于每一个i,重复检测一遍后续元素
if ( temp == data[j] ) { //如果相等,后续元素前移
for ( k = j+1; k <= last; k++ ) data[k-1] = data[k];
last--; //表最后元素位置减1
}
else j++;
}
i++; //检测完data[i],检测下一个
}
}
线性链表单链表的结点类(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
};
2-6线性表可用顺序表或链表存储。试问：
(1) 两种存储表示各有哪些主要优缺点?
(2) 如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？
(3) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？
【解答】
(1) 顺序存储表示是将数据元素存放于一个连续的存储空间中，实现顺序存取或(按下标)直接存取。它的存储效率高，存取速度快。但它的空间大小一经定义，在程序整个运行期间不会发生改变，因此，不易扩充。同时，由于在插入或删除时，为保持原有次序，平均需要移动一半(或近一半)元素，修改效率不高。
链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要存储器中还有空间，就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理顺序，只需要保持原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针，修改效率较高。但存取表中的数据元素时，只能循链顺序访问，因此存取效率不高。
(2) 如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用链接存储表示。
如果采用顺序存储表示，必须在一个连续的可用空间中为这n个表分配空间。初始时因不知道哪个表增长得快，必须平均分配空间。在程序运行过程中，有的表占用的空间增长得快，有的表占用的空间增长得慢；有的表很快就用完了分配给它的空间，有的表才用了少量的空间，在进行元素的插入时就必须成片地移动其他的表的空间，以空出位置进行插入；在元素删除时，为填补空白，也可能移动许多元素。这个处理过程极其繁琐和低效。
如果采用链接存储表示，一个表的存储空间可以连续，可以不连续。表的增长通过动态存储分配解决，只要存储器未满，就不会有表溢出的问题；表的收缩可以通过动态存储释放实现，释放的空间还可以在以后动态分配给其他的存储申请要求，非常灵活方便。对于n个表(包括表的总数可能变化)共存的情形，处理十分简便和快捷。所以选用链接存储表示较好。
(3) 应采用顺序存储表示。因为顺序存储表示的存取速度快，但修改效率低。若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时采用顺序存储表示较好。
2-7 针对带表头结点的单链表，试编写下列函数。
(1) 定位函数Locate：在单链表中寻找第i个结点。若找到，则函数返回第i个结点的地址；若找不到，则函数返回NULL。
(2) 求最大值函数max：通过一趟遍历在单链表中确定值最大的结点。
(3) 统计函数number：统计单链表中具有给定值x的所有元素。
(4) 建立函数create：根据一维数组a[n]建立一个单链表，使单链表中各元素的次序与a[n]中各元素的次序相同，要求该程序的时间复杂性为O(n)。
(5) 整理函数tidyup：在非递减有序的单链表中删除值相同的多余结点。
【解答】
(1) 实现定位函数的算法如下：
template <class Type> ListNode <Type> * List <Type>,,Locate ( int i ) {
//取得单链表中第i个结点地址,i从1开始计数,i <= 0时返回指针NULL
if ( i <= 0 ) return NULL; //位置i在表中不存在
ListNode <Type> * p = first; int k = 0; //从表头结点开始检测
while ( p != NULL && k < i ) { p = p->link; k++; } //循环,p == NULL表示链短,无第i个结点
return p; //若p != NULL,则k == i,返回第i个结点地址
}
(2) 实现求最大值的函数如下：
template <class Type> ListNode <Type> * List <Type>,,Max ( ) {
//在单链表中进行一趟检测，找出具有最大值的结点地址,如果表空,返回指针NULL
if ( first->link == NULL ) return NULL; //空表,返回指针NULL
ListNode <Type> * pmax = first->link,p = first->link->link; //假定第一个结点中数据具有最大值
while ( p != NULL ) { //循环,下一个结点存在
if ( p->data > pmax->data ) pmax = p; //指针pmax记忆当前找到的具最大值结点
p = p->link; //检测下一个结点
}
return pmax;
}
(3) 实现统计单链表中具有给定值x的所有元素的函数如下：
template <class Type> int List <Type>,,Count ( Type& x ) {
//在单链表中进行一趟检测，找出具有最大值的结点地址,如果表空,返回指针NULL
int n = 0;
ListNode <Type> * p = first->link; //从第一个结点开始检测
while ( p != NULL ) { //循环,下一个结点存在
if ( p->data == x ) n++; //找到一个,计数器加1
p = p->link; //检测下一个结点
}
return n;
}
(4) 实现从一维数组A[n]建立单链表的函数如下：
template <class Type> void List <Type>,,Create ( Type A[ ],int n ) {
//根据一维数组A[n]建立一个单链表，使单链表中各元素的次序与A[n]中各元素的次序相同
ListNode<Type> * p;
first = p = new ListNode<Type>; //创建表头结点
for ( int i = 0; i < n; i++ ) {
p->link = new ListNode<Type> ( A[i] ); //链入一个新结点,值为A[i]
p = p->link; //指针p总指向链中最后一个结点
}
p->link = NULL;
}
采用递归方法实现时，需要通过引用参数将已建立的单链表各个结点链接起来。为此，在递归地扫描数组A[n]的过程中，先建立单链表的各个结点，在退出递归时将结点地址p（被调用层的形参）带回上一层（调用层）的实参p->link。
template<Type> void List<Type>,,create ( Type A[ ],int n,int i,ListNode<Type> *& p ) {
//私有函数：递归调用建立单链表
if ( i == n ) p = NULL;
else { p = new ListNode<Type>( A[i] ); //建立链表的新结点
create ( A,n,i+1,p->link ); //递归返回时p->link中放入下层p的内容
}
}
template<Type> void List<Type>,,create ( Type A[ ],int n ) {
//外部调用递归过程的共用函数
first = current = new ListNode<Type>; //建立表头结点
create ( A,n,0,first->link ); //递归建立单链表
}
(5) 实现在非递减有序的单链表中删除值相同的多余结点的函数如下：
template <class Type> void List <Type>,,tidyup ( ) {
ListNode<Type> * p = first->link,temp; //检测指针,初始时指向链表第一个结点
while ( p != NULL && p->link != NULL ) //循环检测链表
if ( p->data == p->link->data ) { //若相邻结点所包含数据的值相等
temp = p->first; p->link = temp->link; //为删除后一个值相同的结点重新拉链
delete temp; //删除后一个值相同的结点
}
else p = p->link; //指针p进到链表下一个结点
}
2-8 设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针,试设计一个算法,将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其它的存储空间。表中允许有重复的数据。
【解答】
#include <iostream.h>
template <class Type> class List;
template <class Type> class ListNode {
friend class List<Type>;
public:
ListNode ( ); //构造函数
ListNode ( const Type& item ); //构造函数
private:
Type data;
ListNode<Type> *link;
};
template <class Type> class List {
public:
List ( const Type finishied ); //建立链表
void Browse ( ); //打印链表
void Merge ( List<Type> &hb ); //连接链表
private:
ListNode<Type> *first,*last;
};
//各成员函数的实现
template <class Type>
ListNode<Type>,,ListNode ( ), link ( NULL ) { }
//构造函数,仅初始化指针成员。
template <class Type> ListNode<Type>,,ListNode ( const Type & item ), data ( item ),link ( NULL ) { }
//构造函数,初始化数据与指针成员。
template <class Type> List<Type>,,List ( const Type finishied ) {
//创建一个带表头结点的有序单链表,finished是停止建表输入标志,是所有输入值中不可能出现的数值。
first = last = new ListNode<Type>( ); //创建表头结点
Type value; ListNode<Type> *p,*q,*s;
cin >> value;
while ( value != finished ) { //循环建立各个结点
s = new ListNode<Type>( value );
q = first; p = first->link;
while ( p != NULL && p->data <= value )
{ q = p; p = p->link; } //寻找新结点插入位置
q->link = s; s->link = p; //在q,p间插入新结点
if ( p == NULL ) last = s;
cin >> value;
}
}
template <class Type> void List<Type>,,Browse ( ) {
//浏览并输出链表的内容
cout<<"\nThe List is, \n";
ListNode<Type> *p = first->link;
while ( p != NULL ) {
cout << p->data;
if ( p != last ) cout << "->";
else cout << endl;
p = p->link;
}
}
template <class Type> void List <Type>,,Merge ( List<Type>& hb) {
//将当前链表this与链表hb按逆序合并，结果放在当前链表this中。
ListNode<Type> *pa,*pb,*q,*p;
pa = first->link; pb = hb.first->link; //检测指针跳过表头结点
first->link = NULL; //结果链表初始化
while ( pa != NULL && pb != NULL ) { //当两链表都未结束时
if ( pa->data <= pb->data )
{ q = pa; pa = pa->link; } //从pa链中摘下
else
{ q = pb; pb = pb->link; } //从pb链中摘下
q→link = first->link; first->link = q; //链入结果链的链头
}
p = ( pa != NULL )? pa, pb; //处理未完链的剩余部分
while ( p != NULL ) {
q = p; p = p->link;
q->link = first->link; first->link = q;
}
}
2-9 设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。
【解答1】
template<class Type> void List<Type>,,Inverse ( ) {
if ( first == NULL ) return;
ListNode<Type> *p = first->link,*pr = NULL;
while ( p != NULL ) {
first->link = pr; //逆转first指针
pr = first; first = p; p = p->link; //指针前移
}
first->link = pr;
}
【解答2】
template<class Type> void List<Type>,,Inverse ( ) {
ListNode<Type> *p,*head = new ListNode<Type> ( ); //创建表头结点,其link域默认为NULL
while ( first != NULL ) {
p = first; first = first->link; //摘下first链头结点
p->link = head->link; head->link = p; //插入head链前端
}
first = head->link; delete head; //重置first,删去表头结点
}
2-10 从左到右及从右到左遍历一个单链表是可能的，其方法是在从左向右遍历的过程中将连接方向逆转，如右图所示。在图中的指针p指向当前正在访问的结点，指针pr指向指针p所指结点的左侧的结点。此时，指针p所指结点左侧的所有结点的链接方向都已逆转。
(1) 编写一个算法，从任一给定的位置(pr,p)开始，将指针p右移k个结点。如果p移出链表，则将p置为0，并让pr停留在链表最右边的结点上。
(2) 编写一个算法，从任一给定的位置(pr,p)开始，将指针p左移k个结点。如果p移出链表，则将p置为0，并让pr停留在链表最左边的结点上。
【解答】
(1) 指针p右移k个结点
template<class Type> void List<Type>,,
siftToRight ( ListNode<Type> *& p,ListNode<Type> *& pr,int k ) {
if ( p == NULL && pr != first ) { //已经在链的最右端
cout << "已经在链的最右端，不能再右移。" << endl;
return;
}
int i; ListNode<Type> *q;
if ( p == NULL ) //从链头开始
{ i = 1; pr = NULL; p = first; } //重置p到链头也算一次右移
else i = 0;
while ( p != NULL && i < k ) { //右移k个结点
q = p->link; p->link = pr; //链指针p→link逆转指向pr
pr = p; p = q; i++; //指针pr,p右移
}
cout << "右移了" << i << "个结点。" << endl;
}
(2) 指针p左移k个结点
template<class Type> void List<Type>,:
siftToLeft ( ListNode<Type> *& p,ListNode<Type> *& pr,int k ) {
if ( p == NULL && pr == first ) { //已经在链的最左端
cout << "已经在链的最左端，不能再左移。" << endl;
return;
}
int i = 0; ListNode<Type> *q;
while ( pr != NULL && i < k ) { //左移k个结点
q = pr->link; pr->link = p; //链指针pr->link逆转指向p
p = pr; pr = q; i++; //指针pr,p左移
}
cout << "左移了" << i << "个结点。" << endl;
if ( i < k ) { pr = p; p = NULL; } //指针p移出表外，重置p,pr
}
2-11 如果用循环链表表示一元多项式，试编写一个函数Polynomial,,Calc(x)，计算多项式在x处的值。
【解答】
下面给出表示多项式的循环链表的类定义。作为私有数据成员，在链表的类定义中封装了3个链接指针：first、last和current，分别指示链表的表头结点、链尾结点和最后处理到的结点。
enum Boolean { False,True }
class Polynomal; //多项式前视类定义
class Term { //项类定义
friend class Polynomal;
private,
double coef,expn; //系数与指数
Term *link; //项链接指针
public:
Term ( double c = 0,double e = 0,Term * next = NULL ), coef (c),expn(e),link (next) { }
}
class Polynomal { //多项式类定义
private,
Term *first,*current; //头指针,当前指针
int n; //多项式阶数
public,
Polynomal ( ); //构造函数
~Polynomal ( ); //析构函数
int Length ( ) const; //计算多项式项数
Boolean IsEmpty ( ) { return first->link == first; } //判是否零多项式
Boolean Find ( const double& value ); //在多项式中寻找其指数值等于value的项
double getExpn ( ) ( ) const; //返回当前项中存放的指数值
double getCoef ( ) ( ) const; //返回当前项中存放的系数值
void Firster ( ) { current = first; } //将当前指针置于头结点
Boolean First ( ); //将当前指针指向链表的第一个结点
Boolean Next ( ); //将当前指针指到当前结点的后继结点
Boolean Prior ( ); //将当前指针指到当前结点的前驱结点
void Insert ( const double coef,double expn ); //插入新结点
void Remove ( ); //删除当前结点
double Calc ( double x ); //求多项式的值
friend Polynomial operator + ( Polynomial &,Polynomial & );
friend Polynomial operator * ( Polynomial &,Polynomial & );
};
对于多项式Pn(x) = a0 + a1x + a2x2 + a3x3 + … + an-1xn-1 + anxn，可用Horner规则将它改写求值：
Pn(x) = a0 + (a1x + ( a2 + ( a3 + … + ( an-1 + an*x )*x … )*x )*x )*x
因为不是顺序表，必须采用递归算法实现：
double Polynomal,,Value ( Term *p,double x ) {
//私有函数：递归求子多项式的值
if ( p->link == first ) return p->coef;
else return p->coef + x * Value ( p->link,x );
}
double Polynomal,,Calc ( double x ) {
//共有函数：递归求多项式的值
Term * pc = first->link;
if ( pc == first ) cout << 0 << endl;
else cout << Value ( pc,x ) << endl;
}
但是，当多项式中许多项的系数为0时，变成稀疏多项式，如P50(x) = a0 + a13x13 + a35x35 + a50x50，为节省存储起见，链表中不可能保存有零系数的结点。此时，求值函数要稍加改变：
#include <math.h>
double Polynomal,,Value ( Term *p,double e,double x ) {
//私有函数：递归求子多项式的值。pow(x,y)是求x的y次幂的函数,它的原型在“math.h”中
if ( p->link == first ) return p->coef;
else return p->coef + pow( x,p->expn – e ) * Value ( p->link,p->expn,x );
}
double Polynomal,,Calc ( double x ) {
//共有函数：递归求多项式的值
Term * pc = first->link;
if ( pc == first ) cout << 0 << endl;
else cout << Value ( pc,0,x ) << endl;
}
2-12 设a和b是两个用带有表头结点的循环链表表示的多项式。试编写一个算法，计算这两个多项式的乘积c = a*b，要求计算后多项式a与b保持原状。如果这两个多项式的项数分别为n与m,试说明该算法的执行时间为O(nm2)或O(n2m)。但若a和b是稠密的,即其很少有系数为零的项,那么试说明该乘积算法的时间代价为O(nm)。
【解答】
假设
则它们的乘积为
例如，a = 1 + 2x + 3x2 + 4x3 + 5x4,b = 6 + 7x + 8x2 + 9x3,它们的乘积
c = (1+2x+3x2+4x3+5x4)*(6+7x+8x2+9x3) =
= 1*6 + (1*7+2*6)x +(1*8+2*7+3*6)x2+(1*9+2*8+3*7+4*6)x3+(2*9+3*8+4*7+5*6)x4+
+(3*9+4*8+5*7)x5+(4*9+5*8)x6+5*9x7
在求解过程中，固定一个ai，用它乘所有bj，得到xi+j的系数的一部分。这是一个二重循环。
i = 0,
i = 1,
i = 2,
i = 3,
i = 4,
根据以上思想得到的算法如下：
Polynomal& Polynomal,,operator * ( Polynomal& a,Polynomal& b ) {
Term * pa = a.first->link,pb,pc,fc; //pa与pb是两个多项式链表的检测指针
first = fc = pc = new Term; //fc是每固定一个ai时ai结点指针,pc是存放指针
while ( pa != NULL ) { //每一个ai与b中所有项分别相乘
pb = b.first->link;
while ( pb != NULL ) { //扫描多项式b所有项
temp = pa->data * pb->data; //计算ai * bj
if ( pc->link != NULL ) pc->link->data = pc->link->data + temp-> //累加
else pc->link = new Term (temp); //增加项,事实上,每次pa变化,链结点要随之增加
pc = pc->link; pb = pb->link;
}
pc = fc = fc->link; pa = pa->link; //处理多项式a 的下一ai
}
pc->link = NULL;
return *this;
}
这个算法有一个二重循环，内层循环中语句的重复执行次数是O(n*m)。其中，n是第一个多项式的阶数，m是第二个多项式的阶数。这是稠密多项式的情形。
对于稀疏多项式的情形请自行考虑。
2-13 计算多项式 Pn (x) = a0 xn + a1 xn-1 + a2 xn-2 + …… + an-1 x + an的值，通常使用的方法是一种嵌套的方法。它可以描述为如下的迭代形式：b0 = a0,bi+1 = x * bi + ai+1,i = 0,1,…,n-1。若设bn = pn （x）,则问题可以写为如下形式：Pn (x) = x * Pn-1 (x) + an,此处,Pn-1 (x) = a0 xn-1 + a1 xn-2 + …… + an-2 x + an-1，这是问题的递归形式。试编写一个递归函数，计算这样的多项式的值。
【解答】
如果用循环链表方式存储多项式，求解方法与3-7题相同。如果用数组方式存储多项式，当零系数不多时，可用顺序存放各项系数的一维数组存储多项式的信息，指数用数组元素的下标表示
0
1
2
3
i
n-2
n-1
Coef
a0
a1
a2
a3
…
ai
…
an-2
an-1
多项式的类定义如下：
struct Polynomal {
double * coef;
int n;
}
这样可得多项式的解法：
double Polynomal,,Value ( int i,double x ) {
//私有函数：递归求子多项式的值
if ( i == n-1 ) return coef[n-1];
else return coef[i] + x * Value ( i+1,x );
}
double Polynomal,,Calc ( double x ) {
//共有函数：递归求多项式的值
if ( n == 0 ) cout << 0 << endl;
else cout << Value ( 0,x ) << endl;
}
2-14 试设计一个实现下述要求的Locate运算的函数。设有一个带表头结点的双向链表L，每个结点有4个数据成员：指向前驱结点的指针prior、指向后继结点的指针next、存放数据的成员data和访问频度freq。所有结点的freq初始时都为0。每当在链表上进行一次Locate (L,x)操作时，令元素值为x的结点的访问频度freq加1，并将该结点前移，链接到与它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。
【解答】
#include <iostream.h>
//双向循环链表结点的构造函数
DblNode (Type value,DblNode<Type> *left,DblNode<Type> *right ),
data ( value ),freq ( 0 ),lLink ( left ),rLink ( right ) { }
DblNode (Type value ),
data ( value ),freq ( 0 ),lLink ( NULL ),rLink ( NULL ) { }
template <class Type>
DblList<Type>,,DblList ( Type uniqueVal ) {
first = new DblNode<Type>( uniqueVal );
first->rLink = first->lLink = first; //创建表头结点
current = NULL;
cout << "开始建立双向循环链表：\n";
Type value; cin >> value;
while ( value != uniqueVal ) { //每次新结点插入在表头结点后面
first->rLink = new DblNode<Type>( value,first,first->rLink );
cin >> value;
}
}
template <class Type>
void DblList<Type>,,Locate ( Type & x ) {
//定位
DblNode<Type> *p = first->rLink;
while ( p != first && p->data != x ) p = p->rLink;
if ( p != first ) { //链表中存在x
p→freq++; //该结点的访问频度加1
current = p; //从链表中摘下这个结点
current->lLink->rLink = current->rLink;
current->rLink->lLink = current->lLink;
p = current->lLink; //寻找从新插入的位置
while ( p != first && current->freq > p->freq )
p = p->lLink;
current->rLink = p->rLink; //插入在p之后
current->lLink = p;
p->rLink->lLink = current;
p->rLink = current;
}
else cout<<"Sorry,Not find!\n"; //没找到
}
2-15 利用双向循环链表的操作改写2-2题，解决约瑟夫(Josephus)问题。
【解答】
#include <iostream.h>
#include,DblList.h”
Template <class Type> void DblList <Type>,,Josephus ( int n,int m ) {
DblNode<Type> p = first,temp;
for ( int i = 0; i < n-1; i++ ) { //循环n-1趟，让n-1个人出列
for ( int j = 0; j < m-1; j++ ) p = p->rLink; //让p向后移动m-1次
cout <<,Delete person, << p->data << endl;
p->lLink->rLink = p->rLink; //从链中摘下p
p->rLink->lLink = p->lLink;
temp = p->rlink; delete p; p = temp; //删除p所指结点后,p改指下一个出发点
}
cout <<,The winner is, << p->data << endl;
}
void main ( ) {
DblList<int> dlist; //定义循环链表dlist并初始化
int n,m; //n是总人数，m是报数值
cout <<,Enter the Number of Contestants?”;
cin >> n >> m;
for ( int i = 1; i <= n; i++ ) dlist.insert (i); //建立数据域为1,2,… 的循环链表
dlist.Josephus (n,m); //解决约瑟夫问题，打印胜利者编号
}
2-16 试设计一个算法，改造一个带表头结点的双向链表，所有结点的原有次序保持在各个结点的rLink域中，并利用lLink域把所有结点按照其值从小到大的顺序连接起来。
【解答】
template<Type> void DblList<Type>,,sort ( ) {
DblNode<Type> *
s = first->link; //指针s指向待插入结点,初始时指向第一个结点
while ( s != NULL ) { //处理所有结点
pre = first; p = first->lLink; //指针p指向待比较的结点,pre是p的前驱指针
while ( p != NULL && s->data < p->data ) //循lLink链寻找结点 *s的插入位置
{ pre = p; p = p->lLink; }
pre->lLink = s; s->lLink = p; //结点 *s在lLink方向插入到 *pre与 *p之间
}
}
2-1 设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，……，如此反复直到所有的人全部出局为止。下面要解决的Josephus问题是：对于任意给定的n,s和m，求出这n个人的出局序列。请以n = 9,s = 1,m = 5为例，人工模拟Josephus的求解过程以求得问题的解。
【解答】
出局人的顺序为5,1,7,4,3,6,9,2,8。
2-2 试编写一个求解Josephus问题的函数。用整数序列1,2,3,……,n表示顺序围坐在圆桌周围的人，并采用数组表示作为求解过程中使用的数据结构。然后使用n = 9,s = 1,m = 5，以及n = 9,s = 1,m = 0，或者n = 9,s = 1,m = 10作为输入数据，检查你的程序的正确性和健壮性。最后分析所完成算法的时间复杂度。
【解答】函数源程序清单如下：
void Josephus( int A[ ],int n,s,m ) {
int i,j,k,tmp;
if ( m == 0 ) {
cout << "m = 0是无效的参数！" << endl;
return;
}
for ( i = 0; i < n; i++ ) A[i] = i + 1; /*初始化，执行n次*/
i = s - 1; /*报名起始位置*/
for ( k = n; k > 1; i-- ) { /*逐个出局，执行n-1次*/
if ( i == k ) i = 0;
i = ( i + m - 1 ) % k; /*寻找出局位置*/
if ( i != k-1 ) {
tmp = A[i]; /*出局者交换到第k-1位置*/
for ( j = i; j < k-1; j++ ) A[j] = A[j+1];
A[k-1] = tmp;
}
}
for ( k = 0; k < n / 2; k++ ) { /*全部逆置,得到出局序列*/
tmp = A[k]; A[k] = A[n-k+1]; A[n-k+1] = tmp;
}
}
例：n = 9,s = 1,m = 5
0
1
2
3
4
5
6
7
8
k = 9
1
2
3
4
5
6
7
8
9
第5人出局,i = 4
k = 8
1
2
3
4
6
7
8
9
5
第1人出局,i = 0
k = 7
2
3
4
6
7
8
9
1
5
第7人出局,i = 4
k = 6
2
3
4
6
8
9
7
1
5
第4人出局,i = 2
k = 5
2
3
6
8
9
4
7
1
5
第3人出局,i = 1
k = 4
2
6
8
9
3
4
7
1
5
第6人出局,i = 1
k = 3
2
8
9
6
3
4
7
1
5
第9人出局,i = 2
k = 2
2
8
9
6
3
4
7
1
5
第2人出局,i = 0
8
2
9
6
3
4
7
1
5
第8人出局,i = 0
逆置
5
1
7
4
3
6
9
2
8
最终出局顺序
例：n = 9,s = 1,m = 0
报错信息 m = 0是无效的参数！
例：n = 9,s = 1,m = 10
0
1
2
3
4
5
6
7
8
k = 9
1
2
3
4
5
6
7
8
9
第1人出局,i = 0
k = 8
2
3
4
5
6
7
8
9
1
第3人出局,i = 1
k = 7
2
4
5
6
7
8
9
3
1
第6人出局,i = 3
k = 6
2
4
5
7
8
9
6
3
1
第2人出局,i = 0
k = 5
4
5
7
8
9
2
6
3
1
第9人出局,i = 4
k = 4
4
5
7
8
9
2
6
3
1
第5人出局,i = 1
k = 3
4
7
8
5
9
2
6
3
1
第7人出局,i = 1
k = 2
4
8
7
5
9
2
6
3
1
第4人出局,i = 0
8
4
7
5
9
2
6
3
1
第8人出局,i = 0
逆置
1
3
6
2
9
5
7
4
8
最终出局顺序
当m = 1时，时间代价最大。达到( n-1 ) + ( n-2 ) + + 1 = n(n-1)/2 ( O(n2)。
2-3 设有一个线性表 (e0,e1,…,en-2,en-1) 存放在一个一维数组A[arraySize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容置换为 (en-1,en-2,…,e1,e0)。
【解答】
template<class Type> void inverse ( Type A[ ],int n ) {
Type tmp;
for ( int i = 0; i <= ( n-1 ) / 2; i++ ) {
tmp = A[i]; A[i] = A[n-i-1]; A[n-i-1] = tmp;
}
}
2-4 顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下,对有127个元素的顺序表进行插入,平均需要移动多少个元素? 删除一个元素,又平均需要移动多少个元素?
【解答】
若设顺序表中已有n = last+1个元素，last是顺序表的数据成员，表明最后表项的位置。又设插入或删除表中各个元素的概率相等，则在插入时因有n+1个插入位置(可以在表中最后一个表项后面追加)，每个元素位置插入的概率为1/(n+1)，但在删除时只能在已有n个表项范围内删除，所以每个元素位置删除的概率为1/n。
插入时平均移动元素个数AMN(Averagy Moving Number )为
删除时平均移动元素个数AMN为
2-5 利用顺序表的操作，实现以下的函数。
(1) 从顺序表中删除具有最小值的元素并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。
(2) 从顺序表中删除第i个元素并由函数返回被删元素的值。如果i不合理或顺序表为空则显示出错信息并退出运行。
(3) 向顺序表中第i个位置插入一个新的元素x。如果i不合理则显示出错信息并退出运行。
(4) 从顺序表中删除具有给定值x的所有元素。
(5) 从顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素，如果s或t不合理或顺序表为空则显示出错信息并退出运行。
(6) 从有序顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素，如果s或t不合理或顺序表为空则显示出错信息并退出运行。
(7) 将两个有序顺序表合并成一个新的有序顺序表并由函数返回结果顺序表。
(8) 从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。
【解答】
(1) 实现删除具有最小值元素的函数如下：
template<Type> Type SeqList<Type>,,DelMin ( ) {
if ( last == -1 ) //表空,中止操作返回
{ cerr <<, List is Empty!, << endl; exit(1); }
int m = 0; //假定0号元素的值最小
for ( int i = 1; i <= last; i++ ) { //循环,寻找具有最小值的元素
if ( data[i] < data[m] ) m = i; //让m指向当前具最小值的元素
Type temp = data[m];
//空出位置由最后元素填补,表最后元素位置减1
data[m] = data[last]; last--;
return temp;
}
(2) 实现删除第i个元素的函数如下(设第i个元素在data[i],i=0,1,(,last)：
template<Type> Type SeqList<Type>,,DelNo#i ( int i ) {
if ( last == -1 || i < 0 || i > last ) //表空,或i不合理,中止操作返回
{ cerr <<, List is Empty or Parameter is out range!, << endl; exit(1); }
Type temp = data[i]; //暂存第i个元素的值
for ( int j = i; j < last; j++ ) //空出位置由后续元素顺次填补
data[j] = data[j+1];
last--; //表最后元素位置减1
return temp;
}
(3) 实现向第i个位置插入一个新的元素x的函数如下(设第i个元素在data[i],i=0,1,(,last)：
template<Type> void SeqList<Type>,,InsNo#i ( int i,Type& x ) {
//表满或参数i不合理,中止操作返回
if ( last == MaxSize-1|| i < 0 || i > last+1 )
{ cerr <<, List is Full or Parameter is out range!, << endl; exit(1); }
//空出位置以便插入,若i=last+1,此循环不做
for ( int j = last; j >= i; j-- )
data[j+1] = data[j];
data[i] = x; //插入
last++; //表最后元素位置加1
}
(4) 从顺序表中删除具有给定值x的所有元素。
template<Type> void SeqList<Type>,,DelValue ( Type& x ) {
int i = 0,j;
while ( i <= last ) //循环,寻找具有值x的元素并删除它
if ( data[i] == x ) { //删除具有值x的元素,后续元素前移
for ( j = i; j < last; j++ ) data[j] = data[j+1];
last--; //表最后元素位置减1
}
else i++;
}
(5) 实现删除其值在给定值s与t之间（要求s小于t）的所有元素的函数如下：
template<Type> void SeqList<Type>,,DelNo#sto#t ( Type& s,Type& t ) {
if ( last == -1 || s >= t )
{ cerr <<,List is empty or parameters are illegal!” << endl; exit(1); }
int i = 0,j;
while ( i <= last ) //循环,寻找具有值x的元素并删除它
//删除满足条件的元素,后续元素前移
if ( data[i] >= s && data[i] <= t ) {
for ( j = i; j < last; j++ ) data[j] = data[j+1];
last--; //表最后元素位置减1
}
else i++;
}
(6) 实现从有序顺序表中删除其值在给定值s与t之间的所有元素的函数如下：
template<Type> void SeqList<Type>,,DelNo#sto#t1 ( Type& s,Type& t ) {
if ( last == -1 || s >= t )
{ cerr <<,List is empty or parameters are illegal!” << endl; exit(1); }
for ( int i = 0; i <= last; i++ ) //循环,寻找值 ≥s 的第一个元素
if ( data[i] >= s ) break; //退出循环时,i指向该元素
if ( i <= last ) {
for ( int j = 1; i + j <= last; j++ )//循环,寻找值 > t 的第一个元素
if ( data[i+j] > t ) break; //退出循环时,i+j指向该元素
//删除满足条件的元素,后续元素前移
for ( int k = i+j; k <= last; k++ )
data[k-j] = data[k];
last-= j; //表最后元素位置减j
}
}
(7) 实现将两个有序顺序表合并成一个新的有序顺序表的函数如下：
template<Type> SeqList<Type>& SeqList<Type>,,Merge ( SeqList<Type>& A,SeqList<Type>& B ) {
//合并有序顺序表A与B成为一个新的有序顺序表并由函数返回
if ( A.Length() + B.Length() > MaxSize )
{ cerr <<,The summary of The length of Lists is out MaxSize!” << endl; exit(1); }
Type value1 = A.Fist ( ),value2 = B.Fisrt ( );
int i = 0,j = 0,k = 0;
//循环,两两比较,小者存入结果表
while ( i < A.length ( ) && j < B.length ( ) ) {
if ( value1 <= value2 )
{ data[k] = value1; value1 = A.Next ( ); i++; }
else { data[k] = value2; value2 = B.Next ( ); j++; }
k++;
}
while ( i < A.Length ( ) ) //当A表未检测完,继续向结果表传送
{ data[k] = value1; value1 = A.Next ( ); i++; k++; }
while ( j < B.Length ( ) ) //当B表未检测完,继续向结果表传送
{ data[k] = value2; value2 = B.Next ( ); j++; k++; }
last = k – 1;
return *this;
}
(8) 实现从表中删除所有其值重复的元素的函数如下：
template<Type> void SeqList<Type>,,DelDouble ( ) {
if ( last == -1 )
{ cerr <<,List is empty!” << endl; exit(1); }
int i = 0,j,k; Type temp;
while ( i <= last ) { //循环检测
j = i + 1; temp = data[i];
while ( j <= last ) { //对于每一个i,重复检测一遍后续元素
if ( temp == data[j] ) { //如果相等,后续元素前移
for ( k = j+1; k <= last; k++ ) data[k-1] = data[k];
last--; //表最后元素位置减1
}
else j++;
}
i++; //检测完data[i],检测下一个
}
}
线性链表单链表的结点类(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
};
2-6线性表可用顺序表或链表存储。试问：
(1) 两种存储表示各有哪些主要优缺点?
(2) 如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？
(3) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？
【解答】
(1) 顺序存储表示是将数据元素存放于一个连续的存储空间中，实现顺序存取或(按下标)直接存取。它的存储效率高，存取速度快。但它的空间大小一经定义，在程序整个运行期间不会发生改变，因此，不易扩充。同时，由于在插入或删除时，为保持原有次序，平均需要移动一半(或近一半)元素，修改效率不高。
链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要存储器中还有空间，就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理顺序，只需要保持原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针，修改效率较高。但存取表中的数据元素时，只能循链顺序访问，因此存取效率不高。
(2) 如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用链接存储表示。
如果采用顺序存储表示，必须在一个连续的可用空间中为这n个表分配空间。初始时因不知道哪个表增长得快，必须平均分配空间。在程序运行过程中，有的表占用的空间增长得快，有的表占用的空间增长得慢；有的表很快就用完了分配给它的空间，有的表才用了少量的空间，在进行元素的插入时就必须成片地移动其他的表的空间，以空出位置进行插入；在元素删除时，为填补空白，也可能移动许多元素。这个处理过程极其繁琐和低效。
如果采用链接存储表示，一个表的存储空间可以连续，可以不连续。表的增长通过动态存储分配解决，只要存储器未满，就不会有表溢出的问题；表的收缩可以通过动态存储释放实现，释放的空间还可以在以后动态分配给其他的存储申请要求，非常灵活方便。对于n个表(包括表的总数可能变化)共存的情形，处理十分简便和快捷。所以选用链接存储表示较好。
(3) 应采用顺序存储表示。因为顺序存储表示的存取速度快，但修改效率低。若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时采用顺序存储表示较好。
2-7 针对带表头结点的单链表，试编写下列函数。
(1) 定位函数Locate：在单链表中寻找第i个结点。若找到，则函数返回第i个结点的地址；若找不到，则函数返回NULL。
(2) 求最大值函数max：通过一趟遍历在单链表中确定值最大的结点。
(3) 统计函数number：统计单链表中具有给定值x的所有元素。
(4) 建立函数create：根据一维数组a[n]建立一个单链表，使单链表中各元素的次序与a[n]中各元素的次序相同，要求该程序的时间复杂性为O(n)。
(5) 整理函数tidyup：在非递减有序的单链表中删除值相同的多余结点。
【解答】
(1) 实现定位函数的算法如下：
template <class Type> ListNode <Type> * List <Type>,,Locate ( int i ) {
//取得单链表中第i个结点地址,i从1开始计数,i <= 0时返回指针NULL
if ( i <= 0 ) return NULL; //位置i在表中不存在
ListNode <Type> * p = first; int k = 0; //从表头结点开始检测
while ( p != NULL && k < i ) { p = p->link; k++; } //循环,p == NULL表示链短,无第i个结点
return p; //若p != NULL,则k == i,返回第i个结点地址
}
(2) 实现求最大值的函数如下：
template <class Type> ListNode <Type> * List <Type>,,Max ( ) {
//在单链表中进行一趟检测，找出具有最大值的结点地址,如果表空,返回指针NULL
if ( first->link == NULL ) return NULL; //空表,返回指针NULL
ListNode <Type> * pmax = first->link,p = first->link->link; //假定第一个结点中数据具有最大值
while ( p != NULL ) { //循环,下一个结点存在
if ( p->data > pmax->data ) pmax = p; //指针pmax记忆当前找到的具最大值结点
p = p->link; //检测下一个结点
}
return pmax;
}
(3) 实现统计单链表中具有给定值x的所有元素的函数如下：
template <class Type> int List <Type>,,Count ( Type& x ) {
//在单链表中进行一趟检测，找出具有最大值的结点地址,如果表空,返回指针NULL
int n = 0;
ListNode <Type> * p = first->link; //从第一个结点开始检测
while ( p != NULL ) { //循环,下一个结点存在
if ( p->data == x ) n++; //找到一个,计数器加1
p = p->link; //检测下一个结点
}
return n;
}
(4) 实现从一维数组A[n]建立单链表的函数如下：
template <class Type> void List <Type>,,Create ( Type A[ ],int n ) {
//根据一维数组A[n]建立一个单链表，使单链表中各元素的次序与A[n]中各元素的次序相同
ListNode<Type> * p;
first = p = new ListNode<Type>; //创建表头结点
for ( int i = 0; i < n; i++ ) {
p->link = new ListNode<Type> ( A[i] ); //链入一个新结点,值为A[i]
p = p->link; //指针p总指向链中最后一个结点
}
p->link = NULL;
}
采用递归方法实现时，需要通过引用参数将已建立的单链表各个结点链接起来。为此，在递归地扫描数组A[n]的过程中，先建立单链表的各个结点，在退出递归时将结点地址p（被调用层的形参）带回上一层（调用层）的实参p->link。
template<Type> void List<Type>,,create ( Type A[ ],int n,int i,ListNode<Type> *& p ) {
//私有函数：递归调用建立单链表
if ( i == n ) p = NULL;
else { p = new ListNode<Type>( A[i] ); //建立链表的新结点
create ( A,n,i+1,p->link ); //递归返回时p->link中放入下层p的内容
}
}
template<Type> void List<Type>,,create ( Type A[ ],int n ) {
//外部调用递归过程的共用函数
first = current = new ListNode<Type>; //建立表头结点
create ( A,n,0,first->link ); //递归建立单链表
}
(5) 实现在非递减有序的单链表中删除值相同的多余结点的函数如下：
template <class Type> void List <Type>,,tidyup ( ) {
ListNode<Type> * p = first->link,temp; //检测指针,初始时指向链表第一个结点
while ( p != NULL && p->link != NULL ) //循环检测链表
if ( p->data == p->link->data ) { //若相邻结点所包含数据的值相等
temp = p->first; p->link = temp->link; //为删除后一个值相同的结点重新拉链
delete temp; //删除后一个值相同的结点
}
else p = p->link; //指针p进到链表下一个结点
}
2-8 设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针,试设计一个算法,将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其它的存储空间。表中允许有重复的数据。
【解答】
#include <iostream.h>
template <class Type> class List;
template <class Type> class ListNode {
friend class List<Type>;
public:
ListNode ( ); //构造函数
ListNode ( const Type& item ); //构造函数
private:
Type data;
ListNode<Type> *link;
};
template <class Type> class List {
public:
List ( const Type finishied ); //建立链表
void Browse ( ); //打印链表
void Merge ( List<Type> &hb ); //连接链表
private:
ListNode<Type> *first,*last;
};
//各成员函数的实现
template <class Type>
ListNode<Type>,,ListNode ( ), link ( NULL ) { }
//构造函数,仅初始化指针成员。
template <class Type> ListNode<Type>,,ListNode ( const Type & item ), data ( item ),link ( NULL ) { }
//构造函数,初始化数据与指针成员。
template <class Type> List<Type>,,List ( const Type finishied ) {
//创建一个带表头结点的有序单链表,finished是停止建表输入标志,是所有输入值中不可能出现的数值。
first = last = new ListNode<Type>( ); //创建表头结点
Type value; ListNode<Type> *p,*q,*s;
cin >> value;
while ( value != finished ) { //循环建立各个结点
s = new ListNode<Type>( value );
q = first; p = first->link;
while ( p != NULL && p->data <= value )
{ q = p; p = p->link; } //寻找新结点插入位置
q->link = s; s->link = p; //在q,p间插入新结点
if ( p == NULL ) last = s;
cin >> value;
}
}
template <class Type> void List<Type>,,Browse ( ) {
//浏览并输出链表的内容
cout<<"\nThe List is, \n";
ListNode<Type> *p = first->link;
while ( p != NULL ) {
cout << p->data;
if ( p != last ) cout << "->";
else cout << endl;
p = p->link;
}
}
template <class Type> void List <Type>,,Merge ( List<Type>& hb) {
//将当前链表this与链表hb按逆序合并，结果放在当前链表this中。
ListNode<Type> *pa,*pb,*q,*p;
pa = first->link; pb = hb.first->link; //检测指针跳过表头结点
first->link = NULL; //结果链表初始化
while ( pa != NULL && pb != NULL ) { //当两链表都未结束时
if ( pa->data <= pb->data )
{ q = pa; pa = pa->link; } //从pa链中摘下
else
{ q = pb; pb = pb->link; } //从pb链中摘下
q→link = first->link; first->link = q; //链入结果链的链头
}
p = ( pa != NULL )? pa, pb; //处理未完链的剩余部分
while ( p != NULL ) {
q = p; p = p->link;
q->link = first->link; first->link = q;
}
}
2-9 设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。
【解答1】
template<class Type> void List<Type>,,Inverse ( ) {
if ( first == NULL ) return;
ListNode<Type> *p = first->link,*pr = NULL;
while ( p != NULL ) {
first->link = pr; //逆转first指针
pr = first; first = p; p = p->link; //指针前移
}
first->link = pr;
}
【解答2】
template<class Type> void List<Type>,,Inverse ( ) {
ListNode<Type> *p,*head = new ListNode<Type> ( ); //创建表头结点,其link域默认为NULL
while ( first != NULL ) {
p = first; first = first->link; //摘下first链头结点
p->link = head->link; head->link = p; //插入head链前端
}
first = head->link; delete head; //重置first,删去表头结点
}
2-10 从左到右及从右到左遍历一个单链表是可能的，其方法是在从左向右遍历的过程中将连接方向逆转，如右图所示。在图中的指针p指向当前正在访问的结点，指针pr指向指针p所指结点的左侧的结点。此时，指针p所指结点左侧的所有结点的链接方向都已逆转。
(1) 编写一个算法，从任一给定的位置(pr,p)开始，将指针p右移k个结点。如果p移出链表，则将p置为0，并让pr停留在链表最右边的结点上。
(2) 编写一个算法，从任一给定的位置(pr,p)开始，将指针p左移k个结点。如果p移出链表，则将p置为0，并让pr停留在链表最左边的结点上。
【解答】
(1) 指针p右移k个结点
template<class Type> void List<Type>,,
siftToRight ( ListNode<Type> *& p,ListNode<Type> *& pr,int k ) {
if ( p == NULL && pr != first ) { //已经在链的最右端
cout << "已经在链的最右端，不能再右移。" << endl;
return;
}
int i; ListNode<Type> *q;
if ( p == NULL ) //从链头开始
{ i = 1; pr = NULL; p = first; } //重置p到链头也算一次右移
else i = 0;
while ( p != NULL && i < k ) { //右移k个结点
q = p->link; p->link = pr; //链指针p→link逆转指向pr
pr = p; p = q; i++; //指针pr,p右移
}
cout << "右移了" << i << "个结点。" << endl;
}
(2) 指针p左移k个结点
template<class Type> void List<Type>,:
siftToLeft ( ListNode<Type> *& p,ListNode<Type> *& pr,int k ) {
if ( p == NULL && pr == first ) { //已经在链的最左端
cout << "已经在链的最左端，不能再左移。" << endl;
return;
}
int i = 0; ListNode<Type> *q;
while ( pr != NULL && i < k ) { //左移k个结点
q = pr->link; pr->link = p; //链指针pr->link逆转指向p
p = pr; pr = q; i++; //指针pr,p左移
}
cout << "左移了" << i << "个结点。" << endl;
if ( i < k ) { pr = p; p = NULL; } //指针p移出表外，重置p,pr
}
2-11 如果用循环链表表示一元多项式，试编写一个函数Polynomial,,Calc(x)，计算多项式在x处的值。
【解答】
下面给出表示多项式的循环链表的类定义。作为私有数据成员，在链表的类定义中封装了3个链接指针：first、last和current，分别指示链表的表头结点、链尾结点和最后处理到的结点。
enum Boolean { False,True }
class Polynomal; //多项式前视类定义
class Term { //项类定义
friend class Polynomal;
private,
double coef,expn; //系数与指数
Term *link; //项链接指针
public:
Term ( double c = 0,double e = 0,Term * next = NULL ), coef (c),expn(e),link (next) { }
}
class Polynomal { //多项式类定义
private,
Term *first,*current; //头指针,当前指针
int n; //多项式阶数
public,
Polynomal ( ); //构造函数
~Polynomal ( ); //析构函数
int Length ( ) const; //计算多项式项数
Boolean IsEmpty ( ) { return first->link == first; } //判是否零多项式
Boolean Find ( const double& value ); //在多项式中寻找其指数值等于value的项
double getExpn ( ) ( ) const; //返回当前项中存放的指数值
double getCoef ( ) ( ) const; //返回当前项中存放的系数值
void Firster ( ) { current = first; } //将当前指针置于头结点
Boolean First ( ); //将当前指针指向链表的第一个结点
Boolean Next ( ); //将当前指针指到当前结点的后继结点
Boolean Prior ( ); //将当前指针指到当前结点的前驱结点
void Insert ( const double coef,double expn ); //插入新结点
void Remove ( ); //删除当前结点
double Calc ( double x ); //求多项式的值
friend Polynomial operator + ( Polynomial &,Polynomial & );
friend Polynomial operator * ( Polynomial &,Polynomial & );
};
对于多项式Pn(x) = a0 + a1x + a2x2 + a3x3 + … + an-1xn-1 + anxn，可用Horner规则将它改写求值：
Pn(x) = a0 + (a1x + ( a2 + ( a3 + … + ( an-1 + an*x )*x … )*x )*x )*x
因为不是顺序表，必须采用递归算法实现：
double Polynomal,,Value ( Term *p,double x ) {
//私有函数：递归求子多项式的值
if ( p->link == first ) return p->coef;
else return p->coef + x * Value ( p->link,x );
}
double Polynomal,,Calc ( double x ) {
//共有函数：递归求多项式的值
Term * pc = first->link;
if ( pc == first ) cout << 0 << endl;
else cout << Value ( pc,x ) << endl;
}
但是，当多项式中许多项的系数为0时，变成稀疏多项式，如P50(x) = a0 + a13x13 + a35x35 + a50x50，为节省存储起见，链表中不可能保存有零系数的结点。此时，求值函数要稍加改变：
#include <math.h>
double Polynomal,,Value ( Term *p,double e,double x ) {
//私有函数：递归求子多项式的值。pow(x,y)是求x的y次幂的函数,它的原型在“math.h”中
if ( p->link == first ) return p->coef;
else return p->coef + pow( x,p->expn – e ) * Value ( p->link,p->expn,x );
}
double Polynomal,,Calc ( double x ) {
//共有函数：递归求多项式的值
Term * pc = first->link;
if ( pc == first ) cout << 0 << endl;
else cout << Value ( pc,0,x ) << endl;
}
2-12 设a和b是两个用带有表头结点的循环链表表示的多项式。试编写一个算法，计算这两个多项式的乘积c = a*b，要求计算后多项式a与b保持原状。如果这两个多项式的项数分别为n与m,试说明该算法的执行时间为O(nm2)或O(n2m)。但若a和b是稠密的,即其很少有系数为零的项,那么试说明该乘积算法的时间代价为O(nm)。
【解答】
假设
则它们的乘积为
例如，a = 1 + 2x + 3x2 + 4x3 + 5x4,b = 6 + 7x + 8x2 + 9x3,它们的乘积
c = (1+2x+3x2+4x3+5x4)*(6+7x+8x2+9x3) =
= 1*6 + (1*7+2*6)x +(1*8+2*7+3*6)x2+(1*9+2*8+3*7+4*6)x3+(2*9+3*8+4*7+5*6)x4+
+(3*9+4*8+5*7)x5+(4*9+5*8)x6+5*9x7
在求解过程中，固定一个ai，用它乘所有bj，得到xi+j的系数的一部分。这是一个二重循环。
i = 0,
i = 1,
i = 2,
i = 3,
i = 4,
根据以上思想得到的算法如下：
Polynomal& Polynomal,,operator * ( Polynomal& a,Polynomal& b ) {
Term * pa = a.first->link,pb,pc,fc; //pa与pb是两个多项式链表的检测指针
first = fc = pc = new Term; //fc是每固定一个ai时ai结点指针,pc是存放指针
while ( pa != NULL ) { //每一个ai与b中所有项分别相乘
pb = b.first->link;
while ( pb != NULL ) { //扫描多项式b所有项
temp = pa->data * pb->data; //计算ai * bj
if ( pc->link != NULL ) pc->link->data = pc->link->data + temp-> //累加
else pc->link = new Term (temp); //增加项,事实上,每次pa变化,链结点要随之增加
pc = pc->link; pb = pb->link;
}
pc = fc = fc->link; pa = pa->link; //处理多项式a 的下一ai
}
pc->link = NULL;
return *this;
}
这个算法有一个二重循环，内层循环中语句的重复执行次数是O(n*m)。其中，n是第一个多项式的阶数，m是第二个多项式的阶数。这是稠密多项式的情形。
对于稀疏多项式的情形请自行考虑。
2-13 计算多项式 Pn (x) = a0 xn + a1 xn-1 + a2 xn-2 + …… + an-1 x + an的值，通常使用的方法是一种嵌套的方法。它可以描述为如下的迭代形式：b0 = a0,bi+1 = x * bi + ai+1,i = 0,1,…,n-1。若设bn = pn （x）,则问题可以写为如下形式：Pn (x) = x * Pn-1 (x) + an,此处,Pn-1 (x) = a0 xn-1 + a1 xn-2 + …… + an-2 x + an-1，这是问题的递归形式。试编写一个递归函数，计算这样的多项式的值。
【解答】
如果用循环链表方式存储多项式，求解方法与3-7题相同。如果用数组方式存储多项式，当零系数不多时，可用顺序存放各项系数的一维数组存储多项式的信息，指数用数组元素的下标表示
0
1
2
3
i
n-2
n-1
Coef
a0
a1
a2
a3
…
ai
…
an-2
an-1
多项式的类定义如下：
struct Polynomal {
double * coef;
int n;
}
这样可得多项式的解法：
double Polynomal,,Value ( int i,double x ) {
//私有函数：递归求子多项式的值
if ( i == n-1 ) return coef[n-1];
else return coef[i] + x * Value ( i+1,x );
}
double Polynomal,,Calc ( double x ) {
//共有函数：递归求多项式的值
if ( n == 0 ) cout << 0 << endl;
else cout << Value ( 0,x ) << endl;
}
2-14 试设计一个实现下述要求的Locate运算的函数。设有一个带表头结点的双向链表L，每个结点有4个数据成员：指向前驱结点的指针prior、指向后继结点的指针next、存放数据的成员data和访问频度freq。所有结点的freq初始时都为0。每当在链表上进行一次Locate (L,x)操作时，令元素值为x的结点的访问频度freq加1，并将该结点前移，链接到与它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。
【解答】
#include <iostream.h>
//双向循环链表结点的构造函数
DblNode (Type value,DblNode<Type> *left,DblNode<Type> *right ),
data ( value ),freq ( 0 ),lLink ( left ),rLink ( right ) { }
DblNode (Type value ),
data ( value ),freq ( 0 ),lLink ( NULL ),rLink ( NULL ) { }
template <class Type>
DblList<Type>,,DblList ( Type uniqueVal ) {
first = new DblNode<Type>( uniqueVal );
first->rLink = first->lLink = first; //创建表头结点
current = NULL;
cout << "开始建立双向循环链表：\n";
Type value; cin >> value;
while ( value != uniqueVal ) { //每次新结点插入在表头结点后面
first->rLink = new DblNode<Type>( value,first,first->rLink );
cin >> value;
}
}
template <class Type>
void DblList<Type>,,Locate ( Type & x ) {
//定位
DblNode<Type> *p = first->rLink;
while ( p != first && p->data != x ) p = p->rLink;
if ( p != first ) { //链表中存在x
p→freq++; //该结点的访问频度加1
current = p; //从链表中摘下这个结点
current->lLink->rLink = current->rLink;
current->rLink->lLink = current->lLink;
p = current->lLink; //寻找从新插入的位置
while ( p != first && current->freq > p->freq )
p = p->lLink;
current->rLink = p->rLink; //插入在p之后
current->lLink = p;
p->rLink->lLink = current;
p->rLink = current;
}
else cout<<"Sorry,Not find!\n"; //没找到
}
2-15 利用双向循环链表的操作改写2-2题，解决约瑟夫(Josephus)问题。
【解答】
#include <iostream.h>
#include,DblList.h”
Template <class Type> void DblList <Type>,,Josephus ( int n,int m ) {
DblNode<Type> p = first,temp;
for ( int i = 0; i < n-1; i++ ) { //循环n-1趟，让n-1个人出列
for ( int j = 0; j < m-1; j++ ) p = p->rLink; //让p向后移动m-1次
cout <<,Delete person, << p->data << endl;
p->lLink->rLink = p->rLink; //从链中摘下p
p->rLink->lLink = p->lLink;
temp = p->rlink; delete p; p = temp; //删除p所指结点后,p改指下一个出发点
}
cout <<,The winner is, << p->data << endl;
}
void main ( ) {
DblList<int> dlist; //定义循环链表dlist并初始化
int n,m; //n是总人数，m是报数值
cout <<,Enter the Number of Contestants?”;
cin >> n >> m;
for ( int i = 1; i <= n; i++ ) dlist.insert (i); //建立数据域为1,2,… 的循环链表
dlist.Josephus (n,m); //解决约瑟夫问题，打印胜利者编号
}
2-16 试设计一个算法，改造一个带表头结点的双向链表，所有结点的原有次序保持在各个结点的rLink域中，并利用lLink域把所有结点按照其值从小到大的顺序连接起来。
【解答】
template<Type> void DblList<Type>,,sort ( ) {
DblNode<Type> *
s = first->link; //指针s指向待插入结点,初始时指向第一个结点
while ( s != NULL ) { //处理所有结点
pre = first; p = first->lLink; //指针p指向待比较的结点,pre是p的前驱指针
while ( p != NULL && s->data < p->data ) //循lLink链寻找结点 *s的插入位置
{ pre = p; p = p->lLink; }
pre->lLink = s; s->lLink = p; //结点 *s在lLink方向插入到 *pre与 *p之间
}
}
