數(shù)據(jù)結(jié)構(gòu) 查找、排序的應(yīng)用實(shí)驗(yàn)

1、淮海工學(xué)院計(jì)算機(jī)科學(xué)系實(shí)驗(yàn)報(bào)告書課程名：數(shù)據(jù)結(jié)構(gòu)題目：查找、排序的應(yīng)用實(shí)驗(yàn)班 級(jí)：學(xué) 號(hào)：m姓 名：排序、查找的應(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)已合二為一，實(shí)驗(yàn)結(jié)果在機(jī)房現(xiàn)場(chǎng)驗(yàn)收和評(píng)分，希望同學(xué)們認(rèn)真對(duì)待， 并于2009年12月20日按時(shí)提

2、交本次實(shí)驗(yàn)報(bào)告（含電子和紙質(zhì)報(bào)告），任何同學(xué)不得拖延。5）如果驗(yàn)收時(shí)間緊張，不能再正課時(shí)間完成者，由老師擇機(jī)決定另行通知專門驗(yàn)收時(shí)間。 凡無(wú)故不主動(dòng)或拖延驗(yàn)收者，均按照不及格處理。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ì)數(shù)據(jù)序列（查找表）：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ù)

3、和線性探測(cè)再散列的沖突處理方法創(chuàng)建表長(zhǎng)為m=11的哈希表；6）實(shí)現(xiàn)5）創(chuàng)建哈希表上的查找。7）分別簡(jiǎn)單選擇排序、堆排序、鏈?zhǔn)交鶖?shù)排序算法對(duì)數(shù)據(jù)序列進(jìn)行排序，并顯示排序結(jié)果。3實(shí)驗(yàn)步驟與源程序 #include #include #include #define LIST_SIZE 20 #define TRUE 1 #define FALSE 0 #define SUCCESS 1 #define UNSUCCESS -1 #define MAX 100#define RADIX 10 #define KEY_SIZE 6 #define LIST_SIZE 20 typedef char K

4、eyType;typedef int OtherType;typedef int PVectorRADIX;typedef struct KeyType keyKEY_SIZE;int type;int next;RecordType1;typedef structRecordType1 RLIST_SIZE+1;int length;int keynum;SLinkList;typedef structKeyType key;OtherType other_data;RecordType;typedef structRecordType rLIST_SIZE+1;int length;Rec

5、ordList;二叉排序樹的創(chuàng)建與查找#define 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 sizeindex;/hashsizesizeindex為當(dāng)前容量int count;/當(dāng)前

6、數(shù)據(jù)元素個(gè)數(shù)HashTable;/順序查找void SeqSearch(RecordList l, KeyType k)/*在順序表l中順序查找其關(guān)鍵字等于k的元素，若找到，則函數(shù)值為該元素在表中的位置，否則 為0*/int i;l.r0.key=k;i=l.length;while (l.ri.key!=k) i;if (i=1)printf(該元素k所在的位置是:)；printf(%d”,i);elseprintf(該元素不存在);/直接插入排序void InsSort(RecordType r, int length)int i,j;for (i=2; i=length; i+)r0=r

7、i;/*將待插入記錄存放到監(jiān)視哨r0中*/j=i-1;while (r0.key rj.key )/* 尋找插入位置 */rj+1= rj;j=j-1;rj+1=r0;/*將待插入記錄插入到已排序的序列中*/ /* InsSort */簡(jiǎn)單選擇排序void SelectSort(RecordType r,int length)int n,k;int x;n=length;for(int i=1;i=n-1;+i)k=i;for(int j=i+1;j=n;+j)if(rj.keyrk.key)k=j;if(k!=i)x=ri.key ;ri.key =rk.key ;rk.key =x;/*

8、SelectSort */冒泡排序void BubbleSort(RecordType r,int length)int x,i,n,change,j;n=length;change=TRUE;for(i=1;i=n-1&change;+i)change=FALSE;for(j=1;jrj+1.key)x=rj.key;rj=rj+1;rj+1.key=x;change=TRUE;快速排序int Partition(RecordList &L,int low,int high) /Partition() sub-function int pivotkey;L.r0=L.rlow;pivotke

9、y=L.rlow.key;while(lowhigh) while(low=pivotkey)-high;L.rlow=L.rhigh;while(lowhigh&L.rlow.key=pivotkey)+low;L.rhigh=L.rlow;L.rlow=L.r0;return(low);void Qsort(RecordList &L,int low,int high) int pivotloc;if(lowhigh) pivotloc=Partition(L,low,high);Qsort(L,low,pivotloc-1);Qsort(L,pivotloc+1,high);void Q

10、uickSort(RecordList &L) Qsort(L,1,L.length);對(duì)排好的序進(jìn)行折半查找算法void BinSrch(RecordList l,KeyType k)int low,high,mid;low=1;high=l.length;while(low=high)mid=(low+high)/2;if (k=l.rmid.key)printf(找到該元素，其位置為%d”,mid);break;/*找到待查元素*/elseif (khigh) printf(沒(méi)有找到該元素);void InsertBST(BSTree *bst, KeyType key)BSTree s

11、;if (*bst = NULL)/*遞歸結(jié)束條件*/s=(BSTree)malloc(sizeof(BSTNode);/*申請(qǐng)新的結(jié)點(diǎn) s*/ s- key=key;s-lchild=NULL;s-rchild=NULL;*bst=s;elseif (key key)InsertBST(&(*bst)-lchild), key);/*將 s 插入左子樹 */else if (key (*bst)-key)InsertBST(&(*bst)-rchild), key); /*將 s 插入右子樹 */void CreateBST(BSTree *bst)KeyType key;*bst=NULL

12、;scanf(%d”, &key);while (key!=ENDKEY)/*ENDKEY 為自定義常量*/InsertBST(bst, key);scanf(%d”, &key);void PreOrder(BSTree root)if (root!=NULL)printf(%d ”,root-key); /*輸出結(jié)點(diǎn) */PreOrder(root-lchild); /*先序遍歷左子樹*/PreOrder(root-rchild); /*先序遍歷右子樹*/BSTree SearchBST(BSTree bst, KeyType key)if (!bst)return NULL;elseif

13、 (bst-key = key)return bst;/* 查找成功*/elseif (bst-key key)return SearchBST(bst-lchild, key);/*在 左子樹繼續(xù)查找*/ elsereturn SearchBST(bst-rchild, key);/*在 右子樹繼續(xù)查找*/BSTNode * DelBST(BSTree t, KeyType k) BSTNode *p, *f,*s ,*q;p=t;f=NULL;while(p)if(p-key=k ) break;f=p；if(p-keyk)p=p-lchild;elsep=p-rchild;if(p=NU

14、LL) return t;if(p-lchild=NULL)if(f=NULL)t=p-rchild;elseif(f-lchild=p) f-lchild=p-rchild ;else f-rchild=p-rchild ;free(p);elseq=p;s=p-lchild;while(s-rchild)q=s;s=s-rchild;if(q=p) q-lchild=s-lchild ;elseq-rchild=s-lchild;p-key=s-key;free(s);return t; /*DelBST*/建立哈希表int CreatHashTable(HashTable &H,int

15、m)int i,keys,p,len;H.elem = (Elemtype *)malloc(MAX * sizeof(Elemtype);H.sizeindex = MAX;/初 始存儲(chǔ)容量H.count=0;printf(請(qǐng)輸入該組關(guān)鍵字的個(gè)數(shù):)；scanf(%d”,&m);printf(請(qǐng)輸入表長(zhǎng)len:);scanf(%d”,&len);H.sizeindex = len;for(i = 0;i m;+i)H.elemi.flag = 0;printf(請(qǐng)輸入該組關(guān)鍵字：)；for(i = 0;i m;+i)scanf(%d”,&keys);p = keys %m;while(H.e

16、lemp.flag = 1)/處理沖突int d=1;p = (p +d)% m;d+;H.elemp.key = keys;H.elemp.flag = 1;H.count+;for(int j=H.count;jlen;j+)H.elemj.key=0;printf(哈希表創(chuàng)建完畢！ n);printf(下標(biāo)關(guān)鍵字n);for(i = 0;ilen;i+)printf(%d ,i);printf(%d”,H.elemi.key);printf(n)；return SUCCESS;void SearchHashTable(HashTable H)int keys,p;printf(請(qǐng)輸入您要

17、查找的關(guān)鍵字：n);scanf(%d”,&keys);for(int i=0;i-1&pH.count)printf(查找成功！ n);printf(該關(guān)鍵字在哈希表中的下標(biāo)為：d n”,p);elseprintf(查找失敗，表中無(wú)此關(guān)鍵字！ n);/堆排序/篩選void sift(RecordType r,int k,int m)int t;t=rk.key;int x=rk.key;int i=k;int j=2*i;int finished=FALSE;while(j=m&!finished)if(jm&rj.key=rj.key)finished=TRUE;elseri=rj;i=j;

18、j=2*i;/*繼續(xù)篩選*/ri.key=t;/* sift */建堆void crt_heap(RecordType r,int length)int n=length;for(int i=n/2;i=1;-i)sift(r,i,n);/堆排序void HeapSort(RecordType r,int length)crt_heap(r,length);int n=length;int b;for(int i=n;i=2;-i)b=r1.key;r1.key=ri.key;ri.key=b;sift(r,1,i-1);/鏈?zhǔn)交鶖?shù)排序void Distribute (SLinkList *L

19、,int i,PVector head,PVector tail) int j,p;for(j=0;jR0.next;while(p)j=L-Rp.keyi;if(headj=0) headj=p;else L-Rtailj.next=p;tailj=p;p=L-Rp.next;void Collect(SLinkList *L,PVector head,PVector tail)int j=0,t;while(headj=0)+j;L-R0.next=headj;t=tailj;while(jRADIX-1)+j;while(jRt.next=headj;t=tailj;L-Rt.next=

20、0;void RadixSort(SLinkList *L )int n,i,d,j,x,k;printf(輸入鏈表長(zhǎng)度：)；scanf(%d”,&(L-length);printf(輸入最大位數(shù):);scanf(%d”,&(L-keynum);PVector head,tail;n=L-length;for(i=0;iRi.next=i+1;L-Rn.next=0;printf(輸入各記錄:);for(j=1;jlength;j+)scanf(%d”,&(L-Rj.type);for(i=1;ilength;i+)x=L-Ri.type;for(j=0;jkeynum;j+)L-Ri.key

21、j=x%10;x=x/10;d=L-keynum;for(i=0;ikeynum;+i)Distribute(L,i,head,tail);Collect(L,head,tail);k=0;printf(排序后為:);while(L-Rk.next)printf(%d ”,L-RL-Rk.next.type); k=L-Rk.next;void main()SLinkList M; 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告 int i,j,select,a,flag=1,m=0;RecordType r20;BSTree bst,result,T;RecordList L,Q;int length,k,low;pri

22、ntf(1進(jìn)行順序查找t2進(jìn)行直接排序t3進(jìn)行冒泡排序n4進(jìn)行快速排序t5對(duì)排 好序的紀(jì)錄序列表進(jìn)行折半查找n6利用原紀(jì)錄序列建立一顆二叉排序樹，并在其上實(shí)現(xiàn)特定關(guān)鍵 字值結(jié)點(diǎn)的查找n7建立哈希表，并對(duì)其進(jìn)行查找n);printf(8簡(jiǎn)單選擇排序9堆排序 10鏈?zhǔn)交鶖?shù)排序n);printf(0 退出);int symbol(1);while(flag)printf(n 請(qǐng)選擇：)；scanf(%d”,&a);if(a=10)symbol=0;while(symbol)printf(請(qǐng)輸入待排序記錄的長(zhǎng)度:)；/交互創(chuàng)建紀(jì)錄表scanf(%d”,&length);printf(請(qǐng)輸入各元素：)；

23、for(i=1;i=length;i+)fflush(stdin);scanf(%d”,&j);ri.key = j;printf(你輸入的各元素為：)；for(i=1;i=length;i+)printf(%d ”,ri.key);printf(n)；symbol=0;switch(a)case 1:printf(請(qǐng)輸入你要查找的元素k：);fflush(stdin);scanf(%d”,&k);L.length=length;for(i=1;i=L.length;i+)L.ri=ri;SeqSearch(L,k);printf(n)；break;case 2:InsSort(r,lengt

24、h);printf(按直接排序后各元素為：)；for(i=1;i=length;i+)printf(%d ”,ri.key);printf(n);break;case 3:BubbleSort(r,length);printf(按冒泡排序后各元素為：)；for(i=1;i=length;i+)printf(%d ”,ri.key);printf(n)；break;case 4:L.length=length;for(i=1;i=L.length;i+)L.ri=ri;QuickSort(L);printf(進(jìn)行快速排序后各元素為：)；for(i=1;i=L.length;i+)printf(%

25、d ”,L.ri.key);printf(n)；break;case 5:InsSort(r,length);L.length=length;for(i=1;ikey);elseprintf(未找到!n);result = DelBST(T,k);/getch();break;case 7:HashTable H;CreatHashTable(H,m);SearchHashTable(H);break;case 0:flag=0;case 8:SelectSort(r,length);printf(按簡(jiǎn)單選擇排序后各元素為：)；for(i=1;i=length;i+)printf(%d ”,ri.key);printf(n)；break;case 9:crt_heap(r,length);HeapSort(r,length);printf(按簡(jiǎn)單選擇排序后各元素為：)；for(i=1;ient s and Sett ingsQTB桌面Debugh. exe1 4 6 7 8戰(zhàn)請(qǐng)請(qǐng)請(qǐng)1323721B67列并，序 慎紀(jì)希擇 順快原哈選 kJI.仃用立單 S1進(jìn)利建簡(jiǎn)如選費(fèi)1HS-7 .待#- 擇入入 -G- .-=1數(shù) 掌在基 廳辜式 1S1列