數據結構知識點總結,有工大老師多年經驗編寫.ppt

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