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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)第1頁(yè)，課件共21頁(yè)，創(chuàng)作于2023年2月第12章目錄

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

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

12.3A類(lèi)題目

12.4B類(lèi)題目

12.4C類(lèi)題目2第2頁(yè)，課件共21頁(yè)，創(chuàng)作于2023年2月

本章精選了24個(gè)與數(shù)據(jù)結(jié)構(gòu)相關(guān)的典型應(yīng)用題目，并按從易到難的順序分為A、B、C三個(gè)類(lèi)別，通過(guò)一周或兩周的時(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í)也將不無(wú)幫助。3第3頁(yè)，課件共21頁(yè)，創(chuàng)作于2023年2月

12.1

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

12.2

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

課程設(shè)計(jì)報(bào)告1．課題分析以無(wú)歧義的陳述說(shuō)明程序設(shè)計(jì)的任務(wù)，強(qiáng)調(diào)的是程序要做什么？并明確規(guī)定：（1）輸入的形式和輸入值的范圍；（2）輸出的形式；（3）程序所能達(dá)到的功能；（4）測(cè)試數(shù)據(jù)：包括正確的輸入及其輸出結(jié)果和含有錯(cuò)誤的輸入及其輸出結(jié)果。2．總體設(shè)計(jì)說(shuō)明本程序中用到的所有數(shù)據(jù)類(lèi)型的定義、主程序的流程以及各程序模塊之間的層次（調(diào)用）關(guān)系。7第7頁(yè)，課件共21頁(yè)，創(chuàng)作于2023年2月3．詳細(xì)設(shè)計(jì)實(shí)現(xiàn)總體設(shè)計(jì)中定義的所有數(shù)據(jù)類(lèi)型，對(duì)每個(gè)操作只需要寫(xiě)出偽碼算法；對(duì)主程序和其他模塊也都需要寫(xiě)出偽碼算法；也可以采用流程圖、N–S圖或PAD圖進(jìn)行描述，畫(huà)出函數(shù)和過(guò)程的調(diào)用關(guān)系圖。4．調(diào)試分析調(diào)試分析的內(nèi)容包括：（1）調(diào)試過(guò)程中遇到的問(wèn)題是如何解決的，以及對(duì)程序設(shè)計(jì)與實(shí)現(xiàn)的討論和分析；（2）算法的時(shí)間復(fù)雜度和空間復(fù)雜度的分析；（3）對(duì)算法的改進(jìn)設(shè)想；（4）程序調(diào)試的收獲和體會(huì)。8第8頁(yè)，課件共21頁(yè)，創(chuàng)作于2023年2月5．用戶(hù)使用說(shuō)明用戶(hù)使用說(shuō)明是為了告訴用戶(hù)如何使用你編寫(xiě)的程序，并舉例列出每一步的操作步驟。6．測(cè)試結(jié)果列出測(cè)試的輸入數(shù)據(jù)和程序運(yùn)行以后的輸出結(jié)果，測(cè)試數(shù)據(jù)應(yīng)該保證完整和嚴(yán)格。7．參考文獻(xiàn)列出參考資料和書(shū)籍。9第9頁(yè)，課件共21頁(yè)，創(chuàng)作于2023年2月12.1.4課程設(shè)計(jì)的考核課程設(shè)計(jì)的成績(jī)分三部分給定。其中：設(shè)計(jì)過(guò)程的答辯占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等必須文件，編譯過(guò)程中產(chǎn)生的各種參考文件、工程文件和Debug文件夾等提交時(shí)一律刪除）。10第10頁(yè)，課件共21頁(yè)，創(chuàng)作于2023年2月11.2課程設(shè)計(jì)的要求1.課題的分類(lèi)與選擇為了使不同編程基礎(chǔ)的同學(xué)通過(guò)課程設(shè)計(jì)都能有所提高，使所有同學(xué)都學(xué)有所獲，根據(jù)課程設(shè)計(jì)題目的難度由低到高，將所有課題分為A、B、C三個(gè)類(lèi)別。教師可以根據(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)，說(shuō)明課題的內(nèi)容、難度，以及實(shí)現(xiàn)的目標(biāo)，經(jīng)老師同意并立項(xiàng)以后方可進(jìn)行。11第11頁(yè)，課件共21頁(yè)，創(chuàng)作于2023年2月

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

B類(lèi)課題共9個(gè)，是難度適中的課題。12.4.1課題B1：哈希查找的實(shí)現(xiàn)與分析12.4.2課題B2：有向無(wú)環(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：平衡二叉樹(shù)的構(gòu)造及輸出12.4.7課題B7：二叉樹(shù)的中序線(xiàn)索化及其非棧非遞歸遍歷12.4.8課題B8：稀疏矩陣的運(yùn)算12.4.9課題B9：基于十字鏈表有向圖的遍歷19第19頁(yè)，課件共21頁(yè)，創(chuàng)作于2023年2月12.5C類(lèi)題目

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