信息工程學院50124

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

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

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

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

5、160; 1.1      編寫目的                 說明編寫本設計說明書的目的，指出預期的讀者。       1.2      背景         &

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

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

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

9、60;           a.    屬于項目的其他已發(fā)表的文件；                 b.    本設計說明書中引用到的文件、資料，包括所用到的軟件開發(fā)標準。       &

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

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

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

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

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

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

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

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

18、括名稱、標識符及數(shù)據(jù)項等。       3.2      數(shù)據(jù)結構與系統(tǒng)元素之間的關系                           用數(shù)據(jù)結構與系統(tǒng)元素之間的矩陣圖表形式，示出各個數(shù)據(jù)結構與訪問這些數(shù)據(jù)結構的系統(tǒng)

19、元素之間的關系。       4接口設計       4.1      用戶接口                 說明本系統(tǒng)向用戶提供的命令、語法結構及系統(tǒng)回答信息等。       4.2 

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

21、#160;5      運行設計       5.1      系統(tǒng)初始化                 說明本系統(tǒng)初始化過程。           

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

23、60;  運行控制                 說明每項外界運行的控制方式、方法和操作步驟。             5.4      運行時間        

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

25、160;            6      信息結構設計（當有相關需求或軟件規(guī)格定義有要求時）           按邏輯結構和物理結構給出本軟件有關信息的設計要點。       6.1      邏輯結構設

26、計       6.1.1      圖形設計           6.1.2      中文（包括單個漢字、短語、詞組。）設計       6.2      物理結構設計  &#

27、160;    6.2.1      圖形設計       6.2.2      中文（包括單個漢字、短語、詞組。）設計       6.3      信息結構與程序的關系         

28、    用信息結構與系統(tǒng)元素之間的矩陣圖表形式，示出各個信息結構與訪問這些信息結構的系統(tǒng)元素之間的關系。             7出錯處理和維護       7.1      出錯信息            

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

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

31、從故障點恢復執(zhí)行或系統(tǒng)從新啟動運行的方法等。           7.3      系統(tǒng)維護                 說明專門安排用于系統(tǒng)檢測與維護的檢測點和系統(tǒng)檢測維護的專用模塊等。3.詳細設計代碼 (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也可以預先用一數(shù)組存放好這個數(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;/選擇中間元素作為基準 while(i<=j) while(ai<mid) +i;/找到一個在mid左邊且不小于mid的元素 while(aj>mid) -j;/找到一個在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); /初始化隨機數(shù)發(fā)生器 for(i=0;i<NUM;i+) arri=rand()%100;/隨機數(shù)在0

39、到99范圍內 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ù)字的個數(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）調試分析 語法錯誤 ：    請檢查是否缺少了分號（行結束符），if、else是否匹配、switch 語句用法是否對等。注意，宏定義、包含文件定義結束不需分號，而類定義結束需要分號。     變量、函數(shù)未定義、重定義：     請檢查變量大小寫、是否包含了相應的頭文件（包括你自己的和 MFC、Windows 的）。     連接錯誤：    這種錯誤一般發(fā)生在你的程序中使用了動態(tài)連結庫(dll)的時候（不管是你的還是Windows本身的）。此時，可以察看是哪個函數(shù)出錯。比如你調用了一個 Windows API，而MSDN中的說明寫到這個函數(shù)需要包含哪個頭文件(.h)、輸入哪個庫(.lib)，那么就要在你的工程