【正文】 的值key說(shuō)明查找成功；或者出現(xiàn)low的值大于high的情況，說(shuō)明查找不成功。建立一個(gè)有序表，數(shù)據(jù)元素從下標(biāo)為1的單元開(kāi)始放入。實(shí)現(xiàn)查找算法時(shí)，首先將low賦值為l，high等于最后一個(gè)數(shù)據(jù)元素的下標(biāo)，然后將給定的關(guān)鍵字的值與查找區(qū)間[low，high]中間的數(shù)據(jù)元素的關(guān)鍵字比較， 實(shí)現(xiàn)查找過(guò)程。//參考程序includedefine KEYTYPE jntdefine MAXSIZE 100typedef struct{KEYTYPE key；}SEELEMENT；typedef struct{SSELEMENT r[MAXSIZE]；int len；}SSTABLE；int search_bin(KEYTYPE k，SSTABLE *st)，//有序表上折半查找{ int low，high，mid；low=1； //low=l表示元素從下標(biāo)為1的單元放起high=stlen； //high=stlen表示最后一個(gè)元素的下標(biāo)while(1ow=high) //low=high為繼續(xù)查找的條件{ mid=(1ow+high)／2； if(k==str[mid].key) //k==str[mid].key表示查找成功 retum mid； else if(kstr[mid].key) //否則繼續(xù)二分查找high=mid－l； else low=mid+l；｝return 0。 //查找不成功，返回0}main(){{ SSTABLE a。int i，j，k。printf(“請(qǐng)輸入有序表元素，元素為整型量(從小到大輸入)，用空格分開(kāi)，99為結(jié)束標(biāo)志：”)； j=0；k=1。I=0。scanf(“%d”，amp。i)；while(i!=99) { j++； [k].key=i； k++。 scanf(“%d”,＆i)； //輸入有序表元素 } =j； printf(“\n有序表元素列表顯示：”)； for(i=l；i=；i++) printf(“%d”，[i])； printf(“\n”)； pfintf(”\n輸入待查元素關(guān)鍵字：”)； scanf[“%d”，＆i]； k=search_bin(i，amp。a)； if(k==0) printf(表中待查元素不存在\n\n)； else printf(”表中待查元素存在\n\n)； }③ 二叉排序樹(shù)基本思想及程序?qū)崿F(xiàn)二叉排序樹(shù)就是指將原來(lái)已有的數(shù)據(jù)根據(jù)大小構(gòu)成一棵二叉樹(shù)，二叉樹(shù)中的所有結(jié)點(diǎn)數(shù)據(jù)滿(mǎn)足一定的大小關(guān)系，所有的左子樹(shù)中的結(jié)點(diǎn)均比根結(jié)點(diǎn)小，所有的右子樹(shù)的結(jié)點(diǎn)均比根結(jié)點(diǎn)大。 二叉排序樹(shù)查找是指按照二叉排序樹(shù)中結(jié)點(diǎn)的關(guān)系進(jìn)行查找，查找關(guān)鍵字首先同根結(jié)點(diǎn)進(jìn)行比較，如果相等則查找成功；如果比根結(jié)點(diǎn)小，則在左子樹(shù)中查找；如果比根結(jié)點(diǎn)大，則在右子樹(shù)中進(jìn)行查找。這種查找方法可以快速縮小查找范圍，大大減少查找關(guān)鍵字的比較次數(shù)，從而提高查找效率。 算法的關(guān)鍵過(guò)程實(shí)際上就是二叉排序樹(shù)的創(chuàng)建和查找兩個(gè)步驟。 首先分析二叉排序樹(shù)的創(chuàng)建運(yùn)算，由于二叉排序樹(shù)中的所有結(jié)點(diǎn)都有一個(gè)大小關(guān)系，因此，每個(gè)結(jié)點(diǎn)必須在二叉排序樹(shù)中尋找其合適的位置。創(chuàng)建二叉排序樹(shù)的第一步就是創(chuàng)建一個(gè)根結(jié)點(diǎn)，第二步就是將其他結(jié)點(diǎn)不斷插入到二叉排序樹(shù)中的合適位置。二叉排序樹(shù)進(jìn)行結(jié)點(diǎn)插入時(shí)，首先要為被插入結(jié)點(diǎn)尋找合適的插入位置。這個(gè)過(guò)程實(shí)際上就是一個(gè)關(guān)鍵值不斷的比較的過(guò)程。第一次比較是與二叉排序樹(shù)的根結(jié)點(diǎn)比較，如果比根結(jié)點(diǎn)的關(guān)鍵值小，則插入到他的左子樹(shù)中；如果比根結(jié)點(diǎn)的關(guān)鍵值大，則插入到它的右子樹(shù)中。在子樹(shù)中重復(fù)這樣過(guò)程，直到找到合適的位置為止。二叉排序樹(shù)的查找運(yùn)算實(shí)際上同二叉排序樹(shù)的創(chuàng)建運(yùn)算是一致的。區(qū)別在于，創(chuàng)建過(guò)程中要為二叉排序樹(shù)中沒(méi)有位置的關(guān)鍵字建立結(jié)點(diǎn)，而查找過(guò)程中，只是在二叉排序樹(shù)中查找是否等于查找關(guān)鍵字值的結(jié)點(diǎn)存在，不管有還是沒(méi)有，它都不會(huì)創(chuàng)建一個(gè)新的結(jié)點(diǎn)。//參考程序includeincludedefine null 0typedef int keytype； //查找關(guān)鍵字為整型數(shù)據(jù)sturc Bsnode //二叉排序樹(shù)結(jié)點(diǎn)類(lèi)型{ keytype data； //數(shù)據(jù)域struct Bsnode *Lchild,*Rchild； //左右指針}。typedef struct Bsnode BST；typedef struct Bsnode *BSP； //BSP為二叉排序樹(shù)結(jié)點(diǎn)類(lèi)型指針BSP createBst(keytype key) //為關(guān)鍵字key創(chuàng)建一個(gè)二叉排序樹(shù)結(jié)點(diǎn){BSP s。s=(BSP)malloc(sizeof(BST))；sdata=key；sLchild=sRchild=null；return(s)；}BSP BSTinsert(BSP T，BSP S) //將S指向的結(jié)點(diǎn)插入到T指向的二叉排序樹(shù)中{BSP q,p。 if(T==null) return(S)。else{ p=T。 q=null。 while(p) //在二叉排序樹(shù)中為s結(jié)點(diǎn)尋找插入位置{ q=p； if(sdata==pdata) //如果S結(jié)點(diǎn)與二叉排序樹(shù)中根結(jié)點(diǎn)的值相等，則不插入 { printf(“The input key(%d)is have in!”，sdata)； return(t)； } if(sdatapdate) //如果比根結(jié)點(diǎn)值小，則在左子樹(shù)中尋找插入位置 p=pLchild； else //否則在右子樹(shù)中尋找插入位置 p=pRchild； } if(sdataqdata) qLchild=s； //作為左孩子插入 else qRchild=s； //作為右孩子插入 return(t)； }}void search(BSP T，keytype x) //在二叉排序樹(shù)T中查找是否存在關(guān)鍵宇{ BSP p；if(T==null){ printf(“error\n”)。 return。 } else { p=T while(p) { if(pdata==x) //如果根結(jié)點(diǎn)是查找的關(guān)鍵字，查找結(jié)束 { printf(“search success!\n”)； return； } else if(xpdata) //如果小于根結(jié)點(diǎn)，則在左于樹(shù)中查找p=pLchild； else p=pRchild； //否則，在右子樹(shù)中查找}if(!p) printf(”%d not exist!\n”，x)； }}void BSTPrint(BSP T) //輸出二叉排序樹(shù){if(T){ BSTPrint(TLchild)； printf(”%d”，Tdata)； BSTPrint(TRchild)； }}main(){BSP T，S；keytype key；int select=0，flag=l；T=null；while(flag) //主菜單{printf(”1…Create Bsort_tree\n”)；printf(”2…Insert key\n”)；printf(”3…Search key\n”)；printf(”4…Quit\n”)；printf(”P(pán)lease select：\n”)；scanf(”%d”，＆select)；switch(select){case l： //創(chuàng)建二叉排序樹(shù){ printf(”P(pán)lease input key to create Bsort_Tree：\n”)； scanf(”%d”，＆key)； while(key!==0){ S=createBst(key)； T=BSTinsert(T，S)； printf(”continue input!\n”)； scanf(“%d”,＆key)； } printf(”Bsort_Tree is：\n”)； BSTPrint(T)； Printf(“\n\n”)； break； } case 2： //在二叉排序樹(shù)中插入關(guān)鍵字{ printf(”P(pán)lease input key which inserted：\n”)； scanf(“%d”，amp。key)； S=createBst(key)； T=BSTinsert(T，S)； printf(”Bsort_Tree is：\n”)； BSTPrint(T)； printf(”\n\n”)； break； }case 3： //在二叉排序樹(shù)中查找關(guān)鍵字{ printf(”P(pán)lease input key which searched：\n”)； scanf(“%d”，＆key)； search(T，key)； printf(”\n\n)。 break； }case4： //產(chǎn)退出{ flag=0； break； } } } }④ 哈希表查找基本思想及程序?qū)崿F(xiàn)哈希表查找是一種基于盡可能不通過(guò)比較操作而直接得到記錄的存儲(chǔ)位置的想法而提出的一種特殊查找技術(shù)。它的基本思想是通過(guò)記錄中的關(guān)鍵字的值key為自變量，通過(guò)某一種確定的函數(shù)h，計(jì)算出函數(shù)值h(key)作為存儲(chǔ)地址，將相應(yīng)關(guān)鍵字的記錄存儲(chǔ)到對(duì)應(yīng)的位置上。而在查找時(shí)仍需要用這個(gè)確定的函數(shù)h進(jìn)行計(jì)算，獲得所要查找的關(guān)鍵字所在記錄的存儲(chǔ)位置。除留余數(shù)法(Division Method)是用關(guān)鍵字key除以某個(gè)正整數(shù)M，所得余數(shù)作為哈希地址的方法。對(duì)應(yīng)的哈希函數(shù)h(key)為h(key)=key%M，一般情況下M的取值為不大于表長(zhǎng)的質(zhì)數(shù)。用開(kāi)放定址法解決沖突，形成下一個(gè)地址的形式是 Hi=(h(key)+di)%M i=l，2，…，k(k≤m1)式中，h(key)為哈希函數(shù)；M為某個(gè)正整數(shù)；di為增量序列。線(xiàn)性探測(cè)再散列是將開(kāi)放定址法中的增量序列di設(shè)定為系列從1開(kāi)始一直到表長(zhǎng)減l的整數(shù)序列：l，2，3，…,m－1（m 為表長(zhǎng))。算法的關(guān)鍵過(guò)程實(shí)際上就是Hash表的創(chuàng)建和查找兩個(gè)步驟。首先分析Hash表的創(chuàng)建運(yùn)算：將由鍵盤(pán)輸入的關(guān)鍵字key作為自變量，通過(guò)除留余數(shù)法構(gòu)造哈希函數(shù)h，計(jì)算出函數(shù)值h(key)作為存儲(chǔ)地址，將該關(guān)鍵字存儲(chǔ)到對(duì)應(yīng)的位置上。如果產(chǎn)生沖突，則采用線(xiàn)性探查法，從關(guān)鍵字的哈希地址開(kāi)始向后掃描，直到找到空位置，將該關(guān)鍵字存儲(chǔ)在這個(gè)位置，插入成功；若掃描到哈希表的最后仍沒(méi)有找到空位置，則插入失敗。查找時(shí)仍利用除留余數(shù)法構(gòu)造哈希函數(shù)h，計(jì)算出函數(shù)值h(key)獲得所要查找的關(guān)鍵字所在記錄的存儲(chǔ)位置。若存儲(chǔ)位置對(duì)應(yīng)的數(shù)據(jù)元素的值與查找關(guān)鍵字相等，則查找成功，否則，采用線(xiàn)性探查法，從關(guān)鍵字的哈希地址開(kāi)始向后掃描，直到找到與關(guān)鍵字相等的數(shù)據(jù)元素，查找成功；若掃描到哈希表的最后仍沒(méi)有找到與關(guān)鍵字相等的數(shù)據(jù)元素，則查找失敗，不存在與關(guān)鍵字相等的數(shù)據(jù)元素。//參考程序include // 哈希表長(zhǎng)最大值define HM 20define M 19define FREE 0 //空閑標(biāo)記define SUCESS 1 // 成功define UNSUCESS 0 //不成功typedef int keytype； // keytype為整型 typedef struct // keytype型關(guān)鍵字key {keytype key； int 。 //查找次數(shù)}hashtable； //哈希表類(lèi)型int h(keytype key) //哈希函數(shù){ return(key%M)；}int HashSearch