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

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

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

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

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

常借助于程序設(shè)計(jì)語(yǔ)言中的數(shù)組來(lái)實(shí)現(xiàn)。2）鏈?zhǔn)酱鎯?chǔ)邏輯上相鄰的元素不要求其物理位置相鄰，元素間的邏輯關(guān)系通過(guò)附設(shè)的指針字段來(lái)表示。常借助于程序設(shè)計(jì)語(yǔ)言中的指針來(lái)實(shí)現(xiàn)。6.1概念和術(shù)語(yǔ)順序存儲(chǔ)：數(shù)據(jù)元素的存儲(chǔ)地址是連續(xù)的鏈?zhǔn)酱鎯?chǔ):數(shù)據(jù)元素的存儲(chǔ)地址不要求是連續(xù)的。有相鄰的數(shù)據(jù)元素a和b，分別采用順序和鏈?zhǔn)酱鎯?chǔ)如下圖所示：abba&b順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)136.2線性結(jié)構(gòu)線性結(jié)構(gòu)的特點(diǎn)：在非空有限集上只有一個(gè)首結(jié)點(diǎn)和一個(gè)尾結(jié)點(diǎn)。每個(gè)元素有且只有一個(gè)直接前驅(qū)（第一個(gè)元素除外）。每個(gè)元素有且只有一個(gè)直接后繼（最后一個(gè)元素除外）。數(shù)據(jù)元素之間存在著一對(duì)一的關(guān)系。常見(jiàn)線性結(jié)構(gòu)：線性表?xiàng)ｊ?duì)列6.2.1線性表1、線性表(LinearList)：是由n(n≥0)個(gè)數(shù)據(jù)元素(結(jié)點(diǎn))a1，a2，…an組成的有限序列。該序列中的所有結(jié)點(diǎn)具有相同的數(shù)據(jù)類型。其中數(shù)據(jù)元素的個(gè)數(shù)n稱為線性表的長(zhǎng)度。當(dāng)n=0時(shí)，稱為空表。當(dāng)n>0時(shí)，將非空的線性表記作：

(a1，a2，…an)6.2.1線性表1、線性表(LinearList)：a1稱為線性表的首結(jié)點(diǎn)，an稱為線性表尾結(jié)點(diǎn)。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、線性表的順序存儲(chǔ)線性表的順序存儲(chǔ)是指用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的各個(gè)元素。使得邏輯結(jié)構(gòu)上相鄰的數(shù)據(jù)元素存儲(chǔ)在相鄰的物理存儲(chǔ)單元。采用順序存儲(chǔ)結(jié)構(gòu)的線性表通常稱為順序表。高級(jí)語(yǔ)言中采用數(shù)組來(lái)表示線性表的順序存儲(chǔ)。6.2.1線性表2、線性表的順序存儲(chǔ)（1）順序表的存儲(chǔ)結(jié)構(gòu)假設(shè)線性表中的第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址為：

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

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

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

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

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

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

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

個(gè)結(jié)點(diǎn)？1提問(wèn)：深度為k時(shí)至少有

個(gè)結(jié)點(diǎn)？k性質(zhì)3:

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

對(duì)完全二叉樹(shù)，若從上至下、從左至右編號(hào)，則編號(hào)為i

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

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

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

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

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

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

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

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