數(shù)據(jù)結(jié)構知識點總結(jié),有工大老師多年經(jīng)驗編寫.ppt

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