資料結構課程設計

題目學院專業班級

學生姓名

指導教師

2016 年06 月2 9日

一、課程設計目的 3

二、課程設計步驟 3

三、課程設計內容 4

四、課程設計報告 6

五、提交材料 6

六、考核方式與評分標準 7

七、參考文獻 8

附錄1 齊齊哈爾大學軟體工程系課程設計說明書（報告）撰寫規範 9

《資料結構與演算法分析》課程設計培養計算機專業的學生的演算法程式設計能力。通過上機實驗，可以培養學生程式設計的方法和技巧，提高學生編制清晰、合理、可讀性好的系統程式的能力，加深對資料結構課程和演算法的理解。使學生更好地掌握資料結構的基本概念、基本原理、及基本演算法,具有分析演算法、設計演算法、構造和開發較複雜演算法的基本能力。

要求學生能綜合運用《資料結構與演算法分析》的相關知識，培養學生上機解決一些與實際應用結合緊密的、規模較大的問題的能力，通過分析、設計、編碼、除錯等各環節的訓練，使學生深刻理解、牢固掌握資料結構和演算法設計技術，掌握分析實際問題的能力並提高c語言程式設計技巧，培養良好的程式設計風格。

課程設計要求獨立完成，題目自選（參考題目見三，也可自擬）,但需要老師確認(6月16日前定題)，一人一題，要求程式有能採用互動式工作方式的介面進行功能的選擇,只能用檔案儲存資料和處理資料不能使用資料庫。要求在教學周的第18週前完成。

隨著計算機效能的提高，它所面臨的軟體開發的複雜度也日趨增加。然而，編制乙個10000行的程式的難度絕不僅僅是乙個5000行的程式的兩倍，因此軟體開發需要系統的方法。一種常用的軟體開發方法，是將軟體開發過程分為分析、設計、實現和維護四個階段。

雖然資料結構課程中的課程設計的複雜度遠不如(從實際問題中提出來的)乙個「真正的」軟體，但為了培養乙個軟體工作者所應具備的科學工作的方法和作風，完成課程設計的應有如下的5個步驟：

1. 問題分析和任務定義

通常，課程設計題目的陳述比較簡潔，或者說是有模稜兩可的含義。因此，在進行設計之前，首先應該充分地分析和理解問題，明確問題要求做什麼，限制條件是什麼。注意：

本步驟強調的是做什麼，而不是怎麼做。對問題的描述應避開演算法和所涉及的資料型別，而是對所需完成的任務作出明確的回答。例如：

輸入資料的型別、值的範圍以及輸入的形式；輸出資料的型別、值的範圍及輸出的形式；若是會話式的輸入，則結束標誌是什麼，是否接受非法的輸入，對非法輸入的回答方式是什麼等等。這一步還應該為除錯程式準備好測試資料，包括合法的輸入資料和非法形式輸入的資料。

2. 資料型別和系統設計

在設計這一步驟中需分邏輯設計和詳細設計兩步實現。邏輯設計指的是，對問題描述中涉及的操作物件定義相應的資料型別，並按照以資料結構為中心的原則劃分模組，定義主程式模組和各抽象資料型別；詳細設計則為定義相應的儲存結構並寫出各過程和函式的偽碼演算法。在這個過程中，要綜合考慮系統功能，使得系統結構清晰、合理、簡單和易於除錯，抽象資料型別的實現盡可能做到資料封裝，基本操作的規格說明盡可能明確具體。

作為邏輯設計的結果，應寫出每個抽象資料型別的定義(包括資料結構的描述和每個基本操作的規格說明)，各個主要模組的演算法，並畫出模組之間的呼叫關係圖。詳細設汁的結果是對資料結構和基本操作的規格說明作出進一步的求精，寫出資料儲存結構的型別定義，按照演算法書寫規範用類c語言寫出過程或函式形式的演算法框架。在求精的過程中，應盡量避免陷入語言細節，不必過早表述輔助資料結構和區域性變數。

3. 編碼實現和靜態檢查

編碼是把詳細設計的結果進一步求精為程式語言程式。程式的每行不要超過60個字元。每個過程(函式)體，即不計首部和規格說明部分，一般不要超過40行。

最長不得超過60 行，否則應該分割成較小的過程(函式)。要控制語句連續巢狀的深度。如何編寫程式才能較快地完成除錯是特別要注意的問題。

對於程式設計很熟練的讀者，如果基於詳細設計的偽碼演算法就能直接在鍵盤上輸入程式的話，則可以不必用筆在紙上寫出編碼，而將這一步的工作放在上機準備之後進行，即在上機除錯之前直接用鍵盤輸入。然而，不管你是否寫出編碼的程式，在上機之前，認真的靜態檢查卻是必不可少的。多數初學者在編好程式後處於以下兩種狀態之一：

一種是對自己的「精心作品」的正確性確信不疑；另一種是認為上機前的任務已經完成，糾查錯誤是上機的工作。這兩種態度是極為有害的。事實上，非訓練有素的程式設計者編寫的程式長度超過50 行時，極少不含有除語法錯誤以外的錯誤。

上機動態除錯決不能代替靜態檢查，否則除錯效率將是極低的。靜態檢查主要有兩種方法，一是用一組測試資料手工執行程式(通常應先分模組檢查)；二是通過閱讀或給別人講解自己的程式而深入全面地理解程式邏輯，在這個過程中再加入一些註解和斷言。如果程式中邏輯概念清楚，後者將比前者有效。

4. 上機準備和上機除錯

上機準備包括以下幾個方面：

(1) 高階語言文字(體現與編譯程式使用者手冊)的擴充和限制。例如，有些c編譯程式限制for語句的迴圈控制變數為區域性簡單變數等。

(2) 如果用c語言，要特別注意平時慣用的類c語言與標準c語言之間的細微差別。

(3) 熟悉機器的作業系統和語言整合環境的使用者手冊，尤其是最常用的命令操作，以便順利進行上機的基本活動。

(4) 掌握除錯工具，考慮除錯方案，設計測試資料並手工得出正確結果。「磨刀不誤砍柴工」。計算機各專業的學生應該能夠熟練運用高階語言的程式偵錯程式debug除錯程式。

上機除錯程式時要帶一本高階語言教材或手冊。除錯最好分模組進行，自底向上，即先除錯低層過程或函式。必要時可以另寫乙個呼叫驅動程式。

這種表面上麻煩的工作實際上可以大大降低除錯所面臨的複雜性，提高除錯工作效率。在除錯過程中可以不斷借助debug的各種功能，提高除錯效率。除錯中遇到的各種異常現象往往是預料不到的，此時不應「苦思具想」，而應動手確定疑點，通過修改程式來證實它或繞過它。

除錯正確後，認真整理源程式及其注釋，印出帶有完整注釋的且格式良好的源程式清單和結果。

5. 總結和整理實習報告

注意：在實踐中，有時候可能想檢驗自己的想法，這時可以上機嘗試一下，看看自己的思路是否可行。

參考題目：

1．二叉樹的應用－哈夫曼樹（電文的編碼和解碼）

2．運動會分數統計

3．學生成績管理系統

4．簡易客房管理系統

5．其他型別管理系統的題目

①人事檔案管理系統

②圖書管理系統

③進銷存貨物管理系統

④職工工資管理系統

6. 稀疏矩陣運算器

7. 長整數的四則運算

8. 校園導遊諮詢

10．停車場管理

11其餘題目：（必須事先得到指導老師允許）

程式經常需要輸入輸出，所以可以在考慮採用什麼樣的資料結構時，考慮如何進行資料的輸入和輸出，可以把輸入和輸出分別實現為乙個函式。實現了輸入輸出功能，也為以後程式的除錯和測試帶來方便。

課程設計報告統一用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）附錄

帶注釋的源程式，如果提交程式，可以只列出程式檔名的清單。

課程設計完成後的下一周的周一上午，也就是2023年6月28-29日，提交如下資料並答辯：

1．課程設計報告。

課程設計報告總體上主要包括以下幾個部分：

1）封面

2）考核方式與評分標準(見六)

3）目錄

4）課程設計報告正文

5）使用說明

2.完整的軟體系統

最終必須向指導老師提交完整的程式源**(.c和.cpp以及.

h為字尾的檔案)、資料檔案以及使用說明檔案等。源**檔案要特別注意程式設計規範、**風格，關鍵**需有合理的注釋，不含任何無用**；資料檔案內要求有一定數量的「真實」資料（如對於記錄檔案，需要有8條以上記錄）；使用說明檔案的第一行，需要給出設計者的學號、姓名，後面為其它說明。

課程設計專案源**和相關資料，放到乙個目錄下，目錄名以學號加姓名方式命名。

綜合實踐1評分表

資料結構課程設計

資料結構課程設計

資料結構課程設計

資料結構課程設計

相關推薦