數(shù)據(jù)結(jié)構(gòu)課程設計

數(shù)據(jù)結(jié)構(gòu)課程設計第一頁，共二十一頁，編輯于2023年，星期三第12章目錄

12.1課程設計的目的與內(nèi)容

12.2課程設計的內(nèi)容

12.3A類題目

12.4B類題目

12.4C類題目2第二頁，共二十一頁，編輯于2023年，星期三

本章精選了24個與數(shù)據(jù)結(jié)構(gòu)相關(guān)的典型應用題目，并按從易到難的順序分為A、B、C三個類別，通過一周或兩周的時間由學生獨立完成其中一個題目。要順利完成本章課題所規(guī)定的任務，需要復習前面各章節(jié)介紹的各種邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及基本算法，熟練掌握并理解前面各章節(jié)的知識要點，并對部分知識點進行相互串聯(lián)。由于部分課題對《計算機組成原理》和《算法分析與設計》等課程的內(nèi)容稍有涉及，認真完成本章的課題任務對后續(xù)課程的學習也將不無幫助。3第三頁，共二十一頁，編輯于2023年，星期三

12.1

課程設計的目的與內(nèi)容12.1.1課程設計的目的1．了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設計方法，培養(yǎng)獨立分析問題的能力；2．綜合運用所學的數(shù)據(jù)結(jié)構(gòu)基本理論和方法，提高在計算機應用中解決實際問題的能力；3．初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設計、程序編碼、程序調(diào)試、數(shù)據(jù)測試等基本方法和技能；4．訓練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者應該具備的科學的工作方法和作風。5．通過課程設計完成具有一定深度和難度的題目。6．編寫課程設計報告，鍛煉軟件開發(fā)文檔撰寫的基本方法。4第四頁，共二十一頁，編輯于2023年，星期三

12.2

課程設計的內(nèi)容1．問題分析和任務定義根據(jù)設計題目的要求，充分地分析和理解問題，明確問題要求做什么？限制條件是什么？2．邏輯設計對問題描述中涉及的操作對象定義相應的數(shù)據(jù)類型，并按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊，定義主程序模塊和各抽象數(shù)據(jù)類型。3．詳細設計定義相應的存儲結(jié)構(gòu)并寫出各函數(shù)的偽碼算法。在這個過程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡單和易于調(diào)試，抽象數(shù)據(jù)類型的實現(xiàn)盡可能做到數(shù)據(jù)封裝，基本操作的規(guī)格說明盡可能明確具體。5第五頁，共二十一頁，編輯于2023年，星期三4．程序編碼把詳細設計的結(jié)果進一步轉(zhuǎn)換為程序設計語言程序。同時加入一些注解，使程序邏輯概念清楚、維護方便。5．程序調(diào)試與測試程序調(diào)試采用自底向上，分模塊進行。即先調(diào)試低層函數(shù)，再逐級調(diào)試上一層的函數(shù)。通過程序調(diào)試熟練掌握調(diào)試工具的各種功能；設計測試數(shù)據(jù)確定疑點，通過修改程序來證實它或繞過它。程序調(diào)試正確后，認真整理源程序及其注釋，形成格式和風格良好的源程序清單。6．結(jié)果分析程序運行結(jié)果不但要包括正確的輸入及其輸出結(jié)果，而且還要人為的輸入一些含有錯誤的數(shù)據(jù)以考察其輸出結(jié)果的正確性。同時進行算法的時間復雜性和空間復雜性分析。7．編寫課程設計報告。6第六頁，共二十一頁，編輯于2023年，星期三12.1.3

課程設計報告1．課題分析以無歧義的陳述說明程序設計的任務，強調(diào)的是程序要做什么？并明確規(guī)定：（1）輸入的形式和輸入值的范圍；（2）輸出的形式；（3）程序所能達到的功能；（4）測試數(shù)據(jù)：包括正確的輸入及其輸出結(jié)果和含有錯誤的輸入及其輸出結(jié)果。2．總體設計說明本程序中用到的所有數(shù)據(jù)類型的定義、主程序的流程以及各程序模塊之間的層次（調(diào)用）關(guān)系。7第七頁，共二十一頁，編輯于2023年，星期三3．詳細設計實現(xiàn)總體設計中定義的所有數(shù)據(jù)類型，對每個操作只需要寫出偽碼算法；對主程序和其他模塊也都需要寫出偽碼算法；也可以采用流程圖、N–S圖或PAD圖進行描述，畫出函數(shù)和過程的調(diào)用關(guān)系圖。4．調(diào)試分析調(diào)試分析的內(nèi)容包括：（1）調(diào)試過程中遇到的問題是如何解決的，以及對程序設計與實現(xiàn)的討論和分析；（2）算法的時間復雜度和空間復雜度的分析；（3）對算法的改進設想；（4）程序調(diào)試的收獲和體會。8第八頁，共二十一頁，編輯于2023年，星期三5．用戶使用說明用戶使用說明是為了告訴用戶如何使用你編寫的程序，并舉例列出每一步的操作步驟。6．測試結(jié)果列出測試的輸入數(shù)據(jù)和程序運行以后的輸出結(jié)果，測試數(shù)據(jù)應該保證完整和嚴格。7．參考文獻列出參考資料和書籍。9第九頁，共二十一頁，編輯于2023年，星期三12.1.4課程設計的考核課程設計的成績分三部分給定。其中：設計過程的答辯占60％，設計作品（源代碼）占20％，課程設計報告占20％。成績評定按照優(yōu)秀、良好、中、及格，不及格五級或者按百分制實施。本課程需要提交歸檔的材料清單如下：（1）課程設計報告（電子稿和打印稿各一份）。（2）程序源代碼文件夾（文件夾中只保留.c或.cpp、.dll、.lib等必須文件，編譯過程中產(chǎn)生的各種參考文件、工程文件和Debug文件夾等提交時一律刪除）。10第十頁，共二十一頁，編輯于2023年，星期三11.2課程設計的要求1.課題的分類與選擇為了使不同編程基礎(chǔ)的同學通過課程設計都能有所提高，使所有同學都學有所獲，根據(jù)課程設計題目的難度由低到高，將所有課題分為A、B、C三個類別。教師可以根據(jù)學生的學習基礎(chǔ)，結(jié)合學生本人的意愿，先對學生進行分組，然后各個小組以抽簽的方式?jīng)Q定具體的課程設計題目。學生也可以根據(jù)個人的能力自行選擇有一定難度的其它數(shù)據(jù)結(jié)構(gòu)課程設計課題，但是自選課題必須預先向指導老師提出申請，說明課題的內(nèi)容、難度，以及實現(xiàn)的目標，經(jīng)老師同意并立項以后方可進行。11第十一頁，共二十一頁，編輯于2023年，星期三

2.課程設計的要求課程設計按照教學要求需要1-2周時間完成，兩周中每天至少要上機3-4小時來調(diào)試程序，總共至少要上機調(diào)試程序30小時。為保證質(zhì)量，要求每個學生將每天的上機調(diào)試程序的時間記錄下來，作為評判成績的標準之一。對題目中要求的功能進行分析，并且設計解決此問題的數(shù)據(jù)存儲結(jié)構(gòu)（有些課題中部分存儲結(jié)構(gòu)已經(jīng)指定，則可采用指定的存儲結(jié)構(gòu)）和算法。給出實現(xiàn)算法功能的一組或多組測試數(shù)據(jù)，程序調(diào)試通過以后，按照此測試數(shù)據(jù)進行程序運行的數(shù)據(jù)測試。程序要有基本的容錯功能。不但能夠在數(shù)據(jù)正常情況下運行，而且當數(shù)據(jù)出現(xiàn)錯誤時，應避免出現(xiàn)死循環(huán)。12第十二頁，共二十一頁，編輯于2023年，星期三課程設計課題總體要求如下：（1）利用C或C++實現(xiàn)課題相應的程序，源程序要按照課程設計規(guī)定的規(guī)則來編寫。（2）系統(tǒng)功能全部采用菜單控制，所有程序應上機調(diào)試通過并運行正確。（3）課程設計程序全部調(diào)試通過以后，也可以對課題的算法提出改進方案，并比較不同算法的優(yōu)缺點。（4）課程設計報告中應給出課題的總體分析、詳細設計、算法過程的具體分析、系統(tǒng)所涉及的邏輯結(jié)構(gòu)圖、數(shù)據(jù)所采用的存儲結(jié)構(gòu)圖、程序流程圖、采用的測試數(shù)據(jù)及其結(jié)果分析、算法時間和空間復雜度的分析等。（5）課程設計報告正文不得少于A4紙10頁（6）如果程序采用C#或Java等其它課堂上尚未開設的編程語言實現(xiàn)，必須預先向指導老師提出申請。13第十三頁，共二十一頁，編輯于2023年，星期三1１.3A類題目A類課題共6個，是難度較低的課題。12.3.1課題A1：多項式運算1．設計目的（1）掌握線性表的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。（2）掌握線性表的插入、刪除等基本運算。（3）掌握線性表的典型應用——多項式運算（加、減、乘、除[選做]）。2．主要內(nèi)容實現(xiàn)順序結(jié)構(gòu)或鏈式結(jié)構(gòu)的多項式加減乘除運算，其中加法、減法和乘法功能為必做，除法功能為選做。14第十四頁，共二十一頁，編輯于2023年，星期三3．設計要求（1）如果有兩個同學同時完成該課題，要求分別采用順序和鏈式兩種存儲結(jié)構(gòu)。（2）如果多項式采用順序結(jié)構(gòu)存儲，則多項式運算的最高次應能達到。（3）通過菜單選擇項輸入兩個多項式，通過菜單依次求得這兩個多項式加、減、乘、除[選做]的運行結(jié)果，并比較程序運行結(jié)果和手工計算結(jié)果是否一致。15第十五頁，共二十一頁，編輯于2023年，星期三12.3.2課題A2：求最小生成樹【基于鄰接矩陣存儲】1．設計目的（1）掌握無向圖（或網(wǎng)）的鄰接矩陣存儲結(jié)構(gòu)；（2）掌握基于鄰接矩陣存儲結(jié)構(gòu)無向圖的遍歷方法。（3）掌握利用Prim或Kruskal算法求解最小生成樹的過程。2．主要內(nèi)容（1）輸入給定無向網(wǎng)的頂點總數(shù)和所有頂點標志；（2）輸入無向網(wǎng)中邊的總數(shù)，并利用循環(huán)依次輸入各條邊的端點標志及權(quán)值，建立該無向網(wǎng)的鄰接矩陣存儲結(jié)構(gòu)；（3）用Prim或者Kruskal算法求該無向網(wǎng)最小生成樹。16第十六頁，共二十一頁，編輯于2023年，星期三3．設計要求（1）如果有兩個同學同時完成該課題，要求分別采用Prim和Kruskal算法求得該無向網(wǎng)的最小生成樹。（2）為方便編程，每個頂點均用一個英文字母作為標志。（3）按選取邊的順序輸出最小生成樹的各條邊。17第十七頁，共二十一頁，編輯于2023年，星期三12.3.3課題A3：非遞歸求解Hanoi問題12.3.4課題A4：迷宮問題12.3.5課題A5：中綴表達式轉(zhuǎn)后綴并求值【運算對象為個位數(shù)】12.3.6課題A6：二叉樹的層次遍歷18第十八頁，共二十一頁，編輯于2023年，星期三12.4B類題目

B類課題共9個，是難度適中的課題。12.4.1課題B1：哈希查找的實現(xiàn)與分析12.4.2課題B2：有向無環(huán)圖的判定及拓撲排序12.4.3課題B3：浮點數(shù)的IEEE754標準格式轉(zhuǎn)換12.4.4課題B4：文件記錄讀取并排序12.4.5課題B5：大整數(shù)運算12.4.6課題B6：平衡二叉樹的構(gòu)造及輸出12.4.7課題B7：二叉樹的中序線索化及其非棧非遞歸遍歷12.4.8課題B8：稀疏矩陣的運算12.4.9課題B9：基于十字鏈表有向圖的遍歷19第十九頁，共二十一頁，編輯于2023年，星期三12.5C類題目

C類課題共9個，是難度較高的課題。12.5.1課題C1：求AOE網(wǎng)的關(guān)鍵路徑12.5.2課題C2：求有向圖的強連通分量12.5.3課題C3：非遞歸方式遍歷二叉樹12.5.4課題C4：求最小生成樹【