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

1、數(shù)據(jù)結(jié)構(gòu)部分?jǐn)?shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)基本結(jié)構(gòu)基本結(jié)構(gòu): 2. 線性結(jié)構(gòu):數(shù)據(jù)之間存在一對一的關(guān)系; 3. 樹 : 數(shù)據(jù)元素間存在一對多的關(guān)系 ; 4. 圖: 數(shù)據(jù)元素間存在多對多的關(guān)系; 定義:相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合.1. 集合 :數(shù)據(jù)元素之間“同屬于一個(gè)集合”; 集合例題. 設(shè)全集I = a, b, c, d, e, f, g, h，集合A = a, b, c, d, e, f，B = c, d, e，C = a, d，那么集合AnBnC為（ ）。A. c, e B. d, e C. e D. c, d, e E. d, f n : 交集,與的關(guān)系 u: 并集,或的關(guān)系 :

2、非的關(guān)系=not nuC= b, c, e, f, g, hAnB= c, d, eAnBnC= c,eA線性結(jié)構(gòu)特點(diǎn)特點(diǎn):由n（n0）個(gè)數(shù)據(jù)元素（結(jié)點(diǎn)）a1，a2，an組成的有限序列,(1). 在這個(gè)序列中,存在唯一稱做“第一個(gè)”的數(shù)據(jù)元素;(2). 存在唯一的一個(gè)被稱做“最后一個(gè)”的數(shù)據(jù)元素;(3). 除第一個(gè)之外,集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū);(4). 除最后一個(gè)元素外,集合中的每個(gè)元素均只有一個(gè)后繼.應(yīng)用應(yīng)用:線性表: 棧和隊(duì)列: 數(shù)組: 線性結(jié)構(gòu)線性表的順序存儲(chǔ)順序存儲(chǔ)結(jié)構(gòu)(1) 方法:把線性表的結(jié)點(diǎn)按邏輯次序依次存放在一組地址連續(xù)的存儲(chǔ)單元里的方法。 a1a2a3a4序列:

3、a1,a2,a3,a4內(nèi)存狀態(tài)地址bb+ lb+ (2-1)*lb+ (3-1)*lL :表示每個(gè)元素所占字節(jié)數(shù)目地址: 元素所占的第一個(gè)單元 的存儲(chǔ)地址(2).特點(diǎn):邏輯上相鄰的結(jié)點(diǎn)其物理位置亦相鄰 結(jié)點(diǎn)結(jié)點(diǎn)a ai i 的存儲(chǔ)地址的存儲(chǔ)地址 不失一般性，設(shè)線性表中所有結(jié)點(diǎn)的類型相同，則每個(gè)結(jié)點(diǎn)所占用存儲(chǔ)空間大小亦相同。假設(shè)表中每個(gè)結(jié)點(diǎn)占用c個(gè)存儲(chǔ)單元，其中第一個(gè)單元的存儲(chǔ)地址則是該結(jié)點(diǎn)的存儲(chǔ)地址，并設(shè)表中開始結(jié)點(diǎn)a1的存儲(chǔ)地址（簡稱為基地址）是LOC（a1），那么結(jié)點(diǎn)ai的存儲(chǔ)地址LOC（ai）可通過下式計(jì)算： LOCLOC（a ai i）= LOC= LOC（a a1 1）+ +（i-1

4、i-1）* *c c 1in 1in練習(xí): 一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是100,每個(gè)元素的長度是2,則第5個(gè)元素的地址是( ) A) 110 B) 108 C) 100 D) 109 B線性表的鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(1)方法: 用一組任意的存儲(chǔ)單元來存放線性表的結(jié)點(diǎn)（這組存儲(chǔ)單元既可以 是連續(xù)的，也可以是不連續(xù)的） 鏈表中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同。為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)，還必須存儲(chǔ)指示其后繼結(jié)點(diǎn)的地址（或位置）信息（稱為指針（pointer）或鏈(link)） (2) 結(jié)點(diǎn)結(jié)構(gòu)datenextdata-存放結(jié)點(diǎn)值的數(shù)據(jù)域next-存放結(jié)點(diǎn)的直接后繼的

5、地址（位置）的指針域（鏈域） 序列: zhao, qian, sun, li, zhouzhaoqianzhousunli存儲(chǔ)地址數(shù)據(jù)(date)指針(next)1li序列: zhao, qian, sun, li, zhou, wu, zheng, wang437qian1313sun119wangnull25wu3731zhao737zheng1943zhou25頭指針 31內(nèi)存中的存儲(chǔ)方式線性表的鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)循環(huán)鏈表循環(huán)鏈表（1）單循環(huán)鏈表在單鏈表中，將終端結(jié)點(diǎn)的指針域NULL改為指向表頭結(jié)點(diǎn)或開始結(jié)點(diǎn)即可。 小結(jié): (1) 線性表的順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)比較順序: 優(yōu) 查找結(jié)點(diǎn)方便

6、 缺 進(jìn)行插入和刪除時(shí),需要花費(fèi)大量的時(shí)間來移動(dòng)數(shù)據(jù) 存儲(chǔ)規(guī)模過大時(shí)難于預(yù)先估計(jì)空間,過大造成空間浪費(fèi),過小 又會(huì)使數(shù)據(jù)溢出.鏈?zhǔn)? 優(yōu) 進(jìn)行數(shù)據(jù)的刪除和插入時(shí)只需要修改指針即可,非常方便. 當(dāng)存儲(chǔ)規(guī)模較大時(shí),動(dòng)態(tài)分配不連續(xù)的內(nèi)存空間,不會(huì)造成浪費(fèi). 缺 查找某個(gè)結(jié)點(diǎn)需要從頭指針起順著鏈掃描才能取到.(2).鏈?zhǔn)酱鎯?chǔ)是最常用的存儲(chǔ)方式之一，它不僅可用來表示線性表，而且可用來表示各種非線性的數(shù)據(jù)結(jié)構(gòu)。 線性結(jié)構(gòu)1、棧的定義、棧的定義 棧（Stack）是限制僅在表的一端一端進(jìn)行插入和刪除運(yùn)算的線性表。(1)通常稱插入、刪除的這一端為棧頂棧頂（Top），另一端稱為棧底棧底（Bottom）。(2)當(dāng)表

7、中沒有元素時(shí)稱為空?？諚?。(3)棧為后進(jìn)先出（Last In First Out）的線性表，簡稱為LIFO表表。 棧的修改是按后進(jìn)先出的原則進(jìn)行。每次刪除（退棧退棧）的總是當(dāng)前棧中最新的元素，即最后插入（進(jìn)棧進(jìn)棧）的元素，而最先插入的是被放在棧的底部，要到最后才能刪除。 設(shè)棧S的初始狀態(tài)為空，元素a, b, c, d, e, f, g依次入棧，以下出棧序列不可能出現(xiàn)的是（ ）。A. a, b, c, e, d, f, g B. b, c, a, f, e, g, dC. a, e, d, c, b, f, gD. d, c, f, e, b, a, g E. g, e, f, d, c, b,

8、 a遞歸E2 2、隊(duì)列的定義、隊(duì)列的定義隊(duì)列（Queue）是只允許在一端一端進(jìn)行插入，而在另一端另一端進(jìn)行刪除的運(yùn)算受限的線性表（1）允許刪除的一端稱為隊(duì)頭（隊(duì)頭（Front）。（2）允許插入的一端稱為隊(duì)尾（隊(duì)尾（Rear）。（3）當(dāng)隊(duì)列中沒有元素時(shí)稱為空隊(duì)列空隊(duì)列。（4）隊(duì)列亦稱作先進(jìn)先出（First In First Out）的線性表，簡稱為FIFO表表。 隊(duì)列的修改是依先進(jìn)先出的原則進(jìn)行的。新來的成員總是加入隊(duì)尾（即不允許加塞），每次離開的成員總是隊(duì)列頭上的（不允許中途離隊(duì)），即當(dāng)前最老的成員離隊(duì)。 某例題:車站呈狹長形，寬度只能容下一臺(tái)車，并且只有一個(gè)出入口。已知某時(shí)該車站站臺(tái)為空，從

9、這一時(shí)刻開始出入記錄為：“進(jìn)出進(jìn)進(jìn)出進(jìn)進(jìn)進(jìn)出出進(jìn)出”。假設(shè)車輛入站的順序?yàn)?,2,3，則車輛出站的順序?yàn)椋?） A、1，2，3，4，5 B、1，2，4，5，7 C、1，3，5，4，6 D、1，3，5，6，7 E、1，3，6，5，7 棧入隊(duì)列出隊(duì)列隊(duì)頭隊(duì)尾E已知隊(duì)列(13，2，11，34，41，77，5，7，18，26，15)，第一個(gè)進(jìn)入隊(duì)列的元素是13，則第五個(gè)出隊(duì)列的元素是( )。 A)5 B)41 C)77 D)13 E)18 B線性結(jié)構(gòu)(1) 一維數(shù)組: 向量(2) 多維數(shù)組 1. 矩陣的存儲(chǔ)a11 a12 a1na21 a22 a2na31 a32 a3nam1am2 amnM個(gè)行向量

10、N個(gè)列向量 2.矩陣地址計(jì)算例題: 已知數(shù)組A中，每個(gè)元素AI，J在存貯時(shí)要占3個(gè)字節(jié)，設(shè)I從1變化到8，J從1變化到10，分配內(nèi)存時(shí)是從地址SA開始連續(xù)按行存貯分配的,試問：A5，8的起始地址為（ ） ASA+141 B.SA+180 CSA+222 DSA+225 LOC(aij)=LOC(a11)+(i-1)j+j-1dA1、樹的定義、樹的定義 樹(Tree)是n(n0)個(gè)結(jié)點(diǎn)的有限集T，T為空時(shí)稱為空樹，否則它滿足如下兩個(gè)條件：(1)有且僅有一個(gè)特定的稱為根(Root)的結(jié)點(diǎn)；(2)其余的結(jié)點(diǎn)可分為m(m0)個(gè)互不相交的子集Tl，T2，Tm，其中每個(gè)子集本身又是一棵樹，并稱其為根的子樹

11、子樹(Subree)。 注意： 樹的遞歸定義遞歸定義刻畫了樹的固有特性：一棵非空樹是由若干棵子樹構(gòu)成的，而子樹又可由若干棵更小的子樹構(gòu)成。 2. 樹的表示樹的表示 （1）樹形圖表示 樹形圖表示是樹結(jié)構(gòu)的主要表示方法。 樹的樹形圖表示中：結(jié)點(diǎn)用圓圈表示，結(jié)點(diǎn)的名字寫在圓圈旁邊（有時(shí)亦可寫在圓圈內(nèi)）。 樹形結(jié)構(gòu)3. 樹的基本術(shù)語樹的基本術(shù)語 （1） 孩子孩子(Child)和雙親和雙親(Parents) 樹中某個(gè)結(jié)點(diǎn)的子樹之根稱為該結(jié)點(diǎn)的孩子孩子(Child)或兒子，相應(yīng)地，該結(jié)點(diǎn)稱為孩子的雙親(Parents)或父親。 同一個(gè)雙親的孩子稱為兄弟(Sibling)。 （2）祖先）祖先(Ancesto

12、r)和子孫和子孫(Descendant) 若樹中結(jié)點(diǎn)k到ks存在一條路徑，則稱k是ks的祖先祖先(Ancestor)，ks是k的子孫子孫(Descendant)。 一個(gè)結(jié)點(diǎn)的祖先是從根結(jié)點(diǎn)到該結(jié)點(diǎn)路徑上所經(jīng)過的所有結(jié)點(diǎn)，而一個(gè)結(jié)點(diǎn)的子孫則是以該結(jié)點(diǎn)為根的子樹中的所有結(jié)點(diǎn)。 約定：結(jié)點(diǎn)k的祖先和子孫不包含結(jié)點(diǎn)k本身。 3. 樹的基本術(shù)語樹的基本術(shù)語 （3） 結(jié)點(diǎn)的度結(jié)點(diǎn)的度(Degree) 樹中的一個(gè)結(jié)點(diǎn)擁有的子樹數(shù)稱為該結(jié)點(diǎn)結(jié)點(diǎn)的度的度(Degree)。 一棵樹的度樹的度是指該樹中結(jié)點(diǎn)的最大度數(shù)。 度為零的結(jié)點(diǎn)稱為葉子葉子(Leaf)或終端結(jié)點(diǎn)終端結(jié)點(diǎn)。 度不為零的結(jié)點(diǎn)稱分支結(jié)點(diǎn)分支結(jié)點(diǎn)或非終

13、端結(jié)點(diǎn)非終端結(jié)點(diǎn)。 除根結(jié)點(diǎn)之外的分支結(jié)點(diǎn)統(tǒng)稱為內(nèi)部結(jié)點(diǎn)內(nèi)部結(jié)點(diǎn)。 （4）結(jié)點(diǎn)的層數(shù)）結(jié)點(diǎn)的層數(shù)(Level)和樹的高度（和樹的高度（Height） 結(jié)點(diǎn)的層數(shù)結(jié)點(diǎn)的層數(shù)(Level)從根起算： 根的層數(shù)為1 其余結(jié)點(diǎn)的層數(shù)等于其雙親結(jié)點(diǎn)的層數(shù)加1。 雙親在同一層的結(jié)點(diǎn)互為堂兄弟堂兄弟。 樹中結(jié)點(diǎn)的最大層數(shù)稱為樹的高度樹的高度(Height)或深度深度(Depth)。 3. 樹的基本術(shù)語樹的基本術(shù)語 （5）有序樹）有序樹(OrderedTree)和無序樹和無序樹(UnoderedTree) 若將樹中每個(gè)結(jié)點(diǎn)的各子樹看成是從左到右有次序的(即不能互換)，則稱該樹為有有序樹序樹(OrderedTr

14、ee)；否則稱為無序樹無序樹(UnoderedTree) （6）森林）森林(Forest) 森林森林(Forest)是m(m0)棵互不相交的樹的集合。 樹和森林的概念相近。刪去一棵樹的根，就得到一個(gè)森林；反之，加上一個(gè)結(jié)點(diǎn)作樹根，森林就變?yōu)橐豢脴洹?樹形結(jié)構(gòu)(1) (1) 二叉樹的遞歸定義二叉樹的遞歸定義 二叉樹(BinaryTree)是n(n0)個(gè)結(jié)點(diǎn)的有限集，它或者是空集(n=0)，或者由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的、分別稱作這個(gè)根的左子樹左子樹和右子樹右子樹的二叉樹組成。 (2)(2)二叉樹的五種基本形態(tài)二叉樹的五種基本形態(tài) 二叉樹可以是空集；根可以有空的左子樹或右子樹；或者左、右子樹皆為

15、空。 二叉樹的五種基本形態(tài)如下圖所示。 思考: 三個(gè)結(jié)點(diǎn)的二叉樹有幾種?二叉樹具有以下重要性質(zhì)：二叉樹具有以下重要性質(zhì)：性質(zhì)1 二叉樹第i層上的結(jié)點(diǎn)數(shù)目最多最多為2i-1(i1)。 推導(dǎo): 顯然! 性質(zhì)2 深度為k的二叉樹至多至多有2k-1個(gè)結(jié)點(diǎn)(k1)。 推導(dǎo): 等比數(shù)列求和.性質(zhì)3 在任意-棵二叉樹中，若終端結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則no=n2+1。 推導(dǎo): 二叉樹的幾種特殊情形二叉樹的幾種特殊情形 (1)滿二叉樹(FullBinaryTree) 一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二又樹稱為滿二叉樹。 滿二叉樹的特點(diǎn)：（1） 每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值。即對給定的高度，它是

16、具有最多結(jié)點(diǎn)數(shù)的二叉樹。（2） 滿二叉樹中不存在度數(shù)為1的結(jié)點(diǎn)，每個(gè)分支結(jié)點(diǎn)均有兩棵高度相同的子樹，且樹葉都在最下一層上。 思考: 滿二叉樹第I(I=1)層上的結(jié)點(diǎn)數(shù)目為( ) 2i-1深度為k的滿二叉樹有( ) 個(gè)結(jié)點(diǎn)(k1) 2k-1二叉樹的幾種特殊情形二叉樹的幾種特殊情形 (2) 完全二叉樹(Complete BinaryTree) 若一棵二叉樹至多只有最下面的兩層上結(jié)點(diǎn)的度數(shù)可以小于2，并且最下一層上的結(jié)點(diǎn)都集中在該層最左邊的若干位置上，則此二叉樹稱為完全二叉樹。 特點(diǎn)： （1） 滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。 （2） 在滿二叉樹的最下一層上，從最右邊開始連續(xù)刪去若

17、干結(jié)點(diǎn)后得到的二叉樹仍然是一棵完全二叉樹。 （3） 在完全二叉樹中，若某個(gè)結(jié)點(diǎn)沒有左孩子，則它一定沒有右孩子，即該結(jié)點(diǎn)必是葉結(jié)點(diǎn)。不是完全二叉樹(3) 平衡二叉樹 平衡二叉樹，又稱AVL樹。它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的高度之差之差的絕對值不超過1.。二叉樹的幾種特殊情形二叉樹的幾種特殊情形 (4) 二叉排序樹 二叉排序樹（Binary Sort Tree）或者是一棵空樹；或者是具有下列性質(zhì)的二叉樹：（1）若左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；（2）若右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；

18、（3）左、右子樹也分別為二叉排序樹；二叉樹的幾種特殊情形二叉樹的幾種特殊情形 (5) 均衡二叉樹 高度為n的均衡二叉樹是指：如果去掉葉節(jié)點(diǎn)級相應(yīng)的樹枝，它應(yīng)該是高度為n-1的滿二叉樹。在這里，樹高等于葉節(jié)點(diǎn)的最大深度，根節(jié)點(diǎn)的深度為0二叉樹的存儲(chǔ)二叉樹的存儲(chǔ)啟發(fā)一般二叉樹的順序存儲(chǔ)一般二叉樹的順序存儲(chǔ) 分析:優(yōu)點(diǎn)和缺點(diǎn)優(yōu)點(diǎn)和缺點(diǎn) 對完全二叉樹而言，順序存儲(chǔ)結(jié)構(gòu)既簡單又節(jié)省存儲(chǔ)空間。 一般的二叉樹采用順序存儲(chǔ)結(jié)構(gòu)時(shí)，雖然簡單，但易造成存儲(chǔ)空間的浪費(fèi)。 最壞的情況下，一個(gè)深度為k且只有k個(gè)結(jié)點(diǎn)的右單支樹需要2k-1個(gè)結(jié)點(diǎn)的存儲(chǔ)空間。 在對順序存儲(chǔ)的二叉樹做插入和刪除結(jié)點(diǎn)操作時(shí)，要大量移動(dòng)結(jié)點(diǎn)。 二

19、叉樹的遍歷二叉樹的遍歷(1) (1) 遍歷概念遍歷概念 所謂遍歷遍歷(Traversal)是指沿著某條搜索路線，依次對樹中每個(gè)結(jié)點(diǎn)均做一次且僅做一次訪問。訪問結(jié)點(diǎn)所做的操作依賴于具體的應(yīng)用問題。 遍歷是二叉樹上最重要的運(yùn)算之一，是二叉樹上進(jìn)行其它運(yùn)算之基礎(chǔ)。 (2) 遍歷的方法遍歷的方法11中序遍歷的遞歸算法定義：中序遍歷的遞歸算法定義： 若二叉樹非空，則依次執(zhí)行如下操作： (1)遍歷左子樹； (2)訪問根結(jié)點(diǎn)； (3)遍歷右子樹。 左 - 根 - 右中序遍歷序列:D B A E C F 2先序遍歷的遞歸算法定義：先序遍歷的遞歸算法定義： 若二叉樹非空，則依次執(zhí)行如下操作： (1) 訪問根結(jié)點(diǎn)

20、； (2) 遍歷左子樹； (3) 遍歷右子樹。 二叉樹的遍歷二叉樹的遍歷先序遍歷序列:A B D C E F 3后序遍歷得遞歸算法定義：后序遍歷得遞歸算法定義： 若二叉樹非空，則依次執(zhí)行如下操作： (1)遍歷左子樹； (2)遍歷右子樹； (3)訪問根結(jié)點(diǎn)。 后序遍歷序列:D B E F C A根 - 左 - 右左 - 右- 根二叉樹的遍歷二叉樹的遍歷中序: 左 根 右/ 先序: 根 左 右/ 后序: 左 右 根/ 最優(yōu)二叉樹最優(yōu)二叉樹( (哈夫曼樹哈夫曼樹) ) 概念(1):樹的路徑長度 樹的路徑長度是從樹根到樹中每一結(jié)點(diǎn)的路徑長度之和。在結(jié)點(diǎn)數(shù)目相同的二叉樹中，完全二叉樹的路徑長度最短。 概

21、念(2):樹的帶權(quán)路徑長度(Weighted Path Length of Tree，簡記為WPL) 結(jié)點(diǎn)的權(quán)結(jié)點(diǎn)的權(quán)：在一些應(yīng)用中，賦予樹中結(jié)點(diǎn)的一個(gè)有某種意義的實(shí)數(shù)。 結(jié)點(diǎn)的帶權(quán)路徑長度結(jié)點(diǎn)的帶權(quán)路徑長度：結(jié)點(diǎn)到樹根之間的路徑長度與該結(jié)點(diǎn)上權(quán)的乘積。 樹的帶權(quán)路徑長度樹的帶權(quán)路徑長度(Weighted Path Length of Tree)(Weighted Path Length of Tree)：定義為樹中所有葉結(jié)點(diǎn)的帶權(quán)路徑長度之和，通常記為： 其中： n表示葉子結(jié)點(diǎn)的數(shù)目 wi和li分別表示葉結(jié)點(diǎn)ki的權(quán)值和根到結(jié)點(diǎn)ki之間的路徑長度。 樹的帶權(quán)路徑長度亦稱為樹的代價(jià)。 最優(yōu)二叉

22、樹最優(yōu)二叉樹( (哈夫曼樹哈夫曼樹) ) 【例】給定4個(gè)葉子結(jié)點(diǎn)a，b，c和d，分別帶權(quán)7，5，2和4。構(gòu)造如下圖所示的三棵二叉樹，它們的帶權(quán)路徑長度分別為： (a)WPL=7*2+5*2+2*2+4*2=36(b)WPL=7*3+5*3+2*1+4*2=46(c)WPL=7*1+5*2+2*3+4*3=35 同等條件下同等條件下,C圖二叉樹的帶權(quán)路徑長度最短圖二叉樹的帶權(quán)路徑長度最短將將C稱為最優(yōu)二叉樹或哈夫曼樹稱為最優(yōu)二叉樹或哈夫曼樹最優(yōu)二叉樹或哈夫曼樹的定義 在權(quán)為wl，w2，wn的n個(gè)葉子所構(gòu)成的所有二叉樹中，帶權(quán)路徑長度最小(即代價(jià)最小)的二叉樹稱為最優(yōu)二叉樹或哈夫曼樹。 最優(yōu)二叉樹最優(yōu)二叉樹( (哈夫曼樹哈夫曼樹) ) 結(jié)論: (1) 最優(yōu)二叉樹中，權(quán)越大的葉子離根越近。 (2) 最優(yōu)二叉樹的形態(tài)