計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)手冊(cè)

1、計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)數(shù) 據(jù) 結(jié) 構(gòu)上 機(jī) 實(shí) 驗(yàn) 手 冊(cè)臺(tái)州學(xué)院數(shù)學(xué)與信息工程學(xué)院計(jì) 算 機(jī) 科 學(xué) 系前 言上機(jī)實(shí)踐是學(xué)生對(duì)所學(xué)知識(shí)的一種全面、綜合的能力訓(xùn)練，是與課堂聽(tīng)講、自學(xué)和練習(xí)相輔相成的必不可少的一個(gè)教學(xué)環(huán)節(jié)，也是對(duì)課堂教學(xué)與實(shí)踐教學(xué)效果的一種檢驗(yàn)。通常，實(shí)驗(yàn)中的問(wèn)題比理論課的習(xí)題復(fù)雜得多，也更接近實(shí)際。實(shí)驗(yàn)課的內(nèi)容一般著眼于原理與應(yīng)用的結(jié)合，使學(xué)生學(xué)會(huì)如何把書(shū)上學(xué)到的知識(shí)運(yùn)用于解決實(shí)際問(wèn)題的過(guò)程中去，培養(yǎng)從事軟件開(kāi)發(fā)設(shè)計(jì)工作所必需的基本技能。另一方面，能使書(shū)上的知識(shí)變活，起到深化理解和靈活掌握教學(xué)內(nèi)容的目的。理論課習(xí)題較偏重于如何編寫(xiě)功能單一的“小”算法，而實(shí)驗(yàn)是軟件設(shè)計(jì)的綜合訓(xùn)練

2、，包括問(wèn)題分析、總體結(jié)構(gòu)設(shè)計(jì)、用戶(hù)界面設(shè)計(jì)、程序設(shè)計(jì)基本技能、多人合作，以至一整套軟件工程規(guī)范的訓(xùn)練和科學(xué)作風(fēng)的培養(yǎng)。此外，還有很重要的一點(diǎn)是：機(jī)器是比任何教師都嚴(yán)格的把關(guān)者。為了達(dá)到上述目的，本實(shí)驗(yàn)課程安排了9個(gè)獨(dú)立的實(shí)驗(yàn)單元，各單元的訓(xùn)練重點(diǎn)在于基本數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)及其應(yīng)用。各實(shí)驗(yàn)單元與理論教學(xué)的各章具有緊密的聯(lián)系，每個(gè)實(shí)驗(yàn)單元安排有難度不等的多個(gè)實(shí)驗(yàn)題，包括必做實(shí)驗(yàn)內(nèi)容和選作實(shí)驗(yàn)內(nèi)容，以便學(xué)生根據(jù)自己的實(shí)際情況選做部分實(shí)驗(yàn)內(nèi)容。每次上機(jī)實(shí)驗(yàn)前，要求同學(xué)們做好充分的準(zhǔn)備，包括實(shí)驗(yàn)的目的要求、程序清單、測(cè)試數(shù)據(jù)和預(yù)計(jì)運(yùn)算結(jié)果等，實(shí)驗(yàn)后寫(xiě)出完整的實(shí)驗(yàn)報(bào)告。每份實(shí)驗(yàn)報(bào)告包括三部分內(nèi)容：實(shí)驗(yàn)?zāi)康暮鸵?/p>

3、求、實(shí)驗(yàn)內(nèi)容及實(shí)驗(yàn)小結(jié)。 實(shí)驗(yàn)報(bào)告書(shū)寫(xiě)規(guī)范實(shí)驗(yàn)報(bào)告包括三部分： 實(shí)驗(yàn)?zāi)康呐c要求 實(shí)驗(yàn)內(nèi)容 實(shí)驗(yàn)小結(jié)其中，實(shí)驗(yàn)內(nèi)容包括： 實(shí)驗(yàn)題目 問(wèn)題分析 程序清單 測(cè)試數(shù)據(jù) 調(diào)試分析 運(yùn)行結(jié)果實(shí)驗(yàn)一 線性表及其應(yīng)用一、實(shí)驗(yàn)?zāi)康呐c要求鞏固對(duì)線性表邏輯結(jié)構(gòu)的理解，熟練掌握線性表的兩種存儲(chǔ)結(jié)構(gòu)及線性表的基本操作在兩種存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)，掌握以線性表作為數(shù)據(jù)結(jié)構(gòu)解決實(shí)際問(wèn)題的方法。二、實(shí)驗(yàn)內(nèi)容（一）順序表操作驗(yàn)證1問(wèn)題描述 對(duì)以順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表，驗(yàn)證其插入、刪除、查找、就地逆置等操作。2基本要求用菜單實(shí)現(xiàn)操作選擇。3測(cè)試數(shù)據(jù)自擬。（二）順序表歸并（選作）1問(wèn)題描述 已知兩順序表sa、sb，其元素均為遞增有序，

4、將此兩表歸并成一個(gè)新的順序表sc，并保持遞增順序。2基本要求略。3測(cè)試數(shù)據(jù)（1）順序表a：1 3 6 7 9 順序表b：2 4 5 8。（2）自擬。4實(shí)現(xiàn)提示 歸并處理算法思想是：依次掃描sa和sb中的元素，比較當(dāng)前元素的值，將較小的元素賦給sc，直到一個(gè)順序表掃描完畢，然后將另一個(gè)順序表的余下的元素復(fù)制到sc中。（三）單鏈表操作驗(yàn)證1問(wèn)題描述 對(duì)以鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)的線性表，驗(yàn)證其插入、刪除、查找、求長(zhǎng)度和就地逆置等操作。2基本要求用菜單實(shí)現(xiàn)操作選擇。3測(cè)試數(shù)據(jù)自擬。（四）單鏈表的應(yīng)用（選作）1問(wèn)題描述某百貨公司倉(cāng)庫(kù)中有一批電視機(jī)，按其價(jià)格從低到高的次序構(gòu)成了一個(gè)單鏈表存于計(jì)算機(jī)中，鏈表的每個(gè)

5、結(jié)點(diǎn)指出同樣價(jià)格的電視機(jī)的臺(tái)數(shù)?，F(xiàn)在又有m臺(tái)價(jià)格為h元的電視機(jī)入庫(kù)。將新入庫(kù)的電視機(jī)的相關(guān)數(shù)據(jù)加入鏈表中。2基本要求注意價(jià)格在鏈表中是否已出現(xiàn)。3測(cè)試數(shù)據(jù)自擬。4 實(shí)現(xiàn)提示鏈表結(jié)點(diǎn)至少包含三個(gè)域：價(jià)格、數(shù)量和指針域，其結(jié)構(gòu)可如下表示： cost num next（五）一元多項(xiàng)式相加（選做）1問(wèn)題描述求兩個(gè)一元多項(xiàng)式a(x)=a0+a1x+a2x2+anxn 和b(x)=b0+b1x+b2x2+bmxm 的和c（x）。2基本要求算法輸入為兩個(gè)多項(xiàng)式中各項(xiàng)的系數(shù)和指數(shù)。算法輸出為多項(xiàng)式的和，參考輸出格式：7x0+6x1+1x2+2x4+4x9+6x11。3測(cè)試數(shù)據(jù)（1）多項(xiàng)式a：7+2x+5x3+

6、4x9+6x11 多項(xiàng)式b： 4x+x2-5x3+2x4（2）自擬。4 實(shí)現(xiàn)提示（1）多項(xiàng)式的存儲(chǔ)結(jié)構(gòu)多項(xiàng)式的每一項(xiàng)由其相應(yīng)的系數(shù)和指數(shù)確定，各項(xiàng)間具有線性關(guān)系，因而可以采用線性表實(shí)現(xiàn)。鑒于多項(xiàng)式非零項(xiàng)項(xiàng)數(shù)的不確定性，采用單鏈表存儲(chǔ)更為恰當(dāng)，多項(xiàng)式的每一個(gè)非零項(xiàng)對(duì)應(yīng)鏈表中的一個(gè)結(jié)點(diǎn)，且鏈表中的結(jié)點(diǎn)從頭到尾按指數(shù)遞增有序排列。多項(xiàng)式鏈表中的結(jié)點(diǎn)結(jié)構(gòu)如下：coef exp next其中coef域存放項(xiàng)的系數(shù)，exp域存放項(xiàng)的指數(shù)，next域存放指向下一結(jié)點(diǎn)的指針。（2）求兩個(gè)多項(xiàng)式和的算法基本思想：定義三個(gè)指針?lè)謩e指向三個(gè)多項(xiàng)式兩多項(xiàng)式a(x)、b(x)和c(x)的鏈表中的當(dāng)前結(jié)點(diǎn)。依次掃描多項(xiàng)式

7、a鏈表和多項(xiàng)式b鏈表中各結(jié)點(diǎn)，作相應(yīng)結(jié)點(diǎn)的指數(shù)比較。若指數(shù)相等，則系數(shù)相加，相加后系數(shù)若不為0，則生成一個(gè)新結(jié)點(diǎn)，鏈入多項(xiàng)式和c的鏈表，相應(yīng)指針后移。若指數(shù)不相等，則對(duì)指數(shù)小的項(xiàng)生成一新結(jié)點(diǎn)，鏈入多項(xiàng)式和c的鏈表，相應(yīng)指針后移。這一過(guò)程直到a、b鏈表中有一個(gè)鏈表掃描完畢為止。將另一個(gè)未掃描完畢的多項(xiàng)式中剩余項(xiàng)結(jié)點(diǎn)鏈入和c的鏈表。三、實(shí)驗(yàn)要求本實(shí)驗(yàn)最低要求為在4個(gè)學(xué)時(shí)內(nèi)完成實(shí)驗(yàn)內(nèi)容（一）和（四）。實(shí)驗(yàn)二 棧和隊(duì)列及其應(yīng)用一、實(shí)驗(yàn)?zāi)康呐c要求深入了解棧和隊(duì)列的特性，以便在實(shí)際問(wèn)題中靈活運(yùn)用，鞏固對(duì)這兩種結(jié)構(gòu)的構(gòu)造方法的掌握。二、實(shí)驗(yàn)內(nèi)容（一）棧操作的驗(yàn)證1問(wèn)題描述 對(duì)于順序棧、鏈棧的基本操作進(jìn)行驗(yàn)證

8、。2基本要求考慮各種可能情況（包括溢出等）。3測(cè)試數(shù)據(jù)自擬。（二）隊(duì)列操作的驗(yàn)證1問(wèn)題描述 對(duì)于順序隊(duì)列、鏈隊(duì)列的基本操作進(jìn)行驗(yàn)證。2基本要求考慮各種可能情況（包括溢出等）。3測(cè)試數(shù)據(jù)自擬。（三）隊(duì)列元素倒置（選做）1問(wèn)題描述q是一個(gè)非空隊(duì)列，s是一個(gè)空棧。實(shí)現(xiàn)將q中元素倒置。2基本要求僅使用棧和隊(duì)列的基本操作及單個(gè)變量x 。3測(cè)試數(shù)據(jù)自擬。4實(shí)現(xiàn)提示將隊(duì)列中元素出隊(duì)，入棧，再將棧中元素出棧并入隊(duì)。三、實(shí)驗(yàn)要求本實(shí)驗(yàn)最低要求為在4個(gè)學(xué)時(shí)內(nèi)完成實(shí)驗(yàn)內(nèi)容（一）和（二）中一種存儲(chǔ)結(jié)構(gòu)下的操作驗(yàn)證。四、應(yīng)用舉例（一）利用隊(duì)列解決分油問(wèn)題問(wèn)題描述 設(shè)有大小不等的三個(gè)無(wú)刻度的油桶，分別能盛滿(mǎn)x，y，z公升

9、油。初始時(shí)，第一個(gè)油桶盛滿(mǎn)油，第二、三個(gè)油桶為空，尋找一種最少步驟的分油方式，在某一個(gè)油桶上分出targ公升油。算法輸入 三個(gè)油桶的盛油量，要分出的油量targ。算法輸出 分油的結(jié)果。算法要點(diǎn) 分油過(guò)程中，由于油桶上沒(méi)有刻度，只能將油桶倒?jié)M或者倒空。三個(gè)油桶盛油的總量始終等于初始時(shí)第一個(gè)油桶盛滿(mǎn)的油量。算法的主要思想：每次判斷當(dāng)前油桶是不是可以倒出油，以及其他某個(gè)油桶是不是可以倒進(jìn)油。如果滿(mǎn)足以上條件，那么當(dāng)前油桶的油或全部倒出，或?qū)⒘硪挥屯暗節(jié)M，針對(duì)兩種不同的情況作不同的處理。使用一個(gè)隊(duì)列p，記錄每次分油時(shí)各個(gè)油桶的盛油量和倒油過(guò)程等信息，隊(duì)列中只記錄互不相同的盛油狀態(tài)（各個(gè)油桶的盛油量）。

10、如果列舉出倒油過(guò)程的所有不同的盛油狀態(tài)，經(jīng)考察全部狀態(tài)后，未能分出targ公升油的情況，就確定這個(gè)分油問(wèn)題無(wú)解。隊(duì)列p通過(guò)指針he和ta實(shí)現(xiàn)倒油過(guò)程的控制。1、算法（1）數(shù)據(jù)類(lèi)型定義typedef struct int st4; int sb,eb; int last; object;object p100;int fu4;int q100;（2）分油算法void fenyou( ) int w4,w14; int he,ta,i,j,k,m,re,targ,fo,un,bo; printf(輸入各油桶盛油量n); printf(1:); /輸入油桶盛油量 scanf(%d,&fu1); pr

11、intf(n); printf(2:); scanf(%d,&fu2); printf(n); printf(3:); scanf(%d,&fu3); printf(n); printf(要分出的油量:); /輸入要分出的油量 scanf(%d,&targ); printf(n); fo=false; /標(biāo)志，true表示分油成功，false表示分油失敗 un=false; he=1; /he 隊(duì)列的頭指針，ta 隊(duì)列的尾指針 ta=1; p1.st1=fu1; /油桶初始狀態(tài)：1 滿(mǎn)，2、3空 p1.st2=0; p1.st3=0; p1.sb=1; p1.eb=1; p1.last=1;

12、do /分油過(guò)程 w1=phe.st1; w2=phe.st2; w3=phe.st3; i=0; while (i0) j=0; while (j3)&(!fo)&(!un) j=j+1; if (wjre) w1j=fuj; w1i=wi-re; else w1i=0; w1j=wj+wi; bo=false; k=1; while (k=ta)&(!bo) bo=true; for (m=1;m=3;m+) if (w1m!=pk.stm) bo=false; k=k+1; if (!bo) ta=ta+1; /分油的一個(gè)步驟入隊(duì) pta.st1=w11; pta.st2=w12; pt

13、a.st3=w13; pta.sb=i; pta.eb=j; pta.last=he; for (m=1;mta) un=true; while (!fo&!un); printf(分油過(guò)程:n); if (!fo) /分油失敗 printf(失敗); else /分油成功，將分油過(guò)程的步驟依次輸出 k=0; i=ta; while (i!=1) k=k+1; qk=i; i=pi.last; for (;k=1;k-) printf(%2d-%2d,pqk.sb,pqk.eb); printf(%3d%3d%3d,pqk.st1, pqk.st2, pqk.st3); printf(n);

14、2、程序#include typedef struct int st4; int sb,eb; int last; object;object p100;int fu4;int q100;/各算法清單同前 void main( )fenyou( );3、測(cè)試數(shù)據(jù)三個(gè)油桶盛油量分別為：80 50 30要分出的油量為：404、程序運(yùn)行結(jié)果分油過(guò)程：1-2 30 50 0 2-3 30 20 30 3-1 60 20 0 2-3 60 0 20 1-2 10 50 20 2-3 10 40 30（二） 迷宮問(wèn)題問(wèn)題描述 編寫(xiě)一個(gè)程序求解迷宮問(wèn)題。迷宮是一個(gè)如圖2.6所示的m行n列的0、1矩陣，其中0

15、表示無(wú)障礙，1表示有障礙。設(shè)入口為（1，1），出口為（m，n），每次移動(dòng)只能從一個(gè)無(wú)障礙的單元移到其周?chē)?個(gè)方向上任一無(wú)障礙的單元，編制程序給出一條通過(guò)迷宮的路徑或報(bào)告一個(gè)“無(wú)法通過(guò)”的信息。算法輸入 代表迷宮人口的坐標(biāo)（默認(rèn)取1，1）。算法輸出 穿過(guò)迷宮的結(jié)果，兩種情況之一： 穿越成功，輸出路徑； 穿越失敗，給出提示。算法要點(diǎn)要尋找一條通過(guò)迷宮的路徑，就必須進(jìn)行試探性搜索，只要有路可走就前進(jìn)一步，無(wú)路可走時(shí)，退回一步，重新選擇未走過(guò)的可走的路，如此繼續(xù)，直至到達(dá)出口或返回入口（無(wú)法通過(guò)迷宮）。可使用如下的數(shù)據(jù)結(jié)構(gòu)：mg1.m,1.n表示迷宮，為避免在走迷宮時(shí)出界，將迷宮數(shù)組的邊界以1包圍起來(lái)

16、，所以一個(gè)mn大小的迷宮，則需要一個(gè)（m+2）(n+2)大小的數(shù)組表示，即mg0.m+1,0.n+1表示迷宮，用數(shù)組zx，zy分別表示x，y方向的移動(dòng)增量，其值如表2.1所示。在探索前進(jìn)路徑時(shí)，需要將搜索的蹤跡記錄下來(lái)，記錄的蹤跡應(yīng)包含當(dāng)前位置以及前趨位置。在搜索函數(shù)中，將所有需要搜索的位置形成一個(gè)隊(duì)列，將隊(duì)列中的每一個(gè)元素可能到達(dá)的位置加入到隊(duì)列中，當(dāng)隊(duì)列中某元素有可能到達(dá)的位置全部加入到隊(duì)列之后，即從隊(duì)列中將該元素去掉。用變量front和rear分別表示隊(duì)列的首與尾，當(dāng)rear指示的元素已到達(dá)出口（m，n）時(shí)，根據(jù)rear所指示的前驅(qū)號(hào)可回溯得到走迷宮的最短路徑。表2.1 zx，zy數(shù)組的

17、方向取值方向北東北東東南南西南西西北下標(biāo)12345678zx-1-101110-1zy01110-1-1-1入口出口圖2.1 迷宮示意圖1、算法（1）類(lèi)型定義 迷宮定義int mgm+2n+2; 定義struct stypeint x,y,pre; sq400;（3）方向數(shù)組定義int zx8,zy8;（2）操作算法輸出路徑算法void printpath( int rear) int i,j; structstype p100; i=rear; do printf(%d,%d),sqi.r,sqi.c); i=sqi.pre; while(i!=0); 走迷宮算法void mgpath( )

18、 int i,j,x,y,v,find,rear,front; sq1.r=1; sq1.c=1; sq1.pre=0; find=0; j=0; front=1; /從（1，1）開(kāi)始搜索 rear=1; mg11=-1; while(front=rear&!find) x=sqfront.r; y=sqfront.c; for(v=0;v8;v+) /循環(huán)掃描每個(gè)方向 i=zxv+x; /選擇一個(gè)前進(jìn)方向（i,j） j=zyv+y; if (mgij=0) /如果該方向可走 rear+; /進(jìn)入隊(duì)列 sqrear.r=i; sqrear.c=j; sqrear.pre=front; mgij

19、=- /避免搜索過(guò)的位置重復(fù)搜索 if (i=m&j=n) /找到了出口 printpath(rear); find=1; front+; if (!find) printf(不存在路徑！);2、程序#include #define m 8 /m、n為迷宮的行、列數(shù)，可以自選 #define n 8struct stype int r,c,pre; sq400;int mgm+2n+2;int zx8=-1,-1,0,1,1,1,0,-1,zy8=0,1,1,1,0,-1,-1,-1;/各算法清單同前 void main() int i,j; printf(輸入迷宮:); for(i=0;i=

20、m+1;i+) printf(第%d行:n,i); for(j=0;j=n+1;j+) scanf(%d,&mgij); printf(輸出迷宮:); for(i=0;i=m+1;i+) for(j=0;jdata=ch; s-lchild=null; s-rchild=null; rear+; qrear=s; /虛結(jié)點(diǎn)指針null或新結(jié)點(diǎn)地址入隊(duì) if(rear=1) /輸入的第一個(gè)結(jié)點(diǎn)為根結(jié)點(diǎn) root=s; else if(s&qfront) /孩子和雙親結(jié)點(diǎn)均不是虛結(jié)點(diǎn) if(rear%2=0) qfront-lchild=s; /新結(jié)點(diǎn)是左孩子 else qfront-rchild

21、=s; /新結(jié)點(diǎn)是右孩子 if(rear%2=1) front+; /結(jié)點(diǎn)*qfront的兩個(gè)孩子已處理完畢，出隊(duì)列 ch=getchar(); /輸入下一個(gè)字符 return root; /返回根指針 （二）二叉樹(shù)的線索化1問(wèn)題描述對(duì)二叉樹(shù)進(jìn)行中序線索化。2基本要求 以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，并對(duì)該線索二叉樹(shù)進(jìn)行中序遍歷。3測(cè)試數(shù)據(jù)自擬。三、實(shí)驗(yàn)要求本實(shí)驗(yàn)要求為在4個(gè)學(xué)時(shí)內(nèi)完成實(shí)驗(yàn)內(nèi)容（一）和（二）。實(shí)驗(yàn)六 樹(shù)的應(yīng)用一、實(shí)驗(yàn)?zāi)康呐c要求通過(guò)應(yīng)用樹(shù)結(jié)構(gòu)解決實(shí)際問(wèn)題，掌握樹(shù)的實(shí)際應(yīng)用，從而將理論與實(shí)際結(jié)合起來(lái)。二、實(shí)驗(yàn)內(nèi)容（一）借助二叉排序樹(shù)實(shí)現(xiàn)排序1問(wèn)題描述對(duì)于給定的n個(gè)關(guān)鍵字值，采用二叉排序樹(shù)方

22、法對(duì)其進(jìn)行排序。2基本要求 以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)。3測(cè)試數(shù)據(jù)自擬。4實(shí)現(xiàn)提示整個(gè)問(wèn)題的求解可抓住以下重點(diǎn): 采用建立二叉排序樹(shù)的方法，將n個(gè)鍵值作為結(jié)點(diǎn)值，生成一棵二叉排序樹(shù)。 對(duì)生成的二叉排序樹(shù)進(jìn)行中序遍歷，得到遞增序列。（二）哈夫曼樹(shù)的構(gòu)造1問(wèn)題描述對(duì)于給定的n 個(gè)結(jié)點(diǎn)的權(quán)值，建立一棵哈夫曼樹(shù)。2基本要求 詳細(xì)說(shuō)明所采用的哈夫曼樹(shù)的存儲(chǔ)格式及輸出方式。3測(cè)試數(shù)據(jù)（1）7個(gè)葉子結(jié)點(diǎn)，權(quán)值分別為：7 5 2 3 8 10 20（2）自擬。（三）標(biāo)識(shí)符的處理（選做）1問(wèn)題描述識(shí)別源程序文件“b.txt”中出現(xiàn)的標(biāo)識(shí)符，并按字母順序輸出這些標(biāo)識(shí)符及所在的行號(hào)序列，對(duì)于同一個(gè)標(biāo)識(shí)符出現(xiàn)的不同行號(hào)，

23、要求按遞增的順序排序輸出。2基本要求 無(wú)。3測(cè)試數(shù)據(jù)自擬。4實(shí)現(xiàn)提示算法分兩步實(shí)現(xiàn): 識(shí)別標(biāo)識(shí)符，形成一棵二叉排序樹(shù)。樹(shù)結(jié)點(diǎn)的鍵值為標(biāo)識(shí)符的前10個(gè)字符，并將同一標(biāo)識(shí)符所在的不同行號(hào)按從小到大的順序存放在一個(gè)鏈?zhǔn)疥?duì)列中。二叉排序樹(shù)中的結(jié)點(diǎn)數(shù)據(jù)域及左、右指針域之外，增設(shè)兩個(gè)分別指向鏈表的首結(jié)點(diǎn)和尾結(jié)點(diǎn)的指針域。如下圖所示： 輸出標(biāo)識(shí)符和相應(yīng)的行號(hào)序列。按中序遍歷由標(biāo)識(shí)符組成的二叉排序樹(shù)，輸出結(jié)點(diǎn)中的標(biāo)識(shí)符及行號(hào)隊(duì)列中的行號(hào)。三、實(shí)驗(yàn)要求本實(shí)驗(yàn)最低要求為在4個(gè)學(xué)時(shí)內(nèi)完成實(shí)驗(yàn)內(nèi)容（一）和（二）。實(shí)驗(yàn)七 圖及其應(yīng)用一、實(shí)驗(yàn)?zāi)康呐c要求掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)，將圖的相關(guān)理論應(yīng)用到解決實(shí)際問(wèn)題的過(guò)

24、程中，深入理解數(shù)據(jù)結(jié)構(gòu)理論在解決實(shí)際問(wèn)題中的作用，鍛煉綜合設(shè)計(jì)能力。二、實(shí)驗(yàn)內(nèi)容（一）以鄰接矩陣為存儲(chǔ)結(jié)構(gòu)的圖的遍歷1問(wèn)題描述對(duì)以鄰接矩陣為存儲(chǔ)結(jié)構(gòu)的圖實(shí)現(xiàn)深度優(yōu)先搜索和廣度優(yōu)先搜索遍歷。2基本要求采用連通無(wú)向圖作為遍歷對(duì)象。3測(cè)試數(shù)據(jù)自擬。（二）以鄰接表為存儲(chǔ)結(jié)構(gòu)的圖的遍歷1問(wèn)題描述對(duì)以鄰接表為存儲(chǔ)結(jié)構(gòu)的圖實(shí)現(xiàn)深度優(yōu)先搜索和廣度優(yōu)先搜索遍歷。2基本要求采用連通無(wú)向圖作為遍歷對(duì)象，建立鄰接表時(shí)頂點(diǎn)對(duì)序號(hào)從大到小輸入。3測(cè)試數(shù)據(jù)自擬。（三）求圖中兩頂點(diǎn)間給定長(zhǎng)度的簡(jiǎn)單路徑1問(wèn)題描述利用遍歷圖的方法輸出一個(gè)無(wú)向圖中從頂點(diǎn)vi到頂點(diǎn)vj的長(zhǎng)度為l的簡(jiǎn)單路徑。2基本要求無(wú)向圖采用鄰接表作為存儲(chǔ)結(jié)構(gòu)，頂

25、點(diǎn)用整數(shù)編號(hào)表示。3測(cè)試數(shù)據(jù)自擬。4實(shí)現(xiàn)提示算法思想：利用深度優(yōu)先搜索遍歷圖，并設(shè)一個(gè)棧（stack）保存遍歷路徑上的頂點(diǎn)，同時(shí)以變量d記下當(dāng)前的路徑長(zhǎng)度。從v=vi出發(fā)，找v的鄰接頂點(diǎn)w，若w已訪問(wèn)過(guò)，則找下一個(gè)鄰接頂點(diǎn)；若w=vj，且d=l-1，則路徑即為所求；若wvj，且dl-1，則從w出發(fā)繼續(xù)遍歷，否則找下一個(gè)鄰接頂點(diǎn)，若找不到下一個(gè)鄰接頂點(diǎn)（設(shè)w=0），則退棧，找前一頂點(diǎn)的下一個(gè)鄰接頂點(diǎn)，若?？眨瑒t說(shuō)明沒(méi)有這樣的路徑。（四）醫(yī)院選址問(wèn)題1問(wèn)題描述n個(gè)村莊之間的交通圖用有向加權(quán)圖表示，圖中的有向邊表示第i個(gè)村莊和第j個(gè)村莊之間有道路，邊上的權(quán)表示這條道路的長(zhǎng)度?，F(xiàn)在要從這n個(gè)村莊中選擇

26、一個(gè)村莊建一所醫(yī)院，問(wèn)這所醫(yī)院應(yīng)建在哪個(gè)村莊，才能使離醫(yī)院最遠(yuǎn)的村莊到醫(yī)院最近。2基本要求無(wú)。3測(cè)試數(shù)據(jù)題中所給加權(quán)有向圖。4實(shí)現(xiàn)提示這是一個(gè)求有向圖中心點(diǎn)的問(wèn)題。設(shè)圖g=（v，e），對(duì)任一頂點(diǎn)k，稱(chēng)e（k）=為頂點(diǎn)k的偏心度，偏心度最小的頂點(diǎn)即為圖g的中心點(diǎn)。圖中所示的加權(quán)有向圖中，其各頂點(diǎn)的偏心度如表所示。表1 頂點(diǎn)的偏心度頂 點(diǎn)偏心度ab6c8d5e7d是具有最小偏心度的頂點(diǎn)，所以圖g的中心點(diǎn)是頂點(diǎn)d。算法分三步實(shí)現(xiàn)： 對(duì)加權(quán)有向圖g，調(diào)用floyd算法，求每對(duì)頂點(diǎn)間最短路徑長(zhǎng)度的矩陣length。 對(duì)矩陣length的每一列求最大值 e（j）=，即得各頂點(diǎn)j的偏心度。 求出具有最小偏心

27、度的頂點(diǎn)k ， 使得e（k）=，頂點(diǎn)k即為圖的中心點(diǎn)。三、實(shí)驗(yàn)要求本實(shí)驗(yàn)最低要求為在6個(gè)學(xué)時(shí)內(nèi)完成：1實(shí)驗(yàn)內(nèi)容（一）或（二）中一題。 2實(shí)驗(yàn)內(nèi)容（三）或（四）中一題。實(shí)驗(yàn)八 查找一、實(shí)驗(yàn)?zāi)康呐c要求本實(shí)驗(yàn)驗(yàn)證數(shù)據(jù)處理的重要技術(shù)之一：查找。通過(guò)對(duì)不同查找技術(shù)的實(shí)踐，注意查找操作的效率，理解提高查找的效率是提高其他操作效率的基礎(chǔ)。二、實(shí)驗(yàn)內(nèi)容（一）有序線性表的查找1問(wèn)題描述 在有序表sortlist中插入一個(gè)元素x，并保持表的有序性。2基本要求 利用二分查找方法完成。3測(cè)試數(shù)據(jù) 根據(jù)以下數(shù)據(jù)類(lèi)型定義自擬。typedef char datatype;typedef int keytype;typede

28、f struct keytype key; datatype temp80; table; / 定義有序線性表類(lèi)型 table sortlist20; / 定義有序線性表 在程序中構(gòu)造線性表sortlist時(shí)應(yīng)使表中結(jié)點(diǎn)按關(guān)健字有序排列。4實(shí)現(xiàn)提示（1）先在有序表中利用二分查找算法查找關(guān)健字等于或小于x.key的結(jié)點(diǎn)，查找思想如下： 定義有序表的兩個(gè)端點(diǎn)值：low=0; high=表長(zhǎng)； 定義折半點(diǎn)：mid = (low+high)/2； 將待查值x.key與折半點(diǎn)(mid)處結(jié)點(diǎn)的關(guān)健字進(jìn)行比較：若x.key與listmid.key相等：查找結(jié)束，mid即插入位置；若x.key大于listm

29、id.key：low=mid+1（定義右子表）；若x.key小于listmid.key：high=mid-1（定義左子表）。 反復(fù)執(zhí)行、，直到插入位置（mid或low）確定。（2）將插入位置后的結(jié)點(diǎn)全部右移一個(gè)結(jié)點(diǎn)位置，并將新結(jié)點(diǎn)放入插入位置。（二）樹(shù)表的查找1問(wèn)題描述 設(shè)計(jì)一個(gè)在二叉排序樹(shù)中查找指定結(jié)點(diǎn)并對(duì)該結(jié)點(diǎn)進(jìn)行修改的非遞歸算法。2測(cè)試數(shù)據(jù) 為提高樹(shù)表查找的可操作性，算法中的輸入數(shù)據(jù)可由數(shù)據(jù)文件tree.txt提供。文件內(nèi)每一行可視作一個(gè)結(jié)點(diǎn)，行首數(shù)字為結(jié)點(diǎn)關(guān)鍵字，文件末尾的數(shù)字-1可做為文件讀取結(jié)束的標(biāo)志。樹(shù)表建立的結(jié)果輸出到文件treelist.txt中，而查找結(jié)果輸出到文件。search.txt中。3實(shí)現(xiàn)提示此問(wèn)題是要求設(shè)計(jì)二叉排序樹(shù)的建立及樹(shù)表查找兩個(gè)算法。二叉排序樹(shù)（樹(shù)表）建立要點(diǎn)： 從文件tree.txt中逐個(gè)讀取結(jié)點(diǎn)數(shù)據(jù)， 申請(qǐng)新結(jié)點(diǎn)空間s，并將從文件中讀出的結(jié)點(diǎn)數(shù)據(jù)存入s， 若結(jié)點(diǎn)s的關(guān)健字小于二