交大學(xué)位考輔導(dǎo)課件3教材

主要內(nèi)容：1.圖2.查找、排序數(shù)據(jù)結(jié)構(gòu)學(xué)位考

復(fù)習(xí)課(3)

第七章圖考核內(nèi)容及要求：熟練掌握圖的相關(guān)概念、性質(zhì)、存儲結(jié)構(gòu)熟練掌握遍歷：深度優(yōu)先遍歷、廣度優(yōu)先遍歷過程；熟練掌握連通分量的求法；熟練掌握最小生成樹、最短路徑概念與方法；掌握拓撲排序、關(guān)鍵路徑的求法及實現(xiàn)方法。1圖的定義、術(shù)語和存儲結(jié)構(gòu)圖：圖結(jié)構(gòu)中，任意兩個結(jié)點之間的關(guān)系是任意的，圖中任意兩個數(shù)據(jù)元素之間都可能相關(guān)圖的抽象數(shù)據(jù)類型頂點、弧、邊有向圖（digraph)有向圖G1=(V1,{A1})，其中V1={v1,v2,v3,v4},A1={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}無向圖(undigraph)無向圖G2=(V2,{E2}) V2={v1,v2,v3,v4,v5},E2={(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}V1V2V3V4V1V2V4V5V3有向圖無向圖頂點數(shù)n和邊(弧)的數(shù)目e：無向圖：有向圖：

完全圖：有n(n-1)/2條邊的無向圖;

有向完全圖：有n(n-1)條弧的有向圖;

稀疏圖、稠密圖子圖：G=(V,{E}),G’=(V’,{E’})，若V’V,且E’E,則稱G’為G的子圖鄰接點：無向圖中，(v,v’)∈E，則v,v’互為鄰接點； 頂點v的度：與v相關(guān)聯(lián)的邊的數(shù)目，TD(v)有向圖中,若<v,v’>∈A，則頂點v鄰接到頂點v’，而頂點v’鄰接自v出度：以v為尾的弧的數(shù)目，OD(v)入度：以v為頭的弧的數(shù)目，ID(v)TD(v)=OD(v)+ID(v)路徑：回路（環(huán)）簡單路徑：頂點序列中頂點不重復(fù)的路徑。連通圖、連通分量、強連通圖、強連通分量：ABLMCDEFGHHIJKABLMCFJDEGHHIK一個連通圖的生成樹：一個極小連通子圖，含有圖中全部結(jié)點，但只有足以構(gòu)成一棵樹的n-1條邊。一棵有n個頂點的生成樹有且僅有n-1條邊但有n-1條邊的圖不一定是生成樹有向圖：如果有一個頂點的入度為0，其余頂點的入度都為1，則是一棵有向樹。ABLMCFJ

圖的存儲結(jié)構(gòu)

數(shù)組表示法（鄰接矩陣）：

用兩個數(shù)組分別存放頂點信息和邊（弧）信息G1.VEXS[4]=[V1V2V3V4]G1.arcs=0110000000011000V1V2V3V4G1V1V2V4V5V3G2G2.arcs=0101010101010111010001100

圖的鄰接矩陣

A[i][j]=1//若<vi,vj>存在

A[i][j]=0//若<vi,vj>不存在無向圖：第i行分量的和為結(jié)點vi的度有向圖：第i行分量的和為結(jié)點vi的出度； 第i列分量的和為結(jié)點vi的入度網(wǎng)的鄰接矩陣

A[i][j]=無窮大<vi,vj>間無邊

=權(quán)<vi,vj>間有邊問題：為什么放無窮大而不放0

鄰接表：一種鏈式存儲結(jié)構(gòu)為圖中的每一個頂點創(chuàng)建一個單鏈表，其中的結(jié)點表示依附于頂點的邊(以該頂點為尾的弧)adjvexnextarcinfo表結(jié)點datafirstarc頭結(jié)點V1V2V3V4v1v2v3v4012321^^3^0^無向圖的鄰接表中，頂點v的度就是該頂點的單鏈表中的結(jié)點數(shù)；有向圖中，第i個鏈表的結(jié)點數(shù)是該頂點的出度；如何求有向圖中頂點的入度？——有向圖的逆鄰接表。v1v2v3v4012321^^3^0^v1v2v3v4012330^0^2^^有向圖G1的鄰接表有向圖G1的逆鄰接表V1V2V3V4v1v2v3v401231^020220233031232^^^^^^^

十字鏈表：有向圖的鏈式存儲datafirstinfirstout頂點結(jié)點tailvexheadvexhlinktlinkinfo弧結(jié)點鄰接多重表：無向圖的另一種鏈式存儲結(jié)構(gòu)。V1V2V4V5V3V1V2V3V4V501234012141032324^^^^^2.圖的遍歷圖的遍歷目標是解決圖的連通性問題、拓撲排序問題、關(guān)鍵路徑問題。圖的遍歷方法：深度優(yōu)先算法、廣度優(yōu)先算法深度優(yōu)先遍歷深度優(yōu)先搜索遍歷：類似于樹的先根遍歷，是樹的先根遍歷的推廣算法：

1.假設(shè)圖中所有頂點的初始狀態(tài)為：未訪問；

2.從圖中某個未訪問的頂點v出發(fā)，訪問此結(jié)點；

3.依次從v的鄰接點出發(fā)深度優(yōu)先遍歷圖，直到圖中所有與v有路徑的頂點都被訪問到；

4.若圖中還有未訪問結(jié)點，則另選一個結(jié)點作起始點，重復(fù)2、3過程。v1V2v6v4v5v8v3v7v1V2v6v4v5v8v3v7圖解深度優(yōu)先遍歷過程一個非連同圖的深度優(yōu)先遍歷過程圖解ABLMCDEFGHHIJKHABLMCDEFGHIJK可能的遍歷序列：ALMJBFCDEGIHK注：圖的存儲結(jié)構(gòu)沒有給定的情況下，圖的遍歷序列不是唯一的。廣度優(yōu)先遍歷廣度優(yōu)先搜索遍歷類似于樹的層次遍歷算法v1V2v6v4v5v8v3v7v1V2v6v4v5v8v3v7一個非連同圖的廣度優(yōu)先遍歷過程圖解ABLMCDEFGHHIJKHABLMCDEFGHIJK可能的遍歷序列：ALFCBMDEGIHK

3.圖的連通性問題——掌握連通分量的求法無向圖的連通分量和生成樹由圖的遍歷得出：對于連通圖，從圖中任一頂點出發(fā)，可以訪問到圖中的所有頂點；對于非連通圖，需要從多個頂點出發(fā)，搜索到樹的各個連通分量中的頂點集。ABLMCDEFGHHIJKHABLMCDEFGHIJK4掌握最小生成樹的概念和求法最小生成樹構(gòu)造連通網(wǎng)的最小代價生成樹。MST性質(zhì)：假設(shè)N=(V,{E})是一個連通網(wǎng)，U是頂點集V上的一個非空子集。若(u,v)是一條具有最小權(quán)值的邊，其中u∈U，v∈V-U,則必存在一棵包含邊(u,v)的最小生成樹。構(gòu)造最小生成樹的算法：Prin算法和Kruskal算法。Prim算法構(gòu)造最小生成樹的過程：V1V2V3V4V5V6V1V2V3V4V5V66512556643V1V2V3V4V5V6V1V2V3V4V5V6V1V2V3V4V5V6V1V2V3V4V5V6Kruskal算法構(gòu)造最小生成樹的過程V1V2V3V4V5V6V1V2V3V4V5V6V1V2V3V4V5V6V1V2V3V4V5V6V1V2V3V4V5V6V1V2V3V4V5V66512556643兩種算法的區(qū)別：普魯姆算法：基于連通地選擇，避免回路克魯斯卡兒算法：離散地選擇，避免回路拓撲排序：由某個集合上的一個偏序得到該集合上的一個全序，就是拓撲排序。偏序：集合中僅有部分成員之間可以比較；全序：集合中全體成員之間均可比較。AOV網(wǎng)：頂點表示活動，弧表示活動之間的優(yōu)先關(guān)系的有向圖稱為頂點表示活動的網(wǎng)。v1v2v3v4v1v2v3v4偏序全序5拓撲排序進行拓撲排序的方法：在有向圖中選一個沒有前驅(qū)的頂點且輸出；從圖中刪除該結(jié)點和所有以該結(jié)點為尾的弧。重復(fù)上述操作。若可以輸出全部頂點，則該圖中不存在環(huán)，否則存在環(huán)。例如：算法實現(xiàn)：以鄰接表的方法存儲有向圖；頭結(jié)點增加信息：頂點入度；增加一個棧：存放入度為0的頂點。v1v2v3v46最短路徑7.6.1從某個源點到其余各頂點的最短路徑Dijkstra算法：按路徑長度遞增的次序產(chǎn)生最短路徑D[i]表示當前所找到的從點v到每個終點vi的最短路徑的長度。

D[i]初值：v到vi的弧的權(quán)值；則： 初值最小的路徑就是從v出發(fā)的最短的一條路徑下面按照長度遞增多次序產(chǎn)生各個終點的最短路徑v1v2v3v4v0v51005060201030105Dijkstra算法求最短路徑終點從v0到各終點的D值和最短路徑的求解過程i=1i=2i=3i=4i=5v1∞∞∞∞無v210(v0,v2)v3∞60(v0,v2,v3)50(v0,v4,v3)v430(v0,v4)30(v0,v4)v5100(v0,v5)100(v0,v5)90(v0,v4,v5)60(v0,v4,v3,v5)vjv2v4v3S{v0,v2}v1v2v3v4v0v51005060201030105查找考核內(nèi)容及要求：熟練掌握順序查找、有序表的查找、索引順序查找、二分查找法及HASHING查找技術(shù)；了解平衡二叉樹、B樹及B+樹的概念；理解查找速度的分析及比較、算法復(fù)雜性的級別。1順序表的查找物理存儲：順序表方式：

typedef

struct{

ElemType

*elem;

int

length;}SSTable查找過程：從表中最后一個元素開始，逐個比較，相等則比較成功，否則直到第一個元素。Int

Search_Seq(SSTable

ST,KeyType

key){//從尾部依次比較key和數(shù)據(jù)元素的關(guān)鍵字，

//當比到0下標才成功則查找不成功，返回0//否則返回下標iST.elem[0].key=key;for(i=ST.length;!EQ(ST.elem[i].key,key);--i);returni;}//Search-Seq0下標為監(jiān)視哨,時間復(fù)雜度O(n)平均查找長度：ASL=sum(pici)i=1…n查找成功：pi=1/nci=1,2,3…nASL=1/n[1+2+…+n]=(n+1)/2查找不成功：ASL=n+1,(n,n-1…1,0)成功和不成功同概率：1/2

ASL=?*1/n[1+2+…+n]+1/2(n+1)=?(n+1)折半查找：先確定待查記錄的范圍，逐步縮小范圍直到找到或找不到。例：在下列數(shù)據(jù)元素中查找關(guān)鍵字為21和85的數(shù)據(jù)元素分析：設(shè)置兩個指針low,high指示待查元素所在范圍的上界和下界。mid＝（low+high）/2ST.elem[mid].key=key:查找成功ST.elem[mid].key<key：low=mid+1ST.elem[mid].key>key:high=mid-1low=high:查找不成功2有序表的查找513192137566475808893lowhighmidintSearch_Bin(SSTable

ST,KeyTable

key){//對有序表的查找采用折半查找，逐步縮小

//查找范圍，直到找到或找不到，返回值為

//找到返回下標，找不到返回0

low=1;high=ST.length;while(low<=high){mid=(low+high)/2;ifEQ(key,ST.elem[mid].key)returnmid;elseifLT(key,ST.elem[mid].key)

high=mid–1;elselow=mid+1;}returnOK;}//Search_Bin

時間復(fù)雜度：O(log2n),ASL=log2(n+1)+1(按照滿二叉樹)分塊查找，索引順序查找分塊有序兩步查找：確定待查記錄所在地子表（塊）；在子表中順序查找3索引順序表的查找221213892033424438244860587449865322121389203342443824486058744986532212138920334244382448605874498653488617134.動態(tài)查找表——二叉排序樹例已知如下長度為8的表，試按表中元素的順序依次插入一棵初始為空的二叉排序樹，畫出插入完成后的二叉排序樹，并求其在等概率下查找成功的平均查找長度。（Mon,Tiger,Win,Butter,Fish,Fly,Pig,Cat)平衡二叉樹平衡因子：左子深度減去右子深度為–1，0，1的二叉排序樹。二叉平衡樹的構(gòu)造（單項左旋/單項右旋），

（左右旋，右左旋）2－22－2右旋左旋左右旋右左旋9.3哈希表確定的對應(yīng)關(guān)系f：記錄的存儲位置關(guān)鍵字對應(yīng)關(guān)系f就是哈希函數(shù)：f(K)哈希函數(shù)是一個映象，構(gòu)造哈希函數(shù)的方法：直接定址法；哈希地址：直接取關(guān)鍵字或者關(guān)鍵字的線性函數(shù)H(key)=key;orH(key)=a*key+b數(shù)字分析法；分析關(guān)鍵字，取關(guān)鍵字的若干數(shù)位組成哈希地址。平方取中法；取關(guān)鍵字平方后的中間幾位為哈希地址——較為常用的方法折疊法：分割關(guān)鍵字、疊加除留余數(shù)法：H(key)=keyMODpp<=哈希表長m沖突現(xiàn)象：當K1≠K2時f(K1)=f(K2)解決沖突的方法開放定址法；Hi=(H(key)+di)MODmi=1,2,···k(k<=m-1)m為哈希表長度；di為增量,di的取法：(1)線性探測再散列；di=1,2,3,···(2)二次探測再散列；di=±k2(3)偽隨機探測再散列：di=偽隨機數(shù)序列再哈希：Hi=RHi(key)鏈地址：所有關(guān)鍵字為同義詞的記錄存儲在同一線性鏈表中公共溢出區(qū)：發(fā)生沖突時填入溢出表。排序考核要求：熟練掌握插入排序、快速排序、堆及選擇排序、歸并排序、基數(shù)排序法；了解最好、最壞、平均排序的時間復(fù)雜性分析方法。插入排序的思想：將一個元素插入到一個有序表中。 根據(jù)尋找插入位置的方法不同分為：直接插入、折半插入、2路插入、表插入等。直接插入排序：最簡單的排序方法思想：將一個元素向一個有序序列插入做法：0位監(jiān)測哨，從一個元素逐步擴大有序序列。舉例1插入排序49386597761327490直接插入排序算法：voidInsertSort(SqList&L){//對順序表L作直接插入排序

for(i=2;i<L.length;++i) if(L.r[i].key<L.r[i-1].key){ L.r[0]=L.r[i]; L.r[i]=L.r[i-1]; for(j=i-2;L[0].key<L[j].key;--j) L.r[j+1]=L.r[j]; L.r[j+1]=L.r[0]; }}折半插入排序查找過程用折半查找方法。

voidBInsertSort(SqList&L){for(i=2;i<=L.length;++i){ L.r[0]=L.r[i]; low=1;high=i-1; while(low<=high){ m=(low+high)/2; if(L.r[0].key<L.[m].key)high=m-1; elselow=m+1; }//while for(j=i-1;j<=high+1;--j)L.r[j+1]=L.r[j]; L.r[high+1]=L.r[0]; }//for}//BInsertSort49386597761327490算法思想：先將整個待排序記錄分割成若干個子序列分別進行直接插入排序，待整個序列中的記錄基本有序時，再進行一次全體記錄的插入排序。具體操作：49386597761327495504491338276549760413274955044938659776

1355387627046549

4997第一次分組這就是第一趟排序結(jié)果第二趟的“增量”就要縮小了！2希爾排序：縮小增量排序，屬于插入排序希爾排序算法:voidShellInsert(SqList&L,int

dk){//對順序表L作一趟希爾排序。

for(i=dk+1;i<=L.length;++i) if(L.r[i].key<L.r[i-dk].key){ L.r[0]=L.r[i]; for(j=k-dkl;j>0&L.r[0].key<L.r[j].key;j-=dk)

L.r[j+dk]=L.r[j];

L.r[j+dk]=L.r[0]; }}//shelinsertvoidShellSort(SqList&L,int

dlta[],intt){//按增量序列dlta[0..t-1]對順序表L作希爾排序

for(k=0;k<t;++k)ShellInsert(L,dlta[k]);}3快速排序冒泡排序：具體做法：依次比較第i個關(guān)鍵字和第i+1個關(guān)鍵字，大者排后，一趟得到最大值。（i=1,2,3,4,---n-1)493865977613274938496597761327493849657697132749384965761397274938496576132797

4938496576132749

97冒泡排序算法voidBubbleSort(SqList&L){ for(k=L.length-1;k>=1;k--) for(i=0;i<=k-1;k++) if(L.r[i].key>L.r[i+1].key){交換兩個記錄}}時間復(fù)雜度：O(n2)4938659776132749lowhigh273865977613

49lowhigh2738139776

6549lowhigh2738

9776136549lowhigh273813

7697

6549lowhigh快速排序的算法快速排序算法：IntPartition(SqList&L,int

low,inthigh){ L.r[0]=L.r[low];

pivotkey=L.r[low].key; while(low<high){ while(low<high&&L.r[high].key>=pivotkey)--high; L.r[low]=L.r[high]; while(low<high&&L.r[low].key<=pivotkey)++low; L.r[high]=L.r[low]; } L.r[low]=L.r[0]; returnlow;}//平均時間：K為常數(shù)因子。就平均時間而言快速排序是目前被認為最好的一種內(nèi)部排序方法。4選擇排序選擇排序基本思想：每一趟在n-i+1(i=1,2,···,n-1)個記錄中選取關(guān)鍵字最小的記錄作為有序序列中第i個記錄。簡單選擇排序：VoidSelectSort(SqList&L){for(i=1;i<L.length;++i){ j=SelectMinKey(L,i);//從L.r[i..L.length]中選擇key最小的記錄

if(i!=j)L.r[i]L.r[j]; }}堆排序堆的定義：n個元素的序列{k1,k2,,kn}當且僅當滿足下列關(guān)系時，稱為堆：思想：每趟選取最小關(guān)鍵字、次小關(guān)鍵字、次次小關(guān)鍵字---。做法：建立一個完全二叉樹，任何非終端結(jié)點的值均不大于其左、右孩子結(jié)點的值。輸出堆頂，將其余的元素建立新的堆。ki≤k2iki≤k2i+1ki≥k2iki≥k2i+1493865977613274997493865271376494949386527137697493865497613279749381349766527974938

1349766527974949381327657697491338276576975歸并排序思想：將兩個或兩個以上的有序表組合成一個新的有序表。具體做法：以兩路歸并示例[49][38][65][97][76][13][27]

n個記錄看成n個有序的序列[3849][6597][1376][27]

第一趟合并[38496597][132776]

[13273849657697]

第二趟合并第三趟合并外部排序考核要求：了解外存及分類技術(shù)簡介了解緩沖區(qū)管理、初始合并串、置換選擇分類技術(shù)、勝者樹及敗者樹3.置換-選擇排序 目標：減少m(初始歸并段的個數(shù))來減少歸并趟數(shù)。

m=upper(n/l),n為外部文件中記錄數(shù)，

l為每段記錄數(shù)目。故增大l,l受內(nèi)存空間限制置換-選擇排序：在得到所有初始歸并段的過程中，選擇最?。ù螅╆P(guān)鍵字和輸入、輸出交叉或同時進行。外部排序方法：思想：分段讀入內(nèi)存、排序；分段寫入外存、有序段歸并。

已知圖G的鄰接表如下圖所示，從其頂點V1出發(fā)的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列分別寫出來，并按圖中給出的存儲結(jié)構(gòu)給出深度優(yōu)先生成樹和廣度優(yōu)先生成樹。V1V2V3V4V5V6413425352典型例題——圖、查找、排序7.5已知以二維數(shù)組表示的圖的鄰接矩陣如下，分別畫出自頂點1出發(fā)進行遍歷得到的深度優(yōu)先和廣度優(yōu)先生成樹12345678910

000000101000100