第2章数组 第2章数组 作为抽象数据类型数组的类声明。 #include <iostream h> 在头文件“ array. h”中 const int DefaultS ize =30: template <class Type> class array i ∥数组是数据类型相同的n(sie)个元素的一个集合,下标范围从0到n-1。对数组中元素 ∥可按下标所指示位置直接访问 Type’ elements; /数组 int Array Size: ∥元素个数 public Array int Size DefaultSsize ) ∥构造函数 ∥复制构造函数 -Array (i delete elements; 3 ∥析构函数 Amay<Iype>& operator=( const array<Iype>&A);∥数组整体赋值(复制) Type& operator [( int 1 ) ∥按下标访问数组元素 int Length()const( return Array Size; 3 ∥取数组长度 void Resize( int Sz ) ∥修改数组长度 顺序表的类定义 ∥定义在头文件“ seqlist. h #include <stdlib h> template <class Type> class Seqlist i private: ∥顺序表的存放数组 int MaxSize. ∥顺序表的最大可容纳项数 int last: ∥顺序表当前已存表项的最后位置 顺序表的当前指针(最近处理的表项) Seqlist( int MaxSize ) ∥构造函数 -Seqlist (i delete []data; 3 ∥析构函数 int Length()const i return last+1;) 计算表长度 int Find( Type& x )const; ∥定位函数:找x在表中位置,置为当前表项 int IsIn( Type& x ) ∥判断x是否在表中,不置为当前表项 Type* GetData(){ return current=-1?NULL: data[ curren;}∥取当前表项的值 插入x在表中当前表项之后,置为当前表项 int Append Type& x 加x到表尾,置为当前表项 Type Remove( Type& x) ∥删除x,置下一表项为当前表项 Type* First (; 取表中第一个表项的值,置为当前表项
第 2 章 数组 9 第 2 章 数组 作为抽象数据类型数组的类声明。 #include <iostream.h> //在头文件“array.h”中 #include <stdlib.h> const int DefaultSize = 30; template <class Type> class Array { //数组是数据类型相同的 n（size）个元素的一个集合, 下标范围从 0 到 n-1。对数组中元素 //可按下标所指示位置直接访问。 private: Type *elements; //数组 int ArraySize; //元素个数 public: Array ( int Size = DefaultSize ); //构造函数 Array ( const Array<Type> & x ); //复制构造函数 ~Array ( ) { delete [ ] elements; } //析构函数 Array<Type> & operator = ( const Array<Type> & A ); //数组整体赋值 (复制) Type& operator [ ] ( int i ); //按下标访问数组元素 int Length ( ) const { return ArraySize; } //取数组长度 void ReSize ( int sz ); //修改数组长度 } 顺序表的类定义 #include < iostream.h> //定义在头文件“seqlist.h”中 #include <stdlib.h> template <class Type> class SeqList { private: Type *data; //顺序表的存放数组 int MaxSize; //顺序表的最大可容纳项数 int last; //顺序表当前已存表项的最后位置 int current; //顺序表的当前指针（最近处理的表项） public: SeqList ( int MaxSize ); //构造函数 ~SeqList ( ) { delete [ ] data; } //析构函数 int Length ( ) const { return last+1; } //计算表长度 int Find ( Type& x ) const; //定位函数: 找 x 在表中位置，置为当前表项 int IsIn ( Type& x ); //判断 x 是否在表中，不置为当前表项 Type *GetData ( ) { return current == -1？NULL : data[current]; } //取当前表项的值 int Insert ( Type& x ); //插入 x 在表中当前表项之后，置为当前表项 int Append ( Type& x ); //追加 x 到表尾，置为当前表项 Type * Remove ( Type& x ); //删除 x，置下一表项为当前表项 Type * First ( ); //取表中第一个表项的值，置为当前表项
第2章数组 Type* Next (i return current last? &data[++current]: NULL; J ∥取当前表项的后继表项的值,置为当前表项 Type Prior(i return current >0? &datal--current: NULL; 3 取当前表项的前驱表项的值,置为当前表项 int Is Empty (i return last ==-1; ∥判断顺序表空否,空则返回1;否则返回 int IsFull(){ return last= Maxsize-l;}∥判断顺序表满否,满则返回1;否则返回0 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[l, int n, s, m )i int i,j, k, tmp; if(m=0){ out<<"m=0是无效的参数!"<<endl for(i=0;1<n;H+)A[=i+1; 初始化,执行n次* 报名起始位置* for(k=n;k>I; i--)( 逐个出局,执行n1次*/ /寻找出局位置* f(il=k-1){ tmp=A[]; 出局者交换到第k-1位置* for(j=i;j<k-1; j++)ADJ=A[+1]: Ak-1= tmp; for(k=0;k<n/2;k++){ /全部逆置,得到出局序列* tmp=ak]: akk]=A[n-k+1: A[n-k+1]=tmp 例:n=9,s=1,m=5
第 2 章 数组 10 Type * Next ( ) { return current < last ? &data[++current] : NULL; } //取当前表项的后继表项的值，置为当前表项 Type * Prior ( ) { return current > 0 ? &data[--current] : NULL; } //取当前表项的前驱表项的值，置为当前表项 int IsEmpty ( ) { return last == -1; } //判断顺序表空否, 空则返回 1; 否则返回 0 int IsFull ( ) { return last == MaxSize-1; } //判断顺序表满否, 满则返回 1; 否则返回 0 } 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
第2章数组 6789第5人出局 9[5第1人出局,i=0 k=7「2346 895第7人出局,i=4 k=6「2346 k=5236|8 678933333 第 人出局,i=2 第 43 人出局 k=4268|9 第6人出局,i=1 k=32896 第9人出局,i=2 k=228‖9|6 第2人出局,i=0 8‖296 71|5第8人出局,i=0 逆置 928最终出局顺序 报错信息m=0是无效的参数! 例:n=9,s=1,m=10 3456789第1人出局,i=0 第3人出局,i=1 k=72456789‖3 第6人出局,i=3 k=624578963 第2人出局,i=0 k=545789 第9人出局,i k=44 78 第5人出局, k=3 第7人出局, k=2 第4人出局,i=0 第8人出局,i=0 逆置 148最终出局顺序 当m=1时,时间代价最大。达到(n-1)+(n-2)+…+1=n(n-1)2≈O(n2)。 3设有一个线性表(eo,el,…,en2,c1)存放在一个一维数组 A[array Size]中的前n个数组元素位置。 请编写一个函数将这个线性表原地逆置,即将数组的前n个原址内容置换为(cnl,cen2,…;,el,eo)。 【解答】 template<class Type> void inverse( Type Al int n)( for(inti=0;i<=(n-1)/2;i++){ tmp =AO: A0=An-i-1: An-i-1=tmp; 2-4假定数组A[ array Size]中有多个零元素,试写出一个函数,将A中所有的非零元素依次移到数组A 的前端A[](0≤i≤ array Size) 【解答】 因为数组是一种直接存取的数据结构,在数组中元素不是像顺序表那样集中存放于表的前端,而 是根据元素下标直接存放于数组某个位置,所以将非零元素前移时必须检测整个数组空间,并将后面 变成零元素的空间清零。函数中设置一个辅助指针free,指示当前可存放的位置,初值为0。 template<class Type> void Array <Type> : compact( )i int free =0
第 2 章 数组 11 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 假定数组A[arraySize]中有多个零元素, 试写出一个函数, 将A 中所有的非零元素依次移到数组A 的前端 A[i]（0 i arraySize）。 【解答】 因为数组是一种直接存取的数据结构，在数组中元素不是像顺序表那样集中存放于表的前端，而 是根据元素下标直接存放于数组某个位置，所以将非零元素前移时必须检测整个数组空间，并将后面 变成零元素的空间清零。函数中设置一个辅助指针 free，指示当前可存放的位置，初值为 0。 template<class Type> void Array<Type> :: compact( ) { int free = 0;
第2章数组 for( int i=0; i <Array Size; i++) ∥检测整个数组 if( elements[I=0) ∥发现非零元素 [elements[free]=elements[i]: free++; elements]=0;) E 5顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下,对有127个元素的 顺序表进行插入,平均需要移动多少个元素?删除一个元素,又平均需要移动多少个元素? 【解答】 若设顺序表中已有n=last+1个元素,last是顺序表的数据成员,表明最后表项的位置。又设插入 或删除表中各个元素的概率相等,则在插入时因有n+1个插入位置(可以在表中最后一个表项后面追 加),每个元素位置插入的概率为1/(n+1),但在删除时只能在已有n个表项范围内删除,所以每个元 素位置删除的概率为1/ 插入时平均移动元素个数 AMN(Averagy Moving Number)为 AMN=∑(n-i-1)=(n-1)+(n-2)+…+1+0) I(n-1)n n-1 2 删除时平均移动元素个数AMN为 AMN= (n+(n-1)+…+1+0) I n(n +I)n n+1 n+1 2-6若矩阵Am中的某一元素A]]是第i行中的最小值,同时又是第j列中的最大值,则称此元素 为该矩阵的一个鞍点。假设以二维数组存放矩阵,试编写一个函数,确定鞍点在数组中的位置(若鞍 点存在时),并分析该函数的时间复杂度 【解答】 int minmax( int A[[, const int m, const int n )( ∥在二维数组Am][n中求所有鞍点,它们满足在行中最小同时在列中最大 int *row new int[m: int*col new int[n] for(i=0; i< m; i++) ∥在各行中选最小数组元素,存于row for(j=1:j<n;j++) if(aoo < row )row=AO0; for(j=0;j<n;++){ ∥在各列中选最大数组元素,存于co ColI=A[]; for(i=1; i<m; i++) if(A0 col[])colD=Ajol for(i=0;i<m;计++) 检测矩阵,寻找鞍点并输出其位置 for(j=0;j<n;j++) if(ro=co)cout<<" The saddle point is:(≤i<“”<j<")”<endl delete [row: delete[ col 此算法有3个并列二重循环,其时间复杂度为Om×n)
第 2 章 数组 12 for ( int i = 0; i < ArraySize; i++ ) //检测整个数组 if ( elements[I] != 0 ) //发现非零元素 { elements[free] = elements[i]; free++; elements[i] = 0; } //前移 } 2-5 顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下, 对有 127 个元素的 顺序表进行插入, 平均需要移动多少个元素? 删除一个元素, 又平均需要移动多少个元素? 【解答】 若设顺序表中已有 n = last+1 个元素，last 是顺序表的数据成员，表明最后表项的位置。又设插入 或删除表中各个元素的概率相等，则在插入时因有 n+1 个插入位置(可以在表中最后一个表项后面追 加)，每个元素位置插入的概率为 1/(n+1)，但在删除时只能在已有 n 个表项范围内删除，所以每个元 素位置删除的概率为 1/n。 插入时平均移动元素个数 AMN(Averagy Moving Number )为 删除时平均移动元素个数 AMN 为 2-6 若矩阵 Amn 中的某一元素 A[i][j]是第 i 行中的最小值，同时又是第 j 列中的最大值，则称此元素 为该矩阵的一个鞍点。假设以二维数组存放矩阵，试编写一个函数，确定鞍点在数组中的位置（若鞍 点存在时），并分析该函数的时间复杂度。 【解答】 int minmax ( int A[ ][ ], const int m, const int n ) { //在二维数组 A[m][n]中求所有鞍点, 它们满足在行中最小同时在列中最大 int *row = new int[m]; int * col = new int[n]; int i, j; for ( i = 0; i < m; i++ ) { //在各行中选最小数组元素, 存于 row[i] row[i] = A[i][0]; for ( j = 1; j < n; j++ ) if ( A[i][j] < row[i] ) row[i] = A[i][j]; } for ( j = 0; j < n; j++ ) { //在各列中选最大数组元素, 存于 col[j] col[i] = A[0][j]; for ( i = 1; i < m; i++ ) if ( A[i][j] > col[j] ) col[j] = A[i][j]; } for ( i = 0; i < m; i++ ) { //检测矩阵，寻找鞍点并输出其位置 for ( j = 0; j < n; j++ ) if ( row[i] == col[j] ) cout << “The saddle point is : (” << i << “, ” << j << “)” << endl; delete [ ] row; delete [ ] col; } 此算法有 3 个并列二重循环，其时间复杂度为 O(mn)。 ( ) 2 n 2 n(n 1) n 1 1 (n (n 1) 1 0) n 1 1 n i n 1 1 AMN n i 0 = + + + − + + + = + − = + = = − = − = − = − − = − + − + + + = 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
第2章数组 2-7设有一个二维数组A[m]n,假设A[O0]存放位置在644(10,A[22]存放位置在67610),每个元 素占一个空间,问A[3][30存放在什么位置?脚注0表示用10进制表示。 【解答】 设数组元素A[[存放在起始地址为Loc(i,j)的存储单元中 Loc(2,2)=Loc(0,0)+2*n+2=644+2*n+2=676 ∴n=(676-2-644)/2=15 Loc(3,3)=Loc(0,0)+3*15+3=644+45+3=692. 2-8利用顺序表的操作,实现以下的函数。 (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>: DeMin(i if las ∥表空,中止操作返回 cr<<“ List is Empty!”<<end;exit(1);} ∥假定0号元素的值最小 for( int i= 1; i<=last; i++) 循环,寻找具有最小值的元素 if( data data[m))m=i: ∥让m指向当前具最小值的元素 Type temp data[m] data m=data[last ]; last-; ∥空出位置由最后元素填补,表最后元素位置减 (2)实现删除第i个元素的函数如下(设第i个元素在data],i=0,1,,last) template<Type> Type SeqList<Type>: DeINofi(int i)i if(last==-1 ll i<0 ll i>last ∥表空,或i不合理,中止操作返回 i cerr <<"List is Empty or Parameter is out range! < endl; exit(1);3 Type temp data ∥暂存第i个元素的值 for( int j=i; j ∥空出位置由后续元素顺次填补 ∥表最后元素位置减1 return temp:
第 2 章 数组 13 2-7 设有一个二维数组 A[m][n]，假设 A[0][0]存放位置在 644(10)，A[2][2]存放位置在 676(10)，每个元 素占一个空间，问 A[3][3](10)存放在什么位置？脚注(10)表示用 10 进制表示。 【解答】 设数组元素 A[i][j]存放在起始地址为 Loc ( i, j ) 的存储单元中。 ∵ Loc ( 2, 2 ) = Loc ( 0, 0 ) + 2 * n + 2 = 644 + 2 * n + 2 = 676. ∴ n = ( 676 - 2 - 644 ) / 2 = 15 ∴ Loc ( 3, 3 ) = Loc ( 0, 0 ) + 3 * 15 + 3 = 644 + 45 + 3 = 692. 2-8 利用顺序表的操作，实现以下的函数。 (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]; data[m] = data[last]; last--; //空出位置由最后元素填补, 表最后元素位置减 1 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; }