資料結構課程設計

指導書山東建築大學

電腦科學與技術學院

二○○六年十二月

課程設計基本情況：

課程名稱：資料結構課程設計

相關課程：c語言程式設計、visual c++程式設計、資料結構

適合專業：電腦科學與技術、網路工程、軟體工程

設計週數：2周

學分： 2學分

開課學期：第4學期

開課單位：電腦科學與技術學院

一、課程設計的教學目的和任務

1、使學生進一步理解和掌握所學的各種基本抽象資料型別的邏輯結構、儲存結構和操作實現演算法，以及它們在程式中的使用方法。

2、使學生初步掌握軟體開發過程的問題分析、設計、編碼、測試等基本方法和基本技能。

3、使學生掌握使用各種計算機資料和有關參考資料，提高學生進行程式設計的基本能力。

4、使學生能用系統的觀點和軟體開發一般規範進行軟體開發，培養軟體工作者所應具備的科學的工作方法和作風。

二、課程設計的主要內容

1．問題分析和任務定義。根據設計題目的要求，充分地分析和理解問題，明確問題要求做什麼？限制條件是什麼？

2．邏輯設計。對問題描述中涉及的操作物件定義相應的資料型別，並按照以資料結構為中心的原則劃分模組，定義主程式模組和各抽象資料型別。邏輯設計的結果應寫出每個抽象資料型別的定義(包括資料結構的描述和每個基本操作的功能說明)，各個主要模組的演算法，並畫出模組之間的呼叫關係圖。

3．物理設計。定義相應的儲存結構並寫出各函式的偽**演算法。在這個過程中，要綜合考慮系統功能，使得系統結構清晰、合理、簡單和易於除錯，抽象資料型別的實現盡可能做到資料封裝，基本操作的規格說明盡可能明確具體。

詳細設計的結果是對資料結構和基本操作作出進一步的求精，寫出資料儲存結構的型別定義，寫出函式形式的演算法框架。

4．程式編碼。把詳細設計的結果進一步求精為程式語言程式。同時加入一些註解和斷言，使程式中邏輯概念清楚。

5．程式除錯與測試。採用自底向上，分模組進行，即先除錯低層函式。能夠熟練掌握除錯工具的各種功能，設計測試資料確定疑點，通過修改程式來證實它或繞過它。

除錯正確後，認真整理源程式及其注釋，形成格式和風格良好的源程式清單和結果。

6．結果分析。程式執行結果包括正確的輸入及其輸出結果和含有錯誤的輸入及其輸出結果。演算法的時間、空間複雜性分析。

7．編寫課程設計報告。

三、課程設計的基本教學要求

1、鞏固和加深對資料結構基本知識的理解，提高綜合運用課程知識的能力。

2、培養學生自學參考書籍，查閱手冊、圖表和文獻資料的能力。

3、通過實際課程設計，初步掌握簡單軟體的分析方法和設計方法。

4、了解與課程有關的工程技術規範，能正確解釋和分析實驗結果。

5、詳細情況參考《資料結構課程設計教學大綱》。

四、課程設計報告的規範

課程設計報告要求規範書寫。應當包括如下八個部分：

1、問題描述：描述要求程式設計解決的問題。

2、基本要求：給出程式要達到的具體的要求。

3、測試資料：設計測試資料，或具體給出測試資料。要求測試資料能全面地測試所設計程式的功能。

4、演算法思想：描述解決相應問題演算法的設計思想。

5、模組劃分：描述所設計程式的各個模組（即函式）功能。

6、資料結構：給出所使用的基本抽象資料型別,所定義的具體問題的資料型別,以及新定義的抽象資料型別。

7、源程式：給出所有源程式清單，要求程式有充分的注釋語句，至少要注釋每個函式引數的含義和函式返回值的含義。

8、測試情況：給出程式的測試情況，並分析執行結果。

五、注意事項

1、學生必須仔細閱讀課程設計任務書，認真主動完成課程設計的要求。有問題及時主動通過各種方式與教師聯絡溝通。

2、學生要發揮自主學習的能力，充分利用時間，安排好課程設計的進度，並在課程設計過程中不斷檢查自己的計畫完成情況，及時向教師匯報。

3、課程設計按照教學要求需要兩周時間完成，兩周中每天（按每週5天）至少要上機4小時來除錯程式，總共至少要上機除錯程式40小時。

4、程設計需要學生完成兩項工作，乙個是把基本資料結構改寫成c++，這是每個學生都要做的。第二是所給的任務書中選擇乙個。工作量不飽滿者，不能及格。

如果要獲得優秀成績必須完成2題以上。(建議3-4個學生一組，每個學生主持完成任務的乙個環節，最好，一組布置3-4個題目，這樣，所有的同學可以參與所有環節的主持工作，得到較充分的鍛鍊。)

六、課程設計需要提交的報告

1. 課程設計報告（1份，a4紙列印，同時包括乙份電子版）

報告要求版面清晰，格式規範，否則重新編寫。報告內容要求參見附錄二。

2. 完整的程式系統（電子方式提交）

能夠對輸入產生相應的輸出，同時盡量的完成視覺化演示。該部分包括源**和可執行檔案兩個部分。

3. 答辯報告（編寫power point答辯報告，電子方式提交）

要求突出重點，思路清晰。同時就此報告準備答辯。

所有以電子方式提交的檔案全部存在乙個目錄中，並對其進行壓縮（用winrar或winzip均可），壓縮後的檔案按規定格式進行命名，命名格式為：學號+姓名.rar（如2004111李盛恩.

rar）。

六、成績評定標準

出勤20%，課程設計說明書50%，成果展示30%。

七、參考資料

1. 嚴蔚敏, 吳偉民. 資料結構. 清華大學出版社, 2005.11

2. 譚浩強. c語言程式設計. 清華大學出版社, 2005.11

3. 範輝. visual c++程式設計. 高等教育出版社

八、設計報告的內容

設計結束後要寫出課程設計報告，以作為整個課程設計評分的書面依據和存檔材料。設計報告以規定格式的電子文件書寫、列印並裝訂，排版及圖、表要清楚、工整。內容及要求如下：

封面：題目、班級、姓名、學號、指導教師和完成日期。

正文包括以下7個內容：

1．需求分析

以無歧義的陳述說明程式設計的任務，強調的是程式要做什麼？並明確規定：

(1) 輸入的形式和輸入值的範圍；

(2) 輸出的形式；

(3) 程式所能達到的功能；

(4) 測試資料：包括正確的輸入及其輸出結果和含有錯誤的輸入及其輸出結果。

2．概要設計

說明本程式中用到的所有抽象資料型別的定義、主程式的流程以及各程式模組之間的層次(呼叫)關係。

3．詳細設計

實現概要設計中定義的所有資料型別，對每個操作只需要寫出偽碼演算法；對主程式和其他模組也都需要寫出偽碼演算法(偽碼演算法達到的詳細程度建議為：按照偽碼演算法可以在計算機鍵盤直接輸入高階程式語言程式)；可採用流程圖 n – s 圖或pad圖進行描述，畫出函式和過程的呼叫關係圖。

4．除錯分析

內容包括：

a．除錯過程中遇到的問題是如何解決的以及對設計與實現的回顧討論和分析；

b．演算法的時空分析(包括基本操作和其他演算法的時間複雜度和空間複雜度的分析)和改進設想；

c．經驗和體會等。

5．使用者使用說明

說明如何使用你編寫的程式，詳細列出每一步的操作步驟。

6．測試結果

列出你的測試結果，包括輸入和輸出。這裡的測試資料應該完整和嚴格，最好多於需求分析中所列。

7．參考文獻

列出參考的相關資料和書籍。

九、大綱執筆人和審定人

編寫人：張志軍

審核人：牛小飛

批准人：李盛恩

編寫日期：2023年12月

附錄課程設計報告範例

一、問題描述：

設編號為1,2,…,n(n>0)個人按順時針方向圍坐一圈，每人持有乙個正整數密碼。開始時任意給出乙個報數上限值m，從第乙個人開始順時針方向自1起順序報數，報到m時停止報數，抱m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下乙個人起重新自1起順序報數；如此下去，直到所有人全部出列為止。要求設計乙個程式模擬此過程，並給出出列人的編號序列。

二、基本要求：

（1）初始報數上限值m和測試資料在程式中確定；

（2）用帶頭結點的單迴圈鍊錶作資料元素的儲存結構；

（3）把帶頭結點的單迴圈鍊錶作為抽象資料型別設計。

三、測試資料：

n = 7，七個人的密碼依次為3,1,7,2,4,8,4

初始報數上限值m = 20

四、演算法思想：

jesephring()函式是實現問題要求的主要函式，其演算法思想是：從1至m對帶頭結點的單迴圈鍊錶迴圈計數，到m時，輸出該結點的編號值，將該結點的密碼作為新的m值，再從該結點的下乙個結點起重新自1起迴圈計數；如此下去，直到單迴圈鍊錶空時迴圈過程結束。

五、模組劃分：

（1）帶頭結點的單迴圈鍊錶抽象資料型別sclinlist，其中包括基本操作的函式有：初始化操作函式、插入乙個結點操作函式、刪除乙個結點操作函式、取乙個結點資料操作函式和判表是否非空操作函式。該抽象資料型別檔名為sclinlist.

h。（2）void sclldeleteafter(sclnode *p)，其功能是刪除帶頭結點的單迴圈鍊錶中指標p所指結點的下乙個結點。這是對帶頭結點的單迴圈鍊錶抽象資料型別sclinlist，補充本問題需要的乙個操作函式。

（3）void jesephring(sclnode *head, int m)，其功能是對帶頭結點的單迴圈鍊錶head,以m為初始報數上限值實現問題要求。

（4）void main(void)，主函式，功能是給出測試資料值，建立測試資料值的帶頭結點單迴圈鍊錶，呼叫jesephring()函式實現問題要求。

六、資料結構：

（1）資料型別datatype定義如下：

typedef struct datatype;

（2）帶頭結點單迴圈鍊錶抽象資料型別sclinlist。

（3）帶頭結點單迴圈鍊錶抽象資料型別的結點結構定義如下：

typedef struct node sclnode;

七、源程式：

源程式存放在兩個檔案中，檔案sclinlist.h是帶頭結點單迴圈鍊錶抽象資料型別，檔案exam3-9.c是主程式。

1. 檔案sclinlist.h：

typedef struct node sclnode; /*結點結構定義*/

void scllinitiate(sclnode **head) /*初始化*/

int scllinsert(sclnode *head, int i, datatype x) /*插入乙個結點*/

資料結構課程設計

資料結構課程設計

資料結構課程設計

資料結構課程設計

相關推薦