第5章數(shù)據(jù)結(jié)構(gòu)

1、2022-3-7大學(xué)計算機基礎(chǔ)1第5章 數(shù)據(jù)結(jié)構(gòu)l數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念l線性表及其存儲結(jié)構(gòu)線性表及其存儲結(jié)構(gòu)l棧及其存儲結(jié)構(gòu)棧及其存儲結(jié)構(gòu)l隊列及其存儲結(jié)構(gòu)隊列及其存儲結(jié)構(gòu)l樹和二叉樹樹和二叉樹l查找查找l排序排序2022-3-7大學(xué)計算機基礎(chǔ)2l數(shù)據(jù)數(shù)據(jù)(Data):是對信息的一種符號表示。在計算機科學(xué)中是對信息的一種符號表示。在計算機科學(xué)中是指所有能輸入到計算機中并被計算機程序處理的符號是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。的總稱。l數(shù)據(jù)元素數(shù)據(jù)元素(Data Element):是數(shù)據(jù)的基本單位，在計算是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考

2、慮和處理。機程序中通常作為一個整體進行考慮和處理。l 一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。數(shù)據(jù)項是數(shù)據(jù)一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。的不可分割的最小單位。l數(shù)據(jù)對象數(shù)據(jù)對象(Data Object)：是性質(zhì)相同的數(shù)據(jù)元素的集合。：是性質(zhì)相同的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個子集。是數(shù)據(jù)的一個子集。l數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(Data Structure)：是相互之間具有一種或多：是相互之間具有一種或多種關(guān)聯(lián)的數(shù)據(jù)元素的集合。種關(guān)聯(lián)的數(shù)據(jù)元素的集合。5.1 數(shù)據(jù)結(jié)構(gòu)的基本概念2022-3-7大學(xué)計算機基礎(chǔ)3 數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容 1） 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的

3、邏輯結(jié)構(gòu)2） 數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)3） 數(shù)據(jù)結(jié)構(gòu)的運算數(shù)據(jù)結(jié)構(gòu)的運算2022-3-7大學(xué)計算機基礎(chǔ)41） 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)是用來描述數(shù)據(jù)元素在數(shù)據(jù)的邏輯結(jié)構(gòu)是用來描述數(shù)據(jù)元素在邏輯上的關(guān)聯(lián)關(guān)系的。它是數(shù)據(jù)的組織形式，邏輯上的關(guān)聯(lián)關(guān)系的。它是數(shù)據(jù)的組織形式，與數(shù)據(jù)在計算機內(nèi)的存儲方式無關(guān)。與數(shù)據(jù)在計算機內(nèi)的存儲方式無關(guān)。 常用的數(shù)據(jù)的邏輯結(jié)構(gòu)有：集合、線性常用的數(shù)據(jù)的邏輯結(jié)構(gòu)有：集合、線性結(jié)構(gòu)、樹狀結(jié)構(gòu)、圖狀結(jié)構(gòu)等。結(jié)構(gòu)、樹狀結(jié)構(gòu)、圖狀結(jié)構(gòu)等。例如：有一個包含了例如：有一個包含了4個元素的數(shù)據(jù)集合個元素的數(shù)據(jù)集合小小學(xué)，初中，高中，大學(xué)學(xué)，初中，高中，大學(xué)。2

4、022-3-7大學(xué)計算機基礎(chǔ)5 數(shù)據(jù)元素之間的前后位置關(guān)系稱為數(shù)據(jù)元素之間的前后位置關(guān)系稱為前后件關(guān)系，也稱為直接前驅(qū)和直接后前后件關(guān)系，也稱為直接前驅(qū)和直接后繼關(guān)系。繼關(guān)系。 所以，數(shù)據(jù)的邏輯結(jié)構(gòu)描述了兩個所以，數(shù)據(jù)的邏輯結(jié)構(gòu)描述了兩個方面的信息：方面的信息： 描述數(shù)據(jù)元素的信息；描述數(shù)據(jù)元素的信息； 描述數(shù)據(jù)元素之間的前后件關(guān)系的信息。描述數(shù)據(jù)元素之間的前后件關(guān)系的信息。2022-3-7大學(xué)計算機基礎(chǔ)62） 數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲器中數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲器中的存儲方式就是數(shù)據(jù)的存儲結(jié)構(gòu)（也稱的存儲方式就是數(shù)據(jù)的存儲結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)構(gòu)）。數(shù)據(jù)的物

5、理結(jié)構(gòu)）。 基本的存儲結(jié)構(gòu)有：順序存儲結(jié)構(gòu)、基本的存儲結(jié)構(gòu)有：順序存儲結(jié)構(gòu)、鏈式存儲結(jié)構(gòu)、索引存儲結(jié)構(gòu)、散列存鏈式存儲結(jié)構(gòu)、索引存儲結(jié)構(gòu)、散列存儲結(jié)構(gòu)。儲結(jié)構(gòu)。2022-3-7大學(xué)計算機基礎(chǔ)73） 數(shù)據(jù)結(jié)構(gòu)的運算數(shù)據(jù)結(jié)構(gòu)的運算 數(shù)據(jù)結(jié)構(gòu)的運算一般包括：插入、數(shù)據(jù)結(jié)構(gòu)的運算一般包括：插入、刪除、查找、分類、合并、分解、復(fù)制、刪除、查找、分類、合并、分解、復(fù)制、修改等。修改等。2022-3-7大學(xué)計算機基礎(chǔ)82. 數(shù)據(jù)結(jié)構(gòu)的表示數(shù)據(jù)結(jié)構(gòu)的表示1） 二元關(guān)系表示法二元關(guān)系表示法2） 圖形表示法圖形表示法2022-3-7大學(xué)計算機基礎(chǔ)91） 二元關(guān)系表示法二元關(guān)系表示法形式：形式： B=（D,R） 其

6、中，其中， B表示數(shù)據(jù)結(jié)構(gòu)，表示數(shù)據(jù)結(jié)構(gòu)，D表示表示數(shù)據(jù)元素的集合，數(shù)據(jù)元素的集合，R表示各數(shù)據(jù)元素表示各數(shù)據(jù)元素之間前后件關(guān)系的集合。之間前后件關(guān)系的集合。 2022-3-7大學(xué)計算機基礎(chǔ)10例例1：求學(xué)歷程：求學(xué)歷程 B=（D,R） D= 小學(xué)，初中，高中，大學(xué)小學(xué)，初中，高中，大學(xué) R= （小學(xué)，初中），（初中，高中），（高中，（小學(xué)，初中），（初中，高中），（高中，大學(xué)）大學(xué)） 例例2：我國的行政區(qū)劃分：我國的行政區(qū)劃分 B=（D,R） D= 中國，省，自治區(qū)，直轄市，北京，天津，中國，省，自治區(qū)，直轄市，北京，天津，上海，重慶上海，重慶 R= （中國，省），（中國，自治區(qū)），（中國，

7、（中國，?。?，（中國，自治區(qū)），（中國，直轄市），（直轄市，北京），直轄市），（直轄市，北京）， （直轄市，天（直轄市，天津），津）， （直轄市，上海），（直轄市，上海）， （直轄市，重慶）（直轄市，重慶） 2022-3-7大學(xué)計算機基礎(chǔ)112） 圖形表示法圖形表示法 每一個數(shù)據(jù)元素均表示為一個矩每一個數(shù)據(jù)元素均表示為一個矩形框，稱為結(jié)點；每一個前后件關(guān)系形框，稱為結(jié)點；每一個前后件關(guān)系表示為一個帶箭頭的有向線段，從前表示為一個帶箭頭的有向線段，從前件結(jié)點指向后件結(jié)點。件結(jié)點指向后件結(jié)點。2022-3-7大學(xué)計算機基礎(chǔ)12例例1：求學(xué)歷程：求學(xué)歷程 例例2：我國的行政區(qū)劃分：我國的行政區(qū)劃分

8、小學(xué)初中高中大學(xué)中國直轄市重慶上海天津北京自治區(qū)省2022-3-7大學(xué)計算機基礎(chǔ)133. 線性結(jié)構(gòu)和非線性結(jié)構(gòu)線性結(jié)構(gòu)和非線性結(jié)構(gòu) 如果一個數(shù)據(jù)結(jié)構(gòu)中沒有任何數(shù)據(jù)元如果一個數(shù)據(jù)結(jié)構(gòu)中沒有任何數(shù)據(jù)元素，則稱該數(shù)據(jù)結(jié)構(gòu)為空數(shù)據(jù)結(jié)構(gòu)。對于素，則稱該數(shù)據(jù)結(jié)構(gòu)為空數(shù)據(jù)結(jié)構(gòu)。對于一個非空的數(shù)據(jù)結(jié)構(gòu)來說，如果滿足以下一個非空的數(shù)據(jù)結(jié)構(gòu)來說，如果滿足以下三個條件：三個條件： 有且只有一個根結(jié)點；有且只有一個根結(jié)點； 每個結(jié)點最多有一個前件結(jié)點，也最多有每個結(jié)點最多有一個前件結(jié)點，也最多有一個后件結(jié)點；一個后件結(jié)點； 插入或刪除任何一個結(jié)點后仍然同時滿足插入或刪除任何一個結(jié)點后仍然同時滿足前兩個條件。前兩個條件

9、。則稱這樣的結(jié)構(gòu)為線性結(jié)構(gòu)，又稱線性表，則稱這樣的結(jié)構(gòu)為線性結(jié)構(gòu)，又稱線性表，否則為非線性結(jié)構(gòu)。否則為非線性結(jié)構(gòu)。2022-3-7大學(xué)計算機基礎(chǔ)14l線性表的基本概念線性表的基本概念l線性表的順序存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)l線性表的鏈式存儲結(jié)構(gòu)線性表的鏈式存儲結(jié)構(gòu)5.2 線性表及其存儲結(jié)構(gòu)2022-3-7大學(xué)計算機基礎(chǔ)15 線性表的基本概念線性表的基本概念線性表(Linear List) ：由n(n0)個數(shù)據(jù)元素組成的有序序列。其中數(shù)據(jù)元素的個數(shù)n稱為線性表的長度。當n=0時稱為空表，常常將非空的線性表(n0)記作： (a1，a2，an) 其中，ai(1in)是線性表中的一個數(shù)據(jù)元素，也稱作

10、結(jié)點。例1、26個英文字母組成的字母表 （A，B，C、Z）例2、學(xué)生健康情況登記表如下：姓姓 名名學(xué)學(xué) 號號性性 別別年齡年齡 健康情況健康情況王小林王小林790631 男男 18 健康健康陳陳 紅紅790632 女女 20 一般一般劉建平劉建平790633 男男 21 健康健康張立立張立立790634 男男 17 神經(jīng)衰弱神經(jīng)衰弱 . . .2022-3-7大學(xué)計算機基礎(chǔ)16 線性表是一種典型的線性結(jié)構(gòu)。這線性表是一種典型的線性結(jié)構(gòu)。這種結(jié)構(gòu)在非空時具有以下特征：種結(jié)構(gòu)在非空時具有以下特征： 有且只有一個根結(jié)點有且只有一個根結(jié)點a1，有且只有一個終端結(jié)點an ； 除根結(jié)點和終端結(jié)點外，其它中

11、間結(jié)點有且只有一個前件結(jié)點，也有且只有一個后件結(jié)點。2022-3-7大學(xué)計算機基礎(chǔ)172. 線性表的順序存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)1） 順序表基本結(jié)構(gòu)順序表基本結(jié)構(gòu) 順序表就是按照線性表各結(jié)點的邏輯順序表就是按照線性表各結(jié)點的邏輯次序把各點依次存放到一組連續(xù)的存儲單次序把各點依次存放到一組連續(xù)的存儲單元里。因此，在線性表的順序存儲結(jié)構(gòu)中，元里。因此，在線性表的順序存儲結(jié)構(gòu)中，前后相鄰的兩個數(shù)據(jù)元素在計算機的存儲前后相鄰的兩個數(shù)據(jù)元素在計算機的存儲空間中也是前后相鄰的，且前后位置關(guān)系空間中也是前后相鄰的，且前后位置關(guān)系跟邏輯關(guān)系一致。在程序設(shè)計語言中，一跟邏輯關(guān)系一致。在程序設(shè)計語言中，一般用

12、一維數(shù)組實現(xiàn)順序表。般用一維數(shù)組實現(xiàn)順序表。2022-3-7大學(xué)計算機基礎(chǔ)18 對于順序表，可以用公式計算對于順序表，可以用公式計算出任一元素的存儲位置。出任一元素的存儲位置。 如果第一個數(shù)據(jù)元素存放位置為LOC(a i)，每個元素需占用 個存儲單元，則線性表中第i+1個數(shù)據(jù)元素的存儲位置和第i個數(shù)據(jù)元素的存儲位置之間滿足下列關(guān)系： LOC(a i+1)=LOC(a i)+ 線性表的第i個數(shù)據(jù)元素ai的存儲位置為： LOC(ai)=LOC(a1)+(i-1)*llla1a2aianLOC(a1)LOC(a1)+ lLOC(ai)=LOC(a1)+(i-1)*lLOC(an)=LOC(a1)+(

13、n-1)*l2022-3-7大學(xué)計算機基礎(chǔ)192） 順序表的運算順序表的運算 順序表的運算主要有：插入、刪除、順序表的運算主要有：插入、刪除、查找、排序、分解、合并和逆轉(zhuǎn)。排序和查找、排序、分解、合并和逆轉(zhuǎn)。排序和查找將在后面介紹，這里介紹一下插入和查找將在后面介紹，這里介紹一下插入和刪除運算。刪除運算。2022-3-7大學(xué)計算機基礎(chǔ)20u插入運算插入運算55557468923555573146892312345123456插入31插入前n=5插入后n=6注：平均情況下，順序表的插入運算需要移動表中一半的元素。2022-3-7大學(xué)計算機基礎(chǔ)21u刪除運算刪除運算5555746892355557

14、892312345123456刪除46刪除前n=5刪除后n=4注：平均情況下，順序表的刪除運算需要移動表中一半的元素。2022-3-7大學(xué)計算機基礎(chǔ)223. 線性表的鏈式存儲結(jié)構(gòu)線性表的鏈式存儲結(jié)構(gòu)1） 線性鏈表基本結(jié)構(gòu)線性鏈表基本結(jié)構(gòu) 線性鏈表是用任意的存儲單元存儲線線性鏈表是用任意的存儲單元存儲線性表的各個數(shù)據(jù)元素的。與順序表不同，性表的各個數(shù)據(jù)元素的。與順序表不同，這組存儲單元可以是連續(xù)的存儲空間，也這組存儲單元可以是連續(xù)的存儲空間，也可以是不連續(xù)的，甚至是零散的。因此，可以是不連續(xù)的，甚至是零散的。因此，對于線性鏈表來說，各數(shù)據(jù)元素的邏輯順對于線性鏈表來說，各數(shù)據(jù)元素的邏輯順序與存儲順

15、序未必一致。序與存儲順序未必一致。2022-3-7大學(xué)計算機基礎(chǔ)23 為了表示存儲線性表中數(shù)據(jù)元素及數(shù)為了表示存儲線性表中數(shù)據(jù)元素及數(shù)據(jù)元素間的前后件關(guān)系，線性鏈表采用結(jié)據(jù)元素間的前后件關(guān)系，線性鏈表采用結(jié)點表示數(shù)據(jù)元素。每個結(jié)點有兩個組成部點表示數(shù)據(jù)元素。每個結(jié)點有兩個組成部分：數(shù)據(jù)域和指針域。其中，數(shù)據(jù)域中存分：數(shù)據(jù)域和指針域。其中，數(shù)據(jù)域中存儲數(shù)據(jù)元素的信息，指針域中存儲數(shù)據(jù)元儲數(shù)據(jù)元素的信息，指針域中存儲數(shù)據(jù)元素間的前后件關(guān)系的信息，一般用指針指素間的前后件關(guān)系的信息，一般用指針指示直接后繼元素或直接前驅(qū)元素的存儲位示直接后繼元素或直接前驅(qū)元素的存儲位置。置。 指向第一個結(jié)點的指針稱為

16、頭指針。指向第一個結(jié)點的指針稱為頭指針。 線性鏈表分為單鏈表、循環(huán)鏈表和雙線性鏈表分為單鏈表、循環(huán)鏈表和雙向鏈表。向鏈表。2022-3-7大學(xué)計算機基礎(chǔ)242） 單鏈表及其運算單鏈表及其運算 單鏈表的每個結(jié)點有兩個域：一個數(shù)單鏈表的每個結(jié)點有兩個域：一個數(shù)據(jù)域和一個指針域。指針域中存儲的是直據(jù)域和一個指針域。指針域中存儲的是直接后繼元素的存儲位置。接后繼元素的存儲位置。V(i)Next(i)i存儲序號 數(shù)據(jù)域 指針域2022-3-7大學(xué)計算機基礎(chǔ)25例：線性表（例：線性表（A,B,C,D,E）的單鏈表存儲結(jié)構(gòu)。）的單鏈表存儲結(jié)構(gòu)。ABCDEhead單鏈表的邏輯結(jié)構(gòu)D66A72C9ENULLB3

17、516head916356672單鏈表的存儲結(jié)構(gòu)2022-3-7大學(xué)計算機基礎(chǔ)26 單鏈表的運算主要有：查找、插入和刪單鏈表的運算主要有：查找、插入和刪除運算。除運算。u查找運算查找運算 基本方法：從頭指針指向的第一個結(jié)點基本方法：從頭指針指向的第一個結(jié)點開始沿著指針鏈依次向后搜索，逐個檢查每開始沿著指針鏈依次向后搜索，逐個檢查每個結(jié)點的數(shù)據(jù)域是否是指定元素，若是則返個結(jié)點的數(shù)據(jù)域是否是指定元素，若是則返回該結(jié)點的地址，否則返回回該結(jié)點的地址，否則返回NULL。2022-3-7大學(xué)計算機基礎(chǔ)27u插入運算插入運算 在單鏈表的第在單鏈表的第i個元素之后插入一個新元素個元素之后插入一個新元素x的基

18、本方法是：的基本方法是：u 在單鏈表中查找到要插入的位置；在單鏈表中查找到要插入的位置；u 生成一個新結(jié)點存儲新元素生成一個新結(jié)點存儲新元素x；u 將新結(jié)點插入到指定位置，更改相應(yīng)元素指針域。將新結(jié)點插入到指定位置，更改相應(yīng)元素指針域。a1ai-1aiana1ai-1aianx插入新元素x之前插入新元素x之后2022-3-7大學(xué)計算機基礎(chǔ)28u刪除運算刪除運算 要刪除單鏈表中第要刪除單鏈表中第i個元素的基本方法是：個元素的基本方法是：u 在單鏈表中查找到要刪除的元素；在單鏈表中查找到要刪除的元素；u 更改相應(yīng)元素的指針域，將第更改相應(yīng)元素的指針域，將第i-1個結(jié)點的指針域不再指向個結(jié)點的指針域

19、不再指向原來的第原來的第i個結(jié)點，改為指向第個結(jié)點，改為指向第i+1個結(jié)點；個結(jié)點；u 將要刪除的結(jié)點移除。將要刪除的結(jié)點移除。a1ai-1aian刪除元素ai之前ai+1a1ai-1aian刪除元素ai之后ai+12022-3-7大學(xué)計算機基礎(chǔ)293）循環(huán)鏈表）循環(huán)鏈表循環(huán)鏈表是一種首尾相接形似環(huán)狀的鏈表。循環(huán)鏈表是一種首尾相接形似環(huán)狀的鏈表。 a1 an .head 非空表 空表2022-3-7大學(xué)計算機基礎(chǔ)304）雙向鏈表）雙向鏈表 雙向鏈表的每個結(jié)點是由雙向鏈表的每個結(jié)點是由3個域組成的，個域組成的，比單鏈表增加了一個指向前件結(jié)點的指針域。比單鏈表增加了一個指向前件結(jié)點的指針域。AAA

20、head注：循環(huán)鏈表和雙向鏈表的插入運算、刪除運算與單鏈表的這兩種運算類似。2022-3-7大學(xué)計算機基礎(chǔ)31l棧的基本概念棧的基本概念l棧的順序存儲結(jié)構(gòu)棧的順序存儲結(jié)構(gòu)l棧的鏈式存儲結(jié)構(gòu)棧的鏈式存儲結(jié)構(gòu)5.3 棧及其存儲結(jié)構(gòu)2022-3-7大學(xué)計算機基礎(chǔ)321. 棧的基本概念棧的基本概念l 棧是一種特殊的線性表。棧是一種特殊的線性表。l 棧是指一端封閉，只允許在另棧是指一端封閉，只允許在另一端插入或刪除元素的線性表。一端插入或刪除元素的線性表。l 封閉的一端稱為棧底，允許插封閉的一端稱為棧底，允許插入或刪除元素的一端稱為棧頂。入或刪除元素的一端稱為棧頂。l 向棧中插入元素的過程稱為入向棧中插

21、入元素的過程稱為入棧運算或進棧運算；從棧中刪棧運算或進棧運算；從棧中刪除元素的過程稱為出棧運算或除元素的過程稱為出棧運算或退棧運算。退棧運算。a n a n-1a2a1棧頂top 棧底bottom出棧入棧2022-3-7大學(xué)計算機基礎(chǔ)33l棧中沒有任何元素稱為空棧。棧中沒有任何元素稱為空棧。l對于非空棧，處于棧頂?shù)脑胤Q為棧頂元素，對于非空棧，處于棧頂?shù)脑胤Q為棧頂元素，處于棧底的元素稱為棧底元素。處于棧底的元素稱為棧底元素。l棧是棧是“先進后出先進后出”（first in last out, FILO）或或“后進先出后進先出”（last in first out, LIFO）表。）表。l棧具

22、有記憶功能。棧具有記憶功能。2022-3-7大學(xué)計算機基礎(chǔ)342. 棧的順序存儲結(jié)構(gòu)棧的順序存儲結(jié)構(gòu) 棧的順序存儲結(jié)構(gòu)也稱為順序棧，它是一種運算棧的順序存儲結(jié)構(gòu)也稱為順序棧，它是一種運算受限的順序表。受限的順序表。 對順序?？梢杂袑樞驐？梢杂?種運算：種運算：CBAtopbottom54321EDCBAtopbottom54321DCBAtopbottom54321(a) 初始棧 (b) 元素D和E入棧后 (c)元素E出棧后 2022-3-7大學(xué)計算機基礎(chǔ)35（1）入棧運算）入棧運算向棧中插入元素的過程稱為入棧運算。向棧中插入元素的過程稱為入棧運算。基本方法是：基本方法是：l將棧頂指針將棧頂

23、指針top向棧頂方向移動一個存儲單元；向棧頂方向移動一個存儲單元；l將要插入的元素插入到棧頂指針將要插入的元素插入到棧頂指針top指向的存儲位指向的存儲位置。置。說明：在執(zhí)行入棧運算前，如果棧本身已經(jīng)是滿棧，說明：在執(zhí)行入棧運算前，如果棧本身已經(jīng)是滿棧，即棧頂指針已經(jīng)指向了棧存儲空間的最后一個位即棧頂指針已經(jīng)指向了棧存儲空間的最后一個位置時，如果繼續(xù)插入新元素，就會發(fā)生置時，如果繼續(xù)插入新元素，就會發(fā)生“上溢上溢”錯誤。所以，要求在執(zhí)行入棧運算前，必須先要錯誤。所以，要求在執(zhí)行入棧運算前，必須先要判斷棧內(nèi)是否還有空間可以容納新的元素插入。判斷棧內(nèi)是否還有空間可以容納新的元素插入。2022-3-

24、7大學(xué)計算機基礎(chǔ)36（2）出棧運算）出棧運算出棧運算是指從棧頂刪除一個元素并把它的值賦給某出棧運算是指從棧頂刪除一個元素并把它的值賦給某個變量。個變量?；痉椒ㄊ牵夯痉椒ㄊ牵簂將棧頂元素賦值給指定變量；將棧頂元素賦值給指定變量；l將棧頂指針將棧頂指針top向棧底方向移動一個存儲單元。向棧底方向移動一個存儲單元。說明：出棧時，原棧頂元素不必真正擦除，只需移動說明：出棧時，原棧頂元素不必真正擦除，只需移動棧頂指針即可，原棧頂元素在下次入棧運算之前棧頂指針即可，原棧頂元素在下次入棧運算之前仍然存在。在執(zhí)行出棧運算前，如果棧是空棧，仍然存在。在執(zhí)行出棧運算前，如果棧是空棧，即棧頂指針為即棧頂指針為0

25、時，已經(jīng)沒有元素可以刪除，如果時，已經(jīng)沒有元素可以刪除，如果還要執(zhí)行出棧運算，則會發(fā)生還要執(zhí)行出棧運算，則會發(fā)生“下溢下溢”錯誤。同錯誤。同樣，也需要在執(zhí)行出棧運算前，先檢查棧頂指針樣，也需要在執(zhí)行出棧運算前，先檢查棧頂指針所指的位置。所指的位置。2022-3-7大學(xué)計算機基礎(chǔ)37（3）讀棧頂元素）讀棧頂元素讀棧頂元素就是將棧頂元素的值賦給某個指定變量。讀棧頂元素就是將棧頂元素的值賦給某個指定變量。說明：說明：l它與出棧運算的差異在于不用移動棧頂指針的位它與出棧運算的差異在于不用移動棧頂指針的位置，即不刪除棧頂元素。置，即不刪除棧頂元素。l當棧頂指針當棧頂指針top為為0時，無法讀取棧頂元素。

26、時，無法讀取棧頂元素。2022-3-7大學(xué)計算機基礎(chǔ)383. 棧的鏈式存儲結(jié)構(gòu)棧的鏈式存儲結(jié)構(gòu) 棧的鏈式存儲結(jié)構(gòu)也稱為鏈棧，它可以看作一種運算棧的鏈式存儲結(jié)構(gòu)也稱為鏈棧，它可以看作一種運算受限的線性鏈表，插入和刪除操作只允許在線性鏈表的一受限的線性鏈表，插入和刪除操作只允許在線性鏈表的一端進行。端進行。top(a) 鏈棧的邏輯示意圖 (b) 鏈棧的入棧運算 (c)鏈棧的出棧運算 DCBADCBAPtopDCBAPtop2022-3-7大學(xué)計算機基礎(chǔ)39（1）入棧運算）入棧運算鏈棧的入棧運算就是向鏈棧中插入一個新的元素。鏈棧的入棧運算就是向鏈棧中插入一個新的元素?；痉椒ㄊ牵夯痉椒ㄊ牵簂先為新

27、元素分配一個結(jié)點；先為新元素分配一個結(jié)點；l結(jié)點的數(shù)據(jù)域存儲新元素的值；結(jié)點的數(shù)據(jù)域存儲新元素的值；l結(jié)點的指針域指向原棧頂元素；結(jié)點的指針域指向原棧頂元素；l改變棧頂指針，使之指向新元素的結(jié)點。改變棧頂指針，使之指向新元素的結(jié)點。2022-3-7大學(xué)計算機基礎(chǔ)40（2）出棧運算）出棧運算鏈棧的出棧運算就是從鏈棧的棧頂處刪除一個元素。鏈棧的出棧運算就是從鏈棧的棧頂處刪除一個元素?；痉椒ㄊ牵夯痉椒ㄊ牵簂保存棧頂元素地址；保存棧頂元素地址；l讀取棧頂元素，將其賦值給指定變量；讀取棧頂元素，將其賦值給指定變量；l改變棧頂指針，使其指向原棧頂元素結(jié)點的后繼改變棧頂指針，使其指向原棧頂元素結(jié)點的后繼

28、結(jié)點；結(jié)點；l釋放原棧頂元素空間。釋放原棧頂元素空間。2022-3-7大學(xué)計算機基礎(chǔ)41l隊列的基本概念隊列的基本概念l隊列的順序存儲結(jié)構(gòu)隊列的順序存儲結(jié)構(gòu)l隊列的鏈式存儲結(jié)構(gòu)隊列的鏈式存儲結(jié)構(gòu)5.4 隊列及其存儲結(jié)構(gòu)2022-3-7大學(xué)計算機基礎(chǔ)421. 隊列的基本概念隊列的基本概念l 隊列也是一種運算受限的特殊隊列也是一種運算受限的特殊線性表。線性表。l 隊列只允許在表的一端插入元隊列只允許在表的一端插入元素，在另一端刪除元素。素，在另一端刪除元素。l 允許插入元素的一端稱為隊尾，允許插入元素的一端稱為隊尾，允許刪除元素的一端稱為隊頭。允許刪除元素的一端稱為隊頭。l 向隊列的隊尾插入元素的

29、過程向隊列的隊尾插入元素的過程稱為入隊運算或進隊運算；從稱為入隊運算或進隊運算；從隊列的隊頭刪除元素的過程稱隊列的隊頭刪除元素的過程稱為出隊運算或退隊運算。為出隊運算或退隊運算。a 1 a 2an隊頭front 隊尾rear出隊入隊2022-3-7大學(xué)計算機基礎(chǔ)43l隊列中沒有任何元素時稱為空隊列。隊列中沒有任何元素時稱為空隊列。l對于長度不為對于長度不為0的非空隊列，處于隊頭的元素的非空隊列，處于隊頭的元素稱為隊頭元素，處于隊尾的元素稱為隊尾元素。稱為隊頭元素，處于隊尾的元素稱為隊尾元素。l隊列是隊列是“先進先出先進先出”（first in first out, FIFO）或或“后進后出后進

30、后出”（last in last out, LILO）表。）表。l隊列中的元素的出隊順序與入隊順序完全相同。隊列中的元素的出隊順序與入隊順序完全相同。2022-3-7大學(xué)計算機基礎(chǔ)442. 隊列的順序存儲結(jié)構(gòu)隊列的順序存儲結(jié)構(gòu) 隊列的順序存儲結(jié)構(gòu)也稱為順序隊列。隊列的順序存儲結(jié)構(gòu)也稱為順序隊列。 一般順序隊列的運算有入隊運算和出隊運算兩種。一般順序隊列的運算有入隊運算和出隊運算兩種。CBArearfront54321DCBArearfront54321DCBrearfront54321(a) 初始隊列 (b) 元素D入隊后 (c)元素A出隊后 2022-3-7大學(xué)計算機基礎(chǔ)45（1）入隊運算）

31、入隊運算順序隊列的入隊運算只涉及尾指針順序隊列的入隊運算只涉及尾指針rear的變化。的變化?；痉椒ㄊ牵夯痉椒ㄊ牵簂將隊尾指針將隊尾指針rear向隊尾方向移動一個存儲單元；向隊尾方向移動一個存儲單元；l將要插入的元素插入隊尾指針將要插入的元素插入隊尾指針rear指向的存儲位指向的存儲位置。置。說明：入隊運算時，如果隊滿或尾指針已經(jīng)指向了隊說明：入隊運算時，如果隊滿或尾指針已經(jīng)指向了隊列存儲空間的最后一個位置，若繼續(xù)插入新元素，列存儲空間的最后一個位置，若繼續(xù)插入新元素，就會發(fā)生就會發(fā)生“上溢上溢”錯誤。錯誤。2022-3-7大學(xué)計算機基礎(chǔ)46（2）出隊運算）出隊運算出隊運算也只涉及頭指針出隊

32、運算也只涉及頭指針front的改變。的改變?；痉椒ㄊ牵夯痉椒ㄊ牵簂將隊頭元素賦值給指定變量；將隊頭元素賦值給指定變量；l將頭指針將頭指針front向隊尾方向移動一個存儲單元。向隊尾方向移動一個存儲單元。說明：在執(zhí)行出隊運算時，如果隊列是空隊，繼續(xù)刪說明：在執(zhí)行出隊運算時，如果隊列是空隊，繼續(xù)刪除元素，則會發(fā)生除元素，則會發(fā)生“下溢下溢”錯誤。錯誤。 在實際應(yīng)用中，由于順序隊列隊頭刪除元素在實際應(yīng)用中，由于順序隊列隊頭刪除元素所在的空間常被閑置，造成資源的浪費，為解決所在的空間常被閑置，造成資源的浪費，為解決這個問題，一般順序隊列常采用循環(huán)隊列的形式。這個問題，一般順序隊列常采用循環(huán)隊列的形

33、式。2022-3-7大學(xué)計算機基礎(chǔ)47循環(huán)隊列循環(huán)隊列l(wèi) 循環(huán)隊列就是將隊列的首尾相連循環(huán)隊列就是將隊列的首尾相連構(gòu)成一個邏輯上的環(huán)狀空間，能構(gòu)成一個邏輯上的環(huán)狀空間，能夠循環(huán)存儲隊列中的數(shù)據(jù)元素。夠循環(huán)存儲隊列中的數(shù)據(jù)元素。l 循環(huán)隊列中，依然是尾指針循環(huán)隊列中，依然是尾指針rear指向隊尾元素，頭指針指向隊尾元素，頭指針front指向指向隊頭元素的前一個位置。隊頭元素的前一個位置。l 當循環(huán)隊列空或滿時，都有當循環(huán)隊列空或滿時，都有front= rear。為了區(qū)分隊列空或。為了區(qū)分隊列空或滿的狀態(tài)，增加了一個標志量滿的狀態(tài)，增加了一個標志量flag，所以當循環(huán)隊列為空時，有所以當循環(huán)隊列為

34、空時，有flag=0且且front= rear同時成立，當同時成立，當循環(huán)隊列為滿時，有循環(huán)隊列為滿時，有flag=1且且front= rear同時成立。同時成立。a 1 a 2an隊頭front 隊尾rear2022-3-7大學(xué)計算機基礎(chǔ)48（1）入隊運算）入隊運算循環(huán)隊列的入隊運算也是指在隊尾加入一個新元素的過程。循環(huán)隊列的入隊運算也是指在隊尾加入一個新元素的過程。基本方法是：基本方法是：l將隊尾指針將隊尾指針rear向隊尾方向移動一個存儲單元，有向隊尾方向移動一個存儲單元，有rear=(rear+1) mod n；l將要插入的元素插入隊尾指針將要插入的元素插入隊尾指針rear指向的存儲位

35、置。指向的存儲位置。說明：當說明：當flag=1且且front= rear時，說明循環(huán)隊列是滿隊狀態(tài)，時，說明循環(huán)隊列是滿隊狀態(tài)，如果進行入隊運算，就會發(fā)生如果進行入隊運算，就會發(fā)生“上溢上溢”錯誤。錯誤。CBArearfront54321DCBAErearfront54321rearfront54321(a) 初始隊列 (b) 元素D和E入隊后 (c)所有元素出隊后 2022-3-7大學(xué)計算機基礎(chǔ)49（2）出隊運算）出隊運算循環(huán)隊列的出隊運算也是指將隊頭元素刪除的過程。循環(huán)隊列的出隊運算也是指將隊頭元素刪除的過程?；痉椒ㄊ牵夯痉椒ㄊ牵簂將隊頭元素賦值給指定變量；將隊頭元素賦值給指定變量；

36、l將頭指針將頭指針front向隊尾方向移動一個存儲單元，有向隊尾方向移動一個存儲單元，有front=(front+1) mod n。說明：在執(zhí)行出隊運算時，如果說明：在執(zhí)行出隊運算時，如果flag=0且且front= rear時，說明循環(huán)隊列是空對狀態(tài)，如果繼續(xù)刪除元時，說明循環(huán)隊列是空對狀態(tài)，如果繼續(xù)刪除元素，就會發(fā)生素，就會發(fā)生“下溢下溢”錯誤。錯誤。2022-3-7大學(xué)計算機基礎(chǔ)503. 隊列的鏈式存儲結(jié)構(gòu)隊列的鏈式存儲結(jié)構(gòu) 隊列的鏈式存儲結(jié)構(gòu)也稱為鏈隊列，它也是一種運算隊列的鏈式存儲結(jié)構(gòu)也稱為鏈隊列，它也是一種運算受限的線性鏈表，入隊和出隊操作必須在線性鏈表的不同受限的線性鏈表，入隊和

37、出隊操作必須在線性鏈表的不同端進行。端進行。rear(a) 鏈隊列的邏輯示意圖 (b) 鏈隊列的入棧運算 (c)鏈隊列的出棧運算 ABCDBCDPArearCDPrearfrontfrontfront2022-3-7大學(xué)計算機基礎(chǔ)51（1）入隊運算）入隊運算鏈隊的入隊運算就是向鏈隊中插入一個新的元素。鏈隊的入隊運算就是向鏈隊中插入一個新的元素?；痉椒ㄊ牵夯痉椒ㄊ牵簂先為新元素分配一個結(jié)點；先為新元素分配一個結(jié)點；l結(jié)點的數(shù)據(jù)域存儲新元素的值；結(jié)點的數(shù)據(jù)域存儲新元素的值；l結(jié)點的指針域設(shè)置為空；結(jié)點的指針域設(shè)置為空；l尾結(jié)點的指針域指向新元素的結(jié)點；尾結(jié)點的指針域指向新元素的結(jié)點；l改變尾指

38、針，使之指向新元素的結(jié)點。改變尾指針，使之指向新元素的結(jié)點。2022-3-7大學(xué)計算機基礎(chǔ)52（2）出隊運算）出隊運算鏈隊的出隊運算就是從鏈隊的隊頭處刪除一個元素。鏈隊的出隊運算就是從鏈隊的隊頭處刪除一個元素?；痉椒ㄊ牵夯痉椒ㄊ牵簂保存隊頭元素地址；保存隊頭元素地址；l讀取隊頭元素，將其賦值給指定變量；讀取隊頭元素，將其賦值給指定變量；l改變頭結(jié)點的指針域，使其指向原隊頭元素結(jié)點改變頭結(jié)點的指針域，使其指向原隊頭元素結(jié)點的后繼結(jié)點；的后繼結(jié)點；l釋放原隊頭元素空間。釋放原隊頭元素空間。2022-3-7大學(xué)計算機基礎(chǔ)53l樹的基本概念樹的基本概念l二叉樹的定義及性質(zhì)二叉樹的定義及性質(zhì)l二叉樹

39、的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)l二叉樹的遍歷二叉樹的遍歷5.5 樹和二叉樹2022-3-7大學(xué)計算機基礎(chǔ)54 樹狀結(jié)構(gòu)是一種重要的非線性結(jié)構(gòu)。它的形狀類似于樹狀結(jié)構(gòu)是一種重要的非線性結(jié)構(gòu)。它的形狀類似于現(xiàn)實中倒立的樹，結(jié)點間呈現(xiàn)分支和層次關(guān)系，能夠方現(xiàn)實中倒立的樹，結(jié)點間呈現(xiàn)分支和層次關(guān)系，能夠方便地描述數(shù)據(jù)之間一對多的聯(lián)系。便地描述數(shù)據(jù)之間一對多的聯(lián)系。 樹結(jié)構(gòu)樹結(jié)構(gòu) （除了一個稱為根的結(jié)點外）每個元素都有（除了一個稱為根的結(jié)點外）每個元素都有且僅有一個直接前趨，有且僅有零個或多個直接后繼。且僅有一個直接前趨，有且僅有零個或多個直接后繼。J JI IA AC CB BD DH HG GF FE

40、E石油大學(xué)石油大學(xué)計算系計算系數(shù)學(xué)專業(yè)數(shù)學(xué)專業(yè)數(shù)理系數(shù)理系外語系外語系物理專業(yè)物理專業(yè)1. 樹的基本概念樹的基本概念2022-3-7大學(xué)計算機基礎(chǔ)55樹形結(jié)構(gòu)常用的術(shù)語樹形結(jié)構(gòu)常用的術(shù)語l根結(jié)點：最上層的沒有前件結(jié)點的結(jié)點。根結(jié)點：最上層的沒有前件結(jié)點的結(jié)點。l葉子結(jié)點：沒有后件結(jié)點的結(jié)點。葉子結(jié)點：沒有后件結(jié)點的結(jié)點。l內(nèi)部結(jié)點：既有前件結(jié)點又有后件結(jié)點的結(jié)點。內(nèi)部結(jié)點：既有前件結(jié)點又有后件結(jié)點的結(jié)點。l父結(jié)點：某一結(jié)點的前件結(jié)點稱為該結(jié)點的父結(jié)點。父結(jié)點：某一結(jié)點的前件結(jié)點稱為該結(jié)點的父結(jié)點。l子結(jié)點：某一結(jié)點的后件結(jié)點稱為該結(jié)點的子結(jié)點。子結(jié)點：某一結(jié)點的后件結(jié)點稱為該結(jié)點的子結(jié)點。l子

41、樹：以某個結(jié)點的一個子結(jié)點為根的樹稱為該結(jié)點的子子樹：以某個結(jié)點的一個子結(jié)點為根的樹稱為該結(jié)點的子樹。樹。l結(jié)點的度：某個結(jié)點連接的子結(jié)點的個數(shù)稱為該結(jié)點的度。結(jié)點的度：某個結(jié)點連接的子結(jié)點的個數(shù)稱為該結(jié)點的度。l樹的度：一顆樹包含的所有結(jié)點的度的最大值稱為這棵樹樹的度：一顆樹包含的所有結(jié)點的度的最大值稱為這棵樹的度。的度。l樹的深度：樹的最大層次數(shù)稱為樹的深度。樹的深度：樹的最大層次數(shù)稱為樹的深度。2022-3-7大學(xué)計算機基礎(chǔ)562. 二叉樹的定義及性質(zhì)二叉樹的定義及性質(zhì)二叉樹是一種重要的樹狀結(jié)構(gòu)。二叉樹是一種重要的樹狀結(jié)構(gòu)。二叉樹是二叉樹是n(n 0)個結(jié)點的有限集合，具有兩個特點：個結(jié)

42、點的有限集合，具有兩個特點：l如果二叉樹非空，則有且只有一個根結(jié)點；如果二叉樹非空，則有且只有一個根結(jié)點；l每個結(jié)點最多有兩個子結(jié)點，分別以這兩個子結(jié)點作為每個結(jié)點最多有兩個子結(jié)點，分別以這兩個子結(jié)點作為根結(jié)點組成該結(jié)點的左子樹和右子樹。根結(jié)點組成該結(jié)點的左子樹和右子樹。二叉樹的度最大為二叉樹的度最大為2。 A A F F G G E E D D C C B B2022-3-7大學(xué)計算機基礎(chǔ)57 A A F F G G E E D D C C B B(a) A A G G E E D D B B C C F F(b) (a)、(b)是不同的二叉樹， (a)的左子樹有四個結(jié)點，(b)的左子樹有兩

43、個結(jié)點，2022-3-7大學(xué)計算機基礎(chǔ)58二叉樹的二叉樹的5種基本形態(tài)：種基本形態(tài)：（a） （b） （c） （d） （e）（a）空二叉樹；（）空二叉樹；（b）僅有根結(jié)點的二叉樹）僅有根結(jié)點的二叉樹 （c）右子樹為空的二叉樹；）右子樹為空的二叉樹； （d）左、右子數(shù)均為非空的二叉樹）左、右子數(shù)均為非空的二叉樹（e）左子樹為空的二叉樹）左子樹為空的二叉樹 2022-3-7大學(xué)計算機基礎(chǔ)59 滿二叉樹滿二叉樹 滿二叉樹是指除了最后一層外，每一層的滿二叉樹是指除了最后一層外，每一層的結(jié)點都有兩個子結(jié)點的二叉樹。也就是說，在結(jié)點都有兩個子結(jié)點的二叉樹。也就是說，在滿二叉樹的任何一層上，結(jié)點的數(shù)目都達到最

44、滿二叉樹的任何一層上，結(jié)點的數(shù)目都達到最大值。大值。 A A G G F F E E D D C C B B A A C C B B深度為3的滿二叉樹深度為2的滿二叉樹2022-3-7大學(xué)計算機基礎(chǔ)60 完全二叉樹完全二叉樹 完全二叉樹是指除了最后一層外，每一層完全二叉樹是指除了最后一層外，每一層的結(jié)點都有兩個子結(jié)點，而在最后一層上，右的結(jié)點都有兩個子結(jié)點，而在最后一層上，右邊的若干結(jié)點缺失的二叉樹。邊的若干結(jié)點缺失的二叉樹。 A A E E D D C C B B A A F F E E D D C C B B 完全二叉樹是二叉樹的特例 滿二叉樹又是完全二叉樹的特例2022-3-7大學(xué)計算機

45、基礎(chǔ)61二叉樹的性質(zhì)二叉樹的性質(zhì)l性質(zhì)性質(zhì)1 二叉樹的第二叉樹的第k層上最多有層上最多有2k-1(k 1)個結(jié)個結(jié)點。當二叉樹為滿二叉樹時取得極限值。點。當二叉樹為滿二叉樹時取得極限值。l性質(zhì)性質(zhì)2 深度為深度為m的二叉樹最多有的二叉樹最多有2m-1(m 1) 個個結(jié)點。結(jié)點。l性質(zhì)性質(zhì)3 二叉樹中度為二叉樹中度為0的結(jié)點數(shù)的結(jié)點數(shù)n0和度為和度為2的結(jié)的結(jié)點數(shù)點數(shù)n2滿足滿足n0=n2+1。l性質(zhì)性質(zhì)4 具有具有n個結(jié)點的二叉樹，深度個結(jié)點的二叉樹，深度h滿足滿足h log2n+1，當二叉樹為完全二叉樹時取得，當二叉樹為完全二叉樹時取得極限值極限值h=log2n+1，其中，其中l(wèi)og2n表示

46、取小于表示取小于等于等于log2n的最大整數(shù)。的最大整數(shù)。2022-3-7大學(xué)計算機基礎(chǔ)62二叉樹的性質(zhì)二叉樹的性質(zhì)l性質(zhì)性質(zhì)5 具有具有n個結(jié)點的完全二叉樹，如果從根個結(jié)點的完全二叉樹，如果從根結(jié)點開始，按層序編號，則對任一編號為結(jié)點開始，按層序編號，則對任一編號為i(i=1,2,n)的結(jié)點，有的結(jié)點，有l(wèi)若若i=1，則該結(jié)點為根結(jié)點；若，則該結(jié)點為根結(jié)點；若i1，則該結(jié)，則該結(jié)點的父結(jié)點的編號為點的父結(jié)點的編號為INT(i/2)。l若若2i n，則編號為，則編號為i的結(jié)點有左子結(jié)點，左子的結(jié)點有左子結(jié)點，左子結(jié)點的編號為結(jié)點的編號為2i，否則該結(jié)點是葉子結(jié)點。，否則該結(jié)點是葉子結(jié)點。l若若

47、2i+1 n，則編號為，則編號為i的結(jié)點有右子結(jié)點，右的結(jié)點有右子結(jié)點，右子結(jié)點的編號為子結(jié)點的編號為2i+1，否則該結(jié)點沒有右子，否則該結(jié)點沒有右子結(jié)點。結(jié)點。2022-3-7大學(xué)計算機基礎(chǔ)633. 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)l二叉樹通常有兩種存儲方式：順序存儲結(jié)構(gòu)和二叉樹通常有兩種存儲方式：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)，由于順序存儲結(jié)構(gòu)局限性較大，鏈式存儲結(jié)構(gòu)，由于順序存儲結(jié)構(gòu)局限性較大，而且空間浪費嚴重，所以一般采用的是鏈式存而且空間浪費嚴重，所以一般采用的是鏈式存儲結(jié)構(gòu)，也稱二叉鏈表。儲結(jié)構(gòu)，也稱二叉鏈表。l與線性表類似，二叉鏈表中的每個存儲結(jié)點也與線性表類似，二叉鏈表中的每個存儲

48、結(jié)點也是由數(shù)據(jù)域和指針域組成。是由數(shù)據(jù)域和指針域組成。L(i)V(i)R(i)存儲序號 左指針域 數(shù)據(jù)域 右指針域i2022-3-7大學(xué)計算機基礎(chǔ)64 A A F F E E D D C C B B D D A A B B C C E E F F t(a) 二叉樹(b) 二叉鏈表的邏輯狀態(tài)2022-3-7大學(xué)計算機基礎(chǔ)654. 二叉樹的遍歷二叉樹的遍歷 二叉樹的遍歷是指沿某條路徑不重復(fù)地訪二叉樹的遍歷是指沿某條路徑不重復(fù)地訪問二叉樹中的所有結(jié)點。這里的訪問是指對結(jié)問二叉樹中的所有結(jié)點。這里的訪問是指對結(jié)點進行某種處理，如讀、寫、改等。點進行某種處理，如讀、寫、改等。 二叉樹遍歷過程中涉及訪問根

49、結(jié)點、遍歷二叉樹遍歷過程中涉及訪問根結(jié)點、遍歷左子樹和遍歷右子樹左子樹和遍歷右子樹3種操作。根據(jù)對結(jié)點訪種操作。根據(jù)對結(jié)點訪問先后的不同，可以將二叉樹的遍歷分為前序問先后的不同，可以將二叉樹的遍歷分為前序遍歷、中序遍歷和后序遍歷遍歷、中序遍歷和后序遍歷3種類型。種類型。2022-3-7大學(xué)計算機基礎(chǔ)66 前序遍歷（前序遍歷（DLR） 前序遍歷是一個遞歸過程，若二叉樹為空，前序遍歷是一個遞歸過程，若二叉樹為空，則結(jié)束返回，對于非空的二叉樹，其遍歷規(guī)則結(jié)束返回，對于非空的二叉樹，其遍歷規(guī)則如下：則如下：l訪問根結(jié)點；訪問根結(jié)點；l前序遍歷左子樹；前序遍歷左子樹；l前序遍歷右子樹。前序遍歷右子樹。l

50、右圖二叉樹的前序遍歷結(jié)果右圖二叉樹的前序遍歷結(jié)果為：為：ABMWFIR A A W W I I M M F F B B R R2022-3-7大學(xué)計算機基礎(chǔ)67 中序遍歷（中序遍歷（LDR） 中序遍歷也是一個遞歸過程，若二叉樹中序遍歷也是一個遞歸過程，若二叉樹為空，則結(jié)束返回，對于非空的二叉樹，其為空，則結(jié)束返回，對于非空的二叉樹，其遍歷規(guī)則如下：遍歷規(guī)則如下：l中序遍歷左子樹；中序遍歷左子樹；l訪問根結(jié)點；訪問根結(jié)點；l中序遍歷右子樹。中序遍歷右子樹。l右圖二叉樹的中序遍歷結(jié)果右圖二叉樹的中序遍歷結(jié)果l為：為：MBWAIRF A A W W I I M M F F B B R R2022-3

51、-7大學(xué)計算機基礎(chǔ)68 后序遍歷（后序遍歷（LRD） 后序遍歷也是一個遞歸過程，若二叉樹后序遍歷也是一個遞歸過程，若二叉樹為空，則結(jié)束返回，對于非空的二叉樹，其為空，則結(jié)束返回，對于非空的二叉樹，其遍歷規(guī)則如下：遍歷規(guī)則如下：l后序遍歷左子樹；后序遍歷左子樹；l后序遍歷右子樹；后序遍歷右子樹；l訪問根結(jié)點。訪問根結(jié)點。l右圖二叉樹的中序遍歷結(jié)果右圖二叉樹的中序遍歷結(jié)果l為：為：MWBRIFA A A W W I I M M F F B B R R2022-3-7大學(xué)計算機基礎(chǔ)69 查找就是指在某種數(shù)據(jù)結(jié)構(gòu)中找到某個指查找就是指在某種數(shù)據(jù)結(jié)構(gòu)中找到某個指定元素的過程。若從數(shù)據(jù)結(jié)構(gòu)中找到了指定的定

52、元素的過程。若從數(shù)據(jù)結(jié)構(gòu)中找到了指定的元素，則稱查找成功，否則稱為查找失敗。元素，則稱查找成功，否則稱為查找失敗。 通常，數(shù)據(jù)結(jié)構(gòu)不同，采用的查找方法也通常，數(shù)據(jù)結(jié)構(gòu)不同，采用的查找方法也不一樣。由于查找的主要操作是元素的比較，不一樣。由于查找的主要操作是元素的比較，所以通常把查找過程中元素的比較次數(shù)作為衡所以通常把查找過程中元素的比較次數(shù)作為衡量一個查找算法效率高低的標準。量一個查找算法效率高低的標準。l順序查找順序查找l二分查找二分查找5.6 查找2022-3-7大學(xué)計算機基礎(chǔ)701. 順序查找順序查找l順序查找是線性表的最簡單的查找方法。順序查找是線性表的最簡單的查找方法。l順序查找的基

53、本方法是：從線性表的一端開始順序查找的基本方法是：從線性表的一端開始依次掃描每個元素，與指定元素進行比較，如依次掃描每個元素，與指定元素進行比較，如果相等，則查找成功，給出元素在表中的位置，果相等，則查找成功，給出元素在表中的位置，如果全部元素掃描完后，仍然沒有找到與指定如果全部元素掃描完后，仍然沒有找到與指定元素相等的，則查找失敗。元素相等的，則查找失敗。l優(yōu)點：算法簡單。缺點：查找效率比較低。優(yōu)點：算法簡單。缺點：查找效率比較低。l順序查找長度為順序查找長度為n的線性表，平均情況下要做的線性表，平均情況下要做(n+1)/2次比較次比較 ，最壞情況下要做，最壞情況下要做n次次比較。比較。l有

54、些情況只能采用順序查找：線性表無序、線有些情況只能采用順序查找：線性表無序、線性鏈表。性鏈表。1112ninin2022-3-7大學(xué)計算機基礎(chǔ)711. 二分查找二分查找l二分查找又稱折半查找，是一種比順序表效率高的線二分查找又稱折半查找，是一種比順序表效率高的線性查找方法。要求線性表必須是有序的。性查找方法。要求線性表必須是有序的。l二分查找的基本方法是：首先將線性表的中間元素與二分查找的基本方法是：首先將線性表的中間元素與指定元素進行比較，如果相等，則查找成功，如果不指定元素進行比較，如果相等，則查找成功，如果不相等，需要進一步判斷被查元素與中間元素的大小，相等，需要進一步判斷被查元素與中間

55、元素的大小，如果被查元素大于中間元素，則要在元素值較大的子如果被查元素大于中間元素，則要在元素值較大的子表中繼續(xù)使用二分法繼續(xù)查找，如果被查元素小于中表中繼續(xù)使用二分法繼續(xù)查找，如果被查元素小于中間元素，則要在元素值較小的子表中繼續(xù)使用二分法間元素，則要在元素值較小的子表中繼續(xù)使用二分法繼續(xù)查找，直到查找成功或查找失敗。繼續(xù)查找，直到查找成功或查找失敗。l優(yōu)點：算法簡單。缺點：查找效率比較低。優(yōu)點：算法簡單。缺點：查找效率比較低。l用二分方法查找長度為用二分方法查找長度為n的有序線性表，最壞情況下比的有序線性表，最壞情況下比較次數(shù)為較次數(shù)為 log2n 次。次。2022-3-7大學(xué)計算機基礎(chǔ)7

56、2例 L2=( 3,12,24,37,45,53,61,78,90,100 )L2=( 3,12,24,37,45,53,61,78,90,100 )，查找，查找 Key=24Key=24的記錄的記錄 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 3 12 24 37 45 53 61 78 90 1003 12 24 37 45 53 61 78 90 100lowlowmidmid highhigh 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 3 12 24 373 12 24 37 45 53 61 78 90

57、 100 45 53 61 78 90 100lowlowmidmid highhigh 24 24 45 45 繼續(xù)在前半個表中用繼續(xù)在前半個表中用二分查找法二分查找法查找查找 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 3 12 3 12 24 3724 37 45 53 61 78 90 100 45 53 61 78 90 100Low mid highLow mid high 24 24 12 12 繼續(xù)在后半個表中用繼續(xù)在后半個表中用二分查找法二分查找法查找查找查找成功2022-3-7大學(xué)計算機基礎(chǔ)73l交換類排序交換類排序l插入類排序插入類

58、排序l選擇類排序選擇類排序5.7 排序2022-3-7大學(xué)計算機基礎(chǔ)741. 交換類排序交換類排序 交換類排序的主要思想是：每次比交換類排序的主要思想是：每次比較待排序列的兩個元素，如果這兩個元較待排序列的兩個元素，如果這兩個元素的值的次序與排序要求的次序相反時，素的值的次序與排序要求的次序相反時，則交換兩者的位置，直到整個序列全部則交換兩者的位置，直到整個序列全部有序為止。有序為止。 常用的交換類排序是：常用的交換類排序是：l冒泡排序快速排序2022-3-7大學(xué)計算機基礎(chǔ)75冒泡排序冒泡排序l冒泡排序的基本思想是：相鄰的兩個元素進行冒泡排序的基本思想是：相鄰的兩個元素進行比較，滿足條件（與要

59、排序的順序相反）就交比較，滿足條件（與要排序的順序相反）就交換。換。l一趟冒泡排序的結(jié)果是把最大（或最?。┑姆乓惶嗣芭菖判虻慕Y(jié)果是把最大（或最?。┑姆诺搅俗詈?，就像重的東西沉到了水底（或輕的到了最后，就像重的東西沉到了水底（或輕的東西浮到了水面）。東西浮到了水面）。l對剩下的元素作相同的操作，直到整個線性表對剩下的元素作相同的操作，直到整個線性表有序。對有序。對n個元素進行排序，冒泡的過程要個元素進行排序，冒泡的過程要n-1趟。趟。l最壞情況下，冒泡排序需要比較最壞情況下，冒泡排序需要比較n(n-1)/2次。次。2022-3-7大學(xué)計算機基礎(chǔ)76例例 用起泡排序法對以下記錄進行排序：用起泡排序

60、法對以下記錄進行排序： 49、38、65、97、76、13、27、49分析： 49 38 65 97 76 13 27 49 38 49 65 97 76 13 27 49 38 49 65 97 76 13 27 49 38 49 65 97 76 13 27 49 38 49 65 76 97 13 27 49 38 49 65 76 13 97 27 49 38 49 65 76 13 27 9749 38 49 65 76 13 27 49 97 49 38 65 97 76 13 27 49一趟起泡排序一趟起泡排序初始初始狀態(tài)狀態(tài)最大者最大者沉底沉底下一趟下一趟只需排只需排的記錄的記