《數(shù)據(jù)結(jié)構(gòu)》內(nèi)部排序12種算法上機(jī)試驗(yàn)報(bào)告

本文格式為Word版，下載可任意編輯——《數(shù)據(jù)結(jié)構(gòu)》內(nèi)部排序12種算法上機(jī)試驗(yàn)報(bào)告

內(nèi)部排序12種算法的經(jīng)典語(yǔ)句,十分詳細(xì)。

成都信息工程學(xué)院計(jì)算機(jī)系

課程試驗(yàn)報(bào)告

內(nèi)部排序12種算法的經(jīng)典語(yǔ)句,十分詳細(xì)。

（說(shuō)明：試驗(yàn)報(bào)告必需包含下面的每項(xiàng)內(nèi)容，根據(jù)試驗(yàn)狀況認(rèn)真填寫(xiě)，封面必需打印或復(fù)?。ˋ4紙），書(shū)寫(xiě)上機(jī)試驗(yàn)報(bào)告內(nèi)容的紙張也用A4紙，最終從側(cè)面裝訂）

一

目的：從鍵盤(pán)輸入一組數(shù)，通過(guò)內(nèi)部排序的

12種算法對(duì)這組數(shù)字進(jìn)行排序。熟練把握剛

剛學(xué)過(guò)的內(nèi)部排序的算法，并對(duì)這12種排序算法的時(shí)間繁雜度進(jìn)行比較，根據(jù)不同的狀況，選擇適合的算法

二

PC機(jī)每人1臺(tái)

三

實(shí)現(xiàn)內(nèi)部排序的12種排序算法的全排序。

四（注：可打?。?/p>

（用傳統(tǒng)流程圖的形式表示）

內(nèi)部排序12種算法的經(jīng)典語(yǔ)句,十分詳細(xì)。

五

（記錄下你調(diào)試程序中出現(xiàn)的錯(cuò)誤信息的英文提醒，分析出錯(cuò)原因及可能的解決方法）

六（注：源程序可打?。?/p>

（同時(shí)記錄下你對(duì)你編寫(xiě)此程序的其它具體想法，）主要的程序：

/********************************直接插入排序***************************/voidInsertSort(SqListL){//直接插入排序inti,j;for(i=2;i=L.length;++i){

內(nèi)部排序12種算法的經(jīng)典語(yǔ)句,十分詳細(xì)。

{//依次將L的第2個(gè)～最終1個(gè)記錄插入d中if(L.r[i].keyd[first].key){//待插記錄小于d中最小值，插到d[first]之前(不需移動(dòng)d數(shù)組的元素)first=(first-1+L.length)%L.length;//設(shè)d為循環(huán)向量d[first]=L.r[i];}elseif(L.r[i].keyd[final].key){//待插記錄大于d中最大值，插到d[final]之后(不需移動(dòng)d數(shù)組的元素)final=final+1;d[final]=L.r[i];}else{//待插記錄大于d中最小值，小于d中最大值，插到d的中間(需要移動(dòng)d數(shù)組的元素)j=final++;//移動(dòng)d的尾部元素以便按序插入記錄while(L.r[i].keyd[j].key){d[(j+1)%L.length]=d[j];j=(j-1+L.length)%L.length;}d[j+1]=L.r[i];}}for(i=1;i=L.length;i++)//把d賦給L.rL.r[i]=d[(i+first-1)%L.length];//線性關(guān)系}

/***************************************希爾排序***************************/voidShellInsert(SqListL,intdk){

//printf(OK);inti,j;for(i=dk+1;i=L.length;i++)if(L.r[i].keyL.r[i-dk].key){L.r[0]=L.r[i];for(j=i-dk;j0(L.r[0].keyL.r[j].key);j=j-dk)L.r[j+dk]=L.r[j];L.r[j+dk]=L.r[0];}}

voidShellSort(SqListL,intdlta[],intt){

//printf(OK);

內(nèi)部排序12種算法的經(jīng)典語(yǔ)句,十分詳細(xì)。

intk;for(k=0;kt;++k)ShellInsert(L,dlta[k]);//display(L);}

/***********************************表插入排序***********************/voidTableInsert(SLinkListTypeSL,RedTypeD[]){//由數(shù)組D建立的n個(gè)元素的表插入排序的靜態(tài)鏈表SLinti,p,q;SL.r[0].rc.key=INT_MAX;//表頭結(jié)點(diǎn)記錄的關(guān)鍵字取得最大整數(shù)（非降序表的表尾）SL.r[0].next=0;//next域?yàn)?表示表尾（現(xiàn)為空表，初始化）for(i=0;iMAXSIZE;i++){SL.r[i+1].rc=D[i];//將數(shù)組D的值賦給靜態(tài)鏈表SLq=0;p=SL.r[0].next;while(SL.r[p].rc.key=SL.r[i+1].rc.key){//靜態(tài)鏈表后移q=p;p=SL.r[p].next;}SL.r[i+1].next=p;SL.r[q].next=i+1;//將當(dāng)前記錄插入到靜態(tài)鏈表}SL.length=MAXSIZE;}

voidArrange(SLinkListTypeSL){

//根據(jù)靜態(tài)鏈表SL中各結(jié)點(diǎn)的指針值調(diào)整記錄位置，使得SL中記錄按關(guān)鍵字非遞減有序排列inti,p,q;SLNodet;p=SL.r[0].next;//p指示第一個(gè)記錄的當(dāng)前位置printf(%d,SL.length);for(i=1;iSL.length;i++){//SL.r[i...i-1]中記錄已按關(guān)鍵字有序排列，第i個(gè)記錄在SL中的當(dāng)前記錄不應(yīng)小于iwhile(pi)p=SL.r[p].next;//找到第i個(gè)記錄，并用p指示其在SL中當(dāng)前位置q=SL.r[p].next;//q指示當(dāng)前未調(diào)整的表尾if(p!=i){t=SL.r[p];//交換記錄，使第i個(gè)記錄到位SL.r[p]=SL.r[i];

內(nèi)部排序12種算法的經(jīng)典語(yǔ)句,十分詳細(xì)。

SL.r[i]=t;SL.r[i].next=p;//指向被移走的記錄，使得以后可由while循環(huán)找回}p=q;//p指示未調(diào)整的表尾，為找到第i+1個(gè)記錄作準(zhǔn)備//print(SL);//printf(\n);}}

/*************************************冒泡排序***********************/voidbubble_sort(SqListL){//冒泡排序inti;intk;RedTypetem;for(i=L.length-1,k=1;i=1k;--i){k=0;for(intj=1;j=i;++j){if(L.r[j].keyL.r[j+1].key){tem=L.r[j];L.r[j]=L.r[j+1];L.r[j+1]=tem;k=1;}}}}

/************************************快速排序**************************/

intPartition(SqListL,intlow,inthigh){//快速排序遞歸函數(shù)的實(shí)現(xiàn)intpivotkey;L.r[0]=L.r[low];pivotkey=L.r[low].key;while(lowhigh){while(lowhighL.r[high].key=pivotkey)--high;L.r[low]=L.r[high];while(lowhighL.r[low].key=pivotkey)

內(nèi)部排序12種算法的經(jīng)典語(yǔ)句,十分詳細(xì)。

L.r[high]=L.r[low];}L.r[low]=L.r[0];returnlow;}

/********************************簡(jiǎn)單項(xiàng)選擇擇排序***********************/intSelectMinKey(SqListL,inti){intj,k=i;for(j=i+1;jL.length;j++){if(L.r[k].keyL.r[j].key)k=j;}returnk;}

voidSelect_Sort(SqListL){inti,j;RedTypetem;for(i=1;iL.length;i++){j=SelectMinKey(L,i);if(i!=j){tem=L.r[i];L.r[i]=L.r[j];L.r[j]=tem;}}}

/**************************************堆排序*************************/

voidHeapAdjust(HeadTypeL,ints,intm){//對(duì)生成的堆進(jìn)行排序，生成大頂堆RedTyperc;rc=L.r[s];intj;for(j=2*s;j=m;j*=2){if(jm(L.r[j].keyL.r[j+1].key))

內(nèi)部排序12種算法的經(jīng)典語(yǔ)句,十分詳細(xì)。

if(rc.key=L.r[j].key)break;L.r[s]=L.r[j];s=j;}L.r[s]=rc;}

voidHeadSort(HeadTypeL)

{//對(duì)一組無(wú)序的數(shù)字進(jìn)行排序生成堆inti;RedTypetemp;for(i=L.length/2;i0;--i)HeapAdjust(L,i,L.length);for(i=L.length;i1;--i){temp=L.r[1];L.r[1]=L.r[i];L.r[i]=temp;HeapAdjust(L,1,i-1);}}

/**************************************歸并排序***************************/voidMerge(RedTypeSR[],RedTypeTR[],ints,intm,intt){//printf(+_+_+_+_+_+_);inti,j,k;

//RcdType*tem;for(j=m+1,k=s,i=s;i=mj=t;k++){if(SR[i].keySR[j].key)TR[k]=SR[i++];elseTR[k]=SR[j++];}while(i=m){//for(l=0;lm-1;l++,k++,i++)TR[k++]=SR[i++];}while(j=t){//for(l=0;ln-j;l++,k++,j++)

內(nèi)部排序12種算法的經(jīng)典語(yǔ)句,十分詳細(xì)。

TR[k++]=SR[j++];}}

voidMSort(RedTypeSR[],RedTypeTR1[],ints,intt){intm;RedTypeTR2[MAXSIZE+1];if(s==t)TR1[s]=SR[s];else{m=(s+t)/2;MSort(SR,TR2,s,m);MSort(SR,TR2,m+1,t);Merge(TR2,TR1,s,m,t);}}

voidMergeSort(SqListL){MSort(L.r,L.r,1,L.length);}

/************************************基數(shù)排序*************************/

oidInitList(SLListL,RedTypeD[],intn)//初始化靜態(tài)鏈表L(把數(shù)組D中的數(shù)據(jù)存于L中){charc[MAX_NUM_OF_KEY],c1[MAX_NUM_OF_KEY];inti,j,max=D[0].key;//max為關(guān)鍵字的最大值for(i=1;in;i++)if(maxD[i].key)

max=D[i].key;L.keynum=int(ceil(log10(max)));L.recnum=n;for(i=1;i=n;i++){L.r[i].otheritems=D[i-1].otherinfo;itoa(D[i-1].key,c,10);//將10進(jìn)制整型轉(zhuǎn)化為字符型，存入cfor(j=strlen(c);jL.keynum;j++)//若c的長(zhǎng)度max的位數(shù)，在c前補(bǔ)'0'{strcpy(c1,0);strcat(c1,c);strcpy(c,c1);}

for(j=0;jL.keynum;j++)L.r[i].keys[j]=c[L.keynum-1-j];

內(nèi)部排序12種算法的經(jīng)典語(yǔ)句,十分詳細(xì)。

}

voidDistribute(SLCellr[],inti,ArrTypef,ArrTypee)//算法10.15

{//靜態(tài)鍵表L的r域中記錄已按(keys[0]，，keys[i-1])有序。本算法按

//第i個(gè)關(guān)鍵字keys[i]建立RADIX個(gè)子表，使同一子表中記錄的keys[i]一致。//f[0..RADIX-1]和e[0..RADIX-1]分別指向各子表中第一個(gè)和最終一個(gè)記錄intj,p;

for(j=0;jRADIX;++j)f[j]=0;//各子表初始化為空表for(p=r[0].next;p;p=r[p].next){j=r[p].keys[i]-'0';//將記錄中第i個(gè)關(guān)鍵字映射到[0..RADIX-1]if(!f[j])f[j]=p;elser[e[j]].next=p;e[j]=p;//將p所指的結(jié)點(diǎn)插入第j個(gè)子表中}}

voidCollect(SLCellr[],ArrTypef,ArrTypee)//算法10.16

//本算法按keys[i]自小至大地將f[0..RADIX-1]所指各子表依次鏈接成//一個(gè)鏈表，e[0..RADIX-1]為各子表的尾指針。{intj,t;

for(j=0;!f[j];j=++j);//找第一個(gè)非空子表r[0].next=f[j];

t=e[j];//r[0].next指向第一個(gè)非空子表中第一個(gè)結(jié)點(diǎn)while(jRADIX-1)

{for(j=++j;jRADIX-1!f[j];j=++j);//找下一個(gè)非空子表if(f[j])//鏈接兩個(gè)非空子表{r[t].next=f[j];t=e[j];}}

r[t].next=0;//t指向最終一個(gè)非空子表中的最終一個(gè)結(jié)點(diǎn)}

voidprintl(SLListL)//按鏈表輸出靜態(tài)鏈表{inti=L.r[0].next,j;while(i)

{for(j=L.keynum-1;j=0;j--)printf(%c,L.r[i].keys[j]);printf();i=L.r[i].next;}

內(nèi)部排序12種算法的經(jīng)典語(yǔ)句,十分詳細(xì)。

voidRadixSort(SLListL)//算法10.17

//L是采用靜態(tài)鏈表表示的順序表。對(duì)L作基數(shù)排序，使得L成為按關(guān)鍵字//自小到大的有序靜態(tài)鏈表，L.r[0]為頭結(jié)點(diǎn)。{inti;

ArrTypef,e;

for(i=0;iL.recnum;++i)L.r[i].next=i+1;L.r[L.recnum].next=0;//將L改造為靜態(tài)鏈表

for(i=0;iL.keynum;++i)//按最低位優(yōu)先依次對(duì)各關(guān)鍵字進(jìn)行分派和收集{Distribute(L.r,i,f,e);//第i趟分派Collect(L.r,f,e);//第i趟收集

printf(第%d趟收集后:\n,i+1);printl(L);printf(\n);}}

voidprint(SLListL)//按數(shù)組序號(hào)輸出靜態(tài)鏈表{inti,j;

printf(keynum=%drecnum=%d\n,L.keynum,L.recnum);for(i=1;i=L.recnum;i++){printf(keys=);

for(j=L.keynum-1;j=0;j--)printf(%c,L.r[i].keys[j]);

printf(otheritems=%dnext=%d\n,L.r[i].otheritems,L.r[i].next);}}

voidSort(SLListL,intadr[])//改此句(類型)

//求得adr[1..L.length]，adr[i]為靜態(tài)鏈表L的第i個(gè)最小記錄的序號(hào){inti=1,p=L.r[0].next;while(p)

{adr[i++]=p;p=L.r[p].next;}}

voidRearrange(SLListL,intadr[])//改此句(類型)

//adr給出靜態(tài)鏈表L的有序次序，即L.r[adr[i]]是第i小的記錄。//本算法按adr重排L.r，使其有序。算法10.18(L的類型有變){inti,j,k;

for(i=1;iL.recnum;++i)//改此句(類型)if(adr[i]!=i){j=i;

內(nèi)部排序12種算法的經(jīng)典語(yǔ)句,十分詳細(xì)。

L.r[0]=L.r[i];//暫存記錄L.r[i]

while(adr[j]!=i)//調(diào)整L.r[adr[j]]的記錄到位直到adr[j]=i為止{k=adr[j];L.r[j]=L.r[k];adr[j]=j;

j=k;//記錄按序到位}

L.r[j]=L.r[0];adr[j]=j;}}

運(yùn)行效果圖：

內(nèi)部排序12種算法的經(jīng)典語(yǔ)句,十分詳細(xì)。

14/16

內(nèi)部排序12種算法的經(jīng)典語(yǔ)句,十分詳細(xì)。

七

（在上機(jī)試驗(yàn)中遇到的你不能解決的其它問(wèn)題，簡(jiǎn)單描述一下你此次上機(jī)的收獲及感想）

心得：

排序時(shí)計(jì)算機(jī)程序設(shè)計(jì)中的一種重要的操作，由于我們無(wú)論做什么樣的程序都會(huì)涉及到排序算法，在第十章的內(nèi)部排序算法中，基本上都是一些經(jīng)典的排序算法，這是我選擇這個(gè)題目的主要原因，由于通過(guò)這個(gè)綜合設(shè)計(jì)，我可以了解不