數(shù)據(jù)結(jié)構(gòu)試驗指導書V2.0

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

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

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

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

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

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

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

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

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

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

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

12、.21.2 實驗內(nèi)容實驗內(nèi)容 問題描述問題描述 設(shè)計實現(xiàn)抽象數(shù)據(jù)類型“三元組” 。每個三元組由任意三個實數(shù)的序列構(gòu)成，基本操作包括：創(chuàng)建一個三元組，取三元組的任意一個分量，置三元組的任意一個分量，求三元組的最大分量，求三元組的最小分量，兩個三元組的對應(yīng)分量相加或相減，給三元組的各分量同乘一個比例因子，顯示三元組，銷毀三元組等。 基本要求基本要求 實現(xiàn)創(chuàng)建一個三元組，取三元組的任意一個分量，置三元組的任意一個分量，求三元組的最大分量，求三元組的最小分量，顯示三元組等基本操作。 算法描述算法描述 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 個分量 Bool put(i,e) 初始條件：三元組已經(jīng)存在，1i3；操作結(jié)果：將三元組的第 i 個分量賦值為 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ù) 由學生任意指定。 選作內(nèi)容選作內(nèi)容 實現(xiàn)兩個三元組的對應(yīng)分量相加或相減，給三元組的各分量同乘一個比例因子，銷毀三元組等操作。實驗項目實驗項目 2 2復數(shù)四則運算復數(shù)四則運算2.12.1 實驗目的實驗目的本次實驗與實驗項目 1 為同一類型實驗，主要目的是在于幫助讀者進一步熟悉抽象數(shù)據(jù)類型的表示和實現(xiàn)方法。抽象數(shù)據(jù)類型需要借助固有數(shù)據(jù)類型來表示和實現(xiàn)，即利用高級程序設(shè)計語言中已經(jīng)存在的數(shù)據(jù)類型來說明新的結(jié)構(gòu)，用已經(jīng)實現(xiàn)的操作來組合新的操作，具體實現(xiàn)細節(jié)依賴于所用語言的功能。2.22.2 實驗內(nèi)容實驗內(nèi)容 問題描述問題描述 設(shè)計

15、實現(xiàn)一個可進行復數(shù)運算的演示程序。 基本要求基本要求 實現(xiàn)下列六種基本運算：1） 由輸入的實部和虛部生成一個復數(shù)；2） 兩個復數(shù)求和；3） 兩個復數(shù)求差；4） 兩個復數(shù)求積；5） 從已知復數(shù)中分離出實部；6） 從已知復數(shù)中分離出虛部；運算結(jié)果以相應(yīng)的復數(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)存在兩個復數(shù)；操作結(jié)果：將兩個復數(shù)的實部和虛部分別進行向加得到一個新的復數(shù)Complex operate-(const complex &)初始條件：已經(jīng)存在兩個復數(shù)；操作結(jié)果：將兩個復數(shù)的實部和虛部分別進行向減得到一個新的復數(shù)Complex operate*(const complex &)初始條件：已經(jīng)存在兩個復數(shù)；操作結(jié)果：按照復數(shù)乘法規(guī)則將兩個復數(shù)的實部相乘結(jié)果減去兩個復數(shù)虛部相乘結(jié)果為新生成復數(shù)的實部；將兩個復數(shù)的虛部和實部交叉相乘再相加的結(jié)果作為新生成復數(shù)的虛部。 Elem reality() 初

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

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

19、一進行具體實現(xiàn)。 算法描述算法描述 1 順序存儲方式templet class AList：public Listprivate: int maxSize; int listSize; int fence; Elem* listArray;public:/線性表創(chuàng)建操作實現(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) /線性表中插入操作實現(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ù)操作實現(xiàn)templet bool AList: append(const Elem&item) if(listSize=maxSize)return false; listArraylistSize+=item; return true; /線性表中刪除操作實現(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; /線性表中查找操作實現(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 鏈式存儲方式template class LList:public List private: Link*head; Link*tail; Link*fence; int leftcnt, rightcnt;/基本線性表的創(chuàng)建操作實現(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;/基本線性表插入操作的實現(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ù)操作的實現(xiàn)template bool LList:append(const Elem&item) tail=tail-next=new Link(item,null); rightcnt+; return true;

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

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

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

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

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

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

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

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

37、將計算過程中得到的八進制數(shù)的各位進棧，待相對應(yīng)的八進制數(shù)的各位均產(chǎn)生以后，再使其按順序出棧，并打印輸出。即得到了與輸入的十進制數(shù)相對應(yīng)的八進制數(shù)。 算法描述算法描述 算法思想如下：當 N0 時重復 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ù) 由學生依據(jù)軟件工程

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

39、&則不是。 基本要求基本要求 對于鍵盤輸入的任意一個字符串，將其進行逆置，判斷原串和逆置的串是否完全一致，完全一致則為回文，因此分別利用隊列的先進先出（FIFO）和棧的后進先出（FILO）實現(xiàn)，算法只能使用一個棧和一個隊列以及若干簡單類型變量，算法時間復雜度應(yīng)為 O(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ù) 由學生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)，如序列 1 和序列 2 均為空串。 實現(xiàn)提示實現(xiàn)提示 利用隊列的先進先出（FIFO）和棧的后進先出（LIFO）特點，將字符串中字符分別進行入棧和入隊操作，字符串輸入結(jié)束后將隊列和棧中字符依次取出，判斷取出的一對字

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

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

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

44、權(quán)高于 2，可以運算算法簡單描述如下：設(shè)置兩個棧，分別存放操作數(shù)和運算符；輸入操作數(shù)時，一定不會運算；運算過程實際就是運算符號比較的過程OpendType EvaluateExpression( ) /表達式求值Stack OPTR;OPTR.Push( # );Stack OPND;c = getchar( );while( !(c = # & GetTop( OPTR ) = #) )if( ! In( c, OP )/ c 是運算符？,OP 是運算符集合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） ） ） 實現(xiàn)提示實現(xiàn)提示 （1）設(shè)置運算符棧和運算數(shù)棧輔助分析

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

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

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

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

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

51、 8 個點的坐標都可根據(jù)與該點的相鄰方位而得到，如圖 8.2 所示。因為出口在（m，n） ，因此試探順序規(guī)定為：從當前位置向前試探的方向為從正東沿順時針方向進行。為了簡化問題，方便的求出新點的坐標，將從正東開始沿順時針進行的這 8 個方向的坐標增量放在一個結(jié)構(gòu)數(shù)組 move 8 中，在 move 數(shù)組中，每個元素有兩個域組成，x：橫坐標增量，y：縱坐標增量。move 數(shù)組如圖 8.3 所示。Move 數(shù)組定義如下：typedef struct int x，y item ; item move8 ;這樣對 move 的設(shè)計會很方便地求出從某點 (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出棧 ;求出下一個要試探的方向 d+ ; while （還有剩余試探方向時） if （d 方向可走）則 （x , y , d）入棧 ; 求新點坐標 (i, j ) ;將新點（i , j）切換為當前點（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) 用前序、中序兩種不同的方法進行遍歷。這兩種遍歷可分別用遞歸方式和非遞歸方式實現(xiàn)，其遞歸方式相當簡捷。在此只給出中序遍歷的非遞歸算法：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é)點的左、右子樹。 交換過程中，同樣需要借助一個指針棧來實現(xiàn)。最先交換二叉樹中樹根結(jié)點的左、右子樹，然后再在其左、右子樹中分別遞歸調(diào)用該函數(shù)，直到所有的結(jié)點的左、右子樹都完成交換為止。 （4）用前序、中序兩種不同的方法進行遍歷交換左、右子樹之后的二叉樹，其實現(xiàn)過程同（2） 。 測試數(shù)據(jù)測試數(shù)據(jù) ABCDEGF（其

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

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

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

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

60、下：void Graph:DFS ( ) visited = new int n; /創(chuàng)建數(shù)組 visited for ( int i = 0; i n; i+ ) visited i = 0; /訪問標記數(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) ; /訪問頂點 v visitedv = 1; /頂點 v 作訪問標記 int w = GetFirstNeighbor (v); /取 v 的第一個鄰接頂點 w while ( w != -1 ) /若鄰接頂點 w 存在 if ( !visitedw ) DFS ( w, visited ); /