查找和排序?qū)嶒?yàn)報(bào)告

查找和排序1．需求分析1．編寫一個(gè)程序輸出在順序表{3，6，2，10，1，8，5，7，4，9}中采用順序方法查找關(guān)鍵字5的過程；2．編寫一個(gè)程序輸出在順序表{1，2，3，4，5，6，7，8，9，10}中采用順序方法查找關(guān)鍵字9的過程；3．編寫一個(gè)程序?qū)崿F(xiàn)直接插入排序算法，并輸出{9，8，7，6，5，4，3，2，1，0}的排序過程；4．編寫一個(gè)程序?qū)崿F(xiàn)快速排序算法，并輸出{6，8，7，9，0，1，3，2，4，5}的排序過程2．系統(tǒng)設(shè)計(jì)1． 靜態(tài)查找表的抽象數(shù)據(jù)類型定義：ADTStaticSearchTable{數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。各個(gè)數(shù)據(jù)元素均含有類型相同，可惟一標(biāo)識(shí)數(shù)據(jù)元素的關(guān)鍵字?jǐn)?shù)據(jù)關(guān)系R：數(shù)據(jù)元素同屬一個(gè)集合基本操作P：Create(&ST,n)操作結(jié)果：構(gòu)造一個(gè)含n個(gè)數(shù)據(jù)元素的靜態(tài)查找表STDestroy(&ST)初始條件：靜態(tài)查找表ST存在操作結(jié)果：銷毀表STSearch(ST,key)初始條件：靜態(tài)查找表ST存在，key為和關(guān)鍵字類型相同的給定值操作結(jié)果：若ST中存在其關(guān)鍵字等于key的數(shù)據(jù)元素，則函數(shù)值為該元素的值或在表中的位置，否則為“空”Traverse(ST,Visit())初始條件：靜態(tài)查找表ST存在，Visit是對(duì)元素操作的應(yīng)用函數(shù)操作結(jié)果：按某種次序?qū)T的每個(gè)元素調(diào)用函數(shù)Visit()一次且僅一次。一旦Visit()失敗，則操作失敗}ADTStaticSearchTable3．調(diào)試分析（1）要在適當(dāng)?shù)奈恢谜{(diào)用Print函數(shù)，以正確顯示排序過程中順序表的變化（2）算法的時(shí)間復(fù)雜度分析：順序查找：T(n)=O(n)折半查找：T(n)=O(logn)直接插入排序：T(n)=O(n2)快速排序：T(n)=O(nlogn)4．測(cè)試結(jié)果用需求分析中的測(cè)試數(shù)據(jù)順序查找：順序表3，6，2，10，1，8，5，7，4，9，查找5折半查找：順序表1，2，3，4，5，6，7，8，9，10，查找9直接插入排序：順序表9，8，7，6，5，4，3，2，1，0，從小到大排序快速排序：順序表6，8，7，9，0，1，3，2，4，5，從小到大排序5．用戶手冊(cè)（1）輸入表長(zhǎng)；（2）依次輸入建立順序表；（3）查找：輸入要查找的關(guān)鍵字（4）回車輸出，查找為下標(biāo)的移動(dòng)過程；排序?yàn)轫樞虮淼淖兓^程6．附錄源程序：（1）順序查找#include<stdio.h>#include<stdlib.h>#defineST_INIT_SIZE200#defineEQ(a,b)((a)==(b))#defineOVERFLOW-2typedefintKeyType;typedefstruct{KeyTypekey;}ElemType;typedefstruct{ElemType*elem;//數(shù)據(jù)元素存儲(chǔ)空間基址,建表時(shí)按實(shí)際長(zhǎng)度分配,0號(hào)單元留空intlength;//表長(zhǎng)度}SSTable;voidInitST(SSTable&ST){ST.elem=(ElemType*)malloc(ST_INIT_SIZE*sizeof(ElemType));if(!ST.elem)exit(OVERFLOW);ST.length=0;}voidCreateST(SSTable&ST){inti;printf("輸入表長(zhǎng):");scanf("%d",&ST.length);for(i=1;i<=ST.length;i++)scanf("%d",&ST.elem[i].key);}voidPrintST(SSTableST){inti;for(i=1;i<=ST.length;i++)printf("%2d",ST.elem[i].key);printf("\n");}intSearch_Seq(SSTableST,KeyTypekey){//在順序表ST中順序查找其關(guān)鍵字等于key的數(shù)據(jù)元素//若找到則函數(shù)值為該元素在表中的位置,否則為0inti;ST.elem[0].key=key;printf("下標(biāo):");for(i=ST.length;!EQ(ST.elem[i].key,key);--i)printf("%d→",i);//從后往前找returni;}voidmain(){SSTableST;KeyTypekey;InitST(ST);CreateST(ST);printf("順序查找表:");PrintST(ST);printf("輸入要查找的關(guān)鍵字:");scanf("%d",&key);intfound=Search_Seq(ST,key);if(found)printf("找到,為第%d個(gè)數(shù)據(jù)\n",found);elseprintf("沒有找到!\n");}（2）折半查找#include<stdio.h>#include<stdlib.h>#defineST_INIT_SIZE200#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineOVERFLOW-2typedefintKeyType;typedefstruct{KeyTypekey;}ElemType;typedefstruct{ElemType*elem;//數(shù)據(jù)元素存儲(chǔ)空間基址,建表時(shí)按實(shí)際長(zhǎng)度分配,0號(hào)單元留空intlength;//表長(zhǎng)度}SSTable;voidInitST(SSTable&ST){ST.elem=(ElemType*)malloc(ST_INIT_SIZE*sizeof(ElemType));if(!ST.elem)exit(OVERFLOW);ST.length=0;}voidCreateST(SSTable&ST){inti;printf("輸入表長(zhǎng):");scanf("%d",&ST.length);for(i=1;i<=ST.length;i++)scanf("%d",&ST.elem[i].key);}voidPrintST(SSTableST){inti;for(i=1;i<=ST.length;i++)printf("%2d",ST.elem[i].key);printf("\n");}intSearch_Bin(SSTableST,KeyTypekey){//在有序表ST中折半查找其關(guān)鍵字等于key的數(shù)據(jù)元素//若找到,則函數(shù)值為該元素在表中的位置,否則為0intlow,high,mid;low=1;high=ST.length;//置區(qū)間初值printf("下標(biāo):");while(low<=high){mid=(low+high)/2;printf("%d→",mid);if(EQ(key,ST.elem[mid].key))returnmid;//找到待查元素elseif(LT(key,ST.elem[mid].key))high=mid-1;//繼續(xù)在前半?yún)^(qū)間進(jìn)行查找elselow=mid+1;}return0;//順序表中不存在待查元素}voidmain(){SSTableST;KeyTypekey;InitST(ST);CreateST(ST);printf("順序查找表:");PrintST(ST);printf("輸入要查找的關(guān)鍵字:");scanf("%d",&key);intfound=Search_Bin(ST,key);if(found)printf("找到,為第%d個(gè)數(shù)據(jù)\n",found);elseprintf("沒有找到!\n");}（3）直接插入排序#include<stdio.h>#defineMAXSIZE20#defineLT(a,b)((a)<(b))typedefintKeyType;typedefstruct{KeyTypekey;}RedType;//記錄類型typedefstruct{RedTyper[MAXSIZE+1];//r[0]閑置或用作哨兵單元intlength;//順序表長(zhǎng)度}SqList;//順序表類型voidCreateSq(SqList&L){inti;printf("輸入表長(zhǎng):");scanf("%d",&L.length);for(i=1;i<=L.length;i++)scanf("%d",&L.r[i].key);}voidPrintSq(SqListL){inti;for(i=1;i<=L.length;i++)printf("%2d",L.r[i].key);printf("\n");}voidInsertSort(SqList&L){//對(duì)順序表L作直接插入排序inti,j;printf("排序過程:\n");for(i=2;i<=L.length;++i){if(LT(L.r[i].key,L.r[i-1].key)){//"<",需將L.r[i]插入有序子表L.r[0]=L.r[i];//復(fù)制為哨兵L.r[i]=L.r[i-1];for(j=i-2;LT(L.r[0].key,L.r[j].key);--j)L.r[j+1]=L.r[j];//記錄后移L.r[j+1]=L.r[0];//插入到正確位置}PrintSq(L);}}//InsertSortvoidmain(){SqListL;CreateSq(L);printf("原始順序表:");PrintSq(L);InsertSort(L);printf("排序后的順序表:");PrintSq(L);}（4）快速排序#include<stdio.h>#defineMAXSIZE20typedefintKeyType;typedefstruct{KeyTypekey;}RedType;//記錄類型typedefstruct{RedTyper[MAXSIZE+1];//r[0]閑置或用作哨兵單元intlength;//順序表長(zhǎng)度}SqList;//順序表類型voidCreateSq(SqList&L){inti;printf("輸入表長(zhǎng):");scanf("%d",&L.length);for(i=1;i<=L.length;i++)scanf("%d",&L.r[i].key);}voidPrintSq(SqListL){inti;for(i=1;i<=L.length;i++)printf("%2d",L.r[i].key);printf("\n");}intPartition(SqList&L,intlow,inthigh){//交換順序表L中子表r[low…h(huán)igh]的記錄,樞軸記錄到位,并返回其所在位置,//此時(shí)在它之前/后的記錄均不大/小于它intpivotkey;L.r[0]=L.r[low];//用子表的第一個(gè)記錄作樞軸記錄pivotkey=L.r[low].key;//樞軸記錄關(guān)鍵字while(low<high){//從表的兩端交替地向中間掃描while(low<high&&L.r[high].key>=pivotkey)--high;L.r[low]=L.r[high];//將比樞軸記錄小的記錄移到低端while(low<high&&L.r[low].key<=pivotkey)++low;L.r[high]=L.r[low];//將比樞軸記錄大的記錄移到高端}L.r[low]=L.r[0];//樞軸記錄到位PrintSq(L);returnlow;//返回樞軸位置}//PartitionvoidQSort(SqList&L,intlow,inthigh){//對(duì)順序表L中的子序列L.r[low…h(huán)igh]作快速排序intpivotloc;if(low<high){//長(zhǎng)度大于1pivotloc=Partition(L,low,high);//將L.r[low…h(huán)igh]一分為二QSort(L,low,pivotloc-1