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

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

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

  [題目分析]本題屬於查找待查找元素是字符串(長將查找元素存放在一維數組中二分檢索(即折半查找或對分查找)是首先用一維數組的中間元素與被檢索元素比較若相等則檢索成功否則根據被檢索元素大於或小於中間元素而在中間元素的右方或左方繼續查找直到檢索成功或失敗(被檢索區間的低端指針大於高端指針)下面給出類C語言的解法

  typedef struct node
  {char data[];//字符串長
  }node;

  非遞歸過程如下

  int binsearch(node string [];int n;char name[])//在有n個字符串的數組string中二分檢索字符串name若檢索成功返回name在string中的下標否則返回
  {int low = high = n ;//low和high分別是檢索區間的下界和上界
  while(low <= high)
  {mid = (low + high) /; //取中間位置
  if(strcmp(string[mid]name) ==) return (mid); //檢索成功
  else if(strcmp(string[mid]name)<) low=mid+; //到右半部分檢索
  else high=mid;  //到左半部分檢索
  }
  return ; //檢索失敗
  }//算法結束

  最大檢索長度為logn

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


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