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

．[题目分析]矩阵中元素按行和按列都已排序要求查找时间复杂度为O（m+n）因此不能采用常规的二层循环的查找可以先从右上角（i=aj=d）元素与x比较只有三种情况一是A[ij]>x 这情况下向j 小的方向继续查找二是A[ij]<x下步应向i大的方向查找三是A[ij]=x查找成功否则若下标已超出范围则查找失败

void search(datatype A[ ][ ] int abcd datatype x)

//n*m矩阵A行下标从a到b列下标从c到d本算法查找x是否在矩阵A中

{i=a; j=d; flag=; //flag是成功查到x的标志

while(i<=b && j>=c)

if(A[i][j]==x) {flag=;break;}

else if (A[i][j]>x) j; else i++;

if(flag) printf(A[%d][%d]=%dijx); //假定x为整型

else printf(矩阵A中无%d 元素x)

}算法search结束

[算法讨论]算法中查找x的路线从右上角开始向下（当x>A[ij]）或向左（当x<A[ij]）向下最多是m向左最多是n最佳情况是在右上角比较一次成功最差是在左下角（A[bc]）比较m+n次故算法最差时间复杂度是O(m+n）

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