5.19.c

数据结构习题及答案

5.19④  若在m行n列的矩阵A中，某个元素aij是
第i行中的最小值，同时有是第j列中的最大值，
则称此元素为该矩阵中的一个马鞍点。假设以二
维数组存储矩阵A，试编写求出矩阵中所有马鞍点
的算法，并分析你的算法在最坏情况下的时间复
杂度。

要求实现以下函数：
void SaddlePoint(Array2D &a, int m, int n);
/* 求出矩阵a中所有马鞍点 */
/* 注意：行号和列号分别为0..m-1和0..n-1 */

二维数组类型Array2D的定义：
typedef char Array2D[MAXLEN][MAXLEN];

调用以下函数输出马鞍点：
void outSP(int x, int y);
/* Use this function to output your point. */
void SaddlePoint(Array2D &a, int m, int n)
/* 求出矩阵a中所有马鞍点                */
/* 注意：行号和列号分别为0..m-1和0..n-1 */
{int i,j,k,min,exist;
 for(i=0;i<m;i++)
   {  
   min=a[i][0];
   for(j=0;j<n;j++)      
       if(a[i][j]<min) min=a[i][j];         //求出行中最小的值       
   for(j=0;j<n;j++)
      {                                     //扫描整行
       if(a[i][j]==min)                     //选出i行中可能为马鞍点的点（行最小值）
         {for(exist=1,k=0;k<m;k++)                   //判断行最小点是否为列最大点
            if(a[k][j]>min){exist=0;break;}
          if(exist==1) outSP(i,j);}
       }      
   }
}