1、班級 學號 姓名 實驗組別 實驗日期 室溫 報告日期 成績 報告內容：（目的和要求、原理、步驟、數據、計算、小結等）實驗名稱：查找與排序算法的實現和應用實驗目的：1. 掌握順序表中查找的實現及監視哨的作用。2. 掌握折半查找所需的條件、折半查找的過程和實現方法。3. 掌握二叉排序樹的創建過程，掌握二叉排序樹查找過程的實現。4. 掌握哈希表的基本概念，熟悉哈希函數的選擇方法，掌握使用線性探測法和鏈地址法進行沖突解決的方法。5. 掌握直接插入排序、希爾排序、快速排序算法的實現。實驗環境（硬/軟件要求）：Windows 2000,Visual C+ 6.0實驗內容： 通過具體算法程序，進一步加深對各

2、種查找算法的掌握，以及對實際應用中問題解決方法的掌握。各查找算法的輸入序列為：26 5 37 1 61 11 59 15 48 19 輸出要求：查找關鍵字37，給出查找結果。對于給定的某無序序列，分別用直接插入排序、希爾排序、快速排序等方法進行排序，并輸出每種排序下的各趟排序結果。各排序算法輸入的無序序列為：26 5 37 1 61 11 59 15 48 19。實驗要求：一、查找法1. 順序查找首先從鍵盤輸入一個數據序列生成一個順序表，然后從鍵盤上任意輸入一個值，在順序表中進行查找。2. 折半查找任意輸入一組數據作為個數據元素的鍵值，首先將此序列進行排序，然后再改有序表上使用折半查找算法進一

3、對給定值key的查找。3. 二叉樹查找任意輸入一組數據作為二叉排序樹中節點的鍵值，首先創建一顆二叉排序樹，然后再次二叉排序樹上實現對一定k的查找過程。 4.哈希表查找 任意輸入一組數值作為個元素的鍵值，哈希函數為Hash（key）=key%11,用線性探測再散列法解決沖突問題。二、排序算法編程實現直接插入排序、希爾排序、快速排序各算法函數；并編寫主函數對各排序函數進行測試。實驗原理：1.順序查找：在一個已知無(或有序）序隊列中找出與給定關鍵字相同的數的具體位置。原理是讓關鍵字與隊列中的數從最后一個開始逐個比較，直到找出與給定關鍵字相同的數為止，它的缺點是效率低下。二分查找又稱折半查找，優點是比

4、較次數少，查找速度快，平均性能好；其缺點是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經常變動而查找頻繁的有序列表。首先，假設表中元素是按升序排列，將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關鍵字大于查找關鍵字，則進一步查找前一子表，否則進一步查找后一子表。重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。2.哈希查找：哈希查找的操作步驟：用給定的哈希函數構造哈希表；根據選擇的沖突處理方法解決地址沖突；在哈希表的基礎上執行哈希查找。 哈希查找的本質是先

5、將數據映射成它的哈希值。哈希查找的核心是構造一個哈希函數，它將原來直觀、整潔的數據映射為看上去似乎是隨機的一些整數。哈希查找的產生有這樣一種背景有些數據本身是無法排序的(如圖像)，有些數據是很難比較的(如圖像)。如果數據本身是無法排序的，就不能對它們進行比較查找。如果數據是很難比較的，即使采用折半查找，要比較的次數也是非常多的。因此，哈希查找并不查找數據本身，而是先將數據映射為一個整數(它的哈希值)，并將哈希值相同的數據存放在同一個位置一即以哈希值為索引構造一個數組。在哈希查找的過程中，只需先將要查找的數據映射為它的哈希值，然后查找具有這個哈希值的數據，這就大大減少了查找次數。如果構造哈希函數

6、的參數經過精心設計，內存空間也足以存放哈希表，查找一個數據元素所需的比較次數基本上就接近于一次。 3.排序算法: 排序(Sorting) 是計算機程序設計中的一種重要操作，它的功能是將一個數據元素（或記錄）的任意序列，重新排列成一個關鍵字有序的序列。開始流程圖：輸入查找條件用戶輸入輸出結果排序創建二叉樹 是是否繼續中序遍歷 否結束實驗代碼：一、查找法1、順序查找#include <stdio.h>#define MAX 100typedef int keytype; typedef struct keytype key;elemtype;typedef struct elemtyp

7、e elemMAX+1; int length;SStable;void create_seq(SStable*list);int seq_search(SStable*list,keytype k);void main() SStable *list,table; keytype key;int i;list=&table;printf("請輸入順序表的長度：");scanf("%d",&list->length);create_seq(list);printf("創建的順序表內容：n");for(i=0;i&

8、lt;list->length;i+)printf("list.elem%d.key=%dn",i+1,list->elemi.key);printf("輸入查找關鍵字：");scanf("%d",&key);seq_search(list,key);void create_seq(SStable *list) int i; printf("請輸入順序表的內容：n");for(i=0;i<list->length;i+) printf("list.elem%d.key=&q

9、uot;,i+1); scanf("%d",&list->elemi.key);int seq_search(SStable*list,keytype k) int i=0,flag=0; while(i<list->length) if(list->elemi.key=k) printf("查找成功.n"); flag=1; printf("list.elem%d.key=%dn",i+1,k);i+;if(flag=0)printf("沒有找到數據%d!n",k);return(

10、flag);2、 折半查找#include<stdio.h>#define MAX 100typedef struct int elemMAX+1;int length;Stable;void creat_seq(Stable*list);int sort_seq(Stable*list);int bin_search(Stable*list,int k,int low,int higt);void main() Stable *list,table;int i,key;list=&table;printf("請輸入線性表的長度：");scanf(&qu

11、ot;%d",&list->length);creat_seq(list);sort_seq(list);printf("排列后的數據n");for(i=1;i<=list->length;i+)printf("list.elem%d.key=%dn",i,list->elemi);printf("n請輸入查找的值:");scanf("%d",&key);bin_search(list,key,1,list->length);void creat_seq(St

12、able*list) int i;printf("請輸入順序表的內容:n");for(i=1;i<=list->length;i+)printf("list.elem%d.key=",i);scanf("%d",&list->elemi);int sort_seq(Stable*list) int i,j,flag;for(i=1;i<list->length;i+)flag=0;for(j=1;j<list->length-i+1;j+)if (list->elemj>l

13、ist->elemj+1)list->elem0=list->elemj+1;list->elemj+1=list->elemj;list->elemj=list->elem0;flag=1;if(flag=0)return 1;int bin_search(Stable*list,int k,int low,int high) int mid;if(low>high) printf("沒有找到要查找的值n");return(0);mid=(low+high)/2;if(list->elemmid=k) printf(&

14、quot;查找成功n");printf("list%d=%dn",mid,k);return(mid);elseif(list->elemmid<k)return(bin_search(list,k,mid+1,high);elsereturn(bin_search(list,k,low,mid-1);3、 二叉樹查找#include <stdio.h>#include <stdlib.h>typedef struct bitnodeint key;struct bitnode *lchild; struct bitnode *

15、rchild;bnode;void ins_bitree(bnode *p,int k)bnode *q;if(p->key >k&&p->lchild)ins_bitree(p->lchild,k);else if(p->key<=k&&p->rchild)ins_bitree(p->rchild,k);else q=(bnode *)malloc(sizeof(bnode);q->key=k;q->lchild=NULL; q->rchild=NULL;if(p->key>k)p-

16、>lchild=q;else p->rchild=q;void bit_search(bnode *p,int k)if(p->key>k&&p->lchild)bit_search(p->lchild,k);else if(p->key<k&&p->rchild)bit_search(p->rchild,k);else if(p->key =k)printf("查找成功!n");else printf("%d不存在!n");void inorder(bno

17、de *p)if(p)inorder(p->lchild);printf("%4d",p->key);inorder(p->rchild);void main () int k;bnode *p;p=NULL;printf("請輸入二叉樹結點的值，輸入0結束:n");scanf("%d",&k);p=(bnode *)malloc(sizeof(bnode);p->key=k;p->lchild=NULL;p->rchild=NULL;scanf("%d",&k)

18、;while (k>0)ins_bitree(p,k);scanf("%d",&k);printf("n");printf("二叉樹排序的結果:");inorder(p);printf("n請輸入查找的值:n");scanf("%d",&k);bit_search(p,k);4、哈希表查找#include <stdio.h>#define MAX 11void ins_hash(int hash,int key)int k,k1,k2;k=key%MAX;if(

19、hashk=0)hashk=key;return ;elsek1=k+1;while(k1<MAX&&hashk1!=0)k1+;if(k1<MAX)hashk1=key;return ; k2=0; while(k2<k&&hashk2!=0)k2+;if(k2<k) hashk2=key; return ;void out_hash(int hash)int i;for(i=0;i<MAX;i+)if(hashi)printf("hash%d=%dn",i,hashi);void hash_search(in

20、t hash,int key)int k,k1,k2,flag=0;k=key%MAX;if(hashk=key)printf("hash%d=%d",k,key);flag=1;else k1=k+1;while(k1<MAX&&hashk1!=key)k1+;if(k1<MAX)printf("hash%d=%d",k1,key);flag=1;k2=0;if(!flag)while(k2<k&&hashk2!=key)k2+;if(k2<k)printf("hash%d=%d&quo

21、t;,k2,key);flag=1;if(flag)printf("查找成功！n");return;elseprintf("查找失敗！n");return;void main()int i,key,k,sum=0;int hashMAX;for(i=0;i<MAX;i+)hashi=0;printf("請輸入數據，以0結束：n");scanf("%d",&key);sum+;while(key&&sum<MAX)ins_hash(hash,key);scanf("%d&

22、quot;,&key);sum+;printf("n");out_hash(hash);printf("n");printf("請輸入查找的值：");scanf("%d",&k);hash_search(hash,k);printf("n");二、排序算法#include<stdio.h>#include<time.h>#define size 11typedef char datatype;typedef struct int key;datatype

23、others;rectype;void INSERTSORT(rectype R) int i,j;for (i=2;i<=size;i+) R0=Ri;j=i-1;while (R0.key<Rj.key) Rj+1=Rj;j-;Rj+1=R0;void SHELLSORT(rectype R,int n)int i,j,h;rectype temp;h=n/2;while(h>0)for(j=h;j<=n-1;j+)temp=Rj;i=j-h;while (i>=0)&&temp.key<Ri.key)Ri+h=Ri;i=i-h;Ri+h

24、=temp;h=h/2;int PARTITION(rectype R,int l,int h)int i,j;rectype temp;i=1;j=h;temp=Ri;dowhile (Rj.key>=temp.key)&&(i<j)j-;if(i<j)Ri+=Rj;while (Ri.key<=temp.key)&&(i<j)i+;if(i<j) Rj-=Ri;while(i!=j);Ri=temp; return i;void QUICKSORT(rectype R,int s1,int t1) int i; if(s1

25、<t1) i=PARTITION(R,s1,t1); QUICKSORT(R,s1,i-1); QUICKSORT(R,i+1,t1); void main() rectype Rsize; int i; printf("請輸入使用插入算法排序的10個數據n"); for(i=1;i<size;i+) scanf("%d",&Ri.key); printf("n插入排序之前n"); for(i=1;i<size;i+) printf("%dt",Ri.key); INSERTSORT(R)

26、; printf("n插入排序之后n");for(i=1;i<size;i+) printf("%dt",Ri.key);printf("n請輸入使用希爾頓算法排序的10個數據n");for(i=0;i<size-1;i+) scanf("%d",&Ri.key);printf("n希爾排序之前n");for(i=0;i<size-1;i+) printf("%dt",Ri.key);SHELLSORT(R,10); printf("n希爾排序之后n");for(i=0;i<siz