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

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

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

數(shù)組常見(jiàn)

幾乎所有的高級(jí)程序設(shè)計(jì)語(yǔ)言都包含數(shù)組這種數(shù)據(jù)的結(jié)構(gòu)形式。本節(jié)將從數(shù)據(jù)結(jié)構(gòu)的角度，簡(jiǎn)單討論數(shù)組的邏輯結(jié)構(gòu)及其存儲(chǔ)方式。4.1多維數(shù)組4.1.14.1.2數(shù)組的概念數(shù)組的存儲(chǔ)結(jié)構(gòu)4.1多維數(shù)組4.1.14.1.2數(shù)組的概念數(shù)組的存儲(chǔ)結(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)成的集合，每個(gè)數(shù)據(jù)元素稱為一個(gè)數(shù)組元素（簡(jiǎn)稱元素）。數(shù)組（Array）一個(gè)行向量形式的線性表一個(gè)列向量形式的線性表數(shù)組的特點(diǎn)13元素推廣性元素本身可以具有某種結(jié)構(gòu)，而不限定是單個(gè)的數(shù)據(jù)元素。元素同一性元素具有相同的數(shù)據(jù)類型。關(guān)系確定性每個(gè)元素均受n（n≥1）個(gè)線性關(guān)系的約束，元素個(gè)數(shù)和元素之間的關(guān)系一般不發(fā)生變動(dòng)。如二維數(shù)組的元素有2個(gè)下標(biāo)4.1多維數(shù)組4.1.14.1.2數(shù)組的概念數(shù)組的存儲(chǔ)結(jié)構(gòu)數(shù)組的存儲(chǔ)結(jié)構(gòu)1515二維數(shù)組順序存儲(chǔ)方式以行序?yàn)橹餍?低下標(biāo)優(yōu)先)以列序?yàn)橹餍?高下標(biāo)優(yōu)先)存得進(jìn)取得出A計(jì)算機(jī)的存儲(chǔ)結(jié)構(gòu)是一維的，而數(shù)組一般是多維的，怎樣存放？思考與討論數(shù)組結(jié)構(gòu)特點(diǎn)16數(shù)目固定（1）數(shù)據(jù)元素?cái)?shù)目固定，一旦定義了一個(gè)數(shù)組結(jié)構(gòu)，就不再有元素個(gè)數(shù)的增減變化。類型相同（2）數(shù)據(jù)元素具有相同的類型。關(guān)系固定（3）數(shù)據(jù)元素的下標(biāo)關(guān)系具有上下界的約束且下標(biāo)有序。數(shù)組基本運(yùn)算17（1）給定一組下標(biāo)，存取相應(yīng)的數(shù)據(jù)元素。（2）給定一組下標(biāo)，修改相應(yīng)的數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值。數(shù)組運(yùn)算數(shù)組的順序存儲(chǔ)1819aij之前共有((i-1)*n+j-1)個(gè)元素基地址aij的存儲(chǔ)地址=Loc(aij

)=Loc(a11

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

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

的存儲(chǔ)地址=Loc(aij

)=

Loc(a11

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

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

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

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

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

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

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

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

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

定義

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

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

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

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

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

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

s2=

“DAY”name……namelinkstruaStr[N]linknextdatanextdatalinkN-10串鏈結(jié)構(gòu)數(shù)組串鏈結(jié)點(diǎn)s1s2...GN-10OOD∧DAY∧鏈?zhǔn)酱饕?串的索引存儲(chǔ)方法79name……namedatanextnamelink串鏈結(jié)構(gòu)linkstru串鏈結(jié)點(diǎn)linknodelinkstruaStr[N]linknextdatanextdatalinkN-10串鏈結(jié)構(gòu)數(shù)組串鏈結(jié)點(diǎn)

//

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

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

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

字符串的查找——模式匹配82模式匹配（PatternMatching）模式匹配(PatternMatching)也稱為串匹配(StringMatching)子串（模式串）在主串（目標(biāo)串）中的定位運(yùn)算即在主串中找出子串出現(xiàn)的位置匹配結(jié)果成功失敗返回t子串在s中的起始位置返回約定標(biāo)記模式匹配算法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è)計(jì)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)串的模式匹配——Brute-Force算法86第一步細(xì)化第二步細(xì)化初始化設(shè)主串S的下標(biāo)i=0；子串T的下標(biāo)j=0從主串S的第1個(gè)字符起和模式T的第一個(gè)字符比較之當(dāng)i、j分別小于S、T的串長(zhǎng)若相同，則繼續(xù)比較后續(xù)字符；

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

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

主串：i=i-j+1;

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

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

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

1

2

3

4

5

6

7

8

9T[j]abcabcacabnext[j]-1000123401結(jié)束位j=比較結(jié)束時(shí)，已經(jīng)比較的子串長(zhǎng)度【知識(shí)ABC】字符串的前綴與字符串的后綴字符串的前綴是指字符串的任意首部（最后一個(gè)字符除外）。如字符串“abbc”的前綴有“a”，“ab”，“abb”，字符串的任意尾部是字符串的后綴（第一個(gè)字符除外），“abbc”的后綴有“c”，“bc”，“bbc”?！扒熬Y”指除了最后一個(gè)字符以外，一個(gè)字符串的全部頭部組合；“后綴”指除了第一個(gè)字符以外，一個(gè)字符串的全部尾部組合。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開(kāi)始STR1和STR2不存在非00下一次比較從si和t0開(kāi)始s與t當(dāng)前比較第一個(gè)字符即不等0-1下一次比較從si+1和t0開(kāi)始串的模式匹配——模式串的next值【例4-9】給出模式串T=“abcac”的next數(shù)組值。104串的模式匹配——模式串的next值105第一步細(xì)化從主串S的第1個(gè)字符起和模式T的第一個(gè)字符比較之若相同，則繼續(xù)比較后續(xù)字符；否則，從主串S的當(dāng)前字符起，和模式T的next字符比較之；給出結(jié)果第二步細(xì)化設(shè)主串S的下標(biāo)i=0；子串T的下標(biāo)j=0當(dāng)i、j分別小于S、T的串長(zhǎng)若：Si與Tj匹配，則i++，j++；否則：將i、j設(shè)置為下次將開(kāi)始匹配的位置:主串：i不變;子串：j=next[j];若已經(jīng)掃描完T串

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

時(shí)，才有可能k=3當(dāng)t0=t2

時(shí)，才有可能k=2當(dāng)t0=t3

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

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

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

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

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

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

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

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

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

模式匹配：主串長(zhǎng)度為n,子串長(zhǎng)度為m）122

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

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

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

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

i/2

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

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

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

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

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

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

Q隊(duì)列元素A出列，A的下標(biāo)i=1

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

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

Q隊(duì)列元素A出列，A的下標(biāo)i=1

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

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

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

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

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

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

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

基于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的二叉樹廣度優(yōu)先遍歷218基于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的二叉樹廣度優(yōu)先遍歷219(1)初始化一個(gè)隊(duì)列，并把根結(jié)點(diǎn)入列隊(duì)；

(2)隊(duì)列元素出隊(duì)，取得一個(gè)結(jié)點(diǎn)，訪問(wèn)該結(jié)點(diǎn)；

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

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