c语言编程要点---第3章

《c语言编程要点---第3章》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、C语言编程要点---第3章排序与查找（下）3．4哪一种查找方法最方便?正如qsort()函数是最方便的排序方法一样，C标准库函数bsearch()是最方便的查找方法。bsearch()函数的原型如下：void*bsearch(constvoid*key，constvoid*bur，size_tnum，size_tsize，in(*comp)(constvoid*，constvoid*))；bsearch()函数在一个数据已经排好序的数组中进行折半查找。折半查找也是一种分割处理式的算法。bsearch()函数的查找过程为：首先比较关键字与数组中间的元素，如果两者相等

2、，则查找结束；如果前者比后者小，则要查找的数据必然在数组的前半部，此后只需在数组的前半部中继续进行折半查找，如果前者比后者大，则要查找的数据必然在数组的后半部，此后只需在数组的后半部中继续进行折半查找。例3．4a给出一个调用bsearch()函数的简单函数。该例所用的comp()函数和例3.1中qsort()函数所用的完全相同。例3．4b给出了一个在已排好序的字符串数组中查找一个字符串的折半查找算法程序。该例没有调用bsearch()函数。上述两例都可以和本章结尾的有关代码一起被编译连接成可执行程序。例3．4a一个使用bsearch()函数的例子1:#includ

3、e2:3:staticintcomp(constvoid*ele1,constvoid*ele2)4:{5:returnstrcmp(*(constchar**ele1,6:*(constchar**)ele2);7:}8:9:constchar*search(constchar*key,constchar**array,10:size_tnum)11:{12:char**p=bsearch(&ckey,array,num,13:sizeof(*array),comp);14:returnp?*P:NULL;15:}例3.4b一个折半查找算法程

4、序1:#include2:3:constchar*search(constchar*key,cosntchar**array,4:size_tnum)5:{6:intlow=0;7:inthigh=num-1;8:9:while(low<=high)10:{11:intmid=(low+high)/2;12:intn=strcmp(key,array[mid]);13:14:if(n0)17:low=mid+1;18:else19:returnarray[mid];20:}21:retu

5、rn0;22:}线性查找也是一种简单的查找方法。尽管在大量数据中进行查找时，线性查找要比bsearch()函数慢，但线性查找还是足以满足许多查找要求的。此外，如果数据未排序或无法随机存取，那么线性查找可能就是唯一可行的查找方法。线性查找的过程为：从数据集的第一个元素开始，依次将关键字和数据集中的每一个元素进行比较，直到找到要找的数据。例3.4c给出了一个线性查找算法程序，它同样可以和本章结尾的有关代码一起编译连接成一个可执行程序。例3．4c一个线性查找算法程序1:#include2:3:constchar*search(constchar*ke

6、y,constchar**array,4:size_num)5:{6:inti;7:8:for(i=0;i

7、都有N个分支(在下文的例子中有16个分支)。树状数据结构和树状查找所涉及的概念相当多，这里无法一一介绍，你可以从有关数据结构或算法的书籍中了解到更多的内容。 键树的概念可以用哈希表树的建立过程来描述： 假设有一个哈希函数，它将数据映射到一个完整的32位整数上，即它的哈希值是一个32位整数。你可以将这个32位的哈希值看作是8个4位的哈希值连接在一起，并用第一个4位哈希值作为索引，建立一个含16个表项的哈希表。 显然，一个仅含16个表项的哈希表将带来许多冲突，因为许多数据将映射到同一个表项中。如果用第二个4位哈希值作为索引，再建立一层哈希表(每个哈希表同样含16个表项

8、)，并使第