數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書源代碼-資料下載頁

　　

【正文】 的值key說明查找成功；或者出現(xiàn)low的值大于high的情況，說明查找不成功。建立一個(gè)有序表，數(shù)據(jù)元素從下標(biāo)為1的單元開始放入。實(shí)現(xiàn)查找算法時(shí)，首先將low賦值為l，high等于最后一個(gè)數(shù)據(jù)元素的下標(biāo)，然后將給定的關(guān)鍵字的值與查找區(qū)間[low，high]中間的數(shù)據(jù)元素的關(guān)鍵字比較， 實(shí)現(xiàn)查找過程。//參考程序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)輸入有序表元素，元素為整型量(從小到大輸入)，用空格分開，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)； }③ 二叉排序樹基本思想及程序?qū)崿F(xiàn)二叉排序樹就是指將原來已有的數(shù)據(jù)根據(jù)大小構(gòu)成一棵二叉樹，二叉樹中的所有結(jié)點(diǎn)數(shù)據(jù)滿足一定的大小關(guān)系，所有的左子樹中的結(jié)點(diǎn)均比根結(jié)點(diǎn)小，所有的右子樹的結(jié)點(diǎn)均比根結(jié)點(diǎn)大。 二叉排序樹查找是指按照二叉排序樹中結(jié)點(diǎn)的關(guān)系進(jìn)行查找，查找關(guān)鍵字首先同根結(jié)點(diǎn)進(jìn)行比較，如果相等則查找成功；如果比根結(jié)點(diǎn)小，則在左子樹中查找；如果比根結(jié)點(diǎn)大，則在右子樹中進(jìn)行查找。這種查找方法可以快速縮小查找范圍，大大減少查找關(guān)鍵字的比較次數(shù)，從而提高查找效率。 算法的關(guān)鍵過程實(shí)際上就是二叉排序樹的創(chuàng)建和查找兩個(gè)步驟。 首先分析二叉排序樹的創(chuàng)建運(yùn)算，由于二叉排序樹中的所有結(jié)點(diǎn)都有一個(gè)大小關(guān)系，因此，每個(gè)結(jié)點(diǎn)必須在二叉排序樹中尋找其合適的位置。創(chuàng)建二叉排序樹的第一步就是創(chuàng)建一個(gè)根結(jié)點(diǎn)，第二步就是將其他結(jié)點(diǎn)不斷插入到二叉排序樹中的合適位置。二叉排序樹進(jìn)行結(jié)點(diǎn)插入時(shí)，首先要為被插入結(jié)點(diǎn)尋找合適的插入位置。這個(gè)過程實(shí)際上就是一個(gè)關(guān)鍵值不斷的比較的過程。第一次比較是與二叉排序樹的根結(jié)點(diǎn)比較，如果比根結(jié)點(diǎn)的關(guān)鍵值小，則插入到他的左子樹中；如果比根結(jié)點(diǎn)的關(guān)鍵值大，則插入到它的右子樹中。在子樹中重復(fù)這樣過程，直到找到合適的位置為止。二叉排序樹的查找運(yùn)算實(shí)際上同二叉排序樹的創(chuàng)建運(yùn)算是一致的。區(qū)別在于，創(chuàng)建過程中要為二叉排序樹中沒有位置的關(guān)鍵字建立結(jié)點(diǎn)，而查找過程中，只是在二叉排序樹中查找是否等于查找關(guān)鍵字值的結(jié)點(diǎn)存在，不管有還是沒有，它都不會(huì)創(chuàng)建一個(gè)新的結(jié)點(diǎn)。//參考程序includeincludedefine null 0typedef int keytype； //查找關(guān)鍵字為整型數(shù)據(jù)sturc Bsnode //二叉排序樹結(jié)點(diǎn)類型{ keytype data； //數(shù)據(jù)域struct Bsnode *Lchild,*Rchild； //左右指針}。typedef struct Bsnode BST；typedef struct Bsnode *BSP； //BSP為二叉排序樹結(jié)點(diǎn)類型指針BSP createBst(keytype key) //為關(guān)鍵字key創(chuàng)建一個(gè)二叉排序樹結(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指向的二叉排序樹中{BSP q,p。 if(T==null) return(S)。else{ p=T。 q=null。 while(p) //在二叉排序樹中為s結(jié)點(diǎn)尋找插入位置{ q=p； if(sdata==pdata) //如果S結(jié)點(diǎn)與二叉排序樹中根結(jié)點(diǎn)的值相等，則不插入 { printf(“The input key(%d)is have in!”，sdata)； return(t)； } if(sdatapdate) //如果比根結(jié)點(diǎn)值小，則在左子樹中尋找插入位置 p=pLchild； else //否則在右子樹中尋找插入位置 p=pRchild； } if(sdataqdata) qLchild=s； //作為左孩子插入 else qRchild=s； //作為右孩子插入 return(t)； }}void search(BSP T，keytype x) //在二叉排序樹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)，則在左于樹中查找p=pLchild； else p=pRchild； //否則，在右子樹中查找}if(!p) printf(”%d not exist!\n”，x)； }}void BSTPrint(BSP T) //輸出二叉排序樹{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(”Please select：\n”)；scanf(”%d”，＆select)；switch(select){case l： //創(chuàng)建二叉排序樹{ printf(”Please 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： //在二叉排序樹中插入關(guān)鍵字{ printf(”Please 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： //在二叉排序樹中查找關(guān)鍵字{ printf(”Please 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)哈希表查找是一種基于盡可能不通過比較操作而直接得到記錄的存儲(chǔ)位置的想法而提出的一種特殊查找技術(shù)。它的基本思想是通過記錄中的關(guān)鍵字的值key為自變量，通過某一種確定的函數(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ù)。用開放定址法解決沖突，形成下一個(gè)地址的形式是 Hi=(h(key)+di)%M i=l，2，…，k(k≤m1)式中，h(key)為哈希函數(shù)；M為某個(gè)正整數(shù)；di為增量序列。線性探測(cè)再散列是將開放定址法中的增量序列di設(shè)定為系列從1開始一直到表長(zhǎng)減l的整數(shù)序列：l，2，3，…,m－1（m 為表長(zhǎng))。算法的關(guān)鍵過程實(shí)際上就是Hash表的創(chuàng)建和查找兩個(gè)步驟。首先分析Hash表的創(chuàng)建運(yùn)算：將由鍵盤輸入的關(guān)鍵字key作為自變量，通過除留余數(shù)法構(gòu)造哈希函數(shù)h，計(jì)算出函數(shù)值h(key)作為存儲(chǔ)地址，將該關(guān)鍵字存儲(chǔ)到對(duì)應(yīng)的位置上。如果產(chǎn)生沖突，則采用線性探查法，從關(guān)鍵字的哈希地址開始向后掃描，直到找到空位置，將該關(guān)鍵字存儲(chǔ)在這個(gè)位置，插入成功；若掃描到哈希表的最后仍沒有找到空位置，則插入失敗。查找時(shí)仍利用除留余數(shù)法構(gòu)造哈希函數(shù)h，計(jì)算出函數(shù)值h(key)獲得所要查找的關(guān)鍵字所在記錄的存儲(chǔ)位置。若存儲(chǔ)位置對(duì)應(yīng)的數(shù)據(jù)元素的值與查找關(guān)鍵字相等，則查找成功，否則，采用線性探查法，從關(guān)鍵字的哈希地址開始向后掃描，直到找到與關(guān)鍵字相等的數(shù)據(jù)元素，查找成功；若掃描到哈希表的最后仍沒有找到與關(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； //哈希表類型int h(keytype key) //哈希函數(shù){ return(key%M)；}int HashSearch