吉林大學(xué)內(nèi)部絕密資料數(shù)據(jù)結(jié)構(gòu)總復(fù)習(xí)（課堂PPT）

1、.1數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)總復(fù)習(xí).2教學(xué)內(nèi)容教學(xué)內(nèi)容l第一章第一章緒論緒論l第二章第二章線性表、堆棧和隊(duì)列線性表、堆棧和隊(duì)列l(wèi)第三章第三章數(shù)組和字符串?dāng)?shù)組和字符串l第六章第六章遞歸遞歸l第四章第四章樹(shù)樹(shù)l第五章第五章圖圖l第七章第七章排序排序l第八章第八章查找查找基礎(chǔ)知識(shí)基礎(chǔ)知識(shí)基礎(chǔ)知識(shí)基礎(chǔ)知識(shí)線性結(jié)構(gòu)線性結(jié)構(gòu)非線性結(jié)構(gòu)非線性結(jié)構(gòu)非線性結(jié)構(gòu)非線性結(jié)構(gòu).3重點(diǎn)內(nèi)容重點(diǎn)內(nèi)容l三三兩兩三三兩兩l三要素（邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、操作）l三個(gè)數(shù)據(jù)結(jié)構(gòu)（線性表、樹(shù)、圖）l兩類算法（排序、查找）l兩個(gè)評(píng)價(jià)算法的主要標(biāo)準(zhǔn)（時(shí)間、空間復(fù)雜性）l兩個(gè)表（33，22）.433（2、3、4、5章）章）線性表樹(shù)圖邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)

2、操作.522（7、8章）章）時(shí)間復(fù)雜性空間復(fù)雜性排序插入、交換、選擇、合并查找有序表的查找雜湊.6重點(diǎn)內(nèi)容重點(diǎn)內(nèi)容l3+2三類數(shù)據(jù)結(jié)構(gòu)l線性表l樹(shù)l圖兩類算法l排序l查找.7教學(xué)內(nèi)容教學(xué)內(nèi)容l基礎(chǔ)知識(shí)第一章緒 論.8一、基礎(chǔ)知識(shí)一、基礎(chǔ)知識(shí)l掌握數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ)掌握數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ)包括：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)結(jié)構(gòu)等基本包括：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)結(jié)構(gòu)等基本 概念。概念。l算法和算法分析算法和算法分析掌握算法、算法的時(shí)間復(fù)雜度和空間復(fù)雜度等概念掌握算法、算法的時(shí)間復(fù)雜度和空間復(fù)雜度等概念掌握算法分析的方法，對(duì)一般算法能分析出時(shí)間復(fù)掌握算法分析的方法，對(duì)一般算法能分析出

3、時(shí)間復(fù)雜度。雜度。 .9一、基礎(chǔ)知識(shí)一、基礎(chǔ)知識(shí)l數(shù)據(jù)數(shù)據(jù):計(jì)算機(jī)程序要處理的“原料”l數(shù)據(jù)元素?cái)?shù)據(jù)元素:是組成數(shù)據(jù)的基本單位。在程序中通常把結(jié)點(diǎn)作為一個(gè)整體進(jìn)行考慮和處理。l數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng):每個(gè)數(shù)據(jù)元素都有學(xué)號(hào)、姓名這兩個(gè)數(shù)據(jù)項(xiàng)構(gòu)成。數(shù)據(jù)項(xiàng)是構(gòu)成數(shù)據(jù)的最小單位。.10一、基礎(chǔ)知識(shí)一、基礎(chǔ)知識(shí)的定義：的定義：按某種邏輯關(guān)系將一批數(shù)據(jù)元素組織起按某種邏輯關(guān)系將一批數(shù)據(jù)元素組織起來(lái)來(lái)按一定的存儲(chǔ)方式把它們存儲(chǔ)起來(lái)；按一定的存儲(chǔ)方式把它們存儲(chǔ)起來(lái)；1.在數(shù)據(jù)上定義需要施加的操作。在數(shù)據(jù)上定義需要施加的操作。.11一、基礎(chǔ)知識(shí)一、基礎(chǔ)知識(shí)l數(shù)據(jù)結(jié)構(gòu)的組成：數(shù)據(jù)結(jié)構(gòu)的組成：數(shù)據(jù)的數(shù)據(jù)的數(shù)據(jù)的數(shù)據(jù)的數(shù)據(jù)需要

4、數(shù)據(jù)需要.12邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)l數(shù)據(jù)元素之間的邏輯關(guān)系稱為數(shù)據(jù)數(shù)據(jù)元素之間的邏輯關(guān)系稱為數(shù)據(jù)的的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)。l邏輯結(jié)構(gòu)的形式化表示邏輯結(jié)構(gòu)的形式化表示邏輯結(jié)構(gòu)表示為二元組邏輯結(jié)構(gòu)表示為二元組 L=(N, R)，其中，其中N(L)是結(jié)點(diǎn)的有限集合，是結(jié)點(diǎn)的有限集合， R(L)是是N上的關(guān)系集合。上的關(guān)系集合。.13邏輯結(jié)構(gòu)的分類邏輯結(jié)構(gòu)的分類l線性結(jié)構(gòu)結(jié)構(gòu)中有且僅有一個(gè)有且僅有一個(gè)始結(jié)點(diǎn)和一個(gè)終結(jié)點(diǎn)，始結(jié)點(diǎn)只有一個(gè)后繼結(jié)點(diǎn)，終結(jié)點(diǎn)只有一個(gè)前趨結(jié)點(diǎn)，每個(gè)內(nèi)結(jié)點(diǎn)有且僅有一個(gè)有且僅有一個(gè)前趨結(jié)點(diǎn)和一個(gè)后繼結(jié)點(diǎn)。l非線性結(jié)構(gòu)（樹(shù)、圖）結(jié)構(gòu)中的結(jié)點(diǎn)可能有多個(gè)可能有多個(gè)前趨結(jié)點(diǎn)和多個(gè)后繼結(jié)點(diǎn).14數(shù)據(jù)

5、的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)l數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)表示稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)鏈接存儲(chǔ)結(jié)構(gòu).15數(shù)據(jù)需要施加的操作數(shù)據(jù)需要施加的操作l數(shù)據(jù)處理是指對(duì)數(shù)據(jù)進(jìn)行查找、插入、刪數(shù)據(jù)處理是指對(duì)數(shù)據(jù)進(jìn)行查找、插入、刪除、合并、排序、統(tǒng)計(jì)以及簡(jiǎn)單計(jì)算等的除、合并、排序、統(tǒng)計(jì)以及簡(jiǎn)單計(jì)算等的操作過(guò)程。操作過(guò)程。線性表樹(shù)圖.16算法描述語(yǔ)言算法描述語(yǔ)言 ADLlADL 的格式算法（變量i1,變量im.變量j1,變量jn）/單行注釋（或/*/多行注釋） 步驟名1 步驟1所執(zhí)行操作的高度概括 語(yǔ)句序列. 步驟名n 步驟n所執(zhí)行操作的高度概括 語(yǔ)句序列. .17時(shí)間復(fù)雜性對(duì)所研究問(wèn)題的基本操作對(duì)所研究問(wèn)題的基本

6、操作數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)操作操作線線性性結(jié)結(jié)構(gòu)構(gòu)樹(shù)樹(shù)型型結(jié)結(jié)構(gòu)構(gòu)圖圖狀狀結(jié)結(jié)構(gòu)構(gòu)集集合合順順 序序存存 儲(chǔ)儲(chǔ)結(jié)結(jié) 構(gòu)構(gòu)鏈鏈 式式存存 儲(chǔ)儲(chǔ)結(jié)結(jié) 構(gòu)構(gòu).19二、常用數(shù)據(jù)結(jié)構(gòu)線性表樹(shù)圖.20線性表l掌握線性表的定義和邏輯結(jié)構(gòu)，了解線性表的基本運(yùn)算。掌握線性表的定義和邏輯結(jié)構(gòu)，了解線性表的基本運(yùn)算。l掌握順序表的插入和刪除操作及平均時(shí)間性能分析。掌握順序表的插入和刪除操作及平均時(shí)間性能分析。l熟練掌握單鏈表查找、插入和刪除操作并分析其時(shí)間復(fù)雜度。熟練掌握單鏈表查找、插入和刪除操作并分析其時(shí)間復(fù)雜度。l了解循環(huán)單鏈表算法和單鏈表上相應(yīng)算法的異同點(diǎn)。了解循環(huán)單鏈表算法和單鏈表

7、上相應(yīng)算法的異同點(diǎn)。l熟練利用單鏈表設(shè)計(jì)算法解決簡(jiǎn)單的應(yīng)用問(wèn)題。熟練利用單鏈表設(shè)計(jì)算法解決簡(jiǎn)單的應(yīng)用問(wèn)題。l掌握雙鏈表的基本操作。掌握雙鏈表的基本操作。l掌握順序表和鏈表的主要優(yōu)缺點(diǎn)掌握順序表和鏈表的主要優(yōu)缺點(diǎn).21線性表線性表定義：線性表定義：一個(gè)線性表是由零個(gè)或多個(gè)一個(gè)線性表是由零個(gè)或多個(gè)具有相同類型的結(jié)點(diǎn)組成的有序集合。具有相同類型的結(jié)點(diǎn)組成的有序集合。用（用（a0，a1，an-1）來(lái)表示一個(gè)線性）來(lái)表示一個(gè)線性表。當(dāng)表。當(dāng)n0時(shí)，時(shí)，a0稱為表的始結(jié)點(diǎn)，稱為表的始結(jié)點(diǎn)，an-1稱為表的終結(jié)點(diǎn)，當(dāng)稱為表的終結(jié)點(diǎn)，當(dāng)n=0時(shí)，線性表中時(shí)，線性表中有零個(gè)結(jié)點(diǎn)，稱為空表。有零個(gè)結(jié)點(diǎn)，稱為空表。

8、.22線性表的存儲(chǔ)結(jié)構(gòu)線性表的存儲(chǔ)結(jié)構(gòu)l順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)l鏈接存儲(chǔ)結(jié)構(gòu)鏈接存儲(chǔ)結(jié)構(gòu)單鏈表單鏈表循環(huán)鏈表循環(huán)鏈表雙向循環(huán)鏈表雙向循環(huán)鏈表.23棧棧 和和 隊(duì)隊(duì) 列（線性表的應(yīng)用）列（線性表的應(yīng)用）l掌握棧的邏輯結(jié)構(gòu)特點(diǎn)。掌握棧的邏輯結(jié)構(gòu)特點(diǎn)。l掌握順序棧和鏈棧上實(shí)現(xiàn)的進(jìn)棧、退棧等基本掌握順序棧和鏈棧上實(shí)現(xiàn)的進(jìn)棧、退棧等基本算法。算法。l掌握隊(duì)列的邏輯結(jié)構(gòu)特點(diǎn)。掌握隊(duì)列的邏輯結(jié)構(gòu)特點(diǎn)。l掌握順序隊(duì)列（主要是循環(huán)隊(duì)列）和鏈隊(duì)列上掌握順序隊(duì)列（主要是循環(huán)隊(duì)列）和鏈隊(duì)列上實(shí)現(xiàn)的入隊(duì)、出隊(duì)等基本算法。實(shí)現(xiàn)的入隊(duì)、出隊(duì)等基本算法。.24棧棧 和和 隊(duì)隊(duì) 列（線性表的應(yīng)用）列（線性表的應(yīng)用）棧和隊(duì)列都

9、是操作受限的線性表?xiàng)：完?duì)列都是操作受限的線性表?xiàng)５亩x：棧是插入和刪除只能在其一端進(jìn)行的線性表。棧的定義：棧是插入和刪除只能在其一端進(jìn)行的線性表。并按先進(jìn)后出（并按先進(jìn)后出（ F I L O )F I L O )或后進(jìn)先出（或后進(jìn)先出（I I）的原則進(jìn)行操作。的原則進(jìn)行操作。隊(duì)列的定義：隊(duì)列是插入在一端進(jìn)行而刪除在其另一端隊(duì)列的定義：隊(duì)列是插入在一端進(jìn)行而刪除在其另一端進(jìn)行的線性表。并按先進(jìn)向出（進(jìn)行的線性表。并按先進(jìn)向出（FIFOFIFO）的原則進(jìn)行操）的原則進(jìn)行操作。能進(jìn)行刪除的一端稱為隊(duì)首（作。能進(jìn)行刪除的一端稱為隊(duì)首（frontfront），能進(jìn)行），能進(jìn)行插入操作的一端稱為隊(duì)尾（插入

10、操作的一端稱為隊(duì)尾（rearrear）。）。.25 棧的應(yīng)用棧的應(yīng)用算術(shù)表達(dá)式求值算術(shù)表達(dá)式求值運(yùn)算規(guī)則：運(yùn)算規(guī)則：(1) 先計(jì)算括號(hào)內(nèi)，后計(jì)算括號(hào)外；先計(jì)算括號(hào)內(nèi)，后計(jì)算括號(hào)外；(2) 在無(wú)括號(hào)或同層括號(hào)內(nèi)，先進(jìn)行乘除運(yùn)算，在無(wú)括號(hào)或同層括號(hào)內(nèi)，先進(jìn)行乘除運(yùn)算，后進(jìn)行加減運(yùn)算，即乘除運(yùn)算的優(yōu)先級(jí)高于加后進(jìn)行加減運(yùn)算，即乘除運(yùn)算的優(yōu)先級(jí)高于加減運(yùn)算的優(yōu)先級(jí)；減運(yùn)算的優(yōu)先級(jí)；(3) 同一優(yōu)先級(jí)運(yùn)算，從左向右依次進(jìn)行。同一優(yōu)先級(jí)運(yùn)算，從左向右依次進(jìn)行。.26數(shù)組、字符串和集合（線性結(jié)構(gòu)）數(shù)組、字符串和集合（線性結(jié)構(gòu)）l掌握一維、二維數(shù)組的存儲(chǔ)方法及對(duì)任意元素求地址公式l掌握稀疏矩陣的概念及存儲(chǔ)方法

11、l掌握串的有關(guān)概念及基本算法。l了解串的兩種存儲(chǔ)表示。l了解模式匹配算法.27樹(shù)樹(shù)l掌握樹(shù)的常用術(shù)語(yǔ)及含義。l掌握二叉樹(shù)的遞歸定義及樹(shù)與二叉樹(shù)的差別。l熟練掌握二叉樹(shù)的性質(zhì)。l掌握二叉樹(shù)的兩種存儲(chǔ)方法。l熟練掌握二叉樹(shù)的四種遍歷算法。l熟練掌握確定四種遍歷所得到的相應(yīng)的結(jié)點(diǎn)訪問(wèn)序列。.28樹(shù)樹(shù)l熟練掌握以二叉樹(shù)遍歷算法為基礎(chǔ)，設(shè)計(jì)有關(guān)算法解決簡(jiǎn)單的應(yīng)用問(wèn)題。l掌握樹(shù)的存儲(chǔ)方法并設(shè)計(jì)有關(guān)算法解決簡(jiǎn)單的應(yīng)用問(wèn)題。l掌握線索二叉樹(shù)的概念及存儲(chǔ)方法并能將一棵二叉樹(shù)線索化。l熟練掌握樹(shù)和森林與二叉樹(shù)之間的轉(zhuǎn)換方法。l熟練掌握根據(jù)給定的葉結(jié)點(diǎn)及其權(quán)值構(gòu)造出哈夫曼樹(shù)。.29常用數(shù)據(jù)結(jié)構(gòu)常用數(shù)據(jù)結(jié)構(gòu)l樹(shù)樹(shù)是由

12、唯一的起始結(jié)點(diǎn)“根結(jié)點(diǎn)”( r o o t)出發(fā)的結(jié)點(diǎn)集合，其中，任何非根結(jié)點(diǎn)都有且僅有一個(gè)前任何非根結(jié)點(diǎn)都有且僅有一個(gè)前趨結(jié)點(diǎn)趨結(jié)點(diǎn)，稱之為該結(jié)點(diǎn)的父結(jié)點(diǎn)；任何結(jié)點(diǎn)都可能任何結(jié)點(diǎn)都可能有多個(gè)后繼結(jié)點(diǎn)有多個(gè)后繼結(jié)點(diǎn)，稱之為該結(jié)點(diǎn)的子結(jié)點(diǎn)；若某結(jié)點(diǎn)沒(méi)有后繼結(jié)點(diǎn)，則稱之為葉子結(jié)點(diǎn)。若存在路徑，其中是的后繼結(jié)點(diǎn)，則稱為的子孫結(jié)點(diǎn)，稱為的祖先結(jié)點(diǎn)，該路徑所經(jīng)歷的邊的個(gè)數(shù)被稱為路徑的長(zhǎng)度。一個(gè)結(jié)點(diǎn)到它的某個(gè)子孫結(jié)點(diǎn)有且僅有一條路徑。.30二叉樹(shù) (Binary Tree)二叉樹(shù)是結(jié)點(diǎn)的有限集合，它必須滿足二叉樹(shù)是結(jié)點(diǎn)的有限集合，它必須滿足 下面的一個(gè)條件：下面的一個(gè)條件：（1）它是空集。）它是空集。（2

13、）它由一個(gè)根結(jié)點(diǎn)）它由一個(gè)根結(jié)點(diǎn),根結(jié)點(diǎn)的左右子樹(shù)根結(jié)點(diǎn)的左右子樹(shù)構(gòu)成，且其左右子樹(shù)滿足二叉樹(shù)定義。構(gòu)成，且其左右子樹(shù)滿足二叉樹(shù)定義。.31樹(shù)的儲(chǔ)結(jié)構(gòu) 1 1 順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu) 完全二叉樹(shù)的順序存儲(chǔ)完全二叉樹(shù)的順序存儲(chǔ): :按層次次序給結(jié)點(diǎn)編號(hào)按層次次序給結(jié)點(diǎn)編號(hào)，使，使用用一維數(shù)組一維數(shù)組A來(lái)存放。來(lái)存放。A0A0存儲(chǔ)二叉樹(shù)的根結(jié)點(diǎn)，存儲(chǔ)二叉樹(shù)的根結(jié)點(diǎn)，AiAi結(jié)點(diǎn)的左孩子結(jié)點(diǎn)存放在結(jié)點(diǎn)的左孩子結(jié)點(diǎn)存放在2i+12i+1處，而處，而AiAi的右孩子的右孩子結(jié)點(diǎn)存放在結(jié)點(diǎn)存放在A2i+2A2i+2處處 2 2 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 二叉樹(shù)諸結(jié)點(diǎn)被隨機(jī)存放在內(nèi)存空間中，結(jié)點(diǎn)二叉樹(shù)諸結(jié)

14、點(diǎn)被隨機(jī)存放在內(nèi)存空間中，結(jié)點(diǎn)之間的關(guān)系用指針說(shuō)明。之間的關(guān)系用指針說(shuō)明。( (線索樹(shù)線索樹(shù)) ).32基本操作l二叉樹(shù)的遍歷：按照一定次序訪問(wèn)樹(shù)中所有結(jié)二叉樹(shù)的遍歷：按照一定次序訪問(wèn)樹(shù)中所有結(jié) 點(diǎn)，并且每個(gè)結(jié)點(diǎn)的值僅被訪問(wèn)一次的過(guò)程。點(diǎn)，并且每個(gè)結(jié)點(diǎn)的值僅被訪問(wèn)一次的過(guò)程。遍歷次序是樹(shù)中結(jié)點(diǎn)的一遍歷次序是樹(shù)中結(jié)點(diǎn)的一個(gè)有序序列，稱為二叉樹(shù)的先根（中根、后根）個(gè)有序序列，稱為二叉樹(shù)的先根（中根、后根）序列。序列。.33構(gòu)造哈夫曼樹(shù)哈夫曼算法基本思想：哈夫曼算法基本思想： 根據(jù)給定的根據(jù)給定的n個(gè)權(quán)值個(gè)權(quán)值w1 , w2 , ,wn構(gòu)成構(gòu)成n棵二叉樹(shù)的棵二叉樹(shù)的森林森林F=T1 ,T2 , ,T

15、n ,其中每棵二叉樹(shù)其中每棵二叉樹(shù)Ti中都只有一中都只有一個(gè)權(quán)值為個(gè)權(quán)值為wi的根結(jié)點(diǎn)，其左、右子樹(shù)均空；的根結(jié)點(diǎn)，其左、右子樹(shù)均空； 在森林在森林F中選出兩棵根結(jié)點(diǎn)權(quán)值最小的樹(shù)作為一棵新中選出兩棵根結(jié)點(diǎn)權(quán)值最小的樹(shù)作為一棵新樹(shù)的左、右子樹(shù)，且置新樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左、樹(shù)的左、右子樹(shù)，且置新樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)上根結(jié)點(diǎn)的權(quán)值之和；右子樹(shù)上根結(jié)點(diǎn)的權(quán)值之和； 從從F中刪除構(gòu)成新樹(shù)的那兩棵樹(shù)，同時(shí)把新樹(shù)加入中刪除構(gòu)成新樹(shù)的那兩棵樹(shù)，同時(shí)把新樹(shù)加入F中；中； 重復(fù)第和第步，直到重復(fù)第和第步，直到F中只含有一棵樹(shù)為止，此中只含有一棵樹(shù)為止，此樹(shù)便是哈夫曼樹(shù)。樹(shù)便是哈夫曼樹(shù)。.34圖l掌握?qǐng)D

16、的常用術(shù)語(yǔ)及含義。掌握?qǐng)D的常用術(shù)語(yǔ)及含義。l掌握?qǐng)D的深度優(yōu)先搜索和廣度優(yōu)先搜索兩種遍掌握?qǐng)D的深度優(yōu)先搜索和廣度優(yōu)先搜索兩種遍歷算法及執(zhí)行過(guò)程。歷算法及執(zhí)行過(guò)程。l熟練掌握確定兩種遍歷所得到的頂點(diǎn)訪問(wèn)序列。熟練掌握確定兩種遍歷所得到的頂點(diǎn)訪問(wèn)序列。.35圖l要求對(duì)給定的連通圖，根據(jù)要求對(duì)給定的連通圖，根據(jù)Prim和和Kruskar算算法構(gòu)造最小生成樹(shù)。法構(gòu)造最小生成樹(shù)。l對(duì)于給定的有向圖，根據(jù)對(duì)于給定的有向圖，根據(jù)Dijkstra算法能畫(huà)出算法能畫(huà)出求單源最短路徑的過(guò)程示意圖。求單源最短路徑的過(guò)程示意圖。l對(duì)于給定的有向圖，若拓?fù)湫蛄写嬖冢瑒t要求對(duì)于給定的有向圖，若拓?fù)湫蛄写嬖?，則要求寫(xiě)出一個(gè)或

17、多個(gè)拓?fù)湫蛄?。?xiě)出一個(gè)或多個(gè)拓?fù)湫蛄?。l對(duì)于給定的有向圖，能求出其關(guān)鍵路徑等。對(duì)于給定的有向圖，能求出其關(guān)鍵路徑等。.36圖l圖（圖（Graph）是一種較線性表和樹(shù)更為復(fù)雜的）是一種較線性表和樹(shù)更為復(fù)雜的非線性結(jié)構(gòu)。在圖結(jié)構(gòu)中，對(duì)結(jié)點(diǎn)（圖中常稱非線性結(jié)構(gòu)。在圖結(jié)構(gòu)中，對(duì)結(jié)點(diǎn)（圖中常稱為頂點(diǎn)）的前趨和后繼個(gè)數(shù)都是不加限制的，為頂點(diǎn)）的前趨和后繼個(gè)數(shù)都是不加限制的，即結(jié)點(diǎn)之間的關(guān)系是任意的。圖中任意兩個(gè)結(jié)即結(jié)點(diǎn)之間的關(guān)系是任意的。圖中任意兩個(gè)結(jié)點(diǎn)之間都可能相關(guān)。圖狀結(jié)構(gòu)可以描述各種復(fù)點(diǎn)之間都可能相關(guān)。圖狀結(jié)構(gòu)可以描述各種復(fù)雜的數(shù)據(jù)對(duì)象。雜的數(shù)據(jù)對(duì)象。.37圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)l鄰接矩陣l鄰接表

18、 (Adjacency List).38圖的基本操作遍歷遍歷深度優(yōu)先遍歷深度優(yōu)先遍歷廣度優(yōu)先遍歷廣度優(yōu)先遍歷.39基于圖的算法拓?fù)渑判蛲負(fù)渑判蜿P(guān)鍵路徑關(guān)鍵路徑最短路徑（最短路徑（Dijkstra算法）算法）最小支撐樹(shù)最小支撐樹(shù)(Prim、Kruskar算法算法).40排序排序l排序排序：將一組雜亂無(wú)章的數(shù)據(jù)按一定的規(guī)律順：將一組雜亂無(wú)章的數(shù)據(jù)按一定的規(guī)律順次排列起來(lái)。次排列起來(lái)。l插入排序插入排序l交換排序交換排序l選擇排序選擇排序l合并排序合并排序各種內(nèi)部排序方法的比較各種內(nèi)部排序方法的比較 排序方法排序方法 最好時(shí)間最好時(shí)間 平均時(shí)間平均時(shí)間 最壞時(shí)間最壞時(shí)間穩(wěn)定性穩(wěn)定性輔助空間輔助空間冒泡冒泡O(n)O(n)O(nO(n2 2) )O(nO(n2 2) )穩(wěn)定穩(wěn)定O(1)O(1)希爾希爾 O(nO(n1.251.25) ) 不穩(wěn)定不穩(wěn)定O(1)O(1)直接插入直接插入O(n)O(n)O(nO(n2 2) )O(nO(n2 2) )穩(wěn)定穩(wěn)定O(1)O(1)直接選擇直接選擇O(nO(n2 2) )O(nO(n2 2) )O(nO(n2 2) )不穩(wěn)定不穩(wěn)定O(1)O(1)快速快速O(nlogO(nlog2 2n)n)O(nlogO(nlog2 2n)n)O(nO(n2 2) )不穩(wěn)定不穩(wěn)定O(l