數(shù)據結構期末復習資料.doc

數(shù)據結構期末復習材料第一章1、數(shù)據結構是一門研究非數(shù)值計算的程序設計問題中計算機的操作對象以及它們之間的關系和操作等的學科。數(shù)據結構(Data Structure)：相互之間存在一種或多種特定關系的數(shù)據元素的集合。2、數(shù)據結構的形式定義：二元組Data_Structure=(D,S) 其中，D是數(shù)據元素的有限集，S是D上關系的有限集。3、數(shù)據元素之間關系的映像：、順序映像(順序存儲結構)：以相對的存儲位置表示后繼關系。2、非順序映像(鏈式存儲結構)：借助指針元素存儲地址的指針表示數(shù)據元素之間的邏輯關系。任何一個算法的設計取決于數(shù)據(邏輯)結構，其實現(xiàn)取決于物理結構。4、 算法的定義：對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。特性：有窮性、確定性、可行性、輸入、輸出5、 算法的評價衡量算法優(yōu)劣的標準正確性(correctness):滿足具體問題的需求可讀性(readability)：易讀、易理解健壯性(robustness):當輸入數(shù)據非法時，算法能夠做出反應或進行處理效率與低存儲量:執(zhí)行時間短、存儲空間小第二章1、線性表是一種最簡單的線性結構。線性結構 是一個數(shù)據元素的有序（次序）關系特點：存在唯一的一個“第一個”的數(shù)據元素；存在唯一的一個“最后一個”的數(shù)據元素；除第一個數(shù)據元素外，均有唯一的前驅；除最后一個數(shù)據元素外，均有唯一的后繼2、線性表類型的實現(xiàn)順序映像 定義：用一組地址連續(xù)的存儲單元依次存放線性表中的數(shù)據元素。以“存儲位置相鄰”表示有序對，則有：LOC(ai) = LOC(ai-1) + l其中l(wèi)是一個數(shù)據元素所占存儲量LOC(ai) = LOC(a1) + (i-1)l特點：1、實現(xiàn)邏輯上相鄰物理地址相鄰2、實現(xiàn)隨機存取 3、若假定在線性表中任何一個位置上進行插入的概率都是相等的，則移動元素的期望值為：若假定在線性表中任何一個位置上進行刪除的概率都是相等的，則移動元素的期望值為：4、 線性表類型的實現(xiàn)鏈式映像 線性鏈表 特點：用一組地址任意的存儲單元存放線性表中的數(shù)據元素。5、在單鏈表中第 i 個結點之前進行插入的基本操作為：找到線性表中第i-1個結點，然后修改其指向后繼的指針。s = (LinkList) malloc ( sizeof (LNode); / 生成新結點s-data = e; s-next = p-next; p-next = s; / 插入在單鏈表中刪除第 i 個結點的基本操作為:找到線性表中第i-1個結點，修改其指向后繼的指針。q = p-next; p-next = q-next; e = q-data; free(q);5、 循環(huán)鏈表：最后一個結點的指針域的指針又指回第一個結點的鏈表。和單鏈表的差別僅在于： 判別鏈表中最后一個結點的條件不再是“后繼是否為空”，而是“后繼是否為頭結點”。6、 雙向鏈表的操作特點：1、“查詢” 和單鏈表相同；2、“插入” 和“刪除”時需要同時修改兩個方向上的指針“插入”：s-next = p-next; p-next = s; s-next-prior = s; s-prior = p;（s是插入的結點）刪除：p-next = p-next-next; p-next-prior = p;（要刪除的是p的下一個結點）課后作業(yè)P13: 2.3、2.5P15: 2.8、2.9(2)第三章1、棧、隊列的特點： 從數(shù)據元素間的邏輯關系看是線性表 從操作方式與種類看不同于線性表：棧與隊列是操作受限的線性表2、棧的基本概念 棧-是限制僅在線性表的一端進行插入和刪除運算的線性表。 棧頂（TOP）-允許插入和刪除的一端。 棧底（bottom)-不允許插入和刪除的一端。 空棧-表中沒有元素。棧-又稱為后進先出的線性表3、 棧中元素的特性：1、具有線性關系2、后進先出4、 棧的進棧出棧規(guī)則：a) 按序進棧：有n個元素1，2，,n，它們按1,2, , n的次序進棧(i進棧時，1(i-1)應該已經進棧)；b) 棧頂出棧：棧底最后出棧；c) 時進時出：元素未完全進棧時，即可出棧。5、棧的表示與實現(xiàn)順序棧 即棧的順序存儲結構：一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據元素。1、 附設一個棧底指針base，總是指向棧底。 2、 附設一個棧頂指針top。空棧時，top=base；非空棧時，總是指向棧頂元素1的位置。 插入一個棧頂元素，指針top增1； 刪除一個棧頂元素，指針top減1； 非空棧中的棧頂指針始終在棧頂元素的下一個位置上鏈棧 ：注意: 鏈棧中指針的方向指向前驅結點！6、隊列n 隊列：只允許在表的一端進行插入，而在表的另一端進行刪除的線性表。 隊尾(rear)允許插入的一端 隊頭(front)允許刪除的一端n 隊列特點：先進先出(FIFO)7、隊列類型的實現(xiàn)n 鏈隊列隊列的鏈式表示和實現(xiàn)n 順序隊列隊列的順序表示和實現(xiàn) 用一組連續(xù)的存儲單元依次存放隊列中的元素8、順序隊列運算時的頭、尾指針變化設兩個指針front,rear,約定：rear指示隊尾元素；front指示隊頭元素前一位置初值front=rear=0空隊列條件：Q.front=Q.rear隊列滿：Q.rear-Q.front=m入隊列： Q.baserear+=x;出隊列：x=Q.base+front;存在問題：設數(shù)組維數(shù)為M，則：n 當rear-front=m時，再有元素入隊發(fā)生溢出真溢出n 當rear已指向隊尾，但隊列前端仍有空位置時，再有元素入隊發(fā)生溢出假溢出！9、 循環(huán)隊列：將數(shù)組首尾相接（即：base0連在basem-1之后)。入/出隊列運算 利用“模運算”，則： 入隊：Q.rear=(Q.rear+1)%m 出隊：Q.front=(Q.front+1)%m隊滿和隊空判斷條件：少用一個元素空間： 隊空：Q.rear=(Q.front) 隊滿：(Q.rear+1)%m=Q.front10、 棧和隊列是限定插入和刪除只能在表的“端點”進行的線性表。a) 棧具有“后進先出”的特性；b) 隊列具有“先進先出”的特性。11、 棧的鏈式存儲不需頭結點。課后作業(yè)1. 用棧結構計算中綴式2+(4-3)*6，畫出計算過程棧的結構。2. 簡述以下算法的功能(棧和隊列的元素類型均為int)void algo3 (Queue &Q) Stack S; int d; InitStack(S); while (!QueueEmpty(Q) DeQueue(Q, d); Push(S, d); while (!StackEmpty(S) Pop(S, d); EnQueue(Q, d); 第四章一、1、串的基本概念n 串-由零個或多個字符組成的有限序列，一般記為：s=a1a2.an (n0)n 串中字符的個數(shù)n稱為串的長度；零個字符，即長度為零的串稱為空串，用或表示?？沾坏扔诳崭翊?，空格串：由一個或多個空格組成的串子串：串中任意個連續(xù)的字符組成的子序列主串：包含子串的串相應地稱為主串相等：兩個串的長度相等，并且對應位置的字符都相同。2、串結構與線性表結構的比較：邏輯結構：極為相似，區(qū)別僅在于串的數(shù)據對象約束為字符集。基本操作：有很大差別1、線性表大多以“單個元素”作為操作對象2、串通常以“串的整體”作為操作對象3、串類型定義4、 串賦值StrAssign、串復制Strcopy、串比較StrCompare、求串長StrLength、串聯(lián)接Concat以及求子串SubString等六種操作構成串類型的最小操作子集。 1、 StrAssign (&T, chars) 初始條件：chars 是字符串常量。操作結果：把 chars 賦為 T 的值。等價于C語言中的strset函數(shù)2、 StrCopy (&T, S) 初始條件：串 S 存在。操作結果：由串 S 復制得串 T。等價于C語言中的strcpy函數(shù)3、 StrCompare (S, T) 初始條件：串 S 和 T 存在。操作結果：若ST，則返回值0； 若ST，則返回值0； 若ST，則返回值0。等價于C語言中的strcmp函數(shù)(按ASCII碼值進行大小比較)4、 StrLength (S) 初始條件：串 S 存在。操作結果：返回 S 的元素個數(shù)，稱為串的長度。等價于C語言中的strlen函數(shù)5、 Concat (&T, S1, S2) 初始條件：串 S1 和 S2 存在。操作結果：用T返回由S1和S2聯(lián)接而成的新串。例如： Concate( T, man, kind) 求得 T = mankind 等價于C語言中的strcat函數(shù)6、 SubString (&Sub, S, pos, len) 初始條件：串S存在，1posStrLength(S) 且 0lenStrLength(S)-pos+1。 操作結果：用Sub返回串S的第pos個字符起長度為len的子串。子串為“串”中的一個字符子序列。例如：SubString( sub, commander, 4, 3)，求得sub = man；SubString( sub, commander, 1, 9)，求得sub = commander；SubString( sub, commander, 9, 1)，求得sub = r；起始位置pos和子串長度len之間存在約束關系，pos+len=StrLength(S)+1 SubString(student, 5, 0) = ? 長度為0的子串為“合法”串5、Index (S, T, pos) 初始條件：串S和T存在，T是非空串， 1posStrLength(S)。操作結果：若主串 S 中存在和串 T 值相同的子串, 則返回它在主串 S 中第pos個字符之后第一次出現(xiàn)的位置;否則函數(shù)值為0?！白哟谥鞔械奈恢谩敝缸哟械牡谝粋€字符在主串中的位序。假設 S = abcaabcaaabc, T = bca Index(S, T, 1) =2 Index(S, T, 3) = 6 Index(S, T, 8) = 0 6、Replace (&S, T, V) 初始條件：串S, T和V均已存在，且T是非空串。 操作結果：用 V 替換主串 S 中出現(xiàn)的所有與（模式串）T 相等的不重疊的子串。例如：假設 S = abcaabcaaabca，T = bca若 V = x， 則經置換后得到 S = abcaabcaaabca7、StrInsert (&S, pos, T) 初始條件：串S和T存在， 1posStrLength(S)1。操作結果：在串S的第pos個字符之前插入串T例如：S = chater，T = rac，則執(zhí)行 StrInsert(S, 4, T)之后得到S = cha racter二、串的表示和實現(xiàn)1、定長順序存儲表示：用一組地址連續(xù)的存儲單元存儲串值的字符序列，稱為順序串?？捎靡粋€數(shù)組來表示。特點：串的實際長度可在這個預定義長度的范圍內隨意設定，超過預定義長度的串值則被舍去，稱之為“截斷” 。按這種串的表示方法實現(xiàn)的串運算時，其基本操作為 “字符序列的復制”順序存儲結構中，串操作的基本操作為“字符序列的復制”，其時間復雜度基于復制的字符序列的長度。2、堆分配存儲表示：特點：仍以一組地址連續(xù)的存儲單元存放串值字符序列，但它們的存儲空間是在程序執(zhí)行過程中動態(tài)分配而得的。串操作實現(xiàn)的算法為：先為新生成的串分配一個存儲空間，然后進行串值的復制。3、串的模式匹配算法課堂練習已知：a=THIS, f=A SAMPLE, c=GOOD, d=NE, b= , 1、s=Concat(a, Concat(SubString(f, 2, 7), Concat(b, SubString(a, 3, 2),2、t=Replace(f, SubString(f, 3, 6), c),3、u=Concat(SubString(c, 3, 1), d), g=IS,4、v=Concat(s, Concat(b, Concat(t, Concat(b, u),試問：s, t, v, StrLength(s), Index(v, g), Index(u, g)各是什么？1、THIS SAMPLE IS 2、A GOOD 3、ONE 4、v=THIS SAMPLE IS A GOOD ONE課后作業(yè)P28：4.5(要求：寫出每一個函數(shù)執(zhí)行后的結果)1. 已知：s=(XYZ)+*，t=(X+Z)*Y。試利用聯(lián)接、求子串和置換等基本操作，將s轉化為t。SubString(&s1, s, 3, 1); YSubString(&s2, s, 6, 1); +SubString(&s3, s, 7, 1); *Replace(&s, s1, s2); (X+Z)+*Concat(&s4, s3, s1); *YConcat(&t, SubString(&s5, s, 1, 5), s4); (X+Z)*Y第五章本章小結n 數(shù)組的兩種存儲映像方式： 行序為主 列序為主n 特殊矩陣的壓縮存儲，關鍵要確定下標之間的映射關系式。n 稀疏矩陣的三元組順序表、行邏輯鏈接的順序存儲和十字鏈表存儲，它們分別應用于矩陣的不同運算中。要注意分析區(qū)別使用的場合。n 廣義表的遞歸定義和存儲結構。1、 數(shù)組-線性表的擴展，其表中的數(shù)據元素本身也是一個數(shù)據結構。2、數(shù)組的順序表示和實現(xiàn)數(shù)組類型的特點:只有引用型操作，沒有加工型操作(插入和刪除)，即不作插入和刪除操作數(shù)組是多維的結構，而存儲空間是一個一維的結構有兩種順序映象的方式：以行序為主序(低下標優(yōu)先) 二維數(shù)組A中任一元素ai,j 的存儲位置 LOC(i,j) = LOC(0,0) + (b2ij)L 其中LOC(0,0)稱為基地址或基址n維數(shù)組數(shù)據元素存儲位置的映象關系：LOC(j1, j2, ., jn ) = LOC(0,0,.,0) + ci ji 其中 cn = L，ci-1 = bi ci , 1 =0)個結點的有限集合，它或為空樹(n=0)，或由一個根結點和至多兩棵稱為根的左子樹和右子樹的互不相交的二叉樹組成。注：二叉樹中不存在度大于2的結點，并且二叉樹的子樹有左子樹和右子樹之分。2、 二叉樹的五種基本形態(tài)：空樹 只含根結點 右子樹為空樹 左子樹為空樹 左右子樹均不為空樹3、二叉樹的性質性質1 ：在二叉樹的第 i 層上至多有2i-1 個結點(i1)。其中2i-1為2的i-1次方性質2：深度為 k 的二叉樹上至多含 2k-1 個結點(k1)。其中2k-1為2的k次方減一性質3：對任何一棵二叉樹，若它含有n0 個葉子結點、n2 個度為2的結點，則必存在關系式：n0 = n2+1。證明：設二叉樹上結點總數(shù) n = n0 + n1 + n2， 二叉樹上分支總數(shù) b = n1+2n2， 而 b = n-1 = n0 + n1 + n2 1 由， n0 = n2 + 1 。除根結點外，其余結點都有一個分支進入，設b為分支總數(shù)，則n=b+1性質4：具有n個結點的完全二叉樹的深度為 log2n +1。 其中 log2n為不大于log2n的最大整數(shù)性質5：若對含 n 個結點的完全二叉樹從上到下且從左至右進行 1 至 n 的編號，則對完全二叉樹中任意一個編號為 i 的結點：(1)若 i=1，則該結點是二叉樹的根，無雙親，否則，編號為i/2的結點為其雙親結點；(2)若 2in，則該結點無左孩子，否則，編號為 2i 的結點為其左孩子結點；(3)若 2i+1n，則該結點無右孩子結點，否則，編號為2i+1 的結點為其右孩子結點。4、 兩類特殊的二叉樹：滿二叉樹：指的是深度為k且含有2k-1個結點的二叉樹。其中2k-1為2的k次方減一特點：是每一層上的結點數(shù)都是最大結點數(shù)。完全二叉樹：樹中所含的 n 個結點和滿二叉樹中編號為 1 至 n 的結點一一對應。特點：葉子結點只可能在層次最大的兩層出現(xiàn)；對任一結點，若其右分支下的子孫的最大層次為l，則其左分支下的子孫的最大層次為l或l+1。n 性質練習：1. 一棵二叉樹在其第五層中有17個結點，可不可能？第i層上至多有2i-1個結點，則25-1=16。所以，不可能。2. 二叉樹的根結點屬于第0層還是屬于第1層？第1層3. 已知一棵二叉樹有20個結點，其中6個結點為葉子，則該樹中度為2的結點數(shù)為 5 ？度為0的結點為 6 ？由性質3：n0=n2+1，則n2=n0-1=6-1=5。4. 已知一棵完全二叉樹中編號為101的結點有LC和RC結點，則其LC結點編號為 202 ，RC結點編號為 203 ？由性質5，可知左孩子為2i，右孩子為2i+15. 一棵深度為h的完全k叉樹，如果按層次自頂向下、同一層自左向右、順序從1開始對全部結點進行編號，試問：該樹上最多有多少個結點？最少有多少個結點？由性質1和定義，可知除第h層外，其余各層都是滿的，所以：1+k+k2+.+kh-2=(kh-1-1)/(k-1)，則最多有： (kh-1-1)/(k-1)+kh-1=(kh-1)/(k-1)；最少有：(kh-1-1)/(k-1)+1三、二叉樹的存儲結構1、順序存儲結構：特點：一組地址連續(xù)的存儲單元存儲各結點(定義一個一維數(shù)組)；自根而下、自左而右存儲結點；按完全二叉樹上的結點位置進行編號和存儲。缺點：空間利用率太低！2、 鏈式存儲結構：二叉鏈表：結點結構至少包含：數(shù)據域和左右孩子指針域 lchild data rchild三叉鏈表：結點結構至少包含：數(shù)據域 、左右孩子指針域 、雙親指針 parent lchild data rchild四、遍歷二叉樹和線索二叉樹1、遍歷二叉樹：順著某一條搜索路徑巡訪二叉樹中的結點，使得每個結點均被訪問一次，而且僅被訪問一次?；静僮魇窃L問結點先(根)序的遍歷算法：若二叉樹為空樹，則空操作；否則， 訪問根結點；先序遍歷左子樹；先序遍歷右子樹。中(根)序的遍歷算法：若二叉樹為空樹，則空操作；否則，中序遍歷左子樹；訪問根結點；中序遍歷右子樹。后(根)序的遍歷算法：若二叉樹為空樹，則空操作；否則，后序遍歷左子樹；后序遍歷右子樹；訪問根結點。2、建立二叉樹的存儲結構：基本要點： 以“遍歷”為基本出發(fā)點；不同的遍歷方法相應地有不同的建立算法代碼如何由二叉樹的先序和中序序列建樹？3、 線索二叉樹指向該線性序列中的“前驅”和 “后繼” 的指針，稱作“線索”。包含“線索”的存儲結構，稱作“線索鏈表”。與其相應的二叉樹，稱作“線索二叉樹”遍歷二叉樹的結果是，求得結點的一個線性序列。線索化的實質是將二叉鏈表中的空指針改為指向前驅或著后續(xù)的線索，而前驅或者后續(xù)的信息只有在遍歷時才能得到，因而線索化的過程即為在遍歷的過程中修改空指針的過程。四、樹和森林1、樹的存儲結構雙親表示法：用一組連續(xù)空間存儲樹的結點，并附設一個指示器指示其雙親結點的位置。其中根節(jié)點的值為-1孩子鏈表表示法：樹結點表和 孩子結點表為了快速查找每個結點的孩子結點樹的二叉鏈表 (孩子-兄弟)存儲表示法：又稱二叉樹表示法，即以二叉鏈表作樹的存儲結構。鏈表中結點的兩個鏈域分別指向結點的第一個孩子結點和下一個兄弟結點。左邊孩子右邊兄弟與孩子兄弟鏈表對應的二叉樹：轉化后，二叉樹的右子樹必為空！2、森林與二叉樹的轉換給定一棵樹，可以找到惟一的一棵二叉樹與之對應。用二叉鏈表作為存儲結構（依據）把森林中第二棵樹的根結點看成第一棵樹的根結點的兄弟，即作為二叉樹的右子樹，則同樣可以導出森林和二叉樹的對應關系。注意：和樹對應的二叉樹，其左、右子樹的概念已改變?yōu)椋?左是孩子，右是兄弟。3、樹和森林的遍歷兩種遍歷樹的方法：先根(次序)遍歷：若樹不空，則先訪問根結點，然后依次先根遍歷各棵子樹。后根(次序)遍歷：若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結點。森林的遍歷：森林由三部分構成：森林中第一棵樹的根結點；森林中第一棵樹的子樹森林；森林中其它樹構成的森林。遍歷森林：先序遍歷：若森林不空，則訪問森林中第一棵樹的根結點；先序遍歷森林中第一棵樹的子樹森林；先序遍歷森林中(除第一棵樹之外)其余樹構成的森林。即：依次從左至右對森林中的每一棵樹進行先根遍歷。中序遍歷：若森林不空，則中序遍歷森林中第一棵樹的子樹森林；訪問森林中第一棵樹的根結點；中序遍歷森林中(除第一棵樹之外)其余樹構成的森林。即：依次從左至右對森林中的每一棵樹進行后根遍歷。五、哈夫曼樹及其應用1、最優(yōu)二叉樹(哈夫曼樹)結點的路徑長度：從根結點到該結點的路徑上分支的數(shù)目。樹的路徑長度：樹中每個結點的路徑長度之和。樹的帶權路徑長度：樹中所有葉子結點的帶權路徑長度之和 WPL(T) = wklk (對所有葉子結點)在所有含 n 個葉子結點、并帶相同權值的 m 叉樹中，必存在一棵其帶權路徑長度取最小值的樹，稱為“最優(yōu)樹”。2、 如何構造最優(yōu)樹？(赫夫曼算法) 以二叉樹為例：根據給定的 n 個權值 w1, w2, , wn，構造 n 棵二叉樹的集合F = T1, T2, , Tn，其中每棵二叉樹中均只含一個帶權值為 wi 的根結點，其左、右子樹為空樹；在 F 中選取其根結點的權值最小的兩棵二叉樹，分別作為左、右子樹構造一棵新的二叉樹，并置這棵新的二叉樹根結點的權值為其左、右子樹根結點的權值之和；從F中刪去這兩棵樹，同時加入剛生成的新樹；重復 (2) 和 (3) 兩步，直至 F 中只含一棵樹為止。3、采用二叉樹設計二進制前綴編碼規(guī)定：左分支用“0”表示；右分支用“1”表示。4、算法實現(xiàn)： 由于哈夫曼樹中沒有度為1的結點，則一棵有n個葉子結點的哈夫曼樹共有2n-1個結點（因n2=n0-1)，可以存儲在一個大小為2n-1的一維數(shù)組中。5、編碼需要從葉子到根；譯碼需要從根到葉子課后作業(yè)P38：6.5 P39：6.6(要求：寫出推導過程)1. 某二叉樹的先序遍歷結點訪問順序是abdgcefh，中序遍歷的訪問順序是dgbaechf，則其后序遍歷的結點訪問順序是（ ）。2. P41：6.23P41：6.23，然后將該樹轉化為對應的二叉樹。 6.26第七章 圖本章小結n 圖是一種復雜的非線性結構。n 圖的存儲表示方法：鄰接矩陣 鄰接表 十字鏈表有向圖 鄰接多重表無向圖n 圖的遍歷：深度優(yōu)先、廣度優(yōu)先n 圖的遍歷的應用：最小生成樹、拓撲排序及關鍵路徑、最短路徑等問題各種算法思想！一、圖的定義和基本術語1、圖的定義圖形結構：較線性表和樹更為復雜的數(shù)據結構。結點之間的關系是任意的，圖中任意兩個數(shù)據元素都可能相關。圖的結構定義：圖：是由一個頂點集 V 和一個頂點間的關系集合組成的數(shù)據結構。Graph = (V , VR)其中，V = x | x 某個數(shù)據對象，是頂點的有窮非空集合；2、頂點之間關系的有窮集合，也叫做邊(edge)或弧(Arc)集合。“弧”是有方向的，3、由頂點集和弧集構成的圖為有向圖。由頂點集和邊集構成的圖稱作無向圖基本術語有(無)向網：弧(邊)上帶權的圖假設圖中有n個頂點，e條邊，則含有 e=n(n-1)/2條邊的無向圖稱作完全圖；含有 e=n(n-1)條弧的有向圖稱作有向完全圖；若邊或弧的個數(shù) en-1時，則形成環(huán)；邊數(shù)n-1時則不連通五、最小生成樹構造網的一棵最小生成樹，即：在 e 條帶權的邊中選取 n-1 條邊（不構成回路），使“權值之和”為最小。1、普里姆算法：基本思想：第一步：取圖中任意一個頂點 v 作為生成樹的根；第二步：往生成樹上添加新的頂點 w。在添加的頂點 w 和已經在生成樹上的頂點v 之間必定存在一條邊，并且該邊的權值在所有連通頂點 v 和 w 之間的邊中取值最小；第三步：繼續(xù)往生成樹上添加頂點，直至生成樹上含有 n 個頂點為止。構造的最小生成樹不一定唯一，但最小生成樹的權值之和一定是相同的。2、 克魯斯卡爾算法：考慮問題的出發(fā)點: 為使生成樹上邊的權值之和達到最小，則應使生成樹中每一條邊的權值盡可能地小?；舅枷耄旱谝徊剑簶嬙煲粋€只含 n 個頂點的子圖 SG；第二步：從權值最小的邊開始，若它的添加不使SG 中產生回路，則在 SG 上加上這條邊；第三步：如此重復，直至加上 n-1 條邊為止比較兩種算法： 普里姆算法：O(n2)、適用于稠密圖 克魯斯卡爾算法：O(eloge)、適用于稀疏圖六、有向無環(huán)圖及其應用定義： 一個無環(huán)的有向圖稱作有向無環(huán)圖1、拓撲排序 檢查有向圖中是否存在回路的方法之一，是對有向圖進行拓撲排序。用頂點表示活動，用弧表示活動間的優(yōu)先關系的有向圖稱為頂點表示活動的網(Activity On Vertex Network)，簡稱AOV-網。在AOV-網中不應該出現(xiàn)有向環(huán)。對給定的AOV-網需首先判斷網中是否有環(huán)。如何進行拓撲排序？ 從有向圖中選取一個沒有前驅的頂點，并輸出之； 從有向圖中刪去此頂點以及所有以它為尾的??； 重復上述兩步，直至圖空，或者圖不空但找不到無前驅的頂點為止。在算法中需要用定量的描述替代定性的概念：沒有前驅的頂點 入度為零的頂點；刪除頂點及以它為尾的弧 弧頭頂點的入度減1。為避免每次都要搜索入度為零的頂點，在算法中設置一個“棧”，以保存“入度為零”的頂點2、關鍵路徑“關鍵活動”指的是：該弧上的權值增加將使有向圖上的最長路徑的長度增加。3、最短路徑從某頂點出發(fā)，沿圖的弧到達另一頂點所經過的路徑中，各邊上權值之和最小的一條路徑最短路徑。注意：和關鍵路徑區(qū)別！第八章 查找本章小結n 查找表是由同一類型的數(shù)據元素(或記錄)構成的集合。n 對查找表經常進行的操作：查詢 檢索 插入 刪去n 靜態(tài)查找表： 順序表 有序表：等概率：折半查找判定樹 不等概率：靜態(tài)樹表的查找次優(yōu)二叉查找樹n 動態(tài)查找表：二叉排序樹和平衡二叉樹 B-樹 哈希表查找的方法取決于查找表的結構一、靜態(tài)查找1、順序表的查找 以順序表表示靜態(tài)查找表, 稱為順序查找表?！吧诒钡淖饔茫好馊ゲ檎疫^程中每一步都要檢測整個表是否查找完畢。分析順序查找的時間性能：在等概率查找的情況下 ，順序表查找的平均查找長度為：當查找不成功的情況不能忽視時，且等概率情況下 =3(n+1)/42、有序表的查找n 折半查找 若以有序表表示靜態(tài)查找表，則查找過程可以基于“折半”進行。注意：折半查找只適用于有序表，且限于順序存儲結構！靜態(tài)樹表的查找n 在不等概率查找的情況下，折半查找不是有序表最好的查找方法。次優(yōu)二叉樹的構造方法 請看PPT第九章幻燈片203、動態(tài)查找表特點：表結構本身在查找過程中動態(tài)生成。二叉排序(查找)樹：或者是一棵空樹；或者是具有如下特性的二叉樹， 若它的左子樹不空，則左子樹上所有結點的值均小于根結點的值； 若它的右子樹不空，則右子樹上所有結點的值均大于根結點的值； 它的左、右子樹也都分別是二叉排序樹。如何構造二叉排序樹是重點 平衡二叉樹(又稱AVL樹) 樹中每個結點的左、右子樹深度之差(稱為平衡因子BF)的絕對值不大于1 AVL樹的平均查找長度和logn是同數(shù)量級的！B-樹 定義：是一種平衡的多路查找樹。一棵m階(結點的最大分支數(shù))的B-樹上：多叉樹的特性：非終端結點結構為：(n, A0 ,K1 ,A1 ,K2 , A2 ,K3 , A3 ,Kn , An )每個非終端結點可能含有： n 至多n個關鍵字Ki，n m-1；n 至少含有m/2-1個關鍵字Ki，即m/2-1n;n n+1個指向子樹的指針Ai(0in);查找樹的特性：非葉結點中的多個關鍵字均自小至大有序排列，即：K1 K2 Kn;且 Ai-1 所指子樹上所有關鍵字均小于Ki; Ai 所指子樹上所有關鍵字均大于Ki;平衡樹的特性：樹中所有葉子結點均不帶信息，且在樹中的同一層次上;根結點或為葉子結點，或至少含有兩棵子樹(至少有一個關鍵字);其余所有非葉結點均至少含有m/2棵子樹，至多含有 m 棵子樹;課堂練習1. 有一個長度為12的有序表R0.11，按折半查找法對表進行查找，在表中各元素等概率情況下查找成功所需的平均比較次數(shù)為 。2. 有一個有序表為1,3,9,12,32,41,45,62,75,77,82,95,99，當采用折半查找法查找關鍵字為82的元素時， 4 次比較后查找成功。構造判定樹如下：3. 順序查找含n個元素的順序表，若查找成功，則比較關鍵字的次數(shù)最多為 n 次；若查找不成功，則比較關鍵字的次數(shù)為 n+1 次。4. 如圖所示的二叉排序樹，其成功的平均查找長度是 ；不成功的平均查找長度是 。5. 一棵深度為k的平衡二叉樹，其每個非葉子結點的平衡因子均為0，則該樹共有 個結點。由于每個非葉子結點的平衡因子均為0，也即每個非終端結點都有左子樹和右子樹且高度相等；因此，這樣的AVL樹即為滿二叉樹，而高度為h的滿二叉樹的結點數(shù)為2h-1。則本題答案為2k-1。6.高度為5(除葉子層之外)的三階B-樹至少有 個結點。由m階B-樹性質可知：根結點至少有兩顆子樹、根結點之外的所有非葉子結點至少有m/2 棵子樹；則三階B-樹的形狀至少類似于一棵滿二叉樹，也即高度為5的三階B-樹至少有25-1=31個結點。本題答案為31。二、哈希表 這個是重點查找的過程為：給定值依次和關鍵字集合中各個關鍵字進行比較；查找的效率取決于和給定值進行比較的關鍵字個數(shù)建立關鍵字與記錄在表中的存儲位置之間的函數(shù)關系，以 f(key) 作為關鍵字為 key 的記錄在表中的位置，通常稱這個函數(shù)f(key)為哈希函數(shù)。關鍵要素：哈希函數(shù)H(key) 處理沖突的方法假設哈希表的地址集為0至(n-1)：沖突是指由關鍵字得到的哈希地址為j的位置上已存有記錄?！疤幚頉_突”就是為該關鍵字的記錄找到另一個“空”的哈希地址。n 開放定址法：為產生沖突的地址 H(key) 求得一個地址序列H0, H1, H2, , Hs 1 sm-1其中：H0 = H(key) Hi = ( H(key) + di ) MOD m， i=1, 2, , sn 鏈地址法：將所有哈希地址相同的記錄都鏈接在同一鏈表中。排序中的基本操作：比較關鍵字大小 和 移動記錄不同的具體實現(xiàn)方法導致不同的算法描述：直接插入排序(基于順序查找) 折半插入排序(基于折半查找) 表插入排序(