数据结构考研分类复习真题 第五章 答案[33]

[题目分析] 寻找马鞍点最直接的方法是在一行中找出一个最小值元素然后检查该元素是否是元素所在列的最大元素如是则输出一个马鞍点时间复杂度是O(m*(m+n))本算法使用两个辅助数组max和min存放每列中最大值元素的行号和每行中最小值元素的列号时间复杂度为O（m*n+m）但比较次数比前种算法会增加也多使用向量空间

int m= n=;

void Saddle(int A[m][n])

//A是m*n的矩阵本算法求矩阵A中的马鞍点

{int max[n]={} //max数组存放各列最大值元素的行号初始化为行号;

min[m]={} //min数组存放各行最小值元素的列号初始化为列号;

i j;

for(i=;i<m;i++) //选各行最小值元素和各列最大值元素

for(j=;j<n;j++)

{if(A[max[j]][j]<A[i][j]) max[j]=i; //修改第j列最大元素的行号

if(A[i][min[i]]>A[i][j]) min[i]=j; //修改第i行最小元素的列号

}

for (i=;i<m;i++)

{j=min[i]; //第i行最小元素的列号

if(i==max[j])printf(A[%d][%d]是马鞍点元素值是%dijA[i][j]); //是马鞍点

}

}// Saddle

[算法讨论] 以上算法假定每行（列）最多只有一个可能的马鞍点若有多个马鞍点因为一行(或一列)中可能的马鞍点数值是相同的则可用二维数组min第一维是行向量是各行行号第二维是列向量存放一行中最大值的列号对最大值也同样处理使用另一二维数组max第一维是列向量是各列列号第二维存该列最大值元素的行号最后用类似上面方法找出每行(i)最小值元素的每个列号（j）再到max数组中找该列是否有最大值元素的行号（i）若有则是马鞍点

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []