第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 若矩阵 Amn 中的某一元素 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(mn)。 ( ) 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 