數(shù)據(jù)結(jié)構(gòu)總復習

1、第一章 緒論1 1 基本概念1 數(shù)據(jù)數(shù)據(jù)是對客觀事物的符號表示，在計算機科學中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。2 數(shù)據(jù)元素數(shù)據(jù)元素是數(shù)據(jù)的基本單位， 數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。3 數(shù)據(jù)對象數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合。4 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)是相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合， 形式定義為一個二元組： D ata_St ructur e=(D， S)其中， D 是數(shù)據(jù)元素的有限集； S 是D 上關系的有限集。 ( 1)集合： 數(shù)據(jù)元素之間除了“ 同屬于一個集合” 的關系外， 別無其他關系。 ( 2)線性結(jié)構(gòu)： 數(shù)據(jù)元素之間存在一個一對一的關

2、系， 有且僅有一個開始結(jié)點和終端結(jié)點， 除開始結(jié)點外， 每個結(jié)點有且僅有一個前趨結(jié)點， 除終端結(jié)點外， 每個結(jié)點有且僅有一個后繼結(jié)點。 (3)樹型結(jié)構(gòu)： 數(shù)據(jù)元素之間存在一個對多個的關系， 有一個開始1結(jié)點和多個終端結(jié)點，除開始結(jié)點外，每個結(jié)點有且僅有一個前趨結(jié)點，除終端結(jié)點外， 每個結(jié)點可能有多個后繼結(jié)點。 (4)網(wǎng)狀結(jié)構(gòu)或圖狀結(jié)構(gòu)： 數(shù)據(jù)元素之間存在多個對多個的關系，每個結(jié)點可能有多個前趨結(jié)點和多個后繼結(jié)點。 樹型結(jié)構(gòu)和網(wǎng)狀結(jié)構(gòu)又稱為非線性結(jié)構(gòu)。 順序存儲、鏈接存儲、索引存儲、散列存儲。1 .2 算法及其分析 算法是是指令的有限運算序列。 算法具有以下5 個重要特性： 1.有窮性； 2.確

3、定性； 3 .可行性； 4.輸入； 5.輸出1 .3 算法的性能分析與度量 1.算法的性能標準 ( 1)正確性； (2 )可讀性； (3)健壯性； (4)高效率與低存儲量 2.算法效率的度量 時間復雜度T (n)=O(f (n) 空間復雜度S (n)=O(f (n) 算法+數(shù)據(jù)結(jié)構(gòu)=程序第二章 線性表2.1 線性表的順序存儲 1.線性表的順序存儲特點邏輯上相鄰的元素， 物理位置也相鄰。靜態(tài)有序表。線性表的順序存儲結(jié)構(gòu)是一種隨機存取的存儲結(jié)構(gòu)。表2-1 插入、刪除、查找、合并算法的時間復雜度2.2 線性表的動態(tài)鏈式存儲特點： 邏輯上相鄰的元素， 物理位置可以不相鄰， 表中元素只能順序訪問， 插入

4、、刪除等操作只需修改指針而不需移動元素。線性表的鏈式存儲結(jié)構(gòu)是一種順序存取的存儲結(jié)構(gòu)。2.3 線性表的靜態(tài)鏈式存儲特點： 用一維數(shù)組描述線性鏈表。2.4其他形式的鏈表1循環(huán)線性鏈表特點：最后一個結(jié)點的指針域指向頭結(jié)點，從任意結(jié)點出發(fā)都可以找到表中的其他結(jié)點。2.雙向鏈表特點:雙向鏈表克服了在單鏈表中求前趨需要遍歷鏈表而導致效率較低的缺點。從任意結(jié)點出發(fā)都可以找到表中的其他結(jié)點。第3 章 棧和隊列棧和隊列是操作受限制的線性表。3.1 棧及其應用棧( s ta ck ) 是限定只在表尾（ 棧頂）進行插入或刪除操作的線性表，是后進先出(LIFO)的線性表。棧結(jié)構(gòu)通常采用的兩種存儲結(jié)構(gòu)是順序存儲結(jié)構(gòu)和

5、鏈表存結(jié)構(gòu)。圖3 1 棧結(jié)構(gòu)的示意圖(A， B， C， D)(C， A， B， D) 3.2隊列及其應用隊列(Queue) 是限定只能在表的一端（ 隊尾）進行插入， 而在表的另一端（ 隊頭）進行刪除操作的線性表。和棧相反， 隊列是一種先進先出(FIFO)的線性表。 圖3 2 隊列的示意圖鏈隊列： 隊列的鏈式存儲結(jié)構(gòu)循環(huán)隊列： 隊列的順序存儲結(jié)構(gòu)1， 2， 3， 4線性表、棧和隊列都是線性結(jié)構(gòu)， 可以在線性表的任何位置插入和刪除元素； 對于棧只能在棧頂插入和刪除元素； 對于隊列只能在隊尾插入元素和在隊首刪除元素。第4 章 串4.1 有關概念1、串(或字符串)， 是由零個或多個字符組成的有序序列。

6、s ='a1a2 an' (n 0 )2、串中字符的數(shù)目稱為串的長度。零個字符的串稱為空串，它的長度為零。3、串中任意個連續(xù)的字符組成的子序列稱為該串的子串。包含子串的串相應地稱為主串。4、空串是所有字符串的子串， 任何字符串是自身的子串。4.2 串的存儲表示1串的定長順序存儲表示用一組地址連續(xù)的存儲單元存儲串值的字符序列，每個串變量分配一個固定長度的存儲區(qū)。2串的變長順序存儲(堆分配存儲)表示用一組地址連續(xù)的存儲單元存儲串值的字符序列，它們的存儲空間是在程序執(zhí)行過程中動態(tài)分配而得，對字串進行操作時不存在溢出問題。3串的塊鏈存儲表示適用于不改變數(shù)據(jù)結(jié)點的操作,如查找(或模式匹配

7、)。4.3 串的常用運算串賦值StrA ssign、串的比較S trC ompare、求串長StrL ength、串連接Strcat 以及求子串Sub String 構(gòu)成串類型的最小操作子集。如果s='I AM A STUD ENT'， t='GOO D'， 則LENGTH(s)的結(jié)果是1 4，CONCAT(SU BSTR(s ,6,2), CONCAT (t,SUB ST R(s,7,8) )A GOOD STUDENTA='BEI' B='J ING' C= ' ' D ='BEIJ ING'S

8、trLength (S) 求串長StrLength (A)=3 S trLeng th( B)=4Concat(&T， S1， S2) 聯(lián)接函數(shù)Concat(&T ,A,B) T= B EIJINGConcat(&T ,B,A) T= J INGBEISubString (&Sub， S， po s， len ) 求子串SubString (&Sub， D， 1， 3)='B EI'SubString (&Sub， D， 4， 0) ' 'SubString (&Sub， D， 4， 4) ' JI

9、NG'Index(S， T， pos ) 定位函數(shù)Index(d， b， pos )=4 Index(d， c， pos )=0如果設e= I 則 Index (d,e， pos)=3Replace(& S， T， V) 置換操作例如， 設S=' BBABBAB BA'， T 'AB'， V= 'C'則Replace(S， T， V)的操作結(jié)果為S= 'B BCBCBA'。StrInsert (&S， p os， T) 插入操作例如： Str Insert (&B,1, A)= B EIJINGSt

10、rDelete (&S， p os， le n) 刪除操作例如： Str Delete (&D,1, 3)= J ING例如， 假設 s=' ZHONGG UOConcat(Su bStrin g(s,1, 5), , Su bS tring (s, 6,3) 'ZHONG GU OConcat(Su bStrin g(s,1, 2), Su bStrin g( s,7,2) 'ZHUO'SubString (d,1,3 )= NAN S=NANJING第五章 數(shù)組和廣義表5 .1 多維數(shù)組類型特點:1 ) 只有引用型操作， 沒有加工型操作；2

11、) 數(shù)組是多維的結(jié)構(gòu)， 而存儲空間是一個一維的結(jié)構(gòu)。有兩種順序映象的方式:以行序為主序(低下標優(yōu)先)；以列序為主序(高下標優(yōu)先)。L OC( ai j ) = LO C( a1 1 ) + ( (i- 1)* n + j-1 ) * L稱為基地址或基址。5 .2 特殊矩陣的壓縮存儲對稱矩陣（書）k =I* (I -1) /2+ J-1下（ 上） 三角矩陣帶狀矩陣5 .3 稀疏矩陣稀疏矩陣的三元組表存儲 （書） 三元組表 稀疏矩陣的十字鏈表存儲 （書）5 .4 廣義表A （ ）B （ e）C （ a，（ b， c， d）D （ A， B， C）E （ a， E）F （ ）廣義表基本運算H ead

12、 (l s)： 返回廣義表ls 的頭部T ail (l s)： 返回廣義表的尾部H ead（ B） e Tail（ B） （ ）H ead（ C） a Tail（ C） （ b， c， d）H ead（ D） A Tail（ D） （ B， C）H ead（ E） a Tail（ E） （ E）H ead（ F） （ ） Tail（ F） （ ）廣義表的存儲1.頭尾表示法2.孩子兄弟表示法第六章 樹與二叉樹6.1 樹的結(jié)構(gòu)特性樹中只有根結(jié)點沒有前趨， 其余結(jié)點有且僅有一個前趨， 所有結(jié)點可有零個或多個后繼。6.2 二叉樹及其性質(zhì)二叉樹：是結(jié)點的有限集，該集合或者為空或者是由一個根結(jié)點和兩棵互不

13、相交的被稱為該根的左子樹和右子樹所組成。二叉樹的五種基本形態(tài)(a)空二叉樹； (b )僅有根結(jié)點的二叉樹， (c)右子樹為空的二叉樹；(d)左、右子樹均非空的二叉樹； (e)左子樹為空的二叉樹。性質(zhì)1 在二叉樹的第i 層上至多有2i -1 個結(jié)點(i 1)。性質(zhì)2 深度為k 的二叉樹至多有2k-1 個結(jié)點， (k 1)。滿二叉樹： 深度為k 且結(jié)點數(shù)為2k -1 的二叉樹。完全二叉樹： 深度為k、有n 個結(jié)點的二叉樹， 當且僅當每一個結(jié)點都與深度為k 的滿二叉樹中編號從1 到n 的結(jié)點一一對應。性質(zhì)3 對任何一棵二叉樹T， 如果其終端結(jié)點數(shù)為n0， 而度為2的結(jié)點數(shù)為n2， 則n0=n2+1。

14、例n0=6 n2=5 n0=n2+1=6特殊形態(tài)的二叉樹(a)滿二叉樹； (b )完全二叉樹；(c)和(d)非完全二叉樹。性質(zhì)4 具有n 個結(jié)點的完全二叉樹的深度為 log2 n+1性質(zhì)5 如果對一棵有n 個結(jié)點的完全二叉樹（ 其深度為 log2 n+1）的結(jié)點按層序編號(從第1 層到第 log2 n+1 層，每層從左到右)，則對任一結(jié)點i(1 i n)， 有( 1)如果i 1， 則結(jié)點i 是二叉樹的根， 無雙親； 如果i >1， 則其雙親是結(jié)點 i 2。( 2)如果2i >n， 則結(jié)點i 無左孩子； 否則其左孩子是結(jié)點2i。( 3)如果2i +1>n， 則結(jié)點i 無右孩子；

15、 否則其右孩子是結(jié)點2i +1。(1)n 個結(jié)點的二叉樹最多有n 層， 最少有 log2 n+1 層；(2)完全二叉樹中度為1 的結(jié)點最多1 個；(3)具有n 個結(jié)點的完全二叉樹， 編號最大的非葉結(jié)點是 n/2， 編號最小的葉結(jié)點是 n/2+1；(4)度為1 的結(jié)點數(shù)為(n +1) mod 2， 度為0 的結(jié)點數(shù)為 n/2， 度為2 的結(jié)點數(shù)為 n/2- 1。6.3 二叉樹的存儲結(jié)構(gòu)1 .順序存儲結(jié)構(gòu)按照完全二叉樹的結(jié)構(gòu)對二叉樹的結(jié)點進行編號。2 .鏈式存儲結(jié)構(gòu)有二叉鏈表、三叉鏈表、雙親鏈表、線索鏈表。（ 1）二叉鏈表： 二叉樹的結(jié)點由一個數(shù)據(jù)元素和分別指向它的左、右子樹的兩個分支構(gòu)成。lch

16、ilddatarchild 含有兩個指針域的結(jié)點結(jié)構(gòu)（ 2） 三叉鏈表：lchilddataparentrchild含有三個指針域的結(jié)點結(jié)構(gòu)（ 3） 線索鏈表lchildltagdatartagrchild (a)單支樹的二叉鏈表； (b)二叉鏈表； ( c)三叉鏈表。6.4遍歷二叉樹前序遍歷、中序(對稱序)遍歷、后序遍歷、層次(按寬度方向)遍歷。先序遍歷為： ABD HECFGI 中序遍歷DHB EAFCIG 后序遍歷為： HDE BFIGCA6.5線索二叉樹線索二叉樹： 加上線索的二叉樹。線索化： 對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程。6.6 樹的存儲結(jié)構(gòu)雙親、孩子鏈表、樹的二叉

17、鏈表(孩子-兄弟)存儲表示法。1 雙親表示法以一組連續(xù)空間存儲樹的結(jié)點，同時在每個結(jié)點中附設一個指示器指示其雙親結(jié)點在鏈表中的位置dataparent2 孩子鏈表表示法這種存儲結(jié)構(gòu)便于那些涉及孩子的操作，但不適合于求結(jié)點的雙親。3 孩子-兄弟表示法又稱二叉樹表示法， 或二叉鏈表表示法。即以二叉鏈表作樹的存儲結(jié)構(gòu)(對照樹與二叉樹的轉(zhuǎn)換)。firstchild 域,nexts ibling 域。6.7二叉樹與樹、森林之間的轉(zhuǎn)換1樹轉(zhuǎn)換為二叉樹的步驟(1)加線： 在各兄弟結(jié)點之間加一連線；(2)抹線：對任何結(jié)點，除了其最左邊的孩子之外，抹掉該結(jié)點原先與其余孩子之間的連線；(3)旋轉(zhuǎn)： 將添加的水平連

18、線和原有的連線， 以樹的根結(jié)點為軸心，按順時針方向粗略地旋轉(zhuǎn)45°。 此二叉樹的根結(jié)點只有左子樹， 而沒有右子樹； 轉(zhuǎn)換生成的二叉樹中各結(jié)點的左孩子是它在原來樹中的最左邊的孩子， 右孩子是它在原來樹中的下一個兄弟。 樹轉(zhuǎn)換為二叉樹的操作過程2 二叉樹還原為樹的步驟( 1)加線：如果p 結(jié)點是雙親結(jié)點的左孩子，則將p 結(jié)點的右孩子，右孩子的右孩子， ， 沿著右分支搜索到的所有右孩子， 都分別與P結(jié)點的雙親用線連起來；( 2)抹線： 抹掉原二叉樹中所有雙親結(jié)點與右孩子的連線；( 3)調(diào)整： 將結(jié)點按層次排列， 形成樹的結(jié)構(gòu)。二叉樹轉(zhuǎn)換為樹的操作過程3 森林轉(zhuǎn)換為二叉樹的步驟( 1)轉(zhuǎn)換：

19、 將森林中的每一棵樹轉(zhuǎn)換成二叉樹；( 2)連線： 將各棵轉(zhuǎn)換后的二叉樹的根結(jié)點相連；( 3)旋轉(zhuǎn)： 將添加的水平連線和原有的連線， 以第一棵樹的根結(jié)點為軸心， 按順時針方向粗略地旋轉(zhuǎn)45°。森林轉(zhuǎn)換為二叉樹的操作過程4 二叉樹還原為森林的步驟( 1)抹線： 抹掉二叉樹根結(jié)點右鏈上的所有結(jié)點上的連線， 分成若干個以右鏈上的結(jié)點為根結(jié)點的子二叉樹；( 2)轉(zhuǎn)換： 將分好的子二叉樹轉(zhuǎn)換成樹；( 3)調(diào)整： 將轉(zhuǎn)換好的樹的根結(jié)點排列成一排。二叉樹還原為森林的操作過程5 樹和森林的遍歷樹有3 種遍歷方法：( 1)先根遍歷若樹非空，則先訪問樹的根結(jié)點，然后依次先根遍歷根的每棵子樹。樹的先根遍歷與

20、轉(zhuǎn)換后的二叉樹的先序遍歷次序一致。( 2)后根遍歷若樹非空，則先依次后根遍歷根的每棵子樹，然后訪問樹的根結(jié)點。樹的后根遍歷與轉(zhuǎn)換后的二叉樹的中序遍歷次序一致。( 3)層次遍歷若樹非空， 則從樹的根結(jié)點起按層從左到右依次訪問各結(jié)點。樹的先根、后根和層次遍歷森林的遍歷(1)先序遍歷若森林非空， 則可以按照下述規(guī)則遍歷： 訪問森林中第一棵樹的根結(jié)點； 先序遍歷第一棵樹中根結(jié)點的子樹森林； 先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。森林的先序遍歷與轉(zhuǎn)換后的二叉樹的先序遍歷次序一致。(2)中序遍歷若森林非空， 則可以按照下述規(guī)則遍歷： 中序遍歷第一棵樹中根結(jié)點的子樹森林； 訪問森林中第一棵樹的根結(jié)點；

21、 中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。森林的中序遍歷與轉(zhuǎn)換后的二叉樹的中序遍歷次序一致。(3)層次遍歷若森林非空， 則可以按照下述規(guī)則遍歷： 對第一棵樹從根結(jié)點起按層從左到右依次訪問結(jié)點； 按層訪問森林中除第一棵樹外剩余的樹構(gòu)成的森林。6.8 赫夫曼樹及其應用赫夫曼( Huffma n)樹， 又稱最優(yōu)二叉樹， 它是n 個帶權(quán)葉子結(jié)點構(gòu)成的所有二叉樹中， 帶權(quán)路徑長度最短的二叉樹。一 基本概念1路徑: 從樹中一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成兩個結(jié)點之間的路徑。 2 路徑長度路徑上的分支數(shù)目稱為路徑長度。 （a） (b) (c)3 樹的路徑長度從樹根到每一個結(jié)點的路徑長度之和稱為樹的路徑

22、長度。(a) 2+2+2+2=8 (b) 3+3+1+2=9 (c) 1+2+3+3=94 結(jié)點的帶權(quán)路徑長度從該結(jié)點到樹根之間的路徑長度與結(jié)點上權(quán)的乘積。5 樹的帶權(quán)路徑長度樹中所有葉子結(jié)點的帶權(quán)路徑長度之和。6 赫夫曼樹帶權(quán)路徑長度WPL 最小的二叉樹稱為最優(yōu)二叉樹或赫夫曼樹。二 赫夫曼樹的構(gòu)造( 1)根據(jù)給定的n 個權(quán)值 w1， w2， ， wn 構(gòu)成n 棵二叉樹的集合F T1， T2， ， Tn， 其中每棵二叉樹Ti 中只有一個帶權(quán)wi的根結(jié)點( xi )， 其左子樹和右子樹均為空；( 2)在F 中選取兩棵根結(jié)點的權(quán)值最小的二叉樹作為左右子樹構(gòu)造一棵新的二叉樹， 且置新的二叉樹的根結(jié)點

23、的權(quán)值為其左、右子樹上根結(jié)點的權(quán)值之和；( 3)在F 中刪除上面選中的那兩棵根結(jié)點權(quán)值最小的二叉樹， 同時將新得到的二叉樹加入F 中；( 4)重復步驟(2 )和(3)， 直到F 中只含一棵樹為止。赫夫曼算法說明( 1)在選取兩棵根結(jié)點權(quán)值最小的二叉樹時， 出現(xiàn)權(quán)值相同的情況時， 可以在相同權(quán)值的二叉樹中選取一棵；( 2)當兩棵根結(jié)點的權(quán)值最小的二叉樹組成新的二叉樹的左子樹和右子樹時， 誰左誰右沒有規(guī)定；( 3)在赫夫曼樹中， 權(quán)值越大的葉子結(jié)點離根越近；( 4)在赫夫曼樹中沒有度為1 的結(jié)點， 根據(jù)二叉樹性質(zhì)n0 n2+1，可以推得n 個葉子結(jié)點的赫夫曼樹共有2n-1 個結(jié)點。8， 6， 2，

24、 4構(gòu)造赫夫曼樹的過程三 赫夫曼編碼7， 19， 2， 6， 32， 3， 21， 1 0WPLHF=7×4+19×2+2×5+6×4+32×2+3×5+21×2+10×4=261WPLEQ=(7+19+2+6+32+3+21+10)×3=300頻數(shù)719263232110哈夫曼編碼11010001000010011110001011011哈夫曼編碼20010100000000010100001110111等長編碼000001010011100101110111第七章 圖7.1 基本概念圖， 有向圖， 無

25、向圖， 端點和鄰接點， 起點和終點， 度、出度和入度， 完全圖， 稠密圖和稀疏圖， 權(quán)和網(wǎng)， 路徑、路徑長度和簡單路徑，回路或環(huán)，子圖，連通圖和連通分量，強連通圖和強連通分量，生成樹。圖由兩個集合V 和E 組成， 記為G =(V， E)， 其中V 是頂點集合， E是V 中頂點偶對(即邊)的集合。用n 表示圖中頂點數(shù)目， e 表示圖中邊或弧的數(shù)目。有n (n-1)/ 2 條邊的無向圖稱為完全圖； 有n(n-1 )條邊的有向圖稱為有向完全圖。有很少條邊或弧(如e<nlog n)的圖稱為稀疏圖，反之稱為稠密圖。v0， v1， ， vn -1， vn無向圖: ( vi， vj ) E有向圖: &

26、lt; vi， vj > E當v0=vn 時此路徑稱為一條簡單回路。與圖的邊或弧相關的數(shù)叫做權(quán)， 帶權(quán)的圖稱為網(wǎng)。連通： 若從頂點vi 到頂點vj 有路徑， 則稱vi 和vj 是連通的。若無向圖圖中任兩點是連通的則稱為連通圖。n 個頂點的連通圖最少有n-1條邊， 最多n (n-1)/2 條邊。強連通圖： 有向圖中，對任兩點vi，vj(v i vj)， 存在從vi 到vj和vj 到vi 的路徑。n 個頂點的強連通圖最少有n 條邊， 最多有n( n-1)條邊。生成樹是一個連通圖的極小連通子圖，它含有圖中全部頂點，但只有足以構(gòu)成一棵二叉樹的n- 1 條邊， 沒有回路。有n- 1 條邊的圖不一定

27、是生成樹。(a) 無向非連通圖G3 (b)G3的3個連通分量 無向非連通圖G3和它的3個連通分量( a)有向非連通圖G 1 (b)G2 的兩個強連通分量有向非連通圖G2 和它的兩個強連通分量(a)連通圖 (b)連通圖的生成樹之一連通圖的生成樹生成森林(staning-fores t)：如果一個有向圖恰有一個頂點的入度為0，其余頂點的入度均為1，則是一棵有向樹。一個有向圖的生成森林由若干棵有向樹組成， 含有圖中全部頂點， 但是只有足以構(gòu)成若干棵不相交的有向樹的弧。(a)有向圖G4 ( b)G4 的生成森林有向圖的生成森林7.2圖的存儲表示1 數(shù)組表示法(鄰接矩陣)鄰接矩陣(adja cency

28、matrix )是圖的一種順序存儲結(jié)構(gòu)。如果圖G (V， E)是無權(quán)圖， 則圖G 的鄰接矩陣定義為： (a)有向圖G1 及其他的鄰接矩陣 (b)無向圖G2 及其他的鄰接矩陣圖的鄰接矩陣如果圖G 是帶權(quán)圖， 則圖G 的鄰接矩陣定義為：網(wǎng)的鄰接矩陣無向圖: nTD(vi) O D(vi)+ ID(vi) A ijj=1有向圖: n nTD(vi) Ai j+ A ijj=1 i=1二 鄰接表表示法鄰接表(Adjacency li st)是圖的一種鏈式存儲結(jié)構(gòu)， 既適用于無向圖又適用于有向圖。1 鄰接表的定義( 1)在鄰接表中， 對圖中的每一個頂點建立一個單鏈表， 第i 個單鏈表中的結(jié)點表示依附于頂

29、點v i 的邊(對有向圖是以頂點v i 為尾的弧)。如果無向圖中有n 個頂點、e 條邊， 則它的鄰接表需要n 個頭結(jié)點和2e 個表結(jié)點。(a) 無向圖G2 及鄰接表(b) 有向圖G1 及鄰接表圖的鄰接表表示(a)有向圖G1 (b) G1 的逆鄰接表有向圖G1 及逆鄰接表三 十字鏈表表示法十字鏈表(orthogonal list )是有向圖的另一種鏈式存儲結(jié)構(gòu)。是將有向圖的鄰接表和逆鄰接表結(jié)合起來得到的一種鏈表。在十字鏈表中，有向圖中每一條弧用一個結(jié)點表示，每個頂點也用一個結(jié)點表示。有向圖的十字鏈表四 鄰接多重表表示法鄰接多重表(Adjacency Multi list )是無向圖的另一種鏈式存

30、儲結(jié)構(gòu)。無向圖G2 的鄰接多重表7.3 圖的遍歷從圖中某一頂點出發(fā)訪遍圖中其余頂點，且使每一個頂點僅被訪問一次。這一過程稱為圖的遍歷。1 深度優(yōu)先搜索DFS (De pt h_F irst Se ar ch)從圖中某個頂點v0 出發(fā)，訪問此頂點，然后依次從v0 的未被訪問的鄰接點出發(fā)深度優(yōu)先搜索遍歷圖，直到圖中所有和v0 有路徑相通的頂點都被訪問到： 若此時圖中尚有頂點未被訪問， 則另選圖中一個未曾被訪問的頂點作始點，重上述過程，直到圖中所有頂點都被訪問到為止。若用鄰接矩陣作存儲結(jié)構(gòu)， 則時間復雜度為O( n2)若用鄰接表作存儲結(jié)構(gòu)， 則時間復雜度為O(n+e)v1 v2 v 4 v8 v5

31、v 3 v6 v72 廣度優(yōu)先搜索BF S(B rea dt h F irs t S ear ch )從圖中某頂點v0 出發(fā)，在訪問v0 之后依次訪問v0 的各個未曾訪問過的鄰接點， 并使“ 先被訪問的頂點的鄰接點” 先于“ 后被訪問的頂點的鄰接點”被訪問，直至圖中所有已被訪問的頂點的鄰接點都被訪問到；然后分別從這些鄰接點出發(fā)廣度優(yōu)先搜索遍歷圖， 直到圖中所有已被訪問的頂點的鄰接點都被訪問到， 若此時圖中尚有頂點未被訪問， 則另選圖中一個未曾被訪問的頂點作起始點， 重復上述過程直到圖中所有頂點都被訪問到為止。v1 v2 v 3 v4 v5 v 6 v7 v8遍歷圖的過程(a)無向圖G4 ; (

32、 b)深度優(yōu)先搜索的過程; (c)廣度優(yōu)先搜索的過程。7.4 圖的連通性1 (強)連通分量的確定2 最小(代價)生成樹MST(M inimum cos t Spannin g Tree )最小生成樹的性質(zhì)： 假設N=(V， E)是一個連通網(wǎng)， U 是頂點集V的一個非空子集，若(u，v)是一條具有最小權(quán)值(代價)的邊，其中u U，v V-U， 則必存在一棵包含邊( u， v)的最小生成樹。普里姆(Pr im)算法：假設N=( V，E)是連通網(wǎng)，TE 是N 上最小生成樹中邊的集合。算法從U=u 0(u0 V), TE=開始，重復執(zhí)行下述操作：在所有u U， v V-U 的邊(u， v ) E 中找

33、一條代價最小的邊( u0,v0)并入集合TE， 同時v0 并入U， 直至U=V 為止。此時TE 中必有n-1 條邊，則T=(V， TE )為N 的最小生成樹。普里姆算法構(gòu)造最小生成樹的過程克魯斯卡爾(K ruskal )算法： 假設N =(V， E )是連通網(wǎng)， 則令最小生成樹的初始狀態(tài)為只有n 個頂點而無邊的非連通圖T=( V， )， 圖中每個頂點自成一個連通分量。在E 中選擇代價最小的邊， 若該邊依附的頂點落在T 中不同的連通分量上， 則將此邊加入到T 中， 否則舍去此邊而選擇下一條代價最小的邊。依次類推， 直至T 中所有頂點都在同一連通分量上為止。克魯斯卡爾算法構(gòu)造最小生成樹的過程普里姆

34、算法的時間復雜度為O(n 2)(與網(wǎng)中邊數(shù)無關)， 適用于求邊稠密的網(wǎng)的最小生成樹。而克魯斯卡爾算法的時間復雜度為O(elog 2e)，適用于求邊稀疏的網(wǎng)的最小生成樹。第八章 查找8.1基本概念查找表是由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合。對查找表經(jīng)常進行的操作有：(1) 查詢某個“ 特定的” 數(shù)據(jù)元素是否在查找表中；(2) 檢索某個“ 特定的” 數(shù)據(jù)元素的各種屬性；(3) 在查找表中插入一個數(shù)據(jù)元素；(4) 從查找表中刪去某個數(shù)據(jù)元素。關鍵字(ke y)： 數(shù)據(jù)元素(或記錄)中某個數(shù)據(jù)項的值， 用它可以標識(識別)一個數(shù)據(jù)元素(或記錄)。若此關鍵字可以惟一地標識一個記錄，則稱此關鍵字為主

35、關鍵字； 反之稱用以識別若干記錄的關鍵字為次關鍵字。查找(或稱檢索)：根據(jù)給定的某個值，在查找表中確定一個其關鍵字等于給定值的記錄或數(shù)據(jù)元素。若表中存在這樣的一個記錄， 則稱查找是成功的；若表中不存在關鍵字等于給定值的記錄，則稱查找不成功。8.2 靜態(tài)查找表1 線性表的順序查找順序查找的過程就是從表的一端開始逐個進行記錄的關鍵字和給定值的比較， 直到查找成功或查找完整個表(不成功)。平均查找長度為( n+1)/22 有序表的查找有序表的查找方法有折半(或二分)查找。設查找范圍為lo w,high ，在l ow 與hig h 之間找一中點x (即mid)，即x (low+ hig) 2。把lo

36、w,high 分為三部分： l ow,x-1 、x、x+1,high 先用給定值ke y 與mi d 指定的值相比， 若相等， 則表示查找成功。若不相等， 此時存在如下兩種情況：( 1)key 值小于mid 所指的值，說明key 在low 和mid 之間，則令指針hig mid- 1， 在表的前半部分再取中間位置的記錄進行比較；( 2)key 值大于mid 所指的值，說明key 在mid 和hig 之間，則令指針low=mid+1， 在表的后半部分再取中間位置的記錄進行比較。如此反復進行， 直至找到或查完全表而查不到為止。記錄編號 1 2 3 4 5 6 7 8 9 10 11關鍵字值 5 1

37、3 19 21 37 56 64 75 80 88 92low mid higlow=1 mid=6 hig=11(a) 初始時(b) key=21 時查找成功 (c) key=85 時查找不成功一個有序表(1)初始時， low= 1,hig= 11,mid =(1+11 ) 2=6(2)當key=21 時，再令m id=(1+5 ) 2=3，rm id.ke y=19，則令low=3+1=4， 再令mid =(4+5) 2=4， rmid.ke y=21(3) 當k ey=85 時， 大于rmi d.key =5 6， 則令l ow=6+1 =7， 再令mid=(7+11) 2=9 ， rm

38、id. key=8 0 ， 則令low=9+1=10 ， 再令mid=(10+11 ) 2)=10， rmi d.key = 88， 令hig=m id-1=10 -1=9<l ow3 .分塊查找線性表及其索引表(R1,R2, ,R6)(R7,R8, ,R12 )(R13,R14, ,R 18)8.3 動態(tài)查找動態(tài)查找的特點是： 表結(jié)構(gòu)本身是在查找過程中動態(tài)生成。1 .二叉排序樹二叉排序樹T 是一棵二叉樹，它或者是空，或者具有下列3 個性質(zhì)：( 1)如果T 的根結(jié)點的左子樹非空， 它的左子樹所有結(jié)點的關鍵字均小于T 的根結(jié)點的關鍵字；( 2)如果T 的根結(jié)點的右子樹非空， 它的右子樹所有

39、結(jié)點的關鍵字均大于T 的根結(jié)點的關鍵字；( 3)T 的根結(jié)點的左子樹和右子樹也均是二叉排序樹。如果按照中序遍歷一棵二叉查找樹所得到的結(jié)點的序列是一個遞增序列。3,12,24,3 7,45,5 3,61,7 8,90,1 0045， 24， 53， 45， 12， 24， 90 二叉排序樹的構(gòu)造過程(a)空樹；(b)插入45；(c)插入24；(d)插入53；(e)插入12；(f)插入90。第九章 內(nèi)部排序91 排序的有關概念排序是將一個數(shù)據(jù)元素(或記錄)的任意序列，重新排列成一按關鍵字(或排序碼)有序的序列。若對于關鍵字相同的兩條記錄Ri 和Rj，經(jīng)排序后仍保持同樣的相對順序，則該排序方法是穩(wěn)定

40、的，否則是不穩(wěn)定的。內(nèi)部排序：指待排序記錄存放在計算機內(nèi)存中進行的排序。外部排序：指待排序記錄的數(shù)量很大，排序過程中需對外存進行訪問。一 直接插入排序直接插入排序( straig ht ins ertio n sort)一種最簡單的排序方法。( 1)算法思想： 逐個處理待排序列中的記錄， 將其與前面已經(jīng)排好序的子序中的記錄進行比較，確定要插入的位置，并將記錄插入到子序中。 開始時，把第 個記錄看成是已經(jīng)排好序的子序，這時子序中只有一個記錄； 從第 個記錄起到最后一個記錄，依次將記錄和前面子序中的記錄比較， 確定記錄插入的位置； 將記錄插入到子序中， 子序記錄個數(shù)加1， 直至子序長度和原來待排序

41、列長度一致時結(jié)束。直接插入排序示例二 折半插入排序例： 28， 1 3， 72， 85， 3 9， 41， 6， 20折半插入排序示例三 希爾排序1.算法思想先將n 個待排記錄序列分割成若干個子序列，然后對各子序列分別進行排序， 當整個序列中的記錄“ 基本有序” 時， 再對全體記錄進行一次直接插入排序。 取定一個正整數(shù)d1<n，把全部記錄按此間隔值，從第一個記錄起進行分組，所有距離為d1 倍數(shù)的記錄放一組中，在各組內(nèi)進行直接插入排序； 取定一個正整數(shù)d2<d1，重復上述分組和排序工作，直至取di 1為止。49 38 65 97 76 13 27 49 55 04取d1 n 2=4，

42、 di +1 di 2，排序過程如下：希爾排序示例 希爾排序是不穩(wěn)定的排序方法。9 .2 快速排序交換排序法， 其基本方法是： 兩兩比較待排序記錄的關鍵字，并交換不滿足順序要求的那些偶對， 直到全部滿足為止。一 起泡排序（ 冒泡排序）起泡排序(bubb le sor t)是一種簡單但是著名的交換排序方法。(1)算法思想。每次進行相鄰兩個元素關鍵字的比較， 如果不符合次序立即交換。 將第1 個記錄的關鍵字k1 和第2 個記錄的關鍵字k2 進行比較，若為逆序(即k1>k2)， 則將兩個記錄進行交換， 若為正序則保持原序； 將第2 個記錄的關鍵字k2 和第3 個記錄的關鍵字k3 進行比較，重復

43、上述排序過程，直到第n-1 個記錄和第n 個記錄的關鍵字進行比較、交換為止； 這樣從(k1,k2)到(kn -1,kn)的n-1 次比較和交換(即上述 和 )的排序過程稱做第一趟起泡排序； 進行第2 趟起泡排序，對前n-1 個記錄進行同樣的操作，其結(jié)果是使得關鍵字次大的記錄被安置到第n- 1 個記錄的位置上；依此類推，第i 趟冒泡排序是從第1 個記錄到第n-i +1 個記錄之間依次比較和交換。重復以上過程直到?jīng)]有記錄需要交換為止。49 38 65 97 76 13 27 49起泡排序的過程示意圖起泡排序是穩(wěn)定的。二 快速排序快速(qu ick so rt)， 又稱分區(qū)交換排序法。1 算法思想。

44、每一步都要把待排序的表里的某個元素放到它在表中的最終位置， 同時在這個元素的前面和后面各形成一個子表， 在前子表中的所有元素的關鍵字都比這個元素的關鍵字小， 而在后子表中的都比它大， 則可以分別對這兩部分記錄繼續(xù)進行排序， 直到最后每個子表都只有一個元素， 以達到整個序列有序。49 38 65 97 76 13 27 49快速排序的過程示意圖快速排序是不穩(wěn)定的。9 .3 選擇排序法選擇排序法的基本思想是： 每一趟在n-i+1( i 1， 2， ， n-1)個記錄中選取關鍵字最小的記錄， 順序放在已排序的記錄序列的最后， 作為有序序列中第i 個記錄， 直到全部排序完成。一 簡單選擇排序（ 直接選

45、擇排序）簡單選擇排序的基本思想是：設n 個待排序的記錄存放在L.r 1.n中， 對n 個待排序記錄進行n-1 趟掃描： 第一趟掃描選出n 個記錄中關鍵字值最小的記錄， 并與L.r 1記錄交換位置； 第二趟掃描選出余下的n-1 個記錄中關鍵字值次最小的記錄，并與L.r2記錄交換位置；依此類推， 直至第n-1 趟掃描結(jié)束， 所有記錄有序為止。33 25 46 13 58 95 18 63簡單選擇排序的過程示意圖直接選擇排序是不穩(wěn)定的。二 樹型選擇排序樹型選擇排序的基本思想是：( 1)把n 個記錄的關鍵字值兩兩比較， 將其中關鍵字值較小的n/ 2個記錄取出來作為第一步比較的結(jié)果保存下來， 然后將這n/2 個關鍵字進行兩兩比較， 繼續(xù)選擇具有較小關鍵字值的記錄， 直至選出一個最小關鍵字值；( 2)對余下的n -1 個記錄的關鍵字值進行第二趟兩兩比較， 再選出一個次小的關鍵字； 如此反復， 直至