第一篇：數據結構實驗報告-靜態查找表中的查找
數據結構實驗
實驗一 靜態查找表中的查找
一、實驗目的：
1、理解靜態查找表的概念
2、掌握順序查找和折半查找算法及其實現方法
3、理解順序查找和折半查找的特點，學會分析算法的性能
二、實驗內容：
1、按關鍵字從小到大順序輸入一組記錄構造查找表，并且輸出該查找表；
2、給定一個關鍵字值，對所構造的查找表分別進行順序查找和折半查找，輸出查找的結果以及查找過程中“比較”操作的執行次數。
三、實驗要求：
1、查找表的長度、查找表中的記錄和待查找的關鍵字值要從終端輸入；
2、具體的輸入和輸出格式不限；
3、算法要具有較好的健壯性，對錯誤操作要做適當處理；
4、輸出信息中要標明所采用的查找方法類型。
實驗二 基于二叉排序樹的查找
一、實驗目的：
1、理解動態查找表和二叉排序樹的概念
2、掌握二叉排序樹的構造算法及其實現方法
3、掌握二叉排序樹的查找算法及其實現方法
二、實驗內容：
1、輸入一組記錄構造一顆二叉排序樹，并且輸出這棵二叉排序樹的中序序列；
2、給定一個關鍵字值，對所構造的二叉排序樹進行查找，并輸出查找的結果。
三、實驗要求：
1、二叉排序樹中的記錄和待查找的關鍵字值要從終端輸入；
2、輸入的記錄格式為(整數，序號)，例如(3, 2)表示關鍵字值為3，輸入序號為2的記錄；
3、算法要具有較好的健壯性，對錯誤操作要做適當處理。
四、程序實現：
(1)實現順序查找表和折半查找表：
#include
int key[MAX_LENGTH];
int length;}stable;
int seqserch(stable ST,int key,int &count){
int i;
for(i=ST.length;i>0;i--)
{
count++;
if(ST.key[i]==key)
return i;
}
return 0;}
int binserch(stable ST,int key,int &count){
int low=1,high=ST.length,mid;
while(low<=high)
{
count++;
mid=(low+high)/2;
if(ST.key[mid]==key)
return mid;
else if(key high=mid-1; else low=mid+1; } return 0;} main(){ stable ST1; int a,b,k,x,count1=0,count2=0,temp=0; ST1.length=0; printf(“請按從小到大的順序輸入查找表數據：(-1代表結束！)n”); for(a=0;a { scanf(“%d”,&temp); if(temp!=-1) { ST1.key[a]=temp; ST1.length++; } else break; } printf(“輸入數據為：n”); for(b=0;b { printf(“%d ”,ST1.key[b]); } printf(“n請輸入要查找的數據：”); scanf(“%d”,&k); a=seqserch(ST1,k,count1)+1; printf(“n順序查找： 該數據的位置在第：%d個n”,a); printf(“查找次數為：%dnn”,count1-1); a=binserch(ST1,k,count2)+1; printf(“折半查找： 該數據的位置在第：%d個n”,a); printf(“查找次數為：%dn”,count2-1);}（2）二叉排序樹的查找： #include typedef struct node { int data; int key; struct node *left,*right;}bitnode,*bittree; void serchbst(bittree T,bittree *F,bittree *C,int data){ while(T!=NULL) { if(T->data==data) { *C=T; break; } else if(data { *F=T; T=T->left; } else { *F=T; T=T->right; } } return 0;} int insertbst(bittree *T,int key,int data){ bittree F=NULL,C=NULL,s; serchbst(*T,&F,&C,data); if(C!=NULL)return 0; s=(bittree)malloc(sizeof(bitnode)); s->data=data; s->key=key; s->left=s->right=NULL; if(F==NULL)*T=s; else if(data F->left=s; else F->right=s; return 1;} void creatbst(bittree *T){ int key,data;*T=NULL; printf(“請輸入數據以構造二叉排序樹：(數據格式為:m n(-1000,-1000)代表結束)n”); scanf(“%d%d”,&key,&data); while(key!=-1000 || data!=-1000) { insertbst(T,key,data); scanf(“%d%d”,&key,&data); } } void midTraverse(bittree T){ if(T!=NULL) { midTraverse(T->left); printf(“(%d,%d)”,T->key,T->data); midTraverse(T->right); } } main(){ bittree T=NULL,C=NULL,F=NULL; int key,data,temp; creatbst(&T); printf(“此二叉樹的中序序列為：”); midTraverse(T); printf(“n請輸入要查找的關鍵字：”); scanf(“%d”,&data); serchbst(T,&F,&C,data); printf(“此關鍵字的數據為：%dn”,C->key);} 五、實現結果： (1)順序查找和折半查找： (2)二叉樹排序樹查找： 六、實驗之心得體會： （1）在這次實驗中，我基本上掌握了順序查找、折半查找和二叉排序樹查找的基本思想和實現方法，讓我體會到了寫程序時，不僅要考慮是否能夠調試出結果，還要考慮程序實現的效率，這是一個編程人員必須要具備的一項總要的素質。 （2）通過這次實驗，讓我體會到同樣的數據在不同的查詢方法下有著不同的查詢效率，就拿實驗一來說，用順序查找法在12個數據中查找一個關鍵字需要的查找的次數為8次，但是，如果折半查找法卻只要兩次，由此可以看出，我們在查找時不僅要考慮查找的實現，還要考慮查找的效率和查找所用的時間。 （3）用二叉排序樹查找效率也比較高，只要你輸入相應的關鍵字，就可已找到所需要的數據，就我個人看來，用二叉排序樹的效率要比順序查找和折半查找的效率更高，查詢的速度更快。 實驗題9.1 設計一個程序exp9-1.cpp，輸出在順序表{3，6，2，10，1，8，5，7，4，9}中采用順序方法找關鍵字5的過程。程序如下： //文件名:exp9-1.cpp #include KeyType key; //KeyType為關鍵字的數據類型 //其他數據 //定義表中最多記錄個數 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(“關鍵字序列:”);for(i=0;i 截圖如下： 實驗題9.2 設計一個程序exp9-2.cpp，輸出在順序表{1，2，3，4，5，6，7，8，9，10}中采用折半查找法查找關鍵字9的過程。 程序如下： //文件名:exp9-2.cpp #include //定義表中最多記錄個數 KeyType key; //KeyType為關鍵字的數據類型 InfoType data; //其他數據 } 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) //繼續在R[low..mid-1]中查找 high=mid-1; else low=mid+1; //繼續在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(“關鍵字序列:”);for(i=0;i 比 較 元 素 中 } else printf(“元素%d的位置是%dn”,k,i);printf(“元素%d不在表中n”,k); 截圖如下： 實驗題9.3 設計一個程序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}中采用分塊查找法查找（每塊的塊長為5，共5塊）關鍵字46的過程。 程序如下： //文件名:exp9-3.cpp #include KeyType key; //KeyType為關鍵字的數據類型 //定義表中最多記錄個數 //定義索引表的最大長度 InfoType data; //其他數據 } NodeType;typedef NodeType SeqList[MAXL];typedef struct { KeyType key;int link; //KeyType為關鍵字的類型 //指向分塊的起始下標 //順序表類型 } 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為每塊的記錄個數 printf(“二分查找n”);while(low<=high) //在索引表中進行二分查找,找到的位置存放在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++; //累計在索引表中的比較次數 } if(low //在索引表中查找成功后,再在線性表中進行順序查找 { 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累計在順序表對應塊中的比較次數 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”); 截圖如下： 《數據結構》 第八次實驗報告 學生姓名 學生班級 學生學號 指導老師 重慶郵電大學計算機學院 計算機專業實驗中心 一、實驗內容 1)有序表的二分查找 ?建立有序表，然后進行二分查找 2)二叉排序樹的查找 ?建立二叉排序樹，然后查找 二、需求分析 二分查找的基本思想是將n個元素分成大致相等的兩部分，取a[n/2]與x做比較，如果x=a[n/2],則找到x,算法中止；如果x 三、概要設計 1、順序查找，在順序表R[0..n-1]中查找關鍵字為k的記錄，成功時返回找到的記錄位置，失敗時返回-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]中進行二分查找，成功時返回記錄的位置，失敗時返回-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 四、詳細設計 源代碼： #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] 五、心得體會 通過這次在實現順序和二分查找算法的過程中，讓我對順序和二分查找算法有了更多的了解。查找根據給定的某個值，在查找表中確定一個其關鍵字等于給定值的數據元素或（記錄）的操作，應用十分廣泛。順序查找是一種最簡單的查找方法。它的基本思路是：從表的一端開始,順序掃描線性表,依次將掃描到的關鍵字和給定值k相比較,若當前掃描到的關鍵字與k相等,則查找成功；若掃描結束后,仍未找到關鍵字等于k的記錄,則查找失敗。二分查找也稱為折半查找要求線性表中的結點必須己按關鍵字值的遞增或遞減順序排列。它首先用要查找的關鍵字k與中間位置的結點的關鍵字相比較,這個中間結點把線性表分成了兩個子表,若比較結果相等則查找完成;若不相等,再根據k與該中間結點關鍵字的比較大小確定下一步查找哪個子表,這樣遞歸進行下去,直到找到滿足條件的結點或者該線性表中沒有這樣的結點。在學習過程中，善于發現，會找到更多的捷徑。 六、附錄 運行結果截圖。 電 子 科 技 大 學 實 驗 報 告 學生姓名：XXX 學 號：20*** 指導教師：劉嶠 實驗地點：信軟機房306 實驗時間：2014/6/20 一、實驗室名稱：軟件實驗室 二、實驗項目名稱：數據結構與算法—排序與查找 三、實驗學時：4 四、實驗原理： 快速排序的基本思想是：通過一躺排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一不部分的所有數據都要小，然后再按次方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。 假設要排序的數組是A[1]……A[N]，首先任意選取一個數據（通常選用第一個數據）作為關鍵數據，然后將所有比它的數都放到它前面，所有比它大的數都放到它后面，這個過程稱為一躺快速排序。一躺快速排序的算法是： 1）設置兩個變量I、J，排序開始的時候I：=1，J：=N 2）以第一個數組元素作為關鍵數據，賦值給X，即X：=A[1]； 3）從J開始向前搜索，即（J：=J-1），找到第一個小于X的值，兩者交換； 4）從I開始向后搜索，即（I：=I+1），找到第一個大于X的值，兩者交換； 5）重復第3、4步，直到I=J。 二分法查找（折半查找）的基本思想： （1）確定該區間的中點位置：mid=（low+high）/2 min代表區間中間的結點的位置，low代表區間最左結點位置，high代表區間最右結點位置 （2）將待查a值與結點mid的關鍵字（下面用R[mid].key）比較，若相等，則查找成功，否則確定新的查找區間： A)如果R[mid].key>a，則由表的有序性可知，R[mid].key右側的值都大于a，所以等于a的關鍵字如果存在，必然在R[mid].key左邊的表中,這時high=mid-1; B)如果R[mid].key C)如果R[mid].key=a，則查找成功。 （3）下一次查找針對新的查找區間，重復步驟（1）和（2） （4）在查找過程中，low逐步增加，high逐步減少，如果high 五、實驗目的： 本實驗通過實現快速排序和折半查找算法，使學生理解如何實現快速查找和排序的基本算法思想。通過練習，加強對算法的理解，提高編程能力。 六、實驗內容： （1）實現數據序列的輸入; （2）實現快速排序算法,并對輸入的序列排序后輸出； （3）實現折半查找算法,并在步驟(2)排序后的序列上,進行任意地 查找,并輸出查詢結果。 七、實驗器材（設備、元器件）： 八、數據結構及程序 #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機一臺，裝有C/C++語言集成開發環境。 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;} 九、程序運行結果： 1.打開程序： 2.嘗試手動輸入模式： 3.搜索已存在數： 4.搜索不存在數： 5.嘗試文件讀入模式并搜索 實驗成功。 十、實驗結論： 使用好的排序與查找算法對于程序的運行效率至關重要，一個好的算法，適合的算法能使計算機對數據的處理事半功倍，而選用錯誤的算法，不但可能事倍功半，還有可能造成不穩定因素。 快速排序的時間復雜度為n（log2n）,是排序算法中最為快速的一種，但是不穩定，對基本有序的序列效率較差。 二分查找算法在查找算法中，速度快，效率高，但是要求數據要有序。 十一、總結及心得體會： 當空間充足，對穩定性要求不高的情況，排序算法宜使用快速排序。 快速排序和二分查找配合，可以以較高的效率查找目標元素。 編號： 139 數據結構與算法課程設計 說明書 動態查找表 學 院： 海洋信息工程學院 專 業： 計算機科學與技術 學生姓名： 學 號： 指導教師： 2015年月 26 日 動態查找表 學生姓名：銀杰 指導老師：王曉瑩 摘 要 本課程設計說明書系統地闡述了我使用C語言在Code::Blocks軟件編寫的動態查找表程序的整個過程，編寫的環境是win7 64位操作系統。根據題目要求，編寫動態查找表使用二叉排序樹，即二叉鏈表作為存儲結構。該程序具有建立數據功能、具有數據查找功能、具有數據插入功能、具有數據刪除功能等基本功能操作。 關鍵詞：動態查找表，Code::Blocks軟件，win7 64位操作系統，C# dynamic lookup table Author :yinjie Tutor :Wangxiaoying Abstract This course design specification system to explain the whole process of using C language in Code:: Blocks software written in the dynamic look-up table program, the preparation of the environment is win7 64 bit operating system.According to the topic request, the preparation of the dynamic look-up table using the two fork sort tree, that is, the two binary list as the storage structure.The program has the function of building data, data searching, data insertion, data deletion and so on.Key words:dynamic lookup table, Code::Blocks software,win7 64 bit operating system，C # 目 錄 引言.........................................................................................................................................................................1 查找的基本概念.................................................................................................................................................1 小結.....................................................................................................................................................................1 題目.....................................................................................................................................................................1 第1章 程序的構圖設計.....................................................................................................................................2 1.1動態查詢表：...............................................................................................................................................2 1.2程序功能流程圖：.......................................................................................................................................2(1)、主函數模塊............................................................................................................................................2(2)、二叉排序樹的生成................................................................................................................................3(3)、二叉排序樹的查找模塊........................................................................................................................4(4)、二叉排序樹的插入模塊........................................................................................................................4(5)、二叉排序樹刪除連接模塊....................................................................................................................5(6)、二叉排序樹的刪除模塊........................................................................................................................5(7)、二叉排序樹的遍歷模塊........................................................................................................................6 第2章 詳細設計的程序.....................................................................................................................................6 各函數模塊.........................................................................................................................................................6(1)主函數模塊................................................................................................................................................6(2)二叉排序樹的生成模塊............................................................................................................................8(3)二叉排序樹的查找模塊............................................................................................................................8(4)二叉排序樹的插入模塊............................................................................................................................9(5)多態查找表刪除模塊..............................................................................................................................10(6)二叉排序樹的中序遍歷模塊..................................................................................................................12 第3章 程序測試和運行.....................................................................................................................................12 3.1 程序測試....................................................................................................................................................12 3.2 程序運行....................................................................................................................................................13 1、主界面 ...................................................................................................................................................13 2、建立二叉排序樹模塊界面.....................................................................................................................13 3、二叉排序樹查找模塊界面.....................................................................................................................14 4、二叉排序樹插入模塊界面.....................................................................................................................14 5、二叉排序樹刪除模塊界面 ...................................................................................................................14 6、退出程序的界面.....................................................................................................................................14 總 結.....................................................................................................................................................................15 程序完成情況...................................................................................................................................................15 有待改進之處...................................................................................................................................................15 課程設計期間的收獲.......................................................................................................................................15 附錄源代碼如下...................................................................................................................................................17 桂林電子科技大學課程設計說明書 引言 查找的基本概念 查找又稱為檢索，就是從一個數據元素集合中找出某個特定的數據元素。查找是數據處理中最為常用的一種操作，查找算法的優劣對整個軟件系統的效率影響很大，尤其當所涉及的數據量較大時，更是如此。在一個數據集合中進行查找操作可選用的方法與該數據元素集合的存儲結構有很大關系。 查找是根據某個給定的值，在數據元素構成的集合中確定是否在這樣一個數據元素，它的關鍵字等于給定值的關鍵字。 要進行查找，必須明確要查找對象的特征，也就是要查找元素的關鍵值。如果在數據集合中能找到與給定值相等的關鍵字，則該關鍵字所屬的數據元素就是所要查找的數據元素，此時稱該查找成功；如果查遍了整個數據元素集合也未能找到與給定值相等的關鍵字，則稱該查找失敗。小結 當然對于這個說明書，我不可能做得至善至美，但是一些基本的格式內容還是符合要求的。首先，我對查找表進行一個簡要的概述。然后，我就查找表進行了詳細的分析，這是設計中很重要的一步。接下來，我把查找表中所有的設計簡明清晰地展現出來，并把我在設計中遇到的問題和分析解決問題的辦法做了分析。最后，在結論中，我對自己的課程設計做了總體的評價同時簡述了我在這次課程設計中的收獲和經驗。 題目 選題十二：動態查找表 【問題描述】 利用二叉排序樹完成動態查找表的建立、指定關鍵字的查找、插入與刪除指定關鍵字結點。【任務要求】 算法輸入：指定一組數據。 桂林電子科技大學課程設計說明書 算法輸出：顯示二叉排序樹的中序遍歷結果、查找成功與否的信息、插入和刪除后的中序遍歷結果(排序結果)。 算法要點：二叉排序樹建立方法、動態查找方法,對樹進行中序遍歷。【測試數據】 自行設定，注意邊界等特殊情況。 第1章 程序的構圖設計 1.1動態查詢表： 依照輸入的一組數據{56,80,65,20}所得的二叉排序樹如下（a）所示：當插入11的時候就如（b）所示。 562065801 156206580 （a） （b）1.2程序功能流程圖： (1)、主函數模塊 桂林電子科技大學課程設計說明書 開始打印輸出動態表的6個功能選擇欄do循環輸入選擇號hSwitch(h)執行對應函數模塊程序退出結束 (2)、二叉排序樹的生成 開始輸入數據個數Xfor循環輸入X個數據調用插入函數Insert二叉樹建成結束 桂林電子科技大學課程設計說明書 (3)、二叉排序樹的查找模塊 開始二叉排序樹是否為空否根結點關鍵字？key是大于遞歸返回在左子樹查找遞歸返回等于小于在右子樹查找查找失敗查找成功結束 (4)、二叉排序樹的插入模塊 開始調用查詢函數Search()是否查詢成功否被插入結點*s為新的根結點是插入的節點根結點<被插結點*s為左孩子插入成功結束 >被插結點*s為右孩子 桂林電子科技大學課程設計說明書 (5)、二叉排序樹刪除連接模塊 開始左右子樹是否為空是While循環否向右走到盡頭重接它的左右子樹將被刪結點的前驅s的內容直接替代該結點的內容被刪除結點的左子樹的右子樹是否為空否重接*q的右子樹是重接*q的左子樹連接成功結束(6)、二叉排序樹的刪除模塊 開始輸入要刪除的的數據是否存在關鍵字等于n的數據元素否調用刪除的連接函數Delete()結束返回是找到關鍵字并刪除 桂林電子科技大學課程設計說明書 (7)、二叉排序樹的遍歷模塊 開始二叉樹根是否為空否對左子樹按中序遍歷進行訪問根結點對右子樹按中序遍歷進行遍歷完成結束是遞歸調用 第2章 詳細設計的程序 各函數模塊 (1)主函數模塊： 用主函數main()來實現。主要是通過設計一個do()函數并讓主函數調用它來顯示主菜單，讓用戶選擇操作。在do()函數中，我應用了switch-case語句來進行選擇，是個比較簡單實現的模塊。最后若選擇“5”退出循環。否則繼續循環。主要代碼如下： int main(){ bitree T=NULL,p;ElemType e;int n;int h;char c; do{ printf(“********************************************************n”); 桂林電子科技大學課程設計說明書 printf(“* *n”); printf(“* 動態查找表 *n”); printf(“* 1.建立二叉排序樹 *n”); printf(“* 2.二叉排序樹查找元素 *n”); printf(“* 3.二叉排序樹插入元素 *n”); printf(“* 4.二叉排序樹刪除元素 *n”); printf(“* 5.退出 *n”); printf(“* *n”); printf(“********************************************************n”); printf(“請輸入你的選擇: n”); scanf(“%d”,&h); switch(h) { case 1:Init(T);printf(“中序遍歷二叉排序樹: ”);Zhongxu(T);printf(“n”); break; case 2:printf(“請輸入要查找的數據:n”);scanf(“%d”,&n);e.key=n; if(Search(T,e,NULL,p)) printf(“數據已經存在!n”); else { printf(“數據不存在!n”);} break; case 3:printf(“請輸入要插入的數據:n”);scanf(“%d”,&n);e.key=n; if(Search(T,e,NULL,p)) printf(“已經存在!n”); else{Insert(T, e);printf(“成功插入!n”);printf(“中序遍歷二叉排序樹: ”);Zhongxu(T);printf(“n”);} break; case 4:printf(“請輸入要刪除的數據:n”);scanf(“%d”,&n);e.key=n; if(Search(T,e,NULL,p)) { Deletebit(T,n);printf(“已經成功刪除!n”);printf(“中序遍歷二叉排序 桂林電子科技大學課程設計說明書 樹: ”);Zhongxu(T);printf(“n”);} else printf(“數據不存在!n”); break; case 5:printf(“退出！n”); break; default:printf(“選擇錯誤，重新開始!n”); } } while(h!=5);}(2)二叉排序樹的生成模塊： 二叉排序樹的生成，是從空的二叉排序樹開始，每輸入一個結點數據，就調用一次插入算法將它插到當前已經生成的二叉排序樹中。主要代碼如下： void Init(bitree &T)//構造一個動態查找表T { int x;int i;int n; ElemType e;printf(“請輸入結點個數: ”);scanf(“%d”,&x); for(i=1;i<=x;i++) { printf(“第%d個結點數據值:”,i);scanf(“%d”,&n); e.key=n;Insert(T,e); } printf(“二叉排序樹已經建立!n”);} (3)二叉排序樹的查找模塊： 二叉排序樹的查找方法如下。當二叉排序樹為空時，查找失敗。 當二叉排序樹根結點的關鍵字等于key時，查找成功。 桂林電子科技大學課程設計說明書 當二叉排序樹根結點的關鍵字大于key時，從根結點的左子樹中以同樣方法進行查找。當二叉樹根結點的關鍵字小于key時，從根結點的右子樹以同樣方法進行查找。顯然，該過程是一個遞歸過程，下面給出這一算法的實現。 主要代碼： bitree Search(bitree T,ElemType e,bitree f,bitree &p)//在二叉排序樹中查找數據 { if(!T) { p=f; return NULL; }//查找不成功 else if(T->data.key==e.key) { p=T;return T; } //查找成功 else if(T->data.key>e.key) return Search(T->lchild,e,T,p); else return Search(T->rchild,e,T,p);}//在二叉排序樹中查找數據(4)二叉排序樹的插入模塊： 若要將一個關鍵字值為key的結點t插到二叉排序樹中，只需要使該結點插入后，二叉排序樹中的元素依然按照原來的規律排列即可。二叉排序樹的插入方法如下。 若二叉排序樹是空樹，則key稱為二叉排序樹的根。 若二叉排序樹為非空，則將key與二叉排序樹的根結點進行比較：如果key的值等于根結點的值，則停止插入；如果key的值小于根結點的值，則將key插到左子樹；如果key的值大于根結點的值，則將key插到右子樹中。主要代碼如下： void Insert(bitree &T,ElemType e)//在二叉排序樹中插入數據 桂林電子科技大學課程設計說明書 { bitree p,s; if(!Search(T,e,NULL,p))//查找不成功 { s=(bitree)malloc(sizeof(bitnode)); s->data=e;s->lchild=s->rchild=NULL; if(!p)T=s;//被插入結點*s為新的根結點 else if(e.key data.key) p->lchild=s;//被插結點*s為左孩子 else p->rchild=s;//被插結點*s為右孩子 } }(5)多態查找表刪除模塊： 從二叉排序樹中刪除一個結點，不能簡單地把以該結點為根的子樹都刪除，只能刪除掉該結點，并且還應該保證刪除后所得到的二叉樹依然滿足二叉樹的性質不變。也就是說，在二叉排序樹中刪除一個結點相當于刪除有序序列中的一個結點。 假設要刪除的結點為P，其雙親結點為F，同時假設結點P是結點F的左孩子（右孩子的情況類似）。刪除操作首先要確定被刪結點P是否在二叉排序樹中。若不在，則不做任何操作；若在，分為以下三種情況討論。若P為葉子結點，可直接將其刪除。 若結點P只有左子樹，或只有右子樹，則可將P的左子樹或右子樹直接改為其雙親結點F的左子樹或右子樹。 若P既有左子樹，又有右子樹此時有兩種處理方法。 方法1：首先找到結點P在中序序列中的直接前驅結點S，然后用結點P的左子樹改為F的左子樹，而將P的右子樹改為S的右子樹。 方法2：首先找到結點P在中序序列中的直接前驅結點s，然后用結點s的值替代結點p的值，再將結點s刪除，原結點s的左子樹改為s的雙親結點q的右子樹。主要代碼如下： 桂林電子科技大學課程設計說明書 void Delete(bitree &p)//從二叉排序樹中刪除結點p，并重接它的左或右子樹 { bitree q,s; if(!p->rchild)//右子樹空，只需重接它的左子樹 { q=p;p=p->lchild;free(q);q=NULL; } else if(!p->lchild)//左子樹空，只需重接它的右子樹 { q=p;p=p->rchild;free(q);q=NULL; } else{//左右子樹均不空 q=p;s=p->lchild; while(s->rchild)//向右走到盡頭 { q=s;s=s->rchild; } p->data=s->data;//將被刪結點的前驅s的內容直接替代該結點的內容 if(q!=p)//若被刪除結點的左子樹的右子樹不為空 q->rchild=s->lchild;//重接*q的右子樹 else q->lchild=s->lchild;//重接*q的左子樹 free(s);s=NULL; } }//刪除結點 void Deletebit(bitree &T,int n)//刪除二叉排序樹中的數據 { if(!T)return;//不存在關鍵字等于n的數據元素 桂林電子科技大學課程設計說明書 else{ if(T->data.key==n)return(Delete(T));//找到關鍵字等于n的數據元素并刪除它 else if(T->data.key>n)Deletebit(T->lchild,n);//繼續在左子樹中刪除 else Deletebit(T->rchild,n);//繼續在右子樹中刪除 } } (6)二叉排序樹的中序遍歷模塊： 中序遍歷二叉樹定義：若二叉樹根為空，則返回；否則，中序遍歷左子樹；訪問根結點；中序遍歷右子樹。主要代碼如下： void Zhongxu(bitree T)//中序遍歷 { if(T!=NULL) { Zhongxu(T->lchild); printf(“%d ”,T->data.key); Zhongxu(T->rchild); } } 第3章 程序測試和運行 3.1 程序測試 程序測試是程序質量保證的主要活動之一，在程序編寫的過程中，在各個階段都有可能存在錯誤和缺陷。通過測試是可以發現程序設計中存在的種種問題，并可以及時改正。避免在程序運行時才出現不必要的錯誤。測試是質量保證一個臨界和決定懲罰，它提供對程序說明、設計和編碼的最終評審。是發現程序缺陷和錯誤的有力手段。根據系統設計目標和功能，對系統進行測試。 桂林電子科技大學課程設計說明書 1、功能性 （1）程序實現的主要功能，包括查詢，插入，刪除等。 （2）題目要求的輸入輸出字段，以及題目要求的輸入限制。 2、可靠性 程序正確實現了對動態查找表的查詢、插入、刪除等各種功能。 3、易用性 現有程序實現了如下易用性： （1）查詢，插入，刪除，操作相關提示信息的一致性，可理解性 ? （2）輸入限制的正確性 （3）輸入限制提示信息的正確性，可理解性，一致性 （4）界面排版簡潔完整 3.2 程序運行 1、主界面 ： 2、建立二叉排序樹模塊界面 ： 桂林電子科技大學課程設計說明書 3、二叉排序樹查找模塊界面 ： 4、二叉排序樹插入模塊界面 ： 5、二叉排序樹刪除模塊界面 ： 6、退出程序的界面 ： 桂林電子科技大學課程設計說明書 總 結 程序完成情況 在編寫程序寫課程設計的時間里，雖然歷經重重困難和挫折，但是在我自己的努力和老師的幫助下終于完成了動態查找表的設計。盡管該程序在功能和性能上可能還有一些缺陷，但是我已經完成了課程設計的任務和目標，達到了題目基本要求，成功完成了算法與數據結構課程設計。有待改進之處 有待改進： 1、我在編寫程序的時候，用的是C++格式去保存編譯的，用了C語言來編寫，但是有一些C++的形式，當我用C來新建保存的時候卻出現問題。所以程序我是用C++來新建保存的。 2、流程圖畫的不是很規范表準，在一些邏輯表達上不夠簡潔清晰。課程設計期間的收獲 在完成此次的課程設計的過程中，我跨越了傳統方式下的教與學的體制束縛，桂林電子科技大學課程設計說明書 通過自己的思考和設計，培養了自學能力和動手能力。并且由原先的被動的接受知識轉換為主動的尋求知識，這可以說是學習方法上的一個很大的突破。在以往的傳統的學習模式下，我們可能會記住很多的書本知識，但是通過課程設計，我們學會了如何將學到的知識轉化為自己的東西，學會了怎么更好的處理知識和實踐相結合的問題。 通過這次課程設計，我認識到數據結構與算法是計算機科學的基礎課程，是我們學習的核心課程。我對數據結構和算法又有了新的認識。數據結構的研究不僅涉及到計算機軟件，而且和計算機硬件的研究也有著密切的關系，無論是編譯程序還是操作系統，都涉及到數據元素在存儲器中的分配問題。在研究信息檢索時也必須考慮如何組織數據，以便使查找和存取數據元素更為方便。可以認為數據結構是介于數學、計算機硬件和計算機軟件三者之間的一個核心內容，是從事計算機科學研究及其應用的人必須掌握的重要內容。 這次的課程設計有效的培養了我們獨立思考的能力，提高了我們的動手操作水平。在具體設計中，我們鞏固了上學期所學的數據結構與算法的理論知識，進一步提高了自己的編程能力。這也是課程設計的目的所在。通過編程實踐，不僅開發了自己的邏輯思維能力，培養了分析問題、解決問題的能力，更充分鍛煉了我們的編程能力。 在這次課程設計中我也知道了的編程能力不強，有很多程序與算法是借鑒別人的，我想只要我有自己寫程序，并且結合他人的程序算法，把程序完成，那我還是學習到東西了的。 在課程設計中我體會到：一個好的程序應該是一個高內聚低耦合的程序。而要做出一個好的程序則應該通過對算法與其數據結構的時間復雜度和空間復雜度進行實現與改進。然而，實際上很難做到十全十美，原因是各要求有時相互制約，要節約算法的執行時間往往要以犧牲更多的存儲空間為代價：而為了節省存儲空間又可能要以更多的時間為代價。因此，只能根據具體情況有所側重：如果程序的使用次數較少，則應該力求算法簡單易懂；如果程序反復多次使用，則應該盡可能選用快速算法或者設置為內聯函數；如果解決問題的數據量極大，但是機器的內存空間不是很充足，則在編寫算法時應該考慮如何節省空間。 學習了《數據結構與算法》這門課，我們在編寫程序時就應該注意到所編寫程序的時間復雜度和空間復雜度，以及是否運用了良好的算法，而不是只是象以前編寫程序時單純使用C++的知識。我們要充分考慮程序的性能，從而編寫出更好的程序。 桂林電子科技大學課程設計說明書 在設計報告的寫作過程中我也學到了做任何事情都要有的心態，首先我明白了做學問要一絲不茍，對于出現的任何問題都不要輕視，要通過正確的途徑去解決，在做事情的過程中要有耐心和毅力，不要一遇到困難就打退堂鼓，只要堅持下去就可以找到思路去解決問題的，在遇到問題時，有必要向老師和同學請教，合作溝通的意義是巨大的。 在這次課程設計中，我認識到了自己的不足之處同時我也收獲了很多知識和經驗，在今后的學習中，我一定勤于思考，并靈活運用所學知識，多進行編程實踐。在總結反思和編程訓練中，不斷提升自己的編程能力。相信在我的努力下，我的程序設計水平一定會不斷提高。 參考文獻 [1]數據結構與算法/汪沁，奚李峰主編.-北京：清華大學出版社，2012.9（第8章 查找） [2]百度文庫>專業資料>IT/計算機>計算機軟件及應用>動態查找表實驗報告 http://wenku.baidu.com/link?url=crizbdK6WO86YXeSJWwkHNdXpaxUDkRJnoShcVDJqBfGO03Cbk6LAdVwBYHxE82kYHkuIjC1HFCiOrSiEWJXOOspWGIo3PNSDjbeY1jHbJu 附錄源代碼如下： 數據結構與算法的課程設計1.cpp第二篇：數據結構查找實驗報告
第三篇：數據結構實驗報告-查找算法
第四篇：數據結構實驗報告-排序與查找
第五篇：數據結構課程設計：動態查找表
點擊咨詢 