數(shù)據(jù)結構課程設計指導書

1、數(shù)據(jù)結構課程設計指導書一. 選題要求1. 基本數(shù)據(jù)結構的操作：設計出相關數(shù)據(jù)結構的相關函數(shù)庫，以便在程序設 計中調用。2. 相關應用：利用相關函數(shù)庫描述一個實際問題。3. 每個學生至少選做一題。二. 設計要求1 ）編程實現(xiàn)邏輯結構、存儲結構及各種基本函數(shù)以及常用函數(shù)自己確定函數(shù)、函數(shù)形式及理由）。2 ）最好能借助語言環(huán)境實現(xiàn)圖形顯示功能，以便能將抽象的數(shù)據(jù)結構以圖 形方式顯示出來，將復雜的運行過程以動態(tài)方式顯示出來。3 ）給出若干例程，演示通過調用自己的庫函數(shù)來實現(xiàn)相關問題的求解。4）測試數(shù)據(jù)：要求使用 1、全部合法數(shù)據(jù)； 2、整體非法數(shù)據(jù)； 3、局部非 法數(shù)據(jù)。進行程序測試，以保證程序的穩(wěn)定

2、。測試數(shù)據(jù)及測試結果請在上交的 資料中寫明 .5）所設計的數(shù)據(jù)結構應盡可能節(jié)省存儲空間。6）程序的運行時間應盡可能少。三考核要求1. 考勤2. 驗收3. 課程設計報告四、設計報告格式及要求： 1、題目2、設計目的3、邏輯結構、存儲結構定義及相關算法4、應用設計5、調試與測試：調試方法，測試結果的分析與討論，測試過程中遇到的主要問題及采取的解決措施6課程設計心得及體會7、源程序清單和執(zhí)行結果：清單中應有足夠的注釋五.課程設計題目一）順序表、鏈表的操作及應用課題1:設計一個計算機管理系統(tǒng)完成圖書管理基本業(yè)務。基本要求：1每種書的登記內容包括書號、書名、著作者、現(xiàn)存量和庫存量；2對書號建立索引表 線

3、性表）以提高查找效率 索引表采用樹表）；3系統(tǒng)主要功能如下：*采編入庫：新購一種書，確定書號后，登記到圖書帳目表中，如果表中 已有，則只將庫存量增加；*借閱：如果一種書的現(xiàn)存量大于0,則借出一本，登記借閱者的書證號和歸還期限，改變現(xiàn)存量；*歸還：注銷對借閱者的登記，改變該書的現(xiàn)存量。課題2：活期儲蓄帳目管理：活期儲蓄處理中，儲戶開戶、銷戶、存入、支出活動頻繁，系統(tǒng)設計要求：1能比較迅速地找到儲戶的帳戶，以實現(xiàn)存款、取款記賬；2能比較簡單，迅速地實現(xiàn)插入和刪除，以實現(xiàn)開戶和銷戶的需要課題3：猴子吃桃子問題：有一群猴子摘了一堆桃子，他們每天都吃當前桃子的一半且再多吃一個，到了 第10天就只余下一個

4、桃子。用多種方法實現(xiàn)求出原來這群猴子共摘了多少個桃 子。要求：1）采用數(shù)組數(shù)據(jù)結構實現(xiàn)上述求解2采用鏈數(shù)據(jù)結構實現(xiàn)上述求解3采用遞歸實現(xiàn)上述求解4可擴展采用4種以上方法課題4：敢死隊問題：有M個敢死隊員要炸掉敵人的一碉堡，誰都不想去，排長決定用輪回數(shù)數(shù)的 辦法來決定哪個戰(zhàn)士去執(zhí)行任務。如果前一個戰(zhàn)士沒完成任務，則要再派一 個戰(zhàn)士上去?，F(xiàn)給每個戰(zhàn)士編一個號，大家圍坐成一圈，隨便從某一個戰(zhàn)士 開始計數(shù)，當數(shù)到5時，對應的戰(zhàn)士就去執(zhí)行任務，且此戰(zhàn)士不再參加下一 輪計數(shù)。如果此戰(zhàn)士沒完成任務，再從下一個戰(zhàn)士開始數(shù)數(shù)，被數(shù)到第5時，此戰(zhàn)士接著去執(zhí)行任務。以此類推，直到任務完成為止。排長是不愿意去的，假設

5、排長為1號，請你設計一程序，求出從第幾號戰(zhàn)士開始計數(shù)才 能讓排長最后一個留下來而不去執(zhí)行任務。要求：至少采用兩種不同的數(shù)據(jù)結構的方法實現(xiàn)。二）棧和隊列的操作及應用 課題5：數(shù)制轉換問題任意給定一個M進制的數(shù)x ，請實現(xiàn)如下要求1求出此數(shù)x的10進制值 用MD表示）2實現(xiàn)對x向任意的一個非M進制的數(shù)的轉換。3 至少用兩種或兩種以上的方法實現(xiàn)上述要求 用棧解決，用數(shù)組解決，其它方法解決）。課題6：利用棧求表達式的值，可供小學生作業(yè)，并能給出分數(shù)。要求：建立試卷庫文件，隨機產生 n個題目；題目涉及加減乘除，帶括弧 的混合運算；隨時可以退出；保留歷史分數(shù)，能回顧歷史，給出與歷史分數(shù) 比較后的評價。課題

6、7:程序開始運行時顯示一個迷宮地圖，迷宮中央有一只老鼠，迷宮的右 下方有一個糧倉。游戲的任務是使用鍵盤上的方向鍵操縱老鼠在規(guī)定的時間內 走到糧倉處。要求：1 老鼠形象可辨認，可用鍵盤操縱老鼠上下左右移動；2迷宮的墻足夠結實，老鼠不能穿墻而過；3正確檢測結果，若老鼠在規(guī)定時間內走到糧倉處，提示成功，否則提 示失?。?添加編輯迷宮功能，可修改當前迷宮，修改內容：墻變路、路變墻；5找出走出迷宮的所有路徑，以及最短路徑；利用序列化功能實現(xiàn)迷宮地圖文件的存盤和讀出等功能。課題8設計一個模擬電梯工作過程的圖形演示系統(tǒng)。要求所設計的電梯能符 合市場上大多數(shù)系統(tǒng)的要求。課題8：學生搭配問題。一班有m個女生,有

7、n個男生m不等于n），現(xiàn)要開一個舞會。男女生分別編 號坐在舞池的兩邊的椅子上。每曲開始時，依次從男生和女生中各出一人配 對跳舞，本曲沒成功配對者坐著等待下一曲找舞伴。請設計一系統(tǒng)模擬動態(tài)地顯示出上述過程，要求如下：1）輸出每曲配對情況；2）計算出任何一個男生 編號為X）和任意女生 編號為Y,在第K曲配對 跳舞的情況至少求出K的兩個值；3）盡量設計出多種算法及程序。提示：用隊列來解決比較方便三）樹的操作及應用課題9:樹與二叉樹的轉換的實現(xiàn)。以及樹的前序、后序的遞歸、非遞歸遍歷 算法，層次序的非遞歸遍歷算法的實現(xiàn)，應包含建樹的實現(xiàn)。課題10：二叉樹的中序、前序、后序的遞歸、非遞歸遍歷算法，層次序的

8、非 遞歸遍歷算法的實現(xiàn)，應包含建樹的實現(xiàn)。課題11:采用哈夫曼編碼思想實現(xiàn)文件的壓縮和恢復功能，并提供壓縮前后 的占用空間之比。要求：1）描述壓縮基本符號的選擇方法。2）運行時的壓縮原文件的規(guī)模應不小于 5K。3）提供恢復文件與原文件的相同性對比功能。課題12：設計程序以實現(xiàn)構造哈夫曼樹的哈夫曼算法。要求：1）可以使用實驗工具的有關功能。2）要能演示構造過程。3）求解出所構造的哈夫曼樹的帶權路徑長度。課題13：設計程序完成如下功能：對給定的圖結構，實現(xiàn)求解最小生成樹的 Kruskal算法，并給出求解過程的動態(tài)演示。先任意創(chuàng)建一個圖；2圖的DFS BFS的遞歸和非遞歸算法的實現(xiàn)3最小生成樹 要求

9、用鄰接矩陣、鄰接表、十字鏈表多種結構存儲實現(xiàn)課題15:設計程序完成如下功能：對給定的圖結構和起點，產生其所有的深度 優(yōu)先搜索遍歷序列，并給出求解過程的動態(tài)演示。課題16：設計程序完成如下功能：對給定的網和起點，實現(xiàn)求解最小生成樹的 PRIM算法，并給出求解過程的動態(tài)演示。課題17:學校超市選址問題 帶權有向圖的中心點）設計要求：對于某一學校超市，其他各單位到其的距離不同，同時各單位人員 去超市的頻度也不同。請為超市選址，要求實現(xiàn)總體最優(yōu)。課題18校園導航問題）：設計你的學校的平面圖，至少包括 10個以上的場所，每兩個場所間可以有不同 的路，且路長也可能不同，找出從任意場所到達另一場所的最佳路徑

10、 最短路徑）。課題19馬的遍歷問題）：設計程序完成如下要求：在中國象棋棋盤上，對任一位置上放置的一個馬，均能選擇一個合適的路線，使得該棋子能按象棋的規(guī) 則不重復地走過棋盤上的每一位置。要求：1）依次輸出所走過的各位置的坐標。2）最好能畫出棋盤的圖形形式，并在其上動態(tài)地標注行走過程。3）程序能方便地地移植到其它規(guī)格的棋盤上。課題20：在8X8的國際象棋棋盤上，如果在放置若干個馬后，使得整個棋盤 的任意空位置上所放置的棋子均能被這些馬吃掉，則稱這組放置為棋盤的一個 滿覆蓋。若去掉滿覆蓋中的任意一個棋子都會使這組放置不再是滿覆蓋，則稱 這一滿覆蓋為極小滿覆蓋。設計程序完成如下要求：要求：1 ）求解一

11、個極小滿覆蓋。2）最好能畫出棋盤的圖形形式，并在其上動態(tài)地演示試探過程3）程序能方便地移植到其它規(guī)格的棋盤上。課題 21：在中國象棋棋盤上實現(xiàn)上一課題的任務。要求：除了上一課題的要求外，還要考慮到“別腿”的規(guī)定。 設每個記錄有下列數(shù)據(jù)項：電話號碼、用戶名、地址；2 從鍵盤輸入各記錄，分別以電話號碼和用戶名為關鍵字建立散列表；3 采用一定的方法解決沖突；4 查找并顯示給定電話號碼的記錄；5 查找并顯示給定用戶名的記錄。擴展要求： 1 系統(tǒng)功能的完善； 2 設計不同的散列函數(shù)，比較沖突 率； 3 在散列函數(shù)確定的前提下，嘗試各種不同類型處理沖突的方法，考察 平均查找長度的變化。六）排序操作及應用課題 23：給出一組實驗來比較下列排序算法的時間性能：快速排序、堆排序、希爾排序、冒泡排序、歸并排序 其它排序也可以作為比較的對象） 要求：1）時間性能包括平均時間性能、最好情況下的時間性能、最差情況下的時 間性能等。2） 實驗數(shù)據(jù) 應具有說服力 ，包 括：規(guī)模