大學計算機基礎 第4章 數(shù)據(jù)結構

1、HEU第第4 4章章 數(shù)據(jù)結構數(shù)據(jù)結構數(shù)據(jù)結構數(shù)據(jù)結構主要內容主要內容數(shù)據(jù)結構概述數(shù)據(jù)結構概述線性表及其操作線性表及其操作樹與二叉樹樹與二叉樹數(shù)據(jù)結構數(shù)據(jù)結構數(shù)據(jù)結構概述數(shù)據(jù)結構概述080611080611 班號班號 82519610 82519610 計算機學院辦公室電話號碼計算機學院辦公室電話號碼10001 10001 哈工程大學郵編哈工程大學郵編230102780618748 230102780618748 身份證號碼身份證號碼 例1：0806118251961010004230102780618748結論結論1.雜亂的數(shù)據(jù)不能表達和交流信息雜亂的數(shù)據(jù)不能表達和交流信息結論結論2.數(shù)據(jù)之

2、間是有聯(lián)系的數(shù)據(jù)之間是有聯(lián)系的 結論結論數(shù)據(jù)之間是有結構的數(shù)據(jù)之間是有結構的結論結論在某種數(shù)據(jù)結構上可定義一組運算在某種數(shù)據(jù)結構上可定義一組運算數(shù)據(jù)結構數(shù)據(jù)結構 的主要內容的主要內容例例2 電話號碼查詢系統(tǒng)電話號碼查詢系統(tǒng) 設有一個電話號碼薄，它記錄了設有一個電話號碼薄，它記錄了n個人的名字和其相應的電個人的名字和其相應的電話號碼，假定按如下形式安排：話號碼，假定按如下形式安排： (a(a1 1，b b1 1)(a)(a2 2，b b2 2)(a)(an n，b bn n) )其中其中ai，bi(i=1，2n) 分別表示某人的名字和對應電話號碼分別表示某人的名字和對應電話號碼問題：問題：設計一

3、個算法，當給定任何一個人的名字時，該算法設計一個算法，當給定任何一個人的名字時，該算法能夠打印出此人的電話號碼，如果該電話簿中根本就沒有能夠打印出此人的電話號碼，如果該電話簿中根本就沒有這個人，則該算法也能夠報告沒有這個人的標志。這個人，則該算法也能夠報告沒有這個人的標志。要做的事情：要做的事情：設計恰當?shù)臄?shù)學模型表示電話號碼簿的所有信息設計恰當?shù)臄?shù)學模型表示電話號碼簿的所有信息采用相應查找算法采用相應查找算法,實現(xiàn)快速查詢與打印實現(xiàn)快速查詢與打印.結論結論2.數(shù)據(jù)之間是有聯(lián)系的數(shù)據(jù)之間是有聯(lián)系的 這些聯(lián)系常常影響算法的選擇和效率。這些聯(lián)系常常影響算法的選擇和效率。 數(shù)據(jù)結構數(shù)據(jù)結構 的主要內

4、容的主要內容例例3: 鋪設煤氣管道問題鋪設煤氣管道問題n個居民區(qū)之間鋪設煤氣管道，個居民區(qū)之間鋪設煤氣管道，只要鋪設只要鋪設n-1條管道即可。條管道即可。假設假設: 任意兩個居民區(qū)之間都可以任意兩個居民區(qū)之間都可以架設管道，架設管道， 每條管道的費用成本不同，每條管道的費用成本不同，要解決的問題要解決的問題: 用一定的數(shù)據(jù)模型表示該問用一定的數(shù)據(jù)模型表示該問題，在此基礎上計算投資最題，在此基礎上計算投資最少（或盡可能少的）的管道少（或盡可能少的）的管道鋪設方案。鋪設方案。CBAED325416216945364740CBAED32162136數(shù)據(jù)結構數(shù)據(jù)結構職工號職工號姓名姓名性別性別出生年月

5、出生年月職務職務單位單位0101郭建成郭建成男男19521952年年8 8月月處長處長 0202肖明肖明男男19581958年年6 6月月科長科長教材科教材科0303晨曦晨曦女女19541954年年1212月月科長科長考務科考務科0404趙麗霞趙麗霞女女19621962年年8 8月月主任主任辦公室辦公室0505崔小龍崔小龍男男19491949年年8 8月月科員科員教材科教材科0606袁莉袁莉女女19651965年年4 4月月科員科員教材科教材科0707王芳王芳女女19621962年年6 6月月科員科員考務科考務科0808張宏愿張宏愿男男19571957年年3 3月月科員科員考務科考務科0909

6、馬明華馬明華男男19651965年年1010月月科員科員考務科考務科1010李冰李冰男男19661966年年7 7月月科員科員辦公室辦公室例例3 3 表表1-1 教務處人事簡表教務處人事簡表 1010條記錄，每條記錄有條記錄，每條記錄有6 6個數(shù)據(jù)項，每條記錄的職工號不同，個數(shù)據(jù)項，每條記錄的職工號不同， 用職工號來代表整個職工記錄。用職工號來代表整個職工記錄。 03080207040609100501按按職職工工年年齡齡從從大大到到小小排排列列03080207040609100501領導和領導和被領導的關系被領導的關系07040810090205060301朋友關系朋友關系線性線性結構結構樹

7、型樹型結構結構圖形圖形結構結構結論結論數(shù)據(jù)之間是有結構的數(shù)據(jù)之間是有結構的數(shù)據(jù)結構數(shù)據(jù)結構 的主要內容的主要內容例例4：圖書目錄管理：圖書目錄管理書目信息：書目信息： 書名，作者，登錄號，分類，出版年月書名，作者，登錄號，分類，出版年月對圖書目錄操作：對圖書目錄操作： 查找：某書在書庫中是否存在？查找：某書在書庫中是否存在？ 插入：購進新書時的登錄；插入：購進新書時的登錄； 刪除：報廢或丟失的書，需從目錄中去掉；刪除：報廢或丟失的書，需從目錄中去掉；結論結論 在某種數(shù)據(jù)結構上可定義一組運算在某種數(shù)據(jù)結構上可定義一組運算數(shù)據(jù)結構數(shù)據(jù)結構數(shù)據(jù)的各種數(shù)據(jù)的各種邏輯結構邏輯結構和和物理結構物理結構，以

8、及，以及它們之間的相應關系它們之間的相應關系對每種結構定義相適應的各種運算對每種結構定義相適應的各種運算設計出相應的算法設計出相應的算法分析算法的效率分析算法的效率 的主要內容的主要內容數(shù)據(jù)結構數(shù)據(jù)結構基本術語基本術語數(shù)據(jù)數(shù)據(jù) 描述客觀事物的描述客觀事物的符號的符號的集合集合結構結構 數(shù)據(jù)元素之間具有的關系。數(shù)據(jù)元素之間具有的關系。數(shù)據(jù)結構數(shù)據(jù)結構 具有結構的數(shù)據(jù)元素的集合。具有結構的數(shù)據(jù)元素的集合。數(shù)據(jù)元素數(shù)據(jù)元素 數(shù)據(jù)整體中相對獨立數(shù)據(jù)整體中相對獨立的基本單位的基本單位,也稱為數(shù)據(jù)也稱為數(shù)據(jù)結點。結點。 數(shù)據(jù)對象數(shù)據(jù)對象 具有相同特性的數(shù)據(jù)元素具有相同特性的數(shù)據(jù)元素的的集合。集合。數(shù)據(jù)結構

9、數(shù)據(jù)結構數(shù)據(jù)的邏輯結構和存儲結構數(shù)據(jù)的邏輯結構和存儲結構某種邏輯結構的數(shù)某種邏輯結構的數(shù)據(jù)在計算機據(jù)在計算機存儲器存儲器中的存儲方式。中的存儲方式。數(shù)據(jù)元素之間具有數(shù)據(jù)元素之間具有的的邏輯關系邏輯關系(結構結構)邏輯結構邏輯結構物理結構物理結構數(shù)據(jù)結構數(shù)據(jù)結構數(shù)據(jù)的邏輯結構和存儲結構數(shù)據(jù)的邏輯結構和存儲結構線性結構線性結構樹型結構樹型結構圖狀結構圖狀結構純集合結構純集合結構數(shù)據(jù)結構數(shù)據(jù)結構職工號職工號姓名姓名性別性別出生年月出生年月職務職務單位單位0101郭建成郭建成男男19521952年年8 8月月處長處長 0202肖明肖明男男19581958年年6 6月月科長科長教材科教材科0303晨曦晨

10、曦女女19541954年年1212月月科長科長考務科考務科0404趙麗霞趙麗霞女女19621962年年8 8月月主任主任辦公室辦公室0505崔小龍崔小龍男男19491949年年8 8月月科員科員教材科教材科0606袁莉袁莉女女19651965年年4 4月月科員科員教材科教材科0707王芳王芳女女19621962年年6 6月月科員科員考務科考務科0808張宏愿張宏愿男男19571957年年3 3月月科員科員考務科考務科0909馬明華馬明華男男19651965年年1010月月科員科員考務科考務科1010李冰李冰男男19661966年年7 7月月科員科員辦公室辦公室例例5 5 表表1-1 教務處人事

11、簡表教務處人事簡表 1010條記錄，每條記錄有條記錄，每條記錄有6 6個數(shù)據(jù)項，每條記錄的職工號不同，個數(shù)據(jù)項，每條記錄的職工號不同， 用職工號來代表整個職工記錄。用職工號來代表整個職工記錄。 03080207040609100501按按職職工工年年齡齡從從大大到到小小排排列列03080207040609100501領導和領導和被領導的關系被領導的關系07040810090205060301朋友關系朋友關系線性線性結構結構樹型樹型結構結構圖形圖形結構結構07040603性別關系性別關系集合集合結構結構數(shù)據(jù)結構數(shù)據(jù)結構數(shù)據(jù)的邏輯結構和存儲結構數(shù)據(jù)的邏輯結構和存儲結構順序存儲結構順序存儲結構鏈式存

12、儲結構鏈式存儲結構數(shù)據(jù)結構數(shù)據(jù)結構線性表及其基本操作線性表及其基本操作學生成績登記表學生成績登記表姓姓 名名英語英語C語言語言高數(shù)高數(shù)學號學號丁一丁一9678870101李二李二8790780102張三張三6786860103孫紅孫紅6981960104王冬王冬8774660105數(shù)據(jù)結構數(shù)據(jù)結構線性表及其基本操作線性表及其基本操作職工工資登記表職工工資登記表(線性表線性表)姓姓 名名崗位津貼崗位津貼基本工資基本工資獎金獎金職工號職工號丁一丁一6002782000101李二李二3001901000102張三張三3001861000103孫紅孫紅5002182000104王冬王冬30019010

13、00105數(shù)據(jù)元素可以有若干數(shù)據(jù)項構成，比如數(shù)據(jù)元素可以有若干數(shù)據(jù)項構成，比如1個記錄個記錄那么數(shù)據(jù)元素之間的是什么關系？那么數(shù)據(jù)元素之間的是什么關系？數(shù)據(jù)結構數(shù)據(jù)結構線性表及其基本操作線性表及其基本操作線性表：線性表：簡稱簡稱表表，是，是n（n0）個具有）個具有相同類相同類型型的數(shù)據(jù)元素的的數(shù)據(jù)元素的有限序列有限序列。線性表的長度：線性表的長度：線性表中數(shù)據(jù)元素的線性表中數(shù)據(jù)元素的個數(shù)個數(shù)。空表：空表：長度等于長度等于零零的線性表，記為：的線性表，記為：L=( )。非空表記為非空表記為：L（a1, a2 , , ai-1, ai , , an)線性表的定義線性表的定義其中，其中，ai（1in

14、）稱為數(shù)據(jù)元素；）稱為數(shù)據(jù)元素；下角標下角標 i 表示該元素在線性表中的位置或序號表示該元素在線性表中的位置或序號 。數(shù)據(jù)結構數(shù)據(jù)結構線性表及其基本操作線性表及其基本操作a1a3a4ana2線性表的圖形表示線性表的圖形表示線性表線性表（a1, a2 , , ai-1, ai , , an)的圖形表示如下：的圖形表示如下：幾個線性表的例子幾個線性表的例子 數(shù)列數(shù)列： ( 25， 12， 78， 34， 100， 88)1 1a1 a2 a3 a4 a5 a6數(shù)據(jù)元素為整數(shù)數(shù)據(jù)元素為整數(shù)2 2字母表字母表： ( A， B， C， , Z)a1 a2 a3 a26數(shù)據(jù)元素字母數(shù)據(jù)元素字母數(shù)據(jù)結構數(shù)據(jù)

15、結構線性表及其基本操作線性表及其基本操作a1a3a4ana2線性表的特性線性表的特性1.有限性有限性：線性表中數(shù)據(jù)元素的個數(shù)是有窮的。：線性表中數(shù)據(jù)元素的個數(shù)是有窮的。2.相同性相同性：線性表中數(shù)據(jù)元素的類型是同一的。：線性表中數(shù)據(jù)元素的類型是同一的。3.順序性順序性：線性表中相鄰的數(shù)據(jù)元素：線性表中相鄰的數(shù)據(jù)元素ai-1和和ai之間存在之間存在序偶關系序偶關系(ai-1, ai)，即，即ai-1是是ai的的前驅前驅， ai是是ai-1的的后繼后繼；a1 無前驅，無前驅，an無后繼，其它每個元素有且僅有一個前無后繼，其它每個元素有且僅有一個前驅和一個后繼。驅和一個后繼。 數(shù)據(jù)結構數(shù)據(jù)結構線性表

16、的順序存儲結構線性表的順序存儲結構順序表順序表線性表的順序存儲結構線性表的順序存儲結構例：例：（34, 23, 67, 43）34236743 4存儲要點存儲要點用一段地址用一段地址連續(xù)連續(xù)的存儲單元的存儲單元依次依次存儲線性表中的數(shù)據(jù)元素存儲線性表中的數(shù)據(jù)元素數(shù)據(jù)結構數(shù)據(jù)結構線性表的順序存儲結構線性表的順序存儲結構如何求得任意元素的存儲地址？如何求得任意元素的存儲地址？ 0 i-2 i-1 n-1 Max-1 a1 ai-1 ai an 空閑空閑 長度長度順序表順序表一般情況下，一般情況下，(a1，a2，, ai-1，ai , , an)的順序存儲：的順序存儲：cLoc(ai)Loc(a1)

17、數(shù)據(jù)結構數(shù)據(jù)結構線性表的順序存儲結構線性表的順序存儲結構 0 i-2 i-1 n-1 Max-1 a1 ai-1 ai an 空閑空閑 長度長度Loc(ai)=Loc(a1) + (i - -1)c順序表順序表cLoc(ai)Loc(a1)一般情況下，一般情況下，(a1，a2，, ai-1，ai , , an)的順序存儲：的順序存儲：數(shù)據(jù)結構數(shù)據(jù)結構線性表的順序存儲結構線性表的順序存儲結構33例：例：（3535，1212，2424，4242），），在在i=i=2 2的位置上插入的位置上插入3333。順序表的插入順序表的插入 435122442a1a2a3a40 1 2 3 4422412335

18、什么時候不能插入什么時候不能插入？注意邊界條件注意邊界條件表滿：表滿：length=MaxSize合理的插入位置：合理的插入位置：1in（i是元素的序號）是元素的序號）數(shù)據(jù)結構數(shù)據(jù)結構線性表的順序存儲結構線性表的順序存儲結構例：（例：（35, 33, 12, 24, 42），），刪除刪除i=2的數(shù)據(jù)元素。的數(shù)據(jù)元素。順序表的刪除順序表的刪除 535a1a2a3a40 1 2 3 4422412334a5122442刪除后順序表的內容刪除后順序表的內容需要考慮的異常情況：需要考慮的異常情況：(1). .是否表空？是否表空？(2). .刪除位置是否合適刪除位置是否合適？(正常位置：正常位置：1in

19、)數(shù)據(jù)結構數(shù)據(jù)結構線性表的鏈式存儲結構線性表的鏈式存儲結構存儲思想：存儲思想：用一組用一組任意任意的存儲單元存放線性表的元素的存儲單元存放線性表的元素。連續(xù)連續(xù)不連續(xù)不連續(xù)零散分布零散分布單鏈表：單鏈表：線性表的鏈接存儲結構。線性表的鏈接存儲結構。數(shù)據(jù)結構數(shù)據(jù)結構線性表的鏈式存儲結構線性表的鏈式存儲結構單鏈表單鏈表結點結點數(shù)據(jù)域數(shù)據(jù)域指針域指針域單鏈表是由若干單鏈表是由若干結點結點構成的；構成的；單鏈表的結點只有一個指針域。單鏈表的結點只有一個指針域。data：存儲數(shù)據(jù)元素存儲數(shù)據(jù)元素next：存儲指向后繼結點的地址存儲指向后繼結點的地址 data next單鏈表的結點結構：單鏈表的結點結構：

20、數(shù)據(jù)域數(shù)據(jù)域指針域指針域0200020803000325 a10200 a20325 a30300 a4 數(shù)據(jù)結構數(shù)據(jù)結構線性表的鏈式存儲結構線性表的鏈式存儲結構0200020803000325存儲特點：存儲特點：1. 邏輯次序和物理次序邏輯次序和物理次序 不一定相同。不一定相同。 2.元素之間的邏輯關系元素之間的邏輯關系 用用指針指針表示。表示。例：例：(a1, a2 ,a3, a4)的存儲示意圖的存儲示意圖單鏈表單鏈表 a10200 a20325 a30300 a4 data next數(shù)據(jù)結構數(shù)據(jù)結構線性表的鏈式存儲結構線性表的鏈式存儲結構單鏈表的插入：在第單鏈表的插入：在第i個結點后插入

21、一個新結點個結點后插入一個新結點思想：思想： 1) 從第從第1個結點出發(fā)，找到第個結點出發(fā)，找到第i個結點；個結點； 2) 將新結點插入其后將新結點插入其后 3) 返回操作結果信息返回操作結果信息(成功與否成功與否)plista2a1aianai+1ppxq 頭指針頭指針空指針空指針p數(shù)據(jù)結構數(shù)據(jù)結構線性表的鏈式存儲結構線性表的鏈式存儲結構單鏈表的刪除：刪除第單鏈表的刪除：刪除第i個結點個結點思想：思想： 1) 從第從第1個結點出發(fā)，找到第個結點出發(fā)，找到第i-1個結點；個結點； 2) 刪除第刪除第i個結點個結點 3) 返回操作結果信息返回操作結果信息(成功與否成功與否)plista2a1ai

22、-1ai+1aippq數(shù)據(jù)結構數(shù)據(jù)結構棧的概念及實現(xiàn)棧的概念及實現(xiàn)棧：棧：限定僅在限定僅在表尾表尾進行插入和刪除操作的進行插入和刪除操作的線性表線性表?？諚＃嚎諚＃翰缓魏螖?shù)據(jù)元素的棧。不含任何數(shù)據(jù)元素的棧。 （a1, a2, , an）棧頂棧頂棧底棧底允許插入和刪除的一端稱為允許插入和刪除的一端稱為棧頂棧頂，另一端稱為，另一端稱為棧底棧底。 a1a2a3數(shù)據(jù)結構數(shù)據(jù)結構棧的概念及實現(xiàn)棧的概念及實現(xiàn)a1a2a3入棧入棧出棧出棧棧底棧底棧頂棧頂插入：入棧、進棧、壓棧插入：入棧、進棧、壓棧刪除：出棧、彈棧刪除：出棧、彈棧棧頂棧頂棧頂棧頂棧的示意圖棧的示意圖數(shù)據(jù)結構數(shù)據(jù)結構棧的概念及實現(xiàn)棧的概念及實

23、現(xiàn)棧的操作特性：棧的操作特性：后進先出后進先出a1a2a3入棧入棧出棧出棧棧底棧底棧頂棧頂插入：入棧、進棧、壓棧插入：入棧、進棧、壓棧刪除：出棧、彈棧刪除：出棧、彈棧棧頂棧頂棧的示意圖棧的示意圖數(shù)據(jù)結構數(shù)據(jù)結構棧的概念及實現(xiàn)棧的概念及實現(xiàn)例：有三個元素按例：有三個元素按a、b、c的次序依次進棧，且每個的次序依次進棧，且每個元素只允許進一次棧，則可能的出棧序列有多少種？元素只允許進一次棧，則可能的出棧序列有多少種？棧底棧底棧頂棧頂ab棧頂棧頂c棧頂棧頂 情況情況1：出棧序列：出棧序列：c b a數(shù)據(jù)結構數(shù)據(jù)結構棧的概念及實現(xiàn)棧的概念及實現(xiàn)例：有三個元素按例：有三個元素按a、b、c的次序依次進棧，

24、且每個的次序依次進棧，且每個元素只允許進一次棧，則可能的出棧序列有多少種？元素只允許進一次棧，則可能的出棧序列有多少種？ 情況情況2：棧底棧底棧頂棧頂ab棧頂棧頂c出棧序列：出棧序列：b c a注意：注意：棧只限制插入和刪除棧只限制插入和刪除位置位置， 沒有限定插入和沒有限定插入和 刪除的刪除的次序次序。 a,b,ca,b,c: : abc(aabc(a進進a a出，出，b b進進b b出，出，c c進進c c出）出） a,bca,bc : : acbacb (a (a進進a a出，出，bcbc進，進，cbcb出）出） ab,cab,c : : bacbac ( (abab進，進，baba出，

25、出，c c進進c c出）出） bcabca ( (abab進，進，b b出，出，caca出）出） abcabc : : c cbaba ( (abcabc進，進，cbacba出）出）只一種情況只一種情況數(shù)據(jù)結構數(shù)據(jù)結構進一步的例題（進一步的例題（P145P145四四1 1）：）：已知四個入棧元素。寫出全部出已知四個入棧元素。寫出全部出棧序列棧序列A,B,C,D: ABCD A,BC,D: ACBD/ACDB A,B,CD: ABDC A,BCD: ADCB AB,C,D: BACD/BCAD/BCDA AB,CD: BADC/BDCA ABC,D: CDBA/CBDA/CBAD ABCD: D

26、CBA特點：特點：D開頭的只有一種開頭的只有一種數(shù)據(jù)結構數(shù)據(jù)結構 一個棧的輸入序列為一個棧的輸入序列為1 2 3 4 5，則下列序列中不可能是，則下列序列中不可能是棧的輸出序列的是棧的輸出序列的是_ A） 2 3 4 1 5 B） 2 3 1 4 5 C） 5 4 1 3 2 D） 1 5 4 3 2數(shù)據(jù)結構數(shù)據(jù)結構棧的概念及實現(xiàn)棧的概念及實現(xiàn)棧的順序存儲結構及實現(xiàn)棧的順序存儲結構及實現(xiàn) 順序棧順序棧棧的順序存儲結構棧的順序存儲結構如何改造數(shù)組實現(xiàn)棧的順序存儲？如何改造數(shù)組實現(xiàn)棧的順序存儲？ 0 1 2 3 4 5 6 7 8a1確定用數(shù)組的哪一端表示棧底。確定用數(shù)組的哪一端表示棧底。附設指針

27、附設指針top指示棧頂元素在數(shù)組中的位置。指示棧頂元素在數(shù)組中的位置。 top數(shù)據(jù)結構數(shù)據(jù)結構棧的概念及實現(xiàn)棧的概念及實現(xiàn)出棧：出棧：top減減1進棧：進棧：top加加1?？眨簵？眨簍op= - -1 0 1 2 3 4 5 6 7 8a1topa2topa3top棧滿：棧滿：top= MAX_SIZE棧的順序存儲結構及實現(xiàn)棧的順序存儲結構及實現(xiàn) 插入一般稱為進棧（插入一般稱為進棧（PUSH），刪除則稱為退棧（），刪除則稱為退棧（POP） 數(shù)據(jù)結構數(shù)據(jù)結構隊列隊列隊列的邏輯結構隊列的邏輯結構空隊列：空隊列：不含任何數(shù)據(jù)元素的隊列。不含任何數(shù)據(jù)元素的隊列。 隊列：隊列：只允許在只允許在一端一端進

28、行插入操作，而進行插入操作，而另一端另一端進行進行刪除操作的線性表。刪除操作的線性表。允許插入（也稱入隊、進隊）的一端稱為隊尾，允允許插入（也稱入隊、進隊）的一端稱為隊尾，允許刪除（也稱出隊）的一端稱為隊頭。許刪除（也稱出隊）的一端稱為隊頭。 （a1, a2, , an）隊尾隊尾隊頭隊頭數(shù)據(jù)結構數(shù)據(jù)結構隊列的操作特性：隊列的操作特性：先進先出先進先出a1a2a3入隊入隊隊尾隊尾隊頭隊頭出隊出隊隊頭隊頭隊列的邏輯結構隊列的邏輯結構數(shù)據(jù)結構數(shù)據(jù)結構0 1 2 3 4 入隊入隊出隊出隊例：例：a1a2a3a4依次入隊依次入隊a1a2a3a4rearrear rear rearfront rear隊列

29、的順序存儲結構及實現(xiàn)隊列的順序存儲結構及實現(xiàn) 設置設置隊頭、隊尾隊頭、隊尾兩個指針兩個指針 數(shù)據(jù)結構數(shù)據(jù)結構例：例：a1a2依次出隊依次出隊0 1 2 3 4 入隊入隊出隊出隊a1a2a3a4rearfront front front隊列的順序存儲結構及實現(xiàn)隊列的順序存儲結構及實現(xiàn) 數(shù)據(jù)結構數(shù)據(jù)結構例：例：a1a2依次出隊依次出隊特殊線性表特殊線性表隊列隊列0 1 2 3 4 入隊入隊出隊出隊a3a4rearfront隊列的移動有什么特點？隊列的移動有什么特點？隊列的順序存儲結構及實現(xiàn)隊列的順序存儲結構及實現(xiàn) 數(shù)據(jù)結構數(shù)據(jù)結構例：例：a1a2依次出隊依次出隊特殊線性表特殊線性表隊列隊列0 1

30、2 3 4 入隊入隊出隊出隊a3a4rearfront整個隊列向數(shù)組下標較大方向移動整個隊列向數(shù)組下標較大方向移動單向移動性單向移動性隊列的順序存儲結構及實現(xiàn)隊列的順序存儲結構及實現(xiàn) 數(shù)據(jù)結構數(shù)據(jù)結構假溢出：假溢出：當元素被插入到數(shù)組中下標最大的位置上之當元素被插入到數(shù)組中下標最大的位置上之后，隊列的空間就用盡了，盡管此時數(shù)組的低端還有后，隊列的空間就用盡了，盡管此時數(shù)組的低端還有空閑空間，這種現(xiàn)象叫做假溢出?？臻e空間，這種現(xiàn)象叫做假溢出。特殊線性表特殊線性表隊列隊列繼續(xù)入隊會出現(xiàn)什么情況？繼續(xù)入隊會出現(xiàn)什么情況？0 1 2 3 4 入隊入隊出隊出隊a3a4rearfronta5rear隊列的

31、順序存儲結構及實現(xiàn)隊列的順序存儲結構及實現(xiàn) 數(shù)據(jù)結構數(shù)據(jù)結構循環(huán)隊列：循環(huán)隊列：將存儲隊列的數(shù)組頭尾相接。將存儲隊列的數(shù)組頭尾相接。特殊線性表特殊線性表隊列隊列如何解決假溢出？如何解決假溢出？0 1 2 3 4 入隊入隊出隊出隊a3a4fronta5rearreara6隊列的順序存儲結構及實現(xiàn)隊列的順序存儲結構及實現(xiàn) 隊列的鏈式存儲結構隊列的鏈式存儲結構，需要隊頭和隊尾的兩個指針。，需要隊頭和隊尾的兩個指針。數(shù)據(jù)結構數(shù)據(jù)結構樹的基本概念及存儲結構樹的基本概念及存儲結構樹的定義樹的定義樹：樹：n（n0）個個結點結點的有限的有限集合集合。當。當n0時，稱為時，稱為空樹；任意一棵非空樹滿足以下條件：

32、空樹；任意一棵非空樹滿足以下條件： 有且僅有一個特定的稱為有且僅有一個特定的稱為根根的結點；的結點； 當當n1時，除根結點之外的其余結點被分成時，除根結點之外的其余結點被分成m（m0）個個互不相交互不相交的有限集合的有限集合T1, ,T2, , , ,Tm，其中其中每個集合又是一棵樹，并稱為這個根結點的每個集合又是一棵樹，并稱為這個根結點的子樹子樹。樹的定義是采用遞歸方法樹的定義是采用遞歸方法數(shù)據(jù)結構數(shù)據(jù)結構樹的基本概念及存儲結構樹的基本概念及存儲結構A只有根結點的樹只有根結點的樹ABCDEFGHIJKLM有子樹的樹有子樹的樹根根子樹子樹數(shù)據(jù)結構數(shù)據(jù)結構樹的基本概念及存儲結構樹的基本概念及存儲

33、結構樹與非樹結構？樹與非樹結構？ 樹的定義樹的定義ACBGFEDHIACBGFDACBGFDE數(shù)據(jù)結構數(shù)據(jù)結構樹的基本概念及存儲結構樹的基本概念及存儲結構樹的應用舉例樹的應用舉例文件結構文件結構My ComputerC:D:E:etcWINDOWSProgram FilesPictureMusic數(shù)據(jù)結構數(shù)據(jù)結構樹的基本概念及存儲結構樹的基本概念及存儲結構樹的基本術語樹的基本術語結點的度：結點的度：結點所擁有的子樹的個數(shù)。結點所擁有的子樹的個數(shù)。樹的度：樹的度：樹中各結點度的最大值。樹中各結點度的最大值。CGBDEFKLHMIJA數(shù)據(jù)結構數(shù)據(jù)結構葉子結點：葉子結點：度為度為0的結點，也稱為終端

34、結點。的結點，也稱為終端結點。分支結點：分支結點：度不為度不為0的結點，也稱為非終端結點。的結點，也稱為非終端結點。CGBDEFKLHMIJA樹的基本術語樹的基本術語樹的基本概念及存儲結構樹的基本概念及存儲結構數(shù)據(jù)結構數(shù)據(jù)結構孩子、雙親：孩子、雙親：樹中某結點子樹的根結點稱為這個結點樹中某結點子樹的根結點稱為這個結點的的孩子結點孩子結點，這個結點稱為它孩子結點，這個結點稱為它孩子結點的的雙親結點雙親結點；兄弟：兄弟：具有同一個雙親的孩子結點互稱為兄弟。具有同一個雙親的孩子結點互稱為兄弟。 CGBDEFKLHMIJA樹的基本術語樹的基本術語樹的基本概念及存儲結構樹的基本概念及存儲結構數(shù)據(jù)結構數(shù)據(jù)

35、結構路徑：路徑：如果樹的結點序列如果樹的結點序列n1, n2, , nk有如下關系：有如下關系：結點結點ni是是ni+1的雙親（的雙親（1=ik），則把，則把n1, n2, , nk稱稱為一條由為一條由n1至至nk的路徑；路徑上經過的的路徑；路徑上經過的邊的個數(shù)邊的個數(shù)稱為稱為路徑長度路徑長度。 CGBDEFKLHMIJA樹的基本術語樹的基本術語樹的基本概念及存儲結構樹的基本概念及存儲結構數(shù)據(jù)結構數(shù)據(jù)結構祖先、子孫：祖先、子孫：在樹中，如果有一條路徑從結點在樹中，如果有一條路徑從結點A A到結到結點點L L，那么，那么A A、B B、E E都稱為都稱為L L的祖先，而的祖先，而B B、E E、

36、L L都稱都稱為為A A的子孫。的子孫。CGBDEFKLHMIJA樹的基本術語樹的基本術語樹的基本概念及存儲結構樹的基本概念及存儲結構數(shù)據(jù)結構數(shù)據(jù)結構結點所在層數(shù)：結點所在層數(shù)：根結點的層數(shù)為根結點的層數(shù)為1 1；對其余任何結點，；對其余任何結點，若某結點在第若某結點在第k k層，則其孩子結點在第層，則其孩子結點在第k+1k+1層。層。樹的深度：樹的深度：樹中所有結點的樹中所有結點的最大層數(shù)最大層數(shù)，也稱，也稱高度高度。1 1層層2層層4 4層層3層層高度高度4CGBDEFKLHMIJC樹的基本術語樹的基本術語樹的基本概念及存儲結構樹的基本概念及存儲結構數(shù)據(jù)結構數(shù)據(jù)結構CBDEFKLHJA71

37、234568910層序編號：層序編號：將樹中結點按照從上層到下層、同層從左將樹中結點按照從上層到下層、同層從左到右的次序依次給他們編以從到右的次序依次給他們編以從1 1開始的連續(xù)自然數(shù)。開始的連續(xù)自然數(shù)。樹的基本術語樹的基本術語樹的基本概念及存儲結構樹的基本概念及存儲結構在樹的每在樹的每一組兄弟一組兄弟結點之間結點之間定義一個定義一個從左到右從左到右的次序，的次序，則得到一則得到一棵棵有序樹；有序樹；否則稱為否則稱為無序樹無序樹 數(shù)據(jù)結構數(shù)據(jù)結構二叉樹及存儲結構二叉樹及存儲結構二叉樹的定義二叉樹的定義 二叉樹是二叉樹是n（n0）個結點的有限集合，該集合或個結點的有限集合，該集合或者為空集（稱為

38、空二叉樹），或者由一個根結點和者為空集（稱為空二叉樹），或者由一個根結點和兩棵兩棵互不相交互不相交的、分別稱為根結點的的、分別稱為根結點的左子樹左子樹和和右子右子樹樹的二叉樹組成。的二叉樹組成。問題轉化：將問題轉化：將樹樹轉換為轉換為二叉樹二叉樹，從而利用二叉樹解，從而利用二叉樹解決樹的有關問題。決樹的有關問題。研究二叉樹的意義？研究二叉樹的意義？數(shù)據(jù)結構數(shù)據(jù)結構二叉樹及存儲結構二叉樹及存儲結構二叉樹的特點：二叉樹的特點： 每個結點最多有每個結點最多有兩兩棵子樹；棵子樹； 二叉樹是二叉樹是有序有序的，其次序不的，其次序不能任意顛倒能任意顛倒。 注意：二叉樹和樹是兩種樹結構。注意：二叉樹和樹是兩

39、種樹結構。ABCDEFGABAB數(shù)據(jù)結構數(shù)據(jù)結構二叉樹及存儲結構二叉樹及存儲結構二叉樹的基本形態(tài)二叉樹的基本形態(tài)空二叉樹空二叉樹只有一個根結點只有一個根結點左子樹左子樹右子樹右子樹根結點同時有左右子樹根結點同時有左右子樹左子樹左子樹根結點只有左子樹根結點只有左子樹右子樹右子樹根結點只有右子樹根結點只有右子樹數(shù)據(jù)結構數(shù)據(jù)結構二叉樹及存儲結構二叉樹及存儲結構具有具有3 3個結點的個結點的樹樹和具有和具有3 3個結點的個結點的二叉樹二叉樹的形態(tài)的形態(tài)v二叉樹和樹是兩種樹結構。二叉樹和樹是兩種樹結構。數(shù)據(jù)結構數(shù)據(jù)結構二叉樹及存儲結構二叉樹及存儲結構斜樹斜樹1 . .所所有結點都只有左子有結點都只有左子

40、樹的二叉樹稱為樹的二叉樹稱為左斜樹左斜樹；2 . .所有結點都只所有結點都只有右子有右子樹的二叉樹稱為樹的二叉樹稱為右斜樹右斜樹；3.3.左斜樹和右斜樹統(tǒng)稱為左斜樹和右斜樹統(tǒng)稱為斜樹斜樹。1. 在斜樹中，每一層只有一個結點；在斜樹中，每一層只有一個結點；2. .斜樹的結點個數(shù)與其深度相同。斜樹的結點個數(shù)與其深度相同。 斜樹的特點：斜樹的特點：ABCABC數(shù)據(jù)結構數(shù)據(jù)結構二叉樹及存儲結構二叉樹及存儲結構滿二叉樹滿二叉樹在一棵二叉樹中，如果所在一棵二叉樹中，如果所有分支結點都存在左子樹有分支結點都存在左子樹和右子樹，并且所有葉子和右子樹，并且所有葉子都在都在同一層上。同一層上。滿二叉樹的特點滿二叉

41、樹的特點： 1. 葉子只能出現(xiàn)在最下一層；葉子只能出現(xiàn)在最下一層； 2. 只有度為只有度為0和度為和度為2的結點。的結點。特殊的二叉樹特殊的二叉樹CDEFGHIJKLM NO1112 13 14 15數(shù)據(jù)結構數(shù)據(jù)結構二叉樹及存儲結構二叉樹及存儲結構滿二叉樹滿二叉樹不是滿二叉樹，雖然不是滿二叉樹，雖然所有分支結點都有左所有分支結點都有左右子樹，但葉子不在右子樹，但葉子不在同一層上。同一層上。滿二叉樹在同樣深度的二叉樹中滿二叉樹在同樣深度的二叉樹中結點結點個數(shù)最多個數(shù)最多滿二叉樹在同樣深度的二叉樹中滿二叉樹在同樣深度的二叉樹中葉子結點葉子結點個數(shù)最多個數(shù)最多A152346

42、7BCDEFGLM89數(shù)據(jù)結構數(shù)據(jù)結構二叉樹及存儲結構二叉樹及存儲結構完全二叉樹完全二叉樹 對一棵具有對一棵具有n個結點的個結點的二叉樹按層序編號，如果二叉樹按層序編號，如果編號為編號為i（1in）的結點的結點與同樣深度的滿二叉樹中與同樣深度的滿二叉樹中編號為編號為i的結點在二叉樹的結點在二叉樹中的位置完全相同。中的位置完全相同。特殊的二叉樹特殊的二叉樹CDEFGHIJKLM NO1112 13 14 15CDEFGHIJ數(shù)據(jù)結構數(shù)據(jù)結構二叉樹及存儲結構二叉樹及存儲結構在滿二叉樹中，從最后在滿二叉樹中，從最后一個結點開始，一個結點開始，連續(xù)連

43、續(xù)去去掉掉任意任意個結點，即是一個結點，即是一棵完全二叉樹。棵完全二叉樹。A1523467910BCDEFGHIJK11L12M13N14O158CDEFGHIJ不是完全二叉樹，結點不是完全二叉樹，結點10與滿二叉樹中的結點與滿二叉樹中的結點10不是同一個結點不是同一個結點數(shù)據(jù)結構數(shù)據(jù)結構二叉樹及存儲結構二叉樹及存儲結構1. 葉子結點只能出現(xiàn)在葉子結點只能出現(xiàn)在最下兩最下兩層層，且最下層的葉子結點都集，且最下層的葉子結點都集中在二叉樹的中在二叉樹的左部左部；2. 完全二叉樹中如果有度為完全二叉樹中如果有度為1的結點的結點，只可能有，只可能有一個一個，且該，且該結結點只

44、有點只有左孩子左孩子。 3. 深度為深度為k的完全二叉樹在的完全二叉樹在k-1層上一定是層上一定是滿滿二叉樹。二叉樹。完全二叉樹的特點完全二叉樹的特點CDEFGHIJ數(shù)據(jù)結構數(shù)據(jù)結構二叉樹及存儲結構二叉樹及存儲結構二叉樹的基本性質二叉樹的基本性質 性質性質5-1 二叉樹的第二叉樹的第i層上層上最多最多有有2i- -1個結點（個結點（i1）。）。 證明：證明：當當i=1時時，第，第1層只有一個根結點，而層只有一個根結點，而 2i-1=20 =1，結論顯然成立。結論顯然成立。假定假定i=k（1ki）時結論成立，即第）時結論成立，即第k層上至多有層上至多有2k-1個結點個結

45、點。 i=k+1時時，因為第，因為第k+1層上的結點是第層上的結點是第k層上結點的孩子，而層上結點的孩子，而二叉樹中每個結點最多有二叉樹中每個結點最多有2個孩子，故在第個孩子，故在第k+1層上最大結點層上最大結點個數(shù)為第個數(shù)為第k層上的最大結點個數(shù)的二倍，即層上的最大結點個數(shù)的二倍，即22k-12k。結論結論成立。成立。CDEFGHIJKLM NO1112 13 14 15數(shù)據(jù)結構數(shù)據(jù)結構性質性質5-2 一棵深度為一棵深度為k的二叉樹中，最多有的二叉樹中，最多有2k- -1個結點，最個結點，最少有少有k個結點。個結點。 證明：由性質證明：由性質1可知，深度為可知，深度

46、為k的二叉樹中結點個數(shù)最多的二叉樹中結點個數(shù)最多= =2k-1；每一層至少要有一個結點，因此深度為每一層至少要有一個結點，因此深度為k的二叉樹，至少有的二叉樹，至少有k個結點。個結點。kii1)(層上結點的最大個數(shù)第深度為深度為k且具有且具有2k-1個結點的二叉樹個結點的二叉樹一定是一定是滿二叉樹，滿二叉樹，深度為深度為k且具有且具有k個結點的二叉樹個結點的二叉樹不一定不一定是斜樹。是斜樹。二叉樹的基本性質二叉樹的基本性質 二叉樹及存儲結構二叉樹及存儲結構CDEFGHIJKLM NO1112 13 14 15數(shù)據(jù)結構數(shù)據(jù)結構性質性質5-3 在一棵二叉樹中，如果葉子結點

47、數(shù)為在一棵二叉樹中，如果葉子結點數(shù)為n0，度為度為2的的結點數(shù)為結點數(shù)為n2，則有則有: n0n21。 證明證明: 設設n為二叉樹的結點總數(shù)，為二叉樹的結點總數(shù)，n1為二叉樹中度為為二叉樹中度為1的結點的結點數(shù)，則有：數(shù)，則有： nn0n1n2 在二叉樹中，除了根結點外，其余結點都有唯一的一個分在二叉樹中，除了根結點外，其余結點都有唯一的一個分枝進入，由于這些分枝是由度為枝進入，由于這些分枝是由度為1和度為和度為2的結點射出的，的結點射出的，一個度為一個度為1的結點射出一個分枝，一個度為的結點射出一個分枝，一個度為2的結點射出兩的結點射出兩個分枝，所以有：個分枝，所以有： nn12n21因此可

48、以得到：因此可以得到：n0n21 。二叉樹的基本性質二叉樹的基本性質 二叉樹及存儲結構二叉樹及存儲結構數(shù)據(jù)結構數(shù)據(jù)結構在有在有n個結點的滿二叉樹中，有多少個葉子結點？個結點的滿二叉樹中，有多少個葉子結點？因為在滿二叉樹中沒有度為因為在滿二叉樹中沒有度為1的結點，只有度為的結點，只有度為0的葉子結點的葉子結點和度為和度為2的分支結點，所以，的分支結點，所以，n n0 + n2n0n2 + 1 即葉子結點即葉子結點n0（n + 1）/2 二叉樹的基本性質二叉樹的基本性質 性質性質5-3 在一棵二叉樹中，如果葉子結點數(shù)為在一棵二叉樹中，如果葉子結點數(shù)為n0，度為度為2的的結點數(shù)為結點數(shù)為n2，則有則

49、有: n0n21。 二叉樹及存儲結構二叉樹及存儲結構數(shù)據(jù)結構數(shù)據(jù)結構性質性質5-4 具有具有n個結點的完全二叉樹的深度為個結點的完全二叉樹的深度為 log2n +1。 證明：假設具有證明：假設具有n個結點的完全二叉樹的深度為個結點的完全二叉樹的深度為k，根據(jù)完全，根據(jù)完全二叉樹的定義和性質二叉樹的定義和性質2，有下式成立，有下式成立 2k-1 n 2k 2k-1-12k-12k-1第第k-1層層第第k層層最少結點數(shù)最少結點數(shù)最多結點數(shù)最多結點數(shù)完全二叉樹的基本性質完全二叉樹的基本性質 二叉樹及存儲結構二叉樹及存儲結構數(shù)據(jù)結構數(shù)據(jù)結構 log2n + 1log2nlog2nlog2n+1k所在區(qū)

50、間所在區(qū)間證明：假設具有證明：假設具有n個結點的完全二叉樹的深度為個結點的完全二叉樹的深度為k，根據(jù)完全，根據(jù)完全二叉樹的定義和性質二叉樹的定義和性質2，有下式成立，有下式成立 2k-1 n 2k完全二叉樹的基本性質完全二叉樹的基本性質 性質性質5-4 具有具有n個結點的完全二叉樹的深度為個結點的完全二叉樹的深度為 log2n +1。 對不等式取對數(shù)，有：對不等式取對數(shù)，有： k-1log2nk即：即： log2nklog2n+1由于由于k是整數(shù)，故必有是整數(shù)，故必有k log2n +1。 二叉樹及存儲結構二叉樹及存儲結構數(shù)據(jù)結構數(shù)據(jù)結構性質性質5-5 對一棵具有對一棵具有n個結點的完全二叉樹

51、中從個結點的完全二叉樹中從1開始按層開始按層序編號，則對于任意的序號為序編號，則對于任意的序號為i（1in）的結點（簡稱為結的結點（簡稱為結點點i），），有：有： (1) 如果如果i1，則結點則結點i的雙親結點的序號為的雙親結點的序號為 i/2； 如果如果i1，則結點則結點i是根結點，無雙親結點。是根結點，無雙親結點。 (2) 如果如果2in，則結點則結點i的左孩子的序號為的左孩子的序號為2i； 如果如果2in，則結點則結點i無左孩子。無左孩子。 (3) 如果如果2i1n，則結點則結點i的右孩子的序號為的右孩子的序號為2i1； 如果如果2i1n，則結點則結點 i無右孩子。無右孩子。 完全二叉樹的基本性質完全二叉樹的基本性質 二叉樹及存儲結構二叉樹及存儲結據(jù)結構數(shù)據(jù)結一棵具有對一棵具有n個結點的完全二叉?zhèn)€結點的完全二叉樹中從樹中從1開始按層序編號，則開始按層序編號，則l 結點結點i的雙親結點為的雙親結點為 i/2；l 結點結點i的左孩子為的左孩子為2i；l 結點結點i的右孩子為的右孩子為2i1。 性質性質5表明，在完全二叉樹中，結點的層序編號反映表明，在完全二叉樹中，結點的層序編號反映了結點之間的邏輯關系。了結點之間的邏