數(shù)據(jù)結(jié)構(gòu)詳解

基本數(shù)據(jù)結(jié)構(gòu)與算法交流數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第1頁。CONTENTS緒論1線性表2棧與隊列3串4樹5圖6排序算法7數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第2頁。1緒論什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的基本概念抽象數(shù)據(jù)類型基本概念算法效率的度量數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第3頁。什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計算機(jī)硬件和計算機(jī)軟件三者之間的一門核心課程關(guān)系對象關(guān)系操作數(shù)學(xué)軟件硬件對象關(guān)系操作數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第4頁。為什么學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)

程序設(shè)計的實(shí)質(zhì)是對實(shí)際問題選擇一種好的數(shù)據(jù)結(jié)構(gòu)，加之設(shè)計一個好的算法，而好的算法在很大程度上取決于描述實(shí)際問題的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第5頁。

算法+數(shù)據(jù)結(jié)構(gòu)=程序6數(shù)據(jù)結(jié)構(gòu)的重要性：結(jié)構(gòu)化編程（代表語言TurboC）：程序=（算法）+（數(shù)據(jù)結(jié)構(gòu)）面向?qū)ο缶幊?代表語言Java、Delphi、c++)：對象=（算法+數(shù)據(jù)結(jié)構(gòu)）

程序=對象+對象程序設(shè)計:為計算機(jī)處理問題編制一組指令集算法:處理問題的策略數(shù)據(jù)結(jié)構(gòu)：問題的數(shù)學(xué)模型數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第6頁。登錄號：書名：作者名：分類號：出版單位：出版時間：價格：書目卡片按書名按作者名按分類號數(shù)據(jù)結(jié)構(gòu)實(shí)際應(yīng)用——索引索引數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第7頁。8樹……..……..…...…...…...…...數(shù)據(jù)結(jié)構(gòu)實(shí)際應(yīng)用——人機(jī)對弈數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第8頁。FBDDAE54798612282數(shù)據(jù)結(jié)構(gòu)實(shí)際應(yīng)用——最短路徑圖C數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第9頁。數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第10頁。數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第11頁。數(shù)據(jù)結(jié)構(gòu)實(shí)際應(yīng)用——HashMap數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第12頁。數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第13頁。抽象數(shù)據(jù)類型基本概念數(shù)據(jù)(data)——所有能被計算機(jī)識別、存儲和處理的符號的集合（包括數(shù)字、字符、聲音、圖像等信息）。數(shù)據(jù)元素(dataelement)——是數(shù)據(jù)的基本單位，具有完整確定的實(shí)際意義(又稱元素、結(jié)點(diǎn)，頂點(diǎn)、記錄等）。數(shù)據(jù)項(xiàng)(Dataitem)——構(gòu)成數(shù)據(jù)元素的項(xiàng)目。是具有獨(dú)立含義的最小標(biāo)識單位（又稱字段、域、屬性等）。數(shù)據(jù)對象（Dataobject）——是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集（如整數(shù)數(shù)據(jù)，字母數(shù)據(jù)等）。三者之間的關(guān)系：數(shù)據(jù)>數(shù)據(jù)元素>數(shù)據(jù)項(xiàng)例：班級通訊錄>個人記錄>姓名、年齡……數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第14頁。數(shù)據(jù)結(jié)構(gòu)涵蓋的內(nèi)容數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第15頁。算法效率的度量Q1.什么是算法？算法的設(shè)計原則？Q2.算法效率的衡量方法與準(zhǔn)則？Q3.算法的存儲空間需求？問題：數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第16頁。程序設(shè)計實(shí)質(zhì)＝好算法＋好結(jié)構(gòu)答：算法是解決某一特定類型問題的有限運(yùn)算序列。是一系列輸入轉(zhuǎn)換為輸出的計算步驟。常用時間復(fù)雜度來衡量Q1.什么是算法？如何評判一個算法的好壞？算法有5個基本特性：算法評價有4個指標(biāo)：有窮性、確定性、可行性、輸入和輸出運(yùn)行時間、占用空間、正確性和簡單性常用空間復(fù)雜度來衡量數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第17頁。Q2算法效率的衡量方法和準(zhǔn)則通常有兩種衡量算法效率的方法:1.事后統(tǒng)計法缺點(diǎn)：1．必須執(zhí)行程序

2．其它因素掩蓋算法本質(zhì)（如計算機(jī)的硬件、軟件等環(huán)境因素，有時掩蓋算法本身優(yōu)劣）數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第18頁。2.事前分析估算法（1）算法選用的策略（2）數(shù)據(jù)的規(guī)模（3）編寫程序的語言（4）編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量（5）計算機(jī)執(zhí)行指令的速度算法執(zhí)行時間相關(guān)的因素：數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第19頁。時間復(fù)雜度的計算O(1)O(n)O(n2)intsum=0,n=100; /*執(zhí)行一次*/sum=(1+n)*n/2; /*執(zhí)行一次*/Printf(“%d”,sum); /*執(zhí)行一次*/intsum=0,n=100; /*執(zhí)行一次*/for(i=1;i<=n;i++){ /*執(zhí)行n+1次*/sum=sum+I; /*執(zhí)行n次*/}printf(“%d”,sum); /*執(zhí)行1次*/intsum=0,n=100; /*執(zhí)行一次*/for(i=1;i<=n;i++){ /*執(zhí)行n+1次*/for(j=1;j<=n;j++){x++; /*執(zhí)行n2次*/sum=sum+x;}}printf(“%d”,sum); /*執(zhí)行1次*/數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第20頁。時間復(fù)雜度的計算推導(dǎo)大O階：1.用常數(shù)1取代運(yùn)行時間中的所有加法常數(shù)2.在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)3.如果最高階項(xiàng)存在且不是1，則去除與這個項(xiàng)目相乘的常數(shù)。得到的結(jié)果就是大O階數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第21頁。2線性表2.1線性表的邏輯結(jié)構(gòu)2.2線性表的順序存儲結(jié)構(gòu)2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第22頁。（a1,a2,…ai-1，ai,ai＋1

，…,an）2.1

線性表的類型定義1.線性表的定義：零或多個數(shù)據(jù)元素的有限序列n=0時稱為數(shù)據(jù)元素線性起點(diǎn)ai的直接前趨ai的直接后繼下標(biāo)，是元素的序號，表示元素在表中的位置n為元素總個數(shù)，即表長空表線性終點(diǎn)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第23頁。線性結(jié)構(gòu)的基本特征:3.除最后元素在外，均有唯一的后繼；4.除第一元素之外，均有唯一的前驅(qū)。在數(shù)據(jù)元素的非空有限集中線性表是一種最簡單的線性結(jié)構(gòu)

1.集合中必存在唯一的一個“第一元素”；2.集合中必存在唯一的一個“最后元素”

；數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第24頁。例1分析26個英文字母組成的英文表

（A,B,C,D,……,Z）姓name性別年齡班級011810205于春梅女18電信016班011810260何仕鵬男18電信017班011810284王爽女18通信011班011810360王亞武男18通信012班：：：

：：例2分析學(xué)生情況登記表數(shù)據(jù)元素都是記錄;元素間關(guān)系是線性數(shù)據(jù)元素都是字母;元素間關(guān)系是線性同一線性表中的元素必定具有相同特性數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第25頁。2.線性表的類型定義數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第26頁。2.2線性表的順序存儲結(jié)構(gòu)2.2.1順序表的表示2.2.2順序表的實(shí)現(xiàn)2.2.3順序表的運(yùn)算效率分析數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第27頁。2.2.1順序表的表示指的是用一段地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素順序存儲定義：順序存儲示意圖：可用數(shù)組來實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第28頁。線性表順序存儲特點(diǎn)：1.

邏輯上相鄰的數(shù)據(jù)元素，其物理上也相鄰；2.

若已知表中首元素在存儲器中的位置，則其他元素存放位置亦可求出設(shè)首元素a1的存放地址為LOC(a1)（稱為首地址），設(shè)每個元素占用存儲空間（地址長度）為C字節(jié)，則表中任一數(shù)據(jù)元素的存放地址為： LOC(ai+1)=LOC(ai)+C

LOC(ai)=LOC(a1)+C*（i-1）

數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第29頁。2.2.2順序表基本操作修改、插入、刪除、查找、排序1)修改通過數(shù)組的下標(biāo)便可訪問某個特定元素并修改。核心語句:

V[i]=x;顯然，順序表修改操作的時間效率是T(n)=O(1)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第30頁。2)插入在線性表的第i個位置前插入一個元素實(shí)現(xiàn)步驟：(n為表長）將第n至第i位的元素向后移動一個位置；將要插入的元素寫到第i個位置；表長加1。數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第31頁。實(shí)現(xiàn)步驟：(n為表長）將第i至第n位的元素向前移動一個位置；表長減1。3)刪除刪除線性表的第i個位置上的元素數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第32頁。2.2.3順序表的運(yùn)算效率分析最好情況：插入在最后一個位置，O(1)最壞情況：插入在第一個位置，O(n)平均情況：平均移動n/2時間復(fù)雜度為O(n)插入時間效率分析:數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第33頁。2.2.3順序表的優(yōu)缺點(diǎn)優(yōu)點(diǎn)無須為表示表中元素之間的邏輯關(guān)系而增加額外的存儲空間可以快速地存取表中任一位置的元素缺點(diǎn)插入和刪除操作需要移動大量元素當(dāng)線性表長度變化較大時，難以確定存儲空間的容量造成存儲空間的“碎片”數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第34頁。2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)2.3.1鏈表的表示2.3.2鏈表的實(shí)現(xiàn){單鏈表，循環(huán)鏈表，雙向鏈表}數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第35頁。特點(diǎn)：邏輯上相鄰，物理上不一定相鄰鏈表中第一個結(jié)點(diǎn)的存儲位置叫頭指針每個存儲結(jié)點(diǎn)都包含兩部分：數(shù)據(jù)域和指針域(鏈域)線性鏈表的最后一個結(jié)點(diǎn)指針為空，通常用NULL或^表示2.3.1鏈表的表示存儲結(jié)構(gòu)：如下圖示意數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第36頁。有時為了方便操作，會在單鏈表的第一個結(jié)點(diǎn)前附設(shè)一個結(jié)點(diǎn)，叫做頭結(jié)點(diǎn)頭結(jié)點(diǎn)數(shù)據(jù)域可不存儲任何信息，也可存儲線性表長度等附加信息數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第37頁。2.3.2鏈表的實(shí)現(xiàn)1.單鏈表2.循環(huán)鏈表3.雙向鏈表數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第38頁。1.單鏈表空鏈表：讀取或修改：數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第39頁。1.單鏈表插入：數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第40頁。1.單鏈表刪除：數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第41頁。1.單鏈表單鏈表和順序存儲結(jié)構(gòu)對比數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第42頁。2.循環(huán)鏈表將單鏈表中斷結(jié)點(diǎn)的指針端由空指針改為指向頭結(jié)點(diǎn)，就使整個單鏈表形成一個環(huán)，這種頭尾相接的單鏈表稱為單循環(huán)鏈表，簡稱循環(huán)鏈表空循環(huán)鏈表：添加、刪除操作與單鏈表對應(yīng)操作相同數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第43頁。3.雙向鏈表單鏈表的每個結(jié)點(diǎn)中，再設(shè)置一個指向其前驅(qū)結(jié)點(diǎn)的指針域，這樣的鏈表簡稱循環(huán)鏈表空雙向鏈表：數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第44頁。3.雙向鏈表插入：刪除：數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第45頁。3.1棧（Stack）3.2隊列（Queue）

3棧和隊列1.基本介紹2.抽象數(shù)據(jù)類型3.順序存儲結(jié)構(gòu)4.鏈?zhǔn)酱鎯Y(jié)構(gòu)1.基本介紹2.抽象數(shù)據(jù)類型3.順序存儲結(jié)構(gòu)4.鏈?zhǔn)酱鎯Y(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第46頁。3.1棧（Stack）1.基本介紹2.抽象數(shù)據(jù)類型3.順序存儲結(jié)構(gòu)4.鏈?zhǔn)酱鎯Y(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第47頁。例如：棧S=(a1,a2,a3,……….,an-1,an

)插入元素到棧頂?shù)牟僮鳎Q為入棧。從棧頂刪除最后一個元素的操作，稱為出棧。an稱為棧頂元素a1稱為棧底元素強(qiáng)調(diào)：插入和刪除都只能在表的一端（棧頂）進(jìn)行！棧是僅在表尾進(jìn)行插入、刪除操作的線性表。表尾(即an端)稱為棧頂/top；表頭(a1端)稱為棧底/base子彈夾就是典型的棧數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第48頁。棧的抽象數(shù)據(jù)類型定義數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第49頁。棧的順序存儲結(jié)構(gòu)棧的順序存儲稱為順序棧，它是利用一組地址連續(xù)的存儲單元存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時附設(shè)一個指針（top）指示當(dāng)前棧頂?shù)奈恢脭?shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第50頁。順序棧的入棧操作——例如用堆棧存放（A，B，C，D）AACBABAtoptoptoptoptop低地址L高地址MBCD數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第51頁。順序棧出棧操作——例如從棧中取出‘B’DCBAtoptopDCABDCBAtopDCBAtop低地址L高地址M數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第52頁。共享?xiàng)Ｋ伎迹簝蓚€相同類型的棧，各自開辟了數(shù)組空間，極有可能第一個棧滿了，而另一個棧還有很多存儲空間，如何解決這個問題？共享?xiàng)＃簩蓚€棧的棧底分別設(shè)置在共享空間的兩端，兩個棧頂向共享空間的中間延伸優(yōu)點(diǎn)：有效利用存儲空間，兩個棧的空間相互調(diào)節(jié)，只有在整個存儲空間被占滿時才會發(fā)生上溢，存取時間復(fù)雜度均為O(1)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第53頁。棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)采用鏈?zhǔn)酱鎯Φ臈７Q為鏈棧。通常采用單鏈表實(shí)現(xiàn)，并規(guī)定所有操作都是在單鏈表的表頭進(jìn)行的優(yōu)點(diǎn)：便于多個棧共享存儲空間，和提高其效率，且不存在棧滿上溢的情況鏈棧的操作與鏈表類似，在此不做詳細(xì)討論對于帶頭結(jié)點(diǎn)和不帶頭結(jié)點(diǎn)的鏈棧，具體的實(shí)現(xiàn)方面有所不同需要注意數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第54頁。3.2隊列（Queue）1.基本介紹2.抽象數(shù)據(jù)類型3.順序存儲結(jié)構(gòu)4.鏈?zhǔn)酱鎯Y(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第55頁。隊列（Queue）是僅在表尾進(jìn)行插入操作，在表頭進(jìn)行刪除操作的線性表。它是一種先進(jìn)先出（ＦＩＦＯ）的線性表。例如：隊列Q=(a1

,a2,a3,……….,an-1,an)在隊尾插入元素稱為入隊；在隊首刪除元素稱為出隊。隊頭隊尾問：為什么要設(shè)計隊列？它有什么獨(dú)特用途？離散事件的模擬（模擬事件發(fā)生的先后順序,例如CPU芯片中的指令譯碼隊列）；操作系統(tǒng)中的作業(yè)調(diào)度（一個CPU執(zhí)行多個作業(yè)）；3.簡化程序設(shè)計。答：數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第56頁。隊列的抽象數(shù)據(jù)類型數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第57頁。隊列的順序存儲結(jié)構(gòu)隊列的順序?qū)崿F(xiàn)是指分配一塊連續(xù)的存儲單元存放隊列中的元素，并附設(shè)兩個指針front和rear，隊頭指針指向隊頭元素，隊尾指針指向隊尾元素的下一個位置。Q(隊尾)(隊首)fronta1a2a3dataa40.......99rear隊尾后地址e數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第58頁。順序隊列的入隊操作：afrontrearrearfrontfrontfrontrearrear空隊5個元素入隊出隊1次出隊3次bcdebcdee數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第59頁。隊列順序存儲結(jié)構(gòu)的不足假溢出！數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第60頁。解決方案：循環(huán)隊列將順序隊列臆造為一個環(huán)狀的空間，即把存儲隊列元素的表從邏輯上看成一個環(huán)，稱為循環(huán)隊列數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第61頁。a3a2a10123N-1rearfront循環(huán)隊列（臆造）新問題：在循環(huán)隊列中，空隊特征是front=rear；隊滿時也會有front=rear；判決條件將出現(xiàn)二義性！解決方案有三：①使用一個計數(shù)器記錄隊列中元素個數(shù)（即隊列長度）；②加設(shè)標(biāo)志位，刪除時置1,插入時置0,則可識別當(dāng)前front=rear屬于何種情況③人為浪費(fèi)一個單元，則隊滿特征可改為front=(rear+1)%N；順序隊列a3a2a1frontrear0123..N-1數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第62頁。隊空條件:front=rear(初始化時：front=rear)隊滿條件：front=(rear+1)%N(N=maxsize)隊列長度（即數(shù)據(jù)元素個數(shù)）：L=（N＋rear－front）%NJ2J3

J1J4

J5frontrear

實(shí)際中常選用方案3（人為浪費(fèi)一個單元）：即front和rear二者之一指向?qū)嵲?，另一個指向空閑元素。

在具有n個單元的循環(huán)隊列中，隊滿時共有N-1個元素左圖中隊列maxsizeN=6左圖中隊列長度L=5數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第63頁。隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)隊列的鏈?zhǔn)奖硎痉Q為鏈隊列，它實(shí)際上是一個同時帶有隊頭指針和隊尾指針的單鏈表空隊列：數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第64頁。隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)入隊：出隊：數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第65頁。串（String）4.1串的基本概念4.2串的比較4.3串的抽象數(shù)據(jù)類型4.4串的存儲結(jié)構(gòu)4.5串的匹配算法數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第66頁。串長：串中字符個數(shù)（n≥0）.n=0時稱為空串?？沾毫銈€字符的串。空白串：由一個或多個空格符組成的串。字串：串s中任意個連續(xù)的字符序列叫s的子串;s叫主串。字串的位置：子串的第一個字符的序號。字符位置：字符在串中的序號。串相等：串長度相等，且對應(yīng)位置上字符相等。

串是由零個或多個字符組成的有限序列，又名叫字符串例如：串S=“a1a2a3……….an-1an

”數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第67頁。4.2串的比較給定兩個串：s=“a1a2……an”,t=“b1b2……bm”,當(dāng)滿足一下條件之一時，s<t。1.n<m，且ai=bi(i=1,2,……，n)例如：s=“hap”,t=“happy”,s<t2.存在某個k<=min(m,n),使得ai=bi(i=1,2,……，k-1),ak<bk例如：s=“happen”,t=“happy”,前四個字母相同，兩串第五個字母，s串‘e’的ASCII碼是101，而字母‘y’的ASCII碼是121，顯然e<y，所以s<t數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第68頁。4.3串的抽象數(shù)據(jù)類型數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第69頁。4.4串的存儲結(jié)構(gòu)定長順序存儲表示——用一組地址連續(xù)的存儲單元存儲串值的字符序列堆分配存儲表示——用一組地址連續(xù)的存儲單元存儲串值的字符序列,但存儲空間是在程序執(zhí)行過程中動態(tài)分配而得。串的塊鏈存儲表示——鏈?zhǔn)椒绞酱鎯κ紫葟?qiáng)調(diào)：串與線性表的運(yùn)算有所不同，是以“串的整體”作為操作對象，例如查找某子串，在主串某位置上插入一個子串等。鏈?zhǔn)酱鎯樞虼鎯?shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第70頁。定長順序存儲：

用一組連續(xù)的存儲單元來存放串，直接使用定長的字符數(shù)組來定義，數(shù)組的上界預(yù)先給出，故稱為靜態(tài)存儲分配。堆分配存儲：

仍用一組連續(xù)的存儲單元來存放串，但存儲空間是在程序執(zhí)行過程中動態(tài)分配而得。數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第71頁。討論：法1存儲密度為

；法2存儲密度為

；顯然，若數(shù)據(jù)元素很多，用法2存儲更優(yōu)—稱為塊鏈結(jié)構(gòu)鏈?zhǔn)酱鎯Γ河面湵泶鎯Υ担撞迦牒蛣h除。法1：鏈表結(jié)點(diǎn)（數(shù)據(jù)域）大小取1法2：鏈表結(jié)點(diǎn)（數(shù)據(jù)域）大小取n(例如n=4)1/29/15=3/5存儲密度=串值所占的存儲位/實(shí)際分配的存儲位A.B.C.INULL……BACD.FEGH.#I##NULL數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第72頁。73算法目的：確定主串中所含子串第一次出現(xiàn)的位置（定位）

——即如何實(shí)現(xiàn)Index(S,T,pos)函數(shù)4.3串的模式匹配算法模式匹配(PatternMatching)即子串定位運(yùn)算（Index函數(shù)）兩種模式匹配算法： 1.樸素模式匹配算法 2.KMP模式匹配算法數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第73頁。樸素模式匹配算法(BF算法)簡單的說，就是對主串的每一個字符作為字串開頭，與要匹配的字符串進(jìn)行匹配。對主串做大循環(huán)，每個字符開頭做小循環(huán)，直到匹配成功，或全部遍歷完為止。若匹配成功，則將S中與T匹配的子序列第一個字符的序號返回舉例：主串S=“goodgoogle”,字串T=“google”數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第74頁。樹和二叉樹（Tree&BinaryTree）5.1樹的基本概念5.2樹的抽象數(shù)據(jù)類型5.3樹的存儲結(jié)構(gòu)5.4二叉樹5.5樹和森林5.6赫夫曼樹及其應(yīng)用數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第75頁。5.1樹的基本概念樹(Tree)是n(n>=0)個結(jié)點(diǎn)的有限集。n=0時稱為空樹。在任意一棵非空樹中：(1)有且僅有一個特定的稱為根(Root)的結(jié)點(diǎn)；(2)當(dāng)n>1時，其余結(jié)點(diǎn)可分為m(m>0)個互不相交的有限集T1、T2、……、Tm,其中每一個集合本身又是一棵樹，并且稱為根的子樹(SubTree)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第76頁。注意1.n>0時根結(jié)點(diǎn)是唯一的，不可能存在多個根結(jié)點(diǎn)2.m>0時子樹的個數(shù)沒有限制，但它們一定是互不相交的5.3樹的基本概念數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第77頁。結(jié)點(diǎn)分類結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹葉結(jié)點(diǎn)(終端結(jié)點(diǎn))：度為0的結(jié)點(diǎn)分支結(jié)點(diǎn)(非終端結(jié)點(diǎn))：度不為0的結(jié)點(diǎn)樹的度：樹內(nèi)各結(jié)點(diǎn)的度的最大值5.3樹的基本概念數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第78頁。結(jié)點(diǎn)間關(guān)系結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子(Child)，相應(yīng)地，該結(jié)點(diǎn)稱為孩子的雙親(Parent)。同一個雙親的孩子之間互稱兄弟(Silbing)。結(jié)點(diǎn)的祖先是從根結(jié)點(diǎn)到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)。以某結(jié)點(diǎn)為根的子樹中任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。對于H來說，D、B、A都是它的祖先對B來說，D、G、H、I都是它的子孫5.3樹的基本概念數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第79頁。樹的分層結(jié)點(diǎn)的層次(Level)：從根開始定義起，根為第一層，根的孩子為第二層,以此類推。堂兄弟：雙親在同一層的結(jié)點(diǎn)。結(jié)點(diǎn)的深度：是從根節(jié)點(diǎn)開始自頂向下逐層累加結(jié)點(diǎn)的高度：從葉節(jié)點(diǎn)開始自底層向上逐層累加樹的深度(Depth)或高度：樹中結(jié)點(diǎn)最大層次5.3樹的基本概念數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第80頁。樹的其他概念D、E、F互為堂兄弟當(dāng)前樹的深度為4如果書中結(jié)點(diǎn)的各子樹看成從左至右是有次序的，不能互換的，則稱該樹為有序樹，否則稱為無序樹。路徑長度：路徑上所經(jīng)過的邊的個數(shù)森林是m(m>=0)棵互不相交的樹的集合5.3樹的基本概念數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第81頁。樹的性質(zhì)1)樹中的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度數(shù)加12)度為m的樹中第i層上至多有mi-1個結(jié)點(diǎn)（i>=1）3)高度為h的m叉樹至多有(mh-1)/(m-1)個結(jié)點(diǎn)4)具有n個結(jié)點(diǎn)的m叉樹的最小高度為[logm(n(m-1)+1)]5.3樹的基本概念數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第82頁。樹與線性表的對比5.3樹的基本概念數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第83頁。5.3樹的抽象數(shù)據(jù)類型數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第84頁。5.3樹的存儲結(jié)構(gòu)說到存儲，我們會想起順序存儲和鏈?zhǔn)酱鎯煞N結(jié)構(gòu)。簡單的順序存儲結(jié)構(gòu)不能滿足樹的實(shí)現(xiàn)要求充分利用順序存儲和鏈?zhǔn)酱鎯Φ奶攸c(diǎn)，可以實(shí)現(xiàn)對樹的存儲結(jié)構(gòu)的實(shí)現(xiàn)存儲結(jié)構(gòu)：①雙親表示法②孩子表示法③孩子兄弟表示法數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第85頁。5.3樹的存儲結(jié)構(gòu)①雙親表示法思路：用一組連續(xù)空間來存儲樹的結(jié)點(diǎn)，同時在每個結(jié)點(diǎn)中附設(shè)一個指示器，指示其雙親結(jié)點(diǎn)在鏈表中的位置。parentsdata結(jié)點(diǎn)結(jié)構(gòu)dataparents1樹結(jié)構(gòu)

23n數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第86頁。缺點(diǎn)：求結(jié)點(diǎn)的孩子時需要遍歷整個結(jié)構(gòu)。5.3樹的存儲結(jié)構(gòu)①雙親表示法實(shí)際中權(quán)限菜單的結(jié)構(gòu)設(shè)計。數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第87頁。存儲結(jié)構(gòu)的設(shè)計是一個非常靈活的過程。一個存儲結(jié)構(gòu)設(shè)計的是否合理，取決于基于該存儲結(jié)構(gòu)的運(yùn)算是否合適、是否方便，時間復(fù)雜度好不好等5.3樹的存儲結(jié)構(gòu)①雙親表示法拓展長子域數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第88頁。5.3樹的存儲結(jié)構(gòu)②孩子表示法思路：將每個結(jié)點(diǎn)的孩子結(jié)點(diǎn)都用單鏈表鏈接起來形成一個線性結(jié)構(gòu)，則N個結(jié)點(diǎn)就有N個孩子鏈表（葉子結(jié)點(diǎn)的孩子鏈表為空表）優(yōu)缺點(diǎn)：尋找子女的操作非常直接，而尋找雙親需要遍歷N個結(jié)點(diǎn)abecdfhgdefghgfedcbah12345678bc數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第89頁。5.3樹的存儲結(jié)構(gòu)③孩子兄弟表示法思路：用二叉鏈表來表示樹，但鏈表中的兩個指針域含義不同。左指針指向該結(jié)點(diǎn)的第一個孩子；右指針指向該結(jié)點(diǎn)的下一個兄弟結(jié)點(diǎn)。nextsiblingdatafirstchild指向左孩子指向右兄弟數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第90頁。abecdfhgbacedfgh③孩子兄弟表示法5.3樹的存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第91頁。5.4二叉樹為何要重點(diǎn)研究每結(jié)點(diǎn)最多只有兩個“叉”的樹？二叉樹的結(jié)構(gòu)最簡單，規(guī)律性最強(qiáng)；可以證明，所有樹都能轉(zhuǎn)為唯一對應(yīng)的二叉樹，不失一般性。1. 二叉樹的基本概念2. 二叉樹的性質(zhì)3. 二叉樹的存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第92頁。1.二叉樹的基本概念定義：是n（n≥0）個結(jié)點(diǎn)的有限集合，該集合或者為空集，或者由一個根結(jié)點(diǎn)以及至多兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成。5.4二叉樹特點(diǎn)：

每個結(jié)點(diǎn)最多有兩棵子樹

左右子樹有順序，次序不能任意顛倒

即使樹中某結(jié)點(diǎn)只有一棵子樹，也要區(qū)分它是左子樹還是右子樹數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第93頁。5.4二叉樹

具有3個結(jié)點(diǎn)的二叉樹可能有幾種不同形態(tài)？普通樹呢？2、二叉樹的五種基本形態(tài)1.空二叉樹2.只有一個根結(jié)點(diǎn)3.根結(jié)點(diǎn)只有左子樹4.根結(jié)點(diǎn)只有右子樹5.根結(jié)點(diǎn)既有左子樹又有右子樹

數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第94頁。滿二叉樹：一棵高度為h，并且含有2h-1個結(jié)點(diǎn)的二叉樹稱為滿二叉樹，即樹中的每一層都含有最多的結(jié)點(diǎn)5.4二叉樹121234567111089131415滿二叉樹按層序編號：約定編號從根結(jié)點(diǎn)（根結(jié)點(diǎn)編號為1）起，自上而下，自左向右。這樣每個結(jié)點(diǎn)對應(yīng)一個編號，對編號為i的結(jié)點(diǎn)，如果有雙親，其雙親為[i/2]，如果有左孩子，則左孩子為2i；如果有右孩子，則右孩子為2i+13、特殊二叉樹——滿二叉樹數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第95頁。4、特殊二叉樹——完全二叉樹完全二叉樹：設(shè)一個高度為h，有n個結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點(diǎn)都與高度為h的滿二叉樹編號為1~n的結(jié)點(diǎn)一一對應(yīng)時，稱為完全二叉樹5.4二叉樹12345671089完全二叉樹特點(diǎn)：1.葉子結(jié)點(diǎn)只能出現(xiàn)在最下兩層2.倒數(shù)第二層，若有葉子結(jié)點(diǎn)，一定都在右部連續(xù)位置3.去掉最后一層，則必為滿二叉樹數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第96頁。5、特殊二叉樹——二叉排序樹、平衡二叉樹

二叉排序樹：一棵二叉樹或空二叉樹，或者是具有如下性質(zhì)的二叉樹：左子樹上所有結(jié)點(diǎn)的關(guān)鍵字均小于根結(jié)點(diǎn)的關(guān)鍵字；右子樹上的所有結(jié)點(diǎn)的關(guān)鍵字均大于根結(jié)點(diǎn)的關(guān)鍵字。左子樹和右子樹又各是一棵二叉排序樹5.4二叉樹平衡二叉樹：樹上任一結(jié)點(diǎn)的左子樹和右子樹的深度之差不超過1數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第97頁。1.二叉樹性質(zhì)性質(zhì)1：在二叉樹的第i層上至多有2i-1個結(jié)點(diǎn)(i>=1)5.4二叉樹性質(zhì)2：深度為k的二叉樹至多有2k-1個結(jié)點(diǎn)(k>=1)性質(zhì)3：對任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1性質(zhì)4：具有n個結(jié)點(diǎn)的完全二叉樹的深度為[log2n]+1([x]表示不大于x的最大整數(shù))數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第98頁。2.二叉樹性質(zhì)性質(zhì)5：如果對一棵有n個結(jié)點(diǎn)的完全二叉樹(其深度為[log2n]+1)的結(jié)點(diǎn)按層編號（從第1層到第[log2n]+1層，每層從左到右），對任一結(jié)點(diǎn)i(1<=i<=n)有： 1）如果i=1，則結(jié)點(diǎn)i是二叉樹的根，無雙親；如果i>1，則其雙親是結(jié)點(diǎn)[i/2] 2）如果2i>n，則結(jié)點(diǎn)i無左孩子(結(jié)點(diǎn)i為葉子結(jié)點(diǎn))；否則其左孩子是結(jié)點(diǎn)2i 3）如果2i+1>n，則結(jié)點(diǎn)i無右孩子；否則其右孩子是結(jié)點(diǎn)2i+15.4二叉樹數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第99頁。5.4二叉樹3.二叉樹的存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)按二叉樹的結(jié)點(diǎn)“自上而下、從左至右”編號，用一組連續(xù)的存儲單元存儲?？砂凑胀耆鏄涞木幪?，把不存在的結(jié)點(diǎn)設(shè)置為缺點(diǎn)：①浪費(fèi)空間；②插入、刪除不便順序存儲結(jié)構(gòu)一般只用于完全二叉樹數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第100頁。5.4二叉樹3.二叉樹的存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)（二叉鏈表）數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第101頁。二叉樹的遍歷是指從根結(jié)點(diǎn)出發(fā)，按照某種次序一次訪問二叉樹中所有的結(jié)點(diǎn)，使得每個結(jié)點(diǎn)被訪問一次且僅被訪問一次二叉樹遍歷方法：①前序遍歷②中序遍歷③后續(xù)遍歷④層序遍歷5.4二叉樹4.遍歷二叉樹數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第102頁。①前序遍歷規(guī)則：若二叉樹為空，則空操作返回，否則先訪問根結(jié)點(diǎn)，然后前序遍歷左子樹，再前序遍歷右子樹5.4二叉樹4.遍歷二叉樹數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第103頁。②中序遍歷規(guī)則：若二叉樹為空，則空操作返回，否則從根結(jié)點(diǎn)開始(注意并不是先訪問根結(jié)點(diǎn))，中序遍歷根結(jié)點(diǎn)的左子樹，然后是訪問根結(jié)點(diǎn)，最后中序遍歷右子樹5.4二叉樹4.遍歷二叉樹數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第104頁。③后序遍歷規(guī)則：若二叉樹為空，則空操作返回，否則從左到右先葉子后結(jié)點(diǎn)的方式遍歷訪問左右子樹，最后是訪問根結(jié)點(diǎn)。4.遍歷二叉樹5.4二叉樹數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第105頁。④層序遍歷規(guī)則：若二叉樹為空，則空操作返回，否則從樹的第一層，也就是根結(jié)點(diǎn)開始訪問，從上而下逐層遍歷，在同一層中，按從左到右的順序?qū)Y(jié)點(diǎn)逐個訪問。5.4二叉樹4.遍歷二叉樹數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第106頁。④層序遍歷規(guī)則：若二叉樹為空，則空操作返回，否則從樹的第一層，也就是根結(jié)點(diǎn)開始訪問，從上而下逐層遍歷，在同一層中，按從左到右的順序?qū)Y(jié)點(diǎn)逐個訪問。5.4二叉樹4.遍歷二叉樹數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第107頁。5.3樹和森林樹轉(zhuǎn)換為二叉樹1.加線：在所有兄弟結(jié)點(diǎn)之間加一條連線2.去線：對書中每個結(jié)點(diǎn)，只保留它與第一個孩子結(jié)點(diǎn)的連線，刪除它與其他孩子系欸但之間的連線3.層次調(diào)整：以樹的根結(jié)點(diǎn)為軸心，將整棵樹順時針旋轉(zhuǎn)一定角度，使之結(jié)構(gòu)層次分明。注意第一個孩子是二叉樹結(jié)點(diǎn)的左孩子，兄弟轉(zhuǎn)換過來的孩子是結(jié)點(diǎn)的右孩子。數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第108頁。5.3樹和森林樹轉(zhuǎn)換為二叉樹數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第109頁。5.3樹和森林森林轉(zhuǎn)換為二叉樹步驟：1.把每個樹轉(zhuǎn)換為二叉樹2.第一棵二叉樹不動，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹的根結(jié)點(diǎn)的右孩子，用線連起來。當(dāng)所有的二叉樹連接起來后就得到了由森林轉(zhuǎn)換來的二叉樹森林是由若干棵樹組成的，所以完全可以理解為，森林中的每一棵樹都是兄弟，可以按照兄弟的處理辦法來操作數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第110頁。5.3樹和森林森林轉(zhuǎn)換為二叉樹數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第111頁。5.3樹和森林二叉樹轉(zhuǎn)換為樹步驟：1.加線。若某結(jié)點(diǎn)的左孩子結(jié)點(diǎn)存在，則將左孩子的n個右孩子結(jié)點(diǎn)用線連接起來2.去線。刪除原二叉樹中所有結(jié)點(diǎn)與其右孩子結(jié)點(diǎn)的連線3.層次調(diào)整，使之結(jié)構(gòu)層次分明二叉樹轉(zhuǎn)換為樹是樹轉(zhuǎn)換為二叉樹的逆過程，也就是反過來做而已數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第112頁。5.3樹和森林二叉樹轉(zhuǎn)換為樹數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第113頁。5.3樹和森林二叉樹轉(zhuǎn)換為森林步驟：1.從根結(jié)點(diǎn)開始，若右孩子存在，則把與右孩子結(jié)點(diǎn)的連線刪除，再查看分離后的二叉樹，若右孩子存在，則連線刪除，直到所有的右孩子連線都刪除為止，得到分離的二叉樹2.將每棵分離后的二叉樹轉(zhuǎn)換為樹判斷一棵二叉樹能夠轉(zhuǎn)換成一棵樹還是森林，標(biāo)準(zhǔn)很簡單，就是只要看這棵樹的根結(jié)點(diǎn)有沒有右孩子，有就是森林，沒有就是一棵樹數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第114頁。5.3樹和森林二叉樹轉(zhuǎn)換為森林?jǐn)?shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第115頁。5.4哈夫曼樹哈夫曼樹的引例效率相對低效率相對高數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第116頁。5.4哈夫曼樹哈夫曼樹的定義在許多實(shí)際應(yīng)用中，樹中結(jié)點(diǎn)常常被賦予一個表示某種意義的數(shù)值，稱為該結(jié)點(diǎn)的權(quán)。從樹根結(jié)點(diǎn)到任意結(jié)點(diǎn)的路徑長度與該結(jié)點(diǎn)上權(quán)值的乘積稱為該結(jié)點(diǎn)的帶權(quán)路徑長度樹中所有的葉結(jié)點(diǎn)的帶權(quán)路徑長度之和稱為該樹的帶權(quán)路徑長度記為Wi是第i個葉結(jié)點(diǎn)所帶的權(quán)值；li是該葉結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長度在含有N個帶權(quán)葉子結(jié)點(diǎn)的二叉樹中，其中帶權(quán)路徑長度(WPL)最小的二叉樹稱為哈夫曼樹，也稱為最優(yōu)二叉樹數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第117頁。5.4哈夫曼樹帶權(quán)路徑長度計算(a)WPL=7*2+5*2+2*2+4*2=36(a)WPL=7*3+5*3+2*1+4*2=46(a)WPL=7*1+5*2+2*3+4*3=35(c)中樹的WPL最小，它為哈夫曼樹數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第118頁。5.4哈夫曼樹哈夫曼樹的構(gòu)造給定N個權(quán)值分別為w1，w2,…，wn的結(jié)點(diǎn)，通過哈夫曼算法構(gòu)造出最優(yōu)二叉樹1.將這n個結(jié)點(diǎn)分別作為n棵僅含一個結(jié)點(diǎn)的二叉樹，構(gòu)成森林F2.構(gòu)造一個新結(jié)點(diǎn)，并從F中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作為新結(jié)點(diǎn)的左、右子樹，并且將新結(jié)點(diǎn)的權(quán)值置為左、右子樹上根結(jié)點(diǎn)的權(quán)值之和3.從F中刪除剛才選出的兩棵樹，同時將新的到的樹加入F中4.重復(fù)步驟2和3，直至F中只剩下一棵樹為止數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第119頁。5.4哈夫曼樹哈夫曼樹的構(gòu)造過程數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第120頁。5.4哈夫曼樹哈夫曼樹的特點(diǎn)1.每個初始結(jié)點(diǎn)最終都稱為葉結(jié)點(diǎn)，并且權(quán)值越小的結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長度越大2.構(gòu)造過程中共新建了N-1個結(jié)點(diǎn)（雙分支結(jié)點(diǎn)），因此哈夫曼樹中結(jié)點(diǎn)總數(shù)為2N-13.每次構(gòu)造都選擇2棵樹作為新結(jié)點(diǎn)的孩子，因此哈夫曼樹中不存在度為1的結(jié)點(diǎn)

數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第121頁。圖6.1圖的基本概念6.2圖的存儲及基本操作(鄰接矩陣法；鄰接表法；鄰接多重表法；十字鏈表法)6.3圖的遍歷(深度優(yōu)先搜索；廣度優(yōu)先搜索)6.4圖的基本應(yīng)用(最小生成樹；最短路徑)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第122頁。6.1圖的基本概念圖G由頂點(diǎn)集V和邊集E組成，記為G=(V,E)，其中V(G)表示圖G中頂點(diǎn)的有限非空集；E(G)表示圖G中頂點(diǎn)之間的關(guān)系(邊)集合。若V={v1,v2,……,vn},用|V|表示圖G中頂點(diǎn)的個數(shù)，也稱為圖G的階，E={(u,v)|u∈V,v∈V},用|E|表示圖G中邊的條數(shù)注意：線性表可以是空表，樹可以是空樹，但圖不可以是空圖圖中不能一個頂點(diǎn)也沒有，但邊集E可以為空數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第123頁。6.1圖的基本概念有向圖：若E是有向邊(也稱為弧)的有限集合時，則圖G為有向圖?；∈琼旤c(diǎn)的有序?qū)?，記?lt;v,w>，其中v,w是頂點(diǎn)，v稱為弧尾，w稱為弧頭，稱為從頂點(diǎn)v到頂點(diǎn)w的弧，也稱v鄰接到w，或w鄰接自v。123

G=(V,E)V={1,2,3}E={<1,2>,<2,1>,<2,3>}數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第124頁。6.1圖的基本概念無向圖：若E是無向邊(簡稱邊)的有限集合時，則圖G為無向圖。邊：是頂點(diǎn)的無序?qū)?，記?v,w)或(w,v)。因?yàn)?v,w)=(w,v),其中v,w是頂點(diǎn)，可以說頂點(diǎn)w和頂點(diǎn)v互為鄰接點(diǎn)。邊(v,w)依附于頂點(diǎn)w和v，或者說邊(v,w)和頂點(diǎn)v,w相關(guān)聯(lián)。1234

G=(V,E)V={1,2,3,4}E={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第125頁。6.1圖的基本概念簡單圖：一個圖G如果滿足：1.不存在重復(fù)邊；2.不存在頂點(diǎn)到自身的邊，則稱圖G為簡單圖。(數(shù)據(jù)結(jié)構(gòu)中僅討論簡單圖)DBCA數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第126頁。6.1圖的基本概念多重圖：若圖G中某兩個結(jié)點(diǎn)之間的邊數(shù)多于一條，又允許頂點(diǎn)通過同一條邊和自己關(guān)聯(lián)，則G為多重圖。(多重圖的定義和簡單圖是相對的)DBCA數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第127頁。6.1圖的基本概念無向完全圖：在無向圖中，如果任意兩個頂點(diǎn)之間都存在邊，則稱該圖為無向完全圖。含有n個頂點(diǎn)的無向完全圖有n(n-1)/2條邊。有向完全圖：在有向圖中，如果任意兩個頂點(diǎn)之間都存在方向相反的兩條弧，則稱該圖為有向完全圖。含有n個頂點(diǎn)的有向完全圖有n(n-1)條有向邊DBCADBCA無向完全圖有向完全圖數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第128頁。6.1圖的基本概念子圖：設(shè)有兩個圖G1=(V1,E1)和G2=(V2,E2)，若V2是V1的子集，則稱G2是G的子圖。注意：

并非V和E的任何子集都能構(gòu)成G的子圖，因?yàn)檫@樣的子集可能不是圖，也就是說，E的子集中的某些邊關(guān)聯(lián)的頂點(diǎn)可能不在這個V的子集中DBCADBCDBCADCA數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第129頁。6.1圖的基本概念連通：在無向圖中，若從頂點(diǎn)v到頂點(diǎn)w有路徑存在，則稱v和w是連通的。連通圖：若圖G中任意兩個頂點(diǎn)都是連通的，則稱圖G為連通圖。否則稱為非連通圖。ABCDEFABCD非連通圖連通圖數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第130頁。6.1圖的基本概念連通分量：無向圖中的極大連通子圖稱為連通分量。如果一個圖有n個頂點(diǎn)，并且有小于n-1條邊，則此圖必為非連通圖注意： 1.要是子圖 2.子圖要是連通的 3.連通子圖含有極大頂點(diǎn)數(shù) 4.具有極大頂點(diǎn)數(shù)的連通子圖包含依附于

這些頂點(diǎn)的所有邊數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第131頁。6.1圖的基本概念圖1是一個無向非連通圖，但是它有兩個連通分量，即圖2和圖3。圖4盡管是圖1的子圖，但是它卻不滿足連通子圖的極大頂點(diǎn)數(shù)，因此它不是圖1的無向圖的連通分量ABCDEF圖1ABCD圖2EF圖3ABD圖4數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第132頁。6.1圖的基本概念強(qiáng)連通：在有向圖中，若從頂點(diǎn)v到頂點(diǎn)w和從頂點(diǎn)w到頂點(diǎn)v之間都有路徑，則稱這兩個頂點(diǎn)是強(qiáng)連通的強(qiáng)連通圖：若圖中任何一對頂點(diǎn)都是強(qiáng)連通的，則此圖稱為強(qiáng)連通圖。DBCA123判斷是否是強(qiáng)連通圖數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第133頁。6.1圖的基本概念強(qiáng)連通分量：有向圖中極大強(qiáng)連通子圖稱為有向圖的強(qiáng)連通分量DBCADBA圖1圖2圖2是圖1的強(qiáng)連通分量數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第134頁。6.1圖的基本概念生成樹：連通圖的生成樹是包含圖中全部頂點(diǎn)的一個極小連通子圖。若圖中頂點(diǎn)數(shù)為n，則它的生成樹含有n-1條邊。對于生成樹而言，若砍去它的一條邊，則會變成非連通圖，若加上一條邊則會形成一個回路。生成森林：在非連通圖中，連通分量的生成樹構(gòu)成了非連通圖的生成森林?jǐn)?shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第135頁。6.1圖的基本概念頂點(diǎn)的度：以該頂點(diǎn)為一個端點(diǎn)的邊的數(shù)目對于無向圖，頂點(diǎn)v的度是指依附于該頂點(diǎn)的邊的條數(shù)，記為TD(v)對于有向圖，頂點(diǎn)v的度分為入度和出度，入度是以頂點(diǎn)v為終點(diǎn)的有向邊的數(shù)目，記為ID(v)；而出度是以頂點(diǎn)v為起點(diǎn)的有向邊的數(shù)目，記為OD(v)。頂點(diǎn)v的度等于其入度和出度之和，即TD(v)=ID(v)+OD(v)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第136頁。6.1圖的基本概念邊上的權(quán)：在一個圖中，每條邊都可以標(biāo)上具有某種含義的數(shù)值，該數(shù)值稱為該邊的權(quán)值。網(wǎng)：邊上帶有權(quán)值的圖稱為帶權(quán)圖稀疏圖：邊數(shù)很少（相對的）的圖稱為稀疏圖稠密圖：邊數(shù)很多（相對的）的圖稱為稠密圖一般當(dāng)圖G滿足|E|<|V|*log|V|時，可以將G看成是稀疏圖數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁，當(dāng)前為第137頁。6.1圖的基本概念路徑長度:頂點(diǎn)Vp到頂點(diǎn)Vq之間有一條路徑是指頂點(diǎn)序列Vp，Vi1，Vi2，……，Vim，Vq。路徑上邊的數(shù)目稱為路徑長度?；芈坊颦h(huán):第一個頂點(diǎn)和最后一個頂點(diǎn)相同的路徑稱為回路或環(huán)。如果一個圖有n個頂點(diǎn)，并且有大于n-1條邊，則此圖一定有環(huán)。簡單路徑：在路徑序列中，頂點(diǎn)不重復(fù)出現(xiàn)的路徑稱為簡單路徑。簡單回路：除第一個頂點(diǎn)和最后一個頂點(diǎn)外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路稱為簡單回路。