數(shù)據(jù)結(jié)構(gòu)試驗(yàn)指導(dǎo)書V2.0

1、V V 2.02.0數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)指導(dǎo)書實(shí)驗(yàn)指導(dǎo)書編寫：編寫：陸紹飛陸紹飛校核：校核：_湖南大學(xué)軟件學(xué)院湖南大學(xué)軟件學(xué)院20112011 年年 9 9 月月目目 錄錄實(shí)驗(yàn)教學(xué)大綱實(shí)驗(yàn)教學(xué)大綱.1 1一、課程所占的學(xué)時(shí)、學(xué)分及實(shí)驗(yàn)課所占學(xué)時(shí)、學(xué)分.1二、實(shí)驗(yàn)適用專業(yè)：.1三、實(shí)驗(yàn)的任務(wù)、性質(zhì)和目的.1四、實(shí)驗(yàn)的基本理論.1五、實(shí)驗(yàn)方式與基本要求.2六、實(shí)驗(yàn)項(xiàng)目的設(shè)置與內(nèi)容提要.2七、考核方式與評分辦法.3實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)項(xiàng)目 1 1三元組三元組 ADTADT.4 4實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)項(xiàng)目 2 2復(fù)數(shù)四則運(yùn)算復(fù)數(shù)四則運(yùn)算 .6 6實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)項(xiàng)目 3 3基本線性表運(yùn)算基本線性表運(yùn)算 .8

2、8實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)項(xiàng)目 4 4基本線性表就地逆置基本線性表就地逆置 .1313實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)項(xiàng)目 5 5數(shù)數(shù)制制轉(zhuǎn)換轉(zhuǎn)換 .1515實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)項(xiàng)目 6 6回文判斷回文判斷 .1717實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)項(xiàng)目 7 7算術(shù)表達(dá)式求值演示算術(shù)表達(dá)式求值演示 .1919實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)項(xiàng)目 8 8迷宮問題迷宮問題 .2222實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)項(xiàng)目 9 9樹與二叉樹樹與二叉樹 .2727實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)項(xiàng)目 1010圖遍歷演示圖遍歷演示 .3030實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)項(xiàng)目 1111二叉排序樹二叉排序樹 .3333實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)項(xiàng)目 1212內(nèi)部排序算法比較內(nèi)部排序算法比較 .3535實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)項(xiàng)目 1313哈希表設(shè)計(jì)哈希表設(shè)計(jì) .363

3、6實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)項(xiàng)目 1414約瑟夫環(huán)約瑟夫環(huán) .3737實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)項(xiàng)目 1515停車場管理停車場管理 .3838實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)項(xiàng)目 1616旅游導(dǎo)游系統(tǒng)旅游導(dǎo)游系統(tǒng) .3939實(shí)驗(yàn)教學(xué)大綱實(shí)驗(yàn)教學(xué)大綱課程名稱：課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法課程編號(hào)：課程編號(hào)：本大綱主筆人：李睿本大綱主筆人：李睿 陸紹飛修改陸紹飛修改一、課程所占的學(xué)時(shí)、學(xué)分及實(shí)驗(yàn)課所占學(xué)時(shí)、學(xué)分一、課程所占的學(xué)時(shí)、學(xué)分及實(shí)驗(yàn)課所占學(xué)時(shí)、學(xué)分總學(xué)時(shí)：80 總學(xué)分：4實(shí)驗(yàn)課時(shí)：48 實(shí)驗(yàn)學(xué)分：1二、實(shí)驗(yàn)適用專業(yè)：二、實(shí)驗(yàn)適用專業(yè)：軟件工程、計(jì)算機(jī)專業(yè)、通信、信息類本科學(xué)生三、實(shí)驗(yàn)的任務(wù)、性質(zhì)和目的三、實(shí)驗(yàn)的任務(wù)、性質(zhì)和目的數(shù)據(jù)結(jié)構(gòu)與算法

4、是一門技術(shù)性與實(shí)踐性很強(qiáng)的課程，實(shí)驗(yàn)的設(shè)置十分重要。為了幫助學(xué)生更好地學(xué)習(xí)本課程，理解和掌握算法設(shè)計(jì)所需的技術(shù)，為整個(gè)專業(yè)學(xué)習(xí)打好基礎(chǔ)，通過要求完成對一些典型問題的分析及其實(shí)現(xiàn)的各環(huán)節(jié)，使學(xué)生掌握所用到的一些技術(shù)，擴(kuò)充知識(shí)面。通過實(shí)驗(yàn)內(nèi)容的訓(xùn)練，突出構(gòu)造性思維訓(xùn)練的特征，提高學(xué)生組織數(shù)據(jù)與進(jìn)行編寫大型程序能力。同時(shí)，上機(jī)實(shí)習(xí)是對學(xué)生的一種全面綜合的訓(xùn)練，是與課堂聽講、自學(xué)和練習(xí)相輔相成的必不可少的一個(gè)教學(xué)環(huán)節(jié)。實(shí)習(xí)題中的問題比平時(shí)的習(xí)題復(fù)雜得多，也更接近實(shí)際。實(shí)習(xí)著眼于原理與應(yīng)用的結(jié)合點(diǎn)，使學(xué)生學(xué)會(huì)把書上學(xué)到的知識(shí)解決實(shí)際問題，培養(yǎng)軟件工程所需要的動(dòng)手能力；另一方面，能使書本知識(shí)變“活” ，起

5、到深化理解和靈活掌握教學(xué)內(nèi)容的目的。平時(shí)的練習(xí)較偏重于如何編寫功能單一的“小”算法，而實(shí)習(xí)題是軟件設(shè)計(jì)的綜合訓(xùn)練，包括問題分析，總體結(jié)構(gòu)設(shè)計(jì)，用戶界面設(shè)計(jì)，程序設(shè)計(jì)基本技能和技巧，多人合作,以至一整套軟件工作規(guī)范的訓(xùn)練和科學(xué)作風(fēng)的培養(yǎng)。此外，還有很重要的一點(diǎn)是：機(jī)器是比任何教師都嚴(yán)厲的檢查者。四、實(shí)驗(yàn)的基本理論四、實(shí)驗(yàn)的基本理論“數(shù)據(jù)結(jié)構(gòu)與算法”是計(jì)算機(jī)專業(yè)一門重要的專業(yè)技術(shù)基礎(chǔ)課程。本課程較系統(tǒng)地介紹了軟件設(shè)計(jì)中常用的數(shù)據(jù)結(jié)構(gòu)以及相應(yīng)的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)算法；介紹了常用的多種查找和排序技術(shù)，并對進(jìn)行性能分析和比較，內(nèi)容非常豐富。本課程的學(xué)習(xí)將為后續(xù)課程的學(xué)習(xí)以及軟件設(shè)計(jì)水平的提高打下良好的基礎(chǔ)，

6、數(shù)據(jù)結(jié)構(gòu)與算法課程是計(jì)算機(jī)專業(yè)的一門核心的關(guān)鍵性課程。為了使學(xué)生熟練掌握并運(yùn)用所學(xué)知識(shí)，本實(shí)驗(yàn)安排了 16 個(gè)主實(shí)習(xí)單元，除實(shí)習(xí) 1、2作為預(yù)備練習(xí)之外，其它各單元的訓(xùn)練重點(diǎn)在于基本的數(shù)據(jù)結(jié)構(gòu)，而不強(qiáng)調(diào)面面俱到。各實(shí)習(xí)單元與教科書的各章只具有粗略的對應(yīng)關(guān)系，一個(gè)實(shí)習(xí)題常常涉及幾部分教學(xué)內(nèi)容。每個(gè)實(shí)習(xí)題采取統(tǒng)一的格式，由問題描述問題描述、基本要求基本要求、測試數(shù)據(jù)測試數(shù)據(jù)、實(shí)現(xiàn)提示實(shí)現(xiàn)提示和選做內(nèi)選做內(nèi)容容等 5 個(gè)部分組成。問題描述問題描述旨在為讀者建立問題提出的背景環(huán)境，指明問題“是什么”；基本要求基本要求則對問題進(jìn)一步求精，劃出問題的邊界，指出具體的參量或前提條件，并規(guī)定該題的最低限度要求

7、；測試數(shù)據(jù)測試數(shù)據(jù)部分旨在為檢查學(xué)生上機(jī)作業(yè)提供方便，在完成實(shí)習(xí)題時(shí)應(yīng)自己設(shè)計(jì)完整和嚴(yán)格的測試方案，當(dāng)數(shù)據(jù)輸入量較大時(shí)，提倡以文件形式向程序提供輸入數(shù)據(jù)；實(shí)現(xiàn)提示實(shí)現(xiàn)提示對實(shí)現(xiàn)中的難點(diǎn)及其解法思路等問題作了簡要提示；選做內(nèi)容選做內(nèi)容向那些尚有余力的讀者提出了更嚴(yán)峻的挑戰(zhàn)，同時(shí)也能開拓其他讀者的思路，在完成基本要求時(shí)就力求避免就事論事的不良思想方法，盡可能尋求具有普遍意義的解法，使得程序結(jié)構(gòu)合理，容易修改擴(kuò)充。五、實(shí)驗(yàn)方式與基本要求五、實(shí)驗(yàn)方式與基本要求為了培養(yǎng)一個(gè)軟件工作者所應(yīng)具備的科學(xué)工作的方法和作風(fēng)，實(shí)驗(yàn)過程要求按以下 5個(gè)步驟進(jìn)行：1問題分析和任務(wù)定義；2數(shù)據(jù)類型和系統(tǒng)設(shè)計(jì)；3編碼實(shí)現(xiàn)和

8、靜態(tài)檢查；4上機(jī)準(zhǔn)備和上機(jī)調(diào)試；5總結(jié)和整理實(shí)習(xí)報(bào)告。六、實(shí)驗(yàn)項(xiàng)目的設(shè)置與內(nèi)容提要六、實(shí)驗(yàn)項(xiàng)目的設(shè)置與內(nèi)容提要序號(hào)實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)學(xué)時(shí)每組人數(shù)實(shí)驗(yàn)類型實(shí)驗(yàn)要求內(nèi) 容 提 要1抽象數(shù)據(jù)類型（三元組 ADT、復(fù)數(shù)四則運(yùn)算）41綜合 必修實(shí)現(xiàn)創(chuàng)建一個(gè)三元組，實(shí)現(xiàn)其基本操作。設(shè)計(jì)實(shí)現(xiàn)抽象數(shù)據(jù)類型“復(fù)數(shù)”。2線性表（基本線性表運(yùn)算、線性表的逆置）41綜合 必修實(shí)現(xiàn)基本線性表的創(chuàng)建、求基本線性表的長度、在基本線性表中查找某個(gè)數(shù)據(jù)元素、在某個(gè)位置插入一個(gè)新數(shù)據(jù)元素、在某個(gè)線性表中刪除某個(gè)數(shù)據(jù)元素等操作。分別以不同存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表的就地逆置3棧、隊(duì)列與遞歸算法設(shè)計(jì)（數(shù)制轉(zhuǎn)換問題，回文判斷）41設(shè)計(jì) 必修將十進(jìn)制

9、數(shù) N 轉(zhuǎn)換為其它 d 進(jìn)制數(shù)；判斷依次讀入的一個(gè)以為結(jié)束符的字母序列，是否為形如序列 1&序列 2模式的字符序列。其中序列 1 和序列 2中都不含字符&，且序列 2是序列 1 的逆序列4算術(shù)表達(dá)式求值演示41設(shè)計(jì) 選修演示用算符優(yōu)先法對算術(shù)表達(dá)式求值過程。5迷宮問題82設(shè)計(jì) 選修以一個(gè) mn 的長方陣表示迷宮，0 和 1分別表示迷宮中的通路和障礙。設(shè)計(jì)一個(gè)程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。6二叉樹的建立與遍歷、圖遍歷的演示82綜合 必修建立一棵二叉樹，并對其進(jìn)行遍歷（先序、中序、后序） ，打印輸出遍歷結(jié)果。以鄰接表為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)連通無

10、向圖的深度優(yōu)先和廣度優(yōu)先遍歷7二叉排序樹查找42綜合 選修從鍵盤讀入一組數(shù)據(jù)，建立二叉排序樹并對其進(jìn)行查找、遍歷、格式化打印等有關(guān)操作8內(nèi)部排序算法比較、哈希表設(shè)計(jì)83綜合 必修各種內(nèi)部排序算法的時(shí)間復(fù)雜度分析結(jié)果只給出了算法執(zhí)行時(shí)間的階，或大概執(zhí)行時(shí)間。試通過隨機(jī)的數(shù)據(jù)比較各算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動(dòng)次數(shù)，以取得直觀感受；針對某個(gè)集體中人名設(shè)計(jì)一個(gè)哈希表，使得平均查找長度不超過 R，并完成相應(yīng)的建表和查表程序。9約瑟夫環(huán)41設(shè)計(jì) 選修設(shè)計(jì)一個(gè)程序求出按約瑟夫規(guī)則的出列順序。10停車場管理81設(shè)計(jì) 選修為停車場編制按要求進(jìn)行管理的模擬程序11旅游導(dǎo)游問題82設(shè)計(jì) 選修假設(shè)一個(gè)旅游景區(qū)由

11、n 個(gè)不同景點(diǎn)組成（有向網(wǎng)） ，并用帶權(quán)鄰接矩陣表示，權(quán)值表示兩個(gè)景點(diǎn)之間的步行時(shí)間，編寫程序求任意兩個(gè)景點(diǎn)之間的最短步行時(shí)間。七、考核方式與評分辦法七、考核方式與評分辦法以實(shí)驗(yàn)報(bào)告及程序完成情況計(jì)算成績，實(shí)驗(yàn)成績占總成績的 20%。實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)項(xiàng)目 1 1三元組三元組 ADTADT1.11.1 實(shí)驗(yàn)?zāi)康膶?shí)驗(yàn)?zāi)康谋敬螌?shí)驗(yàn)的主要目的是在于幫助讀者熟悉抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)方法。抽象數(shù)據(jù)類型需要借助固有數(shù)據(jù)類型來表示和實(shí)現(xiàn)，即利用高級程序設(shè)計(jì)語言中已經(jīng)存在的數(shù)據(jù)類型來說明新的結(jié)構(gòu)，用已經(jīng)實(shí)現(xiàn)的操作來組合新的操作，具體實(shí)現(xiàn)細(xì)節(jié)依賴于所用語言的功能。通過本次實(shí)驗(yàn)還可幫助學(xué)生復(fù)習(xí)高級語言的使用方法。1

12、.21.2 實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)內(nèi)容 問題描述問題描述 設(shè)計(jì)實(shí)現(xiàn)抽象數(shù)據(jù)類型“三元組” 。每個(gè)三元組由任意三個(gè)實(shí)數(shù)的序列構(gòu)成，基本操作包括：創(chuàng)建一個(gè)三元組，取三元組的任意一個(gè)分量，置三元組的任意一個(gè)分量，求三元組的最大分量，求三元組的最小分量，兩個(gè)三元組的對應(yīng)分量相加或相減，給三元組的各分量同乘一個(gè)比例因子，顯示三元組，銷毀三元組等。 基本要求基本要求 實(shí)現(xiàn)創(chuàng)建一個(gè)三元組，取三元組的任意一個(gè)分量，置三元組的任意一個(gè)分量，求三元組的最大分量，求三元組的最小分量，顯示三元組等基本操作。 算法描述算法描述 template class TriplePrivate: Elem e1; Elem e2 Elem

13、 e3;public: Triple(Elem v1, Elem v2, Elem v3) e1=v1; e2=v2; e3=v3; Elem Get(i) 初始條件：三元組已經(jīng)存在，1i3；操作結(jié)果：返回三元組的第 i 個(gè)分量 Bool put(i,e) 初始條件：三元組已經(jīng)存在，1i3；操作結(jié)果：將三元組的第 i 個(gè)分量賦值為 e，成功返回 true，否則返回 false;Elem GetMax()初始條件：三元組已經(jīng)存在， 操作結(jié)果：返回三元組中最大分量值 e;Elem GetMin()初始條件：三元組已經(jīng)存在， 操作結(jié)果：返回三元組中最小分量值 e;void Output（）初始條件：

14、三元組已經(jīng)存在， 操作結(jié)果：輸出三元組中所有分量值; 測試數(shù)據(jù)測試數(shù)據(jù) 由學(xué)生任意指定。 選作內(nèi)容選作內(nèi)容 實(shí)現(xiàn)兩個(gè)三元組的對應(yīng)分量相加或相減，給三元組的各分量同乘一個(gè)比例因子，銷毀三元組等操作。實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)項(xiàng)目 2 2復(fù)數(shù)四則運(yùn)算復(fù)數(shù)四則運(yùn)算2.12.1 實(shí)驗(yàn)?zāi)康膶?shí)驗(yàn)?zāi)康谋敬螌?shí)驗(yàn)與實(shí)驗(yàn)項(xiàng)目 1 為同一類型實(shí)驗(yàn)，主要目的是在于幫助讀者進(jìn)一步熟悉抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)方法。抽象數(shù)據(jù)類型需要借助固有數(shù)據(jù)類型來表示和實(shí)現(xiàn)，即利用高級程序設(shè)計(jì)語言中已經(jīng)存在的數(shù)據(jù)類型來說明新的結(jié)構(gòu)，用已經(jīng)實(shí)現(xiàn)的操作來組合新的操作，具體實(shí)現(xiàn)細(xì)節(jié)依賴于所用語言的功能。2.22.2 實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)內(nèi)容 問題描述問題描述 設(shè)計(jì)

15、實(shí)現(xiàn)一個(gè)可進(jìn)行復(fù)數(shù)運(yùn)算的演示程序。 基本要求基本要求 實(shí)現(xiàn)下列六種基本運(yùn)算：1） 由輸入的實(shí)部和虛部生成一個(gè)復(fù)數(shù)；2） 兩個(gè)復(fù)數(shù)求和；3） 兩個(gè)復(fù)數(shù)求差；4） 兩個(gè)復(fù)數(shù)求積；5） 從已知復(fù)數(shù)中分離出實(shí)部；6） 從已知復(fù)數(shù)中分離出虛部；運(yùn)算結(jié)果以相應(yīng)的復(fù)數(shù)或?qū)崝?shù)的表示形式顯示。 算法描述算法描述 該算法中 Elem 為 float 或 double 類型template class ComplexPrivate: Elem reality; Elem falsehoodpublic: Triple(Elem r, Elem f) reality=r; falsehood=f; Complex o

16、perate+(const complex &)初始條件：已經(jīng)存在兩個(gè)復(fù)數(shù)；操作結(jié)果：將兩個(gè)復(fù)數(shù)的實(shí)部和虛部分別進(jìn)行向加得到一個(gè)新的復(fù)數(shù)Complex operate-(const complex &)初始條件：已經(jīng)存在兩個(gè)復(fù)數(shù)；操作結(jié)果：將兩個(gè)復(fù)數(shù)的實(shí)部和虛部分別進(jìn)行向減得到一個(gè)新的復(fù)數(shù)Complex operate*(const complex &)初始條件：已經(jīng)存在兩個(gè)復(fù)數(shù)；操作結(jié)果：按照復(fù)數(shù)乘法規(guī)則將兩個(gè)復(fù)數(shù)的實(shí)部相乘結(jié)果減去兩個(gè)復(fù)數(shù)虛部相乘結(jié)果為新生成復(fù)數(shù)的實(shí)部；將兩個(gè)復(fù)數(shù)的虛部和實(shí)部交叉相乘再相加的結(jié)果作為新生成復(fù)數(shù)的虛部。 Elem reality() 初

17、始條件：復(fù)數(shù)已經(jīng)存在；操作結(jié)果：返回復(fù)數(shù)的實(shí)部;Elem falsehood () 初始條件：復(fù)數(shù)已經(jīng)存在；操作結(jié)果：返回復(fù)數(shù)的虛部;void Output（）初始條件：復(fù)數(shù)已經(jīng)存在， 操作結(jié)果：以復(fù)數(shù)形式輸出復(fù)數(shù)到屏幕上; 測試數(shù)據(jù)測試數(shù)據(jù) 由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)，如復(fù)數(shù) 0。 實(shí)現(xiàn)提示實(shí)現(xiàn)提示 定義復(fù)數(shù)為兩個(gè)相互之間存在次序關(guān)系的實(shí)數(shù)構(gòu)成抽象數(shù)據(jù)類型，利用實(shí)數(shù)的操作來實(shí)現(xiàn)復(fù)數(shù)的操作。 選作內(nèi)容選作內(nèi)容 實(shí)現(xiàn)復(fù)數(shù)的其他運(yùn)算，如：兩個(gè)復(fù)數(shù)相除、求共軛。實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)項(xiàng)目 3 3基本線性表運(yùn)算基本線性表運(yùn)算3.13.1 實(shí)驗(yàn)?zāi)康膶?shí)驗(yàn)?zāi)康模?）掌握基本線性表順序存儲(chǔ)的

18、類型定義及 C+語言實(shí)現(xiàn)。（2）掌握基本線性表鏈?zhǔn)酱鎯?chǔ)的類型定義及 C+語言實(shí)現(xiàn)。（3）掌握基本線性表順序存儲(chǔ)結(jié)構(gòu)中的各種基本操作。（4）掌握基本線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中的各種基本操作。3.23.2 實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)內(nèi)容 問題描述問題描述 基本線性表經(jīng)常進(jìn)行的運(yùn)算操作有創(chuàng)建基本線性表、求基本線性表的長度、在基本線性表中查找某個(gè)數(shù)據(jù)元素、在某個(gè)位置插入一個(gè)新數(shù)據(jù)元素、在某個(gè)線性表中刪除某個(gè)數(shù)據(jù)元素以及基本線性表的輸出等操作。試編程實(shí)現(xiàn)基本線性表的這些基本運(yùn)算。 基本要求基本要求 實(shí)現(xiàn)基本線性表的基本運(yùn)算可以采用鏈?zhǔn)酱鎯?chǔ)方式實(shí)現(xiàn)，也可以采用順序存儲(chǔ)的方式實(shí)現(xiàn)，在此給出這兩種存儲(chǔ)方式的實(shí)現(xiàn)方法，學(xué)生可任選其

19、一進(jìn)行具體實(shí)現(xiàn)。 算法描述算法描述 1 順序存儲(chǔ)方式templet class AList：public Listprivate: int maxSize; int listSize; int fence; Elem* listArray;public:/線性表創(chuàng)建操作實(shí)現(xiàn) AList(int size=DefaultListSize) maxSize=size; listSize=fence=0; listArray=new ElemmaxSize AList()delete listArray; void clear() delete listArray; listSize=fence=0

20、; listArray=new ElemmaxSize; bool insert(const Elem&); bool append(const Elem&); bool remove(Elem&); void setStart()fence=0;void setEnd()fence=listSize; void prev()if(fence!=0) fence-; void next()if(fence=0)&(pos=0)&(pos=listSize) /線性表中插入操作實(shí)現(xiàn)templet bool AList: insert(const Elem&

21、amp;item) if(listSize=maxSize) return false; for (int i=listSize;ifence;i-) listArrayi=listArrayi-1;listArrayfence=item; listSize+; return true; /在線性表末尾追加數(shù)據(jù)操作實(shí)現(xiàn)templet bool AList: append(const Elem&item) if(listSize=maxSize)return false; listArraylistSize+=item; return true; /線性表中刪除操作實(shí)現(xiàn)templet b

22、ool AList: remove(Elem&it) if(rightlLenth()=0)return false; it=listArrayfence; for(int i=fence;ilistSize-1;i+) listArrayi=listArrayi+1; listSize-; return true; /線性表中查找操作實(shí)現(xiàn)templet bool AList:bool find(Elem k) Elem it; for(L.setStart();L.getValue(it);L.next() if(K=it) return true;/found it return

23、false;/ K not found2 鏈?zhǔn)酱鎯?chǔ)方式template class LList:public List private: Link*head; Link*tail; Link*fence; int leftcnt, rightcnt;/基本線性表的創(chuàng)建操作實(shí)現(xiàn) void init() fence=head=tail=new Link; leftcnt=rightcnt=0; /init void removeall() while(head!=null) fence=head;head=head.next; delete fence; /removeall public: LL

24、ist(int size=DefaultListSize)init(); LList()removeall(); void clear()removeall(); init(); bool insert(const Elem&); bool append(const Elem&); bool remove(Elem&); void setStart() fence=head;rightcnt+=leftcnt; leftcnt=0; /setStart; void setEnd() fence=tail;leftcnt+=rightcnt;rightcnt=0; /se

25、tEnd void prev(); void next() if(fence!=tail)fence=fence-next; rightcnt-; leftcnt+ /next; int leftLength()const return leftcnt; int rightLength() constreturn rightcnt;bool setPos(int Pos); bool getValue(Elem &it) const if(rightLength()=0) return false; it=fence-next-element; return true; /getVal

26、ue void print() const;/基本線性表插入操作的實(shí)現(xiàn)template bool LList:insert(const Elem&item) fence-next=new Link(item,fence-next); if(tail=fence)tail=fence-next; rightcnt+; return true; /基本線性表末尾追加數(shù)據(jù)操作的實(shí)現(xiàn)template bool LList:append(const Elem&item) tail=tail-next=new Link(item,null); rightcnt+; return true;

27、 /基本線性表刪除操作的實(shí)現(xiàn)template bool LList:remove(Elem& it) if(fence-next=NULL) return false; it=fence-next-element; Link*Itemp=fence-next; fence-next=Itemp-next; if(tail=Itemp) tail=fence; delete Itemp rightcnt-; return true; template void LList:prev() Link * temp=head; if (fence=head) return; while(tem

28、p-next!=fence) temp=temp-next; fence=temp; leftcnt-; rightcnt+;template bool LList:setPos(int pos) if(pos(rightcnt+leftcnt) return false; setStart(); for(int i=0;ipos;i+) next(); return true; template void LList:print() const Linl*temp=head; cout“”; while(temp!=fence) coutnext-elementnext; /while; c

29、outnext=NULL) coutnext-elementnext; /while;coutn”; 測試數(shù)據(jù)測試數(shù)據(jù) 由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)。 實(shí)驗(yàn)提示實(shí)驗(yàn)提示 （1）基本線性表是數(shù)據(jù)結(jié)構(gòu)中最簡單、最常用的數(shù)據(jù)類型，它是學(xué)習(xí)其他數(shù)據(jù)結(jié)構(gòu)類型的基礎(chǔ)。因此，雖然基本線性表相對較為簡單，但其各種運(yùn)算內(nèi)容較多，只有熟練掌握和理解基本線性表的基本內(nèi)涵才能在解決實(shí)際問題的過程中準(zhǔn)確運(yùn)用。（2）基本線性表的表示與存儲(chǔ)是基本線性表進(jìn)行各種運(yùn)算的基礎(chǔ)，所以，基本線性表中各個(gè)數(shù)據(jù)元素之間的邏輯和存儲(chǔ)關(guān)系必須要在各種運(yùn)算中準(zhǔn)確體現(xiàn)。不能有任何的思路混淆，也不能有任何的不確定性。 選

30、作內(nèi)容選作內(nèi)容 兩個(gè)線性表的并、交、差等運(yùn)算的實(shí)現(xiàn)。實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)項(xiàng)目 4 4基本線性表就地逆置基本線性表就地逆置4.14.1 實(shí)驗(yàn)?zāi)康膶?shí)驗(yàn)?zāi)康倪M(jìn)一步掌握基本線性表的各種操作，深入理解線性表的存儲(chǔ)方式。4.24.2 實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)內(nèi)容 問題描述問題描述 基本線性表就地逆置是指在基本線性表現(xiàn)有空間的基礎(chǔ)上，將基本線性表中的數(shù)據(jù)元素交換位置排列，排列完之后，新的順序序列與原來的順序序列剛好相反。如原來順序序列“abcdef”，就地逆置后的新順序序列為“fedcba”。根據(jù)基本線性表的鏈?zhǔn)胶晚樞騼煞N存儲(chǔ)結(jié)構(gòu)分別完成：（1）順序結(jié)構(gòu)的就地逆置。（2）鏈?zhǔn)浇Y(jié)構(gòu)的就地逆置。 基本要求基本要求 充分理解題目要求

31、，在對基本線性表逆置時(shí)，必須是在基本線性表原有空間的基礎(chǔ)上進(jìn)行，不能借助臨時(shí)變量所生成的臨時(shí)空間，也不能借助其他形式的臨時(shí)空間。且算法時(shí)間復(fù)雜度要求為 O(n)。 算法描述算法描述 針對兩種存儲(chǔ)結(jié)構(gòu)的基本線性表實(shí)現(xiàn)就地逆置的方法有多種，每種存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)方法選擇一種講解。（1）順序結(jié)構(gòu)基本線性表就地逆置。首先，創(chuàng)建一個(gè)包含若干個(gè)結(jié)點(diǎn)的基本線性表，由于在基本線性表的順序存儲(chǔ)結(jié)構(gòu)中，數(shù)據(jù)元素的個(gè)數(shù)往往會(huì)少于所申請的存儲(chǔ)單元數(shù)，因此，可以利用空閑存儲(chǔ)單元中的某一個(gè)單元為中間單元，將基本線性表中前后對應(yīng)位置上的數(shù)據(jù)元素交換位置，具體方法是將基本線性表的第 1 個(gè)數(shù)據(jù)元素和最后一個(gè)數(shù)據(jù)元素交換位置，第

32、2 個(gè)數(shù)據(jù)元素和倒數(shù)第 2個(gè)數(shù)據(jù)元素交換位置，.，依次類推，直到所有元素都交換了位置，則就地逆置的過程就完成了。算法簡單描述如下：template void Alist:reverlist( ) int i; for(i=0; ilistSize/2; i+) listArraylistSize+1=listArrayi;/將第 listSize+1 號(hào)單元作為中間存儲(chǔ)單元listArrayi=listArraylistSize-i-1;listArraylistSize-i-1= listArraylistSize+1;思考：當(dāng)基本隊(duì)列滿時(shí)應(yīng)該如何處理？（2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)就地逆置為清楚對比基

33、本線性表在逆置前后的變化，鏈?zhǔn)交揪€性表的逆置過程可分為 4 個(gè)步驟進(jìn)行：a)創(chuàng)建包含若干個(gè)結(jié)點(diǎn)的鏈?zhǔn)交揪€性表。利用 for 循環(huán)，從鍵盤上隨機(jī)輸入結(jié)點(diǎn)的個(gè)數(shù)和每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域的值。b)輸出創(chuàng)建成功的鏈?zhǔn)交揪€性表。從表頭到表尾逐個(gè)輸出鏈表中所有結(jié)點(diǎn)的值。c)逆置鏈?zhǔn)交揪€性表。設(shè)鏈?zhǔn)交揪€性表有一個(gè)頭結(jié)點(diǎn)，將鏈?zhǔn)交揪€性表斷開成兩部分，第一部分為只有頭結(jié)點(diǎn)，第二部分為所有含有數(shù)據(jù)元素的結(jié)點(diǎn)。從第二部分中依次取出結(jié)點(diǎn)插入到第一部分的頭結(jié)點(diǎn)后；將第二部分所有結(jié)點(diǎn)插入到第一部分后，就完成了鏈?zhǔn)交揪€性表的逆置（思考：問什么？）d)輸出逆置后的鏈?zhǔn)交揪€性表。核心算法簡單描述如下：template

34、 void class LList:reverlist() Link* p,*q; p=head-next; head-next=NULL;/鏈?zhǔn)骄€性表分為兩部分 while(p!=NULL) q=p; p=p-next; q-next=head-next;head-next=q; 測試數(shù)據(jù)測試數(shù)據(jù) 由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)，如對空線性表進(jìn)行逆置，以及當(dāng)順序線性表表滿時(shí)進(jìn)行逆置。 實(shí)現(xiàn)提示實(shí)現(xiàn)提示 （1）基本線性表的輸入和輸出可以有不同的形式，但是基本線性表的特征不會(huì)改變，不管在實(shí)際問題中要求用何種形式對基本線性表進(jìn)行輸入和輸出，首先必須確定基本線性表用何種存儲(chǔ)方

35、式更為便利。（2）在確定其存儲(chǔ)結(jié)構(gòu)之后，該選用何種解決方案更容易編程實(shí)現(xiàn)、更能有效地組織數(shù)據(jù)，也是在編程之前應(yīng)該考慮的事情。 選作內(nèi)容選作內(nèi)容 無。實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)項(xiàng)目 5 5數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換5.15.1 實(shí)驗(yàn)?zāi)康膶?shí)驗(yàn)?zāi)康膬H僅認(rèn)識(shí)到棧是一種特殊的線性表是遠(yuǎn)遠(yuǎn)不夠的，本次實(shí)習(xí)的目的在于使讀者深入了解棧的特征，以便在實(shí)際問題背景下靈活運(yùn)用它們；同時(shí)還將鞏固這種結(jié)構(gòu)的構(gòu)造方法，接觸較復(fù)雜問題的遞歸算法設(shè)計(jì)。5.25.2 實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)內(nèi)容 問題描述問題描述 十進(jìn)制 N 和其它進(jìn)制數(shù)的轉(zhuǎn)換是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的基本問題,其解決方法很多,其中一個(gè)簡單算法基于下列原理: N=(n div d)*d+n mod d

36、( 其中:div 為整除運(yùn)算,mod 為求余運(yùn)算) 例如 (1348)10=(2504)8，其運(yùn)算過程如下：n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2從中我們可以看出，最先產(chǎn)生的余數(shù) 4 是轉(zhuǎn)換結(jié)果的最低位，這正好符合棧的特性即后進(jìn)先出的特性。所以可以用順序棧來模擬這個(gè)過程。試編程實(shí)現(xiàn)將 10 進(jìn)制數(shù)轉(zhuǎn)換成 N 進(jìn)制數(shù)。 基本要求基本要求 對于鍵盤輸入的任意一個(gè)非負(fù)的十進(jìn)制整數(shù)，打印輸出與其等值的八進(jìn)制數(shù)。由于上述的計(jì)算過程是從低位到高位順序產(chǎn)生的八進(jìn)制數(shù)的各個(gè)數(shù)位，而打印輸出，一般來說應(yīng)從高位到地位進(jìn)行，恰好和計(jì)算過程相反。因此可以先

37、將計(jì)算過程中得到的八進(jìn)制數(shù)的各位進(jìn)棧，待相對應(yīng)的八進(jìn)制數(shù)的各位均產(chǎn)生以后，再使其按順序出棧，并打印輸出。即得到了與輸入的十進(jìn)制數(shù)相對應(yīng)的八進(jìn)制數(shù)。 算法描述算法描述 算法思想如下：當(dāng) N0 時(shí)重復(fù) 1，21.若 N0，則將 N % r 壓入棧 s 中 ，執(zhí)行 2;若 N=0，將棧 s 的內(nèi)容依次出棧，算法結(jié)束。2.用 N / r 代替 N具體描述如下：void conversion( ) Stack s; scanf (“%”,n); while(n) s.push(n%8); n=n/8; while(! s.pop(e) printf(“%d”,e); 測試數(shù)據(jù)測試數(shù)據(jù) 由學(xué)生依據(jù)軟件工程

38、的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)。 實(shí)現(xiàn)提示實(shí)現(xiàn)提示 無。 選作內(nèi)容選作內(nèi)容 無。實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)項(xiàng)目 6 6回文判斷回文判斷6.16.1 實(shí)驗(yàn)?zāi)康膶?shí)驗(yàn)?zāi)康谋敬螌?shí)習(xí)的目的在于進(jìn)一步使讀者深入了解棧和隊(duì)列的特征，以便在實(shí)際問題背景下靈活運(yùn)用它們；同時(shí)還將鞏固這兩種結(jié)構(gòu)的構(gòu)造方法，接觸較復(fù)雜問題的遞歸算法設(shè)計(jì)。6.26.2 實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)內(nèi)容 問題描述問題描述 試寫一個(gè)算法，判斷依次讀入的一個(gè)以為結(jié)束符的字母序列，是否為形如序列 1&序列 2模式的字符序列。其中序列 1 和序列 2 中都不含字符&，且序列 2是序列 1 的逆序列。例如，a+b&b+a是屬該模式的字符序列，而+

39、&則不是。 基本要求基本要求 對于鍵盤輸入的任意一個(gè)字符串，將其進(jìn)行逆置，判斷原串和逆置的串是否完全一致，完全一致則為回文，因此分別利用隊(duì)列的先進(jìn)先出（FIFO）和棧的后進(jìn)先出（FILO）實(shí)現(xiàn)，算法只能使用一個(gè)棧和一個(gè)隊(duì)列以及若干簡單類型變量，算法時(shí)間復(fù)雜度應(yīng)為 O(n)。 算法描述算法描述 對于鍵盤輸入的任意一個(gè)字符串，將每一個(gè)字符分別進(jìn)行如棧和入隊(duì)操作，字符串輸入完后，分別從隊(duì)列和堆棧中取出字符進(jìn)行比較，一旦發(fā)現(xiàn)不同則輸入字符串不是回文，如果將所有字符比較結(jié)束后沒有發(fā)現(xiàn)一對字符不同，則輸入字符串為回文。具體算法簡單描述如下：bool palindrome( ) Queue q=ne

40、w Queue;/ Stack s=new Stack;/ while(c=getchar()!=EOF)/字符串輸入沒有結(jié)束 q.Enqueue(c); s.Push(c); while(s.pop(e)&q.Dequeue(f) if(e!=f) return false; return true; 測試數(shù)據(jù)測試數(shù)據(jù) 由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)，如序列 1 和序列 2 均為空串。 實(shí)現(xiàn)提示實(shí)現(xiàn)提示 利用隊(duì)列的先進(jìn)先出（FIFO）和棧的后進(jìn)先出（LIFO）特點(diǎn)，將字符串中字符分別進(jìn)行入棧和入隊(duì)操作，字符串輸入結(jié)束后將隊(duì)列和棧中字符依次取出，判斷取出的一對字

41、符是否相同。 選作內(nèi)容選作內(nèi)容 無。實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)項(xiàng)目 7 7算術(shù)表達(dá)式求值演示算術(shù)表達(dá)式求值演示7.17.1 實(shí)驗(yàn)?zāi)康膶?shí)驗(yàn)?zāi)康谋敬螌?shí)習(xí)的目的在于進(jìn)一步使讀者深入了解棧和隊(duì)列的特征，以便在實(shí)際問題背景下靈活運(yùn)用它們；同時(shí)還將鞏固這兩種結(jié)構(gòu)的構(gòu)造方法，接觸較復(fù)雜問題的遞歸算法設(shè)計(jì)。7.27.2 實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)內(nèi)容 問題描述問題描述 表達(dá)式求值是實(shí)現(xiàn)程序設(shè)計(jì)語言的基本問題之一，也是棧的應(yīng)用的一個(gè)典型例子。設(shè)計(jì)一個(gè)程序，演示用算符優(yōu)先法對算術(shù)表達(dá)式求值的過程。 基本要求基本要求 以字符序列的形式從終端輸入語法正確的、不含變量的整數(shù)表達(dá)式。按照算符優(yōu)先關(guān)系，實(shí)現(xiàn)對算術(shù)四則混合運(yùn)算表達(dá)式的求值，并演示求值過

42、程中運(yùn)算符棧、運(yùn)算數(shù)棧、輸入字符和主要操作的變化過程。 算法描述算法描述 達(dá)式作為一個(gè)滿足表達(dá)式語法規(guī)則的串存儲(chǔ)，如表達(dá)式“3*2（4+2*2-*3）-5”,它的的求值過程為：自左向右掃描表達(dá)式，當(dāng)掃描到 3*2 時(shí)不能馬上計(jì)算，因?yàn)楹竺婵赡苓€有更高的運(yùn)算，正確的處理過程是：需要兩個(gè)棧：對象棧 s1 和算符棧 s2。當(dāng)自左至右掃描表達(dá)式的每一個(gè)字符時(shí)，若當(dāng)前字符是運(yùn)算對象，入對象棧，是運(yùn)算符時(shí)，若這個(gè)運(yùn)算符比棧頂運(yùn)算符高則入棧，繼續(xù)向后處理，若這個(gè)運(yùn)算符比棧頂運(yùn)算符低則從對象棧出棧兩個(gè)運(yùn)算量，從算符棧出棧一個(gè)運(yùn)算符進(jìn)行運(yùn)算，并將其運(yùn)算結(jié)果入對象棧，繼續(xù)處理當(dāng)前字符，直到遇到結(jié)束符。根據(jù)運(yùn)算規(guī)則

43、，左括號(hào)“（”在棧外時(shí)它的級別最高，而進(jìn)棧后它的級別則最低了; 乘方運(yùn)算的結(jié)合性是自右向左，所以，它的棧外級別高于棧內(nèi); 就是說有的運(yùn)算符棧內(nèi)棧外的級別是不同的。當(dāng)遇到右括號(hào)“） ”時(shí)，一直需要對運(yùn)算符棧出棧，并且做相應(yīng)的運(yùn)算，直到遇到棧頂為左括號(hào)“(”時(shí)，將其出棧，因此右括號(hào)“） ”級別最低但它是不入棧的。對象棧初始化為空，為了使表達(dá)式中的第一個(gè)運(yùn)算符入棧，算符棧中預(yù)設(shè)一個(gè)最低級的運(yùn)算符“（” 。根據(jù)以上分析，每個(gè)運(yùn)算符棧內(nèi)、棧外的級別如下：算符 棧內(nèi)級別 棧外級別*、/ 4 3+、- 2 1( 0 5） 0 0運(yùn)算規(guī)則如下：設(shè)兩個(gè)運(yùn)算符： 1 ， 2， a 1 b 2 c1 2, 1 優(yōu)先

44、權(quán)高于 2，可以運(yùn)算算法簡單描述如下：設(shè)置兩個(gè)棧，分別存放操作數(shù)和運(yùn)算符；輸入操作數(shù)時(shí)，一定不會(huì)運(yùn)算；運(yùn)算過程實(shí)際就是運(yùn)算符號(hào)比較的過程OpendType EvaluateExpression( ) /表達(dá)式求值Stack OPTR;OPTR.Push( # );Stack OPND;c = getchar( );while( !(c = # & GetTop( OPTR ) = #) )if( ! In( c, OP )/ c 是運(yùn)算符？,OP 是運(yùn)算符集合OPND.Push(c);c = getchar( );else OPTR.topValue(OPTRType it);swit

45、ch( Precede (it,c)case : OPTR .Pop(t );OPND.Pop( b );OPND.Pop( a );OPND.Push(Operate( a, t, b );break;/ switch/ if/ whileOPND.topValue(a);/ EvaluateExpression 測試數(shù)據(jù)測試數(shù)據(jù) 3*（7-2） ；8； 1+2+3+4； 88-1*5； 1024/4*8； 1024/（4*8） ；（20+2）*（6/2） ； 3-3-3； 8/（9-9） ； 2*（6+2*（3+6*（6+6） ） ） 實(shí)現(xiàn)提示實(shí)現(xiàn)提示 （1）設(shè)置運(yùn)算符棧和運(yùn)算數(shù)棧輔助分析

46、算符優(yōu)先關(guān)系。（2）在讀入表達(dá)式的字符序列的同時(shí)，完成運(yùn)算符和運(yùn)算數(shù)（整數(shù)）的識(shí)別處理，以及相應(yīng)的運(yùn)算。（3）在識(shí)別出運(yùn)算數(shù)的同時(shí)，要將其字符序列形式轉(zhuǎn)換成整數(shù)形式。（4）在程序的適當(dāng)位置輸出運(yùn)算符棧、運(yùn)算數(shù)棧、輸入字符和主要操作的內(nèi)容。 選作內(nèi)容選作內(nèi)容 （1）擴(kuò)充運(yùn)算符集，如增加乘方、單目減、賦值等運(yùn)算。（2）運(yùn)算量可以是變量。（3）運(yùn)算量可以是實(shí)數(shù)類型。（4）計(jì)算器的功能和仿真界面。實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)項(xiàng)目 8 8迷宮問題迷宮問題8.18.1 實(shí)驗(yàn)?zāi)康膶?shí)驗(yàn)?zāi)康谋敬螌?shí)習(xí)的目的在于進(jìn)一步使讀者深入了解棧和隊(duì)列的特征，以便在實(shí)際問題背景下靈活運(yùn)用它們；同時(shí)還將鞏固這兩種結(jié)構(gòu)的構(gòu)造方法，接觸較復(fù)雜問題的

47、遞歸算法設(shè)計(jì)。8.28.2 實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)內(nèi)容 問題描述問題描述 以一個(gè) mn 的長方陣表示迷宮，0 和 1 分別表示迷宮中的通路和障礙。設(shè)計(jì)一個(gè)程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。 基本要求基本要求 首先實(shí)現(xiàn)一個(gè)以鏈表作為存儲(chǔ)結(jié)構(gòu)的棧類型，然后編寫一個(gè)求解迷宮的非遞歸程序。求得的通路以三元組（i,j,d）的形式輸出，其中：（i,j）指示迷宮的一個(gè)坐標(biāo)，d 表示走到下一坐標(biāo)的方向。如：對于下列數(shù)據(jù)的迷宮，輸出的一條通路為：（1，1，1） ， （1，2，2） ，（2，2，2） ， （3，2，3） ， （3，1，2） ，。 算法描述算法描述 這是實(shí)驗(yàn)心理學(xué)中的一

48、個(gè)經(jīng)典問題，心理學(xué)家把一只老鼠從一個(gè)無頂蓋的大盒子的入口處趕進(jìn)迷宮。迷宮中設(shè)置很多隔壁，對前進(jìn)方向形成了多處障礙，心理學(xué)家在迷宮的唯一出口處放置了一塊奶酪，吸引老鼠在迷宮中尋找通路以到達(dá)出口。求解思想：回溯法是一種不斷試探且及時(shí)糾正錯(cuò)誤的搜索方法。下面的求解過程采用回溯法。從入口出發(fā)，按某一方向向前探索，若能走通（未走過的） ，即某處可以到達(dá)，則到達(dá)新點(diǎn)，否則試探下一方向 ; 若所有的方向均沒有通路，則沿原路返回前一點(diǎn)，換下一個(gè)方向再繼續(xù)試探，直到所有可能的通路都探索到，或找到一條通路，或無路可走又返回到入口點(diǎn)。在求解過程中，為了保證在到達(dá)某一點(diǎn)后不能向前繼續(xù)行走（無路）時(shí)，能正確返回前一點(diǎn)以

49、便繼續(xù)從下一個(gè)方向向前試探，則需要用一個(gè)棧保存所能夠到達(dá)的每一點(diǎn)的下標(biāo)及從該點(diǎn)前進(jìn)的方向。 需要解決的四個(gè)問題：1表示迷宮的數(shù)據(jù)結(jié)構(gòu)：設(shè)迷宮為 m 行 n 列，利用 mazemn來表示一個(gè)迷宮，mazeij=0 或 1; 其中：0 表示通路，1 表示不通，當(dāng)從某點(diǎn)向下試探時(shí)，中間點(diǎn)有 8 個(gè)方向可以試探， （見圖3.4）而四個(gè)角點(diǎn)有 3 個(gè)方向，其它邊緣點(diǎn)有 5 個(gè)方向，為使問題簡單化我們用mazem+2n+2來表示迷宮，而迷宮的四周的值全部為 1。這樣做使問題簡單了，每個(gè)點(diǎn)的試探方向全部為 8，不用再判斷當(dāng)前點(diǎn)的試探方向有幾個(gè)，同時(shí)與迷宮周圍是墻壁這一實(shí)際問題相一致。 如圖 8.1 表示的迷

50、宮是一個(gè) 68 的迷宮。 入口坐標(biāo)為（1，1） ，出口坐標(biāo)為（m，n） 。 入口(1,1) 01234567890111111111111011101111211010111113101000001141011101111511001100016101100110171111111111 出口 (6,8) 圖 8.1 用 mazem+2n+2表示的迷宮迷宮的定義如下：#define m 6 /* 迷宮的實(shí)際行 */#define n 8 /* 迷宮的實(shí)際列 */int maze m+2n+2 ;2試探方向：在上述表示迷宮的情況下，每個(gè)點(diǎn)有 8 個(gè)方向去試探，如當(dāng)前點(diǎn)的坐標(biāo)(x,y)，與其相鄰的

51、 8 個(gè)點(diǎn)的坐標(biāo)都可根據(jù)與該點(diǎn)的相鄰方位而得到，如圖 8.2 所示。因?yàn)槌隹谠冢╩，n） ，因此試探順序規(guī)定為：從當(dāng)前位置向前試探的方向?yàn)閺恼龞|沿順時(shí)針方向進(jìn)行。為了簡化問題，方便的求出新點(diǎn)的坐標(biāo)，將從正東開始沿順時(shí)針進(jìn)行的這 8 個(gè)方向的坐標(biāo)增量放在一個(gè)結(jié)構(gòu)數(shù)組 move 8 中，在 move 數(shù)組中，每個(gè)元素有兩個(gè)域組成，x：橫坐標(biāo)增量，y：縱坐標(biāo)增量。move 數(shù)組如圖 8.3 所示。Move 數(shù)組定義如下：typedef struct int x，y item ; item move8 ;這樣對 move 的設(shè)計(jì)會(huì)很方便地求出從某點(diǎn) (x，y) 按某一方向 v (0=v5,8,25,7

52、,05,6,04,5,1top 3,6,03,6,3 3,5,03,5,0 3,4,03,4,0 3,3,03,3,0 2,2,12,2,1 1,1,11,1,1出棧 ;求出下一個(gè)要試探的方向 d+ ; while （還有剩余試探方向時(shí)） if （d 方向可走）則 （x , y , d）入棧 ; 求新點(diǎn)坐標(biāo) (i, j ) ;將新點(diǎn)（i , j）切換為當(dāng)前點(diǎn)（x , y） ; if ( (x ,)= =(,n) ) 結(jié)束 ; else 重置 d=0 ; else d+ ; 算法如下： int path(maze，move) int mazemn ; item move8 ; SeqStack

53、s ; datetype temp ; int x, y, d, i, j ; temp.x=1 ; temp.y=1 ; temp.d=-1 ; s.Push(temp) ; while (!s.Empty() s.Pop(temp) ;x=temp.x ; y=temp.y ; d=temp.d+1 ;while (d8) i=x+moved.x ; j=y+moved.y ;if ( mazeij= =0 ) temp=x, y, d ; s.Push (temp ) ; x=i ; y=j ; mazexy= -1 ; if (x=m&y= =n) return 1 ; /*迷

54、宮有路*/ else d=0 ; else d+ ; /*while (ddata=ch;createbintree(&(*t)-leftChild);createbintree(&(*t)-rightChild);(2) 用前序、中序兩種不同的方法進(jìn)行遍歷。這兩種遍歷可分別用遞歸方式和非遞歸方式實(shí)現(xiàn)，其遞歸方式相當(dāng)簡捷。在此只給出中序遍歷的非遞歸算法：template void BinaryTree : PreOrder ( ) stack BinTreeNode * st; BinTreeNode *p = root; do while (p != NULL) cout d

55、ata; st. Push (p); p = p -leftChild; if ( St. length()!=0) st. pop (p ); p = p - rightChild; while (p != NULL | | st.length ( )!=0);（3）交換二叉樹中所有結(jié)點(diǎn)的左、右子樹。 交換過程中，同樣需要借助一個(gè)指針棧來實(shí)現(xiàn)。最先交換二叉樹中樹根結(jié)點(diǎn)的左、右子樹，然后再在其左、右子樹中分別遞歸調(diào)用該函數(shù)，直到所有的結(jié)點(diǎn)的左、右子樹都完成交換為止。 （4）用前序、中序兩種不同的方法進(jìn)行遍歷交換左、右子樹之后的二叉樹，其實(shí)現(xiàn)過程同（2） 。 測試數(shù)據(jù)測試數(shù)據(jù) ABCDEGF（其

56、中 表示空格字符） 。則輸出結(jié)果為 先序：ABCDEGF中序：CBEGDFA 實(shí)現(xiàn)提示實(shí)現(xiàn)提示 樹是較基本線性表和特殊線性表稍微復(fù)雜一點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，它的復(fù)雜性體現(xiàn)在數(shù)據(jù)元素的輸入和輸出形式上更為多樣。由于數(shù)據(jù)元素之間的關(guān)系稍微較線性表復(fù)雜，因此在數(shù)據(jù)的組織形式和輸入形式的表達(dá)上一定要吻合，否則很容易創(chuàng)建出不符合要求的樹。 選作內(nèi)容選作內(nèi)容 采用非遞歸算法實(shí)現(xiàn)二叉樹遍歷。9.2.29.2.2 打印二叉樹結(jié)構(gòu)打印二叉樹結(jié)構(gòu) 問題描述問題描述 按凹入表形式橫向打印二叉樹結(jié)構(gòu)，即二叉樹的根在屏幕的最左邊，二叉樹的左子樹在屏幕的下邊，二叉樹的右子樹在屏幕的上邊。例如：圖 9.1 一個(gè)圖 測試數(shù)據(jù)測試數(shù)據(jù)

57、 由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)，如空二叉樹。 實(shí)現(xiàn)提示實(shí)現(xiàn)提示 （1）利用 RDL 遍歷方法；（2）利用結(jié)點(diǎn)的深度控制橫向位置。實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)項(xiàng)目 1010圖遍歷演示圖遍歷演示10.110.1 實(shí)驗(yàn)?zāi)康膶?shí)驗(yàn)?zāi)康模?）掌握圖的鄰接矩陣、鄰接表、十字鏈表等不同存儲(chǔ)形式的表示方法。（2）掌握圖的兩種不同遍歷方法的基本思想并能編程實(shí)現(xiàn)。（3）掌握構(gòu)造最小生成樹的兩種算法，即 Prim 算法和 Kruscal 算法的思想，并能編程實(shí)現(xiàn)。（4）能夠靈活運(yùn)用圖的相關(guān)算法解決相應(yīng)的實(shí)際問題。10.210.2 實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)內(nèi)容 問題描述問題描述 很多涉及圖上操作的算法都以圖的遍歷操作為基

58、礎(chǔ)。試寫一個(gè)程序，演示在連通的無向圖上訪問全部結(jié)點(diǎn)的操作。 基本要求基本要求 以鄰接多重表為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)連通無向圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷。以用戶指定的結(jié)點(diǎn)為起點(diǎn)，分別輸出每種遍歷下結(jié)點(diǎn)訪問序列和相應(yīng)生成樹的邊集。 算法描述算法描述 從已給的連通圖中某一頂點(diǎn)出發(fā)，沿著一些邊訪遍圖中所有的頂點(diǎn)，且使每個(gè)頂點(diǎn)僅被訪問一次，就叫做圖的遍歷 ( Graph Traversal )。圖中可能存在回路，且圖的任一頂點(diǎn)都可能與其它頂點(diǎn)相通，在訪問完某個(gè)頂點(diǎn)之后可能會(huì)沿著某些邊又回到了曾經(jīng)訪問過的頂點(diǎn)。為了避免重復(fù)訪問，可設(shè)置一個(gè)標(biāo)志頂點(diǎn)是否被訪問過的輔助數(shù)組 visited ，它的初始狀態(tài)為 0，在圖

59、的遍歷過程中，一旦某一個(gè)頂點(diǎn) i 被訪問，就立即讓 visited i 為 1，防止它被多次訪問。DFS 在訪問圖中某一起始頂點(diǎn) v 后，由 v 出發(fā)，訪問它的任一鄰接頂點(diǎn) w1；再從 w1 出發(fā)，訪問與 w1 鄰 接但還沒有訪問過的頂點(diǎn) w2；然后再從 w2 出發(fā)，進(jìn)行類似的訪問， 如此進(jìn)行下去，直至到達(dá)所有的鄰接頂點(diǎn)都被訪問過的頂點(diǎn) u 為止。接著，退回一步，退到前一次剛訪問過的頂點(diǎn)，看是否還有其它沒有被訪問的鄰接頂點(diǎn)。如果有，則訪問此頂點(diǎn)，之后再從此頂點(diǎn)出發(fā)，進(jìn)行與前述類似的訪問；如果沒有，就再退回一步進(jìn)行搜索。重復(fù)上述過程，直到連通圖中所有頂點(diǎn)都被訪問過為止。圖的深度優(yōu)先搜索算法描述如

60、下：void Graph:DFS ( ) visited = new int n; /創(chuàng)建數(shù)組 visited for ( int i = 0; i n; i+ ) visited i = 0; /訪問標(biāo)記數(shù)組 visited 初始化 for(int i=0; in;i+)if(visitedi=0) DFS(i,visited); delete visited; /釋放 visited viod Graph:DFS ( const int v, int visited ) cout GetValue (v) ; /訪問頂點(diǎn) v visitedv = 1; /頂點(diǎn) v 作訪問標(biāo)記 int w = GetFirstNeighbor (v); /取 v 的第一個(gè)鄰接頂點(diǎn) w while ( w != -1 ) /若鄰接頂點(diǎn) w 存在 if ( !visitedw ) DFS ( w, visited ); /