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

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

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

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

12.3A類題目

12.4B類題目

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

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

12.1

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

12.2

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

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

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

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

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