數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)課程設(shè)計方案

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題目（ 2013 年）一、必做題1、圖書管理系統(tǒng)（線性表）問題描述設(shè)計一個程序，記錄并統(tǒng)計圖書使用情況?；疽?（ 1）圖書信息包括圖書 ID 號，圖書名，出版社名，出版年月，館藏冊數(shù)。（2）學(xué)生信息包括學(xué)號，姓名，班級，在借冊數(shù)，已還冊數(shù)，違約次數(shù)。（ 3）借閱信息包括圖書 ID 號，圖書名，學(xué)號，姓名，借閱日期，應(yīng)還日期，歸還日 期。（4）采用順序存儲線性表表示圖書信息。采用鏈?zhǔn)酱鎯€性表表示學(xué)生信息。采用雙 向循環(huán)鏈表表示借閱信息 。其中一個雙向循環(huán)鏈表表示在借的借閱信息， 按照圖書 ID 號非遞減排序；另一個雙向循環(huán)鏈表表示已還的借閱信息， 按照圖書 ID 號非遞減排

2、序。 （ 5）圖書信息，學(xué)生信息、借閱信息采用文件方式輸入。圖書信息示例如下，每條信息一行：16000001 數(shù)據(jù)結(jié)構(gòu) 清華大學(xué)出版社 2012.10 30學(xué)生信息示例如下，每條信息一行：161340106 張三 1613401 5 10借閱信息示例如下，每條信息一行：標(biāo)志位 1（ 1 表示借閱 2 表示歸還） 16000001 數(shù)據(jù)結(jié)構(gòu) 161340106 張 三 2013.9.12 （借閱時表示借閱日期， 應(yīng)還日期自動生成， 根據(jù)借閱日期 +60 天； 歸 還時表示歸還日期， 歸還日期要在借閱日期之后， 應(yīng)還日期之前， 如果超過應(yīng)還日期， 則記錄一次違約次數(shù)） 。例如借閱： 1 16000

3、001 數(shù)據(jù)結(jié)構(gòu) 161340106 張三 歸還： 2 16000001 數(shù)據(jù)結(jié)構(gòu) 161340106 張三 2013.10.20 （6）規(guī)定每位學(xué)生不能同時借閱同一本書兩本及以上。圖書歸還后，將該條借閱信息 從借閱鏈表中轉(zhuǎn)移到歸還鏈表中。（ 7）要求模擬數(shù)據(jù)中圖書信息至少 30 本以上，學(xué)生信息至少 20 條以上，借閱信息至 少 50 條以上。（ 8）能夠統(tǒng)計每一本圖書被借閱次數(shù)（已還） ，在借冊數(shù)。查詢每一位學(xué)生的借閱歷 史明細記錄。統(tǒng)計學(xué)生平均借閱次數(shù)，最大借閱次數(shù)，最少借閱次數(shù)。（9）可在此要求基礎(chǔ)上進行功能擴展。2、算術(shù)表達式求值（棧）問題描述一個算術(shù)表達式是由操作數(shù) （operan

4、d） 、運算符 （operator） 和界限符 （delimiter） 組成 的。假設(shè)操作數(shù)是正實數(shù)，運算符只含加減乘除等四種運算符，界限符有左右括號和 表達式起始、結(jié)束符 “#”，如：#（7+15）*（23-28/4 ）#。引入表達式起始、結(jié)束符 是為了方便。編程利用 “算符優(yōu)先法 ”求算術(shù)表達式的值?；疽?1） 從鍵盤或文件讀入一個合法的算術(shù)表達式，輸出正確的結(jié)果（ 2） 顯示輸入序列和棧的變化過程。（ 3） 考慮算法的健壯性，當(dāng)表達式錯誤時，要給出錯誤原因的提示。3、二叉樹的應(yīng)用（二叉樹）問題描述編程實現(xiàn)二叉樹的建立，先序、中序、后序（遞歸和非遞歸方法） 、層序遍歷，二 叉樹的高度、

5、繁茂度，交換左右子樹，統(tǒng)計葉子節(jié)點的數(shù)目，判斷是否為完全二叉樹， 按樹的形態(tài)在屏幕上打印輸出。基本要求 （1） 從文件中讀入建樹信息，樹的節(jié)點數(shù)目不小于 20 個，樹的高度不小于 4。（ 2） 建樹信息采用兩行英文字符表示，每個英文字符代表一個結(jié)點，第1 行為樹的中序遍歷結(jié)果，第 2 行為樹的后序遍歷結(jié)果。4、Huffman 編碼與解碼（ Huffman 編碼、二叉樹）問題描述對一篇英文文章 （大于 2000 個英文字符），統(tǒng)計各字符出現(xiàn)的次數(shù)， 實現(xiàn) Huffman 編碼，以及對編碼結(jié)果的解碼?；疽?（ 1） 輸出每個字符出現(xiàn)的次數(shù)和編碼，其中求最小權(quán)值要求用堆實現(xiàn)。（ 2） 在 Huf

6、fman 編碼后，要將編碼表和英文文章編碼結(jié)果保存到文件中，編碼結(jié)果 必須是二進制形式，即 0 1 的信息用比特位表示，不能用字符 '0'和'1'表示。3） 提供讀編碼文件生成原文件的功能。5、關(guān)鍵路徑問題（圖）問題描述設(shè)計并實現(xiàn)關(guān)鍵路徑的一種應(yīng)用?；疽?（1）實現(xiàn)拓撲排序和關(guān)鍵路徑的發(fā)現(xiàn)。（2）給出一個具體的應(yīng)用環(huán)境。6、排序算法比較（排序）問題描述利用隨機函數(shù)產(chǎn)生 10 個樣本（其中之一已為正序，之一為倒序） ，每個樣本有 20000 隨機整數(shù)，利用直接插入排序、希爾排序，冒泡排序、快速排序、選擇排序、堆排序， 歸并排序（遞歸和非遞歸），基數(shù)排序八種排序

7、方法進行排序 （結(jié)果為由小到大的順序） ， 并統(tǒng)計每一種排序所耗費的平均時間基本要求 （ 1） 原始數(shù)據(jù)存在文件中，每個整數(shù)一行，方便讀入。（ 2） 屏幕顯示每種排序所花的比較次數(shù)。、選做題1、迷宮問題（棧與遞歸）問題描述利用棧操作實現(xiàn)迷宮問題求解?；疽?（1）隨機生成模擬迷宮地圖，不少于 10行 10列，存在文件中（ 2）動態(tài)顯示每一步的結(jié)果 。（ 3）可在此基礎(chǔ)上有改進方法。2、家譜管理系統(tǒng)（樹）問題描述實現(xiàn)具有下列功能的家譜管理系統(tǒng)基本要求 （1）輸入文件以存放最初家譜中各成員的信息，成員的信息中均應(yīng)包含以下內(nèi)容：姓 名、出生日期、婚否、地址、健在否、死亡日期（若其已死亡） ，也可附

8、加其它信息、 但不是必需的。（2）實現(xiàn)數(shù)據(jù)的存盤和讀盤。（3）以圖形方式顯示家譜。（ 4）顯示第 n 代所有人的信息。（ 5）按照姓名查詢，輸出成員信息（包括其本人、父親、孩子的信息） 。（6）按照出生日期查詢成員名單。（7）輸入兩人姓名，確定其關(guān)系。8）某成員添加孩子。（10）修改某成員信息。（11）按出生日期對家譜中所有人排序。（ 12）打開一家譜時，提示當(dāng)天生日的健在成員。（ 13）要求建立至少 30 個成員的數(shù)據(jù)，以較為直觀的方式顯示結(jié)果，并提供文稿形式 以便檢查。（14）界面要求：有合理的提示，每個功能可以設(shè)立菜單，根據(jù)提示，可以完成相關(guān) 的功能要求。（15）存儲結(jié)構(gòu)：根據(jù)系統(tǒng)功能要

9、求自行設(shè)計，但是要求相關(guān)數(shù)據(jù)要存儲在數(shù)據(jù)文件 中。測試數(shù)據(jù)：要求使用 1、全部合法數(shù)據(jù)； 2、局部非法數(shù)據(jù)。進行程序測試，以保 證程序的穩(wěn)定。3、公交線路提示（圖）問題描述 建立南京主要公交線路圖?；疽?（1）輸入任意兩站點，給出最佳的乘車線路和轉(zhuǎn)車地點。 路線信息：可上網(wǎng)查詢最新的公交線路信息4、社交網(wǎng)絡(luò)圖實現(xiàn)（圖）問題描述設(shè)計并實現(xiàn)一種簡單的社交網(wǎng)絡(luò)模型圖?；疽?（ 1） 每個人的信息是一個結(jié)點，人與人的聯(lián)系構(gòu)成邊。個人信息里要有地理坐標(biāo)信 息，以便后續(xù)應(yīng)用中能方便找靠近的人。（ 2） 根據(jù)輸入的任意兩個人信息，給出他們之間的聯(lián)系路徑，最少經(jīng)過多少人構(gòu)成 聯(lián)系。（ 3） 根據(jù)位置信

10、息的動態(tài)變化，找尋附近能夠聯(lián)絡(luò)的人，能夠通過1 次中間人能聯(lián)絡(luò)的人等。（4）模擬仿真結(jié)點的聯(lián)絡(luò)密切程度，根據(jù)聯(lián)絡(luò)密切程度發(fā)現(xiàn)社交網(wǎng)絡(luò)中的小團體。（ 5）可根據(jù)自己的創(chuàng)意添加更多的功能。5、營業(yè)窗口隊列模擬任務(wù)：實現(xiàn)具有 n（n=3 ）個窗口的現(xiàn)實隊列模擬，統(tǒng)計每人的等待時間 要求：1）. 隨機產(chǎn)生顧客的到達時間和服務(wù)時間存盤。2）. 利用存盤數(shù)據(jù)實現(xiàn)隊列的插入和刪除。2）. 當(dāng)有顧客離開時，根據(jù)隊列長度調(diào)整隊尾。3）. 考慮顧客中途離隊的情況。4）. 考慮顧客具有優(yōu)先級的情況。6、電子小字典任務(wù)：建立一個微型電子字典，實現(xiàn)生詞的加入，單詞的查找、刪除，修改等操作。數(shù)據(jù)結(jié)構(gòu)：鍵樹7、稀疏矩陣相乘

11、 任務(wù)：以三元組形式存儲稀疏矩陣，實現(xiàn)矩陣相乘8、平衡二叉樹任務(wù)：平衡二叉樹的建立、結(jié)點的插入和刪除。9、B-樹任務(wù)：3階B-樹的結(jié)點的插入和刪除。10 、編寫“連連看”程序。11、（自選合適的題目）成績評定細則：20 分）20 分）1. 正確性：程序是否可以運行，結(jié)果是否正確（2. 功能的完備性：是否實現(xiàn)要求的所有子功能（3. 課程設(shè)計報告中的算法說明的清晰程度，課程設(shè)計報告中總結(jié)的深刻程度（20 分）4. 獨立完成情況 （ 40 分）總計： 100 分加分項目：1. 工作量和選題難度2. 可讀性：代碼編寫是否規(guī)范，是否便于閱讀。如函數(shù)、變量命名， '的縮進，關(guān)鍵位 置適量注釋等3.

12、 功能的完善：除要求實現(xiàn)的功能外，完成了其它的功能，實現(xiàn)了功能的完善4. 健壯性：異常處理的情況5. 界面的設(shè)計：可視化界面，或者交互良好的 DOS 界面6. （自薦加分項目）代碼量要求： >=2200 行。代碼總量 = 課設(shè)題目 1 代碼量 + 課設(shè)題目 2 代碼量若代碼總量低于 2200 行，則成績按比例打折。編程語言： C、C+ 或 JAVA 任選其一檢查方式 :1. 一對一上機檢查2. 總體上檢查程序的代碼量，正確性，可讀性，健壯性，功能的完備性，程序的結(jié)構(gòu) 是否合理；根據(jù)實際情況進行詳細的程序代碼檢查。時間安排：1 上機時間安排2 課程設(shè)計報告上交時間3 課程設(shè)計檢查時間課程設(shè)計報告要求：1.課程設(shè)計報告封面：包括課題名稱、班級、學(xué)號、學(xué)生姓名、成績和指導(dǎo)教師；2.課程設(shè)計報告目錄：每部分內(nèi)容所在頁碼；3. 需求分析：給出每道題的需求；4. 概要設(shè)計：給出每道題