第一篇：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-查找算法
《數(shù)據(jù)結(jié)構(gòu)》 第八次實(shí)驗(yàn)報(bào)告
學(xué)生姓名 學(xué)生班級(jí) 學(xué)生學(xué)號(hào) 指導(dǎo)老師
重慶郵電大學(xué)計(jì)算機(jī)學(xué)院 計(jì)算機(jī)專業(yè)實(shí)驗(yàn)中心
一、實(shí)驗(yàn)內(nèi)容
1)有序表的二分查找
?建立有序表，然后進(jìn)行二分查找 2)二叉排序樹的查找 ?建立二叉排序樹，然后查找
二、需求分析
二分查找的基本思想是將n個(gè)元素分成大致相等的兩部分，取a[n/2]與x做比較，如果x=a[n/2],則找到x,算法中止；如果x
三、概要設(shè)計(jì)
1、順序查找，在順序表R[0..n-1]中查找關(guān)鍵字為k的記錄，成功時(shí)返回找到的記錄位置，失敗時(shí)返回-1，具體的算法如下所示：
int SeqSearch(SeqList R,int n,KeyType k){
} int i=0;while(i } if(i>=n){ } printf(“%d”,R[i].key);return i;return-1;else printf(“%d”,R[i].key);i++; 2、二分查找，在有序表R[0..n-1]中進(jìn)行二分查找，成功時(shí)返回記錄的位置，失敗時(shí)返回-1，具體的算法如下： int BinSearch(SeqList R,int n,KeyType k){ } return-1;} int low=0,high=n-1,mid,count=0;while(low<=high){ mid=(low+high)/2;printf(“第%d次查找：在[ %d ,%d]中找到元素R[%d]:%dn ”,++count,low,high,mid,R[mid].key);if(R[mid].key==k) return mid;high=mid-1;low=mid+1;if(R[mid].key>k)else 四、詳細(xì)設(shè)計(jì) 源代碼： #include static int a[1024],count=0; void Find1(int low,int high,int x){ int mid;if(low<=high){ mid=(low+high)/2;count++;if(a[mid]>x)Find1(low,mid-1,x);else if(a[mid] void Find2(int low,int high,int x){ int mid;if(low<=high){ mid=(low+high)/2;count++;if(a[mid] 五、心得體會(huì) 通過(guò)這次在實(shí)現(xiàn)順序和二分查找算法的過(guò)程中，讓我對(duì)順序和二分查找算法有了更多的了解。查找根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素或（記錄）的操作，應(yīng)用十分廣泛。順序查找是一種最簡(jiǎn)單的查找方法。它的基本思路是：從表的一端開始,順序掃描線性表,依次將掃描到的關(guān)鍵字和給定值k相比較,若當(dāng)前掃描到的關(guān)鍵字與k相等,則查找成功；若掃描結(jié)束后,仍未找到關(guān)鍵字等于k的記錄,則查找失敗。二分查找也稱為折半查找要求線性表中的結(jié)點(diǎn)必須己按關(guān)鍵字值的遞增或遞減順序排列。它首先用要查找的關(guān)鍵字k與中間位置的結(jié)點(diǎn)的關(guān)鍵字相比較,這個(gè)中間結(jié)點(diǎn)把線性表分成了兩個(gè)子表,若比較結(jié)果相等則查找完成;若不相等,再根據(jù)k與該中間結(jié)點(diǎn)關(guān)鍵字的比較大小確定下一步查找哪個(gè)子表,這樣遞歸進(jìn)行下去,直到找到滿足條件的結(jié)點(diǎn)或者該線性表中沒(méi)有這樣的結(jié)點(diǎn)。在學(xué)習(xí)過(guò)程中，善于發(fā)現(xiàn)，會(huì)找到更多的捷徑。 六、附錄 運(yùn)行結(jié)果截圖。 實(shí)驗(yàn)題9.1 設(shè)計(jì)一個(gè)程序exp9-1.cpp，輸出在順序表{3，6，2，10，1，8，5，7，4，9}中采用順序方法找關(guān)鍵字5的過(guò)程。程序如下： //文件名:exp9-1.cpp #include KeyType key; //KeyType為關(guān)鍵字的數(shù)據(jù)類型 //其他數(shù)據(jù) //定義表中最多記錄個(gè)數(shù) InfoType data; } NodeType;typedef NodeType SeqList[MAXL]; //順序表類型 int SeqSearch(SeqList R,int n,KeyType k)//順序查找算法 { int i=0; while(i { } printf(“%d ”,R[i].key);i++; //從表頭往后找 if(i>=n)return-1; else } void main(){ SeqList R;{ } printf(“%d”,R[i].key);return i; } int n=10,i;KeyType k=5;int a[]={3,6,2,10,1,8,5,7,4,9};for(i=0;i //建立順序表 printf(“關(guān)鍵字序列:”);for(i=0;i 截圖如下： 實(shí)驗(yàn)題9.2 設(shè)計(jì)一個(gè)程序exp9-2.cpp，輸出在順序表{1，2，3，4，5，6，7，8，9，10}中采用折半查找法查找關(guān)鍵字9的過(guò)程。 程序如下： //文件名:exp9-2.cpp #include //定義表中最多記錄個(gè)數(shù) KeyType key; //KeyType為關(guān)鍵字的數(shù)據(jù)類型 InfoType data; //其他數(shù)據(jù) } NodeType;typedef NodeType SeqList[MAXL]; //順序表類型 int BinSearch(SeqList R,int n,KeyType k)//二分查找算法 { int low=0,high=n-1,mid,count=0;while(low<=high) { mid=(low+high)/2;printf(“ 第%d 次 比 較 :在[%d,%d]R[%d]:%dn”,++count,low,high,mid,R[mid].key); if(R[mid].key==k) //查找成功返回 return mid; if(R[mid].key>k) //繼續(xù)在R[low..mid-1]中查找 high=mid-1; else low=mid+1; //繼續(xù)在R[mid+1..high]中查找 } return-1;} void main(){ SeqList R;KeyType k=9;int a[]={1,2,3,4,5,6,7,8,9,10},i,n=10;for(i=0;i //建立順序表 R[i].key=a[i];printf(“關(guān)鍵字序列:”);for(i=0;i 比 較 元 素 中 } else printf(“元素%d的位置是%dn”,k,i);printf(“元素%d不在表中n”,k); 截圖如下： 實(shí)驗(yàn)題9.3 設(shè)計(jì)一個(gè)程序exp9-3.cpp，輸出在順序表{8，14，6，9，10,22,34,18,19,31,40,38,54,66,46,71,78,68,80,85,100,94,88,96,87}中采用分塊查找法查找（每塊的塊長(zhǎng)為5，共5塊）關(guān)鍵字46的過(guò)程。 程序如下： //文件名:exp9-3.cpp #include KeyType key; //KeyType為關(guān)鍵字的數(shù)據(jù)類型 //定義表中最多記錄個(gè)數(shù) //定義索引表的最大長(zhǎng)度 InfoType data; //其他數(shù)據(jù) } NodeType;typedef NodeType SeqList[MAXL];typedef struct { KeyType key;int link; //KeyType為關(guān)鍵字的類型 //指向分塊的起始下標(biāo) //順序表類型 } IdxType;typedef IdxType IDX[MAXI]; //索引表類型 int IdxSearch(IDX I,int m,SeqList R,int n,KeyType k)//分塊查找算法 { int low=0,high=m-1,mid,i,count1=0,count2=0;int b=n/m; //b為每塊的記錄個(gè)數(shù) printf(“二分查找n”);while(low<=high) //在索引表中進(jìn)行二分查找,找到的位置存放在low中 { mid=(low+high)/2;printf(“ 第%d 次 比 較 :在[%d,%d] 中 比 較 元R[%d]:%dn”,count1+1,low,high,mid,R[mid].key); if(I[mid].key>=k) high=mid-1; else low=mid+1; count1++; //累計(jì)在索引表中的比較次數(shù) } if(low //在索引表中查找成功后,再在線性表中進(jìn)行順序查找 { printf(“比較%d次,在第%d塊中查找元素%dn”,count1,low,k); i=I[low].link; printf(“順序查找:n ”); while(i<=I[low].link+b-1 && R[i].key!=k) { i++;count2++; printf(“%d ”,R[i].key);} //count2累計(jì)在順序表對(duì)應(yīng)塊中的比較次數(shù) printf(“n”); printf(“比較%d次,在順序表中查找元素%dn”,count2,k); if(i<=I[low].link+b-1) return i; else return-1;} 素 } return-1;void main(){ } SeqList R;KeyType k=46;IDX I;int a[]={8,14,6,9,10,22,34,18,19,31,40,38,54,66,46,71,78,68,80,85,100,94,88,96,87},i;for(i=0;i<25;i++)R[i].key=a[i]; //建立順序表 I[0].key=14;I[0].link=0;I[1].key=34;I[1].link=4;I[2].key=66;I[2].link=10;I[3].key=85;I[3].link=15;I[4].key=100;I[4].link=20;if((i=IdxSearch(I,5,R,25,k))!=-1)else printf(“元素%d不在表中n”,k);printf(“元素%d的位置是%dn”,k,i);printf(“n”); 截圖如下： 電 子 科 技 大 學(xué) 實(shí) 驗(yàn) 報(bào) 告 學(xué)生姓名：XXX 學(xué) 號(hào)：20*** 指導(dǎo)教師：劉嶠 實(shí)驗(yàn)地點(diǎn)：信軟機(jī)房306 實(shí)驗(yàn)時(shí)間：2014/6/20 一、實(shí)驗(yàn)室名稱：軟件實(shí)驗(yàn)室 二、實(shí)驗(yàn)項(xiàng)目名稱：數(shù)據(jù)結(jié)構(gòu)與算法—排序與查找 三、實(shí)驗(yàn)學(xué)時(shí)：4 四、實(shí)驗(yàn)原理： 快速排序的基本思想是：通過(guò)一躺排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一不部分的所有數(shù)據(jù)都要小，然后再按次方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。 假設(shè)要排序的數(shù)組是A[1]……A[N]，首先任意選取一個(gè)數(shù)據(jù)（通常選用第一個(gè)數(shù)據(jù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個(gè)過(guò)程稱為一躺快速排序。一躺快速排序的算法是： 1）設(shè)置兩個(gè)變量I、J，排序開始的時(shí)候I：=1，J：=N 2）以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給X，即X：=A[1]； 3）從J開始向前搜索，即（J：=J-1），找到第一個(gè)小于X的值，兩者交換； 4）從I開始向后搜索，即（I：=I+1），找到第一個(gè)大于X的值，兩者交換； 5）重復(fù)第3、4步，直到I=J。 二分法查找（折半查找）的基本思想： （1）確定該區(qū)間的中點(diǎn)位置：mid=（low+high）/2 min代表區(qū)間中間的結(jié)點(diǎn)的位置，low代表區(qū)間最左結(jié)點(diǎn)位置，high代表區(qū)間最右結(jié)點(diǎn)位置 （2）將待查a值與結(jié)點(diǎn)mid的關(guān)鍵字（下面用R[mid].key）比較，若相等，則查找成功，否則確定新的查找區(qū)間： A)如果R[mid].key>a，則由表的有序性可知，R[mid].key右側(cè)的值都大于a，所以等于a的關(guān)鍵字如果存在，必然在R[mid].key左邊的表中,這時(shí)high=mid-1; B)如果R[mid].key C)如果R[mid].key=a，則查找成功。 （3）下一次查找針對(duì)新的查找區(qū)間，重復(fù)步驟（1）和（2） （4）在查找過(guò)程中，low逐步增加，high逐步減少，如果high 五、實(shí)驗(yàn)?zāi)康模?/p> 本實(shí)驗(yàn)通過(guò)實(shí)現(xiàn)快速排序和折半查找算法，使學(xué)生理解如何實(shí)現(xiàn)快速查找和排序的基本算法思想。通過(guò)練習(xí)，加強(qiáng)對(duì)算法的理解，提高編程能力。 六、實(shí)驗(yàn)內(nèi)容： （1）實(shí)現(xiàn)數(shù)據(jù)序列的輸入; （2）實(shí)現(xiàn)快速排序算法,并對(duì)輸入的序列排序后輸出； （3）實(shí)現(xiàn)折半查找算法,并在步驟(2)排序后的序列上,進(jìn)行任意地 查找,并輸出查詢結(jié)果。 七、實(shí)驗(yàn)器材（設(shè)備、元器件）： 八、數(shù)據(jù)結(jié)構(gòu)及程序 #include #define MAX_LEN 100 void Sort(int *data,int left,int right){ int i,j,temp; i=left; j=right; temp=data[left]; if(left>right) return; while(i!=j){ while(data[j]>=temp&&j>i) j--; if(j>i) data[i++]=data[j]; while(data[i]<=temp&&j>i) i++; if(j>i) data[j--]=data[i]; } data[i]=temp; Sort(data,left,i-1);PC機(jī)一臺(tái)，裝有C/C++語(yǔ)言集成開發(fā)環(huán)境。 Sort(data,i+1,right);} int Search(int *data,int start,int end,int key,int num){ int result; int p =(start + end)/ 2; if(data[p] == key&&start<=end){ result = p; num++; if(data[p] > key) result = Search(data, start, p, key,num); else result = Search(data, p + 1, end, key,num); return result; } else if(num==0&&start>end){ result =-1; printf(“n 404 NO FOUNDn”); return result; } else if(num!=0&&start>end){ result=-1; if(num==1) printf(“nFounded number only one”); else printf(“nFounded number more than one”); return result; } else if(result!=-1){ if(data[p] > key) result = Search(data, start, p-1, key, num); else result = Search(data, p + 1, end, key, num); return result; } else { result=-1; return result; } } void loadFile(int *data,char *filename,int n){ int i; FILE *pfile=NULL; pfile=fopen(filename,“r”); if(!pfile){ printf(“Open file failn”); exit(0); } else printf(“Open file success!n”); for(i = 0;i < n;i++) fscanf(pfile , “%d ”,&data[i]);} int main(int argc, const char * argv[]){ int input=1,data[MAX_LEN],num=0,key=1,i,cmd; char filename[100]; printf(“Choose Mode :n 1.Input Mode 2.File Moden”); scanf(“%d”,&cmd); if(cmd==1){ printf(“Input data :(Enter 0 to detemine)n”); while(input!=0){ printf(“Enter the %d data :”,num+1); scanf(“%d”,&input); if(input!=0){ data[num]=input; num++; } } } else{ printf(“nInput the address of the file: ”); scanf(“%s”,filename); printf(“nInput the number of elem: ”); scanf(“%d”,&num); loadFile(data,filename,--num); } Sort(data, 0, num); printf(“nSort result: ”); for(i=1;i<=num;i++) printf(“%d ”,data[i]); printf(“nn”); while(key!=0){ printf(“nInput a key to search :(Enter 0 to detemine)”); scanf(“%d”,&key); if(key!=0) Search(data, 0, num, key, 0); } return 0;} 九、程序運(yùn)行結(jié)果： 1.打開程序： 2.嘗試手動(dòng)輸入模式： 3.搜索已存在數(shù)： 4.搜索不存在數(shù)： 5.嘗試文件讀入模式并搜索 實(shí)驗(yàn)成功。 十、實(shí)驗(yàn)結(jié)論： 使用好的排序與查找算法對(duì)于程序的運(yùn)行效率至關(guān)重要，一個(gè)好的算法，適合的算法能使計(jì)算機(jī)對(duì)數(shù)據(jù)的處理事半功倍，而選用錯(cuò)誤的算法，不但可能事倍功半，還有可能造成不穩(wěn)定因素。 快速排序的時(shí)間復(fù)雜度為n（log2n）,是排序算法中最為快速的一種，但是不穩(wěn)定，對(duì)基本有序的序列效率較差。 二分查找算法在查找算法中，速度快，效率高，但是要求數(shù)據(jù)要有序。 十一、總結(jié)及心得體會(huì)： 當(dāng)空間充足，對(duì)穩(wěn)定性要求不高的情況，排序算法宜使用快速排序。 快速排序和二分查找配合，可以以較高的效率查找目標(biāo)元素。 實(shí)驗(yàn)五 查找算法 實(shí)驗(yàn)項(xiàng)目：必做：順序查找、折半查找 選做：二叉查找樹 實(shí)驗(yàn)類型: 驗(yàn)證性 實(shí)驗(yàn)內(nèi)容： 順序查找：用數(shù)組或鏈表實(shí)現(xiàn)，數(shù)據(jù)有序或無(wú)序均可； 折半查找：必須用數(shù)組實(shí)現(xiàn)，且數(shù)據(jù)有序； 注意：提交的實(shí)驗(yàn)報(bào)告要顯示已有的數(shù)據(jù)元素、待查找的數(shù)據(jù)；應(yīng)包含查找成功、不成功的情況。 8.1 實(shí)現(xiàn)順序查找的算法 一，實(shí)驗(yàn)?zāi)康?/p> 1.熟悉掌握各種查找方法，深刻理解各種查找算法及其執(zhí)行的過(guò)程； 2.學(xué)會(huì)分析各種查找算法的性能。 二，實(shí)驗(yàn)內(nèi)容 8.1 實(shí)現(xiàn)順序查找的算法 編寫一個(gè)程序，輸出在順序表{3,6,2,10,1,8,5,7,4,9}中采用順序查找法查找關(guān)鍵字5的結(jié)果。 8.2 實(shí)現(xiàn)折半查找算法 編寫一個(gè)程序，輸出在順序表{1,2,3,4,5,6,7,8,9,10}中采用折半查找方法查找關(guān)鍵字9的結(jié)果。要求：（1）用非遞歸方法；（2）用遞歸方法。8.3 實(shí)現(xiàn)二叉排序樹的基本運(yùn)算 編寫一個(gè)程序?qū)崿F(xiàn)二叉排序樹的基本運(yùn)算，并在此基礎(chǔ)上完成如下功能：（1）由{4,9,0,1,8，6,3,5,2,7}創(chuàng)建一個(gè)二叉排序樹bt； （2）判斷bt是否為一棵二叉排序樹（提示：在遍歷過(guò)程中檢查是否符合二叉排序樹定義）； （3）采用非遞歸方法查找關(guān)鍵字為6的結(jié)點(diǎn)，并輸出其查找路徑（提示：查找過(guò)程中保留經(jīng)過(guò)的結(jié)點(diǎn)信息，找到后順序輸出之）。8.4 實(shí)現(xiàn)哈希表的相關(guān)運(yùn)算 編寫一個(gè)程序，實(shí)現(xiàn)哈希表的相關(guān)運(yùn)算，并在此基礎(chǔ)上完成如下功能： （1）建立{16,74,60,43,54,90,46,31,29,88,77}哈希表A[0…12]，哈希函數(shù)為H(k)=key % 11，并采用線性探測(cè)法解決沖突。輸出哈希表；（2）在上述哈希表中查找關(guān)鍵字為29的記錄； （3）在上述哈希表中刪除關(guān)鍵字為77的記錄，再將其插入，然后輸出哈希表。要求：輸出格式 哈希地址：0 1 2 ………..12 關(guān)鍵字值：…………………… 三，源代碼及結(jié)果截圖 8.1 //實(shí)現(xiàn)順序查找的算法 #include //定義表中最多記錄個(gè)數(shù) typedef int KeyType;typedef int InfoType;typedef struct { KeyType key;//KeyType為關(guān)鍵字的數(shù)據(jù)類型 InfoType data;//其他數(shù)據(jù) } NodeType; typedef NodeType SeqList[MAXL]; //順序表類型 int Search(SeqList R,int n,KeyType k)//順序查找算法 { int i=0;while(i printf(“%d ”,R[i].key); i++; //從表頭往后找 } if(i>=n) return-1;else { printf(“%d”,R[i].key); return i;} } void main(){ SeqList R;int n=10;KeyType k=5;InfoType a[]={3,6,2,10,1,8,5,7,4,9};int i;for(i=0;i //建立順序表 R[i].key=a[i];printf(“查找結(jié)果：n”);if((i=Search(R,n,k))!=-1) printf(“n元素%d的位置是:%d”,k,i);else printf(“n元素%d不在表中n”,k);printf(“n”);} 8.2 //實(shí)現(xiàn)折半查找算法 #include //定義表中最多記錄個(gè)數(shù) typedef int KeyType;typedef char InfoType[10];typedef struct { KeyType key; //KeyType為關(guān)鍵字的數(shù)據(jù)類型 InfoType data; //其他數(shù)據(jù) } NodeType;typedef NodeType SeqList[MAXL]; //順序表類型 int BinSearch1(SeqList R,int n,KeyType k)//非遞歸二分查找算法 { int low=0,high=n-1,mid,count=0;while(low<=high) { mid=(low+high)/2;printf(“第%d 次 查 找 : 在[%d,%d] 中 查 找 到R[%d]:%dn”,++count,low,high,mid,R[mid].key); if(R[mid].key==k) //查找成功返回 return mid;if(R[mid].key>k) //繼續(xù)在R[low..mid-1]中查找 元 素 } } high=mid-1;else low=mid+1; //繼續(xù)在R[mid+1..high]中查找 return-1;int BinSearch2(SeqList R,KeyType k,int low,int high,int count)//遞歸二分查找算法 { int mid;if(low<=high){ mid=(low+high)/2;第%d 次 查 找 : 在[%d,%d] 中 查 找 到 元 素printf(“R[%d]:%dn”,++count,low,high,mid,R[mid].key); if(R[mid].key==k) //查找成功返回 return mid;else if(R[mid].key>k) //繼續(xù)在R[low..mid-1]中查找 BinSearch2(R, k,low,mid-1,count);else BinSearch2(R, k,mid+1,high,count); //繼續(xù)在R[mid+1..high]中查找 } else return-1;} void main(){ } SeqList R;KeyType k=9;int a[]={1,2,3,4,5,6,7,8,9,10},i,n=10;for(i=0;i //建立順序表 printf(“用非遞歸方法:n”);if((i=BinSearch1(R,n,k))!=-1)printf(“元素%d的位置是%dn”,k,i);else printf(“元素%d不在表中n”,k);printf(“用遞歸方法:n”);if((i=BinSearch2(R,k,0,9,0))!=-1)printf(“元素%d的位置是%dn”,k,i);else printf(“元素%d不在表中n”,k); 8.3 //實(shí)現(xiàn)二叉排序樹的基本運(yùn)算 #include int key; struct BTNode *lchild; struct BTNode *rchild;}BTNode;//定義二叉排序樹插入結(jié)點(diǎn)的算法 int BSTInsert(BTNode *&T,int k){ if(T==NULL) { T=(BTNode *)malloc(sizeof(BTNode)); T->lchild=T->rchild=NULL; T->key=k; return 1; } else { if(k==T->key) return 0; else if(k return BSTInsert(T->lchild, k); else return BSTInsert(T->rchild, k); } } //定義二叉排序樹的創(chuàng)建算法 BTNode *createBST(int k[],int n){ BTNode *T; T=NULL; for(int i=0;i<=n-1;i++){ BSTInsert(T,k[i]); } return T;} //判斷是否為二叉排序樹 Status Judge(BTNode *&T){ } //定義二叉排序樹的查找算法 BTNode *BSTSearch(BTNode *&T,int k){ if(T==NULL) return NULL; else if(T==NULL)return 1;else if((T>T->lchild)&&(T } else return 0;Judge(T->lchild);Judge(T->rchild); { printf(“%d ”,T->key); if(T->key==k) return T; else if(k { return BSTSearch(T->lchild, k); } else { return BSTSearch(T->rchild, k); } } } void main(){ int a[50]={4,9,0,1,8,6,3,5,2,7}; BTNode *bt=createBST(a,10); if(Judge(bt)==0)cout<<“bt不是二叉排序樹”< } 8.4 //實(shí)現(xiàn)哈希表的相關(guān)運(yùn)算 #include //定義最大哈希表長(zhǎng)度 #define NULLKEY 0 //定義空關(guān)鍵字值 #define DELKEY-1 //定義被刪關(guān)鍵字值 typedef int KeyType; //關(guān)鍵字類型 typedef char * InfoType;//其他數(shù)據(jù)類型 typedef struct { KeyType key;//關(guān)鍵字域 InfoType data; //其他數(shù)據(jù)域 int count; //探查次數(shù)域 } HashTable[MaxSize]; //哈希表類型 void InsertHT(HashTable ha,int *n,KeyType k,int p)中 { //將關(guān)鍵字k插入到哈希表 int i,adr;adr=k % p;if(ha[adr].key==NULLKEY || ha[adr].key==DELKEY)//x[j]可以直接放在哈希表中 } void CreateHT(HashTable ha,KeyType x[],int n,int m,int p)//創(chuàng)建哈希表 { } else { } n++;i=1;do { adr=(adr+1)% p;i++; //i記錄x[j]發(fā)生沖突的次數(shù) //發(fā)生沖突時(shí)采用線性探查法解決沖突 ha[adr].key=k;ha[adr].count=1;} while(ha[adr].key!=NULLKEY && ha[adr].key!=DELKEY);ha[adr].key=k;ha[adr].count=i; { int i,n1=0;for(i=0;i //哈希表置初值 { ha[i].key=NULLKEY; ha[i].count=0; } } int SearchHT(HashTable ha,int p,KeyType k){ int i=0,adr;adr=k % p;while(ha[adr].key!=NULLKEY && ha[adr].key!=k){ } if(ha[adr].key==k)return adr; //查找失敗 //查找成功 i++; //采用線性探查法找下一個(gè)地址 //在哈希表中查找關(guān)鍵字k for(i=0;i } return-1;int DeleteHT(HashTable ha,int p,int k,int *n)//刪除哈希表中關(guān)鍵字k { } void DispHT(HashTable ha,int n,int m) //輸出哈希表 { float avg=0;int i;printf(“ 哈希表地址:t”);for(i=0;i } else //在哈希表中未找到該關(guān)鍵字 ha[adr].key=DELKEY;n--; //哈希表長(zhǎng)度減1 //在哈希表中找到該關(guān)鍵字 return 1;return 0; printf(“ n”); printf(“ 哈希表關(guān)鍵字:t”); for(i=0;i if(ha[i].key==NULLKEY || ha[i].key==DELKEY)printf(“ ”); //輸出3個(gè)空格 else printf(“ %3d”,ha[i].key);printf(“ n”);printf(“ 搜索次數(shù):t”);for(i=0;i if(ha[i].key==NULLKEY || ha[i].key==DELKEY)printf(“ ”); //輸出3個(gè)空格 else printf(“ %3d”,ha[i].count);printf(“ n”); for(i=0;i } if(ha[i].key!=NULLKEY && ha[i].key!=DELKEY)avg=avg+ha[i].count;avg=avg/n;printf(“平均搜索長(zhǎng)度ASL(%d)=%gn”,n,avg); void main(){ int x[]={16,74,60,43,54,90,46,31,29,88,77};int n=11,m=13,p=13,i,k=29;HashTable ha;CreateHT(ha,x,n,m,p);printf(“n”);DispHT(ha,n,m);printf(“ 查找關(guān)鍵字29:n”);i=SearchHT(ha,p,k);if(i!=-1)printf(“ ha[%d].key=%dn”,i,k);else printf(“ 未找到%dn”,k);k=77;printf(“ 刪除關(guān)鍵字%dn”,k);DeleteHT(ha,p,k,&n);DispHT(ha,n,m);i=SearchHT(ha,p,k);if(i!=-1)printf(“ ha[%d].key=%dn”,i,k);else printf(“ 未找到%dn”,k); } printf(“ 插入關(guān)鍵字%dn”,k);InsertHT(ha,&n,k,p);DispHT(ha,n,m);printf(“n”); 四，實(shí)驗(yàn)小結(jié) 1、通過(guò)本次實(shí)驗(yàn)，加深了我對(duì)查找表的認(rèn)識(shí)。 2、有序表的查找之折半查找：前提必須是有序表，性能只有在均勻分布的時(shí)候才是最優(yōu)的。 3、二叉排序樹查找：通過(guò)一系列的查找和插入過(guò)程形成的樹。之所以叫做排序樹，因?yàn)榘凑罩行虮闅v可得一個(gè)有序的序列。第二篇：數(shù)據(jù)結(jié)構(gòu)查找實(shí)驗(yàn)報(bào)告
第三篇：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-排序與查找
第四篇：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)(實(shí)驗(yàn)五：查找算法)
第五篇：數(shù)據(jù)結(jié)構(gòu)-實(shí)驗(yàn)8查找的算法
點(diǎn)擊咨詢 