《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書(shū)

1、實(shí)驗(yàn)指導(dǎo)書(shū)實(shí)驗(yàn)指導(dǎo)書(shū)課程名稱：數(shù)據(jù)結(jié)構(gòu)課程名稱：數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)課程組課程組 目 錄前 言 .1一、實(shí)驗(yàn)的作用和目的 .2二、實(shí)驗(yàn)方式與考核方式 .2三、實(shí)驗(yàn)要求 .3四、實(shí)驗(yàn)報(bào)告要求 .4五、實(shí)驗(yàn)內(nèi)容 .5實(shí)驗(yàn)一 線性表應(yīng)用 .5實(shí)驗(yàn)二 棧與隊(duì)列應(yīng)用 .10實(shí)驗(yàn)三 二叉樹(shù)的操作 .14實(shí)驗(yàn)四 圖的遍歷 .18實(shí)驗(yàn)五 查找算法應(yīng)用 .21六、選做實(shí)驗(yàn)內(nèi)容 .24實(shí)驗(yàn)六 排序 .24實(shí)驗(yàn)七 數(shù)組和廣義表 .26實(shí)驗(yàn)八 串 .271前前 言言數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)與技術(shù)及相關(guān)專業(yè)的一門(mén)重要專業(yè)基礎(chǔ)課，它主要介紹線性結(jié)構(gòu)、樹(shù)型結(jié)構(gòu)、圖狀結(jié)構(gòu)三種邏輯結(jié)

2、構(gòu)元素的存儲(chǔ)實(shí)現(xiàn)，在此基礎(chǔ)上介紹一些典型算法，以及算法的時(shí)間、空間效率分析。這門(mén)課程的主要任務(wù)是培養(yǎng)學(xué)生的算法設(shè)計(jì)能力及良好的程序設(shè)計(jì)習(xí)慣。通過(guò)本課程的學(xué)習(xí)，使學(xué)生熟練地掌握數(shù)據(jù)結(jié)構(gòu)的內(nèi)在邏輯關(guān)系及其在計(jì)算機(jī)中的表示方法（存儲(chǔ)結(jié)構(gòu)） ，以及相關(guān)基本操作的算法實(shí)現(xiàn)；掌握典型算法的設(shè)計(jì)思想及程序?qū)崿F(xiàn)；熟悉各種數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)科學(xué)中的基本應(yīng)用；培養(yǎng)和訓(xùn)練學(xué)生結(jié)合實(shí)際應(yīng)用，根據(jù)實(shí)際問(wèn)題選取合適的數(shù)據(jù)結(jié)構(gòu)、存儲(chǔ)方案設(shè)計(jì)出簡(jiǎn)潔、高效、實(shí)用的算法；并為學(xué)習(xí)操作系統(tǒng) 、 編譯原理 、 數(shù)據(jù)庫(kù)原理等后續(xù)課程和研制開(kāi)發(fā)各種系統(tǒng)和應(yīng)用軟件打下扎實(shí)的理論與實(shí)踐基礎(chǔ)。學(xué)習(xí)這門(mén)課程，習(xí)題和實(shí)驗(yàn)是兩個(gè)關(guān)鍵環(huán)節(jié)。學(xué)生理解算法

3、，上機(jī)實(shí)驗(yàn)是最佳的途徑之一。因此，實(shí)驗(yàn)環(huán)節(jié)的好壞是學(xué)生能否學(xué)好數(shù)據(jù)結(jié)構(gòu)的關(guān)鍵。為了更好地配合學(xué)生實(shí)驗(yàn)，特編寫(xiě)此實(shí)驗(yàn)指導(dǎo)書(shū)。實(shí)驗(yàn)指導(dǎo)書(shū)按照實(shí)驗(yàn)教學(xué)大綱的要求，為每個(gè)主要的知識(shí)點(diǎn)精選了的典型的實(shí)驗(yàn)題目，對(duì)每個(gè)實(shí)驗(yàn)題目提出具體實(shí)現(xiàn)要求，并對(duì)算法的實(shí)現(xiàn)進(jìn)行提示，希望對(duì)同學(xué)實(shí)驗(yàn)有所幫助。數(shù)據(jù)結(jié)構(gòu)課程組2005 年 5 月2一、一、實(shí)驗(yàn)的作用和目的實(shí)驗(yàn)的作用和目的實(shí)驗(yàn)課是對(duì)學(xué)生的一種全面綜合訓(xùn)練，是與課堂教學(xué)、課后練習(xí)相輔相成的必不可少的一個(gè)教學(xué)環(huán)節(jié)。數(shù)據(jù)結(jié)構(gòu)是一門(mén)實(shí)踐性很強(qiáng)的軟件基礎(chǔ)課程，為了學(xué)好這門(mén)課，每個(gè)學(xué)生必須完成一定數(shù)量的上機(jī)實(shí)驗(yàn)作業(yè)。通過(guò)課程的上機(jī)實(shí)驗(yàn)，可使學(xué)生深刻理解各種邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)的

4、特性；學(xué)會(huì)如何把書(shū)上學(xué)到的知識(shí)用于解決實(shí)際問(wèn)題，培養(yǎng)軟件工作所需要的動(dòng)手能力；另一方面，能使書(shū)上的知識(shí)變“活” ，起到深化理解和靈活掌握教學(xué)內(nèi)容的目的。 本課程的實(shí)驗(yàn)著眼于原理與應(yīng)用的結(jié)合點(diǎn)。通過(guò)課程的實(shí)驗(yàn)，培養(yǎng)學(xué)生分析問(wèn)題，并能針對(duì)實(shí)際應(yīng)用問(wèn)題選擇適用的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)和實(shí)現(xiàn)相應(yīng)算法。同時(shí)，在程序設(shè)計(jì)方法以及上機(jī)操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴(yán)格的訓(xùn)練，培養(yǎng)設(shè)計(jì)具有專業(yè)水準(zhǔn)應(yīng)用程序的能力。 二、實(shí)驗(yàn)方式與考核方式二、實(shí)驗(yàn)方式與考核方式課程實(shí)驗(yàn)采用課內(nèi)實(shí)驗(yàn)學(xué)時(shí)與課外實(shí)驗(yàn)學(xué)時(shí)相結(jié)合（課外實(shí)驗(yàn)學(xué)時(shí)是課內(nèi)實(shí)驗(yàn)學(xué)時(shí)的 2 倍）的方式。本課程的課內(nèi)實(shí)驗(yàn)學(xué)時(shí)為 16 學(xué)時(shí)，要完成的 5

5、 個(gè)實(shí)驗(yàn)主要覆蓋線性表、棧和隊(duì)列、樹(shù)、圖、查找五部分內(nèi)容。每個(gè)實(shí)驗(yàn)中的題目按類型可分為驗(yàn)證型、設(shè)計(jì)性、綜合實(shí)驗(yàn), 按難度可分為達(dá)到“實(shí)驗(yàn)設(shè)置基本要求”和“實(shí)驗(yàn)設(shè)置較高要求”的實(shí)驗(yàn)。每次實(shí)驗(yàn)，每位同學(xué)可結(jié)合自己的情況，從任課教師布置的題目中選取具體實(shí)驗(yàn)題目，按要求完成實(shí)驗(yàn)任務(wù)。3任課教師一般提前 2 周布置實(shí)驗(yàn)任務(wù)和具體實(shí)驗(yàn)題目。學(xué)生要在課下充分了解實(shí)驗(yàn)內(nèi)容，并完成問(wèn)題分析、算法設(shè)計(jì)，并利用課外實(shí)驗(yàn)學(xué)時(shí)基本完成程序設(shè)計(jì)。每個(gè)實(shí)驗(yàn)的課內(nèi)實(shí)驗(yàn)學(xué)時(shí)安排同學(xué)集中在本系實(shí)驗(yàn)室進(jìn)行，任課教師和實(shí)驗(yàn)指導(dǎo)教師針對(duì)同學(xué)的不同問(wèn)題分別進(jìn)行指導(dǎo)，并檢查實(shí)驗(yàn)完成情況，要求學(xué)生回答相關(guān)的問(wèn)題。每次實(shí)驗(yàn)完成后，學(xué)生需整理實(shí)

6、驗(yàn)結(jié)果，并完成實(shí)驗(yàn)報(bào)告。實(shí)驗(yàn)成績(jī)從兩方面評(píng)定：實(shí)驗(yàn)完成情況和實(shí)驗(yàn)報(bào)告質(zhì)量。實(shí)驗(yàn)完成情況：指導(dǎo)教師根據(jù)學(xué)生的實(shí)驗(yàn)準(zhǔn)備情況、實(shí)驗(yàn)難度、實(shí)驗(yàn)完成情況、源程序質(zhì)量、回答問(wèn)題情況、實(shí)驗(yàn)紀(jì)律等方面給分。實(shí)驗(yàn)報(bào)告書(shū)寫(xiě)：學(xué)生在實(shí)驗(yàn)后的一周內(nèi)提交打印好的實(shí)驗(yàn)報(bào)告。教師根據(jù)實(shí)驗(yàn)報(bào)告質(zhì)量評(píng)定成績(jī)。 5 實(shí)驗(yàn)總成績(jī)=（ 第 i 次實(shí)驗(yàn)成績(jī)） i=1 三、實(shí)驗(yàn)要求三、實(shí)驗(yàn)要求 問(wèn)題分析：?jiǎn)栴}分析：充分地分析和理解問(wèn)題本身，弄清要求做什么，包括功能要求、性能要求、設(shè)計(jì)要求和約束以及基本數(shù)據(jù)特性，數(shù)據(jù)間的聯(lián)系等。 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：針對(duì)要求解決的問(wèn)題，考慮各種可能的數(shù)據(jù)結(jié)構(gòu)，并且力求從中出最佳方案（必須連同算法一

7、起考慮） ，確定主要的數(shù)據(jù)結(jié)構(gòu)及全程變量。對(duì)引入的每種數(shù)據(jù)結(jié)構(gòu)和全程變量要詳細(xì)說(shuō)明其功能、初值和操作特點(diǎn)。 算法設(shè)計(jì)：算法設(shè)計(jì)：算法設(shè)計(jì)分概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)，概要設(shè)計(jì)著重解決程序的模塊設(shè)計(jì)問(wèn)題，包括考慮如何把程序自頂向下4分解成若干順序模塊，并決定模塊的接口，即模塊間的相互關(guān)系以及模塊之間的信息交換問(wèn)題。詳細(xì)設(shè)計(jì)則要決定每個(gè)模塊內(nèi)部的具體算法，包括輸入、處理和輸出，相當(dāng)于 C 語(yǔ)言中具體的函數(shù)設(shè)計(jì)。 測(cè)試用例設(shè)計(jì)：測(cè)試用例設(shè)計(jì)：準(zhǔn)備典型測(cè)試數(shù)據(jù)和測(cè)試方案，測(cè)試數(shù)據(jù)要有代表性、敏感性，測(cè)試方案包括模塊測(cè)試和模塊集成測(cè)試。 上機(jī)調(diào)試并分析結(jié)果：上機(jī)調(diào)試并分析結(jié)果：對(duì)程序進(jìn)行編譯，糾正程序中可能出現(xiàn)

8、的語(yǔ)法錯(cuò)誤。測(cè)試前，先運(yùn)行一遍程序看看究竟將會(huì)發(fā)生什么，如果錯(cuò)誤較多，則根據(jù)事先設(shè)計(jì)的測(cè)試方案并結(jié)合現(xiàn)場(chǎng)情況進(jìn)行錯(cuò)誤跟蹤。最后，詳細(xì)記錄實(shí)驗(yàn)過(guò)程，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析，并于一周內(nèi)提交實(shí)驗(yàn)報(bào)告。 四、實(shí)驗(yàn)報(bào)告要求四、實(shí)驗(yàn)報(bào)告要求1實(shí)驗(yàn)報(bào)告格式：實(shí)驗(yàn)報(bào)告首頁(yè)按學(xué)校統(tǒng)一印刷的實(shí)驗(yàn)報(bào)告模版書(shū)寫(xiě)。2實(shí)驗(yàn)報(bào)告內(nèi)容：實(shí)驗(yàn)基本信息按照實(shí)驗(yàn)報(bào)告模版要求內(nèi)容填寫(xiě)，不得有空項(xiàng)。其中：實(shí)驗(yàn)內(nèi)容按任課教師下達(dá)的實(shí)驗(yàn)任務(wù)填寫(xiě)：包括實(shí)驗(yàn)?zāi)康摹⑷蝿?wù)、具體實(shí)驗(yàn)題目和要求；實(shí)驗(yàn)過(guò)程與實(shí)驗(yàn)結(jié)果應(yīng)包括如下主要內(nèi)容：算法設(shè)計(jì)思路簡(jiǎn)介核心算法設(shè)計(jì)描述：可以用自然語(yǔ)言、偽代碼或流程圖等方式算法的實(shí)現(xiàn)和測(cè)試結(jié)果：包括算法時(shí)的輸入、輸出，測(cè)試

9、結(jié)果的分析與討論，測(cè)試過(guò)程中遇5到的主要問(wèn)題及所采用的解決措施。附錄可包括源程序清單或其它說(shuō)明（如功能模塊之間的調(diào)用與被調(diào)用關(guān)系等）實(shí)驗(yàn)報(bào)告雷同者，本次實(shí)驗(yàn)成績(jī)?yōu)?0 分或雷同實(shí)驗(yàn)報(bào)告平分得分五、實(shí)驗(yàn)內(nèi)容五、實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)一實(shí)驗(yàn)一 線性表應(yīng)用線性表應(yīng)用一一. . 實(shí)驗(yàn)?zāi)康膶?shí)驗(yàn)?zāi)康?、掌握用 Turbo C 或 VC+上機(jī)調(diào)試線性表的基本方法；2、掌握線性表的基本操作，如插入、刪除、查找，以及線性表合并等運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上的運(yùn)算；并能夠運(yùn)用線性表基本操作解決問(wèn)題，實(shí)現(xiàn)相應(yīng)算法。二二. . 實(shí)驗(yàn)學(xué)時(shí)：實(shí)驗(yàn)學(xué)時(shí)：課內(nèi)實(shí)驗(yàn)學(xué)時(shí)：2 學(xué)時(shí)課外實(shí)驗(yàn)學(xué)時(shí)：4 學(xué)時(shí)三備選實(shí)驗(yàn)題目三備選實(shí)驗(yàn)題目1

10、 1 單鏈表基本操作練習(xí)（實(shí)驗(yàn)類型：驗(yàn)證型）單鏈表基本操作練習(xí)（實(shí)驗(yàn)類型：驗(yàn)證型）1）問(wèn)題描述：在主程序中設(shè)計(jì)一個(gè)簡(jiǎn)單的菜單，分別調(diào)用相應(yīng)的函數(shù)功能：6 1建立鏈表 2連接鏈表 3輸出鏈表 0結(jié)束2）實(shí)驗(yàn)要求：在程序中定義下述函數(shù)，并實(shí)現(xiàn)所要求的函數(shù)功能： CreateLinklist( ): 從鍵盤(pán)輸入數(shù)據(jù)，創(chuàng)建一個(gè)單鏈表 ContLinklist( )：將前面建立的兩個(gè)單鏈表首尾相連 OutputLinklist( )：輸出顯示單鏈表3）實(shí)驗(yàn)提示: 單鏈表數(shù)據(jù)類型定義（C 語(yǔ)言） # include typedef int ElemType； /元素類型 typedef struct LN

11、ode ElemType data; struct LNode *next; LNode,*LinkList; 為了算法實(shí)現(xiàn)簡(jiǎn)單，最好采用帶頭結(jié)點(diǎn)的單向鏈表。4）注意問(wèn)題: 重點(diǎn)理解鏈?zhǔn)酱鎯?chǔ)的特點(diǎn)及指針的含義。 注意比較順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)的各自特點(diǎn)。 注意比較帶頭結(jié)點(diǎn)、無(wú)頭結(jié)點(diǎn)鏈表實(shí)現(xiàn)插入、刪除算法時(shí)的區(qū)別。7 單鏈表的操作是數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，一定要注意對(duì)這部分的常見(jiàn)算法的理解。2 2 順序表基本操作練習(xí)（實(shí)驗(yàn)類型：驗(yàn)證型）順序表基本操作練習(xí)（實(shí)驗(yàn)類型：驗(yàn)證型）1）問(wèn)題描述： 從鍵盤(pán)輸入一組整型元素序列，建立順序表。 實(shí)現(xiàn)該順序表的遍歷。 在該順序表中進(jìn)行順序查找某一元素,查找成功返回1,否則返

12、回 0。 判斷該順序表中元素是否對(duì)稱,對(duì)稱返回 1,否則返回 0。2）實(shí)驗(yàn)要求： 對(duì)應(yīng)問(wèn)題描述，在程序中定義 4 個(gè)相應(yīng)的函數(shù)，實(shí)現(xiàn)上面要求的函數(shù)功能： 在主程序中設(shè)計(jì)一個(gè)簡(jiǎn)單的菜單，調(diào)用上述 4 個(gè)函數(shù)3）實(shí)驗(yàn)提示: 順序表存儲(chǔ)數(shù)據(jù)類型定義（C 語(yǔ)言） # define MAXSIZE 100 /表中元素的最大個(gè)數(shù) typedef int ElemType； /元素類型 typedef struct list ElemType elemMAXSIZE; /靜態(tài)線性表 int length; /表的實(shí)際長(zhǎng)度 SqList; /順序表的類型名4）注意問(wèn)題: 插入、刪除時(shí)元素的移動(dòng)原因、方向及先后

13、順序。 理解不同的函數(shù)形參與實(shí)參的傳遞關(guān)系。83 3 約瑟夫環(huán)問(wèn)題（實(shí)驗(yàn)類型：綜合型）約瑟夫環(huán)問(wèn)題（實(shí)驗(yàn)類型：綜合型）1）問(wèn)題描述：有編號(hào)為 1, 2n 的 n 個(gè)人按順時(shí)針?lè)较驀蝗?，每人持有一個(gè)正整數(shù)密碼。開(kāi)始給定一個(gè)正整數(shù) m，從第一個(gè)人按順時(shí)針?lè)较蜃?1 開(kāi)始報(bào)數(shù)，報(bào)到 m 者出列，不再參加報(bào)數(shù)，這時(shí)將出列者的密碼作為 m，從出列者順時(shí)針?lè)较虻南乱蝗碎_(kāi)始重新自 1 開(kāi)始報(bào)數(shù)。如此下去，直到所有人都出列。試設(shè)計(jì)算法，輸出出列者的序列。2）實(shí)驗(yàn)要求: 采用順序和鏈?zhǔn)絻煞N存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)3) 實(shí)現(xiàn)提示： 用順序表來(lái)存儲(chǔ)圍座者的序號(hào)和密碼(順序存儲(chǔ)結(jié)構(gòu)). 用 number 和 code 分別表

14、示圍座者的序號(hào)和密碼.假設(shè)圍座者人數(shù)為 j,當(dāng)前使用密碼為 m,開(kāi)始報(bào)數(shù)者位置為 s, 那么下一出列者位置為s=(s+m-1) mod j. 當(dāng)我們要在線性表的順序存儲(chǔ)結(jié)構(gòu)上的第 i 個(gè)位置上插入一個(gè)元素時(shí)，必須先將線性表的第 i 個(gè)元素之后的所有元素依次后移一個(gè)位置，以便騰空一個(gè)位置，再把新元素插入到該位置。若要?jiǎng)h除第 i 個(gè)元素時(shí)，也必須把第 i 個(gè)元素之后的所有元素前移一個(gè)位置。 用鏈?zhǔn)酱鎯?chǔ)解決此問(wèn)題時(shí)可以采用循環(huán)鏈表.4）注意問(wèn)題: 順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)此算法時(shí)計(jì)算出列位置的不同方法，人員出列后所做操作的區(qū)別。4 4 一元稀疏多項(xiàng)式簡(jiǎn)單的計(jì)算器（實(shí)驗(yàn)類型：綜合型）一元稀疏多項(xiàng)式簡(jiǎn)單的

15、計(jì)算器（實(shí)驗(yàn)類型：綜合型）91）問(wèn)題描述：用線性表表示一元稀疏多項(xiàng)式，設(shè)計(jì)一個(gè)一元多項(xiàng)式運(yùn)算器2）實(shí)驗(yàn)要求: 采用單鏈表存儲(chǔ)結(jié)構(gòu)一元稀疏多項(xiàng)式 輸入并建立多項(xiàng)式 輸出多項(xiàng)式 實(shí)現(xiàn)多項(xiàng)式加、減運(yùn)算3) 實(shí)現(xiàn)提示：以兩個(gè)多項(xiàng)式相加為例 結(jié)果多項(xiàng)式另存 掃描兩個(gè)相加多項(xiàng)式，若都未檢測(cè)完：若當(dāng)前被檢測(cè)項(xiàng)指數(shù)相等，系數(shù)相加，若結(jié)果未變成 0，則將結(jié)果插入到結(jié)果多項(xiàng)式。若當(dāng)前被檢測(cè)項(xiàng)指數(shù)不等，則將指數(shù)較小者插入到結(jié)果多項(xiàng)式。 若有一個(gè)多項(xiàng)式已檢測(cè)完，則將另一個(gè)多項(xiàng)式剩余部分直接連接到結(jié)果多項(xiàng)式。5 5 長(zhǎng)整數(shù)（任意長(zhǎng)度）四則運(yùn)算演示程序（實(shí)驗(yàn)類型：綜長(zhǎng)整數(shù)（任意長(zhǎng)度）四則運(yùn)算演示程序（實(shí)驗(yàn)類型：綜合型）合

16、型）1）問(wèn)題描述：設(shè)計(jì)一個(gè)實(shí)現(xiàn)任意長(zhǎng)的整數(shù)進(jìn)行加法運(yùn)算的演示程序2）實(shí)驗(yàn)要求: 利用雙向循環(huán)鏈表實(shí)現(xiàn)長(zhǎng)整數(shù)的存儲(chǔ)，給各結(jié)點(diǎn)含一個(gè)整型變量。任何整型變量的的范圍是 -（215-1）（215-1） 。 輸入和輸出形式：按照中國(guó)對(duì)長(zhǎng)整數(shù)的表示習(xí)慣，每四位一組，組間用逗號(hào)隔開(kāi)。103) 實(shí)現(xiàn)提示： 每個(gè)結(jié)點(diǎn)中可以存放的最大整數(shù)為 215-1=32767，才能保證兩數(shù)相加不會(huì)溢出。但若這樣存，即相當(dāng)于按32768 進(jìn)制數(shù)存，在十進(jìn)制數(shù)與 32768 進(jìn)制數(shù)之間的轉(zhuǎn)換十分不方便。故可以在每個(gè)結(jié)點(diǎn)中僅存十進(jìn)制數(shù)的 4 位，即不超過(guò) 9999 的非負(fù)整數(shù)，整個(gè)鏈表視為萬(wàn)進(jìn)制數(shù)。 可以利用頭結(jié)點(diǎn)數(shù)據(jù)域的符號(hào)代表

17、長(zhǎng)整數(shù)的符號(hào)。用其絕對(duì)值表示元素結(jié)點(diǎn)的樹(shù)木。相加過(guò)程中不要破壞兩個(gè)操作數(shù)鏈表。兩操作數(shù)的頭指針存于指針數(shù)組中是簡(jiǎn)化程序結(jié)構(gòu)的一種方法。4）注意問(wèn)題: 不能給常整數(shù)位數(shù)規(guī)定上限。實(shí)驗(yàn)二實(shí)驗(yàn)二 棧與隊(duì)列應(yīng)用棧與隊(duì)列應(yīng)用一一. . 實(shí)驗(yàn)?zāi)康膶?shí)驗(yàn)?zāi)康?. 實(shí)驗(yàn)設(shè)置基本要求：通過(guò)實(shí)驗(yàn)掌握?；蜿?duì)列的基本操作的實(shí)現(xiàn)，并能靈活運(yùn)用棧或隊(duì)列特性，綜合運(yùn)用程序設(shè)計(jì)、算法分析等知識(shí)解決實(shí)際問(wèn)題。2. 實(shí)驗(yàn)設(shè)置較高要求：理解組成遞歸算法的基本條件，理解遞歸算法與相應(yīng)的非遞歸算法的區(qū)別，理解棧和隊(duì)列的應(yīng)用與作用。二二. . 實(shí)驗(yàn)學(xué)時(shí)：實(shí)驗(yàn)學(xué)時(shí)：課內(nèi)實(shí)驗(yàn)學(xué)時(shí)：4 學(xué)時(shí)課外實(shí)驗(yàn)學(xué)時(shí)：8 學(xué)時(shí)三三. . 備選實(shí)驗(yàn)題目備選實(shí)驗(yàn)

18、題目111 1 十進(jìn)制數(shù)十進(jìn)制數(shù) N N 進(jìn)制數(shù)據(jù)的轉(zhuǎn)換進(jìn)制數(shù)據(jù)的轉(zhuǎn)換 （實(shí)驗(yàn)類型：綜合型）（實(shí)驗(yàn)類型：綜合型）1）問(wèn)題描述：將從鍵盤(pán)輸入的十進(jìn)制數(shù)轉(zhuǎn)換為 N（如二進(jìn)制、八進(jìn)制、十六進(jìn)制）進(jìn)制數(shù)據(jù)。2）實(shí)驗(yàn)要求: 利用順序棧實(shí)現(xiàn)數(shù)制轉(zhuǎn)換問(wèn)題3) 實(shí)現(xiàn)提示： 轉(zhuǎn)換方法利用輾轉(zhuǎn)相除法; 所轉(zhuǎn)換的 N 進(jìn)制數(shù)按低位到高位的順序產(chǎn)生，而通常的輸出是從高位到低位的，恰好與計(jì)算過(guò)程相反，因此轉(zhuǎn)換過(guò)程中每得到一位 N 進(jìn)制數(shù)則進(jìn)棧保存，轉(zhuǎn)換完畢后依次出棧則正好是轉(zhuǎn)換結(jié)果。4）注意問(wèn)題: 何時(shí)入棧、出棧 算法結(jié)束條件2 2 算術(shù)表達(dá)式求值演示（實(shí)驗(yàn)類型：綜合型）算術(shù)表達(dá)式求值演示（實(shí)驗(yàn)類型：綜合型）1）問(wèn)題描

19、述：從鍵盤(pán)輸入一個(gè)算術(shù)表達(dá)式并輸出它的結(jié)果2）實(shí)驗(yàn)要求：算術(shù)表達(dá)式可包含加、減、乘、除、十進(jìn)制整數(shù)和小括號(hào)，利用棧實(shí)現(xiàn)。3) 實(shí)現(xiàn)提示： 表達(dá)式作為一個(gè)串存儲(chǔ)，如表達(dá)式“3*2-(4+2*1)”,其求值過(guò)程為：自左向右掃描表達(dá)式，當(dāng)掃描到 3*2時(shí)不能馬上計(jì)算，因后面可能還有更高的運(yùn)算，正確的處理過(guò)程是：需要兩個(gè)棧：對(duì)象棧 OPND 和算符棧 OPTR;自左至右掃描表達(dá)式, 若當(dāng)前字符是運(yùn)算對(duì)象，入 OPND 棧;12對(duì)運(yùn)算符，若這個(gè)運(yùn)算符比棧頂運(yùn)算符高則入棧，繼續(xù)向后處理，若這個(gè)運(yùn)算符比棧頂運(yùn)算符低則從 OPND 棧出棧兩個(gè)數(shù)，從 OPTR 棧出棧一運(yùn)算符進(jìn)行運(yùn)算，并將其運(yùn)算結(jié)果入 OPND

20、 棧，繼續(xù)處理當(dāng)前字符，直到遇到結(jié)束符。 4）注意問(wèn)題 重點(diǎn)理解棧的算法思想，能夠根據(jù)實(shí)際情況選擇合適的存儲(chǔ)結(jié)構(gòu)。 注意算法的各個(gè)函數(shù)之間值的傳遞情況。3 3 停車(chē)場(chǎng)管理問(wèn)題（實(shí)驗(yàn)類型：綜合型）停車(chē)場(chǎng)管理問(wèn)題（實(shí)驗(yàn)類型：綜合型）1）問(wèn)題描述：設(shè)有一個(gè)可以停放 n 輛汽車(chē)的狹長(zhǎng)停車(chē)場(chǎng)，它只有一個(gè)大門(mén)可以供車(chē)輛進(jìn)出。車(chē)輛按到達(dá)停車(chē)場(chǎng)的早晚依次從停車(chē)場(chǎng)最里面向大門(mén)口處停放(最先到達(dá)的第一輛車(chē)放在停車(chē)場(chǎng)的最里面)。如果停車(chē)場(chǎng)已放滿 n 輛車(chē)，則后來(lái)的車(chē)輛只能在停車(chē)場(chǎng)大門(mén)外的便道上等待，一旦停車(chē)場(chǎng)內(nèi)有車(chē)走開(kāi)，則排在便道上的第一輛車(chē)就進(jìn)入停車(chē)場(chǎng)。停車(chē)場(chǎng)內(nèi)如有某輛車(chē)要開(kāi)走，在它之后進(jìn)入停車(chē)場(chǎng)的車(chē)都必須先退出

21、停車(chē)場(chǎng)為它讓路，待其開(kāi)出停車(chē)場(chǎng)后，這些車(chē)輛再依原來(lái)的次序進(jìn)場(chǎng)。每輛車(chē)在離開(kāi)停車(chē)場(chǎng)時(shí)，都應(yīng)根據(jù)它在停車(chē)場(chǎng)內(nèi)停留的時(shí)間長(zhǎng)短交費(fèi)。如果停留在便道上的車(chē)未進(jìn)停車(chē)場(chǎng)就要離去，允許其離去，不收停車(chē)費(fèi)，并且仍然保持在便道上等待的車(chē)輛的次序。編寫(xiě)程序模擬該停車(chē)場(chǎng)的管理。2）實(shí)驗(yàn)要求: 要求程序輸出每輛車(chē)到達(dá)后的停車(chē)位置（停車(chē)場(chǎng)或便道上） ，以及某輛車(chē)離開(kāi)停車(chē)場(chǎng)時(shí)應(yīng)繳納的費(fèi)用和他在停車(chē)場(chǎng)內(nèi)停留的時(shí)間3）實(shí)現(xiàn)提示：以棧模擬停車(chē)場(chǎng)，以隊(duì)列模擬便道，按照從終端讀入的車(chē)輛“到達(dá)” “離開(kāi)”信息模擬停車(chē)場(chǎng)管理134）注意問(wèn)題 重點(diǎn)理解棧、隊(duì)列的算法思想，能夠根據(jù)實(shí)際情況選擇合適的存儲(chǔ)結(jié)構(gòu)。 棧、隊(duì)列的算法是后續(xù)實(shí)驗(yàn)的基礎(chǔ)

22、（廣義表、樹(shù)、圖、查找、排序等） 。4 4 判斷判斷“回文回文”問(wèn)題（實(shí)驗(yàn)類型：綜合型）問(wèn)題（實(shí)驗(yàn)類型：綜合型）1）問(wèn)題描述：所謂回文，是指從前向后順讀和從后向前倒讀都一樣的字符串。例如，did; pop; I was able 與 elba saw I 等等。2）實(shí)驗(yàn)要求：編寫(xiě)程序，利用棧結(jié)構(gòu)判斷一個(gè)字符串是否是“回文” 。3）實(shí)現(xiàn)提示： 從左向右遇到的字符，若和棧頂元素比較，若不相等，字符入棧，若相等，出棧。如此繼續(xù)，若棧空，字符串是“回文” ，否則不是。5 5 用遞歸和非遞歸兩種方法實(shí)現(xiàn)自然數(shù)的拆分用遞歸和非遞歸兩種方法實(shí)現(xiàn)自然數(shù)的拆分（實(shí)驗(yàn)類型：（實(shí)驗(yàn)類型：綜合型）綜合型）1）問(wèn)題描述

23、：任何大于 1 的自然數(shù) n，總可以拆分成若干大于等于 1 的自然數(shù)之和。 例: n=4 4=1+3 4=1+1+2 4=1+1+1+1 4=2+2 2）實(shí)驗(yàn)要求: 采用遞歸和非遞歸兩種方法實(shí)現(xiàn) 利用交換率得出的拆分看作相同的拆分。3）實(shí)現(xiàn)提示： 遞歸算法: 用數(shù)組 a，ak中存儲(chǔ)已完成的一種拆分 ak能否再拆分取決于 ak/2 是否大于等于ak-1；14 遞歸過(guò)程有兩個(gè)參數(shù)：n 表示要拆分?jǐn)?shù)值的大?。籯 表示 n 存儲(chǔ)在數(shù)組元素 ak中。 非遞歸算法：（1） 棧為兩個(gè)數(shù)組 a,b，ax,bx 表示兩個(gè)棧的棧頂元素；初始化：a1=1,b1=n，i=1, ax=ai,bx=bi（2） 若 i1

24、or axbx,重復(fù) 若 axbx/2，進(jìn)棧并取棧頂元素，返回（2） i=i+1;ai=ax,bi=bx-ax,bx=bi 若 ax=bx，則數(shù)出拆分，退棧兵修改棧頂元素，返回（2） i=i-1;ai=ai+1,ax=ai,bx=bi 其余情況，bx/2axbx，修改棧頂元素，返回（2） ai=ai+1,ax=ai實(shí)驗(yàn)三實(shí)驗(yàn)三 二叉樹(shù)的操作二叉樹(shù)的操作一實(shí)驗(yàn)?zāi)康囊粚?shí)驗(yàn)?zāi)康?、 基本要求：深刻理解二叉樹(shù)性質(zhì)和及各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍；掌握用指針類型描述、訪問(wèn)和處理二叉樹(shù)的運(yùn)算；熟練掌握二叉樹(shù)的遍歷算法； 2、 較高要求: 在遍歷算法的基礎(chǔ)上設(shè)計(jì)二叉樹(shù)更復(fù)雜操作算法；認(rèn)識(shí)哈夫曼樹(shù)、哈夫曼編碼

25、的作用和意義;掌握樹(shù)與森林的存儲(chǔ)與便利。二二. . 實(shí)驗(yàn)學(xué)時(shí)：實(shí)驗(yàn)學(xué)時(shí)：課內(nèi)實(shí)驗(yàn)學(xué)時(shí)：3 學(xué)時(shí)15課外實(shí)驗(yàn)學(xué)時(shí)：6 學(xué)時(shí)三備選實(shí)驗(yàn)題目三備選實(shí)驗(yàn)題目1 1以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)二叉樹(shù)的創(chuàng)建、遍歷（實(shí)以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)二叉樹(shù)的創(chuàng)建、遍歷（實(shí)驗(yàn)類型：驗(yàn)證型）驗(yàn)類型：驗(yàn)證型）1）問(wèn)題描述：在主程序中設(shè)計(jì)一個(gè)簡(jiǎn)單的菜單，分別調(diào)用相應(yīng)的函數(shù)功能： 1建立樹(shù)2前序遍歷樹(shù)3中序(非遞歸)遍歷樹(shù) 4后序遍歷樹(shù)0結(jié)束2）實(shí)驗(yàn)要求：在程序中定義下述函數(shù)，并實(shí)現(xiàn)要求的函數(shù)功能： CreateTree(): 按從鍵盤(pán)輸入的前序序列，創(chuàng)建樹(shù) PreOrderTree()：前序遍歷樹(shù)（遞歸） InOrderT

26、ree()：中序(非遞歸)遍歷樹(shù) LaOrderTree(): 后序遍歷樹(shù)（遞歸）3）實(shí)驗(yàn)提示: 二叉鏈表存儲(chǔ)數(shù)據(jù)類型定義 # define ElemType char /元素類型 typedef struct BiTNode ElemType data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree;16 元素類型可以根據(jù)實(shí)際情況選取。4）注意問(wèn)題: 注意理解遞歸算法的執(zhí)行步驟。 注意字符類型數(shù)據(jù)在輸入時(shí)的處理。 重點(diǎn)理解如何利用棧結(jié)構(gòu)實(shí)現(xiàn)非遞歸算法2 2編寫(xiě)算法交換二叉樹(shù)中所有結(jié)點(diǎn)的左、右子樹(shù)（實(shí)驗(yàn)類編寫(xiě)算法交換二叉樹(shù)中所有結(jié)點(diǎn)的左、右子樹(shù)

27、（實(shí)驗(yàn)類型：綜合型）型：綜合型）1）問(wèn)題描述：編寫(xiě)一算法，交換二叉樹(shù)中所有結(jié)點(diǎn)的左、右子樹(shù)2）實(shí)驗(yàn)要求：以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)3) 實(shí)現(xiàn)提示：設(shè)二叉樹(shù)的根指針未 t，且以二叉鏈表表示，可利用一個(gè)類型為 seqstack 的指針來(lái)實(shí)現(xiàn)，且棧單元包含兩個(gè)域，一個(gè)為 data，另一個(gè)為 top，整個(gè)棧容量為 maxsize，當(dāng)樹(shù)非空時(shí)，將當(dāng)前的樹(shù)根結(jié)點(diǎn)入棧，同時(shí)將當(dāng)前棧頂元素出棧當(dāng)作根結(jié)點(diǎn)，然后依據(jù)當(dāng)前的根結(jié)點(diǎn)是否具有孩子結(jié)點(diǎn)來(lái)判定是否將其左、右指針進(jìn)行交換；再將交換后的左指針或右指針入棧，這樣反復(fù)進(jìn)行，直到?？諡橹?。4）注意問(wèn)題: 注意理解算法中棧結(jié)構(gòu)的利用3 3試編寫(xiě)按層次順序遍歷二叉樹(shù)的算法（

28、實(shí)驗(yàn)類型：綜合試編寫(xiě)按層次順序遍歷二叉樹(shù)的算法（實(shí)驗(yàn)類型：綜合型）型）1）問(wèn)題描述：編寫(xiě)按層次順序遍歷二叉樹(shù)的算法2）實(shí)驗(yàn)要求：以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)3) 實(shí)現(xiàn)提示：本算法要采用一個(gè)隊(duì)列 q，先將二叉樹(shù)根結(jié)點(diǎn)入隊(duì)列，然后出隊(duì)列，輸出該結(jié)點(diǎn)；若它有左子樹(shù)，便將左子樹(shù)根結(jié)點(diǎn)入隊(duì)列；若它有右子樹(shù)，便將右子樹(shù)根結(jié)點(diǎn)入隊(duì)列，17直到隊(duì)列空為止。因?yàn)殛?duì)列的特點(diǎn)是先進(jìn)先出，從而達(dá)到按層次順序遍歷二叉樹(shù)目的。4）注意問(wèn)題: 理解算法中隊(duì)列結(jié)構(gòu)的利用4 4實(shí)現(xiàn)一個(gè)哈夫曼編實(shí)現(xiàn)一個(gè)哈夫曼編/ /譯碼系統(tǒng)（實(shí)驗(yàn)類型：綜合型）譯碼系統(tǒng)（實(shí)驗(yàn)類型：綜合型）1）問(wèn)題描述：利用哈夫曼編碼進(jìn)行信息通信可以大大編寫(xiě)按層次順序遍

29、歷二叉樹(shù)的算法提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳輸數(shù)據(jù)預(yù)先編碼，在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼。對(duì)于雙工信道，每端都需要一個(gè)完整的編碼/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫(xiě)一個(gè)哈夫曼的編/譯碼系統(tǒng)。2）實(shí)驗(yàn)要求：一個(gè)完整的系統(tǒng)應(yīng)具有以下功能：(1) I：初始化(Initialization)。從終端讀入字符集大小 n，以及 n 個(gè)字符和 n 個(gè)權(quán)值，建立哈夫曼樹(shù)，并將它存于文件 hfmTree 中。(2) E：編碼(Encoding)。利用已建好的哈夫曼樹(shù)對(duì)文件ToBeTran 中的正文進(jìn)行編碼，然后將結(jié)果存入文件 CodeFile 中。(3)

30、 D：譯碼(Decoding)。利用已建好的哈夫曼樹(shù)將文件CodeFile 中的代碼進(jìn)行譯碼，結(jié)果存入文件 TextFile 中。(4) P：打印代碼文件(Print)。將文件 CodeFile 以緊湊格式顯示在終端上，每行 50 個(gè)代碼。同時(shí)將此字符形式的編碼文件寫(xiě)入文件 CodePrin 中。(5) T：打印哈夫曼樹(shù)(Tree printing)。將已在內(nèi)存中的哈夫曼樹(shù)以直觀的方式顯示在終端上，同時(shí)將此字符形式的哈夫曼樹(shù)寫(xiě)入文件 TreePrint 中。3) 實(shí)現(xiàn)提示：18(1) 文件 CodeFile 的基類型可以設(shè)為字節(jié)型。(2) 用戶界面可以設(shè)計(jì)為“菜單”方式：顯示上述功能符號(hào)，再加

31、上“Q” ，表示退出運(yùn)行 Quit。請(qǐng)用戶鍵入一個(gè)選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶選擇了“E”為止。(3) 在程序的一次執(zhí)行過(guò)程中，第一次執(zhí)行 I、D 或 C 命令之后，哈夫曼樹(shù)已經(jīng)在內(nèi)存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行 I 命令，因?yàn)槲募?hfmTree 可能早已建好。5 5森林（孩子兄弟鏈表）的建立與遍歷（實(shí)驗(yàn)類型：驗(yàn)證森林（孩子兄弟鏈表）的建立與遍歷（實(shí)驗(yàn)類型：驗(yàn)證型）型）1）問(wèn)題描述：以“孩子兄弟二叉鏈表”為存儲(chǔ)結(jié)構(gòu)，建立和遍歷一個(gè)森林2）實(shí)驗(yàn)要求：以“孩子兄弟二叉鏈表”作為存儲(chǔ)結(jié)構(gòu)3) 實(shí)現(xiàn)提示： 可參考二叉樹(shù)的前序遍歷和中序遍歷算法4）注意問(wèn)題: 理解二叉

32、樹(shù)與樹(shù)的對(duì)應(yīng)關(guān)系 理解樹(shù)和森林遍歷的實(shí)質(zhì)實(shí)驗(yàn)四實(shí)驗(yàn)四 圖的遍歷圖的遍歷一、一、 實(shí)驗(yàn)?zāi)康膶?shí)驗(yàn)?zāi)康?、 基本要求：通過(guò)實(shí)驗(yàn)掌握理解圖的兩種主要存儲(chǔ)結(jié)構(gòu)，掌握?qǐng)D的構(gòu)造算法，掌握?qǐng)D的深度優(yōu)先遍歷、廣度優(yōu)先遍歷算法。2、 較高要求：理解拓?fù)渑判颉OV 網(wǎng)、AOE 網(wǎng)等圖型結(jié)構(gòu)19的操作方法應(yīng)用價(jià)值。二二. . 實(shí)驗(yàn)學(xué)時(shí)：實(shí)驗(yàn)學(xué)時(shí)：課內(nèi)實(shí)驗(yàn)學(xué)時(shí)：3 學(xué)時(shí)課外實(shí)驗(yàn)學(xué)時(shí)：6 學(xué)時(shí)三三. . 備選實(shí)驗(yàn)題目備選實(shí)驗(yàn)題目1 1鍵盤(pán)輸入的數(shù)據(jù)建立圖，并進(jìn)行深度優(yōu)先搜索和廣度優(yōu)鍵盤(pán)輸入的數(shù)據(jù)建立圖，并進(jìn)行深度優(yōu)先搜索和廣度優(yōu)先搜索（實(shí)驗(yàn)類型：驗(yàn)證型）先搜索（實(shí)驗(yàn)類型：驗(yàn)證型）1）問(wèn)題描述：在主程序中設(shè)計(jì)一個(gè)簡(jiǎn)單的菜

33、單，分別調(diào)用相應(yīng)的函數(shù)功能： 1圖的建立 2深度優(yōu)先遍歷圖 3廣度優(yōu)先遍歷圖 0結(jié)束2）實(shí)驗(yàn)要求：在程序中定義下述函數(shù)，并實(shí)現(xiàn)要求的函數(shù)功能： CreateGraph(): 按從鍵盤(pán)的數(shù)據(jù)建立圖 DFSGrahp()：深度優(yōu)先遍歷圖 BFSGrahp()：廣度優(yōu)先遍歷圖3）實(shí)驗(yàn)提示: 圖的存儲(chǔ)可采用鄰接表或鄰接矩陣； 圖存儲(chǔ)數(shù)據(jù)類型定義 （鄰接表存儲(chǔ)） # define MAX_VERTEX_NUM 8 /頂點(diǎn)最大個(gè)數(shù) typedef struct ArcNode int adjvex; struct ArcNode *nextarc;20 int weight; /邊的權(quán) ArcNode;

34、/表結(jié)點(diǎn) # define VertexType int /頂點(diǎn)元素類型 typedef struct VNode int degree,indegree;/頂點(diǎn)的度，入度 VertexType data; ArcNode *firstarc;Vnode /*頭結(jié)點(diǎn)*/,AdjListMAX_VERTEX_NUM; typedef struct AdjList vertices; int vexnum,arcnum;/頂點(diǎn)的實(shí)際數(shù)，邊的實(shí)際數(shù) ALGraph; 4）注意問(wèn)題: 注意理解各算法實(shí)現(xiàn)時(shí)所采用的存儲(chǔ)結(jié)構(gòu)。 注意區(qū)別正、逆鄰接。2 2利用最小生成樹(shù)算法解決通信網(wǎng)的總造價(jià)最低問(wèn)題（實(shí)利用

35、最小生成樹(shù)算法解決通信網(wǎng)的總造價(jià)最低問(wèn)題（實(shí)驗(yàn)類型：綜合型）驗(yàn)類型：綜合型）1）問(wèn)題描述：若在 n 個(gè)城市之間建通信網(wǎng)絡(luò)，秩序架設(shè) n-1 條線路即可。如何以最低的經(jīng)濟(jì)代價(jià)建設(shè)這個(gè)通信網(wǎng)，是一個(gè)網(wǎng)絡(luò)的最小生成樹(shù)問(wèn)題。2）實(shí)驗(yàn)要求：利用克魯斯卡爾算法求網(wǎng)的最小生成樹(shù)3) 實(shí)現(xiàn)提示：通信線路一旦建立，必然是雙向的。因此，構(gòu)造最小生成樹(shù)的網(wǎng)一定是無(wú)向網(wǎng)。為簡(jiǎn)單起見(jiàn)，圖的頂點(diǎn)數(shù)不超過(guò) 10 個(gè)，網(wǎng)中邊的權(quán)值設(shè)置成小于 100。3 3教學(xué)計(jì)劃編制問(wèn)題（實(shí)驗(yàn)類型：綜合型）教學(xué)計(jì)劃編制問(wèn)題（實(shí)驗(yàn)類型：綜合型）1）問(wèn)題描述：軟件專業(yè)的學(xué)生要學(xué)習(xí)一系列課程，其中有些課程必須在其先修課完成后才能學(xué)習(xí)。212）實(shí)驗(yàn)

36、要求：假設(shè)每門(mén)課程的學(xué)習(xí)時(shí)間為一個(gè)學(xué)期，試為該專業(yè)的學(xué)生設(shè)計(jì)教學(xué)計(jì)劃，使他們能在最短時(shí)間內(nèi)修完專業(yè)要求的全部課程。3) 實(shí)現(xiàn)提示： 以頂點(diǎn)代表課程，弧代表課程的先后修關(guān)系，按課程先后關(guān)系建立有向無(wú)環(huán)圖。 利用拓?fù)渑判驅(qū)崿F(xiàn)。4 4給定實(shí)際背景，解決最短路徑問(wèn)題（實(shí)驗(yàn)類型：綜合型）給定實(shí)際背景，解決最短路徑問(wèn)題（實(shí)驗(yàn)類型：綜合型）1）問(wèn)題描述：假設(shè)以一個(gè)帶權(quán)有向圖表示某一區(qū)域的公交線路網(wǎng)，圖中頂點(diǎn)代表一些區(qū)域中的重要場(chǎng)所，弧代表已有的公交線路，弧上的權(quán)表示該線路上的票價(jià)（或搭乘所需時(shí)間） ，試設(shè)計(jì)一個(gè)交通指南系統(tǒng)，指導(dǎo)前來(lái)咨詢者以最低的票價(jià)或最少的時(shí)間從區(qū)域中的某一場(chǎng)所到達(dá)另一場(chǎng)所。2）實(shí)驗(yàn)要求：

37、利用 Dijkstra 算法或 Floyd 算法求最低的票價(jià)或最少的時(shí)間3) 實(shí)現(xiàn)提示： 該問(wèn)題可以歸結(jié)為一個(gè)求帶權(quán)有向圖中頂點(diǎn)間最短路徑的問(wèn)題。 分別建立以票價(jià)（或搭乘所需時(shí)間）為權(quán)的有向圖，再利用 Dijkstra 算法或 Floyd 算法求最短路徑及其路徑長(zhǎng)度。實(shí)驗(yàn)五實(shí)驗(yàn)五 查找算法應(yīng)用查找算法應(yīng)用一、實(shí)驗(yàn)?zāi)康囊?、?shí)驗(yàn)?zāi)康?、實(shí)驗(yàn)設(shè)置基本要求：理解二叉排序樹(shù)、AVL 樹(shù)的查找、插入、刪除、建立算法的思想及程序?qū)崿F(xiàn)；掌握散列存22儲(chǔ)結(jié)構(gòu)的思想，能選擇合適散列函數(shù)，實(shí)現(xiàn)不同沖突處理方法的散列表的查找、建立。運(yùn)用折半查找、分塊查找、二叉排序樹(shù)、散列表等查找算法解決實(shí)際問(wèn)題。2、實(shí)驗(yàn)設(shè)置較高要求

38、：利用 B+樹(shù)設(shè)計(jì)大數(shù)據(jù)集索引結(jié)構(gòu)。 二二. . 實(shí)驗(yàn)學(xué)時(shí)：實(shí)驗(yàn)學(xué)時(shí)：課內(nèi)實(shí)驗(yàn)學(xué)時(shí)：4 學(xué)時(shí)課外實(shí)驗(yàn)學(xué)時(shí)：8 學(xué)時(shí)三、備選實(shí)驗(yàn)題目三、備選實(shí)驗(yàn)題目1.1. 哈希表查找（實(shí)驗(yàn)類型：綜合型）哈希表查找（實(shí)驗(yàn)類型：綜合型）1）問(wèn)題描述：針對(duì)某個(gè)集體的“人名”構(gòu)造哈希表，解決按“人名”進(jìn)行查找的索引結(jié)構(gòu)。2）實(shí)驗(yàn)要求：要求表的平均查找長(zhǎng)度不超過(guò) R，完成相應(yīng)的建表和查表程序。3) 實(shí)現(xiàn)提示：假設(shè)人名為漢語(yǔ)拼音形式。代填入哈希表人名共 30 個(gè)，取平均查找長(zhǎng)度的上限為 2。哈希函數(shù)用除留余數(shù)法構(gòu)造，用再散列法處理沖突。2.2. 構(gòu)造二叉排序樹(shù)，并進(jìn)行中序遍歷（實(shí)驗(yàn)類型：綜合型）構(gòu)造二叉排序樹(shù)，并進(jìn)行中序

39、遍歷（實(shí)驗(yàn)類型：綜合型）1）問(wèn)題描述：從鍵盤(pán)讀入一串整數(shù)構(gòu)造一棵二叉排序樹(shù)，并對(duì)得到的二叉排序述進(jìn)行中序遍歷，得到有序序列。2）實(shí)驗(yàn)要求：該二叉排序樹(shù)以二叉鏈表存儲(chǔ)3）實(shí)現(xiàn)提示：二叉排序樹(shù)的構(gòu)成，可從空的二叉樹(shù)開(kāi)始，每輸入一個(gè)結(jié)點(diǎn)數(shù)據(jù)，就建立一個(gè)新結(jié)點(diǎn)插入到當(dāng)前已生成的二叉排序樹(shù)中，所以它的主要操作是二叉排序樹(shù)插入運(yùn)算。在23二叉排序樹(shù)中插入新結(jié)點(diǎn)，只要保證插入后仍符合二叉排序樹(shù)的定義即可。3.3. 折半查找算法（實(shí)驗(yàn)類型：驗(yàn)證型）折半查找算法（實(shí)驗(yàn)類型：驗(yàn)證型）1）問(wèn)題描述：從鍵盤(pán)讀入一串整數(shù)和一個(gè)待查關(guān)鍵字，查找在該整數(shù)串中是否有這個(gè)待查關(guān)鍵字。如果有，輸出它在整數(shù)串中的位置；如果沒(méi)有，輸

40、出-12）實(shí)驗(yàn)要求： 利用折半查找算法查找 用遞歸和非遞歸兩種方式實(shí)現(xiàn)折半查找算法3) 實(shí)現(xiàn)提示： 遞歸實(shí)現(xiàn)參考書(shū)上折半查找算法的實(shí)現(xiàn) 非遞歸算法利用棧實(shí)現(xiàn)4.4. 借助借助 B B 樹(shù)實(shí)現(xiàn)圖書(shū)索引管理（實(shí)驗(yàn)類型：綜合型）樹(shù)實(shí)現(xiàn)圖書(shū)索引管理（實(shí)驗(yàn)類型：綜合型）1）問(wèn)題描述：圖書(shū)管理基本業(yè)務(wù)活動(dòng)包括：對(duì)一本書(shū)的采編入庫(kù)、清除庫(kù)存、借閱和歸還等。設(shè)計(jì)一個(gè)圖書(shū)管理系統(tǒng)，將上述業(yè)務(wù)活動(dòng)借助計(jì)算機(jī)系統(tǒng)完成。2）實(shí)驗(yàn)要求：作為演示系統(tǒng)，不必使用文件，全部數(shù)據(jù)可以在內(nèi)存中存放。3) 實(shí)現(xiàn)提示：建立 B 樹(shù)結(jié)構(gòu)，利用 B 樹(shù)插入、刪除算法做入庫(kù)、出庫(kù)操作。24六、選做實(shí)驗(yàn)內(nèi)容六、選做實(shí)驗(yàn)內(nèi)容（可利用課外實(shí)驗(yàn)學(xué)

41、時(shí)完成）（可利用課外實(shí)驗(yàn)學(xué)時(shí)完成）實(shí)驗(yàn)六實(shí)驗(yàn)六 排序排序一、實(shí)驗(yàn)?zāi)康囊?、?shí)驗(yàn)?zāi)康?、掌握常見(jiàn)的排序算法(插入排序、交換排序、選擇排序、歸并排序、基數(shù)排序等)的思想、特點(diǎn)及其適用條件。2、能夠分析各種算法的效率3、熟練掌握常見(jiàn)的排序算法的程序?qū)崿F(xiàn)。二二. . 實(shí)驗(yàn)學(xué)時(shí)：實(shí)驗(yàn)學(xué)時(shí)：課內(nèi)實(shí)驗(yàn)學(xué)時(shí)：2 學(xué)時(shí)課外實(shí)驗(yàn)學(xué)時(shí)：4 學(xué)時(shí)三、備選實(shí)驗(yàn)題目三、備選實(shí)驗(yàn)題目1 1常見(jiàn)排序算法實(shí)現(xiàn)（實(shí)驗(yàn)類型：驗(yàn)證型）常見(jiàn)排序算法實(shí)現(xiàn)（實(shí)驗(yàn)類型：驗(yàn)證型）1）問(wèn)題描述：輸入一組關(guān)鍵字序列分別實(shí)現(xiàn)下列排序: （1）實(shí)現(xiàn)簡(jiǎn)單選擇排序、直接插入排序和冒泡排序。 （2）實(shí)現(xiàn)希爾排序算法。 （3）實(shí)現(xiàn)快速排序算法。 （4）實(shí)現(xiàn)堆排

42、序算法。 *（5）快速排序的非遞歸算法。 （6）實(shí)現(xiàn)折半插入排序。（7）在主函數(shù)中設(shè)計(jì)一個(gè)簡(jiǎn)單菜單，分別測(cè)試上述算法。252) 實(shí)現(xiàn)提示： 數(shù)據(jù)類型定義（C 語(yǔ)言） # define MAXSIZE 100 /*參加排序元素的最大個(gè)數(shù)*/ typedef struct list int key; RedType; typedef struct RedType rMAXSIZE+1; int length; /*參加排序元素的實(shí)際個(gè)數(shù)*/ SqList; 算法 5 可以借助棧實(shí)現(xiàn)。3）注意問(wèn)題： 在 RedType 中增加一個(gè)數(shù)據(jù)項(xiàng)驗(yàn)證各種排序算法的穩(wěn)定性。 注意理解各種算法的思想、了解算法的適

43、用情況及時(shí)間復(fù)雜度，能夠根據(jù)實(shí)際情況選擇合適的排序方法。2 2統(tǒng)計(jì)成績(jī)：（實(shí)驗(yàn)類型：綜合型）統(tǒng)計(jì)成績(jī)：（實(shí)驗(yàn)類型：綜合型）1）問(wèn)題描述：給出 n 個(gè)學(xué)生的考試成績(jī)表，每條信息由姓名和分?jǐn)?shù)組成，試設(shè)計(jì)一個(gè)算法： 按分?jǐn)?shù)高低次序，打印出每個(gè)學(xué)生在考試中獲得的名次，分?jǐn)?shù)相同的為同一名次； 按名次列出每個(gè)學(xué)生的姓名與分?jǐn)?shù)。2）基本要求：學(xué)生的考試成績(jī)表必須通過(guò)鍵盤(pán)輸入數(shù)據(jù)而建立，同時(shí)要對(duì)輸出進(jìn)行格式控制。26實(shí)驗(yàn)七實(shí)驗(yàn)七 數(shù)組和廣義表數(shù)組和廣義表一、實(shí)驗(yàn)?zāi)康囊弧?shí)驗(yàn)?zāi)康?、掌握稀疏矩陣的表示方法及其運(yùn)算的實(shí)現(xiàn)2、實(shí)現(xiàn)稀疏矩陣在三元組、十字鏈表等表示下的各運(yùn)算并分析其效率二二. . 實(shí)驗(yàn)學(xué)時(shí)：實(shí)驗(yàn)學(xué)時(shí)：

44、課外實(shí)驗(yàn)學(xué)時(shí)：4 學(xué)時(shí)三、備選實(shí)驗(yàn)題目：三、備選實(shí)驗(yàn)題目：1 1稀疏矩陣運(yùn)算器（實(shí)驗(yàn)類型：綜合型）稀疏矩陣運(yùn)算器（實(shí)驗(yàn)類型：綜合型）1）問(wèn)題描述：稀疏矩陣是指那些多數(shù)元素為零的矩陣。利用“稀疏”特點(diǎn)進(jìn)行存儲(chǔ)和計(jì)算可以大大節(jié)省存儲(chǔ)空間，提高計(jì)算效率。本實(shí)驗(yàn)的主要任務(wù)是實(shí)現(xiàn)一個(gè)能進(jìn)行稀疏矩陣基本運(yùn)算的運(yùn)算器。 2）實(shí)驗(yàn)要求： 以“帶行邏輯鏈接信息” 的三元組順序表表示稀疏矩陣，實(shí)現(xiàn)兩個(gè)矩陣相加、相減和相乘的運(yùn)算。稀疏矩陣的輸入形式采用三元組表示，而運(yùn)算結(jié)果的矩陣則以通常的陣列形式列出。 測(cè)試數(shù)據(jù)： 10 0 0 0 0 0 10 0 00 0 9 + 0 0 -1 = 0 0 8-1 0 0 1 0 -3 0 0 -310 0 0 0 10 00 9 + 0 -1 = 0 10-1 0 1 -3 -2 3273）實(shí)現(xiàn)提示 首先應(yīng)輸入矩陣的行數(shù)和列數(shù)，并判別給出的兩個(gè)矩陣的行、列數(shù)對(duì)于所要求作的運(yùn)算