其他數(shù)據(jù)結(jié)構(gòu)朱全民

1、數(shù)據(jù)結(jié)構(gòu) 講授：朱全民定義數(shù)據(jù)(data) 是對客觀事物的符號的表示。例如數(shù)值、圖像、聲音都屬于數(shù)據(jù)的范疇。數(shù)據(jù)元素(data element) 是數(shù)據(jù)的基本單位 數(shù)據(jù)對象（data object）是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。 數(shù)據(jù)結(jié)構(gòu)（data structure）是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。 數(shù)據(jù)結(jié)構(gòu)的內(nèi)涵1. “操作”的對象：數(shù)據(jù)。2. 數(shù)據(jù)與數(shù)據(jù)間的關(guān)系。3. 針對數(shù)據(jù)的基本操作。 據(jù)此，數(shù)據(jù)結(jié)構(gòu)可以形式定義為：數(shù)據(jù)結(jié)構(gòu)是一個二元組 Data_Structure = (D, S)存儲結(jié)構(gòu)邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間是邏輯關(guān)系。 物理結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)在計(jì)算

2、機(jī)中的存儲方式。順序存儲結(jié)構(gòu)：借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。邏輯上關(guān)聯(lián)的數(shù)據(jù)元素，物理存儲結(jié)構(gòu)中相鄰。 鏈?zhǔn)酱鎯Y(jié)構(gòu) ：借助元素存儲地址的指針(pointer）表示數(shù)據(jù)元素之間的邏輯關(guān)系 。邏輯上關(guān)聯(lián)的數(shù)據(jù)元素，物理存儲結(jié)構(gòu)中不一定相鄰。 幾種常見的數(shù)據(jù)結(jié)構(gòu)模型線性表線性表是一種簡單的數(shù)據(jù)結(jié)構(gòu)，一個具有n個元素的線性表a1,a2 , an，除了a1只有一個后繼，an只有一個前趨，其它元素都有且只有一個前趨和后繼，其中ai的前趨為ai-1 ,ai的后繼為ai+1 Linear-list=（D，R） 其中： Dai| ai D , i1,2,n，n0 R=N,N= |

3、ai-1,aiD0,i1,2,n D為某個數(shù)據(jù)對象線性表的表示順序存儲結(jié)構(gòu) 用數(shù)組類型： list: array 1.max of elemtp ;鏈?zhǔn)酱鎯Y(jié)構(gòu) 用指針類型： point = p_list ; p_list = record elm : elemtp ; link : point ; end;操作順序存儲結(jié)構(gòu)查找：可以實(shí)行折半查找，時間復(fù)雜度O(log2(n) 插入：需要做數(shù)據(jù)的移動。 刪除：需要做數(shù)據(jù)的移動。鏈?zhǔn)酱鎯Y(jié)構(gòu) 查找：只能順序查找，時間復(fù)雜度O(n) 插入：不需要做數(shù)據(jù)的移動。 刪除：不需要做數(shù)據(jù)的移動。舉例約瑟夫問題M個人圍成一圈，從第一個人開始報數(shù)，數(shù)到N的人出

4、圈；再由下一個人開始報數(shù)，數(shù)到N(N1)的人出圈；.。輸出依次出圈的人的編號。M的值預(yù)先選定，N由鍵盤輸入。分析：要解決這道問題，首先需要構(gòu)造一個環(huán)表，構(gòu)造環(huán)的方法很簡單，只要存儲每個人的下一個即可，當(dāng)然，最后一個人的下一個就是第一個人，這樣就構(gòu)成了一個環(huán)，構(gòu)造環(huán)以后，就可進(jìn)行刪除操作，直到環(huán)剩下一個人為止?？焖倥判蚩焖倥判蚴菍γ芭菖判虻囊环N改進(jìn)。他的基本思想是,通過一趟排序?qū)⒋诺挠涗浄指畛瑟?dú)立的兩個部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個序列有序。堆棧堆棧是一種后進(jìn)先出(LIFO)的線性表堆棧的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)順序棧的

5、數(shù)據(jù)結(jié)構(gòu)表示 const maxsize=棧的大小; type sqstktp=record elem: array1.stack_size of elemtp; top:0.maxsize;基本操作 1) 壓棧（PUSH） 2) 彈棧（POP）棧的應(yīng)用算術(shù)達(dá)式求值輸入一個表達(dá)式，該表達(dá)式含有“+”、“-”、“*”、“/”、“（”、“）”和操作數(shù)，輸入以結(jié)束。構(gòu)造兩個棧opnd和optr分別存放操作數(shù)和 操作符構(gòu)造操作符的優(yōu)先關(guān)系表以3*(5-2)+7為例,操作過程見圖算法框架Function exp_reduced: oprandtype; inistack(optr);push(optr,

6、); inistack(opnd) read(w); while not (w=) and (gettop(optr)=) do If not w in op then push(opnd,w);read(w) else case predede(gettop(optr),w) of :theta:=pop(optr);b:=pop(opnd);a:=pop(opnd); push(opnd,operate(a,theta,b); endc return(gettop(opnd)endF隊(duì)列隊(duì)列是一種先進(jìn)先出(FIFO)的線性表隊(duì)列的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)隊(duì)列必須構(gòu)造成循環(huán)隊(duì)列的形式,否則

7、會出現(xiàn)“假溢出” const maxsize=隊(duì)列最大容量； m=maxsize-1; type cyclcquetp = record elem : array0.m of elemtp; rear, front : 0.m; end;基本操作 1) 插入（en_cycque） 2) 刪除（dl_cycque）隊(duì)列的應(yīng)用計(jì)算廣義表（見書P54）寬度優(yōu)先搜索排隊(duì)事件的模擬串串是由0個或多個字符組成的序列串的存儲結(jié)構(gòu) 靜態(tài)存儲結(jié)構(gòu) const maxlen=串被確認(rèn)的最大長度 type strtp=record ch: array 1.maxsize of char; curlen:0.maxl

8、en end; 緊縮數(shù)組 ch:packed array 1.maxlen of char; 按字節(jié)存放 動態(tài)存儲結(jié)構(gòu) const chunksize=chunk; chunk=record ch:array q.chunksize of char; next : pointer; end; 堆結(jié)構(gòu)：每次從自由空間中動態(tài)分配一塊內(nèi)存給串，并建立空間的起始地址串的基本操作串的連接（concat）求子串（substr- Pascal中的copy函數(shù)）插入函數(shù)（insert）刪除函數(shù)（delete）定位函數(shù)（index- Pascal中的pos函數(shù)）KMP算法KMP的基本原理假設(shè)主串為s1s2sn

9、,模式串為p1p2pm , 當(dāng)模式串發(fā)生失配 (sipj)時,模式串”向右滑動”可行距離有多遠(yuǎn)? 假設(shè)此時應(yīng)與模式中的第k (kj)個字符繼續(xù)比較,則模式中的前k-1個字必須與主串的前k-1個字符相等,有 p1p2pk-1= s i-k+1si=k+2si-1 由已經(jīng)得到的部分匹配結(jié)果可知 pj-k+1pj=k+2pj-1= s i-k+1si=k+2si-1所以有 p1p2pk-1= pj-k+1pj=k+2pj-1由上式可知,當(dāng)主串第i個字符與模式串第j個字符不相等時候,僅需將模式串向右滑動到模式串中的第K個字符和主串中的第i個字符對齊,此時模式中的頭K-1個字符的子串肯定與主串中第i個字

10、符之前的K-1個子串相等.怎樣求KKMP示例求next函數(shù)next1=0,設(shè)nextj=k,表明, p1p2pk-1= pj-k+1pj=k+2pj-1(1) 若pk= pj ,則在模式串中有 p1p2pk= pj-k+1pj=k+2pj 顯然 nextj+1=k+1(2) 若pk pj ,則雜模式串中有 p1p2pk pj-k+1pj=k+2pj 則可將求next函數(shù)的問題看成整個模式串既是主串又是模式串的問題,應(yīng)將模式串滑動到nextk個字符和主串的第j個字符相比較.若nextk=k,且pj=pk,則說明在主串中第j+1個字符之前存在一個長度為k的最長子串,和模式串中從首字符起長度為k的子

11、串相等,即 p1p2pk pj-k+1pj=k+2pj也就是說nextj+1=k+1=nextk+1求NEXT算法Proc get_next(t:strtp) next為全程變量j:=1 ;k:=0;next1:=0;While j1時,其余結(jié)點(diǎn)可分為m(m0)個互不相交的有限集T1,T2,Tm,每個集合又是一棵樹,稱為子樹.其他概念: 葉子,樹的度,結(jié)點(diǎn)的度,雙親,孩子,兄弟,深度 有序樹,無序樹,二叉樹,森林二叉樹概念 二叉樹是以結(jié)點(diǎn)為元素的有限集,它或者為空,或者滿足以下條件: 1)有一個特定的結(jié)點(diǎn),叫根 2)余下的結(jié)點(diǎn)分為兩個互不相交的子集L和R,其中L叫左子樹,R叫右子樹幾種特殊的二

12、叉樹 空樹,斜樹,完全二叉樹,滿二叉樹二叉樹的性質(zhì)在二叉樹的第i層上最多有2i-1個結(jié)點(diǎn)深度為K的二叉樹最多有2k-1個結(jié)點(diǎn)在二叉樹中,葉子結(jié)點(diǎn)的總數(shù)總比為度數(shù)為2的結(jié)點(diǎn)多1有n個結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序編號,則對任意一結(jié)點(diǎn)i,有(1)如果i=1,則結(jié)點(diǎn)i是二查樹的根，無雙親；如果i1，則雙親是i/2(2)如果2in，則結(jié)點(diǎn)i無左孩子，否則左孩子為2i(3)如果2i+1n，則結(jié)點(diǎn)i無右孩子，否則右孩子為2i+1二查樹的基本操作存儲結(jié)構(gòu) type bitree=node node=record data :datatype; lchild,rchild:bitree; end;遍歷 先序遍歷

13、 中序遍歷 后序遍歷常見的幾種樹結(jié)構(gòu)最優(yōu)二叉樹（哈夫曼編碼，P92） 樹的代權(quán)路徑長度之和最小的二叉樹二叉排序樹 它或者是一顆空樹，或者是具有如下性質(zhì)的二叉樹：1)若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值2) 若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值3)它左右子樹分別為二叉排序樹。平衡二叉樹(AVL樹)它或者是一棵空樹，或者是具有如下性質(zhì)的二叉樹：它左右子樹都是平衡排序樹，且左右子樹的深度之差超過1。二叉堆 n個元素的序列k1,k2,kn，當(dāng)且僅當(dāng)滿足 ki=k2i 并且 ki =k2i 并且 ki = k2i+1 線段樹 它或者是一顆空樹，或者是具有如

14、下性質(zhì)的二叉樹:樹中每個結(jié)點(diǎn)表示一個區(qū)間。樹的存儲結(jié)構(gòu)雙親表示法 type tnode=record data:datatype; parent:integer; end;孩子兄弟表示法 type tlinktp=tnodetp; tnodetp=record data:elementtp; fch,nsib:tlinktp; 第一個孩子、下一個兄弟 end樹、二叉樹、森林用“孩子兄弟表示法”可以將任意一棵樹轉(zhuǎn)化為二叉樹的形式 森林轉(zhuǎn)化為二叉樹 如果F=T1, T2, ,Tm是森林，則可按如下規(guī)則轉(zhuǎn)化為一棵二叉樹。 1)若F為空，即m=0,則B為空樹 2)若F非空，即m0,則B的根root即為

15、森林中第一棵樹的根root(T1),B的左子樹為從T1中子樹森林F1=T11, T12, ,T1i轉(zhuǎn)換而成的二叉樹；其右子樹Rb 是從森林F=T2, ,Tm中轉(zhuǎn)換出來的二叉樹堆排序堆排序算法PROC shift (var r:listtype; k,m:integer); i:=k.j:=2*I; x:=rk.key;finish:=false t:=rk; while (j=m) and not finish do if (jrj+1.key) then j:=j+1; If x=rj.key then finish:=true Else ri:=rj; i:=j; j:=2*I ri:=t

16、endPPROC heapsort(var r:listtype);For i:=n/2 downto 1 shift(r,I,n);For i:=n downto 2 do r1與ri交換; shift(r,1,i-1) endP圖圖的定義G=(V,E)圖的基本概念有向圖、頂點(diǎn)、入度、出度、弧、環(huán)無向圖、邊、路徑、頂點(diǎn)的度、鄰接簡單圖、完全圖平面圖、二分圖圖的存儲結(jié)構(gòu)鄰接矩陣 graph=Record vex:array1.vtxptr of vertex; arc:arrayvtxptr, vtxptr of vertex;鄰接表 表節(jié)點(diǎn) type arcptr=arcnode; arcn

17、ode=record adjvex:vtxptr; nextarc:arcptr; info: 和弧有關(guān)的其他信息 end; vex=Record vexdata: 和頂點(diǎn)有關(guān)的其他信息 firstarc:arcptr; end;Adjlist=array vtxptr of vexnode;圖的遍歷深度優(yōu)先搜索（P103）廣度有先搜索（P104）最小生成樹PRIM算法示例 prim算法PROC prim(gn:adjmatrix;u0:vtxptr); for v:=1 to vtxnum do if vu0 then with closedgev do vex:=u0;lowcost:=g

18、nu0,v For i:=1 to vtxnum-1 do k:=minimun(closedge) 在V-U中找到最小代價邊的頂點(diǎn) write(closedgek.vex,k); closedgek.lowcost:=0; 頂點(diǎn)k并入U集 If gnk,vclosedgev.lowcost then closedgev.lowcost:=gnk,v; closedgev.vex:=k krusal算法示例圖的連通性問題無向圖的連通性 利用深度有先算法遍歷圖，看是否所有的結(jié)點(diǎn)都被遍歷到。求有向圖的強(qiáng)連同分量(1)從某個頂點(diǎn)出發(fā)沿以該定點(diǎn)為尾的弧進(jìn)行深度有先搜索遍歷，并按其所有鄰接點(diǎn)的搜索都完成

19、的順序?qū)㈨旤c(diǎn)排列起來。(2)從最后完成搜索的頂點(diǎn)出發(fā)，沿著一該定點(diǎn)位頭的弧作逆向深度有先搜索遍歷，若此次不能訪問到有向圖中所有的頂點(diǎn)，則從余下的頂點(diǎn)中最后完成的頂點(diǎn)出發(fā)，繼續(xù)作逆向深度有先搜索遍歷，以此類推，直至有向圖中所有的頂點(diǎn)都訪問為止。(3)每次調(diào)用dfs逆向深度有先遍歷所訪問的頂點(diǎn)集，就是一個強(qiáng)連通分量最短路經(jīng)問題(Dijkstra算法)核心思想：按路徑遞增的次序產(chǎn)生最短路徑的算法 1)找到圖中最短的路徑，設(shè)為（v,vj）,將j設(shè)為已標(biāo)號的點(diǎn) 2)找下一條次短的路徑，假設(shè)終點(diǎn)為k,將k設(shè)為已標(biāo)號的點(diǎn),那么要么是（v,vk）要么是（v,vj,vk）,若經(jīng)過vj ,將j設(shè)為已檢查的點(diǎn),放入

20、集合. 3)以次短路徑出發(fā)找第三短的路徑,類似第二步的方法. 4)按上述方法一直到所有的頂點(diǎn)被檢查過,則從v到其他頂點(diǎn)的最短路徑求出.每一對頂點(diǎn)的最短路徑(floyd算法)假設(shè)求從vi到vj的最短路徑,如果vi到vj有弧,則它們的路徑為costi,j,否則需要進(jìn)行n次試探,首先考慮(vi v1 vj ),比較它與(vi vj )的大小,取較短者為中間節(jié)點(diǎn)序號不大于1的最短路徑,ji假如 (vi,v2 )和 (v2 , vj )都是中間節(jié)點(diǎn)序號不大于1的最短路徑,那么(vi,v2 , vj )可能是中間節(jié)點(diǎn)序號不大于2的最短路徑.將它和中間節(jié)點(diǎn)序號不大于1的最短路相比較,從中選出中間節(jié)點(diǎn)的序號不大于2的最短路徑之后,再增加一個頂點(diǎn)v3,繼續(xù)進(jìn)行試探.這樣進(jìn)行n次試探后,最后得到必然是vi到vj的最短路徑.有向圖的拓?fù)湫蛄卸x 若對有向圖G的頂點(diǎn),存在一個序列v1, vi,vj,vn, 只存在vi到vj的路徑,而不存在vj到vi的路徑,則稱該圖拓?fù)溆行蚍椒?)再有向圖中選一個入度為0的頂點(diǎn),輸出2)刪除該頂點(diǎn)和所有以它為尾的弧3)重復(fù)1,2直到找不到頂點(diǎn)為止4)如果輸出頂點(diǎn)的個數(shù)少于圖中頂點(diǎn)的個數(shù)，則該圖不具有拓?fù)溆行?否則拓?fù)湫蛄芯褪禽敵龅捻旤c(diǎn)順序求有向圖的關(guān)鍵路徑算法思想：求