數(shù)據(jù)結構課程設計報告各種排序算法的實現(xiàn)

.PAGE.數(shù)據(jù)結構課程設計報告題目：專業(yè)：班級：學號：姓名：指導教師：時間：..一、課程設計題目及所涉及知識點設計題目：排序算法實現(xiàn)知識點：malloc申請連續(xù)存儲空間、冒泡排序、快速排序、直接插入排序的算法實現(xiàn)、 構造體的定義與調用、函數(shù)的遞歸調用二、課程設計思路及算法描述設計思路：1、確定程序要實現(xiàn)的功能即〔1〕允許用戶輸入一組數(shù)據(jù)，任意多個?！?〕由用戶選擇對該組數(shù)據(jù)進展排序的方法：直接插入排序、冒泡排序、快速排序。并可以查看每趟排序的結果。2、確定程序所需要的功能塊，存儲構造-構造體，malloc申請存儲空間，各功能函數(shù)--冒泡排序功能塊maopao()；、直接插入排序功能塊insertsort()；、快速排序q_sort(〕；、數(shù)據(jù)訪問功能塊traveres()；、數(shù)據(jù)輸出功能塊liststring();主函數(shù)局部main()；。3、編寫代碼具體實現(xiàn)各項功能，并進展調試。算法描述：冒泡排序〔BubbleSorting〕的根本思想：設待排序n個元素存放在數(shù)組a[n]中,無序區(qū)圍初始為(a(0),a(1),a(2),...,a[n-1]),冒泡排序方法是在當前無序區(qū),從最上面的元素a[0]開場,對每兩個相鄰的元素a[i+1]和a[i](i=0,1,...,n-1)進展比擬,且使值較小的元素換至值較大的元素之上(假設a[i]>a[i+1],那么a[i]和a[i+1]的值互換),這樣經(jīng)過一趟冒泡排序后,假設最后下移的元素為a[k],那么無序區(qū)中值較大的幾個元素到達下端并從小到大依次存放在a[k+1],a[k+2],...a[n-1]中,這樣無序區(qū)圍變?yōu)?a[0],a[1],a[2],...,a[k])。在當前無序區(qū)進展下一趟冒泡排序。這個過程一直到某一趟排序中不出現(xiàn)元素交換的動作，排序完畢。整個排序過程最多執(zhí)行n-1遍。算法實現(xiàn)：voidBubbleSort(SeqListR)//R〔l..n)是待排序的文件，采用自下向上掃描，對R做冒泡排序{ inti，j； Booleanexchange；//交換標志 for(i=1;i<n;i++){//最多做n-1趟排序 exchange=FALSE；//本趟排序開場前，交換標志應為假 for(j=n-1;j>=i；j--)//對當前無序區(qū)R[i..n]自下向上掃描 if(R[j+1].key<R[j].key){//交換記錄 R[0]=R[j+1]；//R[0]不是哨兵，僅做暫存單元 R[j+1]=R[j]； R[j]=R[0]； exchange=TRUE；//發(fā)生了交換，故將交換標志置為真 } if(!exchange)//本趟排序未發(fā)生交換，提前終止算法 return； }//endfor(外循環(huán)) }//BubbleSort直接插入排序〔StraightInsertionSorting〕的根本思想：把n個待排序的元素看成為一個有序表和一個無序表，開場時有序表中只包含一個元素，無序表中包含有n-1個元素，排序過程中每次從無序表中取出第一個元素，將它插入到有序表中的適當位置，使之成為新的有序表，重復n-1次可完成排序過程。

把a[i]插入到a[0]，a[1]，...,a[i-1]之中的具體實施過程為:先把a[i]賦值給變量t,然后將t依次與a[i-1],a[i-2],...進展比擬,將比t大的元素右移一個位置,直到發(fā)現(xiàn)某個j(0<=j<=i-1),使得a[j]<=t或j為(-1),把t賦值給a[j+1].算法實現(xiàn)：voidinsert_sort(ElemTypea[],intn)

//待排序元素用一個數(shù)組a表示，數(shù)組有n個元素

{ inti,j;

ElemTypet;

for(i=1;i<n;i++)//i表示插入次數(shù)，共進展n-1次插入

{ t=a[i];//把待排序元素賦給t

j=i-1;

while((j>=0)&&(t<a[j])){ a[j+1]=a[j];j--;}//順序比擬和移動

a[j+1]=t;}

}

快速排序算法：在R[low..high]中任選一個記錄作為基準(Pivot)，以此基準將當前無序區(qū)劃分為左、右兩個較小的子區(qū)間R[low..pivotpos-1)和R[pivotpos+1..high]，并使左邊子區(qū)間中所有記錄的關鍵字均小于等于基準記錄(不妨記為pivot)的關鍵字pivot.key，右邊的子區(qū)間中所有記錄的關鍵字均大于等于pivot.key，而基準記錄pivot那么位于正確的位置(pivotpos)上，它無須參加后續(xù)的排序。算法實現(xiàn)：voidQuickSort(SeqListR，intlow，inthigh)

{//對R[low..high]快速排序

intpivotpos；//劃分后的基準記錄的位置

if(low<high){//僅當區(qū)間長度大于1時才須排序

pivotpos=Partition(R，low，high)；//對R[low..high]做劃分

QuickSort(R，low，pivotpos-1)；//對左區(qū)間遞歸排序

QuickSort(R，pivotpos+1，high)；//對右區(qū)間遞歸排序

}

}//QuickSort三、課程設計中遇到的難點及解決方法問題：如何實現(xiàn)對每趟排序結果的存儲、訪問？解決方法：設計一個并行的存儲空間〔構造體數(shù)組〕，存儲每趟排序的結果，通過指針型參數(shù) 傳遞存儲空間的地址實現(xiàn)數(shù)據(jù)的實時存儲。問題：如何實現(xiàn)構造體數(shù)組作為參數(shù)傳遞數(shù)據(jù)，并使數(shù)組中的數(shù)據(jù)可以真實的改變，實現(xiàn)類 似于"&〞(引用)應用的功能？解決方法：運用指針即將構造體數(shù)組的首地址作為一個構造體指針進展參數(shù)的傳遞，由于指 針的特性從而實現(xiàn)數(shù)據(jù)的實時傳遞!四、總結課程設計是穩(wěn)固所學知識理論，提高程序設計的重要環(huán)節(jié)，通過課程設計的訓練，使我們能夠綜合應用數(shù)據(jù)構造的根底知識，加深了對于所學知識的理解，也更加懂得了實踐的重要性，也明白了各種算法重要的是理解其原理，而不是死記硬背！同時讓我們更加了解自身缺乏和知識學習缺陷，從而不斷完善自我，提高自己的學習水平。在設計過程中我們真正實現(xiàn)了把所學知識運用于實踐，逐漸培養(yǎng)自己的思維和邏輯能力以及實踐能力，做到學以致用。五、附錄—主要源程序代碼及運行結果#include"stdio.h"#include"malloc.h"typedefintelemtype;typedefstruct{//存儲排序數(shù)據(jù) elemtype*data; intlength;}list;typedefstruct{//存儲每趟排序數(shù)據(jù) elemtype*sqdata;}sqlist,*linklist;/** 設置一個標志位flag，將其初始值設置為非0，表示被排序的表是一個*無序的表，在進展數(shù)據(jù)交換時，修改flag為0。在新一輪排序開場時，檢查*此標志，假設此標志為1，表示上一次沒有做過交換數(shù)據(jù)，那么完畢排序；否那么*繼續(xù)排序；*/intmaopao(list&l,linklistsql,intx){ //冒泡排序 intflag; for(inti=1;i<=x;i++){ flag=1; //標記是否有數(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++) //每趟排序結果的存儲 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++) //每趟排序結果的存儲 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);//遞歸調用 if(right>pivot) q_sort(l,high+1,right); } else printf("未輸入數(shù)據(jù)！");}//訪問一遍數(shù)據(jù)并輸出最終排序結果voidtraveres(listL,intx){ printf("最終排序結果："); for(inti=1;i<=x;i++) printf("%3d",L.data[i]); printf("\n"); printf("***************************************\n\n");}voidliststring(listl,linklistsql,intnum,intx){ //輸出每趟排序結果 intz; printf("共記錄有%d趟排序結果,\n",num); traveres(l,x); printf("要查看第幾趟排序結果？"); scanf("%d",&z); printf("\n"); printf("***************************************\n\n"); printf("第%d趟排序結果為：",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("請輸入要排序的數(shù)據(jù)的個數(shù)："); scanf("%d",&x); if(x==0) printf("數(shù)據(jù)個數(shù)不能為0！\n"); else{ l.data=(elemtype*)malloc(x*sizeof(elemtype)); //申請存儲空間 sql=(linklist)malloc(x*sizeof(linklist)); for(intq=0;q<x;q++) sql[q].sqdata=(elemtype*)malloc(x*sizeof(elemtype));//申請存儲空間 printf("請輸入要排序的數(shù)據(jù)：\n"); for(inti=1;i<=x;i++){ //接收數(shù)據(jù) printf("請輸入第%d個數(shù)據(jù)：",i); scanf("%d",&l.data[i]); } printf("請輸入要使用的排序方法：1、冒泡2、直接插入排