數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)資料.doc

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