數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié),有工大老師多年經(jīng)驗(yàn)編寫.ppt

計(jì)算機(jī)系列課程之間的聯(lián)系 數(shù)據(jù)結(jié)構(gòu)涵蓋的內(nèi)容 二 基本概念和術(shù)語(yǔ) 1 數(shù)據(jù)數(shù)據(jù)是用于描述客觀事物的數(shù)值 字符 以及一切可以輸入到計(jì)算機(jī)中的并由計(jì)算機(jī)程序加以處理的符號(hào)的集合 其范圍隨著計(jì)算機(jī)技術(shù)的發(fā)展而不斷發(fā)展 2 數(shù)據(jù)元素?cái)?shù)據(jù)的基本單位是數(shù)據(jù)元素 在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理 3 數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位 一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成 4 數(shù)據(jù)對(duì)象性質(zhì)相同的元素的集合叫做數(shù)據(jù)對(duì)象 5 結(jié)點(diǎn)數(shù)據(jù)元素在機(jī)內(nèi)的位串表示 即數(shù)據(jù)元素在計(jì)算機(jī)內(nèi)的映象 6 域 字段當(dāng)數(shù)據(jù)元素由若干個(gè)數(shù)據(jù)項(xiàng)組成時(shí) 位串中對(duì)應(yīng)于各個(gè)數(shù)據(jù)項(xiàng)的子串稱為域 字段 是數(shù)據(jù)元素中數(shù)據(jù)項(xiàng)在計(jì)算機(jī)中的映象 7 信息表計(jì)算機(jī)程序所作用的一組數(shù)據(jù)通常稱為信息表 是數(shù)據(jù)對(duì)象在計(jì)算機(jī)中的映象 8 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)元素之間的相互關(guān)系 這種關(guān)系是抽象的 即并不涉及數(shù)據(jù)元素的具體內(nèi)容 是數(shù)據(jù)元素及其相互間的關(guān)系的數(shù)學(xué)描述 9 邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu) 1 邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)中描述的是數(shù)據(jù)元素之間的抽象關(guān)系 邏輯關(guān)系 稱為邏輯結(jié)構(gòu) 2 存儲(chǔ)結(jié)構(gòu) 物理結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示 映象 稱為存儲(chǔ)結(jié)構(gòu) 物理結(jié)構(gòu) 1 1 1基本概念和術(shù)語(yǔ) 3 數(shù)據(jù)元素之間的關(guān)系 邏輯結(jié)構(gòu) 在計(jì)算機(jī)中有兩種表示方法 順序映象 表示 和非順序映象 表示 從而導(dǎo)致兩種不同的存儲(chǔ)結(jié)構(gòu) 順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu) 順序映象 表示 的特點(diǎn)是借助數(shù)據(jù)元素在存儲(chǔ)器中的相對(duì)位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系 非順序映象 表示 的特點(diǎn)是借助指示數(shù)據(jù)元素存儲(chǔ)地址的指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系 1 1 1基本概念和術(shù)語(yǔ) 返回 1 1 2四種基本的數(shù)據(jù)結(jié)構(gòu) 1 集合結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間除了 屬于同一個(gè)集合 的關(guān)系之外 別無其他關(guān)系 關(guān)系比較松散 可用其他結(jié)構(gòu)來表示 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個(gè)對(duì)一個(gè)的關(guān)系 即線性關(guān)系 每個(gè)元素至多有一個(gè)直接前導(dǎo)和后繼 2 線性結(jié)構(gòu) 3 樹型結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個(gè)對(duì)多個(gè)的關(guān)系 即層次關(guān)系 即每一層上的元素可能與下層的多個(gè)元素相關(guān) 而至多與上層的一個(gè)元素相關(guān) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多個(gè)對(duì)多個(gè)的關(guān)系 即任意關(guān)系 任何元素之間都可能有關(guān)系 4 網(wǎng)狀 圖型結(jié)構(gòu) 返回 1 1 3數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象 數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象 研究?jī)?nèi)容 1 數(shù)據(jù)對(duì)象的結(jié)構(gòu)形式 各種數(shù)據(jù)結(jié)構(gòu)的性質(zhì) 邏輯結(jié)構(gòu) 2 數(shù)據(jù)對(duì)象和 關(guān)系 在計(jì)算機(jī)中的表示 物理結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu) 3 數(shù)據(jù)結(jié)構(gòu)上定義的基本操作 算法 4 算法的效率 5 數(shù)據(jù)結(jié)構(gòu)的應(yīng)用 如數(shù)據(jù)分類 檢索 返回 數(shù)據(jù)結(jié)構(gòu)的作用圖 數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)關(guān)系 數(shù)據(jù)表示 數(shù)據(jù)類型 數(shù)學(xué)離散數(shù)學(xué)應(yīng)用數(shù)學(xué) 硬件存儲(chǔ)設(shè)備總體結(jié)構(gòu) 軟件系統(tǒng)軟件應(yīng)用軟件 算法設(shè)計(jì)數(shù)據(jù)運(yùn)算 編碼理論數(shù)據(jù)組合 系統(tǒng)設(shè)計(jì)數(shù)據(jù)存取 2 1算法及其性能評(píng)價(jià)準(zhǔn)則 算法 Algorithm 是對(duì)特定問題求解步驟的一種描述 它是指令 規(guī)則 的有限序列 其中每一條指令表示一個(gè)或多個(gè)操作 算法的特征 有窮性 確定性 能行性 輸入 輸出 算法描述 自然語(yǔ)言 程序設(shè)計(jì)語(yǔ)言 類語(yǔ)言 一 算法 算法的特征和算法描述 常用的算法設(shè)計(jì)方法 遞歸法 Recursion 分治法 Divide andConquer 貪心法 Greedy 動(dòng)態(tài)規(guī)劃 DynamicProgramming 搜索與遍歷 回溯 Backtracking 解空間局部搜索 近似算法 Approximation 在線算法 On Line 等 2 2算法時(shí)間復(fù)雜性分析方法 定理2 1若A n amnm a1n a0是關(guān)于n的m次多項(xiàng)式 則A n nm 此定理說明 時(shí)間復(fù)雜性僅取決于多項(xiàng)式的最高次冪 而與最高次冪的系數(shù)和其他低次項(xiàng)無關(guān) 1 表示實(shí)踐復(fù)雜性為常數(shù)常見的時(shí)間復(fù)雜性及其比較 1 n n n n n n2 n3 2n 設(shè)T1 n O f n T2 n O g n 則加法規(guī)則 T1 n T2 n O max f n g n 乘法規(guī)則 T1 n T2 n O f n g n 1 表達(dá)式和賦值語(yǔ)句 O 1 2 語(yǔ)句序列 用加法規(guī)則 取耗時(shí)最多語(yǔ)句 3 條件語(yǔ)句 O 1 4 FOR語(yǔ)句 O N M N為循環(huán)次數(shù) M為體內(nèi)時(shí)間最多的語(yǔ)句5 WHILE語(yǔ)句 找出與循環(huán)次數(shù)有關(guān)的變量 通過計(jì)算找出上下限 例 x n y 0 while x y 1 y 1 y y 1 時(shí)間復(fù)雜性為O s 0 f n 1 T2 n O f n O 1 常量階 for i 1 i n i for j 1 j n j x s x f n 3n2 2n 1 T3 n O f n O n2 平方階 for i 1 i n i for j 1 j n j c i j 0 for k 1 k n k c i j a i k b k j f n 2n3 3n2 2n 1 T4 n O f n O n3 立方階 for i 1 i n i x s x f n 3n 1 T1 n O f n O n 線形階 第三章線性表 LinerList 知識(shí)點(diǎn) 線性表的邏輯結(jié)構(gòu)和各種存儲(chǔ)表示方法定義在邏輯結(jié)構(gòu)上的各種基本運(yùn)算 操作 在各種存儲(chǔ)結(jié)構(gòu)上如何實(shí)現(xiàn)這些基本運(yùn)算各種基本運(yùn)算的時(shí)間復(fù)雜性 重點(diǎn) 熟練掌握順序表和單鏈表上實(shí)現(xiàn)的各種算法及相關(guān)的時(shí)間復(fù)雜性分析 難點(diǎn) 使用本章所學(xué)的基本知識(shí)設(shè)計(jì)有效算法解決與線性表相關(guān)的應(yīng)用問題 3 1抽象數(shù)據(jù)型線性表 定義 線性表是由n n 0 個(gè)相同類型的元素組成的有序集合 記為 a1 a2 a3 ai 1 ai ai 1 an 其中 n為線性表中元素個(gè)數(shù) 稱為線性表的長(zhǎng)度 當(dāng)n 0時(shí) 為空表 記為 ai為線性表中的元素 類型定義為elementtype a1為表中第1個(gè)元素 無前驅(qū)元素 an為表中最后一個(gè)元素 無后繼元素 對(duì)于 ai 1 ai ai 1 1 i n 稱ai 1為ai的直接前驅(qū) ai 1為ai的直接后繼 位置概念 線性表是有限的 也是有序的 3 1抽象數(shù)據(jù)型線性表 線性表LIST D R D ai ai Elementset i 1 2 n n 0 R H H ai 1 ai D i 2 n 操作 設(shè)L的型為L(zhǎng)IST線性表實(shí)例 x的型為elementtype的元素實(shí)例 p為位置變量 所有操作描述為 Insert x p L Locate x L Retrieve p L Delete p L Previous p L Next p L MakeNull L First L End L 數(shù)學(xué)模型 3 1抽象數(shù)據(jù)型線性表 舉例 設(shè)計(jì)函數(shù)Deleval LIST 3 2線性表的實(shí)現(xiàn) 問題 確定數(shù)據(jù)結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu) 實(shí)現(xiàn)型LIST 并在此基礎(chǔ)上實(shí)現(xiàn)各個(gè)基本操作 存儲(chǔ)結(jié)構(gòu)的三種方式 連續(xù)的存儲(chǔ)空間 數(shù)組 靜態(tài)存儲(chǔ) 非連續(xù)存儲(chǔ)空間 指針 鏈表 動(dòng)態(tài)存儲(chǔ) 游標(biāo) 連續(xù)存儲(chǔ)空間 動(dòng)態(tài)管理思想 靜態(tài)鏈表 3 2 1指針和游標(biāo) 指針 地址量 其值為另一存儲(chǔ)空間的地址 游標(biāo) 整型指示量 其值為數(shù)組的下標(biāo) 用以表示指定元素的 地址 或 位置 所在的數(shù)組下標(biāo) 3 2 2線性表的數(shù)組實(shí)現(xiàn) 順序表 把線性表的元素邏輯順序依次存放在數(shù)組的連續(xù)單元內(nèi) 再用一個(gè)整型量表示最后一個(gè)元素所在單元的下標(biāo) 特點(diǎn) 元素之間的邏輯關(guān)系 相繼 相鄰關(guān)系 用物理上的相鄰關(guān)系來表示 用物理上的連續(xù)性刻畫邏輯上的相繼性 是一種隨機(jī)存儲(chǔ)結(jié)構(gòu) 也就是可以隨機(jī)存取表中的任意元素 其存儲(chǔ)位置可由一個(gè)簡(jiǎn)單直觀的公式來表示 3 2 2線性表的數(shù)組實(shí)現(xiàn) 類型定義 definemaxlength100structLIST elementtypeelements maxlength intlast 位置類型 typedefintposition 線性表L LISTL 表示 L elements p L的第p個(gè)元素L lastL的長(zhǎng)度 最后元素的位置 3 2 2線性表的數(shù)組實(shí)現(xiàn) 操作 voidInsert elementtypex positionp LIST 時(shí)間復(fù)雜性 O n positionLocate elementtypex LISTL positionq for q 1 q L last q if L elements q x return q return L last 1 時(shí)間復(fù)雜性 O n 3 2 2線性表的數(shù)組實(shí)現(xiàn) elementtypeRetrieve positionp LISTL if p L last error 指定元素不存在 elsereturn L elements p 時(shí)間復(fù)雜性 O 1 voidDelete positionp LIST 時(shí)間復(fù)雜性 O n 3 2 2線性表的數(shù)組實(shí)現(xiàn) positionPrevious positionp LISTL if pL last error 前驅(qū)元素不存在 elsereturn p 1 時(shí)間復(fù)雜性 O 1 positionEnd LISTL return L last 1 O 1 positionFirst LISTL return 1 復(fù)雜性 O 1 positionNext positionp LISTL if p L last error 前驅(qū)元素不存在 elsereturn p 1 時(shí)間復(fù)雜性 O 1 positionMakeNull LIST 時(shí)間復(fù)雜性 O 1 3 2 2線性表的數(shù)組實(shí)現(xiàn) 3 2 3線性表的指針實(shí)現(xiàn) 單鏈表 一個(gè)線性表由若干個(gè)結(jié)點(diǎn)組成 每個(gè)結(jié)點(diǎn)均含有兩個(gè)域 存放元素的信息域和存放其后繼結(jié)點(diǎn)的指針域 這樣就形成一個(gè)單向鏈接式存儲(chǔ)結(jié)構(gòu) 簡(jiǎn)稱單向鏈表或單向線性鏈表 結(jié)構(gòu)特點(diǎn) 邏輯次序和物理次序不一定相同 元素之間的邏輯關(guān)系用指針表示 需要額外空間存儲(chǔ)元素之間的關(guān)系 非隨機(jī)存儲(chǔ)結(jié)構(gòu) 3 2 3線性表的指針實(shí)現(xiàn) 操作討論 3 2 3線性表的指針實(shí)現(xiàn) 插入元素 p a 表頭插入元素 b 中間插入元素 c 表尾插入元素 q newcelltype q element x q next p next p next q 或 temp p next p next newcelltype p next element x p next next temp 討論表頭結(jié)點(diǎn)的作用 操作討論 3 2 3線性表的指針實(shí)現(xiàn) 刪除元素 q p next p next q next deleteq 或 q p next p next p next next deleteq 討論結(jié)點(diǎn)ai的位置p 操作 3 2 3線性表的指針實(shí)現(xiàn) positionEnd LISTL positionq q L while q next NULL q q next return q 時(shí)間復(fù)雜性 O n voidInsert elementtypex positionp positionq q newcelltype q element x q next p next p next q 時(shí)間復(fù)雜性 O 1 操作 3 2 3線性表的指針實(shí)現(xiàn) positionLocate elementtypex LISTL positionp p L while p next NULL if p next element x returnp elsep p next returnp 時(shí)間復(fù)雜性 O n elementtypeRetrieve positionp return p next element 時(shí)間復(fù)雜性 O 1 操作 3 2 3線性表的指針實(shí)現(xiàn) voidDelete positionp positionq if p next NULL q p next p next q next deleteq 時(shí)間復(fù)雜性 O 1 positionPrevious positionp positionq if p L next error 不存在前驅(qū)元素 else q L while q next p q q next returnq 時(shí)間復(fù)雜性 O n 操作 3 2 3線性表的指針實(shí)現(xiàn) positionNext positionp positionq if p next NULL error 不存在后繼元素 else q p next returnq 時(shí)間復(fù)雜性 O 1 positionMakeNull LIST 時(shí)間復(fù)雜性 O 1 操作 3 2 3線性表的指針實(shí)現(xiàn) positionFirst LISTL returnL 時(shí)間復(fù)雜性 O 1 靜態(tài)鏈表與動(dòng)態(tài)鏈表的比較 比較參數(shù) 表的容量 存取操作 時(shí)間 空間 鏈?zhǔn)酱鎯?chǔ)靈活 易擴(kuò)充順序存取訪問元素費(fèi)時(shí)間實(shí)際長(zhǎng)度 節(jié)省空間 順序存儲(chǔ)固定 不易擴(kuò)充隨機(jī)存取插入刪除費(fèi)時(shí)間估算表長(zhǎng)度 浪費(fèi)空間 舉例 遍歷線性鏈表 按照線性表中元素的順序 依次訪問表中的每一個(gè)元素 每個(gè)元素只能被訪問一次 voidTravel LISTL positionp p L next while p NULL cout p element p p next 單鏈表逆置問題 方法一 設(shè)表頭為L(zhǎng) 算法如下 p L next next q p next L next next NULL while p null p next L next L next p p q q q next 方法二 線性表由q來表示p null w q while w null w w next q next p p q q w 3 2 5雙向鏈表 雙向連表 在單向鏈表中 對(duì)每個(gè)結(jié)點(diǎn)增加一個(gè)域 用一指向該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn) 線性表的這種存儲(chǔ)結(jié)構(gòu)稱為雙向鏈表 優(yōu)點(diǎn) 實(shí)現(xiàn)雙向查找 單鏈表不易做到 表中的位置i可以用指示含有第i個(gè)結(jié)點(diǎn)的指針表示 缺點(diǎn) 空間開銷大 3 2 5雙向鏈表 操作 刪除位置p的元素 voidDelete positionp DLIST voidInsert elementtypex positionp DLIST 3 2 6環(huán)形鏈表 對(duì)線性鏈表的改進(jìn) 解決 單向操作 的問題 改進(jìn)后的鏈表 能夠從任意位置元素開始 訪問表中的每一個(gè)元素 單向環(huán)形鏈表 在 不帶表頭結(jié)點(diǎn) 的單向鏈表中 使末尾結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn) 得到一個(gè)環(huán)形結(jié)構(gòu) 用指向末尾結(jié)點(diǎn)的指針標(biāo)識(shí)這個(gè)表 存儲(chǔ)結(jié)構(gòu) 與單向鏈表相同 略 操作 在表左端插入結(jié)點(diǎn)Insert x FIRST R R LInsert x R voidLInsert elementtypex LIST 3 2 6環(huán)形鏈表 在表右端插入結(jié)點(diǎn)Insert x END R R RInsert x R voidRInsert elementtypex LISTR LInsert x R R R next 操作 從表左端刪除結(jié)點(diǎn)Delete First R R LDelete R voidLDelete LIST 3 2 6環(huán)形鏈表 3 2 6環(huán)形鏈表 雙向環(huán)形鏈表的結(jié)構(gòu)與雙向連表結(jié)構(gòu)相同 只是將表頭元素的空previous域指向表尾 同時(shí)將表尾的空next域指向表頭結(jié)點(diǎn) 從而形成向前和向后的兩個(gè)環(huán)形鏈表 對(duì)鏈表的操作變得更加靈活 舉例 設(shè)計(jì)算法 將一個(gè)單向環(huán)形鏈表反向 頭元素變成尾元素 尾元素變成新的頭元素 依次類推 3 2 6環(huán)形鏈表 3 3棧 Stack 棧是線性表的一種特殊形式 是一種限定性數(shù)據(jù)結(jié)構(gòu) 也就是在對(duì)線性表的操作加以限制后 形成的一種新的數(shù)據(jù)結(jié)構(gòu) 定義 是限定只在表尾進(jìn)行插入和刪除操作的線性表 棧又稱為后進(jìn)先出 LastInFirstOut 的線性表 簡(jiǎn)稱LIFO結(jié)構(gòu) 棧舉例 3 3棧 棧的基本 MakeNull S 操作 Top S Pop S Push x S Empty S 舉例 利用棧實(shí)現(xiàn)行編輯處理 設(shè)定符號(hào) 為擦訖符 用以刪除 前的字符 符號(hào) 為刪行符 用以刪除當(dāng)前編輯行 原理 一般字符進(jìn)棧 讀字符擦訖符退棧 刪行符則清棧 3 3 1棧的實(shí)現(xiàn) 3 3棧 1 順序存儲(chǔ) 順序棧示意圖 top 類型定義 enumBoolen TRUE FALSE typedefstruct elementtypeelements maxlength inttop STACK STACKS 棧的容量 maxlength 1 棧空 S top 0 棧滿 S top maxlength 1 棧頂元素 S elements S top 3 3 1棧的實(shí)現(xiàn) 1 順序存儲(chǔ) 操作 voidMakeNull STACK BooleanEmpty STACKS if S top 1 returnTRUEelsereturnFALSE elementtypeTop STACKS ifEmpty S returnNULL elsereturn S elements S top 3 3 1棧的實(shí)現(xiàn) 1 順序存儲(chǔ) 操作 voidPop STACK voidPush elementtypex STACK 3 3 1棧的實(shí)現(xiàn) 2 鏈?zhǔn)酱鎯?chǔ) 采用由指針形成的線性鏈表來實(shí)現(xiàn)棧的存儲(chǔ) 要考慮鏈表的哪一端實(shí)現(xiàn)元素的插入和刪除比較方便 實(shí)現(xiàn)的方式如右圖所示 其操作與線性鏈表的表頭插入和刪除元素相同 structnode Elementtypeval node next typedefnode STACK voidMakeNull STACK voidPop STACK booleanEmpty STACKS if S next returnFALSE elsereturnTRUE 多個(gè)棧共用一個(gè)存儲(chǔ)空間的討論 3 4排隊(duì)或隊(duì)列 Queue 隊(duì)列是對(duì)線性表的插入和刪除操作加以限定的另一種限定性數(shù)據(jù)結(jié)構(gòu) 定義 將線性表的插入和刪除操作分別限制在表的兩端進(jìn)行 和棧相反 隊(duì)列是一種先進(jìn)先出 FirstInFirstOut 簡(jiǎn)稱FIFO結(jié)構(gòu) 的線性表 操作 MakeNull Q Front Q EnQueue x Q DeQueue Q Empty Q 3 4隊(duì)列 Queue 3 4 1隊(duì)列的指針實(shí)現(xiàn) 元素的 型 structcelltype elementtypeelement celltype next 隊(duì)列的 型 structQUEUE celltype front celltype rear 3 4 1隊(duì)列的指針實(shí)現(xiàn) 操作 voidMakeNull QUEUE BooleanEmpty Q QUEUE elementtypeFront Q QUEUEQ returnQ front next element 3 4 1隊(duì)列的指針實(shí)現(xiàn) voidEnQueue elementtypex QUEUE voidDelete QUEUE 3 4 2隊(duì)列的數(shù)組實(shí)現(xiàn) 隊(duì)列的 型 structQUEUE elementtypeelement maxlength intfront intrear 隨著不斷有元素出隊(duì)和進(jìn)隊(duì) 插入和刪除 隊(duì)列的狀態(tài)由1變成2 此時(shí)an占據(jù)隊(duì)列的最后一個(gè)位置 第n 1個(gè)元素?zé)o法進(jìn)隊(duì) 但實(shí)際上 前面部分位置空閑 3 4 2隊(duì)列的數(shù)組實(shí)現(xiàn) 解決假溢出的方法有多種 一是通過不斷移動(dòng)元素位置 每當(dāng)有元素出隊(duì)列時(shí) 后面的元素前移一個(gè)位置 使隊(duì)頭元素始終占據(jù)隊(duì)列的第一個(gè)位置 第二種方法是采用循環(huán)隊(duì)列 插入元素 Q rear Q rear 1 maxlength刪除元素 Q front Q front 1 maxlength 隊(duì)空 Q rear 1 maxlength Q front隊(duì)滿 Q rear 1 maxlength Q front 3 4 2隊(duì)列的數(shù)組實(shí)現(xiàn) 問題 如何解決循環(huán)隊(duì)列中隊(duì)空與隊(duì)滿狀態(tài)相同 方法一 約定隊(duì)列頭指針在隊(duì)列尾指針的下一位置上 方法二 另設(shè)一個(gè)標(biāo)志位用以區(qū)別隊(duì)空與隊(duì)滿兩種狀態(tài) 結(jié)論 兩種方法的代價(jià)是相同的 操作 intaddone inti return i 1 maxlength voidMakeNull QUEUE booleanEmpty Q QUEUEQ if addone Q rear Q front returnTRUE elsereturnFALSE 3 4 2隊(duì)列的數(shù)組實(shí)現(xiàn) 操作 elementtypeFront QUEUEQ if Empty Q returnNULL elsereturn Q elements Q front voidEnQueue elementtypex QUEUEQ if addone addone Q rear Q front error 隊(duì)列滿 else Q rear addone Q rear Q elements Q rear x 3 4 2隊(duì)列的數(shù)組實(shí)現(xiàn) voidDeQueue QUEUEQ if Empty Q error 空隊(duì)列 elseQ front addone Q front 3 6串 String 串是線性表的一種特殊形式 表中每個(gè)元素的類型為字符型 是一個(gè)有限的字符序列 串的基本形式可表示成 S a1a2a3 an 其中 charai 0 i n n 0 當(dāng)n 0時(shí) 為空串 n為串的長(zhǎng)度 C語(yǔ)言中串有兩種實(shí)現(xiàn)方法 1 字符數(shù)組 如 charstr1 10 2 字符指針 如 char str2 3 6 1抽象數(shù)據(jù)型串 3 6 2串的實(shí)現(xiàn) 1 串的順序存儲(chǔ)采用連續(xù)的存儲(chǔ)空間 數(shù)組 自第一個(gè)元素開始 依次存儲(chǔ)字符串中的每一個(gè)字符 charstr 10 China 操作 NULL ISNULL IN LEN CONCAT SUBSTR INDEX 2 串的鏈?zhǔn)酱鎯?chǔ)構(gòu)造線性鏈表 element類型為char 自第一個(gè)元素開始 依次存儲(chǔ)字符串中的每一個(gè)字符 3 7數(shù)組 ARRAY 3 7 1抽象數(shù)據(jù)型數(shù)組 數(shù)組是由下標(biāo) index 和值 value 組成的序?qū)?index value 的集合 也可以定義為是由相同類型的數(shù)據(jù)元素組成有限序列 數(shù)組在內(nèi)存中是采用一組連續(xù)的地址空間存儲(chǔ)的 正是由于此種原因 才可以實(shí)現(xiàn)下標(biāo)運(yùn)算 所有數(shù)組都是一個(gè)一維向量 數(shù)組1 a1 a2 a3 ai an 數(shù)組2 a11 a1n a21 a2n aij am1 amn 1 i m 1 j n 數(shù)組3 a111 a11n a121 a12n aijk amn1 amnp 1 i m 1 j n 1 k p 3 7 2數(shù)組的實(shí)現(xiàn) 1 數(shù)組的順序存儲(chǔ) 數(shù)組的順序表示 指的是在計(jì)算機(jī)中 用一組連續(xù)的存儲(chǔ)單元來實(shí)現(xiàn)數(shù)組的存儲(chǔ) 目前的高級(jí)程序設(shè)計(jì)語(yǔ)言都是這樣實(shí)現(xiàn)的 兩種存儲(chǔ)方式 一是按行存儲(chǔ) C語(yǔ)言 PASCAL等 二是按列存儲(chǔ) FORTRAN等 elementtypeA 2 3 1 數(shù)組的順序存儲(chǔ) 對(duì)二維數(shù)組有 LOC A i j LOC A 0 0 n i j 0 i m 1 0 j n 1對(duì)三維數(shù)組有 LOC A i1 i2 i3 LOC A 0 0 0 d2 d3 i1 d3 i2 i3 0 i1 d1 1 0 i2 d2 1 0 i3 d3 1 2 數(shù)組的壓縮存儲(chǔ) 特殊矩陣若n階矩陣A中的元素滿足下述性質(zhì)aij aji1 i j n則稱n階對(duì)稱陣 對(duì)于對(duì)稱矩陣 為實(shí)現(xiàn)節(jié)約存儲(chǔ)空間 我們可以為每一對(duì)對(duì)稱元素分配一個(gè)存儲(chǔ)空間 這樣 原來需要的n2個(gè)元素壓縮存儲(chǔ)到n n 1 2個(gè)元素空間 對(duì)稱關(guān)系 設(shè)sa 0 n n 1 2 做為n階對(duì)稱陣A的存儲(chǔ)結(jié)構(gòu) 則Sa k 和aij的一一對(duì)應(yīng)關(guān)系為 i i 1 2 j當(dāng)i jk j j 1 2 i當(dāng)i j 2 稀疏矩陣 稀疏矩陣中 零元素的個(gè)數(shù)遠(yuǎn)遠(yuǎn)多于非零元素的個(gè)數(shù) 為實(shí)現(xiàn)壓縮存儲(chǔ) 仍考慮只存儲(chǔ)非零元素 第4章樹 1 一個(gè)結(jié)點(diǎn)x組成的集 x 是一株樹 這個(gè)結(jié)點(diǎn)x也是這株樹的根 2 假設(shè)x是一個(gè)結(jié)點(diǎn) T1 T2 Tk是k株互不相交的樹 我們可以構(gòu)造一株新樹 令x為根 并有k條邊由x指向樹T1 T2 Tk 這些邊也叫做分支 T1 T2 Tk稱作根x的樹之子樹 SubTree 樹的構(gòu)造性遞歸定義 遞歸定義 但不會(huì)產(chǎn)生循環(huán)定義 一株樹的每個(gè)結(jié)點(diǎn)都是這株樹的某株子樹的根 注意 樹的邏輯結(jié)構(gòu)特點(diǎn) 除根結(jié)點(diǎn)之外 每株子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū) 但可以有0個(gè)或多個(gè)直接后繼 即一對(duì)多的關(guān)系 反映了結(jié)點(diǎn)之間的層次關(guān)系 結(jié)點(diǎn)的度 元結(jié)點(diǎn)的度 元 和樹的度葉結(jié)點(diǎn) 終端結(jié)點(diǎn) 非終端結(jié)點(diǎn) 分支結(jié)點(diǎn) 子結(jié)點(diǎn) 兒子 子女 父結(jié)點(diǎn) 雙親 兄弟 結(jié)點(diǎn) 和樹的高 路 徑 長(zhǎng)祖先 結(jié)點(diǎn) 后代 子孫 結(jié)點(diǎn)層 結(jié)點(diǎn)的高路 路徑 有序樹無序樹森林 森林forest 是n 0株互不相交的樹的集合 二叉樹 一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集合 該集合或者為空 或者是由一個(gè)根結(jié)點(diǎn)和兩棵分別稱為左子樹和右子樹的 互不相交的二叉樹組成 結(jié)構(gòu)特點(diǎn) 每個(gè)結(jié)點(diǎn)最多只有兩個(gè)孩子結(jié)點(diǎn) 即結(jié)點(diǎn)的度不大于2 子樹有左右之別 子樹的次序 位置 不能顛倒 基本形態(tài) 4 2 1二叉樹的定義及遍歷 高度為K且有2K 1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹 設(shè)二叉樹高度為K 稱滿足下列性質(zhì)的二叉樹為完全二叉樹 1 所有的葉都出現(xiàn)在K或K 1層 2 K 1層的所有葉都在非終結(jié)結(jié)點(diǎn)的右邊 3 除了K 1層的最右非終結(jié)結(jié)點(diǎn)可能有一個(gè) 只能是左分支 或兩個(gè)分支之外 其余非終結(jié)結(jié)點(diǎn)都有兩個(gè)分支 二叉樹的遍歷 根據(jù)某種策略 按照一定的順序訪問二叉樹中的每一個(gè)結(jié)點(diǎn) 使每個(gè)結(jié)點(diǎn)被訪問一次且只被訪問一次 結(jié)果得到二叉樹結(jié)點(diǎn)的線性序列 根 D 左孩子 L 和右孩子 R 三個(gè)結(jié)點(diǎn)可能出現(xiàn)的順序有 DLR LDR LRD DRL RDL RLD 要討論的三種操作分別為 先根順序DLR 中根順序LDR 后根順序LRD 策略 左孩子結(jié)點(diǎn)一定要在右孩子結(jié)點(diǎn)之前訪問 先根順序遍歷二叉樹 若二叉樹非空則 訪問根結(jié)點(diǎn) 先根順序遍歷左子樹 先根順序遍歷右子樹 中根順序遍歷二叉樹 若二叉樹非空則 中根順序遍歷左子樹 訪問根結(jié)點(diǎn) 中根順序遍歷右子樹 后根順序遍歷二叉樹 若二叉樹非空則 后根順序遍歷左子樹 后根順序遍歷右子樹 訪問根結(jié)點(diǎn) 所得到的線性序列分別稱為先根 序 中根 序 和后根 序 序列 如圖所示的二叉樹 對(duì)其進(jìn)行先序 中序和后序遍歷都是從根結(jié)點(diǎn)A開始的 且在遍歷過程中經(jīng)過結(jié)點(diǎn)的路線是一樣的 只是訪問的時(shí)機(jī)不同而已 性質(zhì)1二叉樹的第i層最多有2i 1個(gè)結(jié)點(diǎn) i 1 證明用數(shù)學(xué)歸納法 性質(zhì)2高度為K的二叉樹最多有2K 1個(gè)結(jié)點(diǎn) K 1 證明用求等比級(jí)數(shù)前K項(xiàng)和的公式 20 21 22 2K 2K 1性質(zhì)3對(duì)任何一棵二叉樹 如果其葉結(jié)點(diǎn)有n0個(gè) 度為2的非葉結(jié)點(diǎn)有n2個(gè) 則有n0 n2 1證明 若設(shè)度為1的結(jié)點(diǎn)有n1個(gè) 結(jié)點(diǎn)總數(shù)為n 分支總數(shù)為B 則根據(jù)二叉樹的定義 n n0 n1 n2B 2n2 n1 n 1因此 有2n2 n1 n0 n1 n2 1n2 n0 1n0 n2 1 4 2 2二叉樹的性質(zhì) 性質(zhì)4具有n n 0 個(gè)結(jié)點(diǎn)的完全二叉樹的高度為 log2 n 1 或 log2n 1證明 設(shè)完全二叉樹的高度為K 則有2K 1 1 n 2K 1變形2K 1 n 1 2K2K 1 n 2K取對(duì)數(shù)K 1 log2 n 1 KK 1 log2n K因此有 log2 n 1 KK log2n 1 性質(zhì)5完全 或滿 二叉樹的順序存儲(chǔ)結(jié)構(gòu)及其性質(zhì)如果將一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹自頂向下 同一層自左向右連續(xù)給結(jié)點(diǎn)編號(hào) 1 2 n 且使該編號(hào)對(duì)應(yīng)于數(shù)組的下標(biāo) 則有以下關(guān)系 若i 1 則i是根結(jié)點(diǎn) 無父結(jié)點(diǎn)若i 1 則i的父結(jié)點(diǎn)為 i 2 若2 i n 則i有左兒子且為2 i 否則 i無左兒子 若2 i 1 n 則i有右兒子且為2 i 1 否則 i無右兒子 若i為偶數(shù) 且i n 則有右兄弟 且為i 1 若i為奇數(shù) 且i n i 1 則其左兄弟 且為i 1 voidPreorder BT BTREEBT if IsEmpty BT visit DATA BT Preorder LCHILD BT Preorder RCHILD BT 例1 1 寫一個(gè)遞歸函數(shù) 按先根順序列出二叉樹中每個(gè)結(jié)點(diǎn)的DATA域之值 例1 2 寫一個(gè)遞歸函數(shù) 按中根順序列出二叉樹中每個(gè)結(jié)點(diǎn)的DATA域之值 voidInorder BT BTREEBT if IsEmpty BT Inorder LCHILD BT visit DATA BT Inorder RCHILD BT 例1 3 寫一個(gè)遞歸函數(shù) 按后根順序列出二叉樹中每個(gè)結(jié)點(diǎn)的DATA域之值 voidPostorder BT BTREEBT if IsEmpty BT Postorder LCHILD BT Postorder RCHILD BT visit DATA BT 二元樹的遍歷的非遞歸過程 voidNInorder BT BTREEBT STACKS BTREET MakeNull S T BT while IsEmpty T Empty S if IsEmpty T Push T S T T LCHILD T else T Top S Pop S visit DATA T T T RCHILD T 進(jìn)棧 左走一步 退棧 右走一步 一 順序表示1 完全 或滿 二叉樹 根據(jù)性質(zhì)5 如已知某結(jié)點(diǎn)的層序編號(hào)i 則可求得該結(jié)點(diǎn)的雙親結(jié)點(diǎn) 左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn) 采用一維數(shù)組 按層序順序依次存儲(chǔ)二叉樹的每一個(gè)結(jié)點(diǎn) 如下圖所示 4 2 4二叉樹的表示 二 左右鏈表示 structnode structnode lchild structnode rchild datatypedata typedefstructnode BTREE 三 二叉樹的線索表示 線索二叉樹 若結(jié)點(diǎn)p有左孩子 則p lchild指向其左孩子結(jié)點(diǎn) 否則令其指向其 先序 中序 后序 前驅(qū) 若結(jié)點(diǎn)p有右孩子 則p rchild指向其右孩子結(jié)點(diǎn) 否則令其指向其 先序 中序 后序 后繼 同時(shí)在每個(gè)結(jié)點(diǎn)中增加兩個(gè)標(biāo)志位 以區(qū)分該結(jié)點(diǎn)的的兩個(gè)鏈域是指向其左 右孩子還是指向某種遍歷的前驅(qū) 后繼 structnode datatypedata structnode lchild rchild enumboollchild rchild typdefstructnode THTREE p ltag TRUEp lchild指向左孩子FALSEp lchild指向 中序 前驅(qū) 算法 求 p 中序前驅(qū) 分析 1 當(dāng)p ltag FALSE時(shí) p lchild即為所求 線索 2 當(dāng)p ltag TRUE時(shí) p為p的左子樹的最右結(jié)點(diǎn) THTREEInPre THTREEp THTREEQ Q p lchild if p ltag TRUE while Q rtag TRUE Q Q rchild return Q voidPreOrder BTREET STACKS Makenull S 遞歸工作棧structnode p T while p NULL coutdatarchild NULL Push S p rchild if p lchild NULL p p lchild 進(jìn)左子樹else p Top S Pop S 左子樹空 訪問右子樹 例先序遍歷的非遞歸算法 棧頂保存當(dāng)前結(jié)點(diǎn)的右子樹 voidPreorder BTREEbt STACKS BTREEt t bt Makenull S while t null Empty S whlie t null visit t data push t S t t lc if Empty S t top S pop S t t rc 例先序遍歷的非遞歸算法 棧頂保存當(dāng)前結(jié)點(diǎn)的左子樹 4 3 1樹的三種遍歷 先根順序 訪問根結(jié)點(diǎn) 先根順序遍歷T1 先根順序遍歷T2 先根順序遍歷Tk 中根順序中根順序遍歷T1 訪問根結(jié)點(diǎn) 中根順序遍歷T2 中根順序遍歷Tk 后根順序后根順序遍歷T1 后根順序遍歷T2 后根順序遍歷Tk 訪問根結(jié)點(diǎn) 先根遍歷序列 RADEBCFGHK中根遍歷序列 DAERBGFHKC后根遍歷序列 DEABGHKFCR D A E R B C F G H K 4 3 2樹的存儲(chǔ)結(jié)構(gòu) 1 樹的數(shù)組表示法 雙親表示 父鏈表示 單鏈表示 首先 對(duì)樹T的結(jié)點(diǎn)按下列規(guī)則依次編號(hào) 根結(jié)點(diǎn)編號(hào)為1 對(duì)于T中的每一個(gè)已編號(hào)的結(jié)點(diǎn)k 按從左到右的順序?qū)的兒子結(jié)點(diǎn)編號(hào) 然后 令樹T的結(jié)點(diǎn)編號(hào)與一個(gè)結(jié)構(gòu)體數(shù)組的下標(biāo)對(duì)應(yīng) 結(jié)構(gòu)體數(shù)組的每個(gè)單元包括兩個(gè)域 parent和data域 且規(guī)定 A i data 結(jié)點(diǎn)i的數(shù)據(jù)域的值 父鏈表示 structnode intparent chardata typedefnodeTREE 11 TREET 存儲(chǔ)結(jié)構(gòu) 基本操作的實(shí)現(xiàn) 結(jié)構(gòu)特點(diǎn) 每個(gè)結(jié)點(diǎn)均保存父結(jié)點(diǎn)所在的數(shù)組單元下標(biāo)兄弟結(jié)點(diǎn)的編號(hào)連續(xù) 易求父結(jié)點(diǎn) 祖先結(jié)點(diǎn) 如i的父結(jié)點(diǎn)的父結(jié)點(diǎn)T T i parent parent易求結(jié)點(diǎn)數(shù)據(jù)域的值 T i data不便于CREATEk操作 2 樹的鄰接表表示法 孩子表示法 孩子鏈表表示法 typedefstructCTNode intchild structCTNode next ChildPtr typedefstruct Telementtypedata ChildPtrfirstchild CTBox typedefstruct CTBoxnodes MAX TREE SIZE intn r Ctree 1 結(jié)點(diǎn)結(jié)構(gòu) 2 存貯示例 因每個(gè)結(jié)點(diǎn)有且僅有兩個(gè)指針域 所以也稱為二叉樹表示方法 3 樹的 左 孩子 右 兄弟表示法 二叉樹表示法 類型 typedefstructCSNode 動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)ElemTypedata structCSNode firstchild nextsibling typedefstructCSNode TREE 森林 樹 轉(zhuǎn)換為二元樹 連線 把每株樹的各兄弟結(jié)點(diǎn)連起來 把各株樹的根結(jié)點(diǎn)連起來 視為兄弟 抹線 對(duì)于每個(gè)結(jié)點(diǎn) 只保留與其最左兒子的連線 抹去該結(jié)點(diǎn)與其它結(jié)點(diǎn)之間的連線旋轉(zhuǎn) 按順時(shí)針旋轉(zhuǎn)45度角 左鏈豎畫 右鏈橫畫 4 5樹的應(yīng)用 沒有度數(shù)為1的結(jié)點(diǎn)外結(jié)點(diǎn)數(shù) 內(nèi)結(jié)點(diǎn)數(shù) 1 為什么 有n個(gè)外結(jié)點(diǎn)的擴(kuò)充二元樹共有2n 1個(gè)結(jié)點(diǎn) 4 5 3哈夫曼 Huffman 樹及其應(yīng)用 在二叉樹中 對(duì)于每個(gè)結(jié)點(diǎn) 若出現(xiàn)空 左 右 子樹 則為其加上一個(gè)特殊的結(jié)點(diǎn) 稱為外結(jié)點(diǎn) 由此得到的新二叉樹稱為原二叉樹的擴(kuò)充二叉樹 而原二叉樹的結(jié)點(diǎn)稱為內(nèi)結(jié)點(diǎn) 一 哈夫曼樹的由來及其構(gòu)造 內(nèi)路徑長(zhǎng)I 2 1 3 2 1 3 11外路徑長(zhǎng)E 1 2 5 3 2 4 25 2 擴(kuò)充二元樹的外路徑長(zhǎng) 內(nèi)路徑長(zhǎng)及相互關(guān)系 外路徑長(zhǎng)E 從根結(jié)點(diǎn)到每個(gè)外結(jié)點(diǎn)的路徑長(zhǎng)之和 E lj內(nèi)路徑長(zhǎng)I 從根結(jié)點(diǎn)到每個(gè)內(nèi)結(jié)點(diǎn)的路徑長(zhǎng)之和關(guān)系 E I 2 n n為內(nèi)結(jié)點(diǎn)的個(gè)數(shù) 4 5 3哈夫曼 Huffman 樹及其應(yīng)用 設(shè) wi 2 3 4 11 求 wj lj 加權(quán)路長(zhǎng) a 11 1 4 2 2 3 3 3 34 b 2 1 3 2 4 3 11 3 53 c 2 2 11 2 3 2 4 2 40 3 擴(kuò)充二元樹的加權(quán)路徑長(zhǎng) 外結(jié)點(diǎn)的加權(quán)路徑長(zhǎng) 設(shè)每個(gè)外結(jié)點(diǎn)j對(duì)應(yīng)一個(gè)實(shí)數(shù)wj 稱為外結(jié)點(diǎn)的權(quán)值 lj是從根到外結(jié)點(diǎn)j的路長(zhǎng) 則wj lj個(gè)稱為外結(jié)點(diǎn)j的加權(quán)路長(zhǎng) 擴(kuò)充二元樹的加權(quán)路長(zhǎng) WPL wj lj稱為擴(kuò)充二元樹的加權(quán)路長(zhǎng) 4 5 3哈夫曼 Huffman 樹及其應(yīng)用 哈夫曼樹定義 在給定權(quán)值為w1 w2 wn的n個(gè)葉結(jié)點(diǎn)所構(gòu)成的所有擴(kuò)充二叉樹中 WPL wj lj最小的稱為huffman樹 在哈夫曼樹中 權(quán)值越小 離根越遠(yuǎn) 權(quán)值大的結(jié)點(diǎn)離根最近 構(gòu)造算法 1 由給定的n個(gè)權(quán)值 w0 w1 w2 wn 1 構(gòu)造具有n棵擴(kuò)充二叉樹的森林F T0 T1 T2 Tn 1 其中每棵擴(kuò)充二叉樹Ti只有一個(gè)帶權(quán)值wi的根結(jié)點(diǎn) 其左 右子樹均為空 2 重復(fù)以下步驟 直到F中僅剩下一棵二叉樹為止 在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的擴(kuò)充二叉樹 做為左 右子樹構(gòu)造一棵新的二叉樹 且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左 右子樹上根結(jié)點(diǎn)的權(quán)值之和 在F中刪去這兩棵二叉樹 把新的二叉樹加入F 哈夫曼樹 最優(yōu)二叉樹 F 7 5 2 4 F 7 5 6 7 5 2 4 0 初始 1 合并 2 4 F 7 11 7 5 2 4 7 5 2 4 6 6 11 2 合并 5 6 F 18 5 3 合并 7 11 2 7 4 6 11 18 舉例 編碼和譯碼 哈夫曼 Huffman 樹及其應(yīng)用 是指將文件 字符集 中的每個(gè)字符轉(zhuǎn)換為一個(gè)唯一的二進(jìn)制串 編碼 解碼 是指將二進(jìn)制串轉(zhuǎn)換為對(duì)應(yīng)的字符 譯碼 對(duì)于給定的字符集 可能存在多種編碼方案 但應(yīng)選擇最優(yōu)的 3 編碼的前綴性 對(duì)字符集進(jìn)行編碼時(shí) 如果任意一個(gè)字符的編碼都不是其它任何字符編碼的前綴 則稱這種編碼具有前綴性或前綴編碼 前綴編碼 注意 等長(zhǎng)編碼具有前綴性 變長(zhǎng)編碼可能使譯碼產(chǎn)生二義性 即不具有前綴性 如 E 00 T 01 W 0001 則譯碼時(shí)無法確定信息串是ET還是W 最優(yōu)編碼 Huffman編碼 Huffman編碼問題和編碼算法 對(duì)于給定的字符集以及每個(gè)字符出現(xiàn)的概率 使用頻度 求字符集的最優(yōu)的前綴性編碼 Huffman編碼問題 用huffman算法求字符集最優(yōu)編碼的算法 使字符集中的每個(gè)字符對(duì)應(yīng)一株只有葉結(jié)點(diǎn)的二叉樹 葉的權(quán)值為對(duì)應(yīng)字符的使用頻率 利用huffman算法來構(gòu)造一株huffman樹 對(duì)huffman樹上的每個(gè)結(jié)點(diǎn) 左支附以0 右支附以1 或者相反 則從根到葉的路上的0 1序列就是相應(yīng)字符的編碼 Huffman編碼問題和編碼算法 哈夫曼 Huffman 樹及其應(yīng)用 舉例 第5章圖及其相關(guān)算法 圖是由頂點(diǎn)集合 vertex 及頂點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu) Graph V E 其中V x x 某個(gè)數(shù)據(jù)對(duì)象 是頂點(diǎn)的有窮非空集合 E x y x y V 或E x y V 是頂點(diǎn)之間關(guān)系的有窮集合 也叫做邊 edge 集合 有向圖若圖G的每條邊都有方向 則稱G為有向圖 Digraph 在有向圖中 有向邊 也稱弧 都是頂點(diǎn)的有序?qū)?無向圖若圖G的每條邊都是沒有方向的 則稱G為無向圖 UnDigraph 在無向圖中 每條邊都是頂點(diǎn)的無序?qū)?x y 定義圖 5 1圖的基本概念 無向圖中頂點(diǎn)v的度 Degree 是關(guān)聯(lián)于該頂點(diǎn)的邊的數(shù)目 或與該頂點(diǎn)相鄰的頂點(diǎn)數(shù)目 記為D v 若G是有向圖 則把鄰接到頂點(diǎn)v的頂點(diǎn)數(shù)目或邊數(shù)目稱為頂點(diǎn)v的入度 Indegree 記為ID v 把鄰接于頂點(diǎn)v的頂點(diǎn)數(shù)目或邊數(shù)目稱為頂點(diǎn)v的出度 Outdegree 記為OD v 頂點(diǎn)v的度則定義為該頂點(diǎn)的入度和出度之和 即D v ID v OD v 無論是有向圖還是無向圖 頂點(diǎn)數(shù)n 邊數(shù)e和度數(shù)之間的關(guān)系為 定義結(jié)點(diǎn)的度 在無向圖G中 若存在一個(gè)頂點(diǎn)序列vp vi1 vi2 vim vq 使得 vp vi1 vi1 vi2 vim vq E G 則稱頂點(diǎn)vp路到vq有一條路徑 Path 在有向圖G中 若存在一個(gè)頂點(diǎn)序列vp vi1 vi2 vim vq 使得有向邊 E G 則稱頂點(diǎn)vp路到vq有一條有向路徑 Path 非帶權(quán)圖的路徑長(zhǎng)度是指此路徑上邊的條數(shù) 帶權(quán)圖的路徑長(zhǎng)度是指路徑上各邊的權(quán)之和 簡(jiǎn)單路徑若路徑上各頂點(diǎn)v1 v2 vm均不互相同 則稱這樣的路徑為簡(jiǎn)單路徑 簡(jiǎn)單回路若路徑上第一個(gè)頂點(diǎn)v1與最后一個(gè)頂點(diǎn)vm重合 則稱這樣的簡(jiǎn)單路徑為回路或環(huán) 定義路 徑 路徑長(zhǎng) 簡(jiǎn)單路 簡(jiǎn)單環(huán)路 連通圖與連通分量在無向圖中 若從頂點(diǎn)vi到頂點(diǎn)vj有路徑 則稱頂點(diǎn)vi與vj是連通的 如果圖中任意一對(duì)頂點(diǎn)都是連通的 則稱此圖是連通圖 非連通圖的極大連通子圖叫做連通分量 強(qiáng)連通圖與強(qiáng)連通分量在有向圖中 若對(duì)于每一對(duì)頂點(diǎn)vi和vj 都存在一條從vi到vj和從vj到vi的路徑 則稱此圖是強(qiáng)連通圖 非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量 定義圖的連通性 5 1圖的基本概念 5 2 1鄰接矩陣 AdjacencyMatrix 一 圖的鄰接矩陣表示 5 2圖的存儲(chǔ)表示 在圖的鄰接矩陣表示中 有一個(gè)記錄各個(gè)頂點(diǎn)信息的頂點(diǎn)表 還有一個(gè)表示各個(gè)頂點(diǎn)之間關(guān)系的鄰接矩陣 設(shè)圖A V E 是一個(gè)有n個(gè)頂點(diǎn)的圖 圖的鄰接矩陣是一個(gè)二維數(shù)組A edge n n 定義 4 1 0 無向圖的鄰接矩陣是對(duì)稱的 有向圖的鄰接矩陣可能是不對(duì)稱的 在有向圖中 統(tǒng)計(jì)第i行1的個(gè)數(shù)可得頂點(diǎn)i的出度 統(tǒng)計(jì)第j列1的個(gè)數(shù)可得頂點(diǎn)j的入度 在無向圖中 統(tǒng)計(jì)第i行 列 1的個(gè)數(shù)可得頂點(diǎn)i的度 二 網(wǎng)絡(luò)的鄰接矩陣 defineMaxValueInt Max 在中 defineNumEdges50 邊條數(shù) defineNumVertices10 頂點(diǎn)個(gè)數(shù)typedefcharVertexData 頂點(diǎn)數(shù)據(jù)類型typedefintEdgeData 邊上權(quán)值類型typedefstruct VertexDatavexlist NumVertices 頂點(diǎn)表EdgeDataedge NumVertices NumVertices 鄰接矩陣 邊表 可視為邊之間的關(guān)系intn e 圖中當(dāng)前的頂點(diǎn)個(gè)數(shù)與邊數(shù) MTGraph voidCreateMGragh MTGragh G 建立 無向 圖的鄰接矩陣 inti j k w scanf d d 空間復(fù)雜性 S O n n2 時(shí)間復(fù)雜性 T O n n2 e 當(dāng)e n T O n2 5 2 2鄰接表 AdjacencyList 一 圖的鄰接表表示 對(duì)于G中的每個(gè)頂點(diǎn)vi 把所有鄰接 于 vi的頂點(diǎn)vj鏈成一個(gè)單鏈表 稱為關(guān)于vi的鄰接表 鄰接表中每個(gè)表結(jié)點(diǎn)都有兩個(gè)域 其一是鄰接點(diǎn)域adjvex 用以存放與vi相鄰頂點(diǎn)的序號(hào) 其二是鏈域next 用來將鄰接表的所有表點(diǎn)鏈在一起 另外若要表示邊上的信息如 權(quán)值 則在表結(jié)點(diǎn)中還應(yīng)增加一個(gè)數(shù)據(jù)域cost 無向圖G1鄰接表 G2的逆鄰接表 有向圖G2鄰接表 在無向圖的鄰接表中 一條邊 Vi Vj 在鄰接表中出現(xiàn)兩次 一次在關(guān)于Vi的鄰接表中 一次在關(guān)于Vj的鄰接表中 關(guān)于頂點(diǎn)Vi的鄰接表的結(jié)點(diǎn)數(shù)目為頂點(diǎn)Vi的度 在有向圖的鄰接表中 一條邊在鄰接表中出只現(xiàn)一次關(guān)于頂點(diǎn)Vi的鄰接表中結(jié)點(diǎn)數(shù)目為頂點(diǎn)Vi的出度 在逆鄰接表中關(guān)于頂點(diǎn)Vi的鄰接表中結(jié)點(diǎn)數(shù)目為頂點(diǎn)Vi的入度 defineNumVertices10 頂點(diǎn)個(gè)數(shù)typedefcharVertexData 頂點(diǎn)數(shù)據(jù)類型typedefintEdgeData 邊上權(quán)值類型typedefstructnode 邊表結(jié)點(diǎn)intadjvex 鄰接點(diǎn)域 下標(biāo) EdgeDatacost 邊上的權(quán)值structnode next 下一邊鏈接指針 EdgeNode typedefstruct 頂點(diǎn)表結(jié)點(diǎn)VertexDatavertex 頂點(diǎn)數(shù)據(jù)域EdgeNode firstedge 邊鏈表頭指針 VertexNode typedefstruct 圖的鄰接表VertexNodevexlist NumVertices intn e 圖中當(dāng)前的頂點(diǎn)個(gè)數(shù)與邊數(shù) AdjGraph 在鄰接矩陣中求邊的數(shù)目e 必須檢查整個(gè)矩陣 所耗時(shí)間是O n2 與邊的個(gè)數(shù)e無關(guān) 而在鄰接表中求邊的數(shù)目e 只要對(duì)每個(gè)邊表的結(jié)點(diǎn)個(gè)數(shù)進(jìn)行計(jì)數(shù)即可求得e 所耗時(shí)間是O e n 因此當(dāng)e是否為圖的一條邊 只要判斷矩陣中的第i行第j列是否為非零元素即可 但在鄰接表中 須掃描第i個(gè)邊表 最壞情況下消耗時(shí)間O n 空間復(fù)雜度 兩種存儲(chǔ)結(jié)構(gòu)的比較 圖的搜索 從圖的某個(gè)頂點(diǎn)出發(fā) 訪遍圖中所有的頂點(diǎn) 且使每個(gè)頂點(diǎn)被訪問一次且僅被訪問一次 稱為圖的搜索 遍歷 GraphTraversal 訪問 有許多方法和策略 不同的 訪問 方法和策略導(dǎo)致不同的搜索算法 因此圖