查找,排序的應(yīng)用試驗(yàn)

1、!-淮海工學(xué)院計(jì)算機(jī)科學(xué)系實(shí)驗(yàn)報(bào)告書課程名：數(shù)據(jù)結(jié)構(gòu)題目： 查找、排序的應(yīng)用實(shí)驗(yàn)班 級(jí)：軟件081班學(xué) 號(hào)：110831123姓名：XX評(píng)語(yǔ)：成績(jī)： 指導(dǎo)教師： 批閱時(shí)間:排序、查找的應(yīng)用實(shí)驗(yàn)報(bào)告要求1目的與要求：1） 查找、排序是日常數(shù)據(jù)處理過(guò)程中經(jīng)常要進(jìn)行的操作和運(yùn)算，掌握其算法與應(yīng)用對(duì)于提 高學(xué)生數(shù)據(jù)處理能力和綜合應(yīng)用能力顯得十分重要。2）本次實(shí)驗(yàn)前，要求同學(xué)完整理解有關(guān)排序和查找的相關(guān)算法和基本思想以及種算法使用 的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)；3）利用C或C+語(yǔ)言獨(dú)立完成本次實(shí)驗(yàn)內(nèi)容或題目，程序具有良好的交互性（以菜單機(jī)制 實(shí)現(xiàn)實(shí)驗(yàn)程序的交互運(yùn)行）和實(shí)用性；4）本次實(shí)驗(yàn)在機(jī)房現(xiàn)場(chǎng)驗(yàn)收和平分，希望同學(xué)

2、們認(rèn)真對(duì)待，并按時(shí)完成實(shí)驗(yàn)任務(wù)；5） 認(rèn)真書寫實(shí)驗(yàn)報(bào)告（包括程序清單及相關(guān)實(shí)驗(yàn)數(shù)據(jù)與完整運(yùn)行結(jié)果），并按時(shí)提交。2實(shí)驗(yàn)內(nèi)容或題目題目：對(duì)記錄序列（查找表）：55 ,13, 23，72，109，67, 2，78,13分別實(shí)現(xiàn)如下操作：1）順序查找；2）分別使用直接插入排序、冒泡排序、快速排序?qū)υo(jì)錄序列進(jìn)行排序；3）對(duì)排好序的紀(jì)錄序列表進(jìn)行折半查找；4）利用原紀(jì)錄序列建立一顆二叉排序樹，并在其上實(shí)現(xiàn)特定關(guān)鍵字值結(jié)點(diǎn)的查找；5）按照“除留余數(shù)法”哈希構(gòu)造函數(shù)和線性探測(cè)再散列的沖突處理方法創(chuàng)建表長(zhǎng)為m=11的哈希表;6）實(shí)現(xiàn)5）創(chuàng)建哈希表上的查找。3實(shí)驗(yàn)步驟與源程序#in elude <std

3、io.h>#in elude <stdlib.h>#in elude<malloe.h>#defi ne LIST_SIZE 20#defi ne TRUE 1#defi ne FALSE 0#defi ne SUCCESS 1#defi ne UNSUCCESS -1#defi ne MAX 100typedef char KeyType;typedef int OtherType;typedef structKeyType key;OtherType other_data;RecordType;typedef structReeordType rLIST_SI

4、ZE+1; /* r0為工作單元 */int len gth;RecordList;/二叉排序樹的創(chuàng)建與查找#defi ne ENDKEY 0typedef struct nodeKeyType key ; /*關(guān)鍵字的值*/struct node *lchild,*rchild;/*左右指針 */BSTNode, *BSTree;/*哈希表的創(chuàng)建*/typedef structint key;int flag;/falg=1時(shí)表示有關(guān)鍵字，=0時(shí)表示沒(méi)有關(guān)鍵字Elemtype;typedef structElemtype *elem;/動(dòng)態(tài)分配的哈希表的首地址int size in dex;

5、/hashsizesize in dex為當(dāng)前容量int cou nt;當(dāng)前數(shù)據(jù)元素個(gè)數(shù)HashTable;/*順序查找*/void SeqSearch(RecordList l, KeyType k)/*在順序表I中順序查找其關(guān)鍵字等于k的元素，若找到，則函數(shù)值為該元素在表中的位置，否則為0*/int i;l.r0.key=k;i=l.le ngth;while (l.ri.key!=k) i-;if (i>=1)printf(" 該元素k所在的位置是：”)；prin tf("%d",i);elseprintf(" 該元素不存在");/

6、直接插入排序void In sSort(RecordType r, in t le ngth)/*對(duì)記錄數(shù)組r做直接插入排序，length為數(shù)組中待排序記錄的數(shù)目*/int i,j;for (i=2; i<=le ngth; i+)rO=ri;/*將待插入記錄存放到監(jiān)視哨 r0中*/j=i-1；while (rO.key< rj.key )/*尋找插入位置 */rj+1= rj;j=j-1；rj+1=r0;/* 將待插入記錄插入到已排序的序列中 */* In sSort */*冒泡排序*/void BubbleSort(RecordType r,int length)/*對(duì)記錄數(shù)組

7、r做冒泡排序，length為數(shù)組的長(zhǎng)度*/int x,i, n, cha nge,j;n=len gth;cha nge=TRUE;for(i=1;i<=n-1&&cha nge;+i)cha nge=FALSE;for(j=1;j<=n-i;+j)if(rj.key>rj+1.key)x=rj.key;rj=rj+1;rj+1.key=x;cha nge=TRUE;/快速排序int Partiti on( RecordList &L,i nt low,i nt high)/Partitio n() sub-fu nction int pivotkey

8、;L.r0=L.rlow;pivotkey=L.rlow.key;while(low<high) while(low<high&&L.rhigh.key>=pivotkey)-high;L.rlow=L.rhigh;while(low<high &&L.rlow.key<=pivotkey)+low;L.rhigh=L.rlow;L.rlow=L.r0;return(low); /Partiti on() end/Qsort() sub-fu nctionvoid Qsort(RecordList &L,int low,in

9、t high) int pivotloc;if(low<high) pivotloc=Partiti on( L,low,high);Qsort(L,low,pivotloc-1);Qsort(L,pivotloc+1,high);void QuickSort(RecordList &L) Qsort(L,1 ,L .le ngth);/Quicksort。sub-fu nction/call Qsort()/*對(duì)排好的序進(jìn)行折半查找算法*/void Bi nSrch(RecordList l,KeyType k)/*在有序表I中折半查找其關(guān)鍵字等于k的元素，若找到，則函數(shù)值為該

10、元素在表中的位置*/int low,high,mid;low=1;high=l.length;/* 置區(qū)間初值 */while(low<=high)mid=(low+high)/2;if (k=l.rmid.key)prin tf("找到該元素，其位置為%d",mid);break;/*找到待查元素*/elseif (k<l.rmid. key)high=mid-1;/*未找到，則繼續(xù)在前半?yún)^(qū)間進(jìn)行查找*/elselow=mid+1;/*繼續(xù)在后半?yún)^(qū)間進(jìn)行查找*/沒(méi)有找到該元素");if(low>high) pri ntf(" void

11、 In sertBST(BSTree *bst, KeyType key)/*若在二叉排序樹中不存在關(guān)鍵字等于key的元素，插入該元素*/BSTree s;if (*bst = NULL)/*遞歸結(jié)束條件*/s=(BSTree)malloc(sizeof(BSTNode);/* s-> key=key;s->lchild=NULL;s->rchild=NULL;*bst=s;申請(qǐng)新的結(jié)點(diǎn)s*/ elseif (key < (*bst)->key)InsertBST(&(*bst)->lchild), key);/*else將s插入左子樹*/if (k

12、ey > (*bst)->key)In sertBST(&(*bst)->rchild), key); /*void CreateBST(BSTree *bst)/*從鍵盤輸入元素的值，創(chuàng)建相應(yīng)的二叉排序樹*/將s插入右子樹*/KeyType key;*bst=NULL;scan f("%d", & key);while (key!=ENDKEY) /*ENDKEY為自定義常量 */In sertBST(bst, key); scan f("%d", & key);void PreOrder(BSTree roo

13、t)/*先序遍歷二叉樹，root為指向二叉樹根結(jié)點(diǎn)的指針*/if (root!=NULL)prin tf("%d ",root->key); /*PreOrder(root->lchild); /*PreOrder(root->rchild); /*輸出結(jié)點(diǎn)*/先序遍歷左子樹*/先序遍歷右子樹*/BSTree SearchBST(BSTree bst, KeyType key)/*在根指針bst所指二叉排序樹中，遞歸查找某關(guān)鍵字等于 元素結(jié)點(diǎn)指針，否則返回空指針*/key的元素，若查找成功，返回指向該if (!bst)return NULL;elseif

14、(bst->key = key)return bst;/* 查找成功 */elseif (bst->key > key)return SearchBST(bst->lchild, key);/* elsereturn SearchBST(bst->rchild, key);/*在左子樹繼續(xù)查找*/在右子樹繼續(xù)查找*/BSTNode * DelBST(BSTree t, KeyType k) /*BSTNode *p, *f,*s ,*q;p=t； f=NULL;while(p) /*查找關(guān)鍵字為k的待刪結(jié)點(diǎn)p*/在二叉排序樹t中刪去關(guān)鍵字為k的結(jié)點(diǎn)*/if(p-&

15、gt;key=k ) break; /*找到則跳出循環(huán)*/f=p; /*f 指向p結(jié)點(diǎn)的雙親結(jié)點(diǎn)*/if(p->key>k) p=p->lchild;elsep=p->rchild; if(p=NULL) return t; /* if(p->lchild=NULL) /*pif(f=NULL) t=p->rchild; /*p else若找不到，返回原來(lái)的二叉排序樹*/無(wú)左子樹*/是原二叉排序樹的根*/if(f->lchild=p) /*p是f的左孩子*/f->lchild=p->rchild ; /*else /*p 是f的右孩子*/f

16、->rchild=p->rchild ; /*free(p); /* 釋放被刪除的結(jié)點(diǎn)將p的右子樹鏈到f的左鏈上*/將p的右子樹鏈到f的右鏈上*/p*/else /*p有左子樹*/q=p;s=p->lchild;while(s->rchild) /* 在p的左子樹中查找最右下結(jié)點(diǎn)*/q=s;s=s->rchild;if(q=p)q->lchild=s->lchild ; /*將 s 的左子樹鏈到 q 上 */elseq->rchild=s->lchild;p->key=s->key; /* 將 s 的值賦給 p*/ free(s

17、);return t; /*DelBST*/ /*建立哈希表*/int CreatHashTable(HashTable & H,i nt m)int i,keys,p,le n;H.elem = (Elemtype *)malloc(MAX * sizeof(Elemtype);H.sizei ndex = MAX;/初始存儲(chǔ)容量H.co un t=0;printf("請(qǐng)輸入該組關(guān)鍵字的個(gè)數(shù)：”)；sca nf("%d",&m);printf(”請(qǐng)輸入表長(zhǎng)len:");scan f("%d",&len);H.

18、size in dex = len;for(i = 0;i < m;+i)H.elemi.flag = 0;prin tf("請(qǐng)輸入該組關(guān)鍵字：");for(i = 0;i < m;+i)scan f("%d",&keys);p = keys %m;while(H.elemp.flag = 1)/處理沖突int d=1;p = (p +d)% m; d+;H.elemp.key = keys;H.elemp.flag = 1;H.co un t+;for(i nt j=H.co un t;j<le n;j+)H.elemj.ke

19、y=0;printf(”哈希表創(chuàng)建完畢！n");printf(" 下標(biāo)關(guān)鍵字n");for(i = 0;i<le n;i+)prin tf("%d",i);prin tf("%d",H.elemi.key);prin tf("n");return SUCCESS;void SearchHashTable(HashTable H)int keys,p;printf(”請(qǐng)輸入您要查找的關(guān)鍵字：n");sca nf("%d",&keys);for(i nt i=0;i

20、<H.co un t;i+)if( keys = H.elemi.key)/p是找到的關(guān)鍵字的下標(biāo)p=i;if(p>-1 &&p<H.cou nt)printf("查找成功！n");printf(”該關(guān)鍵字在哈希表中的下標(biāo)為：%d n ”,p); elseprintf(”查找失敗，表中無(wú)此關(guān)鍵字！n");void mai n()int i,j,select,a,flag=1,m=0;printf("1記錄序列n2進(jìn)行順序查找n3 進(jìn)行直接排序n4進(jìn)行冒泡排序n5進(jìn)行快速排序n6對(duì)排好序的紀(jì)錄序列表進(jìn)行折半查找n7利用原紀(jì)

21、錄序列建立一顆二叉排序樹，并在其上實(shí)現(xiàn)特定關(guān)鍵字值結(jié)點(diǎn)的查找n8建立哈希表，并對(duì)其進(jìn)行查找n9退出n");RecordType r20;BSTree bst,result,T;RecordList L,Q;int len gth,k,low;while(flag)prin tf("請(qǐng)選擇：");scan f("%d",&a);switch(a)case 1:prin tf("請(qǐng)輸入待排序記錄的長(zhǎng)度：”)；/交互創(chuàng)建紀(jì)錄表scan f("%d",&len gth);for(i=1;i<=le n

22、gth;i+)printf(”請(qǐng)輸入第d個(gè)記錄元素:",i);fflush(stdi n);scan f("%d",&j); ri.key = j;printf(”你輸入的各元素為：”)；for(i=1;i<=le ngth;i+)prin tf("%d ”,ri.key);prin tf("n");break; case 2:printf(”請(qǐng)輸入你要查找的元素k:");fflush(stdi n);scan f("%d",&k);L.len gth=le ngth;for(i=1

23、;i<=Len gth;i+) L.ri=ri;SeqSearch(L,k);prin tf("n");break;case 3:In sSort(r,le ngth);printf(”按直接排序后各元素為：”)；for(i=1;i<=le ngth;i+)prin tf("%d ",ri.key);prin tf("n");break; case 4:BubbleSort(r,le ngth);printf(”按冒泡排序后各元素為：”)；for(i=1;i<=le ngth;i+)prin tf("%d

24、",ri.key);prin tf("n"); break;case 5:L.len gth=le ngth;for(i=1;i<=Len gth;i+) L.ri=ri;QuickSort(L); printf(”進(jìn)行快速排序后各元素為：”);for(i=1;i<=Len gth;i+)prin tf("%d ",L.ri.key);prin tf("n");break;case 6:In sSort(r,le ngth);L.len gth=le ngth;for(i=1;i<=Len gth;i+)L

25、.ri=ri;printf(”請(qǐng)輸入要查找的元素：”)；sea nf("%d",&k);Bi nSrch(L,k);prin tf("n");break;case 7: int k;printf(”建立二叉排序樹，請(qǐng)輸入序列(以 0結(jié)束):n");CreateBST (& T);printf(”先序遍歷輸出序列為:");PreOrder(T);prin tf("n請(qǐng)輸入要查找的元素：”)；fflush(stdi n);scan f("%d",&k);result = SearchB

26、ST(T,k);if (result != NULL)printf("存在要查找的元素為 dn",result->key);elseprintf("未找到!n");result = DelBST(T,k);/ getch();break;case 8:HashTable H;CreatHashTable(H,m);SearchHashTable(H);break;case 9:flag=0;4測(cè)試數(shù)據(jù)與實(shí)驗(yàn)結(jié)果（可以抓圖粘貼）先記錄序列，再進(jìn)行順序查找，之后分別進(jìn)行直接排序、冒泡排序、快速排序，如圖:237210?131329 碩131323551313236727613?2：781096?727816955677278109C- 11F:11EX1_ 131為兀元元兀己己己己己己己己一在-A1US 丄 2345'召7-8-3-5 3 3 2 7 8 3