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

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

2、慮和處理。機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。l 一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。的不可分割的最小單位。l數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象(Data Object)：是性質(zhì)相同的數(shù)據(jù)元素的集合。：是性質(zhì)相同的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個(gè)子集。是數(shù)據(jù)的一個(gè)子集。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é)計(jì)算機(jī)基礎(chǔ)3 數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容 1） 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的

3、邏輯結(jié)構(gòu)2） 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)3） 數(shù)據(jù)結(jié)構(gòu)的運(yùn)算數(shù)據(jù)結(jié)構(gòu)的運(yùn)算2022-3-7大學(xué)計(jì)算機(jī)基礎(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ù)在計(jì)算機(jī)內(nèi)的存儲(chǔ)方式無關(guān)。與數(shù)據(jù)在計(jì)算機(jī)內(nèi)的存儲(chǔ)方式無關(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)等。例如：有一個(gè)包含了例如：有一個(gè)包含了4個(gè)元素的數(shù)據(jù)集合個(gè)元素的數(shù)據(jù)集合小小學(xué)，初中，高中，大學(xué)學(xué)，初中，高中，大學(xué)。2

4、022-3-7大學(xué)計(jì)算機(jī)基礎(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)描述了兩個(gè)所以，數(shù)據(jù)的邏輯結(jié)構(gòu)描述了兩個(gè)方面的信息：方面的信息： 描述數(shù)據(jù)元素的信息；描述數(shù)據(jù)元素的信息； 描述數(shù)據(jù)元素之間的前后件關(guān)系的信息。描述數(shù)據(jù)元素之間的前后件關(guān)系的信息。2022-3-7大學(xué)計(jì)算機(jī)基礎(chǔ)62） 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)方式就是數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（也稱的存儲(chǔ)方式就是數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)構(gòu)）。數(shù)據(jù)的物

5、理結(jié)構(gòu)）。 基本的存儲(chǔ)結(jié)構(gòu)有：順序存儲(chǔ)結(jié)構(gòu)、基本的存儲(chǔ)結(jié)構(gòu)有：順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、索引存儲(chǔ)結(jié)構(gòu)、散列存鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、索引存儲(chǔ)結(jié)構(gòu)、散列存儲(chǔ)結(jié)構(gòu)。儲(chǔ)結(jié)構(gòu)。2022-3-7大學(xué)計(jì)算機(jī)基礎(chǔ)73） 數(shù)據(jù)結(jié)構(gòu)的運(yùn)算數(shù)據(jù)結(jié)構(gòu)的運(yùn)算 數(shù)據(jù)結(jié)構(gòu)的運(yùn)算一般包括：插入、數(shù)據(jù)結(jié)構(gòu)的運(yùn)算一般包括：插入、刪除、查找、分類、合并、分解、復(fù)制、刪除、查找、分類、合并、分解、復(fù)制、修改等。修改等。2022-3-7大學(xué)計(jì)算機(jī)基礎(chǔ)82. 數(shù)據(jù)結(jié)構(gòu)的表示數(shù)據(jù)結(jié)構(gòu)的表示1） 二元關(guān)系表示法二元關(guān)系表示法2） 圖形表示法圖形表示法2022-3-7大學(xué)計(jì)算機(jī)基礎(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é)計(jì)算機(jī)基礎(chǔ)10例例1：求學(xué)歷程：求學(xué)歷程 B=（D,R） D= 小學(xué)，初中，高中，大學(xué)小學(xué)，初中，高中，大學(xué) R= （小學(xué)，初中），（初中，高中），（高中，（小學(xué)，初中），（初中，高中），（高中，大學(xué)）大學(xué)） 例例2：我國(guó)的行政區(qū)劃分：我國(guó)的行政區(qū)劃分 B=（D,R） D= 中國(guó)，省，自治區(qū)，直轄市，北京，天津，中國(guó)，省，自治區(qū)，直轄市，北京，天津，上海，重慶上海，重慶 R= （中國(guó)，?。ㄖ袊?guó)，自治區(qū)），（中國(guó)，

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

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

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

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

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

12、一維數(shù)組實(shí)現(xiàn)順序表。般用一維數(shù)組實(shí)現(xiàn)順序表。2022-3-7大學(xué)計(jì)算機(jī)基礎(chǔ)18 對(duì)于順序表，可以用公式計(jì)算對(duì)于順序表，可以用公式計(jì)算出任一元素的存儲(chǔ)位置。出任一元素的存儲(chǔ)位置。 如果第一個(gè)數(shù)據(jù)元素存放位置為L(zhǎng)OC(a i)，每個(gè)元素需占用 個(gè)存儲(chǔ)單元，則線性表中第i+1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置和第i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置之間滿足下列關(guān)系： LOC(a i+1)=LOC(a i)+ 線性表的第i個(gè)數(shù)據(jù)元素ai的存儲(chǔ)位置為： 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é)計(jì)算機(jī)基礎(chǔ)192） 順序表的運(yùn)算順序表的運(yùn)算 順序表的運(yùn)算主要有：插入、刪除、順序表的運(yùn)算主要有：插入、刪除、查找、排序、分解、合并和逆轉(zhuǎn)。排序和查找、排序、分解、合并和逆轉(zhuǎn)。排序和查找將在后面介紹，這里介紹一下插入和查找將在后面介紹，這里介紹一下插入和刪除運(yùn)算。刪除運(yùn)算。2022-3-7大學(xué)計(jì)算機(jī)基礎(chǔ)20u插入運(yùn)算插入運(yùn)算55557468923555573146892312345123456插入31插入前n=5插入后n=6注：平均情況下，順序表的插入運(yùn)算需要移動(dòng)表中一半的元素。2022-3-7大學(xué)計(jì)算機(jī)基礎(chǔ)21u刪除運(yùn)算刪除運(yùn)算5555746892355557

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

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

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

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

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

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

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

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

22、有記憶功能。棧具有記憶功能。2022-3-7大學(xué)計(jì)算機(jī)基礎(chǔ)342. 棧的順序存儲(chǔ)結(jié)構(gòu)棧的順序存儲(chǔ)結(jié)構(gòu) 棧的順序存儲(chǔ)結(jié)構(gòu)也稱為順序棧，它是一種運(yùn)算棧的順序存儲(chǔ)結(jié)構(gòu)也稱為順序棧，它是一種運(yùn)算受限的順序表。受限的順序表。 對(duì)順序棧可以有對(duì)順序?？梢杂?種運(yùn)算：種運(yùn)算：CBAtopbottom54321EDCBAtopbottom54321DCBAtopbottom54321(a) 初始棧 (b) 元素D和E入棧后 (c)元素E出棧后 2022-3-7大學(xué)計(jì)算機(jī)基礎(chǔ)35（1）入棧運(yùn)算）入棧運(yùn)算向棧中插入元素的過程稱為入棧運(yùn)算。向棧中插入元素的過程稱為入棧運(yùn)算?；痉椒ㄊ牵夯痉椒ㄊ牵簂將棧頂指針將棧頂

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

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

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

26、時(shí)，無法讀取棧頂元素。2022-3-7大學(xué)計(jì)算機(jī)基礎(chǔ)383. 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也稱為鏈棧，它可以看作一種運(yùn)算棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也稱為鏈棧，它可以看作一種運(yùn)算受限的線性鏈表，插入和刪除操作只允許在線性鏈表的一受限的線性鏈表，插入和刪除操作只允許在線性鏈表的一端進(jìn)行。端進(jìn)行。top(a) 鏈棧的邏輯示意圖 (b) 鏈棧的入棧運(yùn)算 (c)鏈棧的出棧運(yùn)算 DCBADCBAPtopDCBAPtop2022-3-7大學(xué)計(jì)算機(jī)基礎(chǔ)39（1）入棧運(yùn)算）入棧運(yùn)算鏈棧的入棧運(yùn)算就是向鏈棧中插入一個(gè)新的元素。鏈棧的入棧運(yùn)算就是向鏈棧中插入一個(gè)新的元素。基本方法是：基本方法是：l先為新

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

42、點(diǎn)的有限集合，具有兩個(gè)特點(diǎn)：l如果二叉樹非空，則有且只有一個(gè)根結(jié)點(diǎn)；如果二叉樹非空，則有且只有一個(gè)根結(jié)點(diǎn)；l每個(gè)結(jié)點(diǎn)最多有兩個(gè)子結(jié)點(diǎn)，分別以這兩個(gè)子結(jié)點(diǎn)作為每個(gè)結(jié)點(diǎn)最多有兩個(gè)子結(jié)點(diǎn)，分別以這兩個(gè)子結(jié)點(diǎn)作為根結(jié)點(diǎn)組成該結(jié)點(diǎn)的左子樹和右子樹。根結(jié)點(diǎn)組成該結(jié)點(diǎn)的左子樹和右子樹。二叉樹的度最大為二叉樹的度最大為2。 A A F F G G E E D D C C B B2022-3-7大學(xué)計(jì)算機(jī)基礎(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)的左子樹有四個(gè)結(jié)點(diǎn)，(b)的左子樹有兩

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

44、滿二叉樹的任何一層上，結(jié)點(diǎn)的數(shù)目都達(dá)到最大值。大值。 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é)計(jì)算機(jī)基礎(chǔ)60 完全二叉樹完全二叉樹 完全二叉樹是指除了最后一層外，每一層完全二叉樹是指除了最后一層外，每一層的結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)，而在最后一層上，右的結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)，而在最后一層上，右邊的若干結(jié)點(diǎn)缺失的二叉樹。邊的若干結(jié)點(diǎn)缺失的二叉樹。 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é)計(jì)算機(jī)

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

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

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

48、結(jié)點(diǎn)也是由數(shù)據(jù)域和指針域組成。是由數(shù)據(jù)域和指針域組成。L(i)V(i)R(i)存儲(chǔ)序號(hào) 左指針域 數(shù)據(jù)域 右指針域i2022-3-7大學(xué)計(jì)算機(jī)基礎(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é)計(jì)算機(jī)基礎(chǔ)654. 二叉樹的遍歷二叉樹的遍歷 二叉樹的遍歷是指沿某條路徑不重復(fù)地訪二叉樹的遍歷是指沿某條路徑不重復(fù)地訪問二叉樹中的所有結(jié)點(diǎn)。這里的訪問是指對(duì)結(jié)問二叉樹中的所有結(jié)點(diǎn)。這里的訪問是指對(duì)結(jié)點(diǎn)進(jìn)行某種處理，如讀、寫、改等。點(diǎn)進(jìn)行某種處理，如讀、寫、改等。 二叉樹遍歷過程中涉及訪問根

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

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

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

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

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

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

55、元素的大小，如果被查元素大于中間元素，則要在元素值較大的子如果被查元素大于中間元素，則要在元素值較大的子表中繼續(xù)使用二分法繼續(xù)查找，如果被查元素小于中表中繼續(xù)使用二分法繼續(xù)查找，如果被查元素小于中間元素，則要在元素值較小的子表中繼續(xù)使用二分法間元素，則要在元素值較小的子表中繼續(xù)使用二分法繼續(xù)查找，直到查找成功或查找失敗。繼續(xù)查找，直到查找成功或查找失敗。l優(yōu)點(diǎn)：算法簡(jiǎn)單。缺點(diǎn)：查找效率比較低。優(yōu)點(diǎn)：算法簡(jiǎn)單。缺點(diǎn)：查找效率比較低。l用二分方法查找長(zhǎng)度為用二分方法查找長(zhǎng)度為n的有序線性表，最壞情況下比的有序線性表，最壞情況下比較次數(shù)為較次數(shù)為 log2n 次。次。2022-3-7大學(xué)計(jì)算機(jī)基礎(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ù)在前半個(gè)表中用繼續(xù)在前半個(gè)表中用二分查找法二分查找法查找查找 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ù)在后半個(gè)表中用繼續(xù)在后半個(gè)表中用二分查找法二分查找法查找查找查找成功2022-3-7大學(xué)計(jì)算機(jī)基礎(chǔ)73l交換類排序交換類排序l插入類排序插入類

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

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

60、法對(duì)以下記錄進(jìn)行排序： 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)最大者最大者沉底沉底下一趟下一趟只需排只需排的記錄的記