




已閱讀5頁,還剩13頁未讀, 繼續(xù)免費閱讀
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
數(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è)置一個“?!保员4妗叭攵葹榱恪钡捻旤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)致不同的算法描述:直接插入排序(基于順序查找) 折半插入排序(基于折半查找) 表插入排序(
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025屆內(nèi)蒙古巴彥淖爾市臨河區(qū)三中化學(xué)高一下期末綜合測試模擬試題含解析
- 河南禽類交易管理辦法
- 醫(yī)療項目預(yù)算管理辦法
- 民兵物資倉庫管理辦法
- 華為公司采購管理辦法
- 保利發(fā)展存貨管理辦法
- 地質(zhì)勘探與采礦工程
- 基于風(fēng)險分段的懲罰機制研究
- 公共娛樂設(shè)施管理辦法
- 合肥學(xué)校午餐管理辦法
- 糖尿病足的評估
- 2《永遇樂-京口北固亭懷古》公開課一等獎創(chuàng)新教學(xué)設(shè)計統(tǒng)編版高中語文必修上冊
- 短視頻素材購買合同
- DB11T 380-2024 橋面防水工程技術(shù)規(guī)程
- 第四單元整體教學(xué)設(shè)計-部編版語文八年級下冊
- 貴州省畢節(jié)市威寧縣2024年統(tǒng)編版小升初考試語文試卷(原卷版)
- 平安產(chǎn)險湖北省中央財政水稻種植保險條款
- 日語考試N5試題
- 農(nóng)商銀行考試題庫100題
- 小學(xué)學(xué)業(yè)生涯規(guī)劃與目標
- 2023年CQE客訴工程師年度總結(jié)及下年規(guī)劃
評論
0/150
提交評論