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

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

2、EQ(a,b)(a)=(b)#defineLT(a,b)(a)<(b)#definemaxlength20typedefintElemType;typedefstructElemTypekey;ElemTypeother;card;/每條記錄包含的數(shù)據(jù)項typedefstructcardrmaxlength;intlength;SSTable;/一張表中包含的記錄容量voidCreate(SSTable&L);intSearch(SSTableL,intelem);功能函數(shù)：#include"1.h"#include"stdio.h"voi

3、dCreate(SSTable&L)(printf("新的線性表已經(jīng)創(chuàng)建，請確定元素個數(shù)(不超過20)n");scanf("%d”,&L.length);printf("請按遞增序列輸入具體的相應(yīng)個數(shù)的整數(shù)元素(空格隔開)n");for(inti=0;i<L.length;i+)(scanf("%d”,&L.ri.key);intSearch(SSTableL,intelem)(if(L.rL.length-1.key<elem|L.r0.key>elem)(printf("表中沒有

4、該元素(不在范圍內(nèi))n");return0;intlow=0,high=L.length-1;intmid;while(low<=high)(mid=(low+high)/2;if(EQ(L.rmid.key,elem)printf("該元素在第%d位n",mid+1);return0;elseif(LT(elem,L.rmid.key)high=mid-1;elselow=mid+1;printf("表中沒有該元素(不在范圍內(nèi))n");return0;主函數(shù)：#include"stdio.h"#include&quo

5、t;1.h"intmain()SSTableL;Create(L);printf("n");printf("此時的線性表元素：n");for(inta=0;a<L.length;a+)(printf("%d",L.ra.key);printf("n");printf("n");intelem;do(printf("請輸入要查找的元素(輸入000表示結(jié)束程序)n");scanf("%d”,&elem);if(elem!=000)(Search(

6、L,elem);while(elem!=000);return0;運行結(jié)果：(2)編程實現(xiàn)一種內(nèi)部排序算法(如插入排序、快速排序等)。程序代碼部分：直接插入排序頭文件：#definemaxlength20/服大數(shù)據(jù)容量#defineOK1typedefintStatus;typedefintOther;typedefintKeyType;typedefstructKeyTypekey;Otherdata;Red;typedefstructRedrmaxlength+1;力口了個哨兵的位置intlength;/當(dāng)前數(shù)據(jù)個數(shù)SqList;StatusInit(SqList&L);Statu

7、sInsertsort(SqList&L);功能函數(shù)：#include"stdio.h"#include"1.h"StatusInit(SqList&L)printf("新的線性表以創(chuàng)建，請確定元素個數(shù)(不超過20)n");scanf("%d",&L.length);printf("請輸入具體的相應(yīng)個數(shù)的整數(shù)元素(空格隔開)n");for(inti=1/*將哨兵的位置【0】空出來*/;i<L.length+1;i+)scanf("%d",&

8、;L.ri.key);returnOK;StatusInsertsort(SqList&L)for(inti=2;i<L.length+1;i+)L.r0=L.ri;/交換的應(yīng)該是該位置記錄的完整數(shù)據(jù)項，而不僅僅是數(shù)據(jù)項中的一個keyfor(intj=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;returnOK;)主函數(shù)：#include"stdio.h"#include"

9、;1.h"intmain()(SqListL;Init(L);printf("n");printf("排序前的線性表元素：n");for(inta=1;a<L.length+1;a+)(printf("%d",L.ra.key);)printf("n");printf("n");Insertsort(L);printf("排序后的線性表元素：n");for(intb=1;b<L.length+1;b+)(printf("%d",L.r

10、b.key);)printf("n");return0;)快速排序頭文件：#definemaxlength20/服大數(shù)據(jù)容量#defineOK1typedefintStatus;typedefintOther;typedefintKeyType;typedefstructKeyTypekey;Otherdata;Red;typedefstructRedrmaxlength+1;力口了個哨兵的位置intlength;/當(dāng)前數(shù)據(jù)個數(shù)SqList;voidInit(SqList&L);StatusPartition(SqList&L,intlow,inthigh)

11、;voidQSort(SqList&L,intlow,inthigh);功能函數(shù)：#include"stdio.h"#include"1.h"voidInit(SqList&L)printf("新的線性表以創(chuàng)建，請確定元素個數(shù)(不超過20)n");scanf("%d",&L.length);printf("請輸入具體的相應(yīng)個數(shù)的整數(shù)元素(空格隔開)n");for(inti=1/*將存放樞軸中關(guān)鍵字所在記錄完整信息的位置【0】空出來*/;i<L.length+1;i+

12、)scanf("%d",&L.ri.key);StatusPartition(SqList&L,intlow,inthigh)intpivotkey;pivotkey=L.rlow.key;/用第一條記錄的關(guān)鍵字作樞軸L.r0=L.rlow;/存放作為樞軸的關(guān)鍵字所在記錄的完整信息while(low<high)while(low<high&&L.rhigh.key>=pivotkey)high-;/從右端往左L.rlow=L.rhigh;while(low<high&&L.rlow.key<=pi

13、votkey)low+;/從左端往右L.rhigh=L.rlow;)L.rlow=L.r0;returnlow;)voidQSort(SqList&L,intlow,inthigh)(intpivotloc;if(low<high)(pivotloc=Partition(L,low,high);QSort(L,low,pivotloc-1);QSort(L,pivotloc+1,high);)主函數(shù)：#include"stdio.h"#include"1.h"intmain()(SqListL;Init(L);printf("n&

14、quot;);printf("排序前的線性表元素：n");for(inta=1;a<L.length+1;a+)(printf("%d",L.ra.key);)printf("n");printf("n");printf("請輸入無序子列的開始和結(jié)束位置(有序子列不用管)n");intlow,high;scanf("%d%d",&low,&high);QSort(L,low,high);printf("排序后的線性表元素：n");for(intb=1;b<L.length+1;b+)(printf("%d",L.rb.key);)printf("n");return0;運行結(jié)果:斷的線性表以創(chuàng)建，請確定元素個數(shù)（不超過2青輸入具體的相應(yīng)個數(shù)的整數(shù)元素（空格隔開）30-12t33126-24排序前的線性表元素.30-12633126-24排序后的線性表元素；-2-10234661233Pressanj/keytocontinue新的線性表以創(chuàng)建，請確定元素個數(shù)（不超過2m1Q請輸入具體的相應(yīng)個數(shù)的整數(shù)元素（空格隔開）1