第7章-數(shù)據(jù)結(jié)構(gòu)與算法

數(shù)據(jù)結(jié)構(gòu)與算信電學(xué)院計(jì)算機(jī) 1提概線性樹圖排遞歸與分治小2提概線性樹圖排遞歸與分治小3概數(shù)據(jù)算法一般算法分析從時(shí)間角度考慮的比數(shù)據(jù)結(jié)構(gòu)與算法組織大量數(shù)據(jù)的方法和對算法運(yùn)行時(shí)4提概線性樹圖排遞歸與分治小5線性表的基本線性表中的數(shù)據(jù)元素是有序且是有限在這種結(jié)構(gòu)存在一個(gè)唯一的被稱為“第一個(gè)”的數(shù)據(jù)元6線性表的邏輯線性表的定線性表(LinearList)：是由n(n≧0)個(gè)數(shù)據(jù)元素(結(jié)點(diǎn))a1，a2…an組成的有限序列。該序列中當(dāng)n=0時(shí)，稱為空表當(dāng)n>0時(shí)，將非空的線性表記作：7線性表的邏輯結(jié)構(gòu)（續(xù)a1，a2，…ai-1都是ai(2≦i≦n)的前驅(qū)，其中ai-是ai的直接前驅(qū)ai+1，ai+2，…an都是ai(1≦i≦n-1)的后繼，其ai+1是ai的直接后繼一個(gè)數(shù)據(jù)項(xiàng))。例1:26個(gè)英文字母組成的字母表：(A…、8線性表的邏輯結(jié)構(gòu)（續(xù)例3的點(diǎn)數(shù)元素含有多個(gè)數(shù)據(jù)項(xiàng)，每個(gè)項(xiàng)稱為結(jié)點(diǎn)的例4：某校2015 ’06/24/1983)， ’，‘男’，08/12/1984)9線性表的邏輯結(jié)構(gòu)（續(xù)若線性表中的結(jié)點(diǎn)是按值(或按關(guān)鍵字值)小到大(或由大到小)排列的，稱線性表是有的線性表是一種相當(dāng)靈活的度可根據(jù)需要增長或縮短 ADT數(shù)據(jù)對象：Dai|ai∈ElemSet,i=1,2,…,nn≧0數(shù)據(jù)關(guān)系：R={<ai-1,ai>|ai-1,ai∈D,i=2,3,…,nInitList(&L操作結(jié)果：構(gòu)造一個(gè)空的線性表ListEmpty(L初始條件：線性表L已存 操作結(jié)果：L為空，返回TRUE，否則返回線性表的抽象數(shù)據(jù)類型定義（續(xù) em(L,i,&eListInsert(L,i,&e) …}ADT線性表的順順序：把線性表的結(jié)點(diǎn)按邏輯順序依次存放在一組地址連續(xù)的單元里。用這種方法的線性表簡稱順序表。順序的線性表的特點(diǎn)線性表的邏輯順序與物理順序一致 數(shù)據(jù)元間的關(guān)系是以元素在計(jì)算機(jī)內(nèi)“物線性表的順 （續(xù)設(shè)有非空的線性表：(a1，a2，…an)。順序 ……a…a線性表的順 表線性表的順 （續(xù)在具體的機(jī)器環(huán) 線性表的第i個(gè)數(shù)據(jù)元素ai 位置為線性表的順 （續(xù)在高級語言(如C數(shù)組具有隨機(jī)存取的特性，因此，借助數(shù)組述順序表 線性表的順 （續(xù)#define #define -#defineMAX_SIZE100typedefintStatus;typedefintElemType;typedefstructsqlist ElemTypeElem_array[MAX_SIZE]; length;}SqList線性表的鏈 結(jié)鏈用一組任意的單元線性表中的數(shù)據(jù)元素。用這種方法的線性表簡稱線性鏈表。 鏈表中結(jié)點(diǎn)的一組任意的單元可以是鏈表中結(jié)點(diǎn)的邏輯順序和物理順序線性表的鏈 結(jié)構(gòu)（續(xù) data：數(shù)據(jù)域，存放結(jié)點(diǎn)的值next：指針域，存放結(jié)點(diǎn)的直接后繼鏈表是通過每個(gè)結(jié)點(diǎn)的指針域?qū)⒕€性表的n個(gè)點(diǎn)按其邏輯次 在一起的線性表的鏈 結(jié)構(gòu)（續(xù)每一個(gè)結(jié)點(diǎn)只包含一個(gè)指針域的鏈表，稱為操作方頭結(jié)點(diǎn)(頭指針)head指向第一個(gè)結(jié)點(diǎn)。頭結(jié)點(diǎn)數(shù)據(jù)域可以 任何信息(或鏈表長度等信息單鏈表是由表頭唯一確定，因此單鏈表可以指針的名字來例1、線性表 ?? 結(jié)點(diǎn)的單鏈表的邏輯狀態(tài)、物 方

結(jié)點(diǎn)的描述與C語言中用帶指針的結(jié)構(gòu)體類型typedefstruct ElemTypedata; Lnode*next; /*結(jié)點(diǎn)的類型棧的棧(Stack)：是限制在表的一端進(jìn)行插入和除操作的線性表。又稱為后進(jìn)先出或先進(jìn)出線性表?xiàng)ｍ?Top)：允許進(jìn)行插入、刪除操作的端，又稱為表尾。用棧頂指針(top)頂元素棧底(Bottom)：是固定端，又稱為表頭空棧：當(dāng)表中沒有元素時(shí)稱為空棧順序棧示設(shè)棧S=(a1，a2，…an)a1稱為棧底元素，an為

進(jìn)棧

出棧元素，如圖所示棧中元素按a1，a2，…an

順序棧示意棧的抽象數(shù)據(jù)類型ADT數(shù)據(jù)對象：Dai|ai∈ElemSet,i=1,2,…,n，n≥0}數(shù)據(jù)關(guān)系：Rai-1ai>|ai-1，ai∈D,}}ADT 靜態(tài)順 空間 base表示棧底指針，棧底固定不變的；棧頂則著進(jìn)棧和退棧操作而變化。top表示棧頂指數(shù)組中的下一 位置棧的動(dòng)態(tài)順 表示（續(xù)結(jié)點(diǎn)進(jìn)棧：首先將數(shù)據(jù)元素保存到棧頂(top所的當(dāng)前位置)，然后執(zhí)行top加1，使top指向棧的下一 位置結(jié)點(diǎn)出棧：首先執(zhí)行top減1，使top素 位置，然后將棧頂元素取出a堆棧變化示意a

cbacba空

元素a

ba元素b，cba

元素c

fedba元素d，efedba(動(dòng)態(tài))堆棧變化示意棧的鏈 表?xiàng)５逆?結(jié)構(gòu)稱為鏈?zhǔn)沁\(yùn)算受表頭位置上進(jìn)?棧頂指針top?typedefstruct{ElemType data;structLStack*next;}LStack

空

非空順序棧與鏈棧的順序棧需要固定空求鏈棧的大小的時(shí)間復(fù)雜度為O(n)隊(duì)定infirstout)的線性表（簡稱FIFO結(jié)構(gòu)）。只允許在表的一端（隊(duì)尾）（隊(duì)頭）進(jìn)行刪除出隊(duì) 入隊(duì)隊(duì) 隊(duì)例子：車站排隊(duì)；操作系統(tǒng)的作隊(duì)列的類型ADTQueue數(shù)據(jù)對D＝{ai|ai∈ElemSet,i=1,2,...,n,數(shù)據(jù)關(guān)R1＝{<ai-1,ai>|ai-1,ai∈D,約定其中a1端為隊(duì)列an端為隊(duì)列尾}ADT定用鏈表說

^…^…鏈隊(duì)列運(yùn)算指針變化^^^x^x^yx元素^yx元素y入隊(duì)^yx^yx元素x出隊(duì)循環(huán)5432

定

非空隊(duì)列中頭指針指向隊(duì)頭元素尾指針指循環(huán)隊(duì)列示

432

01數(shù)組的數(shù)組可看成是一種特殊的線性表中的數(shù)據(jù)元素本身也是一種線性表結(jié)構(gòu)的原子類型數(shù)組可以看成是線性表的推廣由于數(shù)組中各元素具有統(tǒng)一的類型素的下標(biāo)一般具有固定的上界和下界組的處理比其它復(fù)雜的結(jié)構(gòu)更為簡單二維數(shù)組的數(shù)據(jù)對象D={aij|0≤i≤b1-1,0≤j≤b2-數(shù)據(jù)關(guān)系R={ROW,COLROW={<ai,j,ai,j+1>|0≤i≤b1-1,0≤j≤b2-COL={<ai,j,ai+1,j>|0≤i≤b1-2,0≤j≤b2-二維數(shù)組二維數(shù)組可以看成是一個(gè)Amn(0,1,...p))))))))))

a0,n1Amn

a1,n1(((

((

(((1 am1,n(((1二維數(shù)組C語言typedefelemtype等價(jià)于typedefelemtypearray1[n];typedefarray1array2[m];二維數(shù)組C語言typedefarray2提概線性樹圖排遞歸與分治小樹的樹是n(n0)個(gè)結(jié)點(diǎn)的n=，稱為空樹；如n0，當(dāng)n>1，除根以m(m>0)個(gè)互不T1,T2,…,Tm，其中每個(gè)A只有根結(jié)點(diǎn)

A T1,T2,T3都是根A ，且本身也是一棵樹的基本 兄弟結(jié)點(diǎn)：同一雙親的孩堂兄結(jié)點(diǎn)：雙親在同一層的結(jié)點(diǎn)互為堂兄樹的基本術(shù)語（續(xù)樹的高度：樹中結(jié)點(diǎn)的最結(jié)點(diǎn)的度：結(jié) 的個(gè)數(shù)葉子結(jié)點(diǎn)：也叫終端結(jié)點(diǎn)，是度為0的結(jié)分枝結(jié)點(diǎn)：度不為0有序樹 有序的樹 不能互換無序樹：不考 的順序 樹的基本術(shù)語（續(xù)

DICGB是m（m≥0）DICGBJM不相交的樹的JMEFHEFHLK任何一棵非空樹是一個(gè)二LKTree=其中：root被稱為根結(jié)點(diǎn)F被稱 森樹的基本術(shù)語（續(xù)路徑：樹中的k個(gè)結(jié)點(diǎn)n1,n2，…，nk，滿足ni是ni1的雙親，n1到nk有一條路徑路徑長度：分支數(shù)＝路徑上結(jié)點(diǎn)個(gè)數(shù)一注注根沒有雙親，葉子沒有孩子vi是vj的雙親，則LviL(vj1對比線性結(jié)構(gòu)和樹型線性結(jié)構(gòu) 樹型結(jié)構(gòu)（1:n）(a1,a2,a3,…an-2,an-1,第一個(gè)數(shù)據(jù)

(無前驅(qū)最后一個(gè)數(shù)據(jù)(無后繼其它數(shù)據(jù)一個(gè)后繼

(無前驅(qū) 多個(gè)葉子(無后繼其它數(shù)據(jù)元(一個(gè)前驅(qū)一個(gè)或多個(gè)后繼樹的抽象數(shù)據(jù)類型ADTTree數(shù)據(jù)對象D：具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R：若D為空集，則稱為空樹。否則(1)在D中存在唯一的稱為根的數(shù)據(jù)元素 的有限集T1,T2,…,Tm，其中每一棵子集本身又是 基本操作}ADT定別稱為左和右的、互不相交的二叉樹組特每個(gè)結(jié)點(diǎn)至多只有兩棵（二叉樹中不存在度右根結(jié) 左 二叉樹的五種基本空空只含根為空為空為空 滿二定義一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹22611121314完全二若設(shè)二叉樹的高度為h，則共有hh層外，其它各層(0h-1的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)h層從右向左連續(xù)缺若干結(jié)點(diǎn)。22611二叉樹 結(jié)二叉樹也可以采用兩 方式順 結(jié)構(gòu)和鏈 結(jié)構(gòu)順 結(jié)結(jié)構(gòu)適用于完全二叉樹 二叉樹的每個(gè)結(jié)點(diǎn)編號的順序存放結(jié)點(diǎn)內(nèi)容二叉樹的順序1212349567812345678911234567812340567800的順序

的順序表鏈 結(jié)在順序結(jié)構(gòu)中，利用編號表示元素的位置及元間孩子或雙親的關(guān)系。這種情況下可考慮鏈?zhǔn)匠Ｒ姷亩鏄浣Y(jié)點(diǎn)結(jié)構(gòu)如

鏈 結(jié)類型定義typedefstructBiTNode{emTypedata;structBiTNode鏈 結(jié)這種結(jié)構(gòu)的特點(diǎn)是尋找孩子結(jié)點(diǎn)容易，雙親比較。

二叉樹鏈表表示的DBABDBABCDEFDBA

ACCCEEFEF二叉 二叉鏈

三叉鏈樹和樹 結(jié)雙親表示孩子表示孩子兄弟表示法（二叉鏈表表示法森林與二叉樹的樹和森林的雙親表在每個(gè)結(jié)點(diǎn)中附設(shè)一個(gè)指R-A0B0CR-A0B0C0D1E1F3G6H6K61RARABCDEFGHK3456789雙親表示法 反復(fù)調(diào)用PARENT操作直到遇見點(diǎn)時(shí)，便找到了樹的根域，每個(gè)指針指向一棵的根結(jié)點(diǎn)。其結(jié)第一種格式結(jié)點(diǎn)同構(gòu)，鏈表中會產(chǎn)，浪費(fèi)空……孩子鏈表表每個(gè)結(jié)點(diǎn)的孩子排，以單鏈表作 結(jié)構(gòu)則n個(gè)結(jié)點(diǎn)有n個(gè)孩子鏈表（為空表）n個(gè)頭指針又組成一個(gè)線，可采用順 結(jié)構(gòu)孩子鏈表表Λ53Λ53ABΛCDΛREΛFGΛHΛKΛRABRABCDEFGHKΛ62Λ2Λ2104Λ9Λ9876789孩子兄弟表定又稱二叉樹表示法，或二叉鏈表表示法以二叉鏈表做樹的結(jié)構(gòu)，鏈表中的兩個(gè)鏈域ΛAAΛACBΛΛEΛΛDΛ CBΛΛEΛΛDΛ孩子兄弟表這種結(jié)構(gòu)便于實(shí)現(xiàn)各種樹的操作易于實(shí)現(xiàn)找結(jié)點(diǎn)孩子等的操作。例如要結(jié)點(diǎn)RABCDEFGHKAΛDΛ CRABCDEFGHKAΛDΛ CFRRΛEΛΛΛG?HΛΛKΛ提概線性樹圖排遞歸與分治小圖是由一個(gè)頂點(diǎn)集V和一個(gè)弧集R構(gòu)成的Graph=(V,R其中VR＝{<v,w>|v,w∈V且<v,w>表示v到w的一條v為弧，w為弧尾 謂詞P(v,w)定義了弧<v,w>的意義或信息 圖的結(jié)構(gòu)定義（續(xù)ABECD例如:G1=(V1,VR1)其中V1={AB,CDABECD<B,C>,<C,D>,<D,A>,<E,C>圖的結(jié)構(gòu)定義（續(xù)若<vw>VR必有<wv>VR,為頂點(diǎn)v和頂點(diǎn)w之間存在一條邊由頂點(diǎn)集和邊集構(gòu)成的圖稱作無向圖BCADFE例如BCADFEV2={A,B,C,D,E,VR2={(A,B),(A,(B,E),(C,D),(D,(B,F),(C,F)ABECF名ABECF或“無向網(wǎng)”。B設(shè)圖G=(V,{VR})BBCAECF圖G=(V,{VR}),且VV,VRVR,則稱G為GBCAECF名詞和術(shù)語（續(xù)假設(shè)圖中有n個(gè)頂點(diǎn)，e條邊含有e=n(n-1)/2條邊的無向圖稱作“完全圖若邊或弧的個(gè)數(shù)e<nlogn，則稱作“稀疏圖，否則稱作“稠密圖”名詞和術(shù)語（續(xù)頂點(diǎn)v和w互為“鄰接點(diǎn)(v,w)和頂點(diǎn)v和w相“關(guān)聯(lián)和頂點(diǎn)v關(guān)聯(lián)的邊的數(shù) 定義為邊的“度 例如:ID(B)=3，ID(A)= 名詞和術(shù)語（續(xù)對有向圖由于弧有方向性，則有入度和出度頂點(diǎn)的出度:以頂點(diǎn)v為弧尾的弧的數(shù)目頂點(diǎn)的入度:以頂點(diǎn)v頂點(diǎn)的度(TD)=出度(OD)+入度 例如:OD(B)= ID(B)=TD(B)= 名詞和術(shù)語（續(xù) 設(shè)圖G=(V,{VR})中的 一個(gè)頂點(diǎn)序列{ vi,1vi,m=w}中，(vi,j-1,vi,j)VR1≤j≤m,則稱從頂點(diǎn)u到頂點(diǎn)w之間存在一條路徑，路徑上邊的數(shù)目稱作“路徑長度”。如:從A到F長度為3的路徑簡單路徑:指序列中頂點(diǎn)不重復(fù)出現(xiàn)簡單回路:指序列中第一個(gè)頂點(diǎn)和最后一個(gè)頂 相同的路徑 名詞和術(shù)語（續(xù)BCADFEBCADFE通子圖稱作此圖的“連通分量名詞和術(shù)語（續(xù)EFABECF名詞和術(shù)語（續(xù)B假設(shè)通圖有n個(gè)頂點(diǎn)和e條邊，其中n-1條邊n個(gè)頂點(diǎn)構(gòu)成一個(gè)極小連通BC對非連通圖，則稱由各連通分量的生成樹的A 合為此非連通圖的森林 圖 結(jié)圖的數(shù)組(鄰接矩陣 表圖的鄰接 表有向圖的十字鏈 表無向圖的鄰接多重 表圖的數(shù)組(鄰接矩陣 表定義:矩陣的元素為Aij=01ABCABCDEF010010100010000101001001110000011100 D3 5圖的數(shù)組(鄰接矩陣 表有向圖的鄰接矩陣為非對010010100100100000101100000100ABCFE1 3 圖的鄰接 表FEFEDCBA 3 有向圖的鄰AABECFEFCBAEFCBA有向圖的逆鄰A0

30ABCDE ABCDE在有向圖的鄰接表中 對每個(gè)頂點(diǎn) 是指向該頂點(diǎn)的有向圖的十字鏈 表 A20A20∧10010∧B∧∧B1C∧1202C∧1202∧∧無向圖的鄰接多重 表AA20CB 20CB020D0D0331圖的 遍歷圖的路深度優(yōu)先廣度優(yōu)先深度優(yōu)先搜索遍連通圖的深度優(yōu)先從圖中某個(gè)頂點(diǎn)V0出發(fā)， 深度優(yōu)先搜索遍

w3w 深度優(yōu)先搜索遍V

W1、W2和W3均為的鄰接點(diǎn)，SG1、 SG3分別為含W1、W2和W3的子圖 1頂點(diǎn)VforW1、W2、W3若該鄰接點(diǎn)W未 則從它出發(fā)進(jìn)行深度優(yōu)先搜索遍歷深度優(yōu)先搜索遍從上頁的圖解如何判別V的鄰接點(diǎn)是否 解決的辦法是:為每個(gè)頂點(diǎn)設(shè)立一個(gè) 標(biāo)非連通圖的深度優(yōu)先搜索首先將圖中每個(gè)頂點(diǎn) 標(biāo)志設(shè)FALSE,之后搜索圖中每個(gè)頂 否則繼續(xù)非連通圖的深度優(yōu)先搜索 c cg2 2 TTTTTTTTTTTTF d 次序

Vw8w4Vw8w4其中，V->w1V->w2>w8的路徑長度為V->w7V->w3V->w5路徑長度為V->w6V->w4的路徑 度為3 廣度優(yōu)先搜索遍VV廣度優(yōu)先搜索遍從圖中的某個(gè)頂點(diǎn)V0出發(fā)，并在此頂點(diǎn)之后依次V0的所有未被過的鄰接點(diǎn)，之后按這些頂點(diǎn)被的先后次序依次它們的鄰接點(diǎn)，直至圖中所有和V0有路徑相通的頂點(diǎn)都被到。若此時(shí)圖中尚有頂點(diǎn)未被,則另選一個(gè)未曾被的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被到為止。(連通網(wǎng)的)最小生問題n個(gè)城市只n-1條線路。如何在最節(jié)省經(jīng)費(fèi)的前提下建立這個(gè)該問題等價(jià) 邊中選取n-1條邊（不構(gòu)成回路），使“權(quán)值算法：普里姆和普里姆基本思取圖中任意一個(gè)頂點(diǎn)v作為生成樹的根，之后往生成樹上添加新的頂點(diǎn)w。w和已經(jīng)在生成樹上的頂點(diǎn)v之通頂點(diǎn)vw之間的邊中取值最小。n-1個(gè)頂點(diǎn)為止。普里姆aab57ce83 f所得生成樹權(quán)14+8+3+5+16+21普里姆一般情況下所添加的頂點(diǎn)應(yīng)滿足下列條件U在生成n個(gè)頂點(diǎn)分屬兩個(gè)集合：已落在生成樹上的頂點(diǎn)集U和尚未落U算基本思具體做法:先構(gòu)造一個(gè)只含n個(gè)頂點(diǎn)的子圖SG中產(chǎn)生SG上加上這條邊，如此重復(fù)，直n-1條邊為止。算 f兩種算法算法時(shí)間復(fù)適應(yīng)稀疏提概線性樹圖排遞歸與分治小什么是排例如：將下列52,49,80,36,14,58,61,23,97,調(diào)整14,23,36,49,52,58,61,75,80,什么是排一般情況下，假設(shè)含n個(gè)記錄的序列R1R2Rn，其相應(yīng)的關(guān)鍵字序K1K2，Kn。這些關(guān)鍵字相互之間可個(gè)關(guān)系Kp1≤Kp2≤…≤Kpn。按此固有關(guān)系將上式記錄序列重新排Rp1Rp2,…，Rpn的操作稱作排序若整個(gè)排序過程不需 外存便能完，則稱此類排序問題為內(nèi)部排序內(nèi)部排序的經(jīng)經(jīng)過一內(nèi)部排序的基于不同的“擴(kuò)大有序序列長度的方，內(nèi)部排序方法大致可分插入交換選擇歸并其它方一趟直接插入排序的基本有序序列R[1..i-無序序無無序序有序序列在R[1..i-1]中查找R[i]的插入位置；R[1..j].keyR[i].key<R[j+1..i-將R[i]插入 )到R[j+1]的位置上利用“順序查找”實(shí)現(xiàn)“R[i]的插入位置從R[i-1]起向前進(jìn)行順序查找，監(jiān)視哨為

jjR[0]=R[i];//設(shè)置“哨循環(huán)結(jié)束表明R[i]的插入位置為j+1；for(j=i-1;R[0].key<R[j].key;--j);R[j+1]=R[j]

j插入上述循環(huán)結(jié)束后可以直接進(jìn)行“j插入直接插入令i2，3，n實(shí)現(xiàn)整個(gè)序列的for(i=2;i<=n;++i{插入R[i}直接插入voidInsertionSort(SqList&L)對順L作直接插入排序for(i=2;i<=L.length;++iif(L.r[i].key<L.r[i-1].key)L.r[0] 為監(jiān)L.r[i]=L.r[i-for(j=i-2;L.r[0].key< --jL.r[j+1]=L.r[j+1]=}//

記錄插入到正確起泡假設(shè)在排序過程中，記錄序列R[1..n]n- 鍵字最大的到n- 的位置

起泡voidBubbleSort(ElemR[],intn)i=while(i>1){lastExchangeIndex=1;for(j=1;j<i;j++)if(R[j+1].key<R[j].key)Swap(R[j],lastExchangeIndexj;//記下進(jìn)行交換的記錄}}//}//起泡起泡排序的結(jié)束條最后一趟一般情況下，每經(jīng)過一趟“起泡”，“i減一，但并不是每趟都如此2135789for(j=1for(j=1;j<i;j++)if(R[j+1].key<一趟快速排序（一次劃分將分割成兩部分：R[s..i-1]和R[i+1..t],且R[j].key≤R[i].key≤R[k].key lowlowhighighhigh設(shè)R[s]=52為樞軸暫存在R[0]的位置上要求R