顺序表表 2-1设n个人围坐在一个圆桌周围,现在从第s个人开始报数,数到第m个人,让他出局 然后从出局的下一个人重新开始报数,数到第m个人,再让他出局,……,如此反复直到 所有的人全部出局为止。下面要解决的 Josephus问题是:对于任意给定的n,s和m,求 出这n个人的出局序列。请以n=9,s=1,m=5为例,人工模拟 Josephus的求解过 程以求得问题的解。 解答】 出局人的顺序为5,1 3,6,9,2,8 2-2试编写一个求解 Josephus问题的函数。用整数序列1,2,3,……,n表示顺序围坐 在圆桌周围的人,并采用数组表示作为求解过程中使用的数据结构。然后使用n=9,s= l,m=5,以及n=9,s=1,m=0,或者n=9,s=1,m=10作为输入数据,检 查你的程序的正确性和健壮性。最后分析所完成算法的时间复杂度 【解答】函数源程序清单如下 id Josephus( int A[], int int 0){ cout<"m=0是无效的参数!"<<end1; for(i=0;i<n;i艹)A[i]=i+1;/*初始化,执行n次* /*报名起始位置* for(k /*逐个出局,执行n-1次*/ if i=(i+m-1)%k; /*寻找出局位置*/ if k-1){ tmp Ali] /*出局者交换到第k-1位置*/ for(j=i;j<k-l: j++)alj] ALj+1]: for(k=0;k<n/2;k++) /*全部逆置,得到出局序列*/ tmp = A[k]: A[k]=A[n-k+1]: A[n-k+1]=tmp; 9
5 顺序表表 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
6789第5人出局,i=4 5第1人出局,i=0 kkkk 8915第7人出局,i=4 689715第4人出局,i 第3人出局,i=1 k =三 第6人出局,i=1 第9人出局,i=2 第2人出局,i=0 第8人出局,i=0 逆置 最终出局顺序 例:n=9, 报错信息m=0是无效的参数 例 9, 「23456789第1人出局,i=0 k=8 第3人出局,i=1 第6人出局 k=6 第2人出局,i=0 第9人出局,i=4 333334 第5人出局,i=1 第7人出局,i=1 第4人出局,i=0 第8人出局,i=0 逆置 3|629 最终出局顺序 当m=1时,时间代价最大。达到(n-1)+(n-2)+…+1=n(n-1)/2≈0(n2)。 2-3设有一个线性表(eo,en,…,en2,en-)存放在一个一维数组A[ arraySize]中的前n 个数组元素位置。请编写一个函数将这个线性表原地逆置,即将数组的前n个原址内容置 换为(en,en2 【解答】 template<class Type>void inverse( Type a[ ], int n T ype tm for(inti=0;i<=(n-1)/2;i++) tmp Ali]: A[i] A[n-i-1]: A[n-i-1= tmp 2-4顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下,对有 127个元素的顺序表进行插入,平均需要移动多少个元素?删除一个元素,又平均需要移 动多少个元素? 【解答 若设顺序表中已有n=last+1个元素,last是顺序表的数据成员,表明最后表项的 位置。又设插入或删除表中各个元素的概率相等,则在插入时因有n+1个插入位置(可以 AMN=I 1)=n(n-1)+(m-2)+…+1+0)=1-=n-1
6 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 个插入位置(可以 − = − = − = − − = − + − + + + = n 1 i 0 2 n 1 2 (n 1)n n 1 ((n 1) (n 2) 1 0) n 1 (n i 1) n 1 AMN
在表中最后一个表项后面追加),每个元素位置插入的概率为1/(n+1),但在删除时只能 在已有n个表项范围内删除,所以每个元素位置删除的概率为1/n 插入时平均移动元素个数AMN( Averagy Moving Number)为 删除时平均移动元素个数AMN为 2-5利用顺序表的操作,实现以下的函数。 (1)从顺序表中删除具有最小值的元素并由函数返回被删元素的值。空出的位置由最 后一个元素填补,若顺序表为空则显示出错信息并退出运行。 (2)从顺序表中删除第ⅰ个元素并由函数返回被删元素的值。如果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<T ype>Type Seqlist<Type>:: DelMin() if( last ==-1 //表空,中止操作返回 cerr<“ List is Empty!”<endl;exit(1); //假定0号元素的值最小 for(inti=l;i<=last;i+-){/循环,寻找具有最小值的元素 if(data[i]<data匚m)m=i;//让m指向当前具最小值的元素 Type temp data[m] /空出位置由最后元素填补,表最后元素位置减1 data[m datallast]: last- return temp (2)实现删除第i个元素的函数如下(设第i个元素在data[i],i=0,1,…,ast) template<Type Type Seqlist<Type>:: De lNo#i( int i if last <0|li>last)//表空,或i不合理,中止操作返回 cerr<<" List is Empty or Parameter is out range! "< endl; exit(1) Type temp data[i] //暂存第i个元素的值 for(intj=i;j<last;j+)//空出位置由后续元素顺次填补 datalj] data[j+1] //表最后元素位置减1 turn temp: (3)实现向第i个位置插入一个新的元素x的函数如下(设第i个元素在data[i]
7 在表中最后一个表项后面追加)，每个元素位置插入的概率为 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]
0,1,,last): template<Type >void Seqlist<Type>:: Ins No#i int i, Type&x)i //表满或参数i不合理,中止操作返回 if last = MaxSize-1 0 last+l i cerr<<" List is Full or Parameter is out range! "< end l; exit(1) /空出位置以便插入,若i=last+1,此循环不做 for( int j= last: j>=i:j-) data[计+1]=data[j; datai] =X //插入 last+ //表最后元素位置加 (4)从顺序表中删除具有给定值x的所有元素。 template<Type >void Seqlist<Type>:: Delvalue( Type&x)i int i =0, j: while(i<= last /循环,寻找具有值x的元素并删除它 if( datai] ==x) //删除具有值x的元素,后续元素前移 for(j=i: j< last: j++)data[j]= data[j+1] //表最后元素位置减1 else 1+t: (5)实现删除其值在给定值s与t之间(要求s小于t)的所有元素的函数如下 template<t ype>void SeqList<Type>:: DelNo#sto#t( Type& s, Type&t) if( last ==-1 i cerr << "List is empty or parameters are illegal! "< endl: exit(1) 0 while( i<= last //循环,寻找具有值x的元素并删除它 //删除满足条件的元素,后续元素前移 if( datalil >=s&& data[i]<=t)i for(j=i: j< last: j++)data[j] data[j+1] last //表最后元素位置减1 lse i+ (6)实现从有序顺序表中删除其值在给定值s与t之间的所有元素的函数如下: template<Type>void SeqList<Type>:: DelNo#sto#t1( Type& s, Type& t)[ f la cerr < "List is empty or parameters are illegal! "< endl; exit(1) for(inti=0;i<=last;i++)//循环,寻找值≥s的第一个元素 if( datai >=s)break //退出循环时,i指向该元素 if (i < last)( for(intj=1;i+j<=last;j+)//循环,寻找值〉t的第一个元素 if data[i+j] >t) break //退出循环时,ij指向该元素 //删除满足条件的元素,后续元素前移
8 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 指向该元素 //删除满足条件的元素, 后续元素前移
t k= i+j: k < last; k++) datalk-j] datalk] /表最后元素位置减j (7)实现将两个有序顺序表合并成一个新的有序顺序表的函数如下: template<Type> Seglist<Type>& Seglist<Type>:: Merge( SeqList<Type>&A, Seqlist<Type〉&B){ //合并有序顺序表A与B成为一个新的有序顺序表并由函数返回 if( A Length+B Length> MaxSize I cerr <<"The summary of The length of Lists is out MaxSize! "< endl Type valuel =A Fist () value2 = B Fisrt () int 1= /循环,两两比较,小者存入结果表 while( i< A length()&&j< B length()) if( valuel value2 data[k]= valuel: valuel = A. Next ()i i++ y else i data[k]= value2: value2 = B Next () j++ I k++; while(i< A Length ()) //当A表未检测完,继续向结果表传送 data[]= valuel: valuel =A. Next () i++ k++ while(j< B Length()) /当B表未检测完,继续向结果表传送 i datalk] =value2: value2=B Next () j++ k++ return this (8)实现从表中删除所有其值重复的元素的函数如下 template<T ype>void SeqList<Type>:: DelDouble()i if last ==-1) I cerr<< "List is empty! "< endl: exit(1) int i=0, j, k: Type temp ile( i ( last) //循环检测 j=i+l: temp data[i]: while(j<= last) //对于每一个i,重复检测一遍后续元素 if(temp==data[j]){//如果相等,后续元素前移 for(k=j+l: k<= last; k++)data[k-1]=datalk] last //表最后元素位置减1 //检测完data[i],检测下一个
9 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], 检测下一个 }