1、課 程 設 計學生姓名： 學 號： 專業班級： 課程名稱： 數據結構 學年學期： 20152016學年第2學期 指導教師： 白云飛 2016年6月數據結構課程設計成績評定表學生姓名學 號成績專業班級起止時間2016-6-202016-6-24設計題目指導教師評語學習態度出勤情況： 好 較好 一般 較差 課 題 工 作 量： 飽滿 較大 合理 較小 綜合運用知識能力： 好 較好 一般 較差 方 案 設 計 情況： 合理 較合理 基本合理 不合理 課題結果分析能力： 強 較強 一般 較差 設 計 實 現 情況： 全部 大部分 部分 未實現 設 計 報 告 內容： 詳細 完整 較完整 不完整 設計報

2、告文檔格式： 規范 較規范 基本規范 不規范 獨 立 動 手 能力： 強 較強 一般 較差 指導教師： 年 月 日目 錄1需求分析說明-12概要設計說明-33詳細設計說明-54調試分析-75用戶使用說明-86課程設計總結-117測試結果-128參考書目-1417數 據 結 構 課 程 設 計1 需求分析說明內部排序教學軟件的總體功能要求：內部排序教學軟件的總體目標：在TURBO C2.0 的開發環境下，利用所學C語言和數據結構的相關知識，開發一個具有良好人機界面的內部排序教學軟件，實現各種內部排序，并能使用戶通過其顯示結果對每種排序方法的性能有一個直觀的了解，從而達到教學的目的。基本功能如下：

3、（1）界面友好，易與操作。采用菜單或其它人機對話方式進行選擇。（2）實現各種內部排序。包括冒泡排序，直接插入排序，直接選擇排序，希爾排序，快速排序，堆排序。（3）待排序的元素的關鍵字為整數。可用隨機數據和用戶輸入數據作測試比較。比較的指標為有關鍵字參加的比較次數和關鍵字的移動次數(關鍵字交換以3次計)。（4）演示程序以人機對話的形式進行。每次測試完畢顯示各種比較指標的列表，以便比較各種排序的優劣。以下是各功能模塊的功能描述：1主函數模塊本模塊的主要功能是初始化圖形界面，調用各模塊，實現軟件功能。2排序功能及輸出子模塊本模塊的主要功能是根據用戶的選擇進行數組的創建，并對輸入數據或者隨機產生的數據

4、使用六種排序方法進行排序并統計每種方法的移動次數和比較次數，然后輸出以表格形式輸出。3封面和結束畫面子模塊本模塊的主要功能是當用戶打開本軟件時模擬軟件加載，延時數秒后關閉，并進入圖形界面，在用戶退出軟件時顯示結束畫面，延時數秒后關閉程序。4圖形界面子模塊本模塊的主要功能是根據用戶的選擇顯示不同的畫面，引導用戶使用軟件所提供的各種功能，并在用戶提供必要數據，并選擇排序功能時調用排序模塊，并顯示結果畫面。5輸入子模塊本模塊的主要功能是進行光標定位，輸出提示文字，并對用戶輸入數據進行處理，創建數組。6.鼠標實現模塊本模塊的主要功能是為用戶提供鼠標操作支持，使用戶能使用鼠標進行功能的選擇。測試數據：1

5、：隨機數若干組2：升序數組1，2，3，4，5，6，7，8，9，103：降序數組9，8，7，6，5，4，3，2，1，02 概要設計說明模塊調用圖：主模塊圖形界面子模塊排序功能及輸出子模塊封面和結束畫面子模塊輸入子模塊鼠標實現模塊 可排序表的抽象數據類型定義為：ADT Orderablelist 數據對象：D=Ai | Ai Integer,i=1,2,n, n=0數據關系：R=|Ai-1,AiD,i=1,2,n基本操作：#define MAXSIZE 200/*數組最大長度*/int MOV_CNT; /*移動次數*/int CMP_CNT; /*比較次數*/void Exchange( int

6、 num, int i, int j ) /*交換數組元素i,j*/void ShellSort( int num, int n ) /*希爾排序*/void QuickSort(int p,int c,int d)/*快速排序*/void SIFT( int num, int s, int n ) /*調整建堆函數*/void HeapSort( int num, int n )/*堆排序*/void ChooseSort( int num, int n )/*選擇排序*/void BubbleSort( int num, int n )/*冒泡排序*/void Insertsort( in

7、t num,int n )/*插入排序*/void Sort( int array, int n ) /*調用六種排序方法并輸出移動次數和比較次數*/void CreatRan( int array, int n ) /*建立隨機數組*/void CreatUp( int array, int n )/* 建立升序數組*/void CreatDown( int array, int n ) /*建立降序數組*/int InputLen()/*輸入數組長度 */void InputArray( int array, int n ) /*建立人工輸入的數組*/void Locate( int ro

8、w, int col ) /* 光標定位*/void MouseMath()/*計算鼠標的樣子*/void MouseOn( int x, int y ) /*鼠標光標顯示*/void MouseSetX( int lx, int rx ) /*設置鼠標左右邊界*/ void MouseSetY( int uy, int dy ) /*設置鼠標上下邊界*/void MouseSetXY(int x,int y) /*設置鼠標當前位置*/int MouseStatus( int *x, int *y, int *state )/*鼠標坐標及按鍵情況*/int StartScreen()/*開始界

9、面的進度條*/int MainWin( int x1, int y1, int x2, int y2 )/*主窗口*/int CloseButton( int y1, int x2, int close )/*關閉按鈕*/void Button( int buttonx1, int buttony1, int buttonx2, int buttony2, char *name, int state )/*功能按鈕*/void Clear()/*清屏*/void Screen( int sn )/*界面*/void CloseScreen()/*結束畫面*/int Mouse()/*鼠標事件處

10、理*/int Run( int bn, int sn )/*功能調用*/3 詳細設計說明1 主函數模塊首先調用initgraph函數進行圖形驅動的初始化，然后調用StartScreen函數顯示進度條，模擬軟件加載，然后調用Mouse函數，再調用closegraph函數關閉圖形模式。2 排序功能及輸出子模塊在實現排序功能時，每調用一種排序方法前首先應該把原始數組array復制到num，把移動次數MOV_CNT和比較次數CMP_CNT置零，然后對num進行一種排序，同時進行記數，最后進行光標定位，輸出次數。這樣進行六次，就可以把六種排序方法的移動次數和比較次數統計出來。再這里，光標的定位是利用軟中

11、斷方式實現的，這樣做可以直接利用scanf和printf進行輸入輸出，而不必進行數字和字符串之間的轉化。3 封面和結束畫面子模塊是否初始化鼠標畫主窗口畫界面0讀取鼠標狀態是否在非按鈕區域是否在關閉按鈕上顯示結束畫面結束開始是軟件的封面是一個模擬軟件加載的一個進度條。其設計思路是，先利用bar函數畫出一個淺藍色的矩形條，然后進行光標定位，輸出“Loading”字符串，然后將分十段將矩形條用藍色填充，同時在字符串同一行的右邊幾個字符的距離輸出百分數。由于輸出的是利用字符函數，而非圖形函數，字符的背景色會覆蓋上一次的數字，造成百分數不斷增加，進度條不斷前進的動畫效果。4 圖形界面子模塊這個模塊是軟件

12、最為復雜，開發時間最長，修改次數最多的一個模塊。這個界面主要是仿照傳統的WINDOWS界面。主窗口是由四部分組成，藍色的屏幕背景、灰色的窗體、藍色的標題欄和關閉按鈕。窗口和按鈕的突起效果是現在屏幕上畫一淺色形狀，再將縱橫坐標增加一兩點，畫深色形狀，從而造成突起效果。為了體現動畫的效果，按鈕分三種狀態，突起狀態，平面狀態和凹陷狀態。凹陷效果可由深色形狀在淺色形狀的大小基礎上縮小一兩個像素點得到。一個界面包括提示文字和功能按鈕。軟件一共有6個界面，其中界面0是用戶一開始看到的界面，界面1，2，3，4分別對應于功能按鈕1，2，3，4，界面5是顯示結果的界面。 這個模塊的關鍵在于鼠標控制。鼠標狀態st

13、ate為0時，沒有鼠標鍵按下，為1時鼠標左鍵被按下。鼠標在哪個按鈕上是利用鼠標的坐標值是是否在功能按鈕區域是判斷界面號判斷按鈕號產生按鈕下陷效果否在按鈕的坐標范圍內進行判斷的。判斷用戶是否選擇了某一功能是利用鼠標在哪個按鈕上同時state=1進行判斷的。當鼠標在非按鈕區域按下左鍵時程序會直接進入下一個循環。界面0的四個功能按鈕名為：“Random”,”OrderUp”,”OrderDn”,”Input”,代表產生數組的四種方式隨機、升序、降序、人工輸入。界面1，2，3，4的兩個功能按鈕名為：”Input”,”Static”, 代表確定數組長度的方式人工輸入、默認。界面5包含一個“Restart

14、”按鈕，用來返回到界面0。是讀取鼠標狀態判斷鼠標左鍵是否按下調用Run函數圖2：Mouse()的流程圖否5 輸入子模塊當選擇好功能以后，分4種情況，隨機數組、升序數組、降序數組、人工輸入的數組。長度分兩種，Input是先進行光標定位，然后輸出提示文字，當用戶輸入長度后，把值賦給n，而Static是直接把10賦給n。6 鼠標實現模塊 軟件的鼠標最初使用的系統自帶的樣式，通過BIOS中斷INT 33H實現。可以 4 調試分析我遇到的問題：l 同一數組排序六次由于要對同一數組排序六次，必須在排序前先將數組保存起來，每次排序只對數組副本進行操作。l 鼠標在WIN2000，XP下不能正常顯示鼠標使用軟中

15、斷方式在WIN98下能正常工作，但是更高版本如WIN2000，XP下都不能顯示鼠標，即鼠標處于隱形狀態。經過思考和查找資料,我決定用自已畫一個鼠標指針形狀,并根據中斷提供的坐標值繪制在屏幕的相應坐標上。當鼠標移動時，先將原始位置的鼠標消去，然后在新的位置繪制出指針形狀。l 屏幕和按鈕不停閃爍經過檢查，發現是屏幕重繪頻率過快引起的，在每次繪圖以后加上一定延時，在有意識的控制循環的頻率即可解決。l 圖形界面下輸入數據圖形界面下的輸入一般為字符串，為了不進行數字和字符串之間的轉化，我利用了中斷定位光標，直接利用scanf進行輸入。l 在程序顯示結果后無法返回界面0在結果界面上增加一個按鈕Restar

16、t，利用goto語句即可返回到界面0。5 用戶使用說明用戶打開軟件后，首先見到的是進度條屏幕，如圖3所示，隨后進入了如圖4所示的界面0。圖3圖4界面0的四個功能按鈕名為：“Random”,”OrderUp”,”OrderDn”,”Input”,代表產生數組的四種方式隨機、升序、降序、人工輸入。點選任意一個功能按鈕，將會進入如圖5所示界面。Input按鈕是人工輸入數組長度，Static按鈕是使用默認長度10。當用戶點選Input按鈕時，進入輸入長度的界面。當用戶點選Static按鈕時，進入界面5或輸入數據界面然后進入界面5。圖5圖6 輸入長度界面圖7 輸入數組元素界面用戶在看到輸入長度界面界面后

17、，即可使用鍵盤輸入長度，但要求長度不超過200，按回車鍵確認。同理，用戶在看到輸入數組元素界面后，即可輸入元素，元素之間用空格隔開。最后是結果界面。點擊Restart按鈕可回到界面0。點擊關閉按鈕即可退出。圖8 結果界面6 課程設計總結通過這次數據結構課程設計，使我對軟件的界面設計有了一個比較深刻的了解，對各種內部排序方法的性能有了清晰的認識，使我感覺到到，一個優秀的軟件，不僅僅是可以運行的，更應該具有人性化的界面，協調的布局，合理的結構，良好的性能和一定的容錯性。一個人要完成所有的工作是非常困難和耗時的。在以后的學習中我會更加注意各個方面的能力的協調發展，選擇一兩門技術進行深入研究，成為一個

18、既可以統籌全局，又有一定技術專長的優秀的程序開發人員。7 測試結果下面對幾組數據進行測試。數組： 19，65，85，79，62，33，55，44，77，11排序方法移動次數比較次數堆排序2713冒泡排序13545插入排序189快速排序2745選擇排序279希爾排序3618數組：8，84，86，21，32，54，65，98，75 排序方法移動次數比較次數堆排序2411冒泡排序10836插入排序168快速排序2436選擇排序248希爾排序3216數組：1，2，3，4，5，6，7，8，9排序方法移動次數比較次數堆排序6037冒泡排序036插入排序168快速排序2436選擇排序248希爾排序3218數組： 9，8，7，6，5，4，3，2，1，0排序方法移動次數比較次數堆排序5131冒泡排序13545插入排序6354快速排序2745選擇排序279希爾排序6345對六種排序的性能分析：測試冒泡排序插入排序選擇