查找和排序算法的實現(xiàn)(實驗七)

1、!-實驗七查找和排序算法的實現(xiàn)一. 實驗?zāi)康募耙髮W(xué)生在實驗中體會各種查找和內(nèi)部排序算法的基本思想、適用場合，理解開發(fā) 高效算法的可能性和尋找、構(gòu)造高效算法的方法。掌握運用查找和排序解決一些實際應(yīng)用問題。二. 實驗內(nèi)容:，并計編程實現(xiàn)一種查找算法（如折半查找、二叉排序樹的查找、哈希查找等） 算相應(yīng)的ASL。編程實現(xiàn)一種內(nèi)部排序算法（如插入排序、快速排序等）三. 實驗主要流程、基本操作或核心代碼、算法片段（該部分如不夠填寫，請另加附頁），并計（1） 編程實現(xiàn)一種查找算法（如折半查找、二叉排序樹的查找、哈希查找等）算相應(yīng)的ASL。程序代碼:折半查找:頭文件:#defi ne EQ(a,b) (a)

2、=(b) #defi ne LT(a,b) (a)<(b)#defi ne maxle ngth 20 typ edef int ElemT ype;typ edef structElemT ype key;ElemT ype other;card;/每條記錄包含的數(shù)據(jù)項 typ edef structcard rmaxle ngth; int len gth;SSTable;/ 一張表中包含的記錄容量void Create(SSTable & L); int Search(SSTable L,i nt elem);功能函數(shù):#i nclude"1.h"#i

3、nclude"stdio.h" void Create(SSTable &L)printf("新的線性表已經(jīng)創(chuàng)建，請確定元素個數(shù)(不超過20) n");scan f("%d",&L.le ngth);n");printf("請按遞增序列輸入具體的相應(yīng)個數(shù)的整數(shù)元素(空格隔開)for(i nt i=0;i<Len gth;i+)scan f("%d",&L.ri.key); int Search(SSTable L,i nt elem)if(L.rL.le ngth-

4、1.keyvelem|L.r0.key>elem)printf(”表中沒有該元素(不在范圍內(nèi))n");return 0;int low=0,high=L .len gth-1;int mid;while(low<=high)mid=(low+high)/2;if(EQ(L.rmid.key,elem)printf("該元素在第 %d 位n",mid+1); return 0;else if(LT(elem,L.rmid.key)high=mid-1;elselow=mid+1;printf("表中沒有該元素(不在范圍內(nèi))n");re

5、turn 0;主函數(shù):#i nclude"stdio.h"#i nclude"1.h" int mai n()SSTable L;Create(L);prin tf("n");printf("此時的線性表元素：n");for(i nt a=0;a<L.le ngth;a+)prin tf("%d "丄.ra.key);prin tf("n");prin tf("n");int elem;doprintf("請輸入要查找的元素(輸入000表示

6、結(jié)束程序)n"); sea nf("%d", &elem);if(elem!=000)Seareh(L,elem);while(elem!=000);return 0;?運行結(jié)果：新的線性表已經(jīng)創(chuàng)建，請確定元素個數(shù)（不超過遲町16請按遞増序列輸入具體的相應(yīng)個數(shù)的S數(shù)元素（空格隔開）-2 1 a 6 10 11 14 23 44 99此時的線性耒元素：-2 1 3 6 10 11 14 23 44 99請輸入要查找的元素（輸入甌回表示結(jié)束程序（2）編程實現(xiàn)一種內(nèi)部排序算法（如插入排序、快速排序 等）。程序代碼部分：直接插入排序頭文件:#defi ne max

7、le ngth 20/最大數(shù)據(jù)容量#defi ne OK 1 typ edef int Status; typ edef int Other;typ edef int KeyT ype;typ edef structKeyT ype key;Other data;Red;typ edef structRed rmaxle ngth+1;/加了個哨兵的位置 intlen gth;/當(dāng)前數(shù)據(jù)個數(shù)SqList;Status In it(SqList & L);Status In sertsort(SqList &L);功能函數(shù)：#i nclude"stdio.h"

8、#i nclude"1.h"Status In it(SqList &L)printf("新的線性表以創(chuàng)建，請確定元素個數(shù)(不超過20) n");sca nf("%d",&L.le ngth);printf("請輸入具體的相應(yīng)個數(shù)的整數(shù)元素(空格隔開)n");for(int i=1/*將哨兵的位置【0】空出來*/;i<L.length+1;i+) scan f("%d",&L.ri.key);return OK;Status In sertsort(SqList &

9、amp;L)for(i nt i=2;i<L.le ngth+1;i+)L.r0=L.ri;/交換的應(yīng)該是該位置記錄的完整數(shù)據(jù)項，而不僅僅是數(shù)據(jù)項 中的一個keyfor(i nt j=i;j>0&&L.r0.key<L.rj-1.key/*這里是依據(jù)記錄中的數(shù)據(jù)項 key 來排序的，所以比較的是key，而不是一條記錄的所有數(shù)據(jù)項*/;j-)L.rj=L.rj-1;L.rj=L.r0;return OK; 主函數(shù)：#i nclude"stdio.h"#i nclude"1.h" int main()SqList L;In

10、it(L);prin tf("n");printf("排序前的線性表元素：n"); for(i nt a=1;a<L.le ngth+1;a+)prin tf("%d "丄.ra.key);prin tf("n");prin tf("n");In sertsort(L);printf("排序后的線性表元素：n"); for(i nt b=1;b<L.le ngth+1;b+)prin tf("%d ",L.rb.key);prin tf(&qu

11、ot;n");return 0;快速排序頭文件:#defi ne maxle ngth 20/最大數(shù)據(jù)容量#defi ne OK 1 typ edef int Status; typ edef int Other;typ edef int KeyT ype;typ edef structKeyT ype key;Other data;Red;typ edef structRed rmaxle ngth+1;/加了個哨兵的位置 intlen gth;/當(dāng)前數(shù)據(jù)個數(shù)SqList;void In it(SqList & L);Status P artitio n(SqList &a

12、mp; L,i nt low,i nt high); void QSort(SqList & L,i nt low,i nt high);功能函數(shù)：#i nclude"stdio.h"#i nclude"1.h" void In it(SqList &L)printf("新的線性表以創(chuàng)建，請確定元素個數(shù)(不超過 20) n");sca nf("%d",&L.le ngth);printf("請輸入具體的相應(yīng)個數(shù)的整數(shù)元素(空格隔開) n");for(int i=1/*將存

13、放樞軸中關(guān)鍵字所在記錄完整信息的位置【0】空出來*/;i<L.le ngth+1;i+)scan f("%d",&L.ri.key);Status P artitio n(SqList & L,i nt low,i nt high)int piv otkey;pivotkey=L.rlow.key;/用第一條記錄的關(guān)鍵字作樞軸L.r0=L.rlow;/存放作為樞軸的關(guān)鍵字所在記錄的完整信息 while(low<high)while(low<high&&L.rhigh.key>=pivotkey)high-;/從右端往左

14、L.rlow=L.rhigh;while(low<high&&L.rlow.key<=pivotkey)low+;/從左端往右L.rhigh=L.rlow;L.rlow=L.r0; return low; void QSort(SqList & L,i nt low,i nt high) int piv otioc;if(low<high)p ivotloc =P artitio n( L,low,high); QSort(L,low, pi votloc-1);QSort(L, pivotloc+1,high);主函數(shù)：#i nclude"

15、stdio.h"#i nclude"1.h" int main()SqList L;In it(L);prin tf("n");printf("排序前的線性表元素：n");for(i nt a=1;a<L.le ngth+1;a+)prin tf("%d ",L.ra.key);prin tf("n");prin tf("n");printf("請輸入無序子列的開始和結(jié)束位置(有序子列不用管)n");int low,high;sca nf(

16、"%d %d",&low,&high);QSort(L,low,high);printf("排序后的線性表元素：n");for(i nt b=1;b<L.le ngth+1;b+)prin tf("%d ",L.rb.key);prin tf("n");return 0;運行結(jié)果:新的線性表以創(chuàng)建，請確定元素個數(shù)不起過20）19請輸入具體的相應(yīng)個數(shù)的整數(shù)元素（空格隔開）3 0 -1 2 6 33 12 6 -2 4排序前的線性表元素=3 0 -1 Z 6 33 12 6 -2 4排序后的線性表元素：-2 -1 0 2 3 4 & t 12 33 Piess Any key to c ont inite新的銭性表以創(chuàng)建，請確定元重個數(shù)（不超過2013請輸人具體的相應(yīng)個數(shù)的整數(shù)元素空格隔開）1 -1 2 5 0 88 34 6