《資料結構與演算法》課程設計計畫
一、設計目的
資料結構與演算法課程設計是《資料結構與演算法》課程教學必不可缺的乙個重要環節，它可加深學生對該課程所學內容的進一步的理解與鞏固，是將計算機課程與實際問題相聯接的關鍵步驟。通過課程設計，能夠提高學生分析問題、解決問題，從而運用所學知識解決實際問題的能力，因而必須給予足夠的重視。
二、課程設計任務
7-8人為乙個課題組，組長1人，要求每組任選2題，各組不得重複選題且需獨立完成課題內容，課題組成員必須清楚課題總體設計，必須分有功能模組並獨立完成所分模組程式的編寫任務。最終課題組長組織連調，所有成員必須參加。
三、課程設計內容:
1．二叉樹的中序、前序、後序的遞迴、非遞迴遍歷演算法，按層次遍歷的非遞迴遍歷演算法的實現，應包含建樹的實現。
2．車廂排程
假設停在鐵路排程站入口處的車廂序列的編號一次為1，2，3，4。設計乙個程式，求出所有可能由此輸出的長度為4的車廂序列。
3．平衡二叉樹的判定
給定乙個二叉樹的先序遍歷或後序遍歷結果，判定其是否為平衡二叉樹。
4.圖的基本操作與實現設計要求：
(1)自選儲存結構,輸入含n個頂點（用字元表示頂點）和e條邊的圖g
(2)求每個頂點的度,輸出結果；
(3)指定任意頂點x為初始頂點,對圖g作dfs遍歷,輸出dfs頂點序列(提示:使用乙個棧實現dfs)；
(4)指定任意頂點x為初始頂點,對圖g作bfs遍歷,輸出bfs頂點序列(提示:使用乙個佇列實現bfs)；
(5)輸入頂點x,查詢圖g:若存在含x的頂點,則刪除該結點及與之相關連的邊,並作
dfs遍歷(執行操作3)；否則輸出資訊「無x」；
5.圖的演算法實現
(1)讀入圖的資訊，建立與其對應的鄰接矩陣和鄰接表；
(2)實現prim、kruskal、dijkstra序演算法。
6.內部排序演算法的效能分析
設計要求：設計乙個測試程式比較幾種內部排序演算法的關鍵字比較次數和移動次數以取得直觀感受。
(1)對起泡排序、直接排序、簡單選擇排序、快速排序、希爾排序、堆排序演算法進行比較；
(2)待排序表的表長不小於100，表中資料隨機產生，至少用5組不同資料作比較，比較指標有：關鍵字參加比較次數和關鍵字的移動次數（關鍵字交換記為3次移動）；
(3)輸出比較結果。
網的研究
已知乙個aoe網，求其關鍵路徑長度及關鍵活動有哪些。
8.二叉排序樹的實現
(1) 用二叉鍊錶作儲存結構,以回車('\n')為輸入結束標誌,輸入數列l，生成一棵二叉排序樹t；
(2)對二叉排序樹t作中序遍歷，輸出結果；
(3)輸入元素x,查詢二叉排序樹t,若存在含x的結點,則刪除該結點,並作中序遍歷(執行操作2)；否則輸出資訊「無x」；
9.哈夫曼編碼/解碼器
設計乙個利用哈夫曼演算法的編碼和解碼系統，重複地顯示並處理以下專案，直到選擇退出為止。基本要求如下：
(1)初始化：鍵盤輸入字符集大小n、n個字元和n個權值，建立哈夫曼樹；
(2)編碼：利用建好的哈夫曼樹生成哈夫曼編碼；
(3)輸出編碼；
(4)解碼：利用編碼實現解碼。
10.稀疏矩陣應用
分別實現三元組、十字鍊錶下的稀疏矩陣的儲存、加法、乘法、轉置實現。
11. 串的應用
本設計要求實現的串的儲存、求串長、判斷串相等、取子串、插入子串、刪除子串、串的匹配等。本設計用乙個主控選單程式控制，至少實現以上7個功能
12.構造可以使n個城市連線的最小生成樹
給定乙個地區的n個城市間的距離網，用prim演算法或kruskal演算法建立最小生成樹，並計算得到的最小生成樹的代價。基本要求如下：
(1)城市間的距離網採用鄰接矩陣表示，若兩個城市之間不存在道路，則將相應邊的權值設為自己定義的無窮大值。要求在螢幕上顯示得到的最小生成樹中包括了哪些城市間的道路，並顯示得到的最小生成樹的代價。
(2)表示城市間距離網的鄰接矩陣（要求至少6個城市，10條邊）
(3)最小生成樹中包括的邊及其權值，並顯示得到的最小生成樹的代價。
13. 特殊矩陣的壓縮儲存演算法的實現
對於特殊矩陣可以通過壓縮儲存減少儲存空間。基本要求：
(1)針對多種特殊矩陣進行壓縮儲存，並能顯示壓縮後的相關位址和值；
(2)輸入在原來特殊矩陣中的位址，要求能從壓縮後的矩陣中讀出相應的值；
14.算術表示式的求解
給定乙個算術表示式，通過程式求出最後的結果。基本要求：
(1)從鍵盤輸入要求解的算術表示式；
(2)採用棧結構進行算術表示式的求解過程；
(3)能夠判斷算術表示式正確與否；
(4)對於錯誤表示式給出提示；
(5)對於正確的表示式給出最後的結果；
15.廣義表的應用
由於廣義表在結構上較線性表複雜得多，因此，廣義表的運算也不如線性表簡單。本設計要求實現的廣義表的建立、查詢、輸出、取表頭和取表尾以及求深度等。
本設計用乙個主控選單程式控制，至少實現以下6個功能：
(1)建立廣義表
(2)輸出廣義表
(3)結點的查詢
(4)求廣義表表頭
(5)求廣義表表尾
(6)求廣義表的深度
四、課程設計的基本要求
1．問題分析和任務定義。根據設計題目的要求，充分地分析和理解問題，明確問題要求做什麼？（而不是怎麼做？）限制條件是什麼？
2．邏輯設計。對問題描述中涉及的操作物件定義相應的資料型別，並按照以資料結構為中心的原則劃分模組，定義主程式模組和各抽象資料型別。邏輯設計的結果應寫出每個抽象資料型別的定義(包括資料結構的描述和每個基本操作的功能說明)，各個主要模組的演算法，並畫出模組之間的呼叫關係圖。
3．詳細設計。定義相應的儲存結構並寫出各函式的偽碼演算法。在這個過程中，要綜合考慮系統功能，使得系統結構清晰、合理、簡單和易於除錯，抽象資料型別的實現盡可能做到資料封裝，基本操作的規格說明盡可能明確具體。
詳細設計的結果是對資料結構和基本操作作出進一步的求精，寫出資料儲存結構的型別定義，寫出函式形式的演算法框架。
4．程式編碼。把詳細設計的結果進一步求精為程式語言程式。同時加入一些註解和斷言，使程式中邏輯概念清楚。
5．程式除錯與測試。採用自底向上，分模組進行，即先除錯低層函式。能夠熟練掌握除錯工具的各種功能，設計測試資料確定疑點，通過修改程式來證實它或繞過它。
除錯正確後，認真整理源程式及其注釋，形成格式和風格良好的源程式清單和結果。
6．結果分析。程式執行結果包括正確的輸入及其輸出結果和含有錯誤的輸入及其輸出結果。演算法的時間、空間複雜性分析。
7．編寫課程設計報告並提交相關內容
設計最終需提交的內容包括：
（1）課程設計報告（1份，a4紙列印，同時包括乙份電子版）命名格式為：組號+班級+（組長姓名等）+數計系課程設計報告.doc《如1、數計系10信計（石杭等）課程設計報告.doc>
報告要求版面清晰，格式規範，否則重新編寫。報告內容要求包括：
①問題的概述、分析及研究意義；
②資料結構的邏輯設計和物理儲存設計；
③重要演算法的設計、流程描述或偽**描述；
④資料結構的時空複雜性分析以及重要演算法的複雜性分析；
⑤程式最終實現結果（包括重點結果介面的抓取，能夠說明問題的重要實驗結果資料的列印或其視覺化結果等）。
⑥參考文獻（如果需要）。
⑦附錄部分附上關鍵資料結構的定義及關鍵演算法的源**。
（2）源程式文件（電子方式提交）
源程式**要求結構清晰、可讀性好。應對源程式中的類說明（如果採用物件導向方法設計），函式說明，介面說明，關鍵變數說明等進行注釋；源程式要進行適當的縮排編排。命名格式為：
組號+班級+（組長姓名等）+數計系課程設計源程式《如1、數計系10信計（石杭等）課程設計源程式》
（3）所有以電子方式提交的檔案全部存在乙個目錄中，並對其進行壓縮（用winrar或winzip均可），壓縮後的檔案按規定格式進行命名，命名格式為：組號+班級+（組長姓名等）+課程設計.rar《如1、數計系10信計（石杭等）課程設計.
rar>。
資料結構與演算法課程設計
在程式正確性的前提下，要兼顧介面設計和 可重用性的質量，注重物件導向設計理念的考核。上交的成果的內容必須由以下四個部分組成，缺一不可 1 上交源程式 學生按照課程設計的具體要求所開發的所有源程式 應該放到乙個資料夾中 2 上交程式的說明檔案 儲存在.txt中 在說明文件中應該寫明上交程式所在的目錄，...
演算法與資料結構課程設計報告
演算法與資料結構 課程設計實驗報告書 課程設計名稱 最小套圈設計 學生姓名 張延雲 學號 201058501314 學院 計算機學院 班級 計101 3班 日期 2012年7月13日 一 問題分析和任務定義 1 問題分析 本設計的要求是設計乙個最小套圈。規則是 遊戲者將手中的圓環套圈投向場中的玩具，...
演算法與資料結構課程設計指導書2019
資料結構與演算法 課程設計指導書 宣城校區資訊工程系 2014年12月 課程設計是對學生的一種全面綜合訓練，是與課堂聽講 自學和練習相輔相成的 必不可少的乙個教學環節。通常，課程設計中的問題比平時的習題複雜的多，也更接近實際。課程設計著眼於原理與應用的結合點，使學生學會如何把書上學到的知識用於解決實...