1、文檔來源為：從網絡收集整理.word版本可編輯.歡迎下載支持數據結構大作業專業：班級：題目學生姓名：課程設計報告撰寫的基本要求）題目（三號，黑體，居中）（空一行）一、任務與目標（標題均為小三號，宋體）（正文均為小四號，宋體，行距1.5倍）（這一部分需簡單介紹題目內容，即該題目到底要做什么。如果涉及明確的算法，最好再簡單介紹一下算法產生的背景，還要列出各項本設計要達到的具體的目標。）二、方案設計與論證（對目標進行總體分析，說明要采用的基本思路，說明遇到的問題和解決方法。說明完成本次課程設計的完整過程。要描述程序的設計思想，重點描述你自己提出的與已有工作不同的程序設計思想。）三、算法說明（這一部分

2、需詳細描述解決問題所需要用到的算法和重要的數據結構，即該課程設計到底應該怎么做。基本要求：處理問題中所用到的關鍵算法都要描述清楚，而不是僅描述主函數。算法和數據結構可用偽碼和圖示描述，不要只寫源代碼和注釋。這一部分的目的是讓讀者在短時間內清楚地理解作者解決問題的整體思路，表達方式必須比源代碼更通俗易懂。如果讀者感覺還不如直接讀源代碼來得明白，這一部分內容就失去了意義。）四、全部源程序清單（給出本次大作業所編寫全部源程序已經調試好的可運行代碼清單，字體可以用宋體五號，頁數可增加，每個程序開頭用注釋文字說明此程序的用途和大體工作過程，程序中必要部分也要加入足夠多的注釋行。）五、程序運行的測試與分析

3、（這一部分內容需要緊扣課程設計的題目類型和要求，設計提供相應的測試方法和結果。這部分包括運行圖。對于需要比較不同算法性能優劣的題目，應設計并填寫一張性能比較表格，列出不同算法在同一指標下的性能表現。僅僅羅列出一堆數據是不夠的，還應將數字轉化為圖形、曲線等方式.，幫助讀者更直觀地理解測試結果。對于需要利用某算法解決某問題的題目，應設計并填寫一張測試用例表。每個測試用例一般應包括下列內容： 測試輸入：設計一組輸入數據； 測試目的：設計該輸入的目的在于測試程序在哪方面可能存在漏洞； 正確輸出：對應該輸入，若程序正確，應該輸出的內容； 實際輸出：該數據輸入后，實際測試得到的輸出內容； 錯誤原因：如果實

4、際輸出與正確輸出不符，需分析產生錯誤的可能原因； 當前狀態：分為“通過”（實際輸出與正確輸出相符卜“已改正（實際輸出與正確輸出不符，但現在已修改正確）、“待修改”（實際輸出與正確輸出不符，且尚未改正）三種狀態。需要注意的是，測試員的態度，不是提供幾組簡單的數據讓程序員容易通過，從而宣稱該程序是正確的；而應該是千方百計設計“刁難”的數據，想辦法讓所測試的程序暴露出問題，這樣才能真正幫助程序員完成正確的程序，最后通過嚴格的裁判數據測試。）六、結論與心得（主要說明程序調試中發現的問題和解決辦法，包括你學到了什么，哪里遇到了困難，解決的辦法，可能但因時間關系沒有來得及完成的想法，今后的目標等。）七、參

5、考資料（用五號，宋體，按照規范格式列出。）（要列出在完成設計中查看過并有所利用的所有參考資料，包括各類技術書籍、期刊論文和相關網頁的網址。注意你看過但沒有利用的資料不要列入，要能夠回答你列出資料中的相關問題。）附錄：供選擇的數據結構大作業題目可選題目：1. 航空客運訂票系統錯誤！未定義書簽。2. 散列法的實驗研究錯誤！未定義書簽。3. 學生搭配問題錯誤！未定義書簽。4. 二叉排序樹的實現錯誤!未定義書簽。5. 利用棧求表達式的值錯誤！未定義書簽。6. 走迷宮游戲錯誤!未定義書簽。7. 順序結構、動態鏈表結構下的一元多項式的加法、減法、乘法的實現。錯誤味定義書簽。8.線索二叉樹的應用錯誤！未定義

6、書簽。9. 稀疏矩陣實現與應用錯誤！未定義書簽。10. 樹的應用錯誤！未定義書簽。11. 圖的遍歷和生成樹求解實現錯誤！未定義書簽。12. 排序綜合錯誤！未定義書簽。13. 紙牌游戲錯誤！未定義書簽。14. 利用棧求表達式的值，可供小學生作業，并能給出分數。錯誤！未定義書簽。15. 數制轉換問題錯誤！未定義書簽。16. 停車場問題錯誤！未定義書簽。17. 哈夫曼編碼/譯碼器錯誤！未定義書簽。18. 約瑟夫環錯誤！未定義書簽。19. 任意長的整數加法錯誤！未定義書簽。20. 關鍵路徑問題錯誤！未定義書簽。1 .航空客運訂票系統通過此系統可以實現如下功能：錄入：可以錄入航班情況（數據可以存儲在一個

7、數據文件中，數據結構、具體數據自定）；查詢：可以查詢某個航線的情況（如，輸入航班號，查詢起降時間，起飛抵達城市，航班票價，票價折扣，確定航班是否滿倉）；可以輸入起飛抵達城市，查詢飛機航班情況；訂票：（訂票情況可以存在一個數據文件中，結構自己設定）可以訂票，如果該航班已經無票，可以提供相關可選擇航班；退票：可退票，退票后修改相關數據文件；客戶資料有姓名，證件號，訂票數量及航班情況，訂單要有編號。修改航班信息：當航班信息改變可以修改航班數據文件要求：根據以上功能說明，設計航班信息，訂票信息的存儲結構，設計程序完成功能；2 .散列法的實驗研究基本要求：1、設每個記錄有下列數據項：電話號碼、用戶名、地

8、址；2、從鍵盤輸入各記錄，分別以電話號碼和用戶名為關鍵字建立散列表；3、采用一定的方法解決沖突；4、查找并顯示給定電話號碼的記錄；5、查找并顯示給定用戶名的記錄。進一步完成內容：1設計不同的散列函數，比較沖突率；2、在散列函數確定的前提下，嘗試各種不同類型處理沖突的方法，考察平均查找長度的變化。3 .學生搭配問題一班有m個女生，有n個男生（1不等于門），現要開一個舞會.男女生分別編號坐在舞池的兩邊的椅子上.每曲開始時，依次從男生和女生中各出一人配對跳舞，本曲沒成功配對者坐著等待下一曲找舞伴.請設計一系統模擬動態地顯示出上述過程，要求如下：1、 輸出每曲配對情況2、 計算出任何一個男生（編號為X

9、）和任意女生（編號為Y），在第K曲配對跳舞的情況至少求出K的兩個值.3、 盡量設計出多種算法及程序4、 提示：用隊列來解決比較方便.4 .二叉排序樹的實現用順序和二叉鏈表作存儲結構1）以回車（M）為輸入結束標志，輸入數列L,生成一棵二叉排序樹T;2）對二叉排序樹T作中序遍歷，輸出結果；3）輸入元素x,查找二叉排序樹T,若存在含x的結點，則刪除該結點，并作中序遍歷（執行操作2）；否則輸出信息“無x”；5 .利用棧求表達式的值編寫程序實現表達式求值，即驗證某算術表達式的正確性，若正確，則計算該算術表達式的值。主要功能描述如下：1、從鍵盤上輸入表達式。2、分析該表達式是否合法：（1）是數字，則判斷該

10、數字的合法性。若合法，則壓入數據到堆棧中。（2）是規定的運算符，則根據規則進行處理。在處理過程中，將計算該表達式的值。（3）若是其它字符，則返回錯誤信息。3、若上述處理過程中沒有發現錯誤，則認為該表達式合法，并打印處理結果。程序中應主要包含下面幾個功能函數：voidinitstack（）:初始化堆棧intMake_str（）：語法檢查并計算intpush_operate（intoperate）：將操作碼壓入堆木戔intpush_num(doublenum)：將操作數壓入堆棧intprocede(intoperate)：處理操作碼intchange_opnd(intoperate)：將字符型操作

11、碼轉換成優先級intpush_opnd(intoperate)：將操作碼壓入堆棧intpop_opnd()：將操作碼彈出堆棧intcaculate(intcur_opnd)：簡單計算+，*，/doublepop_num()：彈出操作數6 .走迷宮游戲程序開始運行時顯示一個迷宮地圖，迷宮中央有一只老鼠，迷宮的右下方有一個糧倉。游戲的任務是使用鍵盤上的方向鍵操縱老鼠在規定的時間內走到糧倉處。要求：老鼠形象可辨認，可用鍵盤操縱老鼠上下左右移動；迷宮的墻足夠結實，老鼠不能穿墻而過；正確檢測結果，若老鼠在規定時間內走到糧倉處，提示成功，否則提示失敗；添加編輯迷宮功能，可修改當前迷宮，修改內容：墻變路、路

12、變墻；找出走出迷宮的所有路徑，以及最短路徑。利用序列化功能實現迷宮地圖文件的存盤和讀出等功能7 .順序結構、動態鏈表結構下的一元多項式的加法、減法、乘法的實現。設有一兀多項式Am(X)和Bn(X).Am(X)=A0+AiX1+A2X2+A3X3+a+AmXm123nBn(X)=Bo+BlX+BaX+B3X+BnX請實現求M(X)=Am(X)+Bn(x)M(X)=Am(X)-Bn(X)和M(X)=Am(x)En(X)8 .線索二叉樹的應用要求：實現線索樹建立、插入、刪除、恢復線索的實現。9 .稀疏矩陣實現與應用要求：實現三元組，十字鏈表下的稀疏矩陣的下列應用。(1)稀疏矩陣的存儲(2)稀疏矩陣加

13、法(3)矩陣乘法(4)矩陣轉置10 .樹的應用要求：實現樹與二叉樹的轉換的實現。以及樹的前序、后序的遞歸、非遞歸算法，層次序的非遞歸算法的實現，應包含建樹的實現。11 .圖的遍歷和生成樹求解實現要求：先任意創建一個圖；圖的DFS,BFS的遞歸和非遞歸算法的實現最小生成樹（兩個算法）的實現，求連通分量的實現要求用鄰接矩陣、鄰接表、十字鏈表多種結構存儲實現12 .排序綜合利用隨機函數產生N個隨機整數（20000以上），對這些數進行多種方法進行排序。要求：至少采用三種方法實現上述問題求解（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的結果保存在

14、不同的文件中。統計每一種排序方法的性能（以上機運行程序所花費的時間為準進行對比），找出其中兩種較快的方法。如果采用4種或4種以上的方法者，可適當加分。13 .紙牌游戲任務：編號為152張牌，正面向上，從第2張開始，以2為基數，是2的倍數的牌翻一次，直到最后一張牌；然后，從第3張開始，以3為基數，是3的倍數的牌翻一次，直到最后一張牌；然后從第4張開始，以4為基數，是4的倍數的牌翻一次，直到最后一張牌；再依次5的倍數的牌翻一次，6的，7的直到以52為基數的翻過，輸出：這時正面向上的牌有哪些？14 .利用棧求表達式的值，可供小學生作業，并能給出分數。要求：建立試題庫文件，隨機產生n個題目；題目涉及加

15、減乘除，帶括弧的混合運算；隨時可以退出；保留歷史分數，能回顧歷史，給出與歷史分數比較后的評價15 .數制轉換問題任意給定一個M進制的數x，請實現如下要求1）求出此數x的10進制值（用MD表示）2）實現對x向任意的一個非M進制的數的轉換。3）至少用兩種或兩種以上的方法實現上述要求（用棧解決，用數組解決，其它方法解決）16 .停車場問題停車場是一條可以停放n輛車的狹窄通道，且只有一個大門汽車停放安到達時間的先后依次由北向南排列（大門在最南端，最先到達的第一輛車停在最北端）若停車場已經停滿n輛車，后來的汽車在便道上等候，一旦有車開走，排在便道上的第一輛車可以開入；當停車場的某輛車要離開時，停在他后面

16、的車要先后退為他讓路，等它開出后其他車在按照原次序開入車場，每兩停在車場的車要安時間長短繳費。要求：以棧模擬停車場，以隊列車場外的便道，按照從終端輸入的數據序列進行模擬管理。每一組數據包括三個數據項：汽車“到達”或“離去”信息、汽車牌照號碼、以及到達或離去的時刻。對每一組數據進行操作后的信息為：若是車輛到達，則輸出汽車在停車場的內或便道上的位置：若是車輛離去則輸出汽車在停車場內的停留時間和應繳納的費用（在便道上的停留時間不收費）。棧以順序結構實現，隊列以鏈表結構實現。17 .哈夫曼編碼/譯碼器【問題描述】設計一個利用哈夫曼算法的編碼和譯碼系統，重復地顯示并處理以下項目，直到選擇退出為止。【基本

17、要求】1）將權值數據存放在數據文件（文件名為data.txt，位于執行程序的當前目錄中）2）分別采用動態和靜態存儲結構3）初始化：鍵盤輸入字符集大小n、n個字符和n個權值，建立哈夫曼樹；4）編碼：利用建好的哈夫曼樹生成哈夫曼編碼；5）輸出編碼；6）設字符集及頻度如下表：字符空格ABCDEFGHIJKLM頻度1866413223210321154757153220字符NOPQRSTUVWXYZ頻度5763151485180238181161【進一步完成內容】1）譯碼功能；2）顯示哈夫曼樹；3）界面設計的優化。18 .約瑟夫環問題描述：編號為12n的n個人按順時針方向圍坐一圈，每人持有一個密碼（正整數）。一開始任選-個正整數作為報數的上限值m，從第一個人開始按順時針方向自1開始順序報數，報到m時停止報數，報m的人出列，將他的密碼作為新的m值，從他的順時針方向上的下一個開始重新從1報數，如此下去，直至所有人全部出列為止，設計一個程序求出出列順序。基本要求：1利用單循環鏈表作為存儲結構模擬此過程；2、鍵盤輸入總人數、初始報數上限值m及各人密碼；3、按照出列順