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

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

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

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

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

5、結(jié)點(diǎn)指出同樣價格的電視機(jī)的臺數(shù)?，F(xiàn)在又有m臺價格為h元的電視機(jī)入庫。將新入庫的電視機(jī)的相關(guān)數(shù)據(jù)加入鏈表中。2基本要求注意價格在鏈表中是否已出現(xiàn)。3測試數(shù)據(jù)自擬。4 實(shí)現(xiàn)提示鏈表結(jié)點(diǎn)至少包含三個域：價格、數(shù)量和指針域，其結(jié)構(gòu)可如下表示： cost num next（五）一元多項(xiàng)式相加（選做）1問題描述求兩個一元多項(xiàng)式a(x)=a0+a1x+a2x2+anxn 和b(x)=b0+b1x+b2x2+bmxm 的和c（x）。2基本要求算法輸入為兩個多項(xiàng)式中各項(xiàng)的系數(shù)和指數(shù)。算法輸出為多項(xiàng)式的和，參考輸出格式：7x0+6x1+1x2+2x4+4x9+6x11。3測試數(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)式的存儲結(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ù)的不確定性，采用單鏈表存儲更為恰當(dāng)，多項(xiàng)式的每一個非零項(xiàng)對應(yīng)鏈表中的一個結(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）求兩個多項(xiàng)式和的算法基本思想：定義三個指針分別指向三個多項(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，則生成一個新結(jié)點(diǎn)，鏈入多項(xiàng)式和c的鏈表，相應(yīng)指針后移。若指數(shù)不相等，則對指數(shù)小的項(xiàng)生成一新結(jié)點(diǎn)，鏈入多項(xiàng)式和c的鏈表，相應(yīng)指針后移。這一過程直到a、b鏈表中有一個鏈表掃描完畢為止。將另一個未掃描完畢的多項(xiàng)式中剩余項(xiàng)結(jié)點(diǎn)鏈入和c的鏈表。三、實(shí)驗(yàn)要求本實(shí)驗(yàn)最低要求為在4個學(xué)時內(nèi)完成實(shí)驗(yàn)內(nèi)容（一）和（四）。實(shí)驗(yàn)二 棧和隊列及其應(yīng)用一、實(shí)驗(yàn)?zāi)康呐c要求深入了解棧和隊列的特性，以便在實(shí)際問題中靈活運(yùn)用，鞏固對這兩種結(jié)構(gòu)的構(gòu)造方法的掌握。二、實(shí)驗(yàn)內(nèi)容（一）棧操作的驗(yàn)證1問題描述 對于順序棧、鏈棧的基本操作進(jìn)行驗(yàn)證

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

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

10、如果列舉出倒油過程的所有不同的盛油狀態(tài)，經(jīng)考察全部狀態(tài)后，未能分出targ公升油的情況，就確定這個分油問題無解。隊列p通過指針he和ta實(shí)現(xiàn)倒油過程的控制。1、算法（1）數(shù)據(jù)類型定義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 隊列的頭指針，ta 隊列的尾指針 ta=1; p1.st1=fu1; /油桶初始狀態(tài)：1 滿，2、3空 p1.st2=0; p1.st3=0; p1.sb=1; p1.eb=1; p1.last=1;

12、do /分油過程 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; /分油的一個步驟入隊 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(分油過程:n); if (!fo) /分油失敗 printf(失敗); else /分油成功，將分油過程的步驟依次輸出 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、測試數(shù)據(jù)三個油桶盛油量分別為：80 50 30要分出的油量為：404、程序運(yùn)行結(jié)果分油過程：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（二） 迷宮問題問題描述 編寫一個程序求解迷宮問題。迷宮是一個如圖2.6所示的m行n列的0、1矩陣，其中0

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

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

17、方向取值方向北東北東東南南西南西西北下標(biāo)12345678zx-1-101110-1zy01110-1-1-1入口出口圖2.1 迷宮示意圖1、算法（1）類型定義 迷宮定義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）開始搜索 rear=1; mg11=-1; while(front=rear&!find) x=sqfront.r; y=sqfront.c; for(v=0;v8;v+) /循環(huán)掃描每個方向 i=zxv+x; /選擇一個前進(jìn)方向（i,j） j=zyv+y; if (mgij=0) /如果該方向可走 rear+; /進(jìn)入隊列 sqrear.r=i; sqrear.c=j; sqrear.pre=front; mgij

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

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

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

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

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

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

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

28、f struct keytype key; datatype temp80; table; / 定義有序線性表類型 table sortlist20; / 定義有序線性表 在程序中構(gòu)造線性表sortlist時應(yīng)使表中結(jié)點(diǎn)按關(guān)健字有序排列。4實(shí)現(xiàn)提示（1）先在有序表中利用二分查找算法查找關(guān)健字等于或小于x.key的結(jié)點(diǎn)，查找思想如下： 定義有序表的兩個端點(diǎn)值：low=0; high=表長； 定義折半點(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)全部右移一個結(jié)點(diǎn)位置，并將新結(jié)點(diǎn)放入插入位置。（二）樹表的查找1問題描述 設(shè)計一個在二叉排序樹中查找指定結(jié)點(diǎn)并對該結(jié)點(diǎn)進(jìn)行修改的非遞歸算法。2測試數(shù)據(jù) 為提高樹表查找的可操作性，算法中的輸入數(shù)據(jù)可由數(shù)據(jù)文件tree.txt提供。文件內(nèi)每一行可視作一個結(jié)點(diǎn)，行首數(shù)字為結(jié)點(diǎn)關(guān)鍵字，文件末尾的數(shù)字-1可做為文件讀取結(jié)束的標(biāo)志。樹表建立的結(jié)果輸出到文件treelist.txt中，而查找結(jié)果輸出到文件。search.txt中。3實(shí)現(xiàn)提示此問題是要求設(shè)計二叉排序樹的建立及樹表查找兩個算法。二叉排序樹（樹表）建立要點(diǎn)： 從文件tree.txt中逐個讀取結(jié)點(diǎn)數(shù)據(jù)， 申請新結(jié)點(diǎn)空間s，并將從文件中讀出的結(jié)點(diǎn)數(shù)據(jù)存入s， 若結(jié)點(diǎn)s的關(guān)健字小于二