數(shù)據(jù)結(jié)構(gòu)大作業(yè)題目

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16、的車要先后退為他讓路，等它開出后其他車在按照原次序開入車場，每兩停在車場的車要安時(shí)間長短繳費(fèi)。要求：以棧模擬停車場，以隊(duì)列車場外的便道，按照從終端輸入的數(shù)據(jù)序列進(jìn)行模擬管理。每一組數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“離去”信息、汽車牌照號(hào)碼、以及到達(dá)或離去的時(shí)刻。對(duì)每一組數(shù)據(jù)進(jìn)行操作后的信息為：若是車輛到達(dá)，則輸出汽車在停車場的內(nèi)或便道上的位置：若是車輛離去則輸出汽車在停車場內(nèi)的停留時(shí)間和應(yīng)繳納的費(fèi)用（在便道上的停留時(shí)間不收費(fèi)）。棧以順序結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表結(jié)構(gòu)實(shí)現(xiàn)。17 .哈夫曼編碼/譯碼器【問題描述】設(shè)計(jì)一個(gè)利用哈夫曼算法的編碼和譯碼系統(tǒng)，重復(fù)地顯示并處理以下項(xiàng)目，直到選擇退出為止?！净?/p>

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