自学考试《数据结构》各章复习要点总结.ppt

算法 #define m 10 #define n 10 void saddle ( int A[m][n]) /*求m行n列矩阵的鞍点*/ { int i,j,k,min; } 是否有缺陷？ //O(m*(m+n)) for (i=0；im；i++ ) { } min= A[i][0 ]; j=0; for (k=1；kn；k++ ) if(A[i][k ] min) { min= A[i][k]; j = k ；} for (k=0; km; k++) if(k!=j ) { if(A[k][j ] min) break; } if(k==m) printf ( “\nA[%d][%d]是鞍点” , i, j) ; 算法 例子：若矩阵Amxn中存在某个元素aij满足：aij是第i行中最小值且是第j行列中的最大值，则称该元素为矩阵A的一个鞍点，试编写算法找出A中的所有鞍点。 算法二 用穷举法 ：对每一个元素aij进行判别 1）i，j从第一行第一列开始； 2) 判断Aij是否是第i行中最小的, 若是转3）, 否则转4）; 3）判断Aij是否也是第j列最大的，若是则为鞍点，输出; 4）判断是否到了最后一个元素，若是退出，否则转2) 继续。 算法描述如下： 算法 #define m 10 #define n 10 void saddle ( int A[m][n]) /*求m行n列矩阵的鞍点*/ { int i,j,k,smin,smax； for (i=0；im；i++ ) for (j=0；jn；j++ ) { } } //O(m*n*O(A)) A（判断A[i][j]是否为鞍点） 算法 A（判断A[i][j]是否为鞍点） { k=0； while ( kn ) (A[i][k ] = A[i][j] ) k++; if (kn) smin=false; else smin=true; if ( smin ==true) { k=0； while (km) (A [k] [j]=A [i][j] ) k++; if (km) smax=false; else smax=true; } if ( smin==true smax==true ) printf ( “\nA[%d][%d]是鞍点” ,i,j) ; } //A=O(m+n) 是否有缺陷？ 算法 例子：若矩阵Amxn中存在某个元素aij满足：aij是第i行中最小值且是第j行列中的最大值，则称该元素为矩阵A的一个鞍点，试编写算法找出A中的所有鞍点。 算法三 改进算法减少时间复杂度 1) 先将矩阵每行最小数和每列的最大数求出来，并存放在C[n]和B[m]两个一维数组中； 2) 对C[n]和B[m]的每对元素进行比较，若B[j]和C[i]相等，则A[i][j]一定是鞍点。 算法描述如下： 算法 void Saddle ( int A[m][n]) { int i ，j ，k； int B [n]，C[m]； for ( i=0；im；i++ ) /* 求每行的最小数 */ { C[i]=A[i][0]； for ( j=1；jn；j++ ) if C[i]A[i][j] C[i]=A[i][j] ｝ for (j = 0；jn；j++ ) /*求每列的最大数*/ { B[j] = A[0][j]； for ( i = 1；im；i++ )