算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)手冊

1、算法與數(shù)據(jù)結(jié)構(gòu)實(shí) 驗(yàn) 指 導(dǎo) 手 冊算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)手冊（2015年9月）1 實(shí)驗(yàn)一1、 實(shí)驗(yàn)名稱及學(xué)時(shí)數(shù) 線性表 2學(xué)時(shí)2、 實(shí)驗(yàn)?zāi)康谋敬螌?shí)驗(yàn)的主要目的在于熟悉線性表的基本運(yùn)算在兩種存儲結(jié)構(gòu)上的實(shí)現(xiàn)，其中以熟悉各種鏈表的操作為側(cè)重點(diǎn)。同時(shí)，通過本次實(shí)驗(yàn)幫助學(xué)生復(fù)習(xí)高級語言的使用方法。3、 實(shí)驗(yàn)內(nèi)容必做內(nèi)容1） 城市鏈表問題描述將若干城市的信息，存入一個(gè)帶頭結(jié)點(diǎn)的單鏈表。結(jié)點(diǎn)中的城市信息包括：城市名，城市的位置坐標(biāo)。要求能夠利用城市名和位置坐標(biāo)進(jìn)行有關(guān)查找、插入、刪除、更新等操作?；疽螅?） 給定一個(gè)城市名，返回其位置坐標(biāo)；（2） 給定一個(gè)位置坐標(biāo)P和一個(gè)距離D，返回所有與P的距離小

2、于等于D的城市。測試數(shù)據(jù)由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)。2） 約瑟夫環(huán)問題描述約瑟夫（Joeph）問題的一種描述是：編號為1,2,n的n個(gè)人按順時(shí)針方向圍坐一圈，每人持有一個(gè)密碼（正整數(shù)）。一開始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m，從第一個(gè)人開始按順時(shí)針方向自1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針方向上的下一個(gè)人開始重新從1報(bào)數(shù)，如此下去，直至所有人全部出列為止。試設(shè)計(jì)一個(gè)程序求出出列順序?；疽罄脝蜗蜓h(huán)鏈表存儲結(jié)構(gòu)模擬此過程，按照出列的順序印出各人的編號。測試數(shù)據(jù)m的初值為20；密碼：3，1，7，2，4，8，4（正確的結(jié)

3、果應(yīng)為6，1，4，7，2，3，5）。實(shí)現(xiàn)提示程序運(yùn)行后首先要求用戶指定初始報(bào)數(shù)上限值，然后讀取各人的密碼。設(shè)n30。選做內(nèi)容1） 向上述程序中添加在順序結(jié)構(gòu)上實(shí)現(xiàn)的部分。4、 實(shí)驗(yàn)環(huán)境VC6.05、 實(shí)驗(yàn)要求1） 編程實(shí)現(xiàn)必做實(shí)驗(yàn)內(nèi)容1）、2）。2） 學(xué)生可根據(jù)自己的能力完成選做實(shí)驗(yàn)。3） 填寫實(shí)驗(yàn)報(bào)告（見附件）。6、 實(shí)驗(yàn)步驟2 實(shí)驗(yàn)二1、 實(shí)驗(yàn)名稱及學(xué)時(shí)數(shù) 棧、隊(duì)列與遞歸算法設(shè)計(jì) 2學(xué)時(shí)2、 實(shí)驗(yàn)?zāi)康膬H僅認(rèn)識到棧和隊(duì)列是兩種特殊的線性表是遠(yuǎn)遠(yuǎn)不夠的，本次實(shí)驗(yàn)的目的在于使學(xué)生深入了解棧和隊(duì)列的特征，以便在實(shí)際問題背景下靈活運(yùn)用它們；同時(shí)還將鞏固這兩種結(jié)構(gòu)的構(gòu)造方法，接觸較復(fù)雜問題的遞歸算法設(shè)

4、計(jì)。3、 實(shí)驗(yàn)內(nèi)容必做內(nèi)容1） 數(shù)制轉(zhuǎn)換問題問題描述將十進(jìn)制數(shù)N和其它d進(jìn)制數(shù)的轉(zhuǎn)換是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的基本問題，其解決方案很多，其中最簡單方法基于下列原理：即除d取余法。例如：（1348）10=（2504）8NN div 8N mod 8134816841682102125202從表中我們可以看出，最先產(chǎn)生的余數(shù)4是轉(zhuǎn)換結(jié)果的最低位，這正好符合棧的特性即后進(jìn)先出的特性。所以可以用順序棧來模擬這個(gè)過程。基本要求對于鍵盤輸入的任意一個(gè)非負(fù)的十進(jìn)制整數(shù)，打印輸出與其等值的八進(jìn)制數(shù)。由于上述的計(jì)算過程是從低位到高位順序產(chǎn)生的八進(jìn)制數(shù)的各個(gè)數(shù)位，而打印輸出，一般來說應(yīng)從高位到低位進(jìn)行，恰好和計(jì)算過程相反

5、。因此可以先將計(jì)算過程中得到的八進(jìn)制數(shù)的各位進(jìn)棧，待相對應(yīng)的八進(jìn)制數(shù)的各位均產(chǎn)生以后，再使其按順序出棧，并打印輸出。即得到了與輸入的十進(jìn)制數(shù)相對應(yīng)的八進(jìn)制數(shù)。測試數(shù)據(jù)由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)。2） 括號匹配的檢驗(yàn)問題描述假設(shè)表達(dá)式中允許有兩種括號：圓括號和方括號，其嵌套的順序隨意，即（） ）或（ ）等為正確格式，（ ）或（均為不正確的格式。檢驗(yàn)括號是否匹配的方法可用“期待的緊迫程度”這個(gè)概念來描述。例如：考慮下列的括號序列：()12345678當(dāng)計(jì)算機(jī)接受了第1個(gè)括號以后，它期待著與其匹配的第8個(gè)括號的出現(xiàn)，然而等來的卻是第2個(gè)括號，此時(shí)第1個(gè)括號“”只能暫時(shí)靠邊

6、，而迫切等待與第2個(gè)括號相匹配的第7個(gè)括號“）”的出現(xiàn)，類似的，因只等來了第3個(gè)括號“”，此時(shí)，其期待的緊迫程度較第2個(gè)括號更緊迫，則第2個(gè)括號只能靠邊，讓位于第3個(gè)括號，顯然第3個(gè)括號的期待緊迫程度高于第2個(gè)括號，而第2個(gè)括號的期待緊迫程度高于第1個(gè)括號；在接受了第4個(gè)括號之后，第3個(gè)括號的期待得到了滿足，消解之后，第2個(gè)括號的期待匹配就成了最急迫的任務(wù)了， ，依次類推。可見這個(gè)處理過程正好和棧的特點(diǎn)相吻合。基本要求讀入圓括號和方括號的任意序列，輸出“匹配”或“此串括號匹配不合法”。測試數(shù)據(jù) 輸入（ （），結(jié)果“匹配”輸入 （ ），結(jié)果“此串括號匹配不合法”實(shí)現(xiàn)提示設(shè)置一個(gè)棧，每讀入一個(gè)括號

7、，若是左括號，則作為一個(gè)新的更急迫的期待壓入棧中；若是右括號，并且與當(dāng)前棧頂?shù)淖罄ㄌ栂嗥ヅ洌瑒t將當(dāng)前棧頂?shù)淖罄ㄌ柾顺?，繼續(xù)讀下一個(gè)括號，如果讀入的右括號與當(dāng)前棧頂?shù)淖罄ㄌ柌黄ヅ?，則屬于不合法的情況。在初始和結(jié)束時(shí)，棧應(yīng)該是空的。選作內(nèi)容 1） 停車場管理問題描述設(shè)停車場內(nèi)只有一個(gè)可停放n輛汽車的狹長通道，且只有一個(gè)大門可供汽車進(jìn)出。汽車在停車場內(nèi)按車輛到達(dá)時(shí)間的先后順序，依次由北向南排列（大門在最南端，最先到達(dá)的第一輛車停放在車場的最北端），若車場內(nèi)已停滿n輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當(dāng)停車場內(nèi)某輛車要離開時(shí)，在它之后開入的車輛必須

8、先退出車場為它讓路，待該輛車開出大門外，其它車輛再按原次序進(jìn)入車場，每輛停放在車場的車在它離開停車場時(shí)必須按它停留的時(shí)間長短交納費(fèi)用。試為停車場編制按上述要求進(jìn)行管理的模擬程序。測試數(shù)據(jù)設(shè)n=2，輸入數(shù)據(jù)為：（A，1，5），（A，2，10），（D，1，15），（A，3， 20）， （A，4，25），（A，5，30），（D，2，35），（D，4，40），（E，0，0）。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“離去”信息、汽車牌照號碼及到達(dá)或離去的時(shí)刻，其中，A表示到達(dá)；D表示離去，E表示輸入結(jié)束?；疽笠詶ＤM停車場，以隊(duì)列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理。每一

9、組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“離去”信息、汽車牌照號碼及到達(dá)或離去的時(shí)刻，對每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出數(shù)據(jù)為：若是車輛到達(dá)，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車離去；則輸出汽車在停車場內(nèi)停留的時(shí)間和應(yīng)交納的費(fèi)用（在便道上停留的時(shí)間不收費(fèi)）。棧以順序結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表實(shí)現(xiàn)。實(shí)現(xiàn)提示需另設(shè)一個(gè)棧，臨時(shí)停放為給要離去的汽車讓路而從停車場退出來的汽車，也用順序存儲結(jié)構(gòu)實(shí)現(xiàn)。輸入數(shù)據(jù)按到達(dá)或離去的時(shí)刻有序。棧中每個(gè)元素表示一輛汽車，包含兩個(gè)數(shù)據(jù)項(xiàng)：汽車的牌照號碼和進(jìn)入停車場的時(shí)刻。思考（1） 兩個(gè)棧共享空間，思考應(yīng)開辟數(shù)組的空間是多少？（2） 汽車可有不同種類，則它們的占地面

10、積不同，收費(fèi)標(biāo)準(zhǔn)也不同，如1輛客車和1.5輛小汽車的占地面積相同，1輛十輪卡車占地面積相當(dāng)于3輛小汽車的占地面積。（3） 汽車可以直接從便道上開走，此時(shí)排在它前面的汽車要先開走讓路，然后再依次排到隊(duì)尾。（4） 停放在便道上的汽車也收費(fèi)，收費(fèi)標(biāo)準(zhǔn)比停放在停車場的車低，請思考如何修改結(jié)構(gòu)以滿足這種要求。4、 實(shí)驗(yàn)環(huán)境VC6.05、 實(shí)驗(yàn)要求1） 編程實(shí)現(xiàn)必做實(shí)驗(yàn)內(nèi)容1）、2）。2） 學(xué)生可根據(jù)自己的能力選做實(shí)驗(yàn)內(nèi)容。3） 填寫實(shí)驗(yàn)報(bào)告（見附件）。6、 實(shí)驗(yàn)步驟3 實(shí)驗(yàn)三1、 實(shí)驗(yàn)名稱及學(xué)時(shí)數(shù) 字符串的模式匹配 2學(xué)時(shí)2、 實(shí)驗(yàn)?zāi)康谋敬螌?shí)驗(yàn)的目的是熟悉串類型的實(shí)現(xiàn)方法和文本模式匹配方法，熟悉串的鍵盤

11、輸入獲取方式。3、 實(shí)驗(yàn)內(nèi)容必做內(nèi)容問題描述 設(shè)有兩個(gè)字符串s和t，首先將s1與t1進(jìn)行比較，直到s的某一個(gè)字符si和ti相同，再將它們之后的字符進(jìn)行比較，若也相同，則如此繼續(xù)往下比較，當(dāng)s的某一個(gè)字符si與t的字符tj不同時(shí)，則s返回到本趟開始字符的下一個(gè)字符，即si-j+2，t返回到t1，繼續(xù)開始下一趟的比較，重復(fù)上述過程。若t中的字符全部比較完，則說明本趟匹配成功，本趟的起始位置是i-j+1，否則，匹配失敗?；疽蟊緦?shí)驗(yàn)要求學(xué)生掌握串的特點(diǎn)及順序定長存儲的方式，掌握模式匹配的基本思想及其算法。由用戶通過鍵盤輸入建立一個(gè)主字符串和搜索串，如果主串中包含要搜索的子串，返回子串在主串中的起始

12、位置，否則返回搜索失敗。測試數(shù)據(jù)由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)。4、 實(shí)驗(yàn)環(huán)境VC6.05、 實(shí)驗(yàn)要求1） 編程實(shí)現(xiàn)必做實(shí)驗(yàn)內(nèi)容。2） 填寫實(shí)驗(yàn)報(bào)告（見附件）。6、 實(shí)驗(yàn)步驟4 實(shí)驗(yàn)四1、 實(shí)驗(yàn)名稱及學(xué)時(shí)數(shù) 樹及其應(yīng)用 2學(xué)時(shí)2、 實(shí)驗(yàn)?zāi)康臉涫且环N應(yīng)用極為廣泛的數(shù)據(jù)結(jié)構(gòu)，也是這門課程的重點(diǎn)。它們的特點(diǎn)在于非線性。廣義表本質(zhì)上是樹結(jié)構(gòu)。本章實(shí)驗(yàn)繼續(xù)突出了數(shù)據(jù)結(jié)構(gòu)加操作的程序設(shè)計(jì)觀點(diǎn)，但根據(jù)這兩種結(jié)構(gòu)的非線性特點(diǎn)，將操作進(jìn)一步集中在遍歷操作上，因?yàn)楸闅v操作是其他眾多操作的基礎(chǔ)。遍歷邏輯的（或符號形式的）結(jié)構(gòu)，訪問動作可是任何操作。本次實(shí)驗(yàn)希望幫助學(xué)生熟悉各種存儲結(jié)構(gòu)的特征，

13、以及如何應(yīng)用樹結(jié)構(gòu)解決具體問題（即原理與應(yīng)用的結(jié)合）。3、 實(shí)驗(yàn)內(nèi)容必做內(nèi)容1） 二叉樹的建立與遍歷問題描述建立一棵二叉樹，并對其進(jìn)行遍歷（先序、中序、后序），打印輸出遍歷結(jié)果?；疽?從鍵盤接受輸入（先序），以二叉鏈表作為存儲結(jié)構(gòu)，建立二叉樹（以先序來建立），并采用遞歸算法對其進(jìn)行遍歷（先序、中序、后序），將遍歷結(jié)果打印輸出。測試數(shù)據(jù)ABCDEGF（其中表示空格字符）則輸出結(jié)果為 先序：ABCDEGF中序：CBEGDFA后序：CGBFDBA2） 打印二叉樹結(jié)構(gòu)問題描述按凹入表形式橫向打印二叉樹結(jié)構(gòu)，即二叉樹的根在屏幕的最左邊，二叉樹的左子樹在屏幕的下邊，二叉樹的右子樹在屏幕的上邊。例如：

14、測試數(shù)據(jù)由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)，如空二叉樹。實(shí)現(xiàn)提示（1）利用RDL遍歷方法；（2）利用結(jié)點(diǎn)的深度控制橫向位置。選做內(nèi)容采用非遞歸算法實(shí)現(xiàn)二叉樹遍歷。4、 實(shí)驗(yàn)環(huán)境VC6.05、 實(shí)驗(yàn)要求1） 編程實(shí)現(xiàn)必做實(shí)驗(yàn)內(nèi)容1）、2）。2） 學(xué)生可根據(jù)自己的能力完成選做內(nèi)容。3） 填寫實(shí)驗(yàn)報(bào)告（見附件）。6、 實(shí)驗(yàn)步驟5 實(shí)驗(yàn)五1、 實(shí)驗(yàn)名稱及學(xué)時(shí)數(shù) 圖及其應(yīng)用 2學(xué)時(shí)2、 實(shí)驗(yàn)?zāi)康臉浜蛨D是兩種應(yīng)用極為廣泛的數(shù)據(jù)結(jié)構(gòu)，也是這門課程的重點(diǎn)。它們的特點(diǎn)在于非線性。 稀疏矩陣的十字鏈表存儲結(jié)構(gòu)也是圖的一種存儲結(jié)構(gòu)。本章實(shí)驗(yàn)繼續(xù)突出了數(shù)據(jù)結(jié)構(gòu)加操作的程序設(shè)計(jì)觀點(diǎn)，但根據(jù)這種結(jié)構(gòu)的

15、非線性特點(diǎn)，將操作進(jìn)一步集中在遍歷操作上，因?yàn)楸闅v操作是其它眾多操作的基礎(chǔ)。遍歷邏輯的（或符號形式的）結(jié)構(gòu)，訪問動作可是任何操作。本次實(shí)驗(yàn)希望幫助學(xué)生熟悉各種存儲結(jié)構(gòu)的特征，以及如何應(yīng)用圖結(jié)構(gòu)解決具體問題（即原理與應(yīng)用的結(jié)合）。3、 實(shí)驗(yàn)內(nèi)容必做內(nèi)容1） 圖遍歷的演示問題描述很多涉及圖上操作的算法都是以圖的遍歷操作為基礎(chǔ)的。試寫一個(gè)程序，演示無向圖的遍歷操作?；疽笠脏徑颖頌榇鎯Y(jié)構(gòu)，實(shí)現(xiàn)連通無向圖的深度優(yōu)先和廣度優(yōu)先遍歷。以用戶指定的結(jié)點(diǎn)為起點(diǎn)，分別輸出每種遍歷下的結(jié)點(diǎn)訪問序列和相應(yīng)生成樹的邊集。測試數(shù)據(jù)由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)，如單個(gè)結(jié)點(diǎn)。實(shí)現(xiàn)提示設(shè)圖的結(jié)點(diǎn)

16、不超過30個(gè)，每個(gè)結(jié)點(diǎn)用一個(gè)編號表示（如果一個(gè)圖有n個(gè)結(jié)點(diǎn)，則它們的編號分別為1,2,n）。通過輸入圖的全部邊輸入一個(gè)圖，每條邊為一個(gè)數(shù)對，可以對邊的輸入順序做出某種限制。注意，生成樹的邊是有向邊，端點(diǎn)順序不能顛倒。選做內(nèi)容1） 借助于棧類型（自己定義和實(shí)現(xiàn)）將深度優(yōu)先遍歷用非遞歸算法實(shí)現(xiàn)。2） 以鄰接多重表為存儲結(jié)構(gòu)建立深度優(yōu)先生成樹和廣度優(yōu)先生成樹，再按凹入表或樹形打印生成樹。3） 實(shí)現(xiàn)有向圖的遍歷操作。4、 實(shí)驗(yàn)環(huán)境VC6.05、 實(shí)驗(yàn)要求1） 編程實(shí)現(xiàn)必做實(shí)驗(yàn)內(nèi)容1）。2） 學(xué)生可根據(jù)自己的能力完成選做內(nèi)容。3） 填寫實(shí)驗(yàn)報(bào)告（見附件）。6、 實(shí)驗(yàn)步驟6 實(shí)驗(yàn)六1、 實(shí)驗(yàn)名稱及學(xué)時(shí)數(shù)

17、查找 2學(xué)時(shí)2、 實(shí)驗(yàn)?zāi)康谋敬螌?shí)驗(yàn)旨在集中對幾個(gè)專門的問題作較為深入的探討和理解，不強(qiáng)調(diào)對某些特定的編程技術(shù)的訓(xùn)練。3、 實(shí)驗(yàn)內(nèi)容必做內(nèi)容1） 二叉排序樹問題描述從鍵盤讀入一組數(shù)據(jù)，建立二叉排序樹并對其進(jìn)行查找、遍歷、格式化打印等有關(guān)操作?；疽蠼⒍媾判驑洳ζ溥M(jìn)行查找，包括成功和不成功兩種情況，并給出查找長度。測試數(shù)據(jù)由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)。2） 哈希表設(shè)計(jì)問題描述針對某個(gè)集體中人名設(shè)計(jì)一個(gè)哈希表，使得平均查找長度不超過R，并完成相應(yīng)的建表和查表程序。基本要求假設(shè)人名為中國人姓名的漢語拼音形式。待填入哈希表的人名共有30個(gè)，取平均查找長度的上限為2。哈希

18、函數(shù)用除留余數(shù)法構(gòu)造，用線性探測再散列法或鏈地址法處理沖突。測試數(shù)據(jù)取你周圍較熟悉的30個(gè)人名。選做內(nèi)容1） 實(shí)現(xiàn)二叉排序樹的插入、刪除操作。2） 從教科書上介紹的集中哈希函數(shù)構(gòu)造方法中選出適用者并設(shè)計(jì)幾個(gè)不同的哈希函數(shù)，比較他們的地址沖突率（可以用更大的名字集合作實(shí)驗(yàn)）。3） 研究必做實(shí)驗(yàn)2）的30個(gè)人名的特點(diǎn)，努力找一個(gè)哈希函數(shù)，使得對于不同的拼音名一定不發(fā)生地址沖突。4） 在哈希函數(shù)確定的前提下嘗試各種不同處理沖突的方法，考察平均查找長度的變化和造好的哈希表中關(guān)鍵字的聚集性。4、 實(shí)驗(yàn)環(huán)境VC6.05、 實(shí)驗(yàn)要求1） 編程實(shí)現(xiàn)必做實(shí)驗(yàn)內(nèi)容1）、2）。2） 學(xué)生可根據(jù)自己的能力完成選做內(nèi)容。3） 填寫實(shí)驗(yàn)報(bào)告（見附件）。6、 實(shí)驗(yàn)步驟7 實(shí)驗(yàn)七1、 實(shí)驗(yàn)名稱及學(xué)時(shí)數(shù) 排序 2學(xué)時(shí)2、 實(shí)驗(yàn)?zāi)康谋敬螌?shí)驗(yàn)旨在集中對幾個(gè)專門的問題作較為深入的探討和理解，不強(qiáng)調(diào)對某些特定的編程技術(shù)的訓(xùn)練。3、 實(shí)驗(yàn)內(nèi)容必做內(nèi)容1） 內(nèi)部排序算法比較問題描述各種內(nèi)部排序算法的時(shí)間復(fù)雜度分析結(jié)果只給出了算法執(zhí)行時(shí)間的階，或大概執(zhí)行時(shí)間。試通過隨機(jī)的數(shù)據(jù)比較各算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動次數(shù)，以取得直觀感受。基本要求（1） 對以下9種常用的內(nèi)部排序算法進(jìn)行比較：直接插入排序；折半折入排序；二路插入排序；希爾排序；起泡排序；快