數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(各種排序算法的實(shí)現(xiàn))

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)（各種排序算法的實(shí)現(xiàn)）數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告題專(zhuān)業(yè)：班級(jí)：學(xué)號(hào)：姓名：指導(dǎo)老師：時(shí)間：一、課程設(shè)計(jì)題目及所涉及知識(shí)點(diǎn)設(shè)計(jì)題目：排序算法實(shí)現(xiàn)知識(shí)點(diǎn)：malloc申請(qǐng)連續(xù)存儲(chǔ)空間、冒泡排序、快速排序、直接插入排序的算法實(shí)現(xiàn)、結(jié)構(gòu)體的定義與調(diào)用、函數(shù)的遞歸調(diào)用二、課程設(shè)計(jì)思路及算法描述設(shè)計(jì)思路：1、確定程序要實(shí)現(xiàn)的功能即(1)允許用戶(hù)輸入一組數(shù)據(jù)，任意多個(gè)。(2)由用戶(hù)選擇對(duì)該組數(shù)據(jù)進(jìn)行排序的方法：直接插入排序、冒泡排序、快速排序。并可以查看每趟排序的結(jié)果2、確定程序所需要的功能塊，存儲(chǔ)結(jié)構(gòu)-結(jié)構(gòu)體，malloc申請(qǐng)存儲(chǔ)空間，各功能函數(shù)一冒泡排序功能塊maopaoO；、直接插入排序功能塊insertsort()；、快速排序q_sort()；、數(shù)據(jù)訪問(wèn)功能塊traveresO、、數(shù)據(jù)輸出功能塊liststring();主函數(shù)部分main()；。3、編寫(xiě)代碼具體實(shí)現(xiàn)各項(xiàng)功能，并進(jìn)行調(diào)試。算法描述：「泡排序(BubbleSorting)的基本思想：設(shè)待排序n個(gè)元素存放在數(shù)組a[n]中,無(wú)序區(qū)算法描述：范圍初始為(a(0),a(1),a(2),???,a[n-1]),冒泡排序方法是在當(dāng)前無(wú)序區(qū)內(nèi),從最上面的元素a[0]開(kāi)始,對(duì)每?jī)蓚€(gè)相鄰的元素a[i+1]和a[i](i=0,1,…,n-1)進(jìn)行比較,且使值較小的元素?fù)Q至值較大的元素之上(若a[i]>a[i+l],則a[i]和a[i+l]的值互換)，這樣經(jīng)過(guò)一趟冒泡排序后，假設(shè)最后下移的元素為a[k],則無(wú)序區(qū)中值較大的幾個(gè)元素到達(dá)下端并從小到大依次存放在a[k+l],a[k+2],...a[n-1]中,這樣無(wú)序區(qū)范圍變?yōu)?a[0],a[l],a[2],...,a[k])。在當(dāng)前無(wú)序區(qū)內(nèi)進(jìn)行下一趟冒泡排序。這個(gè)過(guò)程一直到某一趟排序中不出現(xiàn)元素交換的動(dòng)作，排序結(jié)束。整個(gè)排序過(guò)程最多執(zhí)行n-1遍。算法實(shí)現(xiàn)：voidBubbleSort(SeqListR)//R(l..n)是待排序的文件，采用自下向上掃描,對(duì)R做冒泡排序{inti,j；Booleanexchange；//交換標(biāo)志for(i=l;i<n;i++){//最多做nT趟排序exchange二FALSE；〃本趟排序開(kāi)始前，交換標(biāo)志應(yīng)為假for(j=n-l;j>=i；j—)//對(duì)當(dāng)前無(wú)序區(qū)R[i??n]自下向上掃描if(R[j+1]?key〈R[j]?key){//交換記錄R[O]=R[j+l]；//R[0]不是哨兵，僅做暫存單元

R[j+1]=R[j]；R[j]=R[0]；exchange=TRUE；//發(fā)生了交換，故將交換標(biāo)志置為真}if(!exchange)//本趟排序未發(fā)生交換，提前終止算法return；}//endfor(外循環(huán))}//BubbleSort直接插入排序(StraightInsertionSorting)的基本思想：把n個(gè)待排序的元素看成為一個(gè)有序表和一個(gè)無(wú)序表，開(kāi)始時(shí)有序表中只包含一個(gè)元素，無(wú)序表中包含有n-1個(gè)元素，排序過(guò)程中每次從無(wú)序表中取出第一個(gè)元素，將它插入到有序表中的適當(dāng)位置，使之成為新的有序表，重復(fù)n-1次可完成排序過(guò)程。把a(bǔ)[i]插入到a[0]，a[1]，???，a[i-1]之中的具體實(shí)施過(guò)程為:先把a(bǔ)[i]賦值給變量t,然后將t依次與a[i-1],a[i-2],???進(jìn)行比較，將比t大的元素右移一個(gè)位置,直到發(fā)現(xiàn)某個(gè)的元素右移一個(gè)位置,直到發(fā)現(xiàn)某個(gè)j(0<=j<=i-1),使得a[j]<=t或j為(-1),把t賦值給a[j+1]?算法實(shí)現(xiàn)：voidinsert_sort(ElemTypea[],intn)〃待排序元素用一個(gè)數(shù)組a表示，數(shù)組有n個(gè)元素{inti,j;ElemTypet;for(i=1;i<n;i++)//i表示插入次數(shù)，共進(jìn)行n-1次插入t=a[i];〃把待排序元素賦給tj=i-1;while((j>=0)&&(t<a[j])){a[j+1]=a[j];j--;}//順序比較和移動(dòng)a[j+1]=t;}}快速排序算法：在R[low?.high]中任選一個(gè)記錄作為基準(zhǔn)(Pivot)，以此基準(zhǔn)將當(dāng)前無(wú)序區(qū)劃分為左、右兩個(gè)較小的子區(qū)間R[low..pivotposT)和R[pivotpos+1??high]，并使左邊子區(qū)間中所有pivot)的關(guān)鍵字pivot?key，右邊的子區(qū)間中所有記錄的關(guān)鍵字均大于等于pivot?key，而基準(zhǔn)記錄pivot則位于正確的位置(pivotpos)上，它無(wú)須參加后續(xù)的排序。記錄的關(guān)鍵字均小于等于基準(zhǔn)記錄(不妨記為記錄的關(guān)鍵字均小于等于基準(zhǔn)記錄(不妨記為算法實(shí)現(xiàn)：voidQuickSort（SeqListR，intlow，inthigh）{//對(duì)R[low..high]快速排序intpivotpos；//劃分后的基準(zhǔn)記錄的位置f（low<high）{//僅當(dāng)區(qū)間長(zhǎng)度大于1時(shí)才須排序pivotpos=Partition（R，low，high）；〃對(duì)R[low?.high]做劃分QuickSort（R，low，pivotpos-1）；//對(duì)左區(qū)間遞歸排序QuickSort（R，pivotpos+1，high）；//對(duì)右區(qū)間遞歸排序}}//QuickSort三、課程設(shè)計(jì)中遇到的難點(diǎn)及解決辦法問(wèn)題：如何實(shí)現(xiàn)對(duì)每趟排序結(jié)果的存儲(chǔ)、訪問(wèn)？解決方法：設(shè)計(jì)一個(gè)并行的存儲(chǔ)空間（結(jié)構(gòu)體數(shù)組），存儲(chǔ)每趟排序的結(jié)果，通過(guò)指針型參數(shù)傳遞存儲(chǔ)空間的地址實(shí)現(xiàn)數(shù)據(jù)的實(shí)時(shí)存儲(chǔ)。問(wèn)題：如何實(shí)現(xiàn)結(jié)構(gòu)體數(shù)組作為參數(shù)傳遞數(shù)據(jù)，并使數(shù)組中的數(shù)據(jù)可以真實(shí)的改變，實(shí)現(xiàn)類(lèi)似于“&”（引用）應(yīng)用的功能？解決方法：運(yùn)用指針即將結(jié)構(gòu)體數(shù)組的首地址作為一個(gè)結(jié)構(gòu)體指針進(jìn)行參數(shù)的傳遞，由于指針的特性從而實(shí)現(xiàn)數(shù)據(jù)的實(shí)時(shí)傳遞!四、總結(jié)課程設(shè)計(jì)是鞏固所學(xué)知識(shí)理論，提高程序設(shè)計(jì)的重要環(huán)節(jié)，通過(guò)課程設(shè)計(jì)的訓(xùn)練，使我們能夠綜合應(yīng)用數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)知識(shí)，加深了對(duì)于所學(xué)知識(shí)的理解，也更加懂得了實(shí)踐的重要性，也明白了各種算法重要的是理解其原理，而不是死記硬背！同時(shí)讓我們更加了解自身不足和知識(shí)學(xué)習(xí)缺陷，從而不斷完善自我，提高自己的學(xué)習(xí)水平。在設(shè)計(jì)過(guò)程中我們真正實(shí)現(xiàn)了把所學(xué)知識(shí)運(yùn)用于實(shí)踐，逐漸培養(yǎng)自己的思維和邏輯能力以及實(shí)踐能力，做到學(xué)以致用。五、附錄—主要源程序代碼及運(yùn)行結(jié)果#include"stdio.h"#include"malloc.h"typedefintelemtype;typedefstruct{//存儲(chǔ)排序數(shù)據(jù)elemtype*data;intlength;}list;typedefstruct{//存儲(chǔ)每趟排序數(shù)據(jù)elemtype*sqdata;}sqlist,*linklist;/**設(shè)置一個(gè)標(biāo)志位flag,將其初始值設(shè)置為非0,表示被排序的表是一個(gè)*無(wú)序的表，在進(jìn)行數(shù)據(jù)交換時(shí)，修改flag為0。在新一輪排序開(kāi)始時(shí)，檢查*此標(biāo)志，若此標(biāo)志為1，表示上一次沒(méi)有做過(guò)交換數(shù)據(jù)，則結(jié)束排序；否則*繼續(xù)排序；*/intmaopao(list&l,linklistsql,intx){//冒泡排序intflag;for(inti=1;i<=x;i++){flag=1;//標(biāo)記是否有數(shù)據(jù)交換for(intj=1;j<=x-i;j++){if(l.data[j]>l.data[j+1]){l.data[0]=l.data[j];l.data[j]=l.data[j+1];l.data[j+1]=l.data[0];flag=0;}}for(intm=1;m<=x;m++)//每趟排序結(jié)果的存儲(chǔ)sql[i-1].sqdata[m]=l.data[m];if(1==flag)break;}returni-1;//返回排序趟數(shù)}//直接插入排序intInsertsort(list&l,linklistsql,intx){for(inti=2;i<=x;i++){if(l.data[i]<l.data[i-1]){l.data[0]=l.data[i];for(intj=i-1;l.data[0]<l.data[j];j--)l.data[j+1]=l.data[j];l.data[j+1]=l.data[0];}for(intm=1;m<=x;m++)//每趟排序結(jié)果的存儲(chǔ)sql[i-2].sqdata[m]=l.data[m];}returni-2;//返回排序趟數(shù)}voidq_sort(list&l,intlow,inthigh){//快速排序(遞歸)intpivot;intleft,right;l.data[0]=l.data[low];left=low;right=high;if(low<=high){while(low<high){while((low<high)&&(l.data[high]>=l.data[0]))high--;if(low!=high){

l.data[low]=l.data[high];low++;}&&while((low<high)&&(l.data[low]<=l.data[0]))low++;if(low!=high){l.data[high]=l.data[low];high--;}}l.data[low]=l.data[0];pivot=low;if(left<pivot)q_sort(l,left,high-1);//遞歸調(diào)用if(right>pivot)q_sort(l,high+1,right);}elseprintf（"未輸入數(shù)據(jù)！"）;}voidtraveres(listL,intx){printf（“最終排序結(jié)果:"）;//訪問(wèn)一遍數(shù)據(jù)并輸出最終排序結(jié)果injj//訪問(wèn)一遍數(shù)據(jù)并輸出最終排序結(jié)果injjfor(inti=1;i<=x;i++)printf("%3d",L.data[i]);printf("\n");■?■■?■」■」?■■?■」■」?■■?■■?■■?■」■」?■■?■」■」?■■?■■?■」■」?■■?■」■」?■■?■■?■」■」?■printf("***************************************\n\n");}voidliststring(listl,linklistsql,intnum,intx){//輸出每趟排序結(jié)果intz;printf("共記錄有%d趟排序結(jié)果,\n",num);traveres(l,x);");printf("要查看第幾趟排序結(jié)果？scanf("%d",&z);printf("\n");");printf("***************************************\n\n");printf("第%d趟排序結(jié)果為：",z);for(inta=1;a<=x;a++)printf("%5d",sql[z-1].sqdata[a]);printf("\n\n");}voidmain(){//主函數(shù)部分listl;intx;inty;intnum;linklistsql;printf("請(qǐng)輸入要排序的數(shù)據(jù)的個(gè)數(shù):");scanf("%d",&x);if(x==0)printf("數(shù)據(jù)個(gè)數(shù)不能為0!\n");else{l.data=(elemtype *)malloc(x *sizeof(elemtype));//申請(qǐng)存儲(chǔ)空間sql=(linklist )malloc(x *sizeof(linklist));for(intq=0;q<x;q++)sql[q].sqdata=(elemtype*)malloc(x*sizeof(elemtype));//申請(qǐng)存儲(chǔ)空間printf("請(qǐng)輸入要排序的數(shù)據(jù)：\n");for(inti=1;i<=x;i++){//接收數(shù)據(jù)printf("請(qǐng)輸入第%d個(gè)數(shù)據(jù):",i);scanf("%d",&l.data[i]);}冒泡2、printf（"請(qǐng)輸入要使用的排序方法：1、直接插入排序、3冒泡2、printf("您的選擇為：");scanf("%d",&y);-gr-B:|1JI|11II**\n");switch(y){case1:printf("您選擇了“冒泡排序”\n");num=maopao(l,sql,x);liststring(l,sql,num,x);|1fI||lIl**\n");break;case2:printf(”您選擇了“直接插入排序”\n");num=Insertsort(l,sql,x);liststring(l,sql,num,x);IlfIillI■**\n");break;case3:printf("您選擇了“快速排序”