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

第2章串和數(shù)組

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

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

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

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

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

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

稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣的非零元素三元組稀疏矩陣的三元組順序表類(lèi)的定義如下：4.4.4

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2二叉樹(shù)的性質(zhì)

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

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

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

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

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

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

二叉樹(shù)通常可劃分為3個(gè)部分，即根結(jié)點(diǎn)、左子樹(shù)和右子樹(shù)。根據(jù)3個(gè)部分的訪(fǎng)問(wèn)順序不同，可將二叉樹(shù)的遍歷方法分為以下幾種。a.層次遍歷

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

先訪(fǎng)問(wèn)根結(jié)點(diǎn)，再先序遍歷左子樹(shù)，最后先序遍歷右子樹(shù)。c.中序遍歷

先中序遍歷左子樹(shù)，再訪(fǎng)問(wèn)根結(jié)點(diǎn)，最后中序遍歷右子樹(shù)。d.后序遍歷

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

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

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

先序遍歷從二叉樹(shù)的根結(jié)點(diǎn)出發(fā)，沿著該結(jié)點(diǎn)的左子樹(shù)向下搜索，每遇到一個(gè)結(jié)點(diǎn)先訪(fǎng)問(wèn)該結(jié)點(diǎn)，并將該結(jié)點(diǎn)的右子樹(shù)入棧。先序遍歷左子樹(shù)完成后再?gòu)臈ｍ攺棾鲇易訕?shù)的根結(jié)點(diǎn)，然后采用相同的方法先序遍歷右子樹(shù)，直到二叉樹(shù)的所有結(jié)點(diǎn)都被訪(fǎng)問(wèn)。其主要步驟如下:

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

中序遍歷從二叉樹(shù)的根結(jié)點(diǎn)出發(fā)，沿著該結(jié)點(diǎn)的左子樹(shù)向下搜索，每遇到一個(gè)結(jié)點(diǎn)就使其入棧，直到結(jié)點(diǎn)的左孩子結(jié)點(diǎn)為空。再?gòu)臈ｍ攺棾鼋Y(jié)點(diǎn)并訪(fǎng)問(wèn)，然后采用相同的方法中序遍歷結(jié)點(diǎn)的右子樹(shù)，直到二叉樹(shù)的所有結(jié)點(diǎn)都被訪(fǎng)問(wèn)。其主要步驟如下:

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

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

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

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

統(tǒng)計(jì)根結(jié)點(diǎn)的左子樹(shù)的結(jié)點(diǎn)個(gè)數(shù)，

并將其加到count中；

統(tǒng)計(jì)根結(jié)點(diǎn)的右子樹(shù)的結(jié)點(diǎn)個(gè)數(shù)，

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

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

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

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

有一條路徑。2.結(jié)點(diǎn)的路徑長(zhǎng)度

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

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

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

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

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

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

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

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