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

第6章數(shù)據(jù)結(jié)構(gòu)第6章數(shù)據(jù)結(jié)構(gòu)6.1概念和術(shù)語（掌握)6.2線性結(jié)構(gòu)（掌握）6.3樹形結(jié)構(gòu)（了解）6.4圖狀結(jié)構(gòu)（了解）6.5文件（了解）第6章數(shù)據(jù)結(jié)構(gòu)重點：基本概念和術(shù)語線性結(jié)構(gòu)難點：數(shù)據(jù)存儲結(jié)構(gòu)6.1概念和術(shù)語數(shù)據(jù)處理：數(shù)據(jù)：數(shù)值數(shù)據(jù)和非數(shù)值數(shù)據(jù)（字符串、圖像、音頻、視頻等）；處理：既可以是算術(shù)運算，也可以是插入、刪除、查找和排序

等操作。數(shù)據(jù)結(jié)構(gòu)要解決的問題：編寫程序時：面對的是邏輯結(jié)構(gòu)（數(shù)據(jù)的一種抽象表示，更符合人們習(xí)慣）；程序執(zhí)行時：由支持相應(yīng)結(jié)構(gòu)的編譯程序自動把邏輯結(jié)構(gòu)映射成物理結(jié)構(gòu)，從而簡化程序的編寫，減輕編程人員的工作量。數(shù)據(jù)結(jié)構(gòu)討論描述現(xiàn)實世界實體的數(shù)學(xué)模型及其上的操作在計算機中的表示和實現(xiàn)。56.1概念和術(shù)語數(shù)據(jù)信息的載體，所有能被輸入到計算機中且被計算機處理的符號的集合?？梢允菙?shù)值數(shù)據(jù)，也可以是非數(shù)值數(shù)據(jù)。例如：圖像、聲音、文本等。數(shù)據(jù)元素數(shù)據(jù)的基本單位，具有完整、確定的實際意義，在計算機中通常作為一個整體考慮。一般由若干數(shù)據(jù)項組成。例如：張三的基本情況——學(xué)號、姓名、性別、年齡等。數(shù)據(jù)項數(shù)據(jù)不可分割的最小單位。分為數(shù)據(jù)項名和數(shù)據(jù)項值。例如：年齡（數(shù)據(jù)項名）——19、20（數(shù)據(jù)項值）66.1概念和術(shù)語數(shù)據(jù)對象（數(shù)據(jù)元素類）性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。在某個具體問題中，數(shù)據(jù)元素都具有相同的性質(zhì)，屬于同一數(shù)據(jù)對象，數(shù)據(jù)元素是數(shù)據(jù)元素類的一個實例。例如：學(xué)生管理系統(tǒng)——某大學(xué)學(xué)生的基本情況（數(shù)據(jù)）

——本科生的基本情況（數(shù)據(jù)對象）

——某本科生張三的基本情況（數(shù)據(jù)元素）又比如：字符集{‘A’,’B’,’C’……}數(shù)據(jù)結(jié)構(gòu)互相之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。

在任何問題中，數(shù)據(jù)元素不是孤立的，它們之間存在著這樣和那樣的關(guān)系，這種數(shù)據(jù)之間的關(guān)系稱為結(jié)構(gòu)。76.1概念和術(shù)語數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的物理結(jié)構(gòu)。1、數(shù)據(jù)的邏輯結(jié)構(gòu)從具體問題抽象出來的數(shù)學(xué)模型，描述的是數(shù)據(jù)元素之間的邏輯關(guān)系。即數(shù)據(jù)的組織形式。不涉及數(shù)據(jù)元素在計算機中具體的存儲方式。2、數(shù)據(jù)的物理結(jié)構(gòu)（存儲結(jié)構(gòu)）數(shù)據(jù)在計算機中的表示，研究數(shù)據(jù)結(jié)構(gòu)在計算機中的實現(xiàn)方法，包括數(shù)據(jù)結(jié)構(gòu)中元素的表示及數(shù)據(jù)元素間關(guān)系的表示。86.1概念和術(shù)語1、數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)元素間的邏輯結(jié)構(gòu)有四種基本類型：1）集合：數(shù)據(jù)元素除了“同屬于一個集合”外，沒有其他關(guān)系。2）線性結(jié)構(gòu)數(shù)據(jù)元素之間存在著一對一的關(guān)系，例如線性表、棧、隊列等。例如：按學(xué)號排列的學(xué)生數(shù)據(jù)。6.1概念和術(shù)語3）樹形結(jié)構(gòu)數(shù)據(jù)元素之間存在著一對多的關(guān)系，例如樹、二叉樹和森林等。例如：一個單位的工作人員之間的關(guān)系。6.1概念和術(shù)語4）圖狀結(jié)構(gòu)數(shù)據(jù)元素之間存在著多對多的關(guān)系，也稱網(wǎng)狀結(jié)構(gòu)，如無向圖和有向圖等。例如：高速公路交通圖。116.1概念和術(shù)語2、數(shù)據(jù)的物理結(jié)構(gòu)(存儲結(jié)構(gòu))數(shù)據(jù)的物理結(jié)構(gòu)可以采用順序存儲或者鏈?zhǔn)酱鎯Α?）順序存儲邏輯上相鄰的元素存儲在物理位置也相鄰的存儲單元中。

常借助于程序設(shè)計語言中的數(shù)組來實現(xiàn)。2）鏈?zhǔn)酱鎯壿嬌舷噜彽脑夭灰笃湮锢砦恢孟噜?，元素間的邏輯關(guān)系通過附設(shè)的指針字段來表示。常借助于程序設(shè)計語言中的指針來實現(xiàn)。6.1概念和術(shù)語順序存儲：數(shù)據(jù)元素的存儲地址是連續(xù)的鏈?zhǔn)酱鎯?數(shù)據(jù)元素的存儲地址不要求是連續(xù)的。有相鄰的數(shù)據(jù)元素a和b，分別采用順序和鏈?zhǔn)酱鎯θ缦聢D所示：abba&b順序存儲鏈?zhǔn)酱鎯?36.2線性結(jié)構(gòu)線性結(jié)構(gòu)的特點：在非空有限集上只有一個首結(jié)點和一個尾結(jié)點。每個元素有且只有一個直接前驅(qū)（第一個元素除外）。每個元素有且只有一個直接后繼（最后一個元素除外）。數(shù)據(jù)元素之間存在著一對一的關(guān)系。常見線性結(jié)構(gòu)：線性表棧隊列6.2.1線性表1、線性表(LinearList)：是由n(n≥0)個數(shù)據(jù)元素(結(jié)點)a1，a2，…an組成的有限序列。該序列中的所有結(jié)點具有相同的數(shù)據(jù)類型。其中數(shù)據(jù)元素的個數(shù)n稱為線性表的長度。當(dāng)n=0時，稱為空表。當(dāng)n>0時，將非空的線性表記作：

(a1，a2，…an)6.2.1線性表1、線性表(LinearList)：a1稱為線性表的首結(jié)點，an稱為線性表尾結(jié)點。a1，a2，…ai-1都是ai(2≦i≦n)的前驅(qū)，

其中ai-1是ai的直接前驅(qū)；ai+1，ai+2，…an都是ai(1≦i≦n-1)的后繼，

其中ai+1是ai的直接后繼。6.2.1線性表2、線性表的順序存儲線性表的順序存儲是指用一組地址連續(xù)的存儲單元依次存儲線性表中的各個元素。使得邏輯結(jié)構(gòu)上相鄰的數(shù)據(jù)元素存儲在相鄰的物理存儲單元。采用順序存儲結(jié)構(gòu)的線性表通常稱為順序表。高級語言中采用數(shù)組來表示線性表的順序存儲。6.2.1線性表2、線性表的順序存儲（1）順序表的存儲結(jié)構(gòu)假設(shè)線性表中的第一個數(shù)據(jù)元素的存儲地址為：

LOC（b1），每一個數(shù)據(jù)元素占m個字節(jié)，則線性表中第i個元素bi在計算機存儲空間中的存儲地址為：LOC(bi)=LOC(b1)+(i-1)m6.2.1線性表2、線性表的順序存儲（2）順序表的插入操作要在第i（1≤i≤n）個元素之前插入一個新元素時，首先要將第i個到第n個元素依次后移一位，然后將新元素插入到第i項。插入結(jié)束后，線性表的長度就增加了1。6.2.1線性表2、線性表的順序存儲（3）順序表的刪除操作要刪除第i（1≤i≤n）個元素時，則要從第i+1個元素開始，直到第n個元素之間共n–i個元素依次向前移動一個位置。刪除結(jié)束后，線性表的長度就減小了1。6.2.1線性表2、線性表的順序存儲順序存儲的特點：無需為表示結(jié)點間的邏輯關(guān)系而增加額外的存儲空間。順序存儲使線性表具有隨機訪問的特點。進(jìn)行插入、刪除操作時需大量移動數(shù)據(jù)元素，效率較低。6.2.1線性表3、線性表的鏈?zhǔn)酱鎯€性表的鏈表存儲可用連續(xù)或不連續(xù)的存儲單元來存儲線性表中的元素，但是元素之間的邏輯關(guān)系需要用“指針”來指示。分配給每個結(jié)點的存儲單元一般分為兩個域：一個域用來存儲數(shù)據(jù)元素的信息，稱為數(shù)據(jù)域；另一個域用來存儲直接后繼結(jié)點的地址，稱為指針域。6.2.1線性表3、線性表的鏈?zhǔn)酱鎯Γ?）在線性鏈表中查找指定的元素在非空線性鏈表中尋找包含元素值x的結(jié)點：從頭指針指向的結(jié)點開始向后沿指針進(jìn)行掃描，直到后面已經(jīng)沒有結(jié)點或下一個結(jié)點的數(shù)據(jù)域為x為止。6.2.1線性表3、線性表的鏈?zhǔn)酱鎯Γ?）線性鏈表的插入操作（3）線性鏈表的刪除操作6.2.1線性表3、線性表的鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯Φ奶攸c：由于增加了結(jié)點的指針域，空間開銷比較大。鏈表失去了數(shù)組隨機讀取的優(yōu)點。進(jìn)行插入、刪除操作時不需大量移動數(shù)據(jù)元素，效率較高。6.2.2棧（Stack）1、棧的定義棧實際上是一種特殊的線性表。在限定僅在表尾一端進(jìn)行插入或刪除操作的線性表。先進(jìn)后出（FistInLastOut，縮寫為FILO）棧頂:允許插入刪除的一端稱為棧頂。另一端稱為棧底。

順序存儲鏈?zhǔn)酱鎯1a2aian????bottomtop進(jìn)棧（push）出棧(pop)6.2.2棧（Stack）2、順序棧進(jìn)棧和出棧操作6.2.3隊列(Queue)隊列的定義隊列是另一種限定性的線性表，它只允許在表的一端插入元素，而在另一端刪除元素。隊列具有先進(jìn)先出FIFO(FistInFistOut)的特性。在隊列中，允許插入的一端叫做隊尾(rear)，允許刪除的一端則稱為隊頭(front)。a1,a2,…,an出隊入隊隊尾隊首286.3樹形結(jié)構(gòu)樹形結(jié)構(gòu)的特點數(shù)據(jù)元素之間存在著一對多的關(guān)系。非線性結(jié)構(gòu)，每個元素有一個直接前驅(qū)，但可能有多個直接后繼樹形結(jié)構(gòu)的應(yīng)用人類社會的族譜、各種社會機構(gòu)的組織形式等具有明顯層次關(guān)系的結(jié)構(gòu)。296.3.1樹的定義1、樹的定義樹是n（≥0）個結(jié)點的有限集合。當(dāng)n=0時，稱為空樹。在一棵非空樹T中：有一個特定的結(jié)點稱為樹的根結(jié)點；當(dāng)n>1時，除根結(jié)點之外的其余結(jié)點被分成m（m≥1）個互不相交的集合T1，T2，…，Tm，其中每一個集合Ti（1≤i≤m）本身又是一棵樹，并且稱為根結(jié)點的子樹。306.3.1樹的定義2、樹的基本術(shù)語結(jié)點：一個數(shù)據(jù)元素及其若干指向其子樹的分支。結(jié)點的度：結(jié)點所擁有的子樹的個數(shù)稱為結(jié)點的度。樹的度：樹中結(jié)點度的最大值。根結(jié)點：即沒有前驅(qū)的結(jié)點。葉子結(jié)點：樹中度為0的結(jié)點，又稱終端結(jié)點。度不為0的結(jié)點稱為非葉子結(jié)點316.3.1樹的定義孩子結(jié)點、雙親結(jié)點：一個結(jié)點的子樹的根稱為該結(jié)點的孩子結(jié)點或子結(jié)點；相應(yīng)地，該結(jié)點是其孩子結(jié)點的雙親結(jié)點或父結(jié)點。兄弟結(jié)點：具有同一個父結(jié)點的子結(jié)點互稱為兄弟結(jié)點。堂兄弟：即雙親位于同一層的結(jié)點（但并非同一雙親）。祖先：即從根到該結(jié)點所經(jīng)分支的所有結(jié)點。子孫：即該結(jié)點下層子樹中的任意結(jié)點。326.3.1樹的定義結(jié)點的層數(shù)：從根到該結(jié)點的層數(shù)（根結(jié)點第一層）。樹的深度：指所有結(jié)點最大的層數(shù)（Max{各結(jié)點的層次}）。樹的度：所有結(jié)點度的最大值（Max{各結(jié)點的度}）。想想這棵樹的深度和度是多少？6.3.1樹的定義有序樹：一棵樹中結(jié)點的各子樹從左到右是有次序的，即若交換了某結(jié)點各子樹的相對位置，則構(gòu)成不同的樹，則稱為有序樹。無序樹：反之，若結(jié)點各子樹可互換位置，則稱為無序樹。森林：零棵或有限棵不相交的樹的集合成為森林。BDIEHFCGJK346.3.2二叉樹1、二叉樹的概念二叉樹：有限個結(jié)點（n≥0）的集合，該集合或者為空、或者由一個稱為根的結(jié)點及兩個不相交的、被分別稱為左子樹和右子樹的二叉樹組成。當(dāng)集合為空時，稱該二叉樹為空二叉樹。

邏輯結(jié)構(gòu)：一對二（1：2）基本特征:①每個結(jié)點最多只有兩棵子樹（不存在度大于2的結(jié)點）；②左子樹和右子樹次序不能顛倒（有序樹）。356.3.2二叉樹1、二叉樹的概念二叉樹具有5種基本形態(tài)：

滿二叉樹：在二叉樹中，如果所有分支結(jié)點都存在左子樹和右子樹，并且所有葉子結(jié)點都在同一層上，這樣的一棵二叉樹稱作滿二叉樹。366.3.2二叉樹1、二叉樹的概念完全二叉樹：一棵深度為k的有n個結(jié)點的二叉樹，對樹中的結(jié)點按從上至下、從左到右的順序進(jìn)行編號，如果編號為i（1≤i≤n）的結(jié)點與滿二叉樹中編號為i的結(jié)點在二叉樹中的位置相同，則這棵二叉樹稱為完全二叉樹。特點：葉子結(jié)點只能出現(xiàn)在最下層和次最下層，且最下層的葉子結(jié)點集中在樹的左部。注意：一個滿二叉樹必定是一棵完全二叉樹，而完全二叉樹

未必是滿二叉樹。376.3.2二叉樹滿二叉樹完全二叉樹非完全二叉樹386.3.2二叉樹2、二叉樹的主要性質(zhì)性質(zhì)1:

在二叉樹的第i層上最多有2i-1個結(jié)（i≥1）。性質(zhì)2:

深度為k的二叉樹最多有2k-1個結(jié)（k≥1）。提問：第i層上至少有

個結(jié)點？1提問：深度為k時至少有

個結(jié)點？k性質(zhì)3:

具有n個結(jié)點的完全二叉樹的深度必為log2n＋1性質(zhì)4:

對完全二叉樹，若從上至下、從左至右編號，則編號為i

的結(jié)點，其左孩子編號必為2i，其右孩子編號必為2i＋1；其雙親的編號必為i/2（i＝1時為根,除外）。396.3.2二叉樹3、二叉樹的存儲結(jié)構(gòu)(1)順序存儲結(jié)構(gòu)用一組連續(xù)的存儲單元（數(shù)組）存放二叉樹中的結(jié)點。一般是按照二叉樹結(jié)點從上至下、從左到右的順序存儲。完全二叉樹和滿二叉樹采用順序存儲比較合適，樹中結(jié)點的序號可以唯一地反映出結(jié)點之間的邏輯關(guān)系，這樣既能夠最大可能地節(jié)省存儲空間，又可以利用數(shù)組元素的下標(biāo)值確定結(jié)點在二叉樹中的位置以及結(jié)點之間的關(guān)系。40按二叉樹的結(jié)點“自上而下、從左至右”編號，用一組連續(xù)的存儲單元存儲。ABCDEFGHI[1][2][3][4][5][6][7][8][9]ABCGEIDHF問：順序存儲后能否復(fù)原成唯一對應(yīng)的二叉樹形狀？答：若是完全/滿二叉樹則可以做到唯一復(fù)原。而且有規(guī)律：下標(biāo)值為i的雙親，其左孩子的下標(biāo)值必為2i，其右孩子的下標(biāo)值必為2i＋1（即性質(zhì)4）T[0]一般不用6.3.2二叉樹4141討論：不是完全二叉樹怎么辦？答：一律轉(zhuǎn)為完全二叉樹！方法很簡單，將各層空缺處統(tǒng)統(tǒng)補上“虛結(jié)點”，其內(nèi)容為空。AB^C^^^D^…E[1][2][3][4][5][6][7][8][9].[16]ABECD缺點：①浪費空間；②插入、刪除不便

426.3.2二叉樹(2)鏈?zhǔn)酱鎯Y(jié)構(gòu)用鏈表來表示一棵二叉樹。鏈表中每個結(jié)點由三個域組成，除了數(shù)據(jù)域外，還有兩個指針域，分別用來給出該結(jié)點的左子結(jié)點和右子結(jié)點所在的鏈結(jié)點的存儲地址。非完全二叉樹的鏈?zhǔn)酱鎯atalchildrchilddatalchildrchild4343例：

ABECD^AB^D^C^^E^6.3.2二叉樹446.4圖狀結(jié)構(gòu)圖狀結(jié)構(gòu)的特點數(shù)據(jù)元素之間存在著多對多的關(guān)系。圖狀結(jié)構(gòu)的應(yīng)用鐵路交通圖、通信網(wǎng)絡(luò)結(jié)構(gòu)、人與人之間的社會關(guān)系等。456.4圖狀結(jié)構(gòu)1.圖的定義和術(shù)語

G＝（V，E）;其中V＝{vi|vi∈dataobject}；

E＝{(vi,vj)|vi,vj∈V∧P(vi,vj)}。G表示一個圖，V是圖G中頂點的集合，頂點集合構(gòu)成數(shù)據(jù)對象（dataobject），頂點就代表數(shù)據(jù)元素，E是圖G中邊的集合，集合E中P(vi,vj)表示頂點vi和頂點vj之間有一條直接連線，即偶對(vi,vj)表示圖中的一條邊。abcd(b)無向圖G2(a)有向圖G1acbde466.4圖狀結(jié)構(gòu)1.圖的定義和術(shù)語有向圖：在一個圖中，如果任意兩個頂點構(gòu)成的偶對<vi,vj>∈E是有序的，即頂點之間的連線是有方向的，稱該圖為有向圖。無向圖：在一個圖中，如果任意兩個頂點構(gòu)成的偶對(vi,vj)∈E是無序的，即頂點之間的連線是沒有方向的，稱該圖為無向圖。無向圖中，頂點之間的連線稱為邊，用頂點的無序偶對(vi,vj)來表示。有向圖中，頂點之間的連線稱為弧，用頂點的有序偶對

<vi,vj>來表示。476.4圖狀結(jié)構(gòu)無向完全圖：在一個無向圖中，如果任意兩個頂點都有一條邊直接連接，稱該圖為無向完全圖。有向完全圖：在一個有向圖中，如果任意兩個頂點都有方向互為相反的兩條弧相連接，稱該圖為有向完全圖。頂點v的度：指連接該頂點的邊數(shù)，通常記為TD(v)。頂點v的入度：指以該頂點為終點的弧的數(shù)目，記為ID(v);頂點v的出度：指以該頂點為始點的弧的數(shù)目，記為OD(v);

TD(v)=ID(v)+OD(v)1.圖的定義和術(shù)語486.4圖狀結(jié)構(gòu)路徑：在無向圖中，頂點vp到頂點vq之間的路徑是指頂點序列vp,vi1,vi2,…,vim,vq。其中,(vp,vi1),(vi1,vi2),…,,(vim,vq)分別為圖中的邊。路徑的長度：路徑上邊的數(shù)目稱為路徑長度?；芈?環(huán))：始點和終點是同一個頂點的路徑。簡單路徑：頂點不重復(fù)出現(xiàn)的路徑。例：1.圖的定義和術(shù)語6.4圖狀結(jié)構(gòu)2、圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)比較復(fù)雜，表現(xiàn)在：任意頂點之間可能存在聯(lián)系，無法以數(shù)據(jù)元素在存儲區(qū)中的物理位置來表示元素之間的關(guān)系；圖中頂點的度不一樣，有的可能相差很大，若按度數(shù)最大的頂點設(shè)計結(jié)構(gòu)，則會浪費很多存儲單元，反之按每個頂點自己的度設(shè)計不同的結(jié)構(gòu)，又會影響操作。6.4圖狀結(jié)構(gòu)1）鄰接矩陣它用兩個數(shù)組分別存儲數(shù)據(jù)元素（頂點）的信息和數(shù)據(jù)元素之間的關(guān)系（邊或?。┑男畔ⅰＴ刂g的關(guān)系的信息用一個二維數(shù)組來表示。516.4圖狀結(jié)構(gòu)無向圖的鄰接矩陣①無權(quán)無向圖的鄰接矩陣1若(vi,vj)∈E，即vi,vj鄰接0若(vi,vj)E，即vi,vj不鄰接A[i][j]=(a)無向圖abcd0111101111011110(b)鄰接矩陣526.4圖狀結(jié)構(gòu)②帶權(quán)無向圖的鄰接矩陣

權(quán)值可以理解為節(jié)點間的距離、運輸成本等等無向圖的鄰接矩陣是對稱方陣，對于頂點vi，其度數(shù)是第i行的非0元素的個數(shù)，邊數(shù)是上(或下)三角形矩陣中非0元素個數(shù)。有向圖的鄰接矩陣①無權(quán)有向圖6.4圖狀結(jié)構(gòu)②帶權(quán)有向圖的鄰接矩陣6.4圖狀結(jié)構(gòu)6.6外存數(shù)據(jù)組織數(shù)據(jù)通常以文件的方式組織并存儲在外存。文件管理如何高效管理以文件形式存儲在外存上的海量數(shù)據(jù)，使用戶能夠方便使用。文件管理研究如何對外存上的數(shù)據(jù)進(jìn)行組織。6.6.1文件文件（File）通常指的是存儲