《資料結構》
課程設計報告
專業電腦科學與技術
班級 (1)
姓名王昕
學號 20101308003
指導教師顧韻華
起止時間 2011.10~2011.12
課程設計：排序綜合
一、任務描述
（1）至少採用三種方法實現上述問題求解（提示，可採用的方法有插入排序、希爾排序、氣泡排序、快速排序、選擇排序、堆排序、歸併排序）。並把排序後的結果儲存在不同的檔案中。
（2）統計每一種排序方法的效能（以上機執行程式所花費的時間為準進行對比），找出其中兩種較快的方法。
二、問題分析
1、功能分析
分析設計課題的要求，要求程式設計實現以下功能：
（1）顯示隨機數：呼叫dip()函式輸出陣列a。陣列a中儲存有隨機產生的隨機數。
（2）直接選擇排序：通過n-i次關鍵字間的比較，從n-i+1個記錄中選出關鍵字最小的記錄，並和第i個記錄交換之。
（3）氣泡排序：如果有n個數，則要進行n-1趟比較。在第1趟比較中要進行n-1次兩兩比較，在第j趟比較中要進行n-j次兩兩比較。
（4）希爾排序：先將整個待排記錄序列分割成為若干子串行分別進行直接插入排序，待整個序列中的記錄「基本有序」時，再對全體記錄進行一次直接插入排序。
（5）直接插入排序：將乙個記錄插入到已排序好的有序表中，從而得到乙個新的、記錄數增1的有序表。設整個排序有n個數，則進行n-1趟插入，即：
先將序列中的第1個記錄看成是乙個有序的子串行，然後從第2個記錄起逐個進行插入，直至整個序列變成按關鍵字非遞減有序列為止。
（6）顯示各排序演算法排序後的的資料和時間效率，並比較找出其中2種較快的方法。
2、資料物件分析
排序方式：直接選擇排序、氣泡排序、希爾排序、直接插入排序
顯示排序後的的資料和時間效率。
三、資料結構設計
1.主要全程變數及資料結構
資料結構：
typedef struct
keytype key;
infotype otherinfo;
}redtype;
typedef struct
sqlist;
2.演算法的入口引數及說明
#include
#define maxsize 20
#define lt(a,b) ((a)<(b)) //巨集定義
typedef int keytype; //定義關鍵字keytype為int
typedef int infotype; //定義關鍵字infotype為int
typedef structredtype;
typedef structsqlist;
四、功能設計
（一）主控選單設計
為實現排序的操作功能，首先設計乙個含有多個選單項的主控選單程式，然後再為這些選單項配上相應的功能。
程式執行後，給出11個選單項的內容和輸入提示，如下：
歡迎來到排序綜合系統！
選單(1)---直接插入排序
(2)---直接選擇排序
(3)---氣泡排序
(4)---快速排序
(5)---堆排序
(6)---時間效率比較
(7)---顯示隨機數
(0)---退出系統
請在上述序號中選擇乙個並輸入：
（二）程式模組結構
由課題要求可將程式劃分為以下幾個模組（即實現程式功能所需的函式）：
● 主控選單項選擇函式menu_select()
● 插入排序函式：insertsort()
● 選擇排序函式：selectsort()
● 氣泡排序函式：bubblesort()
● 堆排序函式：heapsort()
（三）函式呼叫關係
程式的主要結構（函式呼叫關係）如下圖所示
其中main()是主函式，它進行選單驅動，根據選擇項1~0呼叫相應的函式。
（四）函式實現
#include
#include
#include
#include
#include
#define n 30000
void wrong()
void disp(int a)
}void insertsort(int a,int p) //插入排序
}void selectsort(int a,int p) //選擇排序 }
}void bubblesort(int a,int p) /*氣泡排序演算法*/}}
void creatheap(int a,int i,int n) //建立堆
else
j=n+1;
}a[i]=t;
}void heapsort(int a,int n,int p堆排序
}void quicksort(int a,int n,int p)
st[n];
top++;
st[top].low=0;st[top].high=n-1;
while(top>-1)
low=st[top].low;high=st[top].high;
top--;
i=low;j=high;
if(lowtemp=a[low];
while(i!=j)
while(itemp)j--;
if(iwhile(iif(i
a[i]=temp;
top++;st[top].low=low;st[top].high=i-1;
top++;st[top].low=i+1;st[top].high=high;
}}double tinsertsort(int a,int p);
報告 資料結構綜合課程設計
寧波大紅鷹學院 資訊工程學院課程 設計報告 資訊工程學院制 目錄一 案例描述 一級標題標題四號黑體，段前斷後0.5行 1 1 總體描述 二級標題小四號宋體加粗 1 2 模組描述 1 二 設計思路 1 三 程式設計 2 1 資料結構描述 2 2 主函式及其流程圖 2 3 源程式 2 四 除錯與分析 2...
報告 資料結構綜合課程設計
寧波大紅鷹學院 資訊工程學院課程 設計報告 資訊工程學院制 目錄一 案例描述 一級標題標題四號黑體，段前斷後0.5行 1 1 總體描述 二級標題小四號宋體加粗 1 2 模組描述 1 二 設計思路 1 三 程式設計 2 1 資料結構描述 2 2 主函式及其流程圖 2 3 源程式 2 四 除錯與分析 2...
資料結構課程設計報告
交通諮詢系統設計 不用輸入程式語句，也不用那個截圖 不用太著急，報告周五之前給我就行了 列印和壓縮包都要哈！對了，這段文字記得刪掉啊嘿嘿 題目名稱交通諮詢系統設計 院 系 管理學院 課程名稱資料結構課程設計 班級資訊 10 2 學生姓名呂德麗 指導教師李長雲 目錄一 需求分析及選題要求 3 1 問題...