2011-8-16
一、課程設計目的 3
二、課程設計步驟 3
三、課程設計報告 4
四、課程設計內容 6
五、提交材料 6
六、考核方式與評分標準 7
七、關於編寫**的說明 7
八、參考文獻 8
附錄1 武漢工業學院課程設計說明書（報告）撰寫規範 9
附錄2 visual c++ 6.0簡介 11
培養計算機專業的學生的演算法程式設計能力。通過上機實驗，可以培養學生程式設計的方法和技巧，提高學生編制清晰、合理、可讀性好的系統程式的能力，加深對資料結構課程和演算法的理解。使學生更好地掌握資料結構的基本概念、基本原理、及基本演算法,具有分析演算法、設計演算法、構造和開發較複雜演算法的基本能力。
隨著計算機效能的提高，它所面臨的軟體開發的複雜度也日趨增加。然而，編制乙個10000行的程式的難度絕不僅僅是乙個5000行的程式的兩倍，因此軟體開發需要系統的方法。一種常用的軟體開發方法，是將軟體開發過程分為分析、設計、實現和維護四個階段。
雖然資料結構課程中的課程設計的複雜度遠不如(從實際問題中提出來的)乙個「真正的」軟體，但為了培養乙個軟體工作者所應具備的科學工作的方法和作風，完成課程設計的應有如下的5個步驟：
1. 問題分析和任務定義
通常，課程設計題目的陳述比較簡潔，或者說是有模稜兩可的含義。因此，在進行設計之前，首先應該充分地分析和理解問題，明確問題要求做什麼，限制條件是什麼。注意：
本步驟強調的是做什麼，而不是怎麼做。對問題的描述應避開演算法和所涉及的資料型別，而是對所需完成的任務作出明確的回答。例如：
輸入資料的型別、值的範圍以及輸入的形式；輸出資料的型別、值的範圍及輸出的形式；若是會話式的輸入，則結束標誌是什麼，是否接受非法的輸入，對非法輸入的回答方式是什麼等等。這一步還應該為除錯程式準備好測試資料，包括合法的輸入資料和非法形式輸入的資料。
2. 資料型別和系統設計
在設計這一步驟中需分邏輯設計和詳細設計兩步實現。邏輯設計指的是，對問題描述中涉及的操作物件定義相應的資料型別，並按照以資料結構為中心的原則劃分模組，定義主程式模組和各抽象資料型別；詳細設計則為定義相應的儲存結構並寫出各過程和函式的偽碼演算法。在這個過程中，要綜合考慮系統功能，使得系統結構清晰、合理、簡單和易於除錯，抽象資料型別的實現盡可能做到資料封裝，基本操作的規格說明盡可能明確具體。
作為邏輯設計的結果，應寫出每個抽象資料型別的定義(包括資料結構的描述和每個基本操作的規格說明)，各個主要模組的演算法，並畫出模組之間的呼叫關係圖。詳細設汁的結果是對資料結構和基本操作的規格說明作出進一步的求精，寫出資料儲存結構的型別定義，按照演算法書寫規範用類c語言寫出過程或函式形式的演算法框架。在求精的過程中，應盡量避免陷入語言細節，不必過早表述輔助資料結構和區域性變數。
3. 編碼實現和靜態檢查
編碼是把詳細設計的結果進一步求精為程式語言程式。程式的每行不要超過60個字元。每個過程(函式)體，即不計首部和規格說明部分，一般不要超過40行。
最長不得超過60 行，否則應該分割成較小的過程(函式)。要控制語句連續巢狀的深度。如何編寫程式才能較快地完成除錯是特別要注意的問題。
對於程式設計很熟練的讀者，如果基於詳細設計的偽碼演算法就能直接在鍵盤上輸入程式的話，則可以不必用筆在紙上寫出編碼，而將這一步的工作放在上機準備之後進行，即在上機除錯之前直接用鍵盤輸入。然而，不管你是否寫出編碼的程式，在上機之前，認真的靜態檢查卻是必不可少的。多數初學者在編好程式後處於以下兩種狀態之一：
一種是對自己的「精心作品」的正確性確信不疑；另一種是認為上機前的任務已經完成，糾查錯誤是上機的工作。這兩種態度是極為有害的。事實上，非訓練有素的程式設計者編寫的程式長度超過50 行時，極少不含有除語法錯誤以外的錯誤。
上機動態除錯決不能代替靜態檢查，否則除錯效率將是極低的。靜態檢查主要有兩種方法，一是用一組測試資料手工執行程式(通常應先分模組檢查)；二是通過閱讀或給別人講解自己的程式而深入全面地理解程式邏輯，在這個過程中再加入一些註解和斷言。如果程式中邏輯概念清楚，後者將比前者有效。
4. 上機準備和上機除錯
上機準備包括以下幾個方面：
(1) 高階語言文字(體現與編譯程式使用者手冊)的擴充和限制。例如，有些c編譯程式限制for語句的迴圈控制變數為區域性簡單變數等。
(2) 如果用c語言，要特別注意平時慣用的類c語言與標準c語言之間的細微差別。
(3) 熟悉機器的作業系統和語言整合環境的使用者手冊，尤其是最常用的命令操作，以便順利進行上機的基本活動。
(4) 掌握除錯工具，考慮除錯方案，設計測試資料並手工得出正確結果。「磨刀不誤砍柴工」。計算機各專業的學生應該能夠熟練運用高階語言的程式偵錯程式debug除錯程式。
上機除錯程式時要帶一本高階語言教材或手冊。除錯最好分模組進行，自底向上，即先除錯低層過程或函式。必要時可以另寫乙個呼叫驅動程式。
這種表面上麻煩的工作實際上可以大大降低除錯所面臨的複雜性，提高除錯工作效率。在除錯過程中可以不斷借助debug的各種功能，提高除錯效率。除錯中遇到的各種異常現象往往是預料不到的，此時不應「苦思具想」，而應動手確定疑點，通過修改程式來證實它或繞過它。
除錯正確後，認真整理源程式及其注釋，印出帶有完整注釋的且格式良好的源程式清單和結果。
5. 總結和整理實習報告
注意：在實踐中，有時候可能想檢驗自己的想法，這時可以上機嘗試一下，看看自己的思路是否可行。
課程設計報告統一用a4紙列印，並裝訂成冊，封面格式參見所附文件，正文格式要求參見附錄1。課程設計報告內容具體要求如下：
1. 課程設計實驗報告內容總體要求
1）給出問題分析過程
根據自身對課程的掌握程度，充分分析和理解問題的設計要求，給出較為明確、簡潔的設計思路。
2）給出資料結構描述
根據要解決的問題，考慮各種可能的資料結構型別，從中選擇一種較為有效的方法，並寫出採用的資料結構描述及其功用。
3）給出相應演算法設計
根據問題分析的結果，並確立好所選的資料結構描述，然後寫出合理的演算法設計過程，特別要注意所使用函式間的呼叫與被呼叫關係。
4）給出詳細程式清單
根據演算法的內容，用計算機語言（如c語言）編寫完整的程式，並將程式在機器上反覆除錯，直到結果正確為止，程式要求附上詳細註解。特別要注意演算法與程式的區別以及上下層模組間的介面處理。
5）給出程式執行結果
利用典型的測試用例，將資料輸入到程式執行過程中去，記下執行過程中螢幕顯示情況與相應結果。
2. 具體內容要求：報告包括以下7個內容：
1）以無歧義的陳述說明程式設計的任務，強調的是程式要做什麼？並明確規定：
(1) 輸入的形式和輸入值的範圍；
(2) 輸出的形式；
(3) 程式所能達到的功能；
(4) 測試資料：包括正確的輸入及其輸出結果和含有錯誤的輸入及其輸出結果。
2）概要設計
說明本程式中用到的所有抽象資料型別的定義、主程式的流程以及各程式模組之間的層次(呼叫)關係。
3）詳細設計
實現概要設計中定義的所有資料型別，對每個操作只需要寫出偽碼演算法；對主程式和其他模組也都需要寫出偽碼演算法(偽碼演算法達到的詳細程度建議為：按照偽碼演算法可以在計算機鍵盤直接輸入高階程式語言程式)；畫出函式和過程的呼叫關係圖。
4）除錯分析
內容包括：
(1) 除錯過程中遇到的問題是如何解決的以及對設計與實現的回顧討論和分析；
(2) 演算法的時空分析(包括基本操作和其他演算法的時間複雜度和空間複雜度的分析)
(3) 改進設想；
(4) 經驗和體會等。
5）使用者使用說明
說明如何使用你編寫的程式，詳細列出每一步的操作步驟。
6）測試結果
列出你的測試結果，包括輸入和輸出。這裡的測試資料應該完整和嚴格，最好多於需求分析中所列。
7）附錄
帶注釋的源程式，如果提交程式，可以只列出程式檔名的清單。
題目來自《資料結構題集（c語言版）》（下面簡稱「題集」），但要求可能會略作調整。如果沒有說明，就按原來要求。具體參看下面說明。
1． 約瑟夫環（題集79頁1.2題）
2． 集合的並、交和差運算（題集80頁1.3題）
編制乙個能演示執行集合的元素判定、子集判定、集合的交、集合的並、集合的差的程式，要求使用二叉排序樹表示集合。
3． 長整數的四則運算（題集80頁1.4題）
設計乙個實現任意長的整數進行加法運算的演示程式，利用陣列或雙向迴圈鍊錶實現長整數的儲存。採用每個陣列元素或每個結點含乙個0~9的數字處理方式，然後可進一步考慮題集上的實現提示。
4． 一元稀疏多項式計算器（題集81頁1.5題）
設計乙個一元稀疏多項式簡單計算器，可不實現減法。
5． 停車場管理（題集96頁2.1題）
6． 車廂排程（題集98頁2.3題）
7． 馬踏棋盤（題集98頁2.4題）
8． 算術表示式求值演示（題集99頁2.5題）
9． 簡單行編輯程式（題集118頁3.3題）
10．串基本操作的演示（題集119頁3.4題）
11．哈夫曼編/解碼器（題集149頁5.2題）
12．圖遍歷的演示（題集150頁5.3題）
13．最小生成樹問題（題集152頁5.6題）
14．雜湊表設計（題集166頁6.2題）
針對所在班級同學的「名字」設計乙個雜湊表，使得平均查詢長度不超過2，完成相應的建表和查表程式。要求分別使用開放位址法和鏈位址法來處理衝突，也就是實現兩種形式的雜湊表。
15．多關鍵字排序（題集169頁6.7題）
程式經常需要輸入輸出，所以可以在考慮採用什麼樣的資料結構時，考慮如何進行資料的輸入和輸出，可以把輸入和輸出分別實現為乙個函式。實現了輸入輸出功能，也為以後程式的除錯和測試帶來方便。
課程設計完成後的下一周的周一上午，也就是2023年12月27日，提交如下資料：
1． 課程設計報告。
2． 課程設計專案源**和相關資料，放到乙個目錄下，目錄名以學號加姓名方式命名。
成績評定綜合考慮程式源**、程式執行展示、對所提出的問題的回答情況以及課程設計報告的完成情況。
1．程式執行展示和對所提出的問題的回答，佔總分的50%。依據程式功能正確與否、程式介面是否友好、對所提出的問題是否回答進行評判。
資料結構實驗與課程設計指導書
資料結構 實驗指導書 資料結構課程組 廣東工業大學計算機學院 2014年4月 第1章概述 1.1 課程 教材和實驗 資料結構是電腦科學的演算法理論基礎和軟體設計的技術基礎，主要研究資訊的邏輯結構及其基本操作在計算機中的表示和實現。資料結構不僅是計算機專業的核心課程，而且已成為其他理工專業的熱門選修課...
2019版《資料結構A》課程設計指導書
基本功能 乙個完整的系統應具有以下功能 1.初始化 輸入一串字元 正文 計算不同字元 包括空格 的數目以及每種字元出現的頻率 以該種字元出現的次數作為其出現頻率 根據權值建立哈夫曼樹，輸出每一種字元的哈夫曼編碼。2.編碼 利用求出的哈夫曼編碼，對該正文 字串 進行編碼，並輸出。3.解碼 對於得到的一...
信管108資料結構課程設計指導書
淮陰工學院2008級 資料結構課程設計指導書 殷路王文豪 2010年4月10日 一 資料結構課程設計要求 學生必須仔細閱讀 資料結構 課程設計方案，認真主動完成課程設計的要求。有問題及時主動通過各種方式與教師聯絡溝通。學生要發揮自主學習的能力，充分利用時間，安排好課程設計的時間計畫，設計程式並除錯。...