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

1、數 據 結 構課程設計報告題 目： 專 業(yè)： 班 級： 學 號： 姓 名： 指導老師： 時 間： 一、課程設計題目及所涉及知識點設計題目：排序算法實現(xiàn)知識點：malloc申請連續(xù)存儲空間、冒泡排序、快速排序、直接插入排序的算法實現(xiàn)、結構體的定義與調用、函數的遞歸調用二、課程設計思路及算法描述設計思路：1、確定程序要實現(xiàn)的功能即（1）允許用戶輸入一組數據，任意多個。（2）由用戶選擇對該組數據進行排序的方法：直接插入排序、冒泡排序、快速排序。并可以查看每趟排序的結果。2、確定程序所需要的功能塊，存儲結構-結構體，malloc申請存儲空間，各功能函數-冒泡排序功能塊maopao()；、直接插入排序功

2、能塊insertsort()；、快速排序q_sort(）；、數據訪問功能塊traveres()；、數據輸出功能塊liststring();主函數部分main()；。3、編寫代碼具體實現(xiàn)各項功能，并進行調試。算法描述： 冒泡排序（Bubble Sorting）的基本思想：設待排序n個元素存放在數組an中,無序區(qū)范圍初始為(a(0),a(1),a(2),.,an-1),冒泡排序方法是在當前無序區(qū)內,從最上面的元素a0開始,對每兩個相鄰的元素ai+1和ai(i=0,1,.,n-1)進行比較,且使值較小的元素換至值較大的元素之上(若aiai+1,則ai和ai+1的值互換),這樣經過一趟冒泡排序后,假設

3、最后下移的元素為ak,則無序區(qū)中值較大的幾個元素到達下端并從小到大依次存放在ak+1,ak+2,.an-1中,這樣無序區(qū)范圍變?yōu)?a0,a1,a2,.,ak)。在當前無序區(qū)內進行下一趟冒泡排序。這個過程一直到某一趟排序中不出現(xiàn)元素交換的動作，排序結束。整個排序過程最多執(zhí)行n-1遍。算法實現(xiàn)：void BubbleSort(SeqList R)/R（l.n)是待排序的文件，采用自下向上掃描，對R做冒泡排序 int i，j； Boolean exchange； /交換標志 for(i=1;i=i；j-) /對當前無序區(qū)Ri.n自下向上掃描 if(Rj+1.keyRj.key)/交換記錄 R0=Rj

4、+1； /R0不是哨兵，僅做暫存單元 Rj+1=Rj； Rj=R0； exchange=TRUE； /發(fā)生了交換，故將交換標志置為真 if(!exchange) /本趟排序未發(fā)生交換，提前終止算法 return； /endfor(外循環(huán)) /BubbleSort直接插入排序（Straight Insertion Sorting）的基本思想：把n個待排序的元素看成為一個有序表和一個無序表，開始時有序表中只包含一個元素，無序表中包含有n-1個元素，排序過程中每次從無序表中取出第一個元素，將它插入到有序表中的適當位置，使之成為新的有序表，重復n-1次可完成排序過程。把ai插入到a0，a1，.,ai-

5、1之中的具體實施過程為:先把ai賦值給變量t,然后將t依次與ai-1,ai-2,.進行比較,將比t大的元素右移一個位置,直到發(fā)現(xiàn)某個j(0=j=i-1),使得aj=t或j為(-1),把t賦值給aj+1.算法實現(xiàn)：void insert_sort(ElemType a,int n)/待排序元素用一個數組a表示，數組有n個元素 int i,j;ElemType t;for ( i=1; i=0)& (taj) aj+1=aj; j-; / 順序比較和移動aj+1=t;快速排序算法：在Rlow.high中任選一個記錄作為基準(Pivot)，以此基準將當前無序區(qū)劃分為左、右兩個較小的子區(qū)間Rlow.p

6、ivotpos-1)和Rpivotpos+1.high，并使左邊子區(qū)間中所有記錄的關鍵字均小于等于基準記錄(不妨記為pivot)的關鍵字pivot.key，右邊的子區(qū)間中所有記錄的關鍵字均大于等于pivot.key，而基準記錄pivot則位于正確的位置(pivotpos)上，它無須參加后續(xù)的排序。算法實現(xiàn)： void QuickSort(SeqList R，int low，int high) /對Rlow.high快速排序 int pivotpos； /劃分后的基準記錄的位置 if(lowhigh)/僅當區(qū)間長度大于1時才須排序 pivotpos=Partition(R，low，high)；

7、/對Rlow.high做劃分 QuickSort(R，low，pivotpos-1)； /對左區(qū)間遞歸排序 QuickSort(R，pivotpos+1，high)； /對右區(qū)間遞歸排序 /QuickSort三、課程設計中遇到的難點及解決辦法問題：如何實現(xiàn)對每趟排序結果的存儲、訪問？解決方法：設計一個并行的存儲空間（結構體數組），存儲每趟排序的結果，通過指針型參數傳遞存儲空間的地址實現(xiàn)數據的實時存儲。問題：如何實現(xiàn)結構體數組作為參數傳遞數據，并使數組中的數據可以真實的改變，實現(xiàn)類似于“&”(引用)應用的功能？解決方法：運用指針即將結構體數組的首地址作為一個結構體指針進行參數的傳遞，由于指針的特

8、性從而實現(xiàn)數據的實時傳遞!四、總結課程設計是鞏固所學知識理論，提高程序設計的重要環(huán)節(jié)，通過課程設計的訓練，使我們能夠綜合應用數據結構的基礎知識，加深了對于所學知識的理解，也更加懂得了實踐的重要性，也明白了各種算法重要的是理解其原理，而不是死記硬背！同時讓我們更加了解自身不足和知識學習缺陷，從而不斷完善自我，提高自己的學習水平。在設計過程中我們真正實現(xiàn)了把所學知識運用于實踐，逐漸培養(yǎng)自己的思維和邏輯能力以及實踐能力，做到學以致用。五、附錄主要源程序代碼及運行結果#include stdio.h#include malloc.htypedef int elemtype;typedef struct

9、 /存儲排序數據elemtype *data;int length;list;typedef struct /存儲每趟排序數據elemtype *sqdata;sqlist,*linklist;/*設置一個標志位flag，將其初始值設置為非0，表示被排序的表是一個*無序的表，在進行數據交換時，修改flag為0。在新一輪排序開始時，檢查*此標志，若此標志為1，表示上一次沒有做過交換數據，則結束排序；否則*繼續(xù)排序；*/int maopao(list &l,linklist sql,int x)/冒泡排序int flag;for(int i=1;i=x;i+)flag=1;/標記是否有數據交換fo

10、r(int j=1;jl.dataj+1)l.data0=l.dataj;l.dataj=l.dataj+1;l.dataj+1=l.data0;flag=0;for(int m=1;m=x;m+)/每趟排序結果的存儲sqli-1.sqdatam=l.datam;if(1=flag) break;return i-1;/返回排序趟數/直接插入排序int Insertsort(list &l,linklist sql,int x)for(int i=2;i=x;i+)if(l.datail.datai-1)l.data0=l.datai;for(int j=i-1;l.data0l.dataj;

11、j-)l.dataj+1=l.dataj;l.dataj+1=l.data0;for(int m=1;m=x;m+)/每趟排序結果的存儲sqli-2.sqdatam=l.datam;return i-2;/返回排序趟數void q_sort(list &l,int low,int high)/快速排序（遞歸）int pivot;int left,right;l.data0=l.datalow;left=low;right=high;if(low=high)while(lowhigh)while(low=l.data0)high-;if(low!=high)l.datalow=l.datahig

12、h;low+;while(lowhigh) & (l.datalow=l.data0)low+;if(low!=high)l.datahigh=l.datalow;high-;l.datalow=l.data0;pivot=low;if(leftpivot)q_sort(l,high+1,right);elseprintf(未輸入數據！);/訪問一遍數據并輸出最終排序結果void traveres(list L,int x)printf(最終排序結果：);for(int i=1;i=x;i+)printf(%3d,L.datai);printf(n);printf(*nn);void list

13、string(list l,linklist sql,int num,int x)/輸出每趟排序結果int z;printf(共記錄有%d趟排序結果,n,num);traveres(l,x); printf(要查看第幾趟排序結果？ );scanf(%d,&z);printf(n);printf(*nn);printf(第%d趟排序結果為：,z);for(int a=1;a=x;a+)printf(%5d,sqlz-1.sqdataa);printf(nn);void main()/主函數部分list l;int x;int y;int num;linklist sql;printf(請輸入要排

14、序的數據的個數：);scanf(%d,&x);if(x=0)printf(數據個數不能為0 ！n);elsel.data=(elemtype *)malloc(x * sizeof(elemtype); /申請存儲空間sql=(linklist )malloc(x * sizeof(linklist);for(int q=0;qx;q+)sqlq.sqdata=(elemtype *)malloc(x * sizeof(elemtype);/申請存儲空間printf(請輸入要排序的數據：n);for(int i=1;i=x;i+)/接收數據printf(請輸入第%d個數據：,i);scanf(%d,&l.datai);printf(請輸入要使用的排序方法：1、冒泡 2、直接插入排序、3、快速排序n);printf(您的選擇為：);scanf(%d,&y);printf(*n);switch(y)case 1:printf(您選擇了“冒泡排序”n);num=maopao(l,sql,x);liststring(l,sql,num,x)