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

第4章數(shù)據(jù)結(jié)構(gòu)主要內(nèi)容數(shù)據(jù)結(jié)構(gòu)概述線性表及其操作樹與二叉樹數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)概述080611 班號82519610計算機學院辦公室電話號碼10001哈工程大學郵編230102780618748身份證號碼例1：0806118251961010004230102780618748結(jié)論1.

雜亂的數(shù)據(jù)不能表達和交流信息數(shù)據(jù)結(jié)構(gòu)<數(shù)據(jù)結(jié)構(gòu)>的主要內(nèi)容例2

電話號碼查詢系統(tǒng)設(shè)有一個電話號碼薄，它記錄了n個人的名字和其相應(yīng)的電話號碼，假定按如下形式安排：

(a1，b1)(a2，b2)…(an，bn)其中ai，bi(i=1，2…n)分別表示某人的名字和對應(yīng)電話號碼問題：設(shè)計一個算法，當給定任何一個人的名字時，該算法能夠打印出此人的電話號碼，如果該電話簿中根本就沒有這個人，則該算法也能夠報告沒有這個人的標志。要做的事情：設(shè)計恰當?shù)臄?shù)學模型表示電話號碼簿的所有信息采用相應(yīng)查找算法,實現(xiàn)快速查詢與打印.結(jié)論2. 數(shù)據(jù)之間是有聯(lián)系的這些聯(lián)系常常影響算法的選擇和效率?！禗S》就是要研究數(shù)據(jù)之間的聯(lián)系。數(shù)據(jù)結(jié)構(gòu)<數(shù)據(jù)結(jié)構(gòu)>的主要內(nèi)容例3酒店管理系統(tǒng)中的客房分配問題.

要求:

出借率機會均等，保持一個平均的磨損率．

房間分配方法采用“先退的房間先被起用”的算法．

房間信息組織方法:所有“空”的同類房間的數(shù)據(jù)模型應(yīng)該是一個“隊列”從“隊頭”分配客房；退掉的空客房排在“隊尾”。數(shù)據(jù)結(jié)構(gòu)<數(shù)據(jù)結(jié)構(gòu)>的主要內(nèi)容例4:鋪設(shè)煤氣管道問題n個居民區(qū)之間鋪設(shè)煤氣管道，只要鋪設(shè)n-1條管道即可。假設(shè):任意兩個居民區(qū)之間都可以架設(shè)管道，每條管道的費用成本不同，要解決的問題:用一定的數(shù)據(jù)模型表示該問題，在此基礎(chǔ)上計算投資最少（或盡可能少的）的管道鋪設(shè)方案。CBAED325416216945364740CBAED32162136數(shù)據(jù)結(jié)構(gòu)職工號姓名性別出生年月職務(wù)單位01郭建成男1952年8月處長

02肖明男1958年6月科長教材科03晨曦女1954年12月科長考務(wù)科04趙麗霞女1962年8月主任辦公室05崔小龍男1949年8月科員教材科06袁莉女1965年4月科員教材科07王芳女1962年6月科員考務(wù)科08張宏愿男1957年3月科員考務(wù)科09馬明華男1965年10月科員考務(wù)科10李冰男1966年7月科員辦公室例5

表1-1教務(wù)處人事簡表

10條記錄，每條記錄有6個數(shù)據(jù)項，每條記錄的職工號不同，用職工號來代表整個職工記錄。

03080207040609100501按職工年齡從大到小排列03080207040609100501領(lǐng)導(dǎo)和被領(lǐng)導(dǎo)的關(guān)系07040810090205060301朋友關(guān)系線性結(jié)構(gòu)樹型結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)結(jié)論３． 數(shù)據(jù)之間是有結(jié)構(gòu)的例5中數(shù)據(jù)之間呈線性結(jié)構(gòu)、分層結(jié)構(gòu)（樹狀結(jié)構(gòu)）、圖形結(jié)構(gòu)《DS》就是要研究數(shù)據(jù)之間的各類結(jié)構(gòu)<數(shù)據(jù)結(jié)構(gòu)>的主要內(nèi)容數(shù)據(jù)結(jié)構(gòu)<數(shù)據(jù)結(jié)構(gòu)>的主要內(nèi)容例6：圖書目錄管理書目信息：書名，作者，登錄號，分類，出版年月對圖書目錄操作：查找：某書在書庫中是否存在？插入：購進新書時的登錄；刪除：報廢或丟失的書，需從目錄中去掉；結(jié)論４． 在某種數(shù)據(jù)結(jié)構(gòu)上可定義一組運算《DS》就是要研究各類數(shù)據(jù)結(jié)構(gòu)上的各種運算數(shù)據(jù)結(jié)構(gòu)

《DS》主要研究內(nèi)容：

數(shù)據(jù)的各種邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，以及它們之間的相應(yīng)關(guān)系

并對每種結(jié)構(gòu)定義相適應(yīng)的各種運算

設(shè)計出相應(yīng)的算法

分析算法的效率<數(shù)據(jù)結(jié)構(gòu)>的主要內(nèi)容數(shù)據(jù)結(jié)構(gòu)基本術(shù)語數(shù)據(jù)描述客觀事物的數(shù)字、字符以及一切能夠輸入到計算機中，并且能夠被計算機程序處理的符號的集合結(jié)構(gòu)數(shù)據(jù)元素之間具有的關(guān)系。數(shù)據(jù)結(jié)構(gòu)具有結(jié)構(gòu)的數(shù)據(jù)元素的集合。DS=(D,R)數(shù)據(jù)元素數(shù)據(jù)整體中相對獨立的基本單位,數(shù)據(jù)這個集合中的一個一個的個體數(shù)據(jù)元素也稱為數(shù)據(jù)結(jié)點。數(shù)據(jù)對象具有相同特性的數(shù)據(jù)元素的集合。是數(shù)據(jù)集合的子集。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)具有某種邏輯結(jié)構(gòu)的數(shù)據(jù)在計算機存儲器中的存儲方式(存儲映象)。數(shù)據(jù)元素之間具有的邏輯關(guān)系(結(jié)構(gòu))邏輯結(jié)構(gòu)物理結(jié)構(gòu)數(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)數(shù)據(jù)結(jié)構(gòu)職工號姓名性別出生年月職務(wù)單位01郭建成男1952年8月處長

02肖明男1958年6月科長教材科03晨曦女1954年12月科長考務(wù)科04趙麗霞女1962年8月主任辦公室05崔小龍男1949年8月科員教材科06袁莉女1965年4月科員教材科07王芳女1962年6月科員考務(wù)科08張宏愿男1957年3月科員考務(wù)科09馬明華男1965年10月科員考務(wù)科10李冰男1966年7月科員辦公室例

教務(wù)處人事簡表

10條記錄，每條記錄有6個數(shù)據(jù)項，每條記錄的職工號不同，用職工號來代表整個職工記錄。

03080207040609100501按職工年齡從大到小排列03080207040609100501領(lǐng)導(dǎo)和被領(lǐng)導(dǎo)的關(guān)系07040810090205060301朋友關(guān)系線性結(jié)構(gòu)樹型結(jié)構(gòu)圖形結(jié)構(gòu)數(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)數(shù)據(jù)結(jié)構(gòu)線性表及其基本操作學生成績登記表姓名英語數(shù)據(jù)結(jié)構(gòu)高數(shù)學號丁一9678870101李二8790780102張三6786860103孫紅6981960104王冬8774660105數(shù)據(jù)結(jié)構(gòu)線性表及其基本操作職工工資登記表姓名崗位津貼基本工資獎金職工號丁一6002782000101李二3001901000102張三3001861000103孫紅5002182000104王冬3001901000105數(shù)據(jù)元素之間的關(guān)系是什么？數(shù)據(jù)結(jié)構(gòu)線性表及其基本操作線性表：簡稱表，是n（n≥0）個具有相同類型的數(shù)據(jù)元素的有限序列。線性表的長度：線性表中數(shù)據(jù)元素的個數(shù)?？毡恚洪L度等于零的線性表，記為：L=()。非空表記為：L＝（a1,a2,…,ai-1,ai

,…,an)線性表的定義其中，ai（1≤i≤n）稱為數(shù)據(jù)元素；下角標i表示該元素在線性表中的位置或序號。數(shù)據(jù)結(jié)構(gòu)線性表及其基本操作a1a3a4ana2線性表的圖形表示線性表（a1,a2,…,ai-1,ai

,…,an)的圖形表示如下：幾個線性表的例子

數(shù)列：(25，12，78，34，100，88)1a1a2a3a4a5a6一個數(shù)據(jù)元素為一個整數(shù)2字母表：(‘A’，‘B’，‘C’，……,‘Z’)a1a2a3

……a26一個數(shù)據(jù)元素為一個字母數(shù)據(jù)結(jié)構(gòu)線性表及其基本操作a1a3a4ana2線性表的特性1.有限性：線性表中數(shù)據(jù)元素的個數(shù)是有窮的。2.相同性：線性表中數(shù)據(jù)元素的類型是同一的。3.順序性：線性表中相鄰的數(shù)據(jù)元素ai-1和ai之間存在序偶關(guān)系(ai-1,ai)，即ai-1是ai的前驅(qū)，ai是ai-1的后繼；a1

無前驅(qū)，an無后繼，其它每個元素有且僅有一個前驅(qū)和一個后繼。

數(shù)據(jù)結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)順序表——線性表的順序存儲結(jié)構(gòu)例：（34,23,67,43）342367434存儲要點用一段地址連續(xù)的存儲單元依次存儲線性表中的數(shù)據(jù)元素數(shù)據(jù)結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)如何求得任意元素的存儲地址？0…i-2i-1…n-1Max-1a1…ai-1ai…an空閑長度順序表一般情況下，(a1，a2，…,ai-1，ai,…,an)的順序存儲：cLoc(ai)Loc(a1)數(shù)據(jù)結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)0…i-2i-1…n-1Max-1a1…ai-1ai…an空閑長度Loc(ai)=Loc(a1)+(i-1)×c隨機存取：在O(1)時間內(nèi)存取數(shù)據(jù)元素順序表cLoc(ai)Loc(a1)一般情況下，(a1，a2，…,ai-1，ai,…,an)的順序存儲：數(shù)據(jù)結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)33例：（35，12，24，42），在i=2的位置上插入33。順序表的插入

435122442a1a2a3a401234422412335什么時候不能插入？注意邊界條件表滿：length>=MaxSize合理的插入位置：1≤i≤length+1（i指的是元素的序號）數(shù)據(jù)結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)例：（35,33,12,24,42），刪除i=2的數(shù)據(jù)元素。順序表的刪除535a1a2a3a401234422412334a5122442刪除后順序表的內(nèi)容需要考慮的異常情況：(1).是否表空？(2).刪除位置是否合適？(正常位置：1≤i≤n)數(shù)據(jù)結(jié)構(gòu)線性表的鏈式存儲結(jié)構(gòu)存儲思想：用一組任意的存儲單元存放線性表的元素。連續(xù)不連續(xù)零散分布單鏈表：線性表的鏈接存儲結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)線性表的鏈式存儲結(jié)構(gòu)0200020803000325…………存儲特點：邏輯次序和物理次序不一定相同。

2.元素之間的邏輯關(guān)系用指針表示。例：(a1,a2

,a3,a4)的存儲示意圖單鏈表a10200a20325a30300a4∧數(shù)據(jù)結(jié)構(gòu)線性表的鏈式存儲結(jié)構(gòu)單鏈表結(jié)點數(shù)據(jù)域指針域單鏈表是由若干結(jié)點構(gòu)成的；單鏈表的結(jié)點只有一個指針域。data：存儲數(shù)據(jù)元素next：存儲指向后繼結(jié)點的地址datanext單鏈表的結(jié)點結(jié)構(gòu)：數(shù)據(jù)域指針域0200020803000325…………a10200a20325a30300a4∧數(shù)據(jù)結(jié)構(gòu)帶頭結(jié)點的單鏈表lista1a2an∧lista1a2an∧非空表list=NULL空表單鏈表的表示頭指針：指向第一個結(jié)點的地址。尾標志：終端結(jié)點的指針域為空。空表list∧數(shù)據(jù)結(jié)構(gòu)線性表的鏈式存儲結(jié)構(gòu)單鏈表的插入：在第i個結(jié)點后插入一個新結(jié)點思想：

1)從第1個結(jié)點出發(fā)，找到第i個結(jié)點；

2)將新結(jié)點插入其后

3)返回操作結(jié)果信息(成功與否)plista2a1aian∧ai+1ppxq∧

數(shù)據(jù)結(jié)構(gòu)線性表的鏈式存儲結(jié)構(gòu)單鏈表的插入：刪除第i個結(jié)點思想：

1)從第1個結(jié)點出發(fā)，找到第i-1個結(jié)點；

2)刪除第i個結(jié)點

3)返回操作結(jié)果信息(成功與否)plista2a1ai-1ai+1aippq∧數(shù)據(jù)結(jié)構(gòu)棧的概念及實現(xiàn)棧：限定僅在表尾進行插入和刪除操作的線性表。空棧：不含任何數(shù)據(jù)元素的棧。

（a1,a2,……,an）棧頂棧底允許插入和刪除的一端稱為棧頂，另一端稱為棧底。數(shù)據(jù)結(jié)構(gòu)棧的概念及實現(xiàn)a1a2a3入棧出棧棧底棧頂插入：入棧、進棧、壓棧刪除：出棧、彈棧棧頂棧頂棧的示意圖數(shù)據(jù)結(jié)構(gòu)棧的概念及實現(xiàn)棧的操作特性：后進先出a1a2a3入棧出棧棧底棧頂插入：入棧、進棧、壓棧刪除：出棧、彈棧棧頂棧的示意圖數(shù)據(jù)結(jié)構(gòu)棧的概念及實現(xiàn)例：有三個元素按a、b、c的次序依次進棧，且每個元素只允許進一次棧，則可能的出棧序列有多少種？棧底棧頂ab棧頂c棧頂情況1：出棧序列：cba數(shù)據(jù)結(jié)構(gòu)棧的概念及實現(xiàn)例：有三個元素按a、b、c的次序依次進棧，且每個元素只允許進一次棧，則可能的出棧序列有多少種？情況2：棧底棧頂ab棧頂c出棧序列：bca注意：棧只是對表插入和刪除操作的位置進行了限制，并沒有限定插入和刪除操作進行的時間。數(shù)據(jù)結(jié)構(gòu)棧的概念及實現(xiàn)棧的順序存儲結(jié)構(gòu)及實現(xiàn)順序棧——棧的順序存儲結(jié)構(gòu)如何改造數(shù)組實現(xiàn)棧的順序存儲？

123456789a1確定用數(shù)組的哪一端表示棧底。附設(shè)指針top指示棧頂元素在數(shù)組中的位置。

top數(shù)據(jù)結(jié)構(gòu)棧的概念及實現(xiàn)出棧：top減1進棧：top加1?？眨簍op=0

123456789a1topa2topa3top棧滿：top=MAXSIZE-1棧的順序存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)隊列隊列的邏輯結(jié)構(gòu)空隊列：不含任何數(shù)據(jù)元素的隊列。

隊列：只允許在一端進行插入操作，而另一端進行刪除操作的線性表。允許插入（也稱入隊、進隊）的一端稱為隊尾，允許刪除（也稱出隊）的一端稱為隊頭。（a1,a2,……,an）隊尾隊頭數(shù)據(jù)結(jié)構(gòu)隊列的操作特性：先進先出a1a2a3入隊隊尾隊頭出隊隊頭隊列的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)01234入隊出隊例：a1a2a3a4依次入隊a1a2a3a4rearrearrearrear入隊操作時間性能仍為O(1)frontrear隊列的順序存儲結(jié)構(gòu)及實現(xiàn)設(shè)置隊頭、隊尾兩個指針

數(shù)據(jù)結(jié)構(gòu)例：a1a2依次出隊01234入隊出隊a1a2a3a4rearfrontfrontfront出隊操作時間性能提高為O(1)隊列的順序存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)例：a1a2依次出隊特殊線性表——隊列01234入隊出隊a3a4rearfront隊列的移動有什么特點？隊列的順序存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)例：a1a2依次出隊特殊線性表——隊列01234入隊出隊a3a4rearfront整個隊列向數(shù)組下標較大方向移動單向移動性隊列的順序存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)假溢出：當元素被插入到數(shù)組中下標最大的位置上之后，隊列的空間就用盡了，盡管此時數(shù)組的低端還有空閑空間，這種現(xiàn)象叫做假溢出。特殊線性表——隊列繼續(xù)入隊會出現(xiàn)什么情況？01234入隊出隊a3a4rearfronta5rear隊列的順序存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)循環(huán)隊列：將存儲隊列的數(shù)組頭尾相接。特殊線性表——隊列如何解決假溢出？01234入隊出隊a3a4fronta5rearreara6隊列的順序存儲結(jié)構(gòu)及實現(xiàn)數(shù)據(jù)結(jié)構(gòu)樹的基本概念及存儲結(jié)構(gòu)樹的定義樹：n（n≥0）個結(jié)點的有限集合。當n＝0時，稱為空樹；任意一棵非空樹滿足以下條件：⑴

有且僅有一個特定的稱為根的結(jié)點；⑵

當n＞1時，除根結(jié)點之外的其余結(jié)點被分成m（m>0）個互不相交的有限集合T1,T2,…,Tm，其中每個集合又是一棵樹，并稱為這個根結(jié)點的子樹。樹的定義是采用遞歸方法數(shù)據(jù)結(jié)構(gòu)樹的基本概念及存儲結(jié)構(gòu)A只有根結(jié)點的樹ABCDEFGHIJKLM有子樹的樹根子樹數(shù)據(jù)結(jié)構(gòu)樹的基本概念及存儲結(jié)構(gòu)(a)一棵樹結(jié)構(gòu)(b)一個非樹結(jié)構(gòu)(c)一個非樹結(jié)構(gòu)樹的定義ACBGFEDHIACBGFDACBGFDE數(shù)據(jù)結(jié)構(gòu)樹的基本概念及存儲結(jié)構(gòu)樹的應(yīng)用舉例——文件結(jié)構(gòu)MyComputerC:D:E:etcWINDOWSProgramFilesPictureMusic…………………………………………數(shù)據(jù)結(jié)構(gòu)樹的基本概念及存儲結(jié)構(gòu)樹的基本術(shù)語結(jié)點的度：結(jié)點所擁有的子樹的個數(shù)。樹的度：樹中各結(jié)點度的最大值。CGBDEFKLHMIJA數(shù)據(jù)結(jié)構(gòu)葉子結(jié)點：度為0的結(jié)點，也稱為終端結(jié)點。分支結(jié)點：度不為0的結(jié)點，也稱為非終端結(jié)點。CGBDEFKLHMIJA樹的基本術(shù)語樹的基本概念及存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)孩子、雙親：樹中某結(jié)點子樹的根結(jié)點稱為這個結(jié)點的孩子結(jié)點，這個結(jié)點稱為它孩子結(jié)點的雙親結(jié)點；兄弟：具有同一個雙親的孩子結(jié)點互稱為兄弟。

CGBDEFKLHMIJA樹的基本術(shù)語樹的基本概念及存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)路徑：如果樹的結(jié)點序列n1,n2,…,nk有如下關(guān)系：結(jié)點ni是ni+1的雙親（1<=i<k），則把n1,n2,…,nk稱為一條由n1至nk的路徑；路徑上經(jīng)過的邊的個數(shù)稱為路徑長度。CGBDEFKLHMIJA樹的基本術(shù)語樹的基本概念及存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)祖先、子孫：在樹中，如果有一條路徑從結(jié)點x到結(jié)點y，那么x就稱為y的祖先，而y稱為x的子孫。CGBDEFKLHMIJA樹的基本術(shù)語樹的基本概念及存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)結(jié)點所在層數(shù)：根結(jié)點的層數(shù)為1；對其余任何結(jié)點，若某結(jié)點在第k層，則其孩子結(jié)點在第k+1層。樹的深度：樹中所有結(jié)點的最大層數(shù)，也稱高度。1層2層4層3層高度＝4CGBDEFKLHMIJC樹的基本術(shù)語樹的基本概念及存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)CBDEFKLHJA71234568910層序編號：將樹中結(jié)點按照從上層到下層、同層從左到右的次序依次給他們編以從1開始的連續(xù)自然數(shù)。樹的基本術(shù)語樹的基本概念及存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)二叉樹及存儲結(jié)構(gòu)二叉樹的定義

二叉樹是n（n≥0）個結(jié)點的有限集合，該集合或者為空集（稱為空二叉樹），或者由一個根結(jié)點和兩棵互不相交的、分別