例5.1若矩阵Amxn中存在某个元素a1满足:a1是第行中 最小值且是第列中的最大值,则称该元素为矩阵A的一个 鞍点。试编写一个算法,找出A中的所有鞍点。 基本思想:在矩阵A中求出每一行的最小值元素,然后 判断该元素它是否是它所在列中的最大值,是则打印出, 接着处理下一行。矩阵A用一个二维数组表示 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 11 例5.1 若矩阵Am×n 中存在某个元素aij满足：aij是第i行中 最小值且是第j列中的最大值，则称该元素为矩阵A的一个 鞍点。试编写一个算法，找出A中的所有鞍点。 基本思想：在矩阵A中求出每一行的最小值元素，然后 判断该元素它是否是它所在列中的最大值，是则打印出， 接着处理下一行。矩阵A用一个二维数组表示
void saddle(intA[I[,intm,intn)/*mn是矩阵A的行和列* Int 1.1.min for(=0;1<mi++)/按行处理* i minFAjJLOJ for (=1; j<n;j++) if(A]<min)min=A[i]];找第行最小值* for(j=0;j<n;j++)/检测该行中的每一个最小值是否是鞍点* if(Alli==min k=;p=0 while(p<m & alpl]=min)p++ if(p>=m) printf ("%d, %d, %dn",1, k,min); 算法的时间性能为Om(n+m*n 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 12 void saddle (int A[ ][ ],int m, int n) /*m,n是矩阵A的行和列*/ { int i,j,min; for (i=0;i<m;i++) /*按行处理*/ { min=A[i][0] for (j=1; j<n; j++) if (A[i][j]<min ) min=A[i][j]; /*找第i行最小值*/ for (j=0; j<n; j++) /*检测该行中的每一个最小值是否是鞍点*/ if (A[i][j]==min ) { k=j; p=0; while (p<m && A[p][j]<=min) p++; if ( p>=m) printf (＂%d,%d,%d\n＂ , i ,k,min); } } } 算法的时间性能为O(m*(n+m*n))
5.2特殊矩阵的压缩存储 ◆对称矩阵 ◆三角矩阵 带状矩阵 ★ 2021年1月21日 数据结构讲义 13
2021年1月21日 数据结构讲义 13 5.2 特殊矩阵的压缩存储 对称矩阵 三角矩阵 带状矩阵
52.1对称矩阵 对称矩阵的特点是:在一个n阶方阵中,有a=a,其 中1s,j≤n,如图所示是一个5阶对称矩阵。 4 36478 2842 16g 405 95 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 14 5.2.1 对称矩阵 对称矩阵的特点是：在一个n阶方阵中，有aij=aji ，其 中1≤i , j≤n，如图所示是一个５阶对称矩阵
对称矩阵关于主对角线对称,因此只需存储上三角或下 三角部分即可。比如,只存储下三角中的元素a,其特点 是中且15m,对于上三角中的元素an,它和对应的an 相等,因此当访问的元素在上三角时,直接去访问和它对 应的下三角元素即可,这样,原来需要n*n个存储单元, 现在只需要n(n+1)/2个存储单元了,节约了n(n-1)2个存储 单元,当n较大时,这是可观的一部分存储资源 362 74|6 2021年1月21日 数据结构讲义 15
2021年1月21日 数据结构讲义 15 • 对称矩阵关于主对角线对称，因此只需存储上三角或下 三角部分即可。比如，只存储下三角中的元素aij，其特点 是中j≤i且1≤i≤n，对于上三角中的元素aij ，它和对应的aji 相等，因此当访问的元素在上三角时，直接去访问和它对 应的下三角元素即可，这样，原来需要n*n个存储单元， 现在只需要n(n+1)/2个存储单元了，节约了n(n-1)/2个存储 单元，当n较大时，这是可观的一部分存储资源