信息工程學(xué)院50124

1、信息工程學(xué)院信息管理與信息系統(tǒng)專業(yè)09級(jí)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書信息工程學(xué)院2012-12數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書設(shè)計(jì)題目排序綜合技術(shù)參數(shù)設(shè)計(jì)要求利用隨機(jī)函數(shù)或人工輸入產(chǎn)生N個(gè)隨機(jī)整數(shù)（20000以上），對(duì)這些數(shù)進(jìn)行多種方法進(jìn)行排序。要求：至少采用三種方法實(shí)現(xiàn)上述問題求解（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的結(jié)果保存在不同的文件中。設(shè)計(jì)內(nèi)容設(shè)計(jì)步驟1、 結(jié)點(diǎn)結(jié)構(gòu)的設(shè)計(jì)2、 算法設(shè)計(jì)與分析3、 程序設(shè)計(jì)、實(shí)現(xiàn)、調(diào)試4、 課程設(shè)計(jì)說明書設(shè)計(jì)計(jì)劃進(jìn)度安排1、 設(shè)計(jì)工作1周2、 實(shí)現(xiàn)與調(diào)試1周設(shè)計(jì)考核1、 課程設(shè)計(jì)說明書50%2、 結(jié)果正確

2、50%3、 以上設(shè)計(jì)符合課程設(shè)計(jì)教學(xué)大綱，可獲的2學(xué)分。 附件：課程設(shè)計(jì)模版數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)Course Design of Data Structure院系：信息工程學(xué)院專業(yè)：信息管理與信息系統(tǒng)姓名：xxxxx學(xué)號(hào)：xxxxx指導(dǎo)老師：xxxxx完成時(shí)間：2012年 12月 30日目 錄1需求分析說明2概要設(shè)計(jì)說明3詳細(xì)設(shè)計(jì)代碼4調(diào)試分析5測(cè)試結(jié)果 排序計(jì)算器平面設(shè)計(jì)圖需求分析說明內(nèi)部排序教學(xué)軟件的總體功能要求：內(nèi)部排序的總體目標(biāo)：在VC+ 的開發(fā)環(huán)境下，利用所學(xué)C+語言和數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識(shí)，開發(fā)一個(gè)具有良好人機(jī)界面的內(nèi)部排序教學(xué)軟件，實(shí)現(xiàn)各種內(nèi)部排序，并能使用戶通過其顯示結(jié)果對(duì)每種排序方法

3、的性能有一個(gè)直觀的了解，從而達(dá)到教學(xué)的目的。基本功能如下：（1）界面友好，易與操作。采用菜單或其它人機(jī)對(duì)話方式進(jìn)行選擇。（2）實(shí)現(xiàn)各種內(nèi)部排序。包括冒泡排序，直接插入排序，直接選擇排序，希爾排序，快速排序，堆排序。（3）待排序的元素的關(guān)鍵字為整數(shù)?？捎秒S機(jī)數(shù)據(jù)和用戶輸入數(shù)據(jù)作測(cè)試比較。比較的指標(biāo)為有關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字的移動(dòng)次數(shù)。（4）演示程序以人機(jī)對(duì)話的形式進(jìn)行。每次測(cè)試完畢顯示各種比較指標(biāo)的列表，以便比較各種排序的優(yōu)劣。模塊調(diào)用圖：主模塊圖形界面子模塊排序功能及輸出子模塊封面和結(jié)束畫面子模塊輸入子模塊鼠標(biāo)現(xiàn)模塊 2概要設(shè)計(jì)說明    

4、0;            軟件的概要設(shè)計(jì)又稱為軟件系統(tǒng)（程序系統(tǒng)）的設(shè)計(jì)，本文件應(yīng)說明軟件系統(tǒng)即程序系統(tǒng)設(shè)計(jì)的總體考慮，包括系統(tǒng)的基本處理流程、軟件 系統(tǒng)的組織結(jié)構(gòu)、模塊劃分、功能分配、數(shù)據(jù)結(jié)構(gòu)、接口、運(yùn)行、    出錯(cuò)處理和系統(tǒng)維護(hù)等方面的設(shè)計(jì)，為詳細(xì)設(shè)計(jì)提供基礎(chǔ)。           引言     &#

5、160; 1.1      編寫目的                 說明編寫本設(shè)計(jì)說明書的目的，指出預(yù)期的讀者。       1.2      背景         &

6、#160;       a.    說明待開發(fā)軟件系統(tǒng)的名稱。                 b.    列出開發(fā)此軟件系統(tǒng)的提出者、開發(fā)者、和用戶。       1.3     

7、; 基線                 說明本系統(tǒng)設(shè)計(jì)的設(shè)計(jì)基線。       1.4      范圍                 說明本設(shè)計(jì)說

8、明書所涉及的設(shè)計(jì)內(nèi)容范圍。       1.5      定義             列出本設(shè)計(jì)說明書中用到的專門術(shù)語和外文字母組詞的原詞組。       1.6      參考資料     

9、60;           a.    屬于項(xiàng)目的其他已發(fā)表的文件；                 b.    本設(shè)計(jì)說明書中引用到的文件、資料，包括所用到的軟件開發(fā)標(biāo)準(zhǔn)。       &

10、#160; 列出這些文件資料的標(biāo)題、編號(hào)、發(fā)表日期、出版單位和查找來源。       2      總體設(shè)計(jì)           2.1      概述       2.1.1      需

11、求規(guī)定                 說明本系統(tǒng)主要的輸入、處理、輸出的功能和性能要求等。         2.2.2      運(yùn)行環(huán)境              &

12、#160;  說明本系統(tǒng)運(yùn)行的硬件環(huán)境和支持環(huán)境。       2.2      設(shè)計(jì)       2.2.1      設(shè)計(jì)構(gòu)思                  &#

13、160;說明對(duì)本系統(tǒng)設(shè)計(jì)的構(gòu)思、采用的關(guān)鍵技術(shù)、主要算法和關(guān)鍵數(shù)據(jù)結(jié)構(gòu)。       2.2.2      系統(tǒng)流程       a.    用流程圖示出本系統(tǒng)的主要控制流程和處理流程；                 

14、b.    用流程圖示出本系統(tǒng)主要的數(shù)據(jù)通路，并說明處理的主要階段。       2.2.3      結(jié)構(gòu)設(shè)計(jì)                 a.    系統(tǒng)元素       

15、          確定本系統(tǒng)的元素及其功能，用一覽表說明本系統(tǒng)的系統(tǒng)元素（各層模塊、子程序、公用程序等）的劃分，按層次給出它們的標(biāo)識(shí)符和功能。                 b.    系統(tǒng)層次結(jié)構(gòu)         

16、        用框圖分層次地給出各個(gè)系統(tǒng)元素之間的控制和被控制的關(guān)系。       2.2.4      功能需求與程序的關(guān)系                 用功能需求與程序的矩陣圖表形式    

17、，示出各項(xiàng)功能的實(shí)現(xiàn)與各系統(tǒng)元素之間的分配關(guān)系。       3      系統(tǒng)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)       3.1      數(shù)據(jù)結(jié)構(gòu)                 列出本系統(tǒng)所使用的主要數(shù)據(jù)結(jié)構(gòu)，包

18、括名稱、標(biāo)識(shí)符及數(shù)據(jù)項(xiàng)等。       3.2      數(shù)據(jù)結(jié)構(gòu)與系統(tǒng)元素之間的關(guān)系                           用數(shù)據(jù)結(jié)構(gòu)與系統(tǒng)元素之間的矩陣圖表形式，示出各個(gè)數(shù)據(jù)結(jié)構(gòu)與訪問這些數(shù)據(jù)結(jié)構(gòu)的系統(tǒng)

19、元素之間的關(guān)系。       4接口設(shè)計(jì)       4.1      用戶接口                 說明本系統(tǒng)向用戶提供的命令、語法結(jié)構(gòu)及系統(tǒng)回答信息等。       4.2 

20、     外部接口       說明本系統(tǒng)的軟件同硬件和支持軟件之間的接口。       4.3      內(nèi)部接口             說明本系統(tǒng)內(nèi)部相關(guān)模塊之間的接口。      &

21、#160;5      運(yùn)行設(shè)計(jì)       5.1      系統(tǒng)初始化                 說明本系統(tǒng)初始化過程。           

22、;      5.2      運(yùn)行模塊組合                 說明本系統(tǒng)每項(xiàng)外界運(yùn)行需經(jīng)過哪些內(nèi)部模塊的組合和支持軟件。             5.3   

23、60;  運(yùn)行控制                 說明每項(xiàng)外界運(yùn)行的控制方式、方法和操作步驟。             5.4      運(yùn)行時(shí)間        

24、60;        說明每項(xiàng)運(yùn)行模塊組合預(yù)計(jì)占用各種資源的時(shí)間。             5.5      運(yùn)行安全                 說明系統(tǒng)安全運(yùn)行的控制。&#

25、160;            6      信息結(jié)構(gòu)設(shè)計(jì)（當(dāng)有相關(guān)需求或軟件規(guī)格定義有要求時(shí)）           按邏輯結(jié)構(gòu)和物理結(jié)構(gòu)給出本軟件有關(guān)信息的設(shè)計(jì)要點(diǎn)。       6.1      邏輯結(jié)構(gòu)設(shè)

26、計(jì)       6.1.1      圖形設(shè)計(jì)           6.1.2      中文（包括單個(gè)漢字、短語、詞組。）設(shè)計(jì)       6.2      物理結(jié)構(gòu)設(shè)計(jì)  &#

27、160;    6.2.1      圖形設(shè)計(jì)       6.2.2      中文（包括單個(gè)漢字、短語、詞組。）設(shè)計(jì)       6.3      信息結(jié)構(gòu)與程序的關(guān)系         

28、    用信息結(jié)構(gòu)與系統(tǒng)元素之間的矩陣圖表形式，示出各個(gè)信息結(jié)構(gòu)與訪問這些信息結(jié)構(gòu)的系統(tǒng)元素之間的關(guān)系。             7出錯(cuò)處理和維護(hù)       7.1      出錯(cuò)信息            

29、     用一覽表列出本系統(tǒng)各種可能出錯(cuò)或故障的信息形式及其含義。       7.2      補(bǔ)救措施                 說明系統(tǒng)故障出現(xiàn)后可能采取的變通措施，包括：       a.

30、0;   后備技術(shù)當(dāng)系統(tǒng)原始數(shù)據(jù)一旦丟失時(shí)，啟用副本的建立和啟動(dòng)技術(shù)；             b.    降效技術(shù)使用另一效率稍低的方法以求得所需結(jié)果的某些部份，如手工操作和人工記錄數(shù)據(jù)；             c.    恢復(fù)及再啟動(dòng)技術(shù)讓系統(tǒng)

31、從故障點(diǎn)恢復(fù)執(zhí)行或系統(tǒng)從新啟動(dòng)運(yùn)行的方法等。           7.3      系統(tǒng)維護(hù)                 說明專門安排用于系統(tǒng)檢測(cè)與維護(hù)的檢測(cè)點(diǎn)和系統(tǒng)檢測(cè)維護(hù)的專用模塊等。3.詳細(xì)設(shè)計(jì)代碼 (1)希爾排序代碼void ShellInsert(int array

32、,long dk,long n) int sentinel; /哨兵 for(long i=dk;i<n;i+) if(arrayi<arrayi-dk) sentinel=arrayi; for(long j=i-dk;(j>=0)&&(sentinel<arrayj);j-=dk) arrayj+dk=arrayj; arrayj+dk=sentinel; / return;void ShellSort(int array,long n,long t) /for(int i=0;i<t;i+)cout<<dltai<<&

33、quot; "cout<<endl; long *dlta=new longt; if(t>0)dlta0=1; long temp=1; for(long i=1;i<t;i+) dltai=temp+1; temp*=2; for(i=t-1;i>=0;i-) ShellInsert(array,dltai,n); /dlta=.9,5,3,2,1也可以預(yù)先用一數(shù)組存放好這個(gè)數(shù)列! delete dlta; return;（2）選擇排序代碼#include<iostream> using namespace std; int main()

34、 int num10 = 9,8,10,3,4,6,4,7,2,1; cout<<"排序前："<<endl; for (int m = 0;m < 10;m+) cout<<numm<<" " for (int i = 0;i < 9;i+) int pos = i; for (int j = i+1;j < 10;j+) if (numpos > numj) pos = j; int tem; tem = numpos; numpos = numi; numi = tem; cou

35、t<<endl<<"排序后："<<endl; for (int m = 0;m < 10;m+) cout<<numm<<" " return 0; （3）快速排序代碼#include <cstdio>#include <cstdlib>#include <cstring>#include <iostream>using namespace std;int n,a100000;void Init() scanf("%d",

36、&n); for(int i=0;i!=n;+i) scanf("%d",&ai);void Qsort(int l,int r) int i,j,mid,t; i=l; j=r; mid=a(i+j)>>1;/選擇中間元素作為基準(zhǔn) while(i<=j) while(ai<mid) +i;/找到一個(gè)在mid左邊且不小于mid的元素 while(aj>mid) -j;/找到一個(gè)在mid右邊且不大于mid的元素 if(i<=j) swap(ai,aj);/交換 +i; -j; if(i<r) Qsort(i,r);/遞

37、歸 if(l<j) Qsort(l,j);/遞歸 void Print() for(int i=0;i!=n;+i) printf("%d ",ai);int main() Init();/讀入 Qsort(0,n-1);/快速排序 Print();/輸出 return 0;（4）直接排序代碼#include<iostream> using namespace std; #define NUM 10 void DirectInsert(int *list,int n) int i; int j； int x;for (i=1;i<n;i+) x =

38、listi; for (j=i-1;j>=0;j-) if (listj>x) listj+1 = listj; else break; listj+1 = x; void Print(int *list,int n) int i; for (i=0;i<5;i+) cout << listi << "," cout << endl; int main() int arrNUM; int i; srand(1); /初始化隨機(jī)數(shù)發(fā)生器 for(i=0;i<NUM;i+) arri=rand()%100;/隨機(jī)數(shù)在0

39、到99范圍內(nèi) cout << "before sorting :" << endl; Print(arr,sizeof(arr)/sizeof(int); DirectInsert(arr,sizeof(arr)/sizeof(int); cout << "after sorting :" << endl; Print(arr,sizeof(arr)/sizeof(int); return 0; （5）冒泡排序代碼#include<iostream>void sort(int array,int

40、 n)using namespace std;int i,j,min=0;for(j=0;j<n-1;j+)for(i=0;i<n-1-j;i+)if(arrayi>arrayi+1)min=arrayi;arrayi=arrayi+1;arrayi+1=min;for(i=0;i<n;i+)cout<<arrayi<<" " if(i=n-1) cout<<"n"void main()using namespace std;cout<<"Please input the

41、number of Numbers(輸入數(shù)字的個(gè)數(shù)): "int n;cin>>n;cout<<"Enter the array(輸入數(shù)據(jù)): "int array100,i;for(i=0;i<n;i+)cin>>arrayi;sort(array,n);（4）調(diào)試分析 語法錯(cuò)誤 ：    請(qǐng)檢查是否缺少了分號(hào)（行結(jié)束符），if、else是否匹配、switch 語句用法是否對(duì)等。注意，宏定義、包含文件定義結(jié)束不需分號(hào)，而類定義結(jié)束需要分號(hào)。     變量、函數(shù)未定義、重定義：     請(qǐng)檢查變量大小寫、是否包含了相應(yīng)的頭文件（包括你自己的和 MFC、Windows 的）。     連接錯(cuò)誤：    這種錯(cuò)誤一般發(fā)生在你的程序中使用了動(dòng)態(tài)連結(jié)庫(dll)的時(shí)候（不管是你的還是Windows本身的）。此時(shí)，可以察看是哪個(gè)函數(shù)出錯(cuò)。比如你調(diào)用了一個(gè) Windows API，而MSDN中的說明寫到這個(gè)函數(shù)需要包含哪個(gè)頭文件(.h)、輸入哪個(gè)庫(.lib)，那么就要在你的工程