熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

數據結構考研分類復習真題 第五章 答案[35]

2013-11-15 15:12:14  來源: 數據結構 

  .[題目分析]矩陣中元素按行和按列都已排序要求查找時間復雜度為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)

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


From:http://tw.wingwit.com/Article/program/sjjg/201311/23044.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.