數(shù)據(jù)結(jié)構(gòu)實驗報告排序算法

1、排序算法驗證及評價實驗報告班級：10020801 姓名：吳亮 學(xué)號：2008302651 電話： 日期：2010.1.8(一) 需求分析1、輸入輸出的形式： 根據(jù)題目要求與提示輸入以文件名，并用你選擇的排序進(jìn)行排序，再編輯以文件名，把你的排好序的文件放入該文件。2、程序所能達(dá)到的功能： 程序?qū)δ愕奈募锏臄?shù)據(jù)進(jìn)行排序。3、測試數(shù)據(jù)： 打開你編輯的文件，查看文件是否已排序。 (二) 概要設(shè)計一，前五種排序：1 基本操作：（1）快速排序函數(shù)int partions(int l,int low,int high); 交換順序表中l(wèi)low.high的記錄，使樞軸記錄到位，并返回請其所在位置，此時在它之

2、前（后）的記錄均不大（?。┯谒?，返回low值void qsort(int *l,int low,int high); 交換順序表中l(wèi)low.high的記錄，使樞軸記錄到位，并返回請其所在位置，此時在它之前（后）的記錄均不大（?。┯谒黺oid qsort(int *l,int low,int high) 對順序表l中的子序列l(wèi)low.hing作快速排序 （2）希爾排序函數(shù)void ShellInsert(int *L,int dk); 對順序表做一趟希爾排序void ShellSort(int *L, int dlta, int t); 按增量序列dlta0.t-1對順序表l做希爾排序（3）錦標(biāo)

3、賽排序函數(shù)void UpdateTree(int *tree, int *active, int pos); 建立具有最大根的樹void TournamentSort(int *array, int length); 對array進(jìn)行錦標(biāo)賽排序（4）堆排序函數(shù)void HeapAdjust(int h, int s, int m); 已知hs.m中記錄的關(guān)鍵字除hs之外均滿足堆的定義，本函數(shù)調(diào)整hs的關(guān)鍵字，使hs.m成為一個大頂堆void heapsort(int h);對順序表h進(jìn)行堆排序 （5）歸并排序void Merge(int array, int first, int mid, i

4、nt last); 將有序表的SRi.m和SRm+1.n歸并為有序的TRi.n void _MergeSort(int *array, int first, int last); 將SRs.t歸并排序為TR1s.tvoid MergeSort(int *array, int length); 對順序表l進(jìn)行排序2、        模塊調(diào)用圖：main()void qsort(int *l,int low,int high)void ShellSort(int *L, int dlta, int t);void Tournam

5、entSort(int *array, int length)void heapsort(int h)void MergeSort(int *array, int length)int partions(int l,int low,int high);void ShellInsert(int *L,int dk)void UpdateTree(int *tree, int *active, int pos)void HeapAdjust(int h, int s, int m)void Merge(int array, int first, int mid, int last)void _Me

6、rgeSort(int *array, int first, int last)                   二，基數(shù)排序（1）本實驗用到了鏈表結(jié)構(gòu)類型。typedef struct /靜態(tài)鏈表的結(jié)點類型long keysMAX_NUM_OF_KEY;long key0;int next;SLCell;typedef struct /靜態(tài)鏈表類型SLCell *r;int keynum;long recnum

7、;SLList;(2)實驗基本操作：void CreatList_Sq(SLList &L,long k,long *a,long *b) 構(gòu)造一個的靜態(tài)鏈表。void RadixSort(SLList &L) L是采用靜態(tài)鏈表表示的順序表對L作基數(shù)排序，使得L成為按關(guān)鍵字自小到大的有序靜態(tài)鏈表，L.r0為頭結(jié)點void Distribute(SLCell *r,int i,ArrType &f,ArrType &e) 靜態(tài)鏈表L的r域中記錄已按(key0,.,keyi-1)有序，本算法按第i個關(guān)鍵字keyi建立RADIX個子表，使同一子表中記錄的keysi相同

8、，f0.RADIX-1和e0.RADIX-1分別指向各子表中第一個和最后一個記錄void Collect(SLCell *r,int i,ArrType &f,ArrType &e) 本算法按keysi自小而大地將f0.RADIX-1所指各子表依次連接成一個鏈表，e0.RADIX為各子表的尾指針（3）模塊調(diào)用分析：main()void CreatList_Sq(SLList &L,long k,long *a,long *b)void RadixSort(SLList &L)void Distribute(SLCell *r,int i,ArrType &

9、;f,ArrType &e)void Collect(SLCell *r,int i,ArrType &f,ArrType &e) (四) 程序使用說明及測試結(jié)果1   程序使用說明（1）         本程序的運行環(huán)境為VC6.0。（2）         進(jìn)入演示程序后即顯示提示信息：先選擇排序類型（前五種排序在第一個程序里輸入相應(yīng)的數(shù)字，基數(shù)排序直接進(jìn)入第二個程序） ，再輸入文件名，如：

10、data01.txt，待文件排序完成后，輸入輸出的文件名，這樣排序后的數(shù)據(jù)就存儲在輸出文件中。在進(jìn)行希爾排序時，在輸入文件名后，還得根據(jù)提示輸入你想要排序的趟數(shù)，以及每趟排序的增量。運行界面：3   調(diào)試中的錯誤及解決辦法。(遇到時給出) 調(diào)試過程中，遇到了許多的問題，如：一開始直接用靜態(tài)數(shù)組作為存儲結(jié)構(gòu)，結(jié)果在文件較大時，由于存儲空間過小，系統(tǒng)崩潰。在同其他同學(xué)討論后，我改用指針動態(tài)分配數(shù)組的存儲空間。還有，在寫錦標(biāo)賽排序時，由于教材沒有直接給出算法，導(dǎo)致我花了相當(dāng)長的時間來思考和調(diào)試該算法。 （五）、實驗總結(jié)(實驗心得)你在編程過程中花時多少？零散的時間全部加上，大概有15-6個小時。多少時間在紙上設(shè)計？大概兩個多小時。多少時間上機(jī)輸入和調(diào)試？13到14個小時。多少時間在思考問題？不知道，一兩個吧。遇到了哪些難題？調(diào)試過程中，遇到了許多的問題，如：一開始直接用靜態(tài)數(shù)組作為存儲結(jié)構(gòu)，結(jié)果在文件較大時，由于存儲空間過小