數(shù)據(jù)結(jié)構(gòu)與算法實踐指導 課件匯 張彬連 6-圖-11-動態(tài)規(guī)劃

第6章

圖主講教師：張彬連吉首大學6.1知識簡介

圖是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為G=（V，E），V表示圖G中頂點的集合，E表示圖G中邊的集合。根據(jù)圖的邊是否有無方向，將圖分為有向圖和無向圖。如果圖的任意兩個頂點之間的邊是無向的，則稱該圖為無向圖。如果無向圖的邊是帶權(quán)值的，則稱為無向網(wǎng)。如果圖的任意兩個頂點之間的邊是有向的，這樣的邊稱為弧，稱這樣的圖為有向圖。如果有向圖的弧是帶權(quán)值的，則稱為有向網(wǎng)。6.1.1圖的定義6.1知識簡介

圖有兩種典型的存儲結(jié)構(gòu)：鄰接矩陣存儲結(jié)構(gòu)和鄰接表存儲結(jié)構(gòu)。6.1.2圖的存儲6.1知識簡介1、鄰接矩陣存儲結(jié)構(gòu)6.1.2圖的存儲

鄰接矩陣表示法是用一個頂點表和一個鄰接矩陣來存儲圖的方法。頂點表用來記錄各個頂點的信息。鄰接矩陣是用來存儲各個頂點之間關(guān)系的矩陣。設(shè)圖G(V，E)是具有n個頂點的圖，則圖的鄰接矩陣是一個二維數(shù)組G.arcs[n][n]，定義為，如果頂點i和頂點j之間有邊或弧，則值為1，否則為0。G.arcs[i][j]表示如下：

6.1知識簡介6.1.2圖的存儲

下圖顯示了一個無向圖及其鄰接矩陣。

無向圖的鄰接矩陣是對稱的矩陣，圖中頂點i的度等于鄰接矩陣中對應(yīng)的第i行(列)中1的個數(shù)，鄰接矩陣中所有元素之和等于無向圖邊的2倍。1、鄰接矩陣存儲結(jié)構(gòu)6.1知識簡介

下圖顯示了一個有向圖及其鄰接矩陣。

有向圖的鄰接矩陣可能是不對稱的。圖中頂點i的出度等于鄰接矩陣中第i行元素之和，頂點的入度等于鄰接矩陣中第i列元素之和。鄰接矩陣中所有元素之和等于有向圖中弧的個數(shù)。1、鄰接矩陣存儲結(jié)構(gòu)6.1.2圖的存儲6.1知識簡介

為了表示一個圖，應(yīng)該描述的信息有頂點信息表、頂點個數(shù)、邊的個數(shù)、頂點之間的關(guān)系，而鄰接矩陣主要表示頂點之間的關(guān)系。

用鄰接矩陣表示圖的定義如下：#defineMAXINT32767//表示極大值，即∞#defineMAXVNUM100//最大頂點數(shù)typedefstruct{VerTexTypevexs[MAXVNUM];//頂點表ArcTypearcs[MAXVNUM][MAXVNUM];//鄰接矩陣intvexNum； //頂點數(shù)intarcNum;//邊或弧數(shù)}AMGraph;1、鄰接矩陣存儲結(jié)構(gòu)6.1.2圖的存儲6.1知識簡介6.1.2圖的存儲

如果用鄰接矩陣存儲網(wǎng)，則鄰接矩陣中元素的值用權(quán)值或無窮表示。如果兩個頂點之間有邊則對應(yīng)鄰接矩陣中的值為該邊的權(quán)值，如果沒有邊則值為無窮。

鄰接矩陣的空間復雜度為O(n2)，其中n為頂點個數(shù)。1、鄰接矩陣存儲結(jié)構(gòu)6.1知識簡介

鄰接表是圖的一種鏈式存儲結(jié)構(gòu)。鄰接表表示法主要包括兩個部分：邊表和表頭結(jié)點表。邊表是對圖中每個頂點建立一個單鏈表，把與該頂點鄰接的頂點放在這個鏈表中。表頭結(jié)點表是用順序存儲結(jié)構(gòu)存儲圖中頂點信息以及與該頂點對應(yīng)邊表第一個結(jié)點的地址。

表頭結(jié)點表是由表頭結(jié)點組成。表頭結(jié)點包括兩個部分：數(shù)據(jù)域和鏈域，數(shù)據(jù)域用來存儲頂點信息，鏈域用來指向邊表的第一個結(jié)點。

邊表由表示頂點間關(guān)系的邊結(jié)點組成。邊結(jié)點包括三個部分：鄰接點域、數(shù)據(jù)域和鏈域。鄰接點域用來表示頂點的某個鄰接點在圖中的位置。數(shù)據(jù)域用來存儲與邊相關(guān)的信息，如權(quán)值。鏈域用來指向與該頂點鄰接的下一條邊或弧的結(jié)點。6.1.2圖的存儲2、鄰接表存儲結(jié)構(gòu)6.1知識簡介下圖為一個無向圖及其鄰接表表示。

無向圖某個頂點的度等于該頂點對應(yīng)單鏈表中結(jié)點個數(shù)，鏈表中所有結(jié)點的個數(shù)等于無向圖邊的2倍。6.1.2圖的存儲2、鄰接表存儲結(jié)構(gòu)6.1知識簡介下圖為一個有向圖及其鄰接表表示。

有向圖中某個頂點的出度等于鄰接表中對應(yīng)單鏈表中結(jié)點個數(shù)，鏈表中所有結(jié)點的個數(shù)等于有向圖弧的個數(shù)。6.1.2圖的存儲2、鄰接表存儲結(jié)構(gòu)6.1知識簡介用鄰接表表示圖的定義如下：#defineMAXVNUM100//最大頂點數(shù)typedefstructArcNode//邊結(jié)點{intadjvex;//該邊所依附的另一個頂點的序號structArcNode*nextarc;

//指向下一條邊的指針OtherInfoinfo;//邊（或弧）相關(guān)的信息}ArcNode;typedefstructVNode//表頭結(jié)點{ VerTexTypedata;//頂點信息ArcNode*firstarc;//指向第一條依附該頂點的邊}VNode,AdjList[MAXVNUM];//AdjList表示鄰接表類型6.1.2圖的存儲2、鄰接表存儲結(jié)構(gòu)6.1知識簡介typedefstruct{AdjListvertices;//鄰接表intvexNum;//頂點個數(shù)intarcNum;//邊或弧的個數(shù)}ALGraph;//鄰接表表示如果用鄰接表存儲網(wǎng)，則在邊結(jié)點中數(shù)據(jù)域info存儲對應(yīng)邊或弧的權(quán)值。鄰接表的空間復雜度為O(n+e)，n為頂點個數(shù)，e為邊個數(shù)。用鄰接表表示圖的定義如下：6.1.2圖的存儲2、鄰接表存儲結(jié)構(gòu)6.1知識簡介6.1.3圖的遍歷1、深度優(yōu)先遍歷

圖的深度優(yōu)先搜索遍歷（簡稱DFS）類似于樹的先序遍歷，是樹的先序遍歷的推廣。對于一個連通圖，深度優(yōu)先遍歷的過程如下：

第一步，從圖中某個頂點v出發(fā)，訪問這個起始頂點v。

第二步，找到剛訪問頂點的一個沒有訪問的鄰接點w，以w為新的起始點對圖進行深度優(yōu)先遍歷，直到剛訪問過的頂點所有鄰接點都被訪問為止。

第三步，返回前一個訪問過且仍有未被訪問的鄰接點的頂點，找到該頂點的一個未被訪問的鄰接點，訪問該頂點。

重復第二步和第三步，直至圖中所有頂點都被訪問過，搜索結(jié)束。6.1知識簡介6.1.3圖的遍歷1、深度優(yōu)先遍歷

訪問過程為了避免頂點重復訪問，設(shè)置訪問標志visited[MAXVNUM]，數(shù)組的初始值都為false，表示開始時所有的頂點都沒有被訪問。當訪問某個頂點后，將該頂點對應(yīng)的visited值設(shè)置為true，表示該頂點已被訪問。此遍歷的特點是盡可能先對縱深方向進行搜索。

對于非連通圖，從某個頂點出發(fā)遍歷后，圖中一定還有頂點未被訪問，需要從圖中另選一個未被訪問的頂點作為起點，重復上述深度優(yōu)先搜索過程，直到圖中所有頂點都被訪問為止。

注意上述深度優(yōu)先遍歷的過程第二步，以w為新的起始點對圖進行深度優(yōu)先遍歷。因此，深度優(yōu)先遍歷在一般情況下可用遞歸方式實現(xiàn)。

6.1知識簡介6.1.3圖的遍歷2、廣度優(yōu)先遍歷

廣度優(yōu)先遍歷（簡稱BFS）類似于樹的層次遍歷。對于一個連通圖，廣度優(yōu)先遍歷過程為：

第一步，從圖中某個頂點v出發(fā)，訪問頂點v。

第二步，依次訪問頂點v的各個未被訪問過鄰接點。

第三步，分別從這些鄰接點出發(fā)依次訪問它們的鄰接點，并使“先被訪問的頂點的鄰接點”先于“后被訪問的頂點的鄰接點”被訪問。

重復第三步，直到圖中所有已被訪問的頂點的鄰接點都被訪問到。6.1知識簡介6.1.3圖的遍歷2、廣度優(yōu)先遍歷

在進行廣度優(yōu)先搜索遍歷時，先訪問的頂點其鄰接點先被訪問。如果頂點i先于頂點j訪問，則頂點i的未被訪問過的鄰接點先于頂點j的未被訪問過的鄰接點訪問。因此，算法實現(xiàn)時需使用隊列來保存已被訪問過的頂點。

訪問過程中為了避免頂點重復訪問，設(shè)置訪問標志visited[MAXVNUM]，數(shù)組的初始值都為false，當訪問某個頂點后，將該頂點對應(yīng)的visited值設(shè)置為true，表示已訪問。6.1知識簡介6.1.3圖的遍歷2、廣度優(yōu)先遍歷

對于非連通圖，從某個頂點出發(fā)遍歷后，圖中一定還有頂點未被訪問，需要從圖中另選一個未被訪問的頂點作為起點，重復上述廣度優(yōu)先搜索過程，直到圖中所有頂點都被訪問為止。

圖的遍歷過程實質(zhì)上是對每個頂點查找其鄰接點的過程。6.2實驗?zāi)康?/p>

通過本章的實驗，加深對圖的鄰接矩陣、鄰接表兩種存儲方式以及深度優(yōu)先搜索、廣度優(yōu)先搜索等知識的理解，培養(yǎng)學生用圖結(jié)構(gòu)解決實際問題的能力，同時鍛煉學生實際編程和算法設(shè)計的能力。6.3實驗范例

用鄰接矩陣作為圖的存儲結(jié)構(gòu)建立一個無向圖。6.3.1范例16.3實驗范例1、問題分析6.3.1范例1

采用鄰接矩陣存儲無向圖時，需要知道頂點數(shù)、邊數(shù)和邊信息，其中矩陣（二維數(shù)組）的大小由頂點數(shù)決定，邊信息將存儲在矩陣內(nèi)。

建立無向圖的算法步驟：

①輸入總頂點數(shù)vexNum和總邊數(shù)arcNum。

②依次輸入頂點的信息并將其存入頂點表vexs中。

③初始化鄰接矩陣，將每個元素初始化為0。

④構(gòu)造鄰接矩陣。依次輸入每條邊依附的頂點，確定兩個頂點在圖中的位置i、j，將鄰接矩陣中的第i行第j列和第j行第i列的值賦值1。6.3實驗范例2、算法描述6.3.1范例1先定義無向圖存儲結(jié)構(gòu)如下：typedefstruct{VerTexTypevexs[MAXVNUM];//頂點表ArcTypearcs[MAXVNUM][MAXVNUM];//鄰接矩陣intvexNum; //頂點數(shù)intarcNum;//邊數(shù)}AMGraph;其中頂點類型VerTexType和邊類型ArcType可以定義成所需要的類型。6.3實驗范例2、算法描述6.3.1范例1

然后定義函數(shù)建立無向圖的鄰接矩陣，函數(shù)可以定義如下：StatusCreateUDG(AMGraph&G)｛inti,j,k;VerTexTypev1,v2;printf("輸入圖的頂點個數(shù)和邊數(shù):");scanf("%d%d",&G.vexNum,&G.arcNum);printf("輸入頂點信息：");fflush(stdin);//清空輸入緩沖區(qū)for(i=0;i<G.vexNum;i++){G.vexs[i]=getchar();

}6.3實驗范例2、算法描述6.3.1范例1

然后定義函數(shù)建立無向圖的鄰接矩陣，函數(shù)可以定義如下：//初始化鄰接矩陣for(i=0;i<G.vexNum;i++)for(j=0;j<G.vexNum;j++)G.arcs[i][j]=0;printf("\n");printf("輸入邊的信息(v1,v2),每輸入一條邊回車:\n");for(k=0;k<G.arcNum;k++){fflush(stdin);scanf("(%c,%c)",&v1,&v2);//查找兩個頂點的下標i=LocateVex(G,v1);j=LocateVex(G,v2);G.arcs[i][j]=1;G.arcs[j][i]=1;}returnOK;}6.3實驗范例2、算法描述6.3.1范例1

對于給出的一個頂點v，可以在頂點表中查找v對應(yīng)的下標，設(shè)計LocateVex()函數(shù)如下：intLocateVex(AMGraphG,VerTexTypev)//查找頂點v在頂點表中的位置{inti;for(i=0;i<G.vexNum;i++){if(G.vexs[i]==v)returni;}return-1;//未找到，返回-1}6.3實驗范例3、算法分析6.3.1范例1

執(zhí)行CreateUDG()函數(shù)的時間主要由用戶輸入數(shù)據(jù)的速度確定，用戶從鍵盤輸入數(shù)據(jù)需要的時間遠遠大于函數(shù)中其它語句的執(zhí)行時間。因此，計算這個函數(shù)的時間復雜度意義不大。6.3實驗范例對范例1中建立的無向圖進行深度優(yōu)先遍歷，輸出遍歷序列。6.3.2范例26.3實驗范例1、問題分析6.3.2范例2

假設(shè)從圖中第v個頂點出發(fā)對圖進行深度優(yōu)先遍歷。先訪問這個頂點，然后找到該頂點的一個沒有被訪問的鄰接點，假設(shè)為第j個頂點，以第j個頂點為新的起始點對圖進行深度優(yōu)先遍歷，直到頂點v的所有鄰接點都被訪問為止。為了表示頂點是否被訪問過，定義一個訪問標志數(shù)組visited1，如果第j個頂點沒有被訪問過，則visited1[j]=0，否則visited1[j]=1。6.3實驗范例2、算法描述6.3.2范例2

根據(jù)以上分析，先設(shè)置一個訪問標志數(shù)組visited1，然后從第v個頂點出發(fā)深度優(yōu)先遍歷無向圖G?？稍O(shè)計深度優(yōu)先遍歷函數(shù)如下：intvisited1[MAXVNUM]={0};//定義成一個全局量voidDFSTraverse(AMGraphG,intv)

{//以v為起始頂點深度優(yōu)先遍歷無向圖Gintj;printf("%3c",G.vexs[v]);visited1[v]=1;//頂點v已被訪問for(j=0;j<G.vexNum;j++)

{if(G.arcs[v][j]==1&&visited1[j]==0)//第j個頂點與v相鄰且沒有被訪問DFSTraverse(G,j);//從頂點j出發(fā)深度優(yōu)先遍歷}}6.3實驗范例3、算法分析6.3.2范例2

采用鄰接矩陣存儲方式對圖進行深度優(yōu)先遍歷時，查找一個頂點的鄰接頂點所需的時間為O(n)，需要對n個頂點的鄰接頂點進行查找，因此該時間復雜度為O(n2)。6.3實驗范例

對范例1中建立的無向圖進行廣度優(yōu)先遍歷，輸出遍歷序列。6.3.3范例36.3實驗范例1、問題分析6.3.3范例3

假設(shè)從圖中第v個頂點出發(fā)進行廣度優(yōu)先遍歷。先訪問此頂點，然后訪問該頂點的各個未曾訪問的鄰接點w1，w2，…，wk。然后，依次從w1，w2，…，wk出發(fā)訪問各自未被訪問的鄰接點。重復上面的步驟，直到全部頂點都被訪問為止。

廣度優(yōu)先遍歷需要借助隊列保存當前已經(jīng)訪問過的頂點，然后再訪問這些頂點的鄰接點。為了表示頂點是否被訪問過，定義一個訪問標志數(shù)組visited2，如果第j個頂點沒有被訪問過，則visited2[j]=0，否則visited2[j]=1。6.3實驗范例2、算法描述6.3.3范例3

根據(jù)以上分析，先設(shè)置一個訪問標志數(shù)組，然后從第v個頂點出發(fā)廣度優(yōu)先遍歷無向圖G。可設(shè)計廣度優(yōu)先遍歷函數(shù)BFSTraverse()如下：voidBFSTraverse(AMGraphG,intv)//以頂點v為起始頂點廣度優(yōu)先遍歷圖G{

intu,j;SqQueueQ;intvisited2[MAXVNUM]={0};

printf("%3c",G.vexs[v]);//訪問起始頂點

visited2[v]=1;//將起始頂點設(shè)值已訪問標志

InitQueue(Q);//初始化隊列

EnQueue(Q,v);//將被訪問頂點入隊6.3實驗范例2、算法描述6.3.3范例3

根據(jù)以上分析，先設(shè)置一個訪問標志數(shù)組，然后從第v個頂點出發(fā)廣度優(yōu)先遍歷無向圖G。可設(shè)計廣度優(yōu)先遍歷函數(shù)BFSTraverse()如下：while(!QueueEmpty(Q)){DeQueue(Q,u);//隊頭元素出隊for(j=0;j<G.vexNum;j++){//找到頂點u的沒有被訪問的鄰接點，訪問并入隊if(G.arcs[u][j]==1&&visited2[j]==0){printf("%3c",G.vexs[j]);visited2[j]=1;

EnQueue(Q,j);}

}

}}6.3實驗范例

前面三個函數(shù)加上隊列的基本操作，最后三個案例的源代碼如下：#include<stdio.h>#include<stdlib.h>#defineMAXVNUM100//最大頂點數(shù)#defineMAXQSIZE100#defineOK1#defineERROR0typedefcharVerTexType;typedefintArcType;typedefintStatus;//定義隊列typedefintQElemType;2、算法描述6.3.3范例3typedefstruct{QElemType*base;intfront;intrear;}SqQueue;6.3實驗范例

前面三個函數(shù)加上隊列的基本操作，最后三個案例的源代碼如下：2、算法描述6.3.3范例3//初始化隊列QStatusInitQueue(SqQueue&Q){Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));if(!Q.base)returnERROR;Q.front=0;Q.rear=0;returnOK;}//將元素e入隊QStatusEnQueue(SqQueue&Q,QElemTypee){if((Q.rear+1)%MAXQSIZE==Q.front)returnERROR;Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;returnOK;}6.3實驗范例

前面三個函數(shù)加上隊列的基本操作，最后三個案例的源代碼如下：2、算法描述6.3.3范例3//將隊列Q的對頭元素出隊，并用e返回出隊元素StatusDeQueue(SqQueue&Q,QElemType&e){if(Q.front==Q.rear)returnERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;returnOK;}//判斷隊列Q是否為空intQueueEmpty(SqQueueQ){if(Q.front==Q.rear)return1;elsereturn0;}6.3實驗范例

前面三個函數(shù)加上隊列的基本操作，最后三個案例的源代碼如下：2、算法描述6.3.3范例3//加上建立圖、深度優(yōu)先遍歷和廣度優(yōu)先遍歷三個函數(shù)的定義//主函數(shù)intmain(){AMGraphG;CreateUDG(G);printf("深度優(yōu)先遍歷序列為:");DFSTraverse(G,0);printf("\n");printf("廣度優(yōu)先遍歷序列為:");BFSTraverse(G,0);return0;}6.3實驗范例3、算法分析6.3.3范例3

采用鄰接矩陣存儲方式對圖進行廣度優(yōu)先遍歷時，查找一個頂點的鄰接頂點所需的時間為O(n)，需要對n個頂點的鄰接頂點進行查找，因此該時間復雜度為O(n2)。6.4實驗任務(wù)完成下列任務(wù)，并分析各算法的時間復雜度。任務(wù)1：用鄰接表作為圖的存儲結(jié)構(gòu)建立一個無向圖。任務(wù)2：在任務(wù)1建立的無向圖鄰接表的基礎(chǔ)上，對圖進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，輸出遍歷序列，并分析算法的時間復雜度。任務(wù)3（擴展題，選做）：用鄰接矩陣作為圖的存儲結(jié)構(gòu)建立一個連通網(wǎng)，并構(gòu)造該網(wǎng)的最小生成樹。6.4實驗任務(wù)完成下列任務(wù)，并分析各算法的時間復雜度。任務(wù)4（擴展題，選做）：校園導航系統(tǒng)。

用無向圖表示你所在學校的校園景點平面圖，圖中頂點表示主要景點，存放景點的編號、名稱、簡介等信息，圖中的邊表示景點間的道路，存放路徑長度等信息。要求實現(xiàn)如下功能：

①

查詢各景點的相關(guān)信息。

②

查詢圖中任意兩個景點間的最短路徑。

③

查詢圖中任意兩個景點間的所有路徑。6.5任務(wù)提示用鄰接表表示法創(chuàng)建無向圖步驟如下：

①輸入總頂點數(shù)和總邊數(shù)。

②依次輸入點的信息存入頂點表中，使每個表頭結(jié)點的指針域初

始化為NULL。

③創(chuàng)建鄰接表：

輸入邊，確定邊所依附的兩個頂點的序號i和j；

生成兩個邊表結(jié)點，將兩個結(jié)點的數(shù)據(jù)域存入j和i，并將這兩個邊表結(jié)點分別插入vi和vj對應(yīng)的兩個邊鏈表的頭部。任務(wù)1提示6.5任務(wù)提示偽代碼描述如下：任務(wù)1提示StatusCreateUDG(ALGraph&G){//輸入總頂點數(shù)，總邊數(shù)cin>>G.vexNum>>G.arcNum;//輸入各點，構(gòu)造表頭結(jié)點表for(i=0;i<G.vexNum;++i){cin>>G.vertices[i].data;//輸入頂點值G.vertices[i].firstarc=NULL;//初始化表頭結(jié)點的指針域為NULL}6.5任務(wù)提示偽代碼描述如下：任務(wù)1提示StatusCreateUDG(ALGraph&G){for(k=0;k<G.arcNum;++k){//輸入各邊，構(gòu)造鄰接表cin>>v1>>v2; //輸入一條邊依附的兩個頂點i=LocateVex(G,v1);

j=LocateVex(G,v2);//找到頂點在頂點表中的下標//生成一個新的邊結(jié)點*p1p1=newArcNode;p1->adjvex=j;//鄰接點序號為jp1->nextarc=G.vertices[i].firstarc;//將p1插入頂點vi的邊表頭部

G.vertices[i].firstarc=p1;6.5任務(wù)提示偽代碼描述如下：任務(wù)1提示StatusCreateUDG(ALGraph&G){for(k=0;k<G.arcNum;++k){//輸入各邊，構(gòu)造鄰接表//生成另一個對稱的新的邊結(jié)點*p2

p2=newArcNode;

p2->adjvex=i;//鄰接點序號為ip2->nextarc=G.vertices[j].firstarc;//將新結(jié)點*p2插入頂點vj的邊表頭部

G.vertices[j].firstarc=p2;}

returnOK;}6.5任務(wù)提示

基于鄰接表存儲方式的遍歷與基于鄰接矩陣存儲方式的遍歷在找鄰接點方式上有所不同。在鄰接表中，某個頂點的所有鄰接點存儲在該頂點對應(yīng)的邊表中，對邊表進行遍歷就可以找到頂點的所有鄰接點。任務(wù)2提示6.5任務(wù)提示基于鄰接表存儲方式深度優(yōu)先遍歷圖G的偽代碼描述如下：任務(wù)2提示voidDFS(ALGraphG,intv){//從第v個頂點出發(fā)對圖G進行深度優(yōu)先遍歷cout<<G.vertices[i].data;//訪問第v個頂點visited[v]=true;//設(shè)置已訪問標志

p=G.vertices[v].firstarc;//p指向v的邊鏈表的第一個邊結(jié)點while(p!=NULL)//依次檢查v的鄰接點{w=p->adjvex;//w是v的鄰接點//如果w未訪問，則遞歸調(diào)用DFSif(!visited[w])DFS(G,w); p=p->nextarc;//p指向下一個邊結(jié)點}}6.5任務(wù)提示基于鄰接表存儲方式廣度優(yōu)先遍歷圖G的偽代碼描述如下：任務(wù)2提示voidBFS(ALGraphG,intv)//從第v個頂點出發(fā)對圖G進行廣度優(yōu)先遍歷{

cout<<G.vertices[v].data;//訪問第v個頂點visited[v]=1;//設(shè)置已訪問標志InitQueue(Q);//初始化隊列QEnQueue(Q,v);//并將v入隊

while(!QueueEmpty(Q))//隊列非空

{DeQueue(Q,u);//隊頭元素出隊并賦給up=G.vertices[u].firstarc;//找到u的邊結(jié)點6.5任務(wù)提示基于鄰接表存儲方式廣度優(yōu)先遍歷圖G的偽代碼描述如下：任務(wù)2提示voidBFS(ALGraphG,intv)//從第v個頂點出發(fā)對圖G進行廣度優(yōu)先遍歷{while(p!=NULL){w=p->adjvex;if(visited[w]==0)//w為u的尚未訪問的鄰接頂點{cout<<G.vertices[w].data;//訪問第w個頂點visited[w]=1;//設(shè)置已訪問標志EnQueue(Q,w);//w進隊}p=p->nextarc;//找下一個鄰接點

}}}6.5任務(wù)提示

如果連通圖是一個網(wǎng)絡(luò)，生成樹的各邊權(quán)值之和稱為這棵生成樹的代價，稱該網(wǎng)絡(luò)所有生成樹中權(quán)值最小的生成樹為最小代價生成樹，簡稱為最小生成樹。常見的構(gòu)造最小生成樹的算法有普里姆（Prim）算法和克魯斯卡爾(Kruskal)算法。兩種算法都是利用MST性質(zhì)構(gòu)造最小生成樹的算法。任務(wù)3提示MST性質(zhì)：假設(shè)N=(V，E)是一個連通網(wǎng)，U是頂點集V的一個非空子集，若(u，v)是一條具有最小權(quán)值（代價）的邊，其中u∈U、v∈V-U，則必存在一棵包含邊(u，v)的最小生成樹。6.5任務(wù)提示

實現(xiàn)克魯斯卡爾(Kruskal)算法一般采用邊集數(shù)組形式存儲網(wǎng)，而不是鄰接矩陣方式存儲，所以本題采用Prim算法。任務(wù)3提示

普里姆（Prim）算法的基本思想：假設(shè)網(wǎng)G=（V，E）是連通的，T=（U，TE）為要構(gòu)造的一棵最小生成樹，其中U是G上最小生成樹頂點的集合，TE是G上最小生成樹中邊的集合。開始時U={u0}，TE={}。重復進行如下操作：在所有u∈U，v∈V-U的邊（u,v）∈E中，選擇一條權(quán)最小的邊（u,v）并入TE中，同時將v并入U，直到U=V為止。這時產(chǎn)生的TE中必有n-1條邊，T=（U，TE）是G的一棵最小生成樹。6.5任務(wù)提示算法實現(xiàn)過程中需引進一個數(shù)組closedge，其定義如下：struct//定義從頂點集U到V-U的權(quán)值最小的邊的輔助數(shù)組{ArcTypelowcost;//存放最小邊上的權(quán)值VerTexTypeadjvex;//最小邊在集合U中的頂點}closedge[MAXVNUM];任務(wù)3提示

數(shù)組中的兩個成員adjvex和lowcost，分別用于存放最小邊在集合U中的頂點和最小邊上的權(quán)值。6.5任務(wù)提示

所有的頂點closedge[i].adjvex都已在U中。任務(wù)3提示

若closedge[k].lowcost=0，則表示下標為k的頂點在U中；

若0＜closedge[k].lowcost＜∞，則下標為k的頂點在V-U中，且(closedge[k].adjvex,vex[k])是與頂點vex[k]鄰接的且兩鄰接頂點分別在U和V-U的所有邊中權(quán)值最小的邊，其最小權(quán)值就是closedge[k].lowcost；

若closedge[k].lowcost=∞，則表示closedge[k].adjvex與頂點vex[k]之間沒有邊，用∞表示。6.5任務(wù)提示任務(wù)3提示基于鄰接矩陣存儲和closedge數(shù)組的Prim算法的實現(xiàn)步驟如下：

①首先將初始頂點u加入U中，對其余的每一個頂點，將closedge中對應(yīng)的值初始化為該頂點到u的邊信息。

②循環(huán)vexNum－1次，做如下處理：從各組邊closedge中選出最小邊closedge[k]，輸出此邊；將k加入U中；更新剩余的每組最小邊信息closedge[j]，對于V－U中的邊，新增加了一條從k到j(luò)的邊，如果新邊的權(quán)值比closedge[j].lowcost小，則將closedge[j].lowcost更新為新邊的權(quán)值。6.5任務(wù)提示

可以采用鄰接矩陣的方式對圖進行存儲。需要查詢?nèi)我鈨蓚€景點的最短路徑，也就是圖中任何兩個頂點之間的最短路徑。求所有頂點之間的路徑可用Floyd算法。

可以基于深度優(yōu)先遍歷求任何兩個景點的所有路徑。任務(wù)4提示6.5任務(wù)提示（1）求所有頂點之間的最短路徑——Floyd算法任務(wù)4提示Floyd算法又稱為插點法，是一種利用動態(tài)規(guī)劃的思想尋找給定的加權(quán)圖中多源點之間最短路徑的算法，與Dijkstra算法類似。該算法名稱以創(chuàng)始人之一、1978年圖靈獎獲得者、斯坦福大學計算機科學系教授羅伯特·弗洛伊德命名。

通過一個圖的權(quán)值矩陣求出它的每兩點間的最短路徑矩陣。從圖的帶權(quán)鄰接矩陣A=[a(i,j)]n×n開始，迭代地進行n次更新，即由矩陣D(0)=A，按一個公式，構(gòu)造出矩陣D(1)；又用同樣地公式由D(1)構(gòu)造出D(2)；……；最后又用同樣的公式由D(n-1)構(gòu)造出矩陣D(n)。矩陣D(n)的i行j列元素便是i號頂點到j(luò)號頂點的最短路徑長度，稱D(n)為圖的距離矩陣，同時還可引入一個后繼節(jié)點矩陣path來記錄兩點間的最短路徑。6.5任務(wù)提示（1）求所有頂點之間的最短路徑——Floyd算法任務(wù)4提示

在實現(xiàn)過程中需要引入兩個輔助的二維數(shù)組：二維數(shù)組Path[i][j]，存儲最短路徑上頂點vj的前一頂點的序號；二維數(shù)組D[i][j]，記錄頂點vi和vj之間的最短路徑長度。6.5任務(wù)提示（1）求所有頂點之間的最短路徑——Floyd算法任務(wù)4提示算法步驟如下：

①將vi到vj的最短路徑長度初始化，即D[i][j]=G.arcs[i][j]。

②進行n次比較和更新。在vi和vj之間加入頂點v0，比較（vi，vj）和（vi，v0，vj）的路徑長度，取其中較短者作為vi到vj的中間頂點序號不大于0的最短路徑。6.5任務(wù)提示（1）求所有頂點之間的最短路徑——Floyd算法任務(wù)4提示算法步驟如下：在vi和vj之間加入頂點v1，得到（vi，…，v1）和（v1，…，vj），其中（vi，…，v1）是從vi到v1的且中間頂點序號不大于0的最短路徑，（v1，…，vj）是從v1到vj的且中間頂點的序號不大于0的最短路徑。這兩個路徑已經(jīng)在上一步求出。比較（vi，…，v1，…，vj）與上一步求出的vi到vj的中間頂點序號不大于0的的路徑長度，取其中較短者作為vi到vj的中間頂點序號不大于1的最短路徑。6.5任務(wù)提示（1）求所有頂點之間的最短路徑——Floyd算法任務(wù)4提示算法步驟如下：依次類推，在vi和vj之間加入頂點vk，得到（vi，…，vk）和（vk，…，vj），其中（vi，…，vk）是從vi到vk的且中間頂點序號不大于k-1的最短路徑，（vk，…，vj）是從vk到vj的且中間頂點的序號不大于k-1的最短路徑。將（vi，…，vk，…，vj）和已經(jīng)得到的從vi到vj的且中間頂點序號不大于k-1的的路徑相比較，其長度較短者便是vi到vj的中間頂點序號不大于k的最短路徑。經(jīng)過n次比較后，最后求得的必是從vi到vj的最短路徑。6.5任務(wù)提示（1）求所有頂點之間的最短路徑——Floyd算法任務(wù)4提示

圖中的所有頂點對vi和vj間的最短路徑長度對應(yīng)一個n階方陣D。在上述n+1步中，D的值不斷變化，對應(yīng)一個n階方陣序列。n階方陣序列可定義為：D(-1)，D(0)，D(1)，…，D(k)，…，D(n-1)

其中，D(-1)[i][j]=G.arcs[i][j]，D(k)[i][j]=min{D(k-1)[i][j]，D(k-1)[i][k]+D(k-1)[k][j]}0≤k≤n-1。

顯然，D(1)[i][j]是從vi到vj的且中間頂點的序號不大于1的最短路徑的長度；D(k)[i][j]是從vi到vj的且中間頂點的序號不大于k的最短路徑的長度；D(n-1)[i][j]就是從vi到vj的最短路徑的長度。6.5任務(wù)提示（1）求所有頂點之間的最短路徑——Floyd算法任務(wù)4提示算法的偽代碼描述如下：voidShortestPath_Floyd(AMGraphG){//所有頂點對初始化已知路徑長度和距離for(i=0;i<G.vertexNum,i++)for(j=0;j<G.vertexNum;j++){D[i][j]=G.arcs[i][j];//i和j之間有邊，則j的前驅(qū)為i，否則為-1if(D[i][j]<MAXINT&&i!=j)Path[i][j]=i;elsePath[i][j]=-1;

}for(k=0;k<G.vertexNum;k++)for(i=0;i<G.vertexNum;i++)for(j=0;j<G.vertexNum;j++)//找到i和j之間更短路徑，此路徑經(jīng)過kif(D[i][k]+D[k][j]<D[i][j]){D[i][j]=D[i][k]+D[k][j];//更新路徑Path[i][j]=Path[k][j];//修改前驅(qū)}}6.5任務(wù)提示（1）求所有頂點之間的最短路徑——Floyd算法任務(wù)4提示

該算法的時間復雜度為O(n3)。6.5任務(wù)提示（2）求無向圖中任意兩個頂點的所有路徑算法任務(wù)4提示

該法基于圖的深度優(yōu)先遍歷。實現(xiàn)過程中使用棧和標記數(shù)組為輔助。棧用來存儲正在搜索的路徑，棧底為源點。一個標記數(shù)組用來標記每一輪搜索過程中路徑上的頂點是否被訪問（或者表示是否在棧中，避免回路的產(chǎn)生）。6.5任務(wù)提示（2）求無向圖中任意兩個頂點的所有路徑算法任務(wù)4提示利用深度優(yōu)先搜索獲取兩點間所有簡單路徑的過程為：

給定一個無向網(wǎng)G的鄰接矩陣存儲方式，起始頂點v和目標頂點w。輔助棧S和輔助標記數(shù)組flag[]。開始時將v入棧S，并將v對應(yīng)標記改為已訪問標記。只要棧S不為空，獲得棧頂元素t，如果棧頂元素為目標頂點w，則找到一條頂點v到頂點w的路徑，其路徑就在棧S中，輸出棧S中的所有元素，并將該頂點出棧，同時設(shè)置未訪問標記，回溯到上一個頂點。6.5任務(wù)提示（2）求無向圖中任意兩個頂點的所有路徑算法任務(wù)4提示利用深度優(yōu)先搜索獲取兩點間所有簡單路徑的過程為：

如果棧頂元素不是目標頂點w，則找到v的一個未訪問的頂點i，以該頂點為起始頂點找到到目標頂點w的路徑。如果該頂點的所有鄰接點都找完，這時將該頂點出棧，同時設(shè)置未訪問標記，回溯到上一個頂點。當起始頂點的所有鄰接點都找完，棧為空，算法結(jié)束。6.5任務(wù)提示（2）求無向圖中任意兩個頂點的所有路徑算法任務(wù)4提示算法偽代碼描述如下：輔助棧S和輔助標記數(shù)組flag[MAXVNUM]。voidDFS_AllPath(AMGraphG,VerTexTypev,VerTexTypew){s1=LocateVex(G,v);//找到頂點v的下標Push(S,v);//將起始頂點入棧flag[s1]=1;//將其標記為已訪問標記，也就是在棧中while(StackEmpty(S)!=1)//棧不為空{(diào)GetTop(S,t);//獲得當前頂點s1=LocateVex(G,t);6.5任務(wù)提示（2）求無向圖中任意兩個頂點的所有路徑算法任務(wù)4提示算法偽代碼描述如下：輔助棧S和輔助標記數(shù)組flag[MAXVNUM]。voidDFS_AllPath(AMGraphG,VerTexTypev,VerTexTypew){s1=LocateVex(G,t);if(t==w)//找到目標結(jié)點{printf("找到一條路徑：");printStack(S);printf("\n");//將頂點出棧，并設(shè)為未訪問標志Pop(S,x);s2=LocateVex(G,x);flag[s2]=0;break;

}6.5任務(wù)提示（2）求無向圖中任意兩個頂點的所有路徑算法任務(wù)4提示算法偽代碼描述如下：輔助棧S和輔助標記數(shù)組flag[MAXVNUM]。voidDFS_AllPath(AMGraphG,VerTexTypev,VerTexTypew){else{for(i=0;i<G.vertexNum;i++){if(G.arcs[s1][i]!=MAXINT&&flag[i]==0)

{

//找到一個未訪問的鄰接點

DFS_AllPath(G,G.vex[i],w);

}

}6.5任務(wù)提示（2）求無向圖中任意兩個頂點的所有路徑算法任務(wù)4提示算法偽代碼描述如下：輔助棧S和輔助標記數(shù)組flag[MAXVNUM]。voidDFS_AllPath(AMGraphG,VerTexTypev,VerTexTypew){if(i==G.vertexNum)//當其所有鄰接點都訪問完{Pop(S,t);//將棧頂頂點出棧S2=LocateVex(G,t);flag[s2]=0;//設(shè)未訪問標記break;}}}}第7章

查找7.1知識簡介

在數(shù)據(jù)結(jié)構(gòu)中，查找是計算機科學中的一個重要概念和操作，它是指在一組預(yù)先組織好的數(shù)據(jù)集合（稱為查找表或查找結(jié)構(gòu)）中確定一個特定的數(shù)據(jù)元素（記錄或鍵值對）的過程。查找的目的通常是為了找到與給定關(guān)鍵字相匹配的數(shù)據(jù)元素。7.1.1查找1、查找表

查找表是由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合。由于“集合”中的數(shù)據(jù)元素之間存在著完全松散的關(guān)系，因此查找表是一種非常靈便的數(shù)據(jù)結(jié)構(gòu)，可以利用其他的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)，如線性表、樹表和散列表等。7.1知識簡介2、關(guān)鍵字

關(guān)鍵字是數(shù)據(jù)元素中的某個特定字段，用以區(qū)分不同的數(shù)據(jù)元素。主關(guān)鍵字通常是用來進行查找的主要依據(jù)，而次關(guān)鍵字則可以用于輔助排序或進一步細化搜索條件。7.1.1查找3、查找方法

按數(shù)據(jù)結(jié)構(gòu)組織方式可以分為：線性表的查找、樹表的查找和哈希表的查找。

線性表的查找：采用線性表作為查找表的組織形式，在線性表中查找指定元素主要方法有：順序查找、折半查找（也稱為二分查找，僅限于有序線性表）、分塊查找。7.1知識簡介7.1.1查找

樹表的查找：采用樹作為查找表的組織形式，查找操作主要依賴于樹的類型和特性，查找方法有：二叉排序樹（二叉查找樹）、B樹、AVL樹、紅黑樹等，根據(jù)結(jié)點的關(guān)鍵字值進行遞歸搜索。

哈希表的查找：哈希表（HashTable）是一種高效的數(shù)據(jù)結(jié)構(gòu)，它通過使用哈希函數(shù)將關(guān)鍵字映射到一個固定大小的數(shù)組中，從而實現(xiàn)快速查找、插入和刪除操作。4、查找性能指標

查找長度：查找過程中實際需要對比的關(guān)鍵字次數(shù)。

平均查找長度(ASL)：為了確定數(shù)據(jù)元素在查找表中的位置，需和給定值進行比較的關(guān)鍵字個數(shù)的期望值，稱為查找算法在查找成功時的平均查找長度。它是衡量查找算法效率的重要標準。7.1知識簡介

在線性表的查找中，順序查找既適用于線性表的順序存儲結(jié)構(gòu)，用適用于線性表的鏈式存儲結(jié)構(gòu)，折半查找要求線性表必須是順序存儲結(jié)構(gòu)，分塊查找的表可以是順序存儲結(jié)構(gòu)也可以是鏈式存儲結(jié)構(gòu)，但索引表必須是順序存儲結(jié)構(gòu)。7.1.2線性表的查找

查找表采用順序存儲結(jié)構(gòu)的數(shù)據(jù)描述為：//數(shù)據(jù)元素類型typedefstruct{KeyTypekey;//關(guān)鍵字域InfoTypeotherinfo;}ElemType;typedefstruct{ElemType*R;//存儲空間基地址intlength;//當前長度}SSTable;7.1知識簡介7.1.3樹表的查找

樹表的查找主要掌握二叉排序樹。二叉排序樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：若左子樹不空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值；若右子結(jié)不空，則右子樹上所有結(jié)點的值均大于根結(jié)點的值；左右子樹又分別是二叉排序樹。

采用二叉鏈表存儲結(jié)構(gòu)存儲二叉排序樹，二叉鏈表存儲表示如下：//數(shù)據(jù)元素類型typedefstruct{KeyTypekey;//關(guān)鍵字項InfoTypeotherinfo;//其他數(shù)據(jù)項}ElemType;typedefstructBSTNode{ElemTypedata;structBSTNode*lchild;//左孩子指針

structBSTNode*rchild;//右孩子指針}BSTNode,*BSTree;7.2實驗?zāi)康?/p>

通過本章的實驗，深刻理解基于不同查找結(jié)構(gòu)的查找技術(shù)，在實際應(yīng)用中能夠靈活選擇或設(shè)計合適的查找方法，同時鍛煉學生實際編程和算法設(shè)計的能力。7.3實驗范例學號姓名性別大學英語高等數(shù)學2023001AlanF93882023002DanieM75692023003PeterM56772023004BillF87902023005HelenM79862023006AmyF6875一個班有50個學生，每個學生的信息有學號、姓名、性別、大學英語成績和高等數(shù)學成績，學生信息如下表所示。要求根據(jù)輸入的學號查找學生的信息。7.3實驗范例

順序查找（設(shè)置監(jiān)視哨）：根據(jù)輸入的n個學生的信息，建立順序表，并在順序表中用順序查找方法（帶監(jiān)視哨）查找與輸入的學號相同的學生信息，輸出該學生的所有信息。7.3.1范例17.3實驗范例1、問題分析7.3.1范例1

先需要定義順序表，順序表中每個元素用來存儲一個學生的信息，需要定義結(jié)構(gòu)體類型，數(shù)據(jù)元素的類型就是結(jié)構(gòu)體類型。

然后初始化順序表，分配能放MAXSIZE+1學生信息的空間（下標為0的單元用來存放哨兵），將順序表的長度初始化為0。

接著建立長度為n的順序表，輸入n個學生信息，將學生信息存入順序表中。這個過程和實驗一的過程相同。輸入需要查找學生的學號，利用順序查找在順序表中查找和給定學號相同的學生。7.3實驗范例1、問題分析7.3.1范例1

順序查找（帶監(jiān)視哨）操作的基本步驟：

先將帶查找的關(guān)鍵字的值存入監(jiān)視哨中，監(jiān)視哨可設(shè)置在表頭，也可設(shè)置在表尾，這里我們將其設(shè)置在表頭。

接著從表中最后一個元素開始，逆序掃描查找表，依次將掃描到的元素的學號與所給學號進行比較，相等，返回該元素的下標。由于將待查找的學號放在下標為0的位置，如果元素不存在，當比較到監(jiān)視哨時兩個學號相等，返回0，表示查找失敗。

由于順序表中的數(shù)據(jù)元素包含多個數(shù)據(jù)，輸入一個學生信息和輸出一個學生信息分別定義兩個函數(shù)來實現(xiàn)。7.3實驗范例2、算法描述7.3.1范例1先定義順序查找表SSTable，定義如下：//數(shù)據(jù)元素類型typedefstructStudent{charNo[8];//學號charname[16];//姓名charsex;//性別intenglish;//大學英語成績intmath;//高等數(shù)學成績}ElemType;//順序查找表typedefstruct{ElemType*R;//存儲空間基地址intlength;//當前長度}SSTable;7.3實驗范例2、算法描述7.3.1范例1

順序查找表類型定義好之后，可以初始化查找表ST。先新申請能存儲MAXSIZE+1個ElemType型數(shù)據(jù)的空間（下標為0的單元用來存放哨兵），然后將查找表ST的初始長度length設(shè)置為0。初始化查找表的函數(shù)可以定義如下：voidInitList(SSTable&ST){

//分配內(nèi)存單元，下標為0的位置放哨兵

ST.R=(ElemType*)malloc((MAXSIZE+1)*sizeof(ElemType));

if(!ST.R)

exit(0);

ST.length=0;}7.3實驗范例2、算法描述7.3.1范例1

接著設(shè)計函數(shù)用來建立長度為n的查找表ST，輸入n個學生信息存入查找表ST中，將查找表當前長度length設(shè)置為n。在定義該函數(shù)之前定義函數(shù)用來輸入一個學生信息。輸入一個學生信息的函數(shù)定義如下：voidInputOneStu(ElemType&stu){fflush(stdin);//清空輸入緩沖區(qū)printf("學號:");gets(stu.No);fflush(stdin);printf("姓名:");fflush(stdin);gets();printf("性別：");scanf("%c",&stu.sex);printf("大學英語成績：");scanf("%d",&stu.english);printf("高等數(shù)學成績：");scanf("%d",&stu.math);}7.3實驗范例2、算法描述7.3.1范例1

在建立長度為n的查找表函數(shù)中循環(huán)n次調(diào)用函數(shù)InputOneStu()用來輸入n個學生信息，函數(shù)可以定義如下：voidCreateSSTable(SSTable&ST,intn){inti;printf("輸入%d個學生信息：\n",n);for(i=1;i<=n;i++){InputOneStu(ST.R[i]);}ST.length=n;}7.3實驗范例2、算法描述7.3.1范例1

設(shè)計查找函數(shù)，在查找表ST中查找學號等于stdNo的元素，找到則返回該元素的序號，否則返回0。函數(shù)可以定義如下：intSearch_Seq(SSTable&ST,char*stdNo){inti;strcpy(ST.R[0].No,stdNo);//設(shè)置哨兵for(i=ST.length;strcmp(ST.R[i].No,stdNo)!=0;i--);returni;}7.3實驗范例2、算法描述7.3.1范例1

定義函數(shù)PrintStuInfo(Studentstu)實現(xiàn)輸出一個學生的信息。函數(shù)可以定義如下：voidPrintStuInfo(Studentstu){printf("學號：%s\n",stu.No);printf("姓名：%s\n",);printf("性別：%c\n",stu.sex);printf("大學英語成績：%d\n",stu.english);printf("高等數(shù)學成績：%d\n",stu.math);}7.3實驗范例2、算法描述7.3.1范例1

在main()函數(shù)中定義查找表L，然后調(diào)用InitList()函數(shù)對查找表L進行初始化，接著調(diào)用CreateSSTable()函數(shù)將n個學生信息存入查找表中，輸入待查找的學號存入stdNo字符數(shù)組中，調(diào)用Search_Seq()函數(shù)在L中查找學號等于stdNo的學生，并返回其下標。如果返回值不等于0，表示該學號的學生存在，輸出該學生的所有信息。如果等于0，表示該學號的學生不存在。7.3實驗范例2、算法描述7.3.1范例1#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMAXSIZE100//在main()之前加入類型定義和函數(shù)定義intmain(){intm,stdPos;charstdNo[8];SSTableL;InitList(L);printf("---------順序查找---------\n");printf("請輸入順序表的長度:");scanf("%d",&m);CreateSSTable(L,m);7.3實驗范例2、算法描述7.3.1范例1printf("請輸入需要查找的學生學號：");fflush(stdin);scanf("%s",stdNo);stdPos=Search_Seq(L,stdNo);if(stdPos!=0){printf("存在學號為%s的學生，該學生信息如下\n",stdNo);PrintStuInfo(L.R[stdPos]);}else{printf("不存在學號為%s的學生！\n",stdNo);}return0;}7.3實驗范例3、算法分析7.3.1范例1

按值查找操作時間主要耗費在比較元素上，而比較的次數(shù)取決于被查元素在表中的位置，平均比較次數(shù)為(n+1)/2，時間復雜度為O(n)。通過設(shè)置監(jiān)視哨，當順序表長度大于1000時，進行一次查找所需的平均時間比普通算法的時間幾乎減少一半。7.3實驗范例

二分查找（遞歸算法）：假設(shè)范例1中的順序表已按照學號遞增有序，用二分查找方法在該順序表中查找與給定學號相等的學生信息，并輸出該學生的所有信息。7.3.2范例27.3實驗范例1、問題分析7.3.2范例2

能使用二分查找的前提是待查找表是有序的，而且是順序存儲方式。在任務(wù)1所建的查找表基礎(chǔ)上用二分查找查找，在建立查找表時按學號從小到大的順序輸入學生信息。二分查找是從表的中間元素開始查找，如果給定值和中間元素的關(guān)鍵字值相等，則查找成功；如果給定值大于或小于中間元素的關(guān)鍵字值，則在表中大于或小于中間元素的那一半中查找，重復操作，直到找到或者在某步中查找區(qū)間為空，則查找失敗。7.3實驗范例1、問題分析7.3.2范例2

假設(shè)待查找表ST中元素的起止元素下標為low和high，查找關(guān)鍵字值為key的元素的步驟為：

（1）判斷l(xiāng)ow是否大于high，是則返回-1，查找結(jié)束；

（2）否則，計算中間元素的下標mid，mid=(low+high)/2，將下標為mid的元素的關(guān)鍵字值和key進行比較：

如果key和下標為mid的元素關(guān)鍵字的值相等，返回mid；

如果key小于下標為mid的元素關(guān)鍵字的值，則在下標為low和mid-1之間的元素中繼續(xù)查找；

如果key大于下標為mid的元素關(guān)鍵字的值，則在下標為mid+1和high之間的元素中繼續(xù)查找。7.3實驗范例1、問題分析7.3.2范例2

本范例中需要查找和給定學號相同的學生信息，所以key