數(shù)據(jù)結(jié)構(gòu)與算法分析新視角（第2版） 課件 第4-6章 數(shù)組和串、樹、圖

內(nèi)容特殊的線性表多維數(shù)組與字符串Chapter

4DataStructuresandAlgorithmAnalysis主要內(nèi)容字符串的定義及存儲方法模式匹配方法字符串使用二維數(shù)組表示矩陣及運算三角矩陣、對稱矩陣、稀疏矩陣等各種壓縮存儲方法實現(xiàn)矩陣運算二維數(shù)組學習目標掌握多維數(shù)組的存儲結(jié)構(gòu)，熟悉特殊矩陣的壓縮存儲方法；熟悉稀疏矩陣三元組從順序表、行的單鏈表到十字鏈表等到多種存儲結(jié)構(gòu)的演變過程；了解串操作的應(yīng)用方法和特點，理解串匹配算法。數(shù)組與字符串4字符串字符串是基于數(shù)組的一種重要數(shù)據(jù)結(jié)構(gòu)數(shù)組數(shù)組是一組相關(guān)的同類型數(shù)據(jù)的集合，它們與實際應(yīng)用中數(shù)據(jù)的自然組織方法直接吻合，有著廣泛的用途。多維數(shù)組的概念在數(shù)值計算和圖形應(yīng)用方面非常有用數(shù)組在計算機中的連續(xù)存儲方式反映了內(nèi)存中數(shù)據(jù)組織的底層機制。數(shù)組與線性表的關(guān)系5線性關(guān)系運算受限元素擴展元素受限棧隊列串多維數(shù)組線性表、棧和隊列等，均是線性結(jié)構(gòu)，其中的數(shù)據(jù)元素是非結(jié)構(gòu)的原子類型。數(shù)組可以看成是線性表的擴展，即表中的元素本身也是一種數(shù)據(jù)結(jié)構(gòu)。數(shù)組與線性表的關(guān)系6線性關(guān)系運算受限元素擴展元素受限棧隊列串多維數(shù)組線性表、棧和隊列等，均是線性結(jié)構(gòu)，其中的數(shù)據(jù)元素是非結(jié)構(gòu)的原子類型。數(shù)組可以看成是線性表的擴展，即表中的元素本身也是一種數(shù)據(jù)結(jié)構(gòu)。4.1CONTENTS多維數(shù)組矩陣的壓縮存儲4.24.3字符串4.3本章小結(jié)4.1CONTENTS多維數(shù)組矩陣的壓縮存儲4.24.3字符串4.3本章小結(jié)關(guān)于數(shù)組的種種9數(shù)組簡單數(shù)組應(yīng)該是我們最熟悉的數(shù)據(jù)組織形式之一。由于數(shù)組中各元素具有統(tǒng)一的類型，并且數(shù)組元素的下標一般具有固定的上界和下界，因此，數(shù)組的處理比其他復雜的結(jié)構(gòu)更為簡單。數(shù)組與數(shù)據(jù)結(jié)構(gòu)各種數(shù)據(jù)結(jié)構(gòu)的順序存儲分配，也都是借用一維數(shù)組來描述它們的存儲結(jié)構(gòu)。數(shù)組的維多維數(shù)組是一維數(shù)組的推廣。

數(shù)組常見

幾乎所有的高級程序設(shè)計語言都包含數(shù)組這種數(shù)據(jù)的結(jié)構(gòu)形式。本節(jié)將從數(shù)據(jù)結(jié)構(gòu)的角度，簡單討論數(shù)組的邏輯結(jié)構(gòu)及其存儲方式。4.1多維數(shù)組4.1.14.1.2數(shù)組的概念數(shù)組的存儲結(jié)構(gòu)4.1多維數(shù)組4.1.14.1.2數(shù)組的概念數(shù)組的存儲結(jié)構(gòu)數(shù)組的概念12a11a12…a1n

a21a22…a2n

…………

am1am2…amn

Amxn=a11a12a1n

a21a22…a2n

………

am1am2amn

Amxn=（a）（b）Amxn=[[a11a12…a1n],[a21a22…a2n],…,[am1am2…amn]]（c）是由類型相同的數(shù)據(jù)元素構(gòu)成的集合，每個數(shù)據(jù)元素稱為一個數(shù)組元素（簡稱元素）。數(shù)組（Array）一個行向量形式的線性表一個列向量形式的線性表數(shù)組的特點13元素推廣性元素本身可以具有某種結(jié)構(gòu)，而不限定是單個的數(shù)據(jù)元素。元素同一性元素具有相同的數(shù)據(jù)類型。關(guān)系確定性每個元素均受n（n≥1）個線性關(guān)系的約束，元素個數(shù)和元素之間的關(guān)系一般不發(fā)生變動。如二維數(shù)組的元素有2個下標4.1多維數(shù)組4.1.14.1.2數(shù)組的概念數(shù)組的存儲結(jié)構(gòu)數(shù)組的存儲結(jié)構(gòu)1515二維數(shù)組順序存儲方式以行序為主序(低下標優(yōu)先)以列序為主序(高下標優(yōu)先)存得進取得出A計算機的存儲結(jié)構(gòu)是一維的，而數(shù)組一般是多維的，怎樣存放？思考與討論數(shù)組結(jié)構(gòu)特點16數(shù)目固定（1）數(shù)據(jù)元素數(shù)目固定，一旦定義了一個數(shù)組結(jié)構(gòu)，就不再有元素個數(shù)的增減變化。類型相同（2）數(shù)據(jù)元素具有相同的類型。關(guān)系固定（3）數(shù)據(jù)元素的下標關(guān)系具有上下界的約束且下標有序。數(shù)組基本運算17（1）給定一組下標，存取相應(yīng)的數(shù)據(jù)元素。（2）給定一組下標，修改相應(yīng)的數(shù)據(jù)元素中某個數(shù)據(jù)項的值。數(shù)組運算數(shù)組的順序存儲1819aij之前共有((i-1)*n+j-1)個元素基地址aij的存儲地址=Loc(aij

)=Loc(a11

)+((i-1)*n+j-1)*L數(shù)組的順序存儲2021aij

之前共有((j-1)*m+i-1)個元素基地址aij

的存儲地址=Loc(aij

)=

Loc(a11

)+((j-1)*m+i-1)*L數(shù)組的順序存儲和訪問22設(shè)數(shù)組a[1…60,1…70]的基地址為2048，每個元素占2個存儲單元，若以列序為主序順序存儲，求元素a[32,58]的存儲地址。注：a[1…60,1…70]是數(shù)組的一種表示方法，表示行優(yōu)先的二維數(shù)組，行下標范圍為1到60，列下標范圍為1到70。解：數(shù)組行數(shù)m=60-1+1=60；

列數(shù)n=70-1+1=70；行下標i=32;列下標j=58;元素長度L=2；列優(yōu)先元素求址公式Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*L得：LOC(a32,58)=2048+[(58-1)*60+(32-1)]*2＝8950i、j均從0開始，求址公式為Loc(aij)=Loc(a00)+[j*m+i)]*LLOC(a32,58)=2048+[58*60+32]*2＝9072例思考與討論若數(shù)組是a[0…59,0…69]，結(jié)果是否仍為8950？數(shù)組的順序存儲和訪問23Loc(aij)=Loc(a00)+[j*m+i)]*L4.1CONTENTS多維數(shù)組矩陣的壓縮存儲4.24.3字符串4.3本章小結(jié)特殊矩陣的存儲問題25數(shù)值分析計算中常常有高階矩陣 值相同元素或者零元素分布有一定規(guī)律的矩陣對稱矩陣上三角矩陣特殊矩陣如何高效存儲上述矩陣思考與討論節(jié)省存儲空間，節(jié)約傳輸時間例特殊矩陣的存儲問題26我們可以設(shè)想把相同的數(shù)據(jù)只存儲一次，來實現(xiàn)數(shù)據(jù)的壓縮存儲。節(jié)省存儲空間，節(jié)約傳輸時間。 值相同元素或者零元素分布有一定規(guī)律的矩陣特殊矩陣這在矩陣規(guī)模很大時（即高階矩陣），可獲得很高的效率。27【知識ABC】數(shù)據(jù)壓縮

數(shù)據(jù)壓縮是指在不丟失信息的前提下，縮減數(shù)據(jù)量以減少存儲空間，提高其傳輸、存儲和處理效率的一種技術(shù)方法。數(shù)據(jù)壓縮方法——去除掉確定的或可推知的信息，而保留不確定的信息。矩陣壓縮存儲時會有什么問題？可以采用的方法是什么？思考與討論A數(shù)據(jù)存儲數(shù)據(jù)恢復（1）相同的數(shù)據(jù)只存儲一次；（2）零元素不占存儲空間，數(shù)據(jù)存放到一維數(shù)組中找到同一元素在一維數(shù)組與矩陣中的對應(yīng)關(guān)系即可恢復原有的矩陣形式B矩陣壓縮存儲方法28確定存放壓縮后數(shù)據(jù)的向量的空間大??；確定二維數(shù)組下標i,j與向量下標k的關(guān)系。步驟1步驟2矩陣的壓縮存儲2929特殊矩陣的壓縮存儲稀疏矩陣的壓縮存儲三元組表的存儲結(jié)構(gòu)十字鏈表的存儲結(jié)構(gòu)4.2矩陣的壓縮存儲4.2.14.2.24.2.34.2.4對稱矩陣的壓縮存儲三角矩陣的壓縮存儲對角矩陣的壓縮存儲稀疏矩陣的壓縮存儲4.2矩陣的壓縮存儲4.2.14.2.24.2.34.2.4對稱矩陣的壓縮存儲三角矩陣的壓縮存儲對角矩陣的壓縮存儲稀疏矩陣的壓縮存儲32特殊矩陣壓縮存儲——對稱矩陣

在一個n階方陣A中，若元素滿足下述性質(zhì)，則稱A為對稱矩陣。

aij=aji(0≦i,j≦n-1)對稱矩陣用向量存儲，對稱矩陣元素可以只存儲下或上三角部分對稱矩陣壓縮存儲方法3334k等于aij前的元素個數(shù)（此處k的值從0開始）：k=1+2+3+...+i+j=i(1+i)/2+j（i≥j）4.2矩陣的壓縮存儲4.2.14.2.24.2.34.2.4對稱矩陣的壓縮存儲三角矩陣的壓縮存儲對角矩陣的壓縮存儲稀疏矩陣的壓縮存儲三角矩陣的壓縮存儲36上三角矩陣下三角矩陣除了存儲主對角線及上（下）三角中的元素外，再加一個存儲常數(shù)c的空間。三角矩陣壓縮存儲方法設(shè)n階方陣A，若其下三角的元素除對角線外均為常數(shù)c，即aij=c，0≤j<i<n，則稱該方陣為上三角矩陣。三角矩陣三角矩陣的壓縮存儲37三角矩陣中的重復元素c可只用一個存儲空間，其余的元素正好有n(n+1)/2個，因此，三角矩陣可壓縮存儲到長度為n(n+1)/2]+1的向量中，其中c存放在向量的最后一個位置下三角矩陣K值i、j關(guān)系a[i,j]=sa[k]i(i+1)/2+j當aij在下三角區(qū)域，i>=jcn(n+1)/2當aij在上三角區(qū)域，i<j下三角矩陣壓縮

4.2矩陣的壓縮存儲4.2.14.2.24.2.34.2.4對稱矩陣的壓縮存儲三角矩陣的壓縮存儲對角矩陣的壓縮存儲稀疏矩陣的壓縮存儲對角矩陣壓縮存儲39存儲所有非零元素對角矩陣壓縮存儲方法所有非零元素都集中在以主對角線為中心的帶狀區(qū)域中的方陣，也稱為帶型矩陣。對角矩陣三對角矩陣壓縮方法一40設(shè)有n階三對角矩陣A[n][n],將三條對角線上的元素逐行存放于數(shù)組B[M]中，使得B[k]=A[i][j],給出i、j與k的對應(yīng)關(guān)系。三對角矩陣壓縮方法一41三對角矩陣壓縮方法二42只存儲帶內(nèi)的元素4.2矩陣的壓縮存儲4.2.14.2.24.2.34.2.4對稱矩陣的壓縮存儲三角矩陣的壓縮存儲對角矩陣的壓縮存儲稀疏矩陣的壓縮存儲稀疏矩陣的壓縮存儲44設(shè)矩陣Amn中有s個非零元素，若s遠遠小于矩陣元素的總數(shù)（即s<<m×n），則稱A為稀疏矩陣（sparsematrix）。如何進行稀疏矩陣的壓縮存儲？討論一下稀疏矩陣令e=s/(m*n)，稱e為矩陣的稀疏因子。通常認為e≦0.05時稱之為稀疏矩陣矩陣的稀疏因子稀疏矩陣及其應(yīng)用45PageRank算法是用于標識網(wǎng)頁的等級/重要性的一種方法，是Google用來衡量一個網(wǎng)站好壞的唯一標準。PageRank算法首先要把各個網(wǎng)頁及網(wǎng)頁間的聯(lián)系存儲到計算機中，存儲可以用矩陣來實現(xiàn)（相關(guān)內(nèi)容見第6章）。由于互聯(lián)網(wǎng)上網(wǎng)頁的數(shù)量是巨大的，則這樣的矩陣元素是網(wǎng)頁數(shù)目的平方。如果我們假定有10億個網(wǎng)頁，那么這個矩陣就有100億億個元素。PageRank算法中要用到矩陣相乘，對應(yīng)這樣大的矩陣相乘，計算量是非常大的。PageRank算法的發(fā)明者LarryPage和SergeyBrin兩人利用稀疏矩陣計算的技巧，大大的簡化了計算量。簽名掃描圖，白色像素遠遠多于黑色像素PageRank算法稀疏矩陣的實例46電信總局到其各支局間的通信問題例雙面鑲邊的塊對角矩陣——稀疏矩陣用連線表示各局間有通信關(guān)系電信總局支局稀疏矩陣的壓縮存儲4747存儲所有非零元素稀疏矩陣壓縮存儲原則前面講述的各種特殊矩陣，其非零元素的分布都是有規(guī)律的，因此總能找到一種方法將它們壓縮存儲到一個向量中，并且一般都能找到矩陣中的元素與該向量的對應(yīng)關(guān)系，通過這個關(guān)系，仍能對矩陣的元素進行隨機存取。稀疏矩陣非零元素分布無規(guī)律，如何進行壓縮存儲？記位置，記值稀疏矩陣的壓縮存儲4848稀疏矩陣常用壓縮存儲形式位置下標、元素值帶行指針向量的單鏈表表示法十字鏈表法三元組表1鏈表存儲2稀疏矩陣存儲——三元組表49三元組表存稀疏矩陣中各非零元的值、行列位置和矩陣的行列數(shù)三元組表存儲原則稀疏矩陣的壓縮存儲——三元組順序表【例4-3】用三元組表的形式存儲稀疏矩陣。解：設(shè)稀疏矩陣為M[6,7]，為方便管理，可以把矩陣的行、列、非零元素個數(shù)信息，專門用三元組的第0行來記錄。50稀疏矩陣的壓縮存儲——三元組順序表51matrix[MAX]0矩陣行數(shù)矩陣列數(shù)非零元個數(shù)1行下標列下標非零元素值2行下標列下標非零元素值…MAX-1行下標列下標非零元素值matrix[0]用于存儲矩陣行數(shù)、列數(shù)、非零元個數(shù)structnode{introw,col;//非零元素的行下標和列下標

intvalue;//非零元素值};typedefstructnodeNODE;NODEmatrix[MAX]；數(shù)據(jù)結(jié)構(gòu)設(shè)計稀疏矩陣的壓縮存儲——鏈式存儲結(jié)構(gòu)52valuenextcol結(jié)點結(jié)構(gòu)設(shè)計

typedefstructnode{intcol,value;structnode*next;}linklist;linklist*TAB[ROW];#defineROW4稀疏矩陣的壓縮存儲——鏈式存儲結(jié)構(gòu)53十字鏈表的存儲結(jié)構(gòu)54

structnode{introw,col,value;structnode*down,*right;};typedefstructnodeNODE;三元組rowcolvaluedownright向下域：鏈接同一列下一個非0元素向右域：鏈接同一行下一個非0元素十字鏈表的存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)設(shè)計矩陣的壓縮存儲小結(jié)55矩陣壓縮存儲：值相同的元素分配一個存儲空間，零元素不分配存儲空間；稀疏矩陣的壓縮存儲保存非零元素的值及其在矩陣中的位置；特殊矩陣的壓縮存儲：確定元素的存儲位置與元素在矩陣中的位置的對應(yīng)關(guān)系；4.1CONTENTS多維數(shù)組矩陣的壓縮存儲4.24.3字符串4.3本章小結(jié)字符編譯字符串處理文獻查詢機器翻譯源碼翻譯為機器碼利用計算機把一種自然源語言轉(zhuǎn)變?yōu)榱硪环N自然目標語言的過程，一般指自然語言之間句子和全文的翻譯。計算機將檢索者輸入檢索系統(tǒng)的檢索提問(即檢索標識)按檢索者預先制定的檢索策略與系統(tǒng)文檔（機讀數(shù)據(jù)庫）中的存貯標識進行類比、匹配運算,通過“人機對話”而檢索出所需要的文獻內(nèi)容特殊的線性表——字符串搜索引擎高級語言提供串處理功能搜索引擎是指根據(jù)一定的策略、運用特定的計算機程序從互聯(lián)網(wǎng)上搜集信息，在對信息進行組織和處理后，為用戶提供檢索服務(wù)，將用戶檢索相關(guān)的信息展示給用戶的系統(tǒng)。非數(shù)值數(shù)據(jù)4.3字符串4.3.14.3.24.3.3字符串的定義字符串的存儲結(jié)構(gòu)字符串的查找方法4.3字符串4.3.14.3.24.3.3字符串的定義字符串的存儲結(jié)構(gòu)字符串的查找方法字符串定義60串是一種特殊的線性表，它是由n(≥0)個字符組成的有限序列

定義

記作s=“a1,a2,a3,...an”s-串名，a1,a2,a3,...an串值ai是串中字符，n是串的長度高級語言提供串處理功能a1a2...ai...ai是字符an串的例子61串的實例串長度注“Thisisastring”16空格也算一個字符“string”6“”1空格串:僅由一個或多個空格組成的串“”0空串:長度為0的串稱為空串，它不包括任何字符“你好”4串中所包含的字符可以是字母、數(shù)字或其他字符，這依賴于具體計算機所允許的字符集指的是串中所包含的字符個數(shù)。串長度62兩個串相等，當且僅當兩個串長度相同，并且各個對應(yīng)位置的字符都相同。串的有關(guān)術(shù)語串中任意連續(xù)的字符組成的子序列稱為該串的子串;子串t在主串S中的位置是指主串s中第一個與t相同的子串的首字母在主串中的位置;子串子串的位置串相等例：c=“DATASTRUCTURE”，f=“DATA”f是c的子串例：s=“ababcabcac”,t=“abc”子串t在主串s中的位置為3串的基本操作63（1）字符串的長度計算（2）字符串的復制（3）字符串的連接（4）字符串的替換（5）字符串的插入（6）字符串的刪除（7）字符串的比較（8）抽取字符串（9）字符串的分割（10）字符串的查找由于串的匹配（字符串查找）算法的重要性與應(yīng)用的廣泛性，因此對它做一專門的介紹。由于在許多高級語言中都提供相應(yīng)的串操作處理功能，故對串的操作不再贅述。4.3字符串4.3.14.3.24.3.3字符串的定義字符串的存儲結(jié)構(gòu)字符串的查找算法字符串的存儲結(jié)構(gòu)65

由于串是一種特殊的線性表，它的每個結(jié)點僅由一個字符組成，因此存儲串的方法也同樣可以采用順序存儲或鏈式存儲。順序串66串的字符順序地存儲在內(nèi)存一片相鄰的空間順序串串的順序存儲——方案1012345…abcdef…空閑curlen用一個指針來向指最后一個字符typedefstruct{charch[MAXSIZE];intcurlen;}SeqString;數(shù)據(jù)結(jié)構(gòu)設(shè)計串的順序存儲——方案2串長chars[MAXSIZE+1];0123456…6abcdef空閑用數(shù)組的0號單元存放串的長度串值從1號單元開始存放直接記錄串長數(shù)據(jù)結(jié)構(gòu)設(shè)計69串的順序存儲——方案3串終結(jié)符chars[MAXSIZE+1];0123456…abcdef\0空閑在串尾存儲一個不會在串中出現(xiàn)的特殊字符作為串的終結(jié)符數(shù)據(jù)結(jié)構(gòu)設(shè)計串的順序存儲特點70預定義串的最大長度

使得串的某些操作受限（截尾），如串的連接、插入、置換等運算；插入和刪除操作不方便需要移動大量的字符串的塊鏈存儲結(jié)構(gòu)71abcdefg結(jié)點大小為1的鏈串可用單鏈表方式來存儲串值。串的鏈式存儲結(jié)構(gòu)簡稱為鏈串。鏈串與單鏈表的差異只是它的結(jié)點數(shù)據(jù)域為字符。鏈式串串的塊鏈存儲結(jié)構(gòu)72abcdefg結(jié)點大小為1的鏈串typedefstructlinknode{chardata;structlinknode*next;}linkstring;數(shù)據(jù)結(jié)構(gòu)設(shè)計單字符鏈串存儲結(jié)構(gòu)設(shè)計的優(yōu)缺點是什么？思考&討論討論：每個鏈結(jié)點中只放一個字符，插入、刪除、求長度等運算非常方便，但存儲效率低。改進的方法，可以在一個鏈結(jié)點中存儲多個字符，這樣就可以改善存儲效率，在處理不定長的大字符串時很有效，這是順序串和鏈串的綜合折中，稱為塊鏈結(jié)構(gòu)。串的塊鏈存儲結(jié)構(gòu)73abcdefg結(jié)點大小為1的鏈串typedefstructlinknode{chardata[4];structlinknode*next;}linkstring;abcdefg\0結(jié)點大小為4的鏈串typedefstructlinknode{chardata;structlinknode*next;}linkstring;數(shù)據(jù)結(jié)構(gòu)設(shè)計串的塊鏈存儲結(jié)構(gòu)74【例4-4】結(jié)點大小為4的鏈串“abcdefg”，在第n個字符后插入“xyz”。如n=3，對應(yīng)鏈串中的字符c。設(shè)計插入方案。串的索引存儲方法75s16s24...........pleaseek..帶長度的串索引表namelengthstadrtypedefstruct{charname[maxsize];//串名intlength;//串長度char*stadr;//串起始地址}lnode設(shè)：S1=“please”，S2=

“seek”.用串變量的名字作為關(guān)鍵字組織起來的索引表，表中串名與串值之間一一對應(yīng)。1串的索引存儲結(jié)構(gòu)76s1s2...........abcdefgbcd..帶頭尾指針的串索引表nameenadrstadrtypedefstruct{charname[maxsize];//串名char*stadr,//串頭地址char*enadr;//串尾地址}enode;2串的索引存儲方法設(shè)：S1=“abcdefg”，S2=“bcd”一個串設(shè)置兩個指針，一個指向串開頭，一個指向串末尾77s10s21bcd\0........abcdefg\0typedefstruct{charname[maxsize];inttag；//特征位

union{char*stadr;//特征位為0，放串首地址charvalue[4];//特征位為1，放串值}uval;}tagnode

nametagstadr/value..帶特征位的串索引表3串的索引存儲方法設(shè)：S1=“abcdefg”S2=“bcd”在索引表中設(shè)置一標志量tag來標示存儲的是串地址還是串內(nèi)容，這樣設(shè)計可以讓較短的串存取便捷一些。78設(shè)：s1=“GOOD”

s2=

“DAY”name……namelinkstruaStr[N]linknextdatanextdatalinkN-10串鏈結(jié)構(gòu)數(shù)組串鏈結(jié)點s1s2...GN-10OOD∧DAY∧鏈式串索引表4串的索引存儲方法79name……namedatanextnamelink串鏈結(jié)構(gòu)linkstru串鏈結(jié)點linknodelinkstruaStr[N]linknextdatanextdatalinkN-10串鏈結(jié)構(gòu)數(shù)組串鏈結(jié)點

//

串鏈數(shù)組定義typedefstruct{charname[maxsize];//串名linkstring*link;}linkstru;linkstruaStr[N];

//串鏈結(jié)點定義typedefstructlinknode{chardata;structlinknode*next;}linkstring;串的索引存儲方法4.3字符串4.3.14.3.24.3.3字符串的定義字符串的存儲結(jié)構(gòu)字符串的查找算法

字符串的查找——模式匹配81搜索引擎——做字符串査找匹配的工作。模式匹配算法是搜索引擎的關(guān)鍵，它直接影響系統(tǒng)的實時性能。

字符串的查找——模式匹配82模式匹配（PatternMatching）模式匹配(PatternMatching)也稱為串匹配(StringMatching)子串（模式串）在主串（目標串）中的定位運算即在主串中找出子串出現(xiàn)的位置匹配結(jié)果成功失敗返回t子串在s中的起始位置返回約定標記模式匹配算法83BF算法KMP算法BM算法84串的模式匹配——Brute-Force算法85功能描述輸入輸出BF模式匹配主串s的內(nèi)容int不匹配：-1index子串t的內(nèi)容匹配：子串在主串中的位置函數(shù)名形參函數(shù)類型#defineMaxSize100typedefstruct{charch[MaxSize];intlen;}SqString;函數(shù)框架設(shè)計數(shù)據(jù)結(jié)構(gòu)設(shè)計串的模式匹配——Brute-Force算法86第一步細化第二步細化初始化設(shè)主串S的下標i=0；子串T的下標j=0從主串S的第1個字符起和模式T的第一個字符比較之當i、j分別小于S、T的串長若相同，則繼續(xù)比較后續(xù)字符；

若：Si與Tj匹配，則i++，j++；否則從主串S的下一個字符起再重新和模式T的字符比較之；

否則：將i、j設(shè)置為下次將開始匹配的位置:

主串：i=i-j+1;

子串：j=0;直到整個T串掃描完畢若已經(jīng)掃描完T串則返回“匹配”給出結(jié)果否則返回“不匹配”串的模式匹配——Brute-Force算法/*==============================================函數(shù)功能：BF算法-——求模式t在目標串s是否匹配函數(shù)輸入：目標串s、模式串t函數(shù)輸出：匹配成功：返回模式串t首次在s中出現(xiàn)的位置

匹配不成功：返回-1================================================*/87串的模式匹配——Brute-Force算法【例4-5】分析給定字符串S和T時，BF算法的執(zhí)行次數(shù)兩個字符串S和T分別為S=“abcdgggkh”（N=9）T=“gggk”（M=4）88匹配成功平均比較次數(shù)算法分析最好情形串的模式匹配——Brute-Force算法89【例4-6】分析給定字符串S和T時，BF算法的執(zhí)行次數(shù)兩個字符串S和T分別為：S=“ggggggggk”（N=9）T=“gggk” （M=4）算法分析最壞情形注意書中改錯：S串中最后應(yīng)該為k串的模式匹配——Brute-Force算法90算法分析最壞情形匹配成功平均比較次數(shù)串的模式匹配——Brute-Force算法91匹配算法是檢測引擎的關(guān)鍵，它直接影響系統(tǒng)的實時性能。最壞情況下的時間復雜度O(m×n)（∵n>>m）最好情況下的時間復雜度O(m+n)串的模式匹配——在鏈串上的算法實現(xiàn)【例4-7】BF算法在鏈串上的實現(xiàn)用結(jié)點大小為1的單鏈表做串的存儲結(jié)構(gòu)，實現(xiàn)樸素的匹配算法。若匹配成功，則返回有效位移所指的結(jié)點地址，否則返回空指針。92分析：用結(jié)點大小為1的單鏈表做串的存儲結(jié)構(gòu)時，實現(xiàn)樸素的匹配算法很簡單。只是現(xiàn)在的位移是結(jié)點地址而非整數(shù)，且單鏈表中沒有存儲長度信息。若匹配成功，則返回有效位移所指的結(jié)點地址，否則返回空指針。串的模式匹配——在鏈串上的算法實現(xiàn)93功能描述輸入輸出IndexLBF模式匹配主串s的地址子串在主串中的位置子串t的地址函數(shù)名形參函數(shù)類型typedefstructnode{charch;structnode*next;}LinkString;函數(shù)框架設(shè)計數(shù)據(jù)結(jié)構(gòu)設(shè)計串的模式匹配——在鏈串上的算法實現(xiàn)94偽代碼細化描述設(shè)sptr指向主串s開始比較地址sptr，tptr指向子串起始地址；當(兩串均未處理到末尾)若(sptr結(jié)點值=tptr結(jié)點值)

sptr與tptr移動指向下一個結(jié)點否則first移動指向下一個開始比較的結(jié)點sptr指向主串s開始比較地址sptr，tptr指向子串起始地址；若tptr已指向鏈尾，即查找完畢，“匹配”返回first否則“不匹配”返回NULL串的模式匹配——在鏈串上的算法實現(xiàn)/*==============================================函數(shù)功能：BF算法在鏈串上的實現(xiàn)函數(shù)輸入：目標串鏈表起始地址，模式串鏈表起始地址函數(shù)輸出：匹配點地址=================================================*/95模式匹配算法96BF算法KMP算法BM算法串的模式匹配——KMP算法97BF算法KMP算法無回溯改進了回溯問題有回溯效率低D.E.Knuth與V.R.Prett和J.H.Morris共同提出，因此稱為克努特-莫里斯-普拉特操作（簡稱KMP算法）。KMP算法思路：不回溯主串s的位置指針i，以提高搜索效率。算法關(guān)鍵點：模式串t位置指針j不能每次都從頭開始，而是根據(jù)“失配”時的位置，決定下一次的開始位置。KMP算法測試1【例4-8】用KMP算法思路做串的匹配測試1設(shè)：T=“abcabcacab”S=“babcbabcabcaabcabcabcacabc”觀察結(jié)果每次比較結(jié)束時，已比較子串中，前綴與后綴相同的部分，在下一次就可以跳過不再比較。99100每次比較結(jié)束時，已經(jīng)比較子串中，前綴與后綴相同的部分——下一次就可以“跳過”不用再比較j=0，表示當前比較，第一個字符就不相等，下一次從主串結(jié)束位的下一個字符開始比較KMP算法測試1101j0

1

2

3

4

5

6

7

8

9T[j]abcabcacabnext[j]-1000123401結(jié)束位j=比較結(jié)束時，已經(jīng)比較的子串長度【知識ABC】字符串的前綴與字符串的后綴字符串的前綴是指字符串的任意首部（最后一個字符除外）。如字符串“abbc”的前綴有“a”，“ab”，“abb”，字符串的任意尾部是字符串的后綴（第一個字符除外），“abbc”的后綴有“c”，“bc”，“bbc”?！扒熬Y”指除了最后一個字符以外，一個字符串的全部頭部組合；“后綴”指除了第一個字符以外，一個字符串的全部尾部組合。102串的模式匹配——模式串的next值103next函數(shù)定義j表示子串t比較結(jié)束位，i表示主串s結(jié)束位t0t1t2…tk

1表示模式串t的k位前綴，用STR1表示tj

ktj

k+1…tj

1表示結(jié)束位j前的k位子串，用STR2表示情形j值next[j]取值含義STR1=STR2非0k下一次比較從si和tk開始STR1和STR2不存在非00下一次比較從si和t0開始s與t當前比較第一個字符即不等0-1下一次比較從si+1和t0開始串的模式匹配——模式串的next值【例4-9】給出模式串T=“abcac”的next數(shù)組值。104串的模式匹配——模式串的next值105第一步細化從主串S的第1個字符起和模式T的第一個字符比較之若相同，則繼續(xù)比較后續(xù)字符；否則，從主串S的當前字符起，和模式T的next字符比較之；給出結(jié)果第二步細化設(shè)主串S的下標i=0；子串T的下標j=0當i、j分別小于S、T的串長若：Si與Tj匹配，則i++，j++；否則：將i、j設(shè)置為下次將開始匹配的位置:主串：i不變;子串：j=next[j];若已經(jīng)掃描完T串

則返回“匹配”否則返回“不匹配”串的模式匹配——模式串的next值106如j=4時，k的變化從1~3，t0依次要和t1、t2、t3比較：若t0=t3，則k=1若t0t1=t2t3，則k=2若t0t1t2=t1t2t3，則k=3實際的情形是：當t0=t1

時，才有可能k=3當t0=t2

時，才有可能k=2當t0=t3

時，才有可能k=1故求next[j]的過程，就是一個在T串中匹配T前綴的過程107串的模式匹配——模式串的next值108求next算法描述初始化起始位k=-1，j=0；（k=-1，標志下一次開始位：T串從0開始，S串從j++開始）在s串的有效范圍內(nèi)

S[j]與T[k]相等或k=-1j、k后移一位

下一次子串開始比較位next[j]=k；

否則，設(shè)置重新比較位置：j串不變，k串從next表中取得下一次開始的位置串的模式匹配109#defineMaxSize30//串結(jié)構(gòu)typedefstruct{charch[MaxSize];//用數(shù)組存儲串值

intlen;//串長度}SqString;數(shù)據(jù)結(jié)構(gòu)設(shè)計串的模式匹配110功能描述輸入輸出求next值GetNext模式串結(jié)構(gòu)SqString（next數(shù)組地址）（next數(shù)組地址）函數(shù)名形參函數(shù)類型/*=======================================函數(shù)功能：由模式串t求出next的值函數(shù)輸入：模式串t，（next數(shù)組）函數(shù)輸出：無=========================================*/函數(shù)框架設(shè)計串的模式匹配111功能描述輸入輸出KMP匹配算法KMPIndex目標串結(jié)構(gòu)SqString模式串結(jié)構(gòu)SqStringint-1：不匹配int值：匹配位置函數(shù)名形參函數(shù)類型/*==============================================函數(shù)功能：KMP算法-——求模式t在目標串s是否匹配函數(shù)輸入：目標串s、模式串t函數(shù)輸出：匹配成功：返回模式串t首次在s中出現(xiàn)的位置

匹配不成功：返回-1================================================*/書中改錯=1，改為-1函數(shù)框架設(shè)計串的模式匹配112step1后不需要再和S[3]進行比較，可以將模式串一次向右滑動4個字符的位置，直接進行i=4，j=0時的字符比較?！纠?-10】用KMP算法思路做串的匹配測試2串的模式匹配【例4-10】用KMP算法思路做串的匹配測試2113tj=tk時next[j]置-1next[j]取值為-1的含義：下一次比較從si+1和t0開始KMP算法中，如何改進重復的比較步驟？模式匹配算法效率分析114設(shè)主串s的長度為n,子串t長度為m算法程序段時間復雜度說明BFO(m*n)一般情形接近O(m+n)KMP求next數(shù)組O(m)僅當模式串與主串之間存在許多“部分匹配”的情況下，KMP算法才明顯比BF算法快得多KMP匹配O(n)KMP算法最大特點：不需要回溯，在匹配過程中，對主串僅需從頭至尾掃描一遍，對處理從外部設(shè)備輸入的龐大文件很有效，可以邊讀入邊匹配，而無須回頭重讀。模式匹配算法115BF算法KMP算法BM算法BM算法簡介116算法模式串移動方向比較方向說明BF從左到右從左到右KMP從左到右從左到右實際應(yīng)用并不多BM從左到右從右到左文本編輯器常采用算法效率：BM算法>KMP算法>BF算法4.1CONTENTS多維數(shù)組矩陣的壓縮存儲4.24.3字符串4.3本章小結(jié)多維數(shù)組各概念間的聯(lián)系118多維數(shù)組存儲結(jié)構(gòu)邏輯結(jié)構(gòu)以行為主優(yōu)先存儲以列為主優(yōu)先存儲特殊矩陣定義：值相同元素或者零元素分布有一定規(guī)律的矩陣壓縮方法：將矩陣元素存儲于向量中，并找出二者的下標映射關(guān)系稀疏矩陣定義：非零元素個數(shù)遠少于零元素個數(shù)的矩陣壓縮方法：三元組表，十字鏈表，帶行向量的鏈表n維數(shù)組是線性表，它的每個元素是n-1維數(shù)組運算矩陣壓縮字符串各概念間的聯(lián)系119字符串存儲結(jié)構(gòu)概念運算順序存儲塊鏈存儲索引存儲復制、連接、替換求長度、插入、刪除比較、抽取、分割子串、主串模式匹配模式匹配算法：BF算法、KMP算法基本操作經(jīng)典算法邏輯結(jié)構(gòu)字符間呈線性關(guān)系矩陣壓縮要點120壓縮對象高階矩陣壓縮條件矩陣中非零元素呈某種規(guī)律分布；或：矩陣中出現(xiàn)大量的零元素壓縮目的使用高效的存儲方法，減少數(shù)據(jù)的存儲量壓縮方法

對原矩陣的二維數(shù)組存儲，根據(jù)數(shù)據(jù)分布特征進行壓縮，存儲至向量等結(jié)構(gòu)

稀疏矩陣的壓縮存儲除了要保存非零元素的值外，還要保存其在矩陣中的位置本章小結(jié)一維數(shù)組是線性表結(jié)點一對一相連，M*N二維數(shù)組有M行或N列線性表組合陣列。隨機存取說的是每個結(jié)點存取時間都一樣長短，特殊矩陣有對稱、對角、三角種種有規(guī)律包含。壓縮存是把二維的矩陣映射到一維的空間，行列二下標對一維下標的變換。稀疏矩陣很特別，是大矩陣非零的元素稀少分布星星點點，三元組表、行鏈表、十字鏈表壓縮存儲方法有三，設(shè)計思路都是存非零的元素值與位置在哪邊。121本章小結(jié)多個字符連在一起是字符的串，串結(jié)構(gòu)依然是線性表無二般。數(shù)組或鏈串存字符各種方案，求串長、比大小、做連接運算都簡單，唯模式匹配有點難。匹配是主串里面把子串查看，BF蠻力法要一個字符一個字符挨個驗，復雜度大歐mn速度有點慢。KMP不愧是三個臭皮匠湊成諸葛亮，細觀察巧安排主串無回溯，子串定位繼續(xù)的點在next表中尋探，大歐n加m提速果然贊。

（注：二維數(shù)組：M行N列

模式匹配：主串長度為n,子串長度為m）122

結(jié)點邏輯關(guān)系分層次的非線性結(jié)構(gòu)樹Chapter

5DataStructuresandAlgorithmAnalysis主要內(nèi)容廣義表的概念、存儲結(jié)構(gòu)、基本運算廣義表樹的定義和基本術(shù)語二叉樹的概念、存儲結(jié)構(gòu)遍歷二叉樹哈夫曼樹及其應(yīng)用樹學習目標了解數(shù)據(jù)的邏輯結(jié)構(gòu)從線性結(jié)構(gòu)到非線性結(jié)構(gòu)的過渡了解包含子結(jié)構(gòu)的線性結(jié)構(gòu)理解鏈式存儲結(jié)構(gòu)在表達非線性數(shù)據(jù)結(jié)構(gòu)中的作用掌握樹的概念、存儲方法、基本運算了解廣義表的概念、結(jié)構(gòu)特點及其存儲表示方法實際問題中的樹及抽象樹的邏輯結(jié)構(gòu)樹的存儲結(jié)構(gòu)二叉樹的邏輯結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)及實現(xiàn)樹的遍歷樹的應(yīng)用廣義表*CONTENTS5.15.25.35.45.55.65.75.8實際問題中的樹及抽象樹的邏輯結(jié)構(gòu)樹的存儲結(jié)構(gòu)二叉樹的邏輯結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)及實現(xiàn)樹的遍歷樹的應(yīng)用廣義表*CONTENTS5.15.25.35.45.55.65.75.85.1實際問題中的樹及抽象樹引例1——日常生活中的樹形結(jié)構(gòu)129樹引例2——計算機的目錄結(jié)構(gòu)130樹引例3——樹形結(jié)構(gòu)的網(wǎng)站131表達式樹132實際問題本質(zhì)的抽象133一切具有層次關(guān)系的問題都可用樹來描述實際問題中的樹及抽象樹的邏輯結(jié)構(gòu)樹的存儲結(jié)構(gòu)二叉樹的邏輯結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)及實現(xiàn)樹的遍歷樹的應(yīng)用廣義表*CONTENTS5.15.25.35.45.55.65.75.8樹的邏輯結(jié)構(gòu)135abdcefhgijlmnk層次結(jié)構(gòu)一多對應(yīng)非線性線性結(jié)構(gòu)便不足以方便地描述這樣的復雜情形樹5.2樹的邏輯結(jié)構(gòu)5.2.15.2.2樹的定義和基本術(shù)語樹的操作定義5.2樹的邏輯結(jié)構(gòu)5.2.15.2.2樹的定義和基本術(shù)語樹的操作定義樹138定義AGDCBFE樹形結(jié)構(gòu)是一種重要的非線性結(jié)構(gòu)，討論的是層次和分支關(guān)系樹是遞歸結(jié)構(gòu)——在樹的定義中又用到了樹的概念樹（tree）是包含n個結(jié)點的有限集合，其中：（1）有一個根結(jié)點，它只有直接后繼，但沒有直接前趨。（2）除根結(jié)點之外的其余數(shù)據(jù)元素被分為m個根的子樹。當樹的集合為空時，n=0，此時稱為空樹，空樹中沒有結(jié)點。樹的示意圖139樹的圖形表示方法140樹的相關(guān)術(shù)語141AGDCBFE包含一個數(shù)據(jù)元素及若干指向子樹的分支結(jié)點的子樹的根稱為該結(jié)點的孩子一個結(jié)點的直接上層結(jié)點稱為該結(jié)點的雙親同一雙親的孩子結(jié)點B、C、D是A的孩子，E、F是B的孩子A是B、C、D的雙親，B是E、F的雙親B、C、D是兄弟關(guān)系樹的結(jié)點孩子結(jié)點雙親結(jié)點兄弟結(jié)點樹的相關(guān)術(shù)語142AGDCBFE結(jié)點層樹的深度結(jié)點的度樹的度葉子結(jié)點分枝結(jié)點有序樹無序樹森林Level1Level2Level3根結(jié)點的層定義為1；根的孩子為第二層結(jié)點，依此類推；樹中最大的結(jié)點層度不為0的結(jié)點也叫終端結(jié)點，是度為0的結(jié)點樹中最大的結(jié)點度結(jié)點子樹的個數(shù)不考慮子樹的順序子樹有序的樹互不相交的樹集合樹的基本術(shù)語——示例143E,K,L,GH,I,M樹的概念144我們熟悉的樹形結(jié)構(gòu)中，無序樹、有序樹有哪些？思考&討論討論：有序樹無序樹的區(qū)別在于子樹是否有順序要求，有順序要求的如家譜、書的目錄等；無序的可以是計算機中的文件夾目錄等。5.2樹的邏輯結(jié)構(gòu)5.2.15.2.2樹的定義和基本術(shù)語樹的操作定義構(gòu)造建立一棵樹，初始化。樹的基本操作查找可以是查找根結(jié)點、雙親結(jié)點、孩子結(jié)點、葉子結(jié)點、指定值的結(jié)點等。插入刪除在指定位置插入/刪除結(jié)點遍歷沿著某條搜索路線，依次對樹中每個結(jié)點均做一次且僅做一次訪問。訪問結(jié)點所做的操作依賴于具體的應(yīng)用問題求深度計算樹的高度。實際問題中的樹及抽象樹的邏輯結(jié)構(gòu)樹的存儲結(jié)構(gòu)二叉樹的邏輯結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)及實現(xiàn)樹的遍歷樹的應(yīng)用廣義表*CONTENTS5.15.25.35.45.55.65.75.8樹的存儲結(jié)構(gòu)148存得進取得出A存數(shù)值存聯(lián)系B樹形結(jié)構(gòu)的存儲原則。非線性結(jié)構(gòu)比線性關(guān)系復雜，存儲樹形結(jié)構(gòu)問題的關(guān)鍵與重點。樹的存儲結(jié)構(gòu)149149樹形結(jié)構(gòu)存儲結(jié)點間聯(lián)系的原則是什么？一個雙親n個孩子對于設(shè)計好的存儲結(jié)構(gòu)，檢驗的標準則是只要在存儲結(jié)構(gòu)中能找到一個結(jié)點的這兩種關(guān)系，那么這樣的存儲結(jié)構(gòu)設(shè)計就是可行的。我們可以稱之為“雙親孩子檢驗原則”。雙親孩子檢驗法思考&討論5.3樹的存儲結(jié)構(gòu)5.3.15.3.2樹的連續(xù)存儲方式樹的鏈式存儲方式5.3樹的存儲結(jié)構(gòu)5.3.15.3.2樹的連續(xù)存儲方式樹的鏈式存儲方式樹連續(xù)存儲1——雙親孩子表示法152樹連續(xù)存儲2——雙親表示法153樹連續(xù)存儲3——孩子表示法1545.3樹的存儲結(jié)構(gòu)5.3.15.3.2樹的連續(xù)存儲方式樹的鏈式存儲方式樹的鏈式存儲方式156樹的鏈式存儲方式1571.同構(gòu)型結(jié)構(gòu)的特點有哪些？關(guān)于樹的結(jié)構(gòu)討論158思考&討論2．什么樣的樹在用同構(gòu)型結(jié)構(gòu)時，空的指針域最少？討論：同構(gòu)型結(jié)構(gòu)消除了異構(gòu)型的缺陷，結(jié)構(gòu)的統(tǒng)一化使管理變得容易，但若多數(shù)結(jié)點的度小于樹的度，則部分指針域為空，造成存儲空間的浪費。159什么樣的樹在用同構(gòu)型結(jié)構(gòu)時，空鏈域最少？設(shè)有n個結(jié)點，度為d的樹，用同構(gòu)型結(jié)點存儲整個鏈表共有指針域數(shù)有用的指針域數(shù)n*d個n-1個空的指針域數(shù)n(d-1)+1個R=空的指針域數(shù)整個鏈表共有指針域數(shù)=n(d-1)+1ndR=n→∞Limn→∞Limn(d-1)+1nd=1d1-K越小越好結(jié)論：d=2時，空鏈域最少二叉樹關(guān)于樹的結(jié)構(gòu)討論根結(jié)點的地址不占指針域degree——度想去掉結(jié)點個數(shù)的因素思考&討論樹鏈式存儲——孩子兄弟表示法160樹鏈式存儲——孩子鏈表表示法161樹鏈式存儲——孩子鏈表表示法162實際問題中的樹及抽象樹的邏輯結(jié)構(gòu)樹的存儲結(jié)構(gòu)二叉樹的邏輯結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)及實現(xiàn)樹的遍歷樹的應(yīng)用廣義表*CONTENTS5.15.25.35.45.55.65.75.8164若我們能找到普通樹轉(zhuǎn)換為二叉樹、二叉樹又能還原成原來的普通樹的方法，就完美地解決了這個問題。把二叉樹作為典型的結(jié)構(gòu)加以研究討論，相應(yīng)的結(jié)果能用到普通的樹上面嗎？二叉樹普通樹思考&討論樹轉(zhuǎn)換為二叉樹165樹轉(zhuǎn)換為二叉樹的過程中各結(jié)點的聯(lián)系有怎樣的變化？樹轉(zhuǎn)換為二叉樹166思考&討論討論：加線的過程，是增加了結(jié)點和兄弟的直接關(guān)聯(lián)；去線的操作，是去掉了除長子之外的聯(lián)系，但是可以通過長子的兄弟關(guān)系，間接得到所有孩子的信息，這個和前面介紹的“樹鏈式存儲-孩子兄弟表示法”是一樣的原理。森林轉(zhuǎn)換為二叉樹167二叉樹還原為樹168樹還原為二叉樹的過程中各結(jié)點的聯(lián)系有怎樣的變化？思考&討論一個結(jié)點x的左孩子其子孫，從來歷上看，都是這個左孩子的兄弟，如圖5.24中的FG點，都是E的子孫，EFG都是B的孩子，故加線是恢復結(jié)點與孩子的關(guān)系；去線是去掉兄弟間的連線，這樣就可以恢復成原來的樹結(jié)構(gòu)了。樹與二叉樹的存儲關(guān)系169樹鏈式存儲——孩子兄弟表示法1705.4二叉樹的邏輯結(jié)構(gòu)5.4.15.4.2二叉樹的概念二叉樹的基本性質(zhì)5.4.3二叉樹的操作定義5.4二叉樹的邏輯結(jié)構(gòu)5.4.15.4.2二叉樹的概念二叉樹的基本性質(zhì)5.4.3二叉樹的操作定義173說明：二叉樹是每個結(jié)點最多有兩個子樹的有序樹。二叉樹的子樹通常稱為“左子樹”（leftsubtree）和“右子樹”（rightsubtree）。左、右子樹的順序不能互換。二叉樹的概念AFGEDCB二叉樹是遞歸結(jié)構(gòu)，在二叉樹的定義中又用到了二叉樹的概念

二叉樹是n(n≥0)個結(jié)點的有限集，它或為空樹(n=0)，或由一個根結(jié)點和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構(gòu)成。二叉樹二叉樹的概念174二叉樹與樹的區(qū)別是什么？思考&討論討論：盡管二叉樹與樹有許多相似之處，樹和二叉樹的兩個主要差別：（1）樹中結(jié)點的最大度數(shù)沒有限制，而二叉樹結(jié)點的最大度數(shù)為2；（2）樹的結(jié)點無左、右之分，而二叉樹的結(jié)點有左、右之分，二叉樹的基本形態(tài)175二叉樹的特殊形態(tài)——滿二叉樹176如果深度為k的二叉樹，有2k-1個結(jié)點則稱為滿二叉樹二叉樹的特殊形態(tài)——完全二叉樹177可以說滿二叉樹是完全二叉樹的特例情形、(b)完全二叉樹(c)不是完全二叉樹二叉樹的特殊形態(tài)——完全二叉樹178完全二叉樹5.4二叉樹的邏輯結(jié)構(gòu)5.4.15.4.2二叉樹的概念二叉樹的基本性質(zhì)5.4.3二叉樹的操作定義二叉樹的基本性質(zhì)180深度為h的二叉樹至多有2h–1個結(jié)點（h

≥1）對任何一棵二叉樹，若它含有n0個葉子結(jié)點、n2個度為2的結(jié)點，則必存在關(guān)系式：n0=n2+1FGCBADE在二叉樹的第i層上至多有2i-1個結(jié)點（i≥1）性質(zhì)1性質(zhì)2性質(zhì)3完全二叉樹的性質(zhì)181具有n個結(jié)點的完全二叉樹的深度為：[log2n]+1若對含n個結(jié)點的完全二叉樹從上到下且從左至右進行1至n的編號，則對完全二叉樹中任意一個編號為i的結(jié)點：若i=1，則該結(jié)點是二叉樹的根，無雙親，否則，編號為

i/2

的結(jié)點為其雙親結(jié)點；若2i>n，則該結(jié)點無左孩子，否則，編號為2i的結(jié)點為其左孩子結(jié)點；若2i+1>n，則該結(jié)點無右孩子結(jié)點，否則，編號為2i+1的結(jié)點為其右孩子結(jié)點。123456FCBADE方括號表示取整性質(zhì)4性質(zhì)5完全二叉樹的性質(zhì)【例5-1】二叉樹各種結(jié)點數(shù)目的計算若一個完全二叉樹有n=1450個結(jié)點，則度為1的結(jié)點、度為2的結(jié)點、葉子結(jié)點個數(shù)分別是多少？有多少左孩子，多少右孩子？該樹的高度是多少？解：樹的高度：∵是完全二叉樹

∴1～10層全滿，k=10最下層葉子結(jié)點的個數(shù)=n-（2k

-1）=1450-1023=427k-1層帶葉子的結(jié)點數(shù)=[427+1/2]=214k-1層結(jié)點數(shù)=2k-1=512k-1層葉子數(shù)=512-214=298∴總?cè)~子數(shù)n0=427+298=725度為2的結(jié)點n2=n0-1=724度為1的結(jié)點n1=n-1-2n2=1450-1-2*724=1有左孩子結(jié)點數(shù)=度為2的結(jié)點數(shù)+度為1的結(jié)點數(shù)=725有右孩子結(jié)點數(shù)=度為2的結(jié)點數(shù)=724182二叉樹的特殊形態(tài)——完全二叉樹183完全二叉樹k層最下層k-1層k-1層帶葉子的結(jié)點k-1層帶的葉子數(shù)5.4二叉樹的邏輯結(jié)構(gòu)5.4.15.4.2二叉樹的概念二叉樹的基本性質(zhì)5.4.3二叉樹的操作定義二叉樹的操作定義構(gòu)造建立一棵樹，初始化查找查找指定條件的結(jié)點插入

刪除在指定位置插入/刪除結(jié)點遍歷

對樹中每個結(jié)點均做一次且僅做一次訪問求深度計算樹的高度實際問題中的樹及抽象樹的邏輯結(jié)構(gòu)樹的存儲結(jié)構(gòu)二叉樹的邏輯結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)及實現(xiàn)樹的遍歷樹的應(yīng)用廣義表*CONTENTS5.15.25.35.45.55.65.75.8普通樹二叉樹二叉樹的存儲結(jié)構(gòu)及實現(xiàn)已討論過一般形式樹的存儲方案簡化對照樹的一般形式來討論二叉樹的存儲方案5.5二叉樹的存儲結(jié)構(gòu)及實現(xiàn)5.5.15.5.2二叉樹的順序存儲結(jié)構(gòu)二叉樹的鏈式存儲結(jié)構(gòu)5.5.3建立動態(tài)二叉鏈表二叉樹順序存儲——結(jié)點間關(guān)系分析189二叉樹順序存儲——結(jié)點間關(guān)系分析190二叉樹順序存儲——結(jié)點位置分析191二叉樹順序存儲——結(jié)點位置分析192完全二叉樹存儲方案是否適用一般的二叉樹存儲？將二叉樹的所有結(jié)點，按照完全二叉樹的編號方法進行編號，按序存儲到一片連續(xù)的存儲單元中。結(jié)點的順序?qū)⒎从吵鼋Y(jié)點之間邏輯關(guān)系。二叉樹的順序存儲思考&討論二叉樹順序存儲——結(jié)點位置分析193退化的二叉樹的存儲5.5二叉樹的存儲結(jié)構(gòu)及實現(xiàn)5.5.15.5.2二叉樹的順序存儲結(jié)構(gòu)二叉樹的鏈式存儲結(jié)構(gòu)5.5.3建立動態(tài)二叉鏈表二叉樹的鏈式存儲結(jié)構(gòu)195

二叉樹的每個結(jié)點含有兩個指針域來分別指向相應(yīng)的分支，稱其為二叉鏈表二叉鏈表二叉樹的鏈式存儲結(jié)構(gòu)196二叉樹的每個結(jié)點含有兩個指針域來分別指向相應(yīng)的分支。二叉樹的鏈式存儲二叉樹的三叉鏈存儲結(jié)構(gòu)197樹的三重鏈表表示198靜態(tài)二叉鏈表199ADBCFE021435孩子結(jié)點在數(shù)組中的位置。用-1表示無左孩子或右孩子采用數(shù)組存儲的靜態(tài)二叉鏈表5.5二叉樹的存儲結(jié)構(gòu)及實現(xiàn)5.5.15.5.2二叉樹的順序存儲結(jié)構(gòu)二叉樹的鏈式存儲結(jié)構(gòu)5.5.3建立動態(tài)二叉鏈表層次輸入法創(chuàng)建二叉鏈表方法一201層次輸入法創(chuàng)建二叉鏈表方法一202

Q隊列元素A出列，A的下標i=1

將A的左孩子結(jié)點地址（在下標為2*i處）填入A結(jié)點的左指針域

將A的右孩子結(jié)點地址（在下標為2*i+1處）填入A結(jié)點的右指針域?qū)哟屋斎敕▌?chuàng)建二叉鏈表方法一203

Q隊列元素A出列，A的下標i=1

將A的左孩子結(jié)點地址（在下標為2*i處）填入A結(jié)點的左指針域

將A的右孩子結(jié)點地址（在下標為2*i+1處）填入A結(jié)點的右指針域204層次輸入法創(chuàng)建二叉鏈表方法一偽代碼描述設(shè)二叉樹的深度為k，則隊列Q的長度至少為2k-1+1(隊列的0下標位不用)生成樹的所有結(jié)點，結(jié)點地址按結(jié)點編號順序填入隊列數(shù)組Q[]中隊頭元素下標i=1當Q隊列i<k-1層元素個數(shù)(2k-1)

Q隊列元素i出列將i的左孩子結(jié)點地址(下標2*i）填入i的左指針域?qū)的右孩子結(jié)點地址(下標2*i+1的結(jié)點）填入i的右指針域返回根結(jié)點地址層次輸入法創(chuàng)建二叉鏈表方法二205

輸入結(jié)點信息，若輸入的結(jié)點不是虛結(jié)點，則建立一個新結(jié)點。若新結(jié)點是第1個結(jié)點，則令其為根結(jié)點，否則將新結(jié)點作為孩子鏈接到它的雙親結(jié)點上。如此反復進行，直到輸入結(jié)束標志“?！睘橹箤哟屋斎敕▌?chuàng)建二叉鏈表方法二206

輸入結(jié)點信息，若輸入的結(jié)點不是虛結(jié)點，則建立一個新結(jié)點。若新結(jié)點是第1個結(jié)點，則令其為根結(jié)點，否則將新結(jié)點作為孩子鏈接到它的雙親結(jié)點上。如此反復進行，直到輸入結(jié)束標志“?！睘橹?07層次輸入法創(chuàng)建二叉鏈表方法二偽代碼細化描述設(shè)二叉樹的深度為k，則隊列Q的長度設(shè)置按完全二叉樹編號至樹的最后一個結(jié)點當輸入結(jié)點信息不是結(jié)束標志‘#’若輸入的結(jié)點不是虛結(jié)點，則建立一個新結(jié)點并入隊若新結(jié)點是第1個結(jié)點，則令其為根結(jié)點，否則將新結(jié)點作為孩子鏈接到它的雙親結(jié)點上。若新結(jié)點是雙親結(jié)點的右孩子，則雙親結(jié)點出隊。返回根結(jié)點地址208層次輸入法創(chuàng)建二叉鏈表方法二功能描述輸入輸出CreaTree無根地址函數(shù)名形參函數(shù)類型

typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;數(shù)據(jù)結(jié)構(gòu)設(shè)計函數(shù)框架設(shè)計層次輸入法創(chuàng)建二叉鏈表方法二/*===============================================函數(shù)功能：層次輸入法創(chuàng)建二叉鏈表函數(shù)輸入：無函數(shù)輸出：二叉鏈表根結(jié)點鍵盤輸入：按完全二叉樹結(jié)點編號規(guī)則順序輸入結(jié)點值，空結(jié)點為@====================================================*/2095.6樹的遍歷5.6.15.6.2樹的廣度優(yōu)先遍歷樹的深度優(yōu)先遍歷5.6.3樹的遍歷的應(yīng)用引例1——機電設(shè)備通電自檢模型211設(shè)備通電自檢步驟應(yīng)該如何進行檢測步驟：左子樹：網(wǎng)卡等正常→PCI正?！@卡等正?！荘CI正?！蹇ㄕＳ易訕洌河脖P等正?！獯嬲！I盤等正?！渌！前蹇ㄕＵ脴洌喊蹇ㄕ！前蹇ㄕ！嬎銠C正常在上述的檢測過程中，“后序遍歷”的意思是指樹的根結(jié)點是最后被訪問到的，無論是整棵樹還是左右子樹?！昂笮虮闅v”引例2——網(wǎng)購商品的管理212FoodMeatPorkBeefFruitYellowBananMangoRedCherry如何打印商品清單“先序遍歷”根結(jié)點：Food左子樹：Meat→Pork/Beef右子樹：Fruit→（左子樹）Yellow→Banan/MangoFruit→（右子樹）Red→Cherry引例3——樹中結(jié)點的快速查找策略213“中序遍歷”如何得到有序序列？二分查找遞歸過程根為1的樹：左子樹（空）→根1→右子樹（2）→結(jié)果為1、2根為3的樹：左子樹（1,2）→根3→右子樹（4,5）→結(jié)果為1、2、3、4、5根為9的樹：左子樹（7,8）→根9→右子樹（10,11）→結(jié)果為7、8、9、10、11214遍歷的基本概念對結(jié)點的處理。如修改結(jié)點數(shù)據(jù)、輸出結(jié)點數(shù)據(jù)。

按某種順序訪問數(shù)據(jù)結(jié)構(gòu)中的結(jié)點，要求每個結(jié)點訪問一次且僅訪問一次。遍歷對線性結(jié)構(gòu)是容易解決的，而二叉樹是非線性的，因而需要尋找一種規(guī)律，以便使二叉樹上的結(jié)點能排列在一個線性隊列上，從而便于遍歷。如何訪問二叉樹的每個結(jié)點，而且每個結(jié)點僅被訪問一次？CBADFE遍歷訪問215遍歷的基本概念——基本遍歷策略廣度遍歷(Breadth-FirstSearch)深度遍歷(Depth_FirstSearch)5.6樹的遍歷5.6.15.6.2樹的廣度優(yōu)先遍歷樹的深度優(yōu)先遍歷5.6.3樹的遍歷的應(yīng)用基于順序存儲結(jié)構(gòu)的樹的廣度優(yōu)先遍歷217廣度遍歷（層次遍歷）方法：從上到下、從左到右訪問各結(jié)點適用于順序存儲結(jié)構(gòu)

基于鏈式存儲結(jié)構(gòu)的二叉樹廣度優(yōu)先遍歷218基于鏈式存儲結(jié)構(gòu)的二叉樹廣度優(yōu)先遍歷219(1)初始化一個隊列，并把根結(jié)點入列隊；

(2)隊列元素出隊，取得一個結(jié)點，訪問該結(jié)點；

(3)若該結(jié)點的左孩子非空，則將該結(jié)點的左子樹入隊列；

(4)若該結(jié)點的右孩子非空，則將該結(jié)點的右子樹入隊列；(5)循環(huán)執(zhí)行步驟2到4，直至隊列為空。算法描述基于鏈式存儲結(jié)構(gòu)的二叉樹廣度優(yōu)先遍歷220二叉樹結(jié)點結(jié)構(gòu)描述typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;bitree*Q[MAXSIZE];//設(shè)數(shù)組Q做隊列，隊列元素類型為二叉鏈表結(jié)點類型功能輸入輸出層次遍歷二叉樹leverOrder二叉鏈表根結(jié)點地址無函數(shù)名形參函數(shù)類型函數(shù)框架設(shè)計數(shù)據(jù)結(jié)構(gòu)設(shè)計基于鏈式存儲結(jié)構(gòu)的二叉樹廣度優(yōu)先遍歷/*=====================================函數(shù)功能：層次遍歷二叉樹，打印遍歷序列函數(shù)輸入：二叉鏈表根結(jié)點地址bitree*Ptr函數(shù)輸出：無=======================================*/2215.6樹的遍歷5.6.15.6.2樹的廣度優(yōu)先遍歷樹的深度優(yōu)先遍歷5.6.3樹的遍歷的應(yīng)用樹的深度優(yōu)先遍歷223深度優(yōu)先遍歷方法深度優(yōu)先遍歷遞歸算法深度優(yōu)先遍歷非遞歸算法樹的深度優(yōu)先遍歷224深度優(yōu)先遍歷方法深度優(yōu)先遍歷遞歸算法深度優(yōu)先遍歷非遞歸算法深度優(yōu)先遍歷方法225先左后右：DLR，LDR，LRD先右后左：DRL，RDL，RLD226深度優(yōu)先遍歷方法先序遍歷（DLR）中序遍歷（LDR）后序遍歷（LRD）深度遍歷策略——先序遍歷227若二叉樹非空，則依次進行以下操作（1）訪問根結(jié)點；（2）先序遍歷左子樹；（3）先序遍歷右子樹；深度遍歷策略——中序遍歷228若二叉樹非空，則依次進行以下操作（1）中序遍歷左子樹；（2）訪問根結(jié)點；（3）中序遍歷右子樹；深度遍歷策略——后序遍歷229若二叉樹非空，則依次進行以下操作（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(jié)點；用投影法理解樹的遍歷230用投影法理解樹的遍歷231用投影法理解樹的遍歷232先序遍歷的例子233先序遍歷的例子234情形圈中表示DLR序列情形圈中表示DLR序列1樹的根A6A的右子樹繼續(xù)細化2A的左子樹繼續(xù)細化7A右子樹的根E3A左子樹的根B8E的右子樹繼