數(shù)據(jù)結(jié)構(gòu)（Java版）課件 呂云翔 第4、5章 串和數(shù)組、樹形結(jié)構(gòu)

第2章串和數(shù)組

目錄2串的基本概念、抽象描述和分類串的模式匹配數(shù)組的概念、特性、遍歷特殊矩陣的壓縮存儲4.14.24.34.4總結(jié)4.54.1串的基本概念、抽象描述和分類4.1.1串的基本概念4順序存儲字符串線性表字符串也叫串，是由字符組成的有限序列，是一種常用的非數(shù)值數(shù)據(jù)。串的邏輯結(jié)構(gòu)是線性表，串是一種特殊的線性表，其每個數(shù)據(jù)元素都是一個字符。但是串的操作特點與線性表不同，主要是對子串進(jìn)行操作，通常采用順序存儲結(jié)構(gòu)存儲。字符串可以表示為str="a0a1…ai…an-1"，其中str為串名，也叫串變量；i為字符ai在串中的位序號；雙引號中的字符序列稱為串值；n為串的長度；當(dāng)n=0時字符串不包含任何字符，為空串；當(dāng)字符串由一個或多個空白字符組成時為空白串。串變量4.1.1串的基本概念5字符串中任意個連續(xù)字符組成的子序列稱為字符串的子串，此字符串為該子串的主串。子串在主串中的位置是指子串在主串中第一次出現(xiàn)時的第一個字符在主串中的位置。空串是任意串的子串，每個字符串都是其自身的子串，除自身外，主串的其他子串稱為主串的真子串。串的比較規(guī)則和字符的比較規(guī)則有關(guān)，字符的比較規(guī)則由所屬的字符集的編碼決定。兩個串相等是指串長度相同并且各對應(yīng)位置上的字符也相同。兩個串的大小由對應(yīng)位置上的首個不同字符的大小決定，字符比較次序是從頭開始依次向后。當(dāng)兩個串的長度不等而對應(yīng)位置上的字符都相同時較長的串定義為較大。4.1.2串的抽象數(shù)據(jù)類型描述6字符串是數(shù)據(jù)元素類型為字符的線性表，其抽象數(shù)據(jù)類型描述與線性表相似，又根據(jù)串在實際問題中的應(yīng)用抽象出串的基本操作，可得串的抽象數(shù)據(jù)類型Java語言描述如左邊所示。4.1.2串的抽象數(shù)據(jù)類型描述7字符串的抽象數(shù)據(jù)類型Java抽象類包含了串的主要基本操作，如果要使用這個接口，還需要具體的類來實現(xiàn)。串的Java抽象類的實現(xiàn)方法主要有以下兩種：(1)基于順序存儲的實現(xiàn)，為順序串；(2)基于鏈?zhǔn)酱鎯Φ膶崿F(xiàn)，為鏈串。4.1.3順序串81.順序串的描述：順序串與順序表的邏輯結(jié)構(gòu)相同，存儲結(jié)構(gòu)類似，均可用數(shù)組來存儲數(shù)據(jù)元素。但串具有獨特的不同于線性表的操作，屬于特殊類型的線性表。下圖所示為順序串。4.1.3順序串9實現(xiàn)IString抽象類的順序串類的Java語言描述如下：4.1.3順序串10實現(xiàn)IString抽象類的順序串類的Java語言描述如下：4.1.3順序串11實現(xiàn)IString抽象類的順序串類的Java語言描述如下：4.1.3順序串12實現(xiàn)IString抽象類的順序串類的Java語言描述如下：4.1.3順序串13實現(xiàn)IString抽象類的順序串類的Java語言描述如下：4.1.3順序串142.順序串基本操作的實現(xiàn)

順序串有許多基本操作，例如，求子串操作、插入操作、刪除操作、連接操作、比較操作。

下面，我們對這幾個操作逐個使用Java實現(xiàn)。4.1.3順序串151)求子串操作求子串操作subString(begin,end)是返回長度為n的字符串中位序號從begin到end-1的字符序列，其中0≤begin≤n-1，begin<end≤n。其主要步驟如下：(1)檢查參數(shù)begin和end是否滿足0≤begin≤n-1和begin<end≤n，若不滿足，拋出異常。(2)返回位序號為begin到end-1的字符序列。代碼如左圖所示4.1.3順序串162)插入操作插入操作insert(i,str)是在長度為n的字符串的第i個元素之前插入串str，其中0≤i≤n。其主要步驟如下：(1)判斷參數(shù)i是否滿足0≤i≤n，若不滿足，則拋出異常。(2)重新分配存儲空間為n+m，m為插入的字符串str的長度。(3)將第i個及之后的數(shù)據(jù)元素向后移動m個存儲單元。(4)將str插入到字符串從i開始的位置。4.1.3順序串173)刪除操作刪除操作delete(begin,end)是將長度為n的字符串的位序號為begin到end-1的元素刪除，其中參數(shù)begin和end滿足0≤begin≤curLen-1和begin<end≤curLen。其主要步驟如下：(1)判斷參數(shù)begin和end是否滿足0≤begin≤curLen-1和begin<end≤curLen，若不滿足，則拋出異常。(2)將字符串位序號為end的數(shù)據(jù)元素及其之后的數(shù)據(jù)元素向前移動到位序號為begin的位置。(3)字符串長度減小end-begin。4.1.3順序串184)連接操作5)比較操作4)concat(str)是將串str插入到字符串的尾部，此時調(diào)用insert(curLen,str)即可實現(xiàn)。5)比較操作compareTo(str)是將字符串與串str按照字典序進(jìn)行比較。若當(dāng)前字符串較大，返回1；若相等，返回0。若當(dāng)前字符串較小，返回-1。其主要步驟如下：(1)確定需要比較的字符的個數(shù)n為兩個字符串長度的較小值。(2)從下標(biāo)0至n-1依次進(jìn)行比較。4.1.3順序串19【例4.1】編寫一個程序，完成構(gòu)造串、判斷串是否為空、返回串的長度、求子串等操作。示例答案：4.1.4鏈串20鏈串的描述：鏈串采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，和線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)類似，可以采用單鏈表存儲串值。鏈串由一系列大小相同的結(jié)點組成，每個結(jié)點用數(shù)據(jù)域存放字符，指針域存放指向下一個結(jié)點的指針。與線性表不同的是每個結(jié)點的數(shù)據(jù)域可以是一個字符或者多個字符。若每個結(jié)點的數(shù)據(jù)域為一個字符，這種鏈表稱為單字符鏈表；若每個結(jié)點的數(shù)據(jù)域為多個字符，則稱為塊鏈表。在塊鏈表中每個結(jié)點的數(shù)據(jù)域不一定被字符占滿，可通過添加空字符或者其他非串值字符來簡化操作。如圖所示為兩種不同類型的鏈串。4.1.4鏈串21鏈串的優(yōu)缺點：在串的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，單字符鏈表的插入、刪除操作較為簡單，但存儲效率低。塊鏈表雖然存儲效率較高但插入、刪除操作需要移動字符，較為復(fù)雜。此外，與順序串相比，鏈串需要從頭部開始遍歷才能訪問某個位置的元素。所以用戶在應(yīng)用中需要根據(jù)實際情況選擇合適的存儲結(jié)構(gòu)。4.2串的模式匹配4.2串的模式匹配2301020304GOAL串的模式匹配也叫查找定位，指的是在當(dāng)前串中尋找模式串的過程，主要的模式匹配算法有BruteForce算法和KMP算法。4.2.1BruteForce算法24BruteForce算法從主串的第一個字符開始和模式串的第一個字符進(jìn)行比較，若相等，則繼續(xù)比較后續(xù)字符；否則從主串的第二個字符開始重新和模式串進(jìn)行比較。依此類推，直到模式串的每個字符依次與主串的字符相等，匹配成功。4.2.1BruteForce算法25BruteForce算法的實現(xiàn)簡單，但效率非常低。m為模式串的長度，n為主串的長度。（1）最好情況：第一次匹配即成功，比較次數(shù)為模式串的長度m，時間復(fù)雜度為O(m)。（2）最壞情況：每次匹配比較至模式串的最后一個字符，并且比較了目標(biāo)串中所有長度為m的子串，此時的時間復(fù)雜度為O(m×n)。缺點：每次匹配沒有利用前一次匹配的比較結(jié)果，使算法中存在較多的重復(fù)比較，降低了算法的效率；如果利用部分字符匹配的結(jié)果，可將算法的效率提高。因此提出了KMP算法，在下一節(jié)進(jìn)行介紹。4.2.2KMP算法261.算法分析設(shè)主串為s="ababcabdabcabca"、模式串為p="abcabc"，指針i、j分別指示主串和模式串所比較字符的位序號。當(dāng)某次匹配不成功時有si≠pj，并且si-jsi-j+1…si-1=p0p1…pj-1。此時需要尋找前綴子串p0p1…pk-1=pj-kpj-k+1…pj-1，其中0<k<j，這時候即滿足si-ksi-k+1…si-1=p0p1…pk-1，下一次匹配可直接比較si和pk。此外，為了減少比較次數(shù)，k應(yīng)取最大值，即p0p1…pk-1應(yīng)為滿足此性質(zhì)的最長前綴子串。若k不存在，下一次匹配則直接比較si和p0。4.2.2KMP算法272.K值的計算通過前面的分析已知，每次模式串開始比較的位置（即k的值）僅與模式串本身有關(guān)。一般用next[j]來表示pj對應(yīng)的k值。初始時可定義next[0]=-1，next[1]=0。設(shè)next[j]=k，則p0p1…pk-1=pj-kpj-k+1…pj-1，k為滿足等式的最大值。計算next[j+1]的值。(1)若pk=pj，則存在p0p1…pk-1pk=pj-kpj-k+1…pj-1pj，此時next[j+1]=k+1。(2)若pk≠pj，可以把計算next[j]的值的問題看成新的模式匹配過程，主串為p，模式串為p的前綴子串。出現(xiàn)不匹配，應(yīng)將模式串的比較位置變?yōu)閗′=next[k]，若pj=p_(k^')，則next[j+1]=k′+1=next[k]+1，否則繼續(xù)執(zhí)行步驟(2)，直到pj=pk，或者當(dāng)k=0并且pj≠pk時next[j+1]=0。4.2.2KMP算法282.K值的計算代碼實現(xiàn)：4.2.2KMP算法293.KMP算法步驟設(shè)主串的長度為n、模式串的長度為m，求next[]的時間復(fù)雜度為O(m)。在KMP中，因主串的下標(biāo)不需要回退，比較次數(shù)最多為n-m+1，所以KMP算法的時間復(fù)雜度為O(m+n)。KMP算法的主要步驟如下。(1)計算模式串的next[]函數(shù)值。(2)i為主串的比較字符位序號，j為模式串的比較字符位序號。當(dāng)字符相等時，i、j分別加1后繼續(xù)比較；否則i的值不變，j=next[j]，繼續(xù)比較。(3)重復(fù)步驟(2)，直到j(luò)等于模式串的長度時匹配成功，否則匹配失敗。4.2.2KMP算法303.KMP算法步驟小測試：請計算str=“abcababc”的next[j]的值

參考答案：當(dāng)j=0時，next[0]=-1;當(dāng)j=1時，next[1]=0;當(dāng)j=2時，next[2]=0;當(dāng)j=3時，next[3]=0;當(dāng)j=4時，next[4]=1;當(dāng)j=5時，next[5]=2;當(dāng)j=6時，next[6]=1;當(dāng)j=7時，next[7]=2。4.3數(shù)組的概念、特性和遍歷4.3.1數(shù)組的基本概念數(shù)組是n個具有相同數(shù)據(jù)類型的數(shù)據(jù)元素構(gòu)成的集合，數(shù)組元素按某種次序存儲在地址連續(xù)的存儲單元中,是順序存儲的隨機(jī)存儲結(jié)構(gòu)。數(shù)組元素在數(shù)組中的位置稱為數(shù)組元素的下標(biāo)，用戶通過下標(biāo)可以訪問相應(yīng)的數(shù)組元素。數(shù)組下標(biāo)的個數(shù)是數(shù)組的維數(shù)，具有一個下標(biāo)的數(shù)組叫一維數(shù)組，具有兩個下標(biāo)的數(shù)組叫二維數(shù)組。一維數(shù)組的邏輯結(jié)構(gòu)是線性表，多維數(shù)組是線性表的擴(kuò)展。二維數(shù)組可以看成數(shù)組元素是一維數(shù)組的數(shù)組。下圖所示為二維數(shù)組的矩陣表示。4.3.1數(shù)組的基本概念二維數(shù)組中的每個數(shù)據(jù)元素ai,j都受到兩個關(guān)系的約束，即行關(guān)系和列關(guān)系。ai.,j+1是ai,j在行關(guān)系中的后繼元素；ai+1,j是ai,j在列關(guān)系中的后繼元素。因為二維數(shù)組可以看成數(shù)組元素是一維數(shù)組的數(shù)組，所以二維數(shù)組也可看成線性表，即A=(a0,a1,…,an-1)，其中每個數(shù)據(jù)元素ai是一個列向量的線性表，即ai=(a0i,a1i,…,am-1i);或者表述為A=(a0,a1,…,am-1)，其中每個數(shù)據(jù)元素ai是一個行向量的線性表，即ai=(a0i,a1i,…,an-1i)。其中，每個元素同時屬于兩個線性表，第i行的線性表和第j列的線性表，具體可以分析如下：（1）a0,0是起點，沒有前驅(qū)元素；am-1,n-1是終點，沒有后繼元素。（2）邊界元素ai,0和a0,j（1≤j<n,1≤i<m）只有一個前驅(qū)元素；ai,n-1和am-1,j（0≤j<n-1,1≤i<m-1）只有一個后繼元素。（3）ai,j（1≤j<n-1,1≤i<m-1）有兩個前驅(qū)元素和兩個后繼元素。4.3.2數(shù)組的特性數(shù)組元素被存放在一組地址連續(xù)的存儲單元里，并且每個數(shù)據(jù)元素的大小相同，故只要已知首地址和每個數(shù)據(jù)元素占用的內(nèi)存單元大小即可求出數(shù)組中任意數(shù)據(jù)元素的存儲地址。對于一維數(shù)組A[n]，數(shù)據(jù)元素的存儲地址為Loc(i)=Loc(0)+i×L(0≤i<n)，其中Loc(i)是第i個元素的存儲地址，Loc(0)是數(shù)組的首地址，L是每個數(shù)據(jù)元素占用的字節(jié)數(shù)。對于二維數(shù)組，采用行優(yōu)先順序進(jìn)行存儲，即先存儲數(shù)組的第一行，再依次存儲其他各行。對于一個n×m的數(shù)組A[n][m]，數(shù)組元素的存儲地址為Loc(i,j)=Loc(0,0)+(i×m+j)×L，其中Loc(i,j)是第i行第j列的數(shù)組元素的存儲地址，Loc(0,0)是數(shù)組的首地址，L是每個數(shù)據(jù)元素占用的字節(jié)數(shù)。4.3.2數(shù)組的特性將計算數(shù)組元素的存儲位置的公式推廣到一般情況，可得n維數(shù)組A[m1][m2]…[mn]的數(shù)據(jù)元素的存儲位置：在n維數(shù)組中，計算數(shù)組中數(shù)據(jù)元素的存儲地址的時間復(fù)雜度為O(1)，n維數(shù)組是一種隨機(jī)存儲結(jié)構(gòu)。4.3.3數(shù)組的遍歷36行主序數(shù)組遍歷列主序?qū)ΧS數(shù)組進(jìn)行遍歷操作有兩種次序，即行主序和列主序。（1）行主序：以行序為主要次序，按行序遞增訪問數(shù)組的每行，同一行按列序遞增訪問數(shù)組元素。（2）列主序：以列序為主要次序，按列序遞增訪問數(shù)組的每列，同一列按行序遞增訪問數(shù)組元素。4.3.3數(shù)組的遍歷37SWOT舉例：請你設(shè)計一個算法，求二維數(shù)組A[n,n]的兩條對角線元素之和。答案示例：4.4特殊矩陣的壓縮存儲4.4特殊矩陣的壓縮存儲39在科學(xué)技術(shù)和工程計算的許多領(lǐng)域，矩陣是數(shù)值分析問題研究的對象。特殊矩陣是具有許多相同數(shù)據(jù)元素或者零元素且數(shù)據(jù)元素的分布具有一定規(guī)律的矩陣，例如對稱矩陣、三角矩陣和對角矩陣。數(shù)據(jù)壓縮技術(shù)是計算機(jī)軟件領(lǐng)域研究的一個重要問題，圖像、音頻、視頻等多媒體信息都需要進(jìn)行數(shù)據(jù)壓縮存儲。本節(jié)將以特殊矩陣為例介紹矩陣的壓縮存儲。矩陣采用二維數(shù)組進(jìn)行存儲，至少占用m×n個存儲單元。當(dāng)矩陣的階數(shù)很大時，矩陣所占用的存儲空間巨大，因此需要研究矩陣的壓縮存儲問題，根據(jù)不同矩陣的特點設(shè)計不同的壓縮存儲方法，節(jié)省存儲空間，同時保證采用壓縮存儲的矩陣仍然能夠正確地進(jìn)行各種矩陣運算。4.4特殊矩陣的壓縮存儲常用的矩陣壓縮存儲方法主要有以下兩種：(1)對于零元素分布有規(guī)律的特殊矩陣，采用線性壓縮或三角形的二維數(shù)組，只存儲有規(guī)律的部分元素。(2)對于零元素分布沒有規(guī)律的特殊矩陣，只存儲非零元素。下面，我們分別介紹一下不同類型的矩陣壓縮存儲方式4.4.1三角矩陣的壓縮存儲三角矩陣包括上三角矩陣和下三角矩陣。假如是一個n階矩陣，由n（n+1）/2個元素組成。當(dāng)i<j時矩陣中的數(shù)據(jù)元素滿足=0，矩陣為下三角矩陣；當(dāng)i>j時，矩陣中的數(shù)據(jù)元素滿足=0，矩陣為上三角矩陣。三角矩陣中具有近一半的分布有規(guī)律的零元素，所以三角矩陣采取只存儲主對角線以及上/下三角部分的矩陣元素的壓縮方法，主要分為以下兩種：線性壓縮存儲2.使用三角形的二維數(shù)組壓縮存儲4.4.1三角矩陣的壓縮存儲線性壓縮存儲將下三角矩陣的主對角線及其以下元素按行主序順序壓縮成線性存儲結(jié)構(gòu)，存儲元素的個數(shù)為n（n+1）/2，其中元素的存儲地址如下：其中，注意L為數(shù)據(jù)元素所占據(jù)存儲空間的字節(jié)數(shù)。計算各數(shù)據(jù)元素的存儲地址的時間復(fù)雜度為O（1）,三角矩陣的線性壓縮存儲結(jié)構(gòu)是隨機(jī)存儲結(jié)構(gòu)。4.4.1三角矩陣的壓縮存儲2.使用三角形的二維數(shù)組壓縮存儲三角形的二維數(shù)組實際上是一種動態(tài)數(shù)組結(jié)構(gòu)，第i行一維數(shù)組的長度為i+1，存儲在mat[i][j]中，如圖4.4所示。計算各數(shù)據(jù)元素的存儲地址的時間復(fù)雜度為O（1）,此壓縮存儲結(jié)構(gòu)是隨機(jī)存儲結(jié)構(gòu)。4.4.2對稱矩陣的壓縮存儲n階對稱矩陣是指一個n階矩陣中的數(shù)據(jù)元素滿足ai,j=aj,i。對稱矩陣在進(jìn)行壓縮存儲時只存儲主對角線和上/下部分?jǐn)?shù)據(jù)元素，即將對稱矩陣的主對角線及其上/下部分?jǐn)?shù)據(jù)元素按行主序順序壓縮成線性存儲，占用n（n+1）/2個存儲單元,矩陣元素的線性壓縮存儲地址為：4.4.3對角矩陣的壓縮存儲如果一個矩陣的所有非零元素都集中在以主對角線為中心的帶狀區(qū)域，則稱該矩陣為對角矩陣。它是一個n階矩陣，除了主對角線上的元素，其科元素均為0，則是主對角矩陣；除了主對角線上及主對角線上下各一個元素外，其余元素均為0，為三對角矩陣。在壓縮存儲對角矩陣時，只存儲主對角線及其兩側(cè)部分的元素。如壓縮存儲主對角矩陣，將主對角元素順序壓縮成線性存儲，存儲元素個數(shù)為n，矩陣數(shù)據(jù)元素的線性壓縮存儲地址為：4.4.4

稀疏矩陣的壓縮存儲稀疏矩陣是指矩陣中的非零元素個數(shù)遠(yuǎn)遠(yuǎn)小于矩陣元素個數(shù)并且非零元素的分布沒有規(guī)律的矩陣。設(shè)矩陣中有t個非零元素，非零元素占元素總數(shù)的比例稱為矩陣的稀疏因子，通常稀疏因子小于0.05的矩陣稱為稀疏矩陣。一般使用以下幾種方法進(jìn)行稀疏矩陣的壓縮存儲。稀疏矩陣的非零元素三元組稀疏矩陣的十字鏈表存儲4.4.4

稀疏矩陣的壓縮存儲稀疏矩陣的非零元素三元組稀疏矩陣的壓縮存儲原則是只存儲矩陣中的非零元素，而僅存儲非零元素是不夠的，必須存儲該元素在矩陣中的位置。矩陣元素的行號、列號和元素值稱為該元素的三元組。在Java語言中稀疏矩陣的三元組表示的結(jié)點結(jié)構(gòu)定義如下：4.4.4

稀疏矩陣的壓縮存儲稀疏矩陣的非零元素三元組稀疏矩陣的三元組順序表類的定義如下：4.4.4

稀疏矩陣的壓縮存儲2.稀疏矩陣的十字鏈表存儲當(dāng)稀疏矩陣中非零元素的位置或個數(shù)經(jīng)常發(fā)生變化時不宜采用三元組順序表存儲結(jié)構(gòu)，而應(yīng)該采用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示。十字鏈表是稀疏矩陣的另一種存儲結(jié)構(gòu)，在十字鏈表中稀疏矩陣的非零元素用一個結(jié)點來表示，每個結(jié)點由5個域組成。row域存放該元素的行號，column域存放該元素的列號，value域存放該元素的值，right域存放與該元素同行的下一個非零元素結(jié)點的指針，down域存放與該元素同列的下一個非零元素結(jié)點的指針。每個非零數(shù)據(jù)元素結(jié)點既是某個行鏈表中的一個結(jié)點，也是某個列鏈表中的結(jié)點，整個稀疏矩陣構(gòu)成了一個十字交叉的鏈表，這樣的鏈表就稱為十字鏈表。4.4.4

稀疏矩陣的壓縮存儲2.稀疏矩陣的十字鏈表存儲在Java語言中可以將稀疏矩陣的十字鏈表表示的結(jié)點結(jié)構(gòu)定義如下：稀疏矩陣的十字鏈表類的定義如右：4.4.4

稀疏矩陣的壓縮存儲2.稀疏矩陣的十字鏈表存儲在Java語言中可以將稀疏矩陣的十字鏈表表示的結(jié)點結(jié)構(gòu)定義如下：稀疏矩陣的十字鏈表類的定義如右：4.4.4

稀疏矩陣的壓縮存儲下面，我們做一個例題，來深入了解不同存儲結(jié)構(gòu)的優(yōu)缺點:已知A為稀疏矩陣，試從空間和時間角度比較采用二維數(shù)組和三元組順序表兩種不同的存儲結(jié)構(gòu)完成求運算的優(yōu)缺點。參考答案:設(shè)稀疏矩陣為m行n列，如果采用二維數(shù)組存儲，其空間復(fù)雜度為O(m×n)；因為要將所有的矩陣元素累加起來，所以需要用一個兩層的嵌套循環(huán)，其時間復(fù)雜度也為O(m×n)。如果采用三元組順序表進(jìn)行壓縮存儲，假設(shè)矩陣中有t個非零元素，其空間復(fù)雜度為O(t)，將所有的矩陣元素累加起來只需將三元組順序表掃描一遍，其時間復(fù)雜度也為O(t)。當(dāng)t<<m×n時采用三元組順序表存儲可獲得較好的時空性能。4.5總結(jié)4.5總結(jié)54(1)字符串是數(shù)據(jù)元素類型為字符的線性表，串具有插入、刪除、鏈接、查找、比較等基本操作。

(2)字符串具有順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)兩種存儲結(jié)構(gòu)。字符串的順序存儲結(jié)構(gòu)叫順序串，與順序表的邏輯結(jié)構(gòu)相同，存儲結(jié)構(gòu)類似，均可用數(shù)組來存儲數(shù)據(jù)元素。字符串的鏈?zhǔn)酱鎯Y(jié)構(gòu)叫鏈串，和線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)類似，可以采用單鏈表存儲串值。鏈串由一系列大小相同的結(jié)點組成，每個結(jié)點用數(shù)據(jù)域存放字符，指針域存放指向下一個結(jié)點的指針。

(3)串的模式匹配也叫查找定位，指的是在當(dāng)前串中尋找模式串的過程，主要的模式匹配算法有BruteForce算法和KMP算法。

4.5總結(jié)55(4)數(shù)組是n個具有相同數(shù)據(jù)類型的數(shù)據(jù)元素構(gòu)成的集合，數(shù)組元素按某種次序存儲在地址連續(xù)的存儲單元中，是一種隨機(jī)存儲結(jié)構(gòu)。

(5)特殊矩陣是具有許多相同數(shù)據(jù)元素或者零元素且數(shù)據(jù)元素的分布具有一定規(guī)律的矩陣，例如對稱矩陣、三角矩陣和對角矩陣。為了節(jié)省存儲空間，對矩陣進(jìn)行壓縮存儲。特殊矩陣的壓縮存儲方法是將呈現(xiàn)規(guī)律性分布的、值相同的多個矩陣元素壓縮存儲到一個存儲空間。

(6)稀疏矩陣是具有較多零元素，并且非零元素的分布無規(guī)律的矩陣。稀疏矩陣的壓縮存儲是只給非零數(shù)據(jù)元素分配存儲空間。

THEEND第5章樹形結(jié)構(gòu)目錄58樹二叉樹哈夫曼樹及哈夫曼編碼樹和森林第一節(jié)第二節(jié)第三節(jié)第四節(jié)第一節(jié)樹樹的基本概念60提出語義網(wǎng)絡(luò)是奎廉（J.R.Quillian）1968年在研究人類聯(lián)想記憶時提出的一種心理學(xué)模型。他認(rèn)為記憶是由概念間的聯(lián)系實現(xiàn)的。隨后在他設(shè)計的可教式語言理解器（TeachableLanguageComprehendent）中又把它用作為知識表示方法。1972年，西蒙（Simon）在他的自然語言理解系統(tǒng)中也采用了語義網(wǎng)絡(luò)知識表示法。1975年,亨德里克（GGHendrix）又對全稱量詞的表示提出了語義網(wǎng)絡(luò)分區(qū)技術(shù)。目前，語義網(wǎng)絡(luò)已經(jīng)成為人工智能中應(yīng)用較多的一種知識表示方法，尤其是在自然語言處理方面的應(yīng)用。1.1樹的基本概念61子樹根節(jié)點互不相交樹是數(shù)據(jù)元素之間具有層次關(guān)系的非線性結(jié)構(gòu)，是由n個結(jié)點構(gòu)成的有限集合，結(jié)點數(shù)為0的樹叫空樹。樹必須滿足以下條件。(1)有且僅有一個被稱為根的結(jié)點。(2)其余結(jié)點可分為m個互不相交的有限集合，每個集合又構(gòu)成一棵樹，叫根結(jié)點的子樹。與線性結(jié)構(gòu)不同，樹中的數(shù)據(jù)元素具有一對多的邏輯關(guān)系，除根結(jié)點以外，每個數(shù)據(jù)元素可以有多個后繼但有且僅有一個前驅(qū)，反映了數(shù)據(jù)元素之間的層次關(guān)系。樹是遞歸定義的。結(jié)點是樹的基本單位，若干個結(jié)點組成一棵子樹，若干棵互不相交的子樹組成一棵樹。遞歸1.1樹的基本概念62樹的表示方法有多種，如樹形表示法、文氏圖表示法、凹入圖表示法和廣義表表示法，如左圖。人們在生活中所見的家譜、Windows的文件系統(tǒng)等，雖然表現(xiàn)形式各異，在本質(zhì)上是樹結(jié)構(gòu)。右圖給出了樹的邏輯結(jié)構(gòu)示意圖。1.2樹的術(shù)語1.結(jié)點

樹的結(jié)點就是構(gòu)成樹的數(shù)據(jù)元素，就是其他數(shù)據(jù)結(jié)構(gòu)中存儲的數(shù)據(jù)項，在樹形表示法中用圓圈表示。2.結(jié)點的路徑

結(jié)點的路徑是指從根結(jié)點到該結(jié)點所經(jīng)過結(jié)點的順序排列。3.路徑的長度

路徑的長度指的是路徑中包含的分支數(shù)。4.結(jié)點的度

結(jié)點的度指的是結(jié)點擁有的子樹的數(shù)目。5.樹的度

樹的度指的是樹中所有結(jié)點的度的最大值。6.葉結(jié)點

葉結(jié)點是樹中度為0的結(jié)點，也叫終端結(jié)點。01020304GOAL1.2樹的術(shù)語7.分支結(jié)點

分支結(jié)點是樹中度不為0的結(jié)點，也叫非終端結(jié)點。8.子結(jié)點

子結(jié)點是指結(jié)點的子樹的根結(jié)點，也叫孩子結(jié)點。9.父結(jié)點

具有子結(jié)點的結(jié)點叫該子結(jié)點的父結(jié)點，也叫雙親結(jié)點。10.子孫結(jié)點

子孫結(jié)點是指結(jié)點的子樹中的任意結(jié)點。11.祖先結(jié)點

祖先結(jié)點是指結(jié)點的路徑中除自身之外的所有結(jié)點。12.兄弟結(jié)點兄弟結(jié)點是指和結(jié)點具有同一父結(jié)點的結(jié)點。01020304GOAL1.2樹的術(shù)語13.結(jié)點的層次

樹中根結(jié)點的層次為0，其他結(jié)點的層次是父結(jié)點的層次加1。14.樹的深度

樹的深度是指樹中所有結(jié)點的層次數(shù)的最大值加1。15.有序樹

有序樹是指樹的各結(jié)點的所有子樹具有次序關(guān)系，不可以改變位置。16.無序樹

無序樹是指樹的各結(jié)點的所有子樹之間無次序關(guān)系，可以改變位置。17.森林

森林是由多個互不相交的樹構(gòu)成的集合。給森林加上一個根結(jié)點就變成一棵樹，將樹的根結(jié)點刪除就變成森林。01020304GOAL第二節(jié)二叉樹2.1二叉樹的基本概念671.普通二叉樹

二叉樹是特殊的有序樹，它也是由n個結(jié)點構(gòu)成的有限集合。當(dāng)n=0時稱為空二叉樹。二叉樹的每個結(jié)點最多只有兩棵子樹，子樹也為二叉樹，互不相交且有左右之分，分別稱為左二叉樹和右二叉樹。

二叉樹也是遞歸定義的，在樹中定義的度、層次等術(shù)語同樣也適用于二叉樹。2.滿二叉樹

滿二叉樹是特殊的二叉樹，它要求除葉結(jié)點外的其他結(jié)點都具有兩棵子樹，并且所有的葉結(jié)點都在同一層上。3.完全二叉樹

完全二叉樹是特殊的二叉樹，若完全二叉樹具有n個結(jié)點，它要求n個結(jié)點與滿二叉樹的前n個結(jié)點具有完全相同的邏輯結(jié)構(gòu)。2.2二叉樹的性質(zhì)性質(zhì)1：二叉樹中第i層的結(jié)點數(shù)最多為2i。證明：當(dāng)i=0時只有一個根結(jié)點，成立；假設(shè)對所有的k(0≤k<i)成立，即第i-1層上最多有2i-1個結(jié)點，那么由于每個結(jié)點最多有兩棵子樹，在第i層上結(jié)點數(shù)最多為2i-1×2=2i個，得證。性質(zhì)2：深度為h的二叉樹最多有2h-1個結(jié)點。證明：由性質(zhì)1得，深度為h的二叉樹的結(jié)點個數(shù)最多為20+21+…+2h-1=2h-1，得證。性質(zhì)3：若二叉樹的葉結(jié)點的個數(shù)為n，度為2的結(jié)點個數(shù)為m，有n=m+1。證明：設(shè)二叉樹中度為1的結(jié)點個數(shù)為k，二叉樹的結(jié)點總數(shù)為s，有s=k+n+m。又因為除根結(jié)點外每個結(jié)點都有一個進(jìn)入它的分支，所以s-1=k+2*m。整理后得到n=m+1，得證。0102032.2二叉樹的性質(zhì)0405

2.2二叉樹的性質(zhì)

2.2二叉樹的性質(zhì)2.3二叉樹的存儲結(jié)構(gòu)1）二叉樹的順序存儲結(jié)構(gòu)二叉樹的順序存儲結(jié)構(gòu)是指將二叉樹的各個結(jié)點存放在一組地址連續(xù)的存儲單元中，所有結(jié)點按結(jié)點序號進(jìn)行順序存儲。因為二叉樹為非線性結(jié)構(gòu)，所以必須先將二叉樹的結(jié)點排成線性序列再進(jìn)行存儲，實際上是對二叉樹先進(jìn)行一次層次遍歷。二叉樹的各結(jié)點間的邏輯關(guān)系由結(jié)點在線性序列中的相對位置確定?？梢岳?.2節(jié)中的性質(zhì)5將二叉樹的結(jié)點排成線性序列，將結(jié)點存放在下標(biāo)為對應(yīng)編號的數(shù)組元素中。為了存儲非完全二叉樹，需要在樹中添加虛結(jié)點使其成為完全二叉樹后再進(jìn)行存儲，這樣會造成存儲空間的浪費。2.3二叉樹的存儲結(jié)構(gòu)2）二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)

二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)是指將二叉樹的各個結(jié)點隨機(jī)存放在存儲空間中，二叉樹的各結(jié)點間的邏輯關(guān)系由指針確定。每個結(jié)點至少要有兩條鏈分別連接左、右孩子結(jié)點才能表達(dá)二叉樹的層次關(guān)系。根據(jù)指針域個數(shù)的不同，二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)又分為以下兩種：a.二叉鏈?zhǔn)酱鎯Y(jié)構(gòu)b.三叉鏈?zhǔn)酱鎯Y(jié)構(gòu)2.3二叉樹的存儲結(jié)構(gòu)a.二叉鏈?zhǔn)酱鎯Y(jié)構(gòu)

二叉樹的每個結(jié)點設(shè)置兩個指針域和一個數(shù)據(jù)域。數(shù)據(jù)域中存放結(jié)點的值，指針域中存放左、右孩子結(jié)點的存儲地址。

采用二叉鏈表存儲二叉樹，每個結(jié)點只存儲了到其孩子結(jié)點的單向關(guān)系，沒有存儲到其父結(jié)點的關(guān)系，因此要獲得父結(jié)點將花費較多的時間，需要從根結(jié)點開始在二叉樹中進(jìn)行查找，所花費的時間是遍歷部分二叉樹的時間，且與查找結(jié)點所處的位置有關(guān)。b.三叉鏈?zhǔn)酱鎯Y(jié)構(gòu)

二叉樹的每個結(jié)點設(shè)置3個指針域和一個數(shù)據(jù)域。數(shù)據(jù)域中存放結(jié)點的值，指針域中存放左、右孩子結(jié)點和父結(jié)點的存儲地址。2.3二叉樹的存儲結(jié)構(gòu)2）二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)下圖所示為二叉鏈?zhǔn)酱鎯腿骀準(zhǔn)酱鎯Φ慕Y(jié)點結(jié)構(gòu)。

兩種鏈?zhǔn)酱鎯Y(jié)構(gòu)各有優(yōu)缺點，二叉鏈?zhǔn)酱鎯Y(jié)構(gòu)空間利用率高，而三叉鏈?zhǔn)酱鎯Y(jié)構(gòu)既便于查找孩子結(jié)點，又便于查找父結(jié)點。在實際應(yīng)用中，二叉鏈?zhǔn)酱鎯Y(jié)構(gòu)更加常用，因此本書中二叉樹的相關(guān)算法都是基于二叉鏈?zhǔn)酱鎯Y(jié)構(gòu)設(shè)計的。2.3二叉樹的存儲結(jié)構(gòu)3）二叉鏈?zhǔn)酱鎯Y(jié)構(gòu)的結(jié)點類的描述2.3二叉樹的存儲結(jié)構(gòu)4）二叉樹類的描述2.4二叉樹的遍歷1）二叉樹的遍歷方法

二叉樹通?？蓜澐譃?個部分，即根結(jié)點、左子樹和右子樹。根據(jù)3個部分的訪問順序不同，可將二叉樹的遍歷方法分為以下幾種。a.層次遍歷

自上而下、從左到右依次訪問每層的結(jié)點。b.先序遍歷

先訪問根結(jié)點，再先序遍歷左子樹，最后先序遍歷右子樹。c.中序遍歷

先中序遍歷左子樹，再訪問根結(jié)點，最后中序遍歷右子樹。d.后序遍歷

先后序遍歷左子樹，再后序遍歷右子樹，最后訪問根結(jié)點。2.3二叉樹的遍歷2）二叉樹遍歷操作實現(xiàn)的遞歸算法前序遍歷中序遍歷后序遍歷2.4二叉樹的遍歷3）二叉樹遍歷操作實現(xiàn)的非遞歸算法

二叉樹遍歷操作的遞歸算法結(jié)構(gòu)簡潔，易于實現(xiàn)，但是在時間上開銷較大，運行效率較低，為了解決這一問題，可以將遞歸算法轉(zhuǎn)換為非遞歸算法，轉(zhuǎn)換方式有以下兩種： a.使用臨時遍歷保存中間結(jié)果，用循環(huán)結(jié)構(gòu)代替遞歸過程； b.利用棧保存中間結(jié)果。

二叉樹遍歷操作實現(xiàn)的非遞歸算法利用棧結(jié)構(gòu)通過回溯訪問二叉樹的每個結(jié)點。2.4二叉樹的遍歷3）二叉樹遍歷操作實現(xiàn)的非遞歸算法A.先序遍歷

先序遍歷從二叉樹的根結(jié)點出發(fā)，沿著該結(jié)點的左子樹向下搜索，每遇到一個結(jié)點先訪問該結(jié)點，并將該結(jié)點的右子樹入棧。先序遍歷左子樹完成后再從棧頂彈出右子樹的根結(jié)點，然后采用相同的方法先序遍歷右子樹，直到二叉樹的所有結(jié)點都被訪問。其主要步驟如下:

(1)將二叉樹的根結(jié)點入棧。(2)若棧非空，將結(jié)點從棧中彈出并訪問。(3)依次訪問當(dāng)前訪問結(jié)點的左孩子結(jié)點，并將當(dāng)前結(jié)點的右孩子結(jié)點入棧。(4)重復(fù)步驟(2)和(3)，直到棧為空。2.3二叉樹的存儲結(jié)構(gòu)3）二叉樹遍歷操作實現(xiàn)的非遞歸算法A.先序遍歷2.4二叉樹的遍歷3）二叉樹遍歷操作實現(xiàn)的非遞歸算法B.中序遍歷

中序遍歷從二叉樹的根結(jié)點出發(fā)，沿著該結(jié)點的左子樹向下搜索，每遇到一個結(jié)點就使其入棧，直到結(jié)點的左孩子結(jié)點為空。再從棧頂彈出結(jié)點并訪問，然后采用相同的方法中序遍歷結(jié)點的右子樹，直到二叉樹的所有結(jié)點都被訪問。其主要步驟如下:

(1)將二叉樹的根結(jié)點入棧。(2)若棧非空，將棧頂結(jié)點的左孩子結(jié)點依次入棧，直到棧頂結(jié)點的左孩子結(jié)點為空。(3)將棧頂結(jié)點彈出并訪問，并使棧頂結(jié)點的右孩子結(jié)點入棧。(4)重復(fù)步驟(2)和(3)，直到棧為空。2.3二叉樹的存儲結(jié)構(gòu)3）二叉樹遍歷操作實現(xiàn)的非遞歸算法B.中序遍歷2.4二叉樹的遍歷3）二叉樹遍歷操作實現(xiàn)的非遞歸算法C.后序遍歷

后序遍歷從二叉樹的根結(jié)點出發(fā)，沿著該結(jié)點的左子樹向下搜索，每遇到一個結(jié)點需要判斷其是否為第一次經(jīng)過，若是則使結(jié)點入棧，后序遍歷該結(jié)點的左子樹，完成后再遍歷該結(jié)點的右子樹，最后從棧頂彈出該結(jié)點并訪問。后序遍歷算法的實現(xiàn)需要引入兩個變量，一個為訪問標(biāo)記變量flag，用于標(biāo)記棧頂結(jié)點是否被訪問，若flag=true，證明該結(jié)點已被訪問，其左子樹和右子樹已經(jīng)遍歷完畢，可繼續(xù)彈出棧頂結(jié)點，否則需要先遍歷棧頂結(jié)點的右子樹；一個為結(jié)點指針t,指向最后一個被訪問的結(jié)點，查看棧頂結(jié)點的右孩子結(jié)點，證明此結(jié)點的右子樹已經(jīng)遍歷完畢，棧頂結(jié)點可出棧并訪問。其主要步驟如下:

(1)將二叉樹的根結(jié)點入棧，t賦值為空。(2)若棧非空，將棧頂結(jié)點的左孩子結(jié)點依次入棧，直到棧頂結(jié)點的左孩子結(jié)點為空。(3)若棧非空，查看棧頂結(jié)點的右孩子結(jié)點，若右孩子結(jié)點為空或者與p相等，則彈出棧頂結(jié)點并訪問，同時使t指向該結(jié)點，并置flag為true；否則將棧頂結(jié)點的右孩子結(jié)點入棧，并置flag為false。(4)若flag為true，重復(fù)步驟(3)；否則重復(fù)步驟(2)和(3)，直到棧為空。2.3二叉樹的存儲結(jié)構(gòu)3）二叉樹遍歷操作實現(xiàn)的非遞歸算法C.后序遍歷2.5二叉樹遍歷算法的應(yīng)用1）二叉樹上的查找算法二叉樹上的查找是在二叉樹中查找值為x的結(jié)點，若找到返回該結(jié)點，否則返回空值，可以在二叉樹的先序遍歷過程中進(jìn)行查找，主要步驟如下：

(1)若二叉樹為空，則不存在值為x的結(jié)點，返回空值；否則將根結(jié)點的值與x進(jìn)行比較，若相等，返回該結(jié)點。(2)若根結(jié)點的值與x的值不等，則在左子樹中進(jìn)行查找，若找到，則返回該結(jié)點。(3)若沒有找到，則在根結(jié)點的右子樹中進(jìn)行查找，若找到，返回該結(jié)點，否則返回空值。2.5二叉樹遍歷算法的應(yīng)用1）二叉樹上的查找算法2.5二叉樹遍歷算法的應(yīng)用2）統(tǒng)計二叉樹的結(jié)點個數(shù)的算法二叉樹的結(jié)點個數(shù)等于根結(jié)點加上左、右子樹的結(jié)點的個數(shù)，可以利用二叉樹的先序遍歷序列，引入一個計數(shù)變量count，count的初值為0，每訪問根結(jié)點一次就將count的值加1，其主要操作步驟如下： (1)count值初始化為0。 (2)若二叉樹為空，返回count值。 (3)若二叉樹非空，則count值加1，

統(tǒng)計根結(jié)點的左子樹的結(jié)點個數(shù)，

并將其加到count中；

統(tǒng)計根結(jié)點的右子樹的結(jié)點個數(shù)，

并將其加到count中。。2.5二叉樹遍歷算法的應(yīng)用3）求二叉樹的深度二叉樹的深度是所有結(jié)點的層次數(shù)的最大值加1，也就是左子樹和右子樹的深度的最大值加1，可以采用后序遍歷的遞歸算法解決此問題，其主要步驟如下： (1)若二叉樹為空，返回0。 (2)若二叉樹非空，

求左子樹的深度、求右子樹的深度。 (3)比較左、右子樹的深度，

取最大值加1即為二叉樹的深度。。2.6二叉樹的建立二叉樹遍歷操作可使非線性結(jié)構(gòu)的樹轉(zhuǎn)換成線性序列。先序遍歷序列和后序遍歷序列反映父結(jié)點和孩子結(jié)點間的層次關(guān)系，中序遍歷序列反映兄弟結(jié)點間的左右次序關(guān)系。因為二叉樹是具有層次關(guān)系的結(jié)點構(gòu)成的非線性結(jié)構(gòu)，并且每個結(jié)點的孩子結(jié)點具有左右次序，所以已知一種遍歷序列無法唯一確定一棵二叉樹，只有同時知道中序和先序遍歷序列，或者同時知道中序和后序遍歷序列，才能同時確定結(jié)點的層次關(guān)系和結(jié)點的左右次序，才能唯一確定一棵二叉樹。2.6二叉樹的建立1）由中序和先序遍歷序列建立二叉樹其主要步驟為如下： (1)取先序遍歷序列的第一個結(jié)點作為根結(jié)點，序列的結(jié)點個數(shù)為n。 (2)在中序遍歷序列中尋找根結(jié)點，其位置為i，可確定在中序遍歷序列中根結(jié)點之前的i個結(jié)點構(gòu)成的序列為根結(jié)點的左子樹中序遍歷序列，根結(jié)點之后的n-i-1個結(jié)點構(gòu)成的序列為根結(jié)點的右子樹中序遍歷序列。 (3)在先序遍歷序列中根結(jié)點之后的i個結(jié)點構(gòu)成的序列為根結(jié)點的左子樹先序遍歷序列，先序遍歷序列之后的n-i-1個結(jié)點構(gòu)成的序列為根結(jié)點的右子樹先序遍歷序列。 (4)對左、右子樹重復(fù)步驟(1)、(2)、(3)，確定左、右子樹的根結(jié)點和子樹的左右、子樹。 (5)算法遞歸進(jìn)行即可建立一棵二叉樹。2.6二叉樹的建立1）由中序和先序遍歷序列建立二叉樹假設(shè)二叉樹的先序遍歷序列為ABECFG、中序遍歷序列為BEAFCG,由中序和先序遍歷序列建立二叉樹的過程如圖所示：2.6二叉樹的建立1）由中序和先序遍歷序列建立二叉樹2.6二叉樹的建立9501從先序遍歷序列中依次讀取字符2）由標(biāo)明空子樹的先序遍歷序列創(chuàng)建二叉樹02若字符為#，建立空子樹03建立左子樹04建立右子樹2.6二叉樹的建立2）由標(biāo)明空子樹的先序遍歷序列創(chuàng)建二叉樹2.6二叉樹的建立97【例5.3】已知二叉樹的中序和后序序列分別為CBEDAFIGH和CEDBIFHGA，試構(gòu)造該二叉樹。解：二叉樹的構(gòu)造過程如下圖所示。圖(c)即為構(gòu)造出的二叉樹。第三節(jié)哈夫曼樹及哈夫曼編碼3.哈夫曼樹及哈夫曼編碼目前常用的圖像、音頻、視頻等多媒體信息由于數(shù)據(jù)量大，必須對它們采用數(shù)據(jù)壓縮技術(shù)來存儲和傳輸。數(shù)據(jù)壓縮技術(shù)通過對數(shù)據(jù)進(jìn)行重新編碼來壓縮存儲，以便減少數(shù)據(jù)占用的存儲空間，在使用時再進(jìn)行解壓縮，恢復(fù)數(shù)據(jù)的原有特性。其壓縮方法主要有有損壓縮和無損壓縮兩種。有損壓縮是指壓縮過程中可能會丟失數(shù)據(jù)信息，如將BMP位圖壓縮成JPEG格式的圖像，會有精度損失；無損壓縮是指壓縮存儲數(shù)據(jù)的全部信息，確保解壓后的數(shù)據(jù)不丟失。哈夫曼編碼是數(shù)據(jù)壓縮技術(shù)中的無損壓縮技術(shù)。01020304GOAL3.哈夫曼樹及哈夫曼編碼3.1哈夫曼樹的基本概念3.2哈夫曼樹的構(gòu)造3.3哈夫曼編碼3.4構(gòu)造哈夫曼樹和哈夫曼編碼的類的描述3.1哈夫曼樹的基本概念1.結(jié)點間的路徑

結(jié)點間的路徑是指從一個結(jié)點到另一個結(jié)點所經(jīng)過的結(jié)點序列。從根結(jié)點到X結(jié)點有且僅

有一條路徑。2.結(jié)點的路徑長度

結(jié)點的路徑長度是指從根結(jié)點到結(jié)點的路徑上的邊數(shù)。3.結(jié)點的權(quán)

結(jié)點的權(quán)是指人給結(jié)點賦予的一個具有某種實際意義的數(shù)值。4.結(jié)點的帶權(quán)路徑長度

結(jié)點的帶權(quán)路徑長度是指結(jié)點的權(quán)值和結(jié)點的路徑長度的乘積。5.樹的帶權(quán)路徑長度

樹的帶權(quán)路徑長度是指樹的葉結(jié)點的帶權(quán)路徑長度之和。6.最優(yōu)二叉樹

最優(yōu)二叉樹是指給定n個帶有權(quán)值的結(jié)點作為葉結(jié)點構(gòu)造出的具有最小帶權(quán)路徑長度的

二叉樹。最優(yōu)二叉樹也叫哈夫曼樹。3.2哈夫曼樹的構(gòu)造給定n個葉結(jié)點，它們的權(quán)值分別是{w1,w2,…,wn}，構(gòu)造相應(yīng)的哈夫曼樹的主要步驟如下：

(1)構(gòu)造由n棵二叉樹組成的森林，每棵二叉樹只有一個根結(jié)點，根結(jié)點的權(quán)值分別為{w1,w2,…,wn}。(2)在森林中選取根結(jié)點權(quán)值最小和次小的兩棵二叉樹分別作為左子樹和右子樹去構(gòu)造一棵新的二叉樹，新二叉樹的根結(jié)點權(quán)值為兩棵子樹的根結(jié)點權(quán)值之和。(3)將兩棵二叉樹從森林中刪除，并將新的二叉樹添加到森林中。(4)重復(fù)步驟(2)和(3)，直到森林中只有一棵二叉樹，此二叉樹即為哈夫曼樹。假設(shè)給定的權(quán)值為{1，2，3，4，5}，右圖展示了哈夫曼樹的構(gòu)造過程。3.2哈夫曼樹的構(gòu)造【例5.4】對于給定的一組權(quán)值W＝(5，2，9，11，8，3，7)，試構(gòu)造相應(yīng)的哈夫曼樹，并計算它的帶權(quán)路徑長度。解：構(gòu)造的哈夫曼樹如下圖所示：

樹的帶權(quán)路徑長度如下：WPL=2×4+3×4+5×3+7×3+8×3+9×2+11×2=1203.3哈夫曼編碼01020304GOAL在傳送信息時需要將信息符號轉(zhuǎn)化成二進(jìn)制組成的符號串，一般每個字符由一個字節(jié)或兩個字節(jié)表示，即8或16個位數(shù)。為了提高存儲和傳輸效率，需要設(shè)計對字符集進(jìn)行二進(jìn)制編碼的規(guī)則，使得利用這種規(guī)則對信息進(jìn)行編碼時編碼位數(shù)最小，即需要傳輸?shù)男畔⒘孔钚?。哈夫曼編碼是一種變長的編碼方案，數(shù)據(jù)的編碼因其使用頻率的不同而長短不一，使用頻率高的數(shù)據(jù)其編碼較短，使用頻率低的數(shù)據(jù)其編碼較長，從而使所有數(shù)據(jù)的編碼總長度最短。各數(shù)據(jù)的使用頻率通過在全部數(shù)據(jù)中統(tǒng)計重復(fù)數(shù)據(jù)的出現(xiàn)次數(shù)獲得。又因為在編碼序列中若使用前綴相同的編碼來表示不同的字符會造成二義性，額外的分隔符號會造成傳