第2章数组 第2章数组 作为抽象数据类型数组的类声明。 #include 在头文件“ array. h”中 const int DefaultS ize =30: template class array i ∥数组是数据类型相同的n(sie)个元素的一个集合,下标范围从0到n-1。对数组中元素 ∥可按下标所指示位置直接访问 Type’ elements; /数组 int Array Size: ∥元素个数 public Array int Size DefaultSsize ) ∥构造函数 ∥复制构造函数 -Array (i delete elements; 3 ∥析构函数 Amay& operator=( const array&A);∥数组整体赋值(复制) Type& operator [( int 1 ) ∥按下标访问数组元素 int Length()const( return Array Size; 3 ∥取数组长度 void Resize( int Sz ) ∥修改数组长度 顺序表的类定义 ∥定义在头文件“ seqlist. h #include template 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 //在头文件“array.h”中 #include const int DefaultSize = 30; template class Array { //数组是数据类型相同的 n（size）个元素的一个集合, 下标范围从 0 到 n-1。对数组中元素 //可按下标所指示位置直接访问。 private: Type *elements; //数组 int ArraySize; //元素个数 public: Array ( int Size = DefaultSize ); //构造函数 Array ( const Array & x ); //复制构造函数 ~Array ( ) { delete [ ] elements; } //析构函数 Array & operator = ( const Array & A ); //数组整体赋值 (复制) Type& operator [ ] ( int i ); //按下标访问数组元素 int Length ( ) const { return ArraySize; } //取数组长度 void ReSize ( int sz ); //修改数组长度 } 顺序表的类定义 #include //定义在头文件“seqlist.h”中 #include template 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){ outI; 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 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 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 void inverse( Type Al int n)( for(inti=0;i void Array : 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 void inverse ( Type A[ ], int n ) { Type tmp; for ( int i = 0; i void Array :: 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 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 SeqList: DeMin(i if las ∥表空,中止操作返回 cr Type SeqList: DeINofi(int i)i if(last==-1 ll ilast ∥表空,或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 SeqList :: DelMin ( ) { if ( last == -1 ) //表空, 中止操作返回 { cerr Type SeqList :: DelNo#i ( int i ) { if ( last == -1 || 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; }
第2章数组 (3)实现向第i个位置插入一个新的元素x的函数如下(设第i个元素在data[],i=0,1,…,1ast) template void Seqlist: InsNo#i( int i, Type& x)t if( last== MaxSize-1lI ∥表满或参数i不合理,中止操作返回 i cerr =i;j- ∥空出位置以便插入,若=last+1,此循环不做 data[+1=datad: data[0=x ∥插入 last++ ∥表最后元素位置加 (4)从顺序表中删除具有给定值x的所有元素。 template void Seqlist: Del Value Type&x)i while(i void SeqList: DeINoffstot Type& S, Type& t)i if last i cerr void SeqList: DelNotfstotftI ( Type& s, Type& t)t if last i cerr =s)break ∥退出循环时,i指向该元素 if (it的第一个元素 if( data[i+j>t)break ∥退出循环时,计指向该元素 for( int k=itj; k <= last; k++) 删除满足条件的元素,后续元素前移 data(k-j= data[ k]; last-= ∥表最后元素位置减j
第 2 章 数组 14 (3) 实现向第 i 个位置插入一个新的元素 x 的函数如下(设第 i 个元素在 data[i], i=0,1,,last)： template void SeqList :: InsNo#i ( int i, Type& x ) { if ( last == MaxSize-1|| i last+1 ) //表满或参数 i 不合理, 中止操作返回 { cerr = i; j-- ) //空出位置以便插入, 若 i=last+1, 此循环不做 data[j+1] = data[j]; data[i] = x; //插入 last++; //表最后元素位置加 1 } (4) 从顺序表中删除具有给定值 x 的所有元素。 template void SeqList :: DelValue ( Type& x ) { int i = 0, j; while ( i void SeqList :: DelNo#sto#t ( Type& s, Type& t ) { if ( last == -1 || s >= t ) { cerr = s && data[i] void SeqList :: DelNo#sto#t1 ( Type& s, Type& t ) { if ( last == -1 || s >= t ) { cerr = s ) break; //退出循环时, i 指向该元素 if ( i 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 }
第2章数组 (7)实现将两个有序顺序表合并成一个新的有序顺序表的函数如下: Type> SeqList& SeqList: Merge( SeqList& A, SeqList& B)t ∥合并有序顺序表A与B成为一个新的有序顺序表并由函数返回 if(A Length +B Length Maxs ize i cerr void SeqList: DelDouble ()t if( last ==-1) i cerr <<"List is empty! "< endl; exit(1):) j, k; Type temp while(i<= last)i ∥循环检测 j=i+1; temp=data[]; ∥对于每一个讠,重复检测一遍后续元素 if( temp ==datad)i ∥如果相等,后续元素前移 for (k=j+; k<=last; k++)data[k-1= data[ k]; ∥表最后元素位置减1 H++ 川检测完data[,检测下一个 2-9设有一个nxn的对称矩阵A,如图(a)所示。为了节约存储,可以只存对角线及对角线以上的元素 或者只存对角线或对角线以下的元素。前者称为上三角矩阵,后者称为下三角矩阵。我们把它们按行 存放于一个一维数组B中,如图(b)和图(c)所示。并称之为对称矩阵A的压缩存储方式。试问 (1)存放对称矩阵A上三角部分或下三角部分的一维数组B有多少元素? (2)若在一维数组B中从0号位置开始存放,则如图(a)所示的对称矩阵中的任一元素a在只存上
第 2 章 数组 15 } (7) 实现将两个有序顺序表合并成一个新的有序顺序表的函数如下： template SeqList& SeqList :: Merge ( SeqList& A, SeqList& B ) { //合并有序顺序表 A 与 B 成为一个新的有序顺序表并由函数返回 if ( A.Length() + B.Length() > MaxSize ) { cerr void SeqList :: 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], 检测下一个 } } 2-9 设有一个 nn 的对称矩阵 A，如图(a)所示。为了节约存储，可以只存对角线及对角线以上的元素， 或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。我们把它们按行 存放于一个一维数组 B 中，如图(b)和图(c)所示。并称之为对称矩阵 A 的压缩存储方式。试问： (1) 存放对称矩阵 A 上三角部分或下三角部分的一维数组 B 有多少元素？ (2) 若在一维数组 B 中从 0 号位置开始存放，则如图(a)所示的对称矩阵中的任一元素 aij 在只存上
第2章数组 三角部分的情形下(图(b)应存于一维数组的什么下标位置?给出计算公式 (3)若在一维数组B中从0号位置开始存放,则如图(a所示的对称矩阵中的任一元素a在只存下 三角部分的情形下(图(c)应存于一维数组的什么下标位置?给出计算公式。 【解答】 (1)数组B共有n+(n-1)+…+1=n*(n+1)/2个元素。 1gn2…1n 2122·Czn (a)对称矩阵 (b)只存上三角部分 (c)只存下三角部分 a11…,lana…ang… ann an az az- ar;a1。g (2)只存上三角部分时,若i≤j,则数组元素A[]]前面有i-1行(1-i-1,第0行第0列不算) 第1行有n个元素,第2行有n-1个元素,……,第i-1行有n-i+2个元素。在第i行中,从对角线算 起,第j号元素排在第j-计+1个元素位置(从1开始),因此,数组元素A[i]在数组B中的存放位置 +(n-1)+(n-2)+……+(n-1+2)+J-i+1 =(2n-+2)*(i-1)/2+j-i+1 =(2n-i)*(i-1)/2+j 若i>j,数组元素A][]在数组B中没有存放,可以找它的对称元素A][。在 数组B的第(2nj)*(j-1)/2+i位置中找到 如果第0行第0列也计入,数组B从0号位置开始存放,则数组元素A[[在数组B中的存放位 置可以改为 当i≤j时,=(2n-i+1)*i/2+j-i=(2n-i-1)*i/2+j 当i>j时,=(2n-j-1)*j/2+ (3)只存下三角部分时,若i≥j,则数组元素A[前面有i-1行(1~i-1,第0行第0列不算) 第1行有1个元素,第2行有2个元素,……,第i-1行有i-1个元素。在第i行中,第j号元素排在 第j个元素位置,因此,数组元素A]在数组B中的存放位置为 1+2+…+(1-1)+j=(i-1)*1/2+ 若i<j,数组元素A[订]在数组B中没有存放,可以找它的对称元素A[。在 数组B的第(-1)*/2+i位置中找到
第 2 章 数组 16 三角部分的情形下(图(b))应存于一维数组的什么下标位置？给出计算公式。 (3) 若在一维数组 B 中从 0 号位置开始存放，则如图(a)所示的对称矩阵中的任一元素 aij 在只存下 三角部分的情形下(图(c))应存于一维数组的什么下标位置？给出计算公式。 【解答】 (1) 数组 B 共有 n + ( n-1 ) + + 1= n * ( n+1 ) / 2 个元素。 (2) 只存上三角部分时，若 i j，则数组元素 A[i][j]前面有 i-1 行（1i-1，第 0 行第 0 列不算)， 第 1 行有 n 个元素，第 2 行有 n-1 个元素，，第 i-1 行有 n-i+2 个元素。在第 i 行中，从对角线算 起，第 j 号元素排在第 j-i+1 个元素位置（从 1 开始），因此，数组元素 A[i][j]在数组 B 中的存放位置 为 n + (n-1) + (n-2) + + (n-i+2) + j-i+1 = (2n-i+2) * (i-1) / 2 + j-i+1 = (2n-i) * (i-1) / 2 + j 若 i > j，数组元素 A[i][j]在数组 B 中没有存放，可以找它的对称元素 A[j][i]。在 数组 B 的第 (2n-j) * (j-1) / 2 + i 位置中找到。 如果第 0 行第 0 列也计入，数组 B 从 0 号位置开始存放，则数组元素 A[i][j]在数组 B 中的存放位 置可以改为 当 i j 时，= (2n-i+1) * i / 2 + j - i = ( 2n - i - 1 ) * i / 2 + j 当 i > j 时，= (2n - j - 1) * j / 2 + i (3) 只存下三角部分时，若 i j，则数组元素 A[i][j]前面有 i-1 行（1i-1，第 0 行第 0 列不算)， 第 1 行有 1 个元素，第 2 行有 2 个元素，，第 i-1 行有 i-1 个元素。在第 i 行中，第 j 号元素排在 第 j 个元素位置，因此，数组元素 A[i][j]在数组 B 中的存放位置为 1 + 2 + + (i-1) + j = ( i-1)*i / 2 + j 若 i < j，数组元素 A[i][j]在数组 B 中没有存放，可以找它的对称元素 A[j][i]。在 数组 B 的第 (j-1)*j / 2 + i 位置中找到
第2章数组 如果第0行第0列也计入,数组B从0号位置开始存放,则数组元素A][j在数组B中的存放位 置可以改为 当i≥j时,=i*(i+1)/2+j 当i<j时,=j+1)/2+i 2-10设A和B均为下三角矩阵,每一个都有n行。因此在下三角区域中各有n(n+1)2个元素。另设 有一个二维数组C,它有n行n+1列。试设计一个方案,将两个矩阵A和B中的下三角区域元素存放 于同一个C中。要求将A的下三角区域中的元素存放于C的下三角区域中,B的下三角区域中的元素 转置后存放于C的上三角区域中。并给出计算A的矩阵元素a和B的矩阵元素b在C中的存放位置 下标的公式。 【解答】 b。b A b b b b b b n-22 m-10an-11an-12 计算公式 C[门 [j= CL/[刁 UD={C+当≥/时 [iL+1 2-11在实际应用中经常遇到的稀疏矩阵是三对 c1112 角矩阵,如右图所示。在该矩阵中除主对角线及 a212223 在主对角线上下最临近的两条对角线上的元素 c32c33a34 外,所有其它元素均为0。现在要将三对角矩阵 A中三条对角线上的元素按行存放在一维数组B an1n2 anin-1 anin 中,且a1存放于B[0]。试给出计算A在三条对 角线上的元素a(15i≤n15j5计+1)在一维 a1a1z az1@ azzaz3 a3;…anon 数组B中的存放位置的计算公式 【解答】 在B中的存放顺序为[a,an2,a,a2,a,a3,a3,as4,…,anml,am],总共有3n-2个非零元素 元素a在第i行,它前面有3(-1)-1个非零元素,而在本行中第j列前面有j计+1个,所以元素a在B 中位置为2*计+j-3 2-12设带状矩阵是nxn阶的方阵,其中所有的非零元素都在由主对 b 角线及主对角线上下各b条对角线构成的带状区域内,其它都为零元 b条对角线
第 2 章 数组 17 = − − − − − − − − − − − − − 10 11 12 1 1 1 1 20 21 22 22 12 10 11 11 21 11 00 00 10 20 10 n n n n n n n n n n n n n a a a a b a a a b b a a b b b a b b b b C = 当 时 当 时 [ ][ ], [ ][ ], [ ][ ] C j i i j C i j i j A i j 如果第 0 行第 0 列也计入，数组 B 从 0 号位置开始存放，则数组元素 A[i][j]在数组 B 中的存放位 置可以改为 当 i j 时，= i*(i+1) / 2 + j 当 i < j 时，= j*(j+1) / 2 + i 2-10 设 A 和 B 均为下三角矩阵，每一个都有 n 行。因此在下三角区域中各有 n(n+1)/2 个元素。另设 有一个二维数组 C，它有 n 行 n+1 列。试设计一个方案，将两个矩阵 A 和 B 中的下三角区域元素存放 于同一个 C 中。要求将 A 的下三角区域中的元素存放于 C 的下三角区域中，B 的下三角区域中的元素 转置后存放于 C 的上三角区域中。并给出计算 A 的矩阵元素 aij 和 B 的矩阵元素 bij 在 C 中的存放位置 下标的公式。 【解答】 计算公式 2-11 在实际应用中经常遇到的稀疏矩阵是三对 角矩阵，如右图所示。在该矩阵中除主对角线及 在主对角线上下最临近的两条对角线上的元素 外，所有其它元素均为 0。现在要将三对角矩阵 A 中三条对角线上的元素按行存放在一维数组 B 中，且 a11 存放于 B[0]。试给出计算 A 在三条对 角线上的元素 aij （1 i n, i-1 j i+1）在一维 数组 B 中的存放位置的计算公式。 【解答】 在 B 中的存放顺序为 [ a11, a12, a21, a22, a23, a32, a33, a34, …, an n-1, ann ]，总共有 3n-2 个非零元素。 元素 aij 在第 i 行，它前面有 3(i-1)-1 个非零元素，而在本行中第 j 列前面有 j-i+1 个，所以元素 aij 在 B 中位置为 2*i+j-3。 2-12 设带状矩阵是 nn 阶的方阵，其中所有的非零元素都在由主对 角线及主对角线上下各 b 条对角线构成的带状区域内，其它都为零元 = −10 −11 −1 −1 10 11 00 an an an n a a a A = −10 −11 −1 −1 10 11 00 bn bn bn n b b b B + + = 当 时 当 时 [ ][ 1], [ ][ 1], [ ][ ] C i j i j C j i i j B i j
第2章数组 素。试问: (1)该带状矩阵中有多少个非零元素? (2)若用一个一维数组B按行顺序存放各行的非零元素,且设a1存放在B[0中,请给出一个公式, 计算任一非零元素a在一维数组B中的存放位置。 【解答】 (1)主对角线包含n个非零元素,其上下各有一条包含n-1个非零元素的次对角线,再向外,由 各有一条包含n-2个非零元素的次对角线,……,最外层上下各有一条包含n-b个非零元素的次对角 线。则总共的非零元素个数有 =n+2 (n-1)+(n-b)b =n+b2n-b-1)=(2b+1)n-b-b2 2 n+2(n-1)+2(n-2)+…+2(n-b)=n+2(n-1)+(n-2)+…+(n-b)) (2)在用一个一维数组B按行顺序存放各行的非零元素时,若设b≤n/2,则可按各行非零元素个 数变化情况,分3种情况讨论 ①当1≤I≤b+1时,矩阵第1行有b+1个元素,第2行有b+2个元素,第3行有b+3个元素,…… 第i行存有bi个元素,因此,数组元素A[在B[]中位置分析如下: 第i行(i≥1)前面有i-1行,元素个数为(b+1)+(b+2)+…+(b+i-1)=(i-1)*bi*(i-1)2,在第i行第j 列(≥1)前面有j1个元素,则数组元素A[[在B[]中位置为 (-1)*b i*(1-1) 2 ②当b+1<i≤nb+1时,各行都有2b+1个元素。因为数组A[J]前b行共有b*b+(b+1)*b/2= b(3*b+1)2个元素,所以数组元素A[[在B[]中位置为 b*(3*b+1) (i-b-1)*(2*b b ③当nb+l<i≤n时,各行元素个数逐步减少。当i=nb+1时有2b个非零元素,当i=n-b+2时有 2b-1个非零元素,当i=nb+3时有2b-2个非零元素,…,当in时有b+1个非零元素。因为前面nb 行总共有b*(3*b+1)2+(n-2+b)+(2*b+1)个非零元素,所以在最后各行数组元素A[订在B[j中位置为 b*(3*b+1 (1-n+b-1)*(4*b-i+n-b+2) 2(-2*b)*(2*b+1)+ -+1-1+b 2 2-13稀疏矩阵的三元组表可以用带行指针数组的二元组表代替。 1201100130 稀疏矩阵有多少行,在行指针数组中就有多少个元素:第i个元 素的数组下标i代表矩阵的第i行,元素的内容即为稀疏矩阵第i 0-400030 行的第一个非零元素在二元组表中的存放位置。二元组表中每个 0008000 二元组只记录非零元素的列号和元素值,且各二元组按行号递增 0000000 的顺序排列。试对右图所示的稀疏矩阵,分别建立它的三元组表0-900200 和带行指针数组的二元组表 【解答】 行指针数组 二元组表data 0 1 3
第 2 章 数组 18 − − 0 9 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 4 0 0 0 3 0 0 0 0 0 0 0 14 12 0 11 0 0 13 0 素。试问： (1) 该带状矩阵中有多少个非零元素？ (2) 若用一个一维数组 B 按行顺序存放各行的非零元素，且设 a11 存放在 B[0]中，请给出一个公式， 计算任一非零元素 aij 在一维数组 B 中的存放位置。 【解答】 (1) 主对角线包含 n 个非零元素，其上下各有一条包含 n-1 个非零元素的次对角线，再向外，由 各有一条包含 n-2 个非零元素的次对角线，……，最外层上下各有一条包含 n-b 个非零元素的次对角 线。则总共的非零元素个数有 n + 2(n-1) + 2(n-2) + … + 2(n-b) = n + 2( (n-1) + (n-2 ) + … + (n-b) ) (2) 在用一个一维数组 B 按行顺序存放各行的非零元素时，若设 b≤n/2，则可按各行非零元素个 数变化情况，分 3 种情况讨论。 ① 当 1≤i≤b+1 时，矩阵第 1 行有 b+1 个元素，第 2 行有 b+2 个元素，第 3 行有 b+3 个元素，……， 第 i 行存有 b+i 个元素，因此，数组元素 A[i][j]在 B[ ]中位置分析如下： 第 i 行(i≥1)前面有 i-1 行，元素个数为 (b+1)+(b+2)+…+(b+i-1) = (i-1)*b+i*(i-1)/2，在第 i 行第 j 列(j≥1)前面有 j-1 个元素，则数组元素 A[i][j]在 B[ ]中位置为 ② 当 b+1<i≤n-b+1 时，各行都有 2b+1 个元素。因为数组 A[ ][ ]前 b 行共有 b*b+(b+1)*b/2 = b*(3*b+1)/2 个元素，所以数组元素 A[i][j]在 B[ ]中位置为 ③ 当 n-b+1<i≤n 时，各行元素个数逐步减少。当 i=n-b+1 时有 2b 个非零元素，当 i=n-b+2 时有 2b-1 个非零元素，当 i=n-b+3 时有 2b-2 个非零元素，…，当 i=n 时有 b+1 个非零元素。因为前面 n-b 行总共有 b*(3*b+1)/2+(n-2*b)*(2*b+1)个非零元素，所以在最后各行数组元素 A[i][j]在 B[ ]中位置为 2-13 稀疏矩阵的三元组表可以用带行指针数组的二元组表代替。 稀疏矩阵有多少行，在行指针数组中就有多少个元素：第 i 个元 素的数组下标 i 代表矩阵的第 i 行，元素的内容即为稀疏矩阵第 i 行的第一个非零元素在二元组表中的存放位置。二元组表中每个 二元组只记录非零元素的列号和元素值，且各二元组按行号递增 的顺序排列。试对右图所示的稀疏矩阵，分别建立它的三元组表 和带行指针数组的二元组表。 【解答】 2 n b(2n b 1) (2b 1)n - b - b 2 ((n 1) (n b))b n 2* = + − − = + − + − = + ( ) j 1 2 i * (i 1) i 1 * b + − − − + (i b 1)*(2*b 1) j i b 2 b*(3*b 1) + − − + + − + + j i b 2 (i n b 1)*(4*b i n b 2) (n 2*b)*(2*b 1) 2 b*(3*b 1) + − + − + − − + − + + − + + + 行指针数组 row 0 0 1 3 2 4 3 6 4 7 5 7 二元组表 data col value 0 0 12 1 2 11 2 5 13 3 6 14 4 1 -4 5 5 3 6 3 8
