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

[题目分析]本题属于查找待查找元素是字符串（长）将查找元素存放在一维数组中二分检索（即折半查找或对分查找）是首先用一维数组的中间元素与被检索元素比较若相等则检索成功否则根据被检索元素大于或小于中间元素而在中间元素的右方或左方继续查找直到检索成功或失败（被检索区间的低端指针大于高端指针）下面给出类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

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