1、12數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。通俗解釋：數(shù)據(jù)相當(dāng)于書(shū)通俗解釋：數(shù)據(jù)相當(dāng)于書(shū). . 計(jì)算機(jī)相當(dāng)于書(shū)架，存放了很多書(shū)，書(shū)架分為計(jì)算機(jī)相當(dāng)于書(shū)架，存放了很多書(shū)，書(shū)架分為很多格子，書(shū)存放在不同格子（內(nèi)存空間，對(duì)應(yīng)一個(gè)地址），中。很多格子，書(shū)存放在不同格子（內(nèi)存空間，對(duì)應(yīng)一個(gè)地址），中。為了更快的取到想要的書(shū)為了更快的取到想要的書(shū), ,要用特定的存放方式要用特定的存放方式數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)3線性表線性表線性表：線性表：n n個(gè)數(shù)據(jù)元素的有序集合，個(gè)數(shù)據(jù)元素的有序集合，“連成線的連成線的”是一種是一種常用的數(shù)據(jù)結(jié)構(gòu)。其中數(shù)據(jù)元素

2、之間的關(guān)系通常是一對(duì)一常用的數(shù)據(jù)結(jié)構(gòu)。其中數(shù)據(jù)元素之間的關(guān)系通常是一對(duì)一的關(guān)系，即除了第一個(gè)和最后一個(gè)數(shù)據(jù)元素之外，其它數(shù)的關(guān)系，即除了第一個(gè)和最后一個(gè)數(shù)據(jù)元素之外，其它數(shù)據(jù)元素都是首尾相接的據(jù)元素都是首尾相接的 實(shí)際應(yīng)用中常見(jiàn)的特殊線性表：棧、隊(duì)列、字符串、一維數(shù)組4非線性表非線性表非線性表：各個(gè)數(shù)據(jù)元素不再保持在一個(gè)線性序列中，每非線性表：各個(gè)數(shù)據(jù)元素不再保持在一個(gè)線性序列中，每個(gè)數(shù)據(jù)元素可能與零個(gè)或者多個(gè)其他數(shù)據(jù)元素發(fā)生聯(lián)系個(gè)數(shù)據(jù)元素可能與零個(gè)或者多個(gè)其他數(shù)據(jù)元素發(fā)生聯(lián)系 主要代表：樹(shù)、圖結(jié)構(gòu)、多維數(shù)組 5鏈表鏈表 鏈?zhǔn)且环N存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，通過(guò)鏈鏈?zhǔn)且环N存儲(chǔ)單元上非連

3、續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，通過(guò)鏈表中的指針依次訪問(wèn)數(shù)據(jù)。表中的指針依次訪問(wèn)數(shù)據(jù)。 鏈表由一系列結(jié)點(diǎn)（鏈表中每一個(gè)元素稱為結(jié)點(diǎn)）組成，鏈表由一系列結(jié)點(diǎn)（鏈表中每一個(gè)元素稱為結(jié)點(diǎn)）組成，數(shù)據(jù)元素可根據(jù)需要實(shí)時(shí)添加、動(dòng)態(tài)生成。數(shù)據(jù)元素可根據(jù)需要實(shí)時(shí)添加、動(dòng)態(tài)生成。 由于非連續(xù)，鏈表無(wú)法隨機(jī)讀取，需要通過(guò)指針依次訪問(wèn)，查找數(shù)據(jù)時(shí)間長(zhǎng)。 6棧棧 棧是棧是只能在某一端插入和刪只能在某一端插入和刪除除的數(shù)據(jù)結(jié)構(gòu)。的數(shù)據(jù)結(jié)構(gòu)。 （想象用桶堆積物品，先堆進(jìn)來(lái)的壓在底下，隨后一件件往上堆。取走時(shí)，只能從上面一件件取。堆和取都在頂部進(jìn)行，底部一般是不動(dòng)的。） 棧進(jìn)行刪除和插入的一端稱棧頂棧頂，另一堆稱棧底棧底。插入一般

4、稱為進(jìn)棧（PUSH），刪除則稱為退棧（POP）。 棧的特征是“后進(jìn)先出后進(jìn)先出”7棧棧一個(gè)棧可以用定長(zhǎng)為的數(shù)組來(lái)表示用一個(gè)棧指針TOP指向棧頂。若TOP0，表示棧空，TOP=N時(shí)棧滿。進(jìn)棧時(shí)TOP加。退棧時(shí)TOP減。當(dāng)TOP0）個(gè)元素組成的有限集合，其中： （1）每個(gè)元素稱為結(jié)點(diǎn)結(jié)點(diǎn) （2）有且僅有一個(gè)特定的結(jié)點(diǎn)，稱為根結(jié)點(diǎn)或樹(shù)根根結(jié)點(diǎn)或樹(shù)根 （3）除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)能分成m（m=0）個(gè)互不相交的有限集合 T0,T1,T2,Tm-1。其中的每個(gè)子集又都是一棵樹(shù)，這些集合稱為這棵樹(shù)的子樹(shù)。2 2的子的子節(jié)點(diǎn)節(jié)點(diǎn)5 5，6 6的父的父節(jié)點(diǎn)節(jié)點(diǎn)根節(jié)點(diǎn)根節(jié)點(diǎn)2 2的兄弟的兄弟12樹(shù)樹(shù) 一個(gè)結(jié)點(diǎn)的子樹(shù)

5、個(gè)數(shù)，稱為這個(gè)結(jié)點(diǎn)的一個(gè)結(jié)點(diǎn)的子樹(shù)個(gè)數(shù)，稱為這個(gè)結(jié)點(diǎn)的度度 如：結(jié)點(diǎn)1的度為3，結(jié)點(diǎn)3的度為0 度為度為0 0的結(jié)點(diǎn)稱為的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)葉結(jié)點(diǎn) 如：結(jié)點(diǎn)3、5、6、8、9 度不為度不為0 0的結(jié)點(diǎn)稱為的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)分支結(jié)點(diǎn) 如：結(jié)點(diǎn)1、2、4、7 根以外的分支結(jié)點(diǎn)又稱為根以外的分支結(jié)點(diǎn)又稱為內(nèi)部結(jié)點(diǎn)內(nèi)部結(jié)點(diǎn) 如：結(jié)點(diǎn)2、4、7 樹(shù)中各結(jié)點(diǎn)的度的最大值稱為樹(shù)中各結(jié)點(diǎn)的度的最大值稱為這棵樹(shù)的度這棵樹(shù)的度 右側(cè)這顆樹(shù)度為33）。13樹(shù)樹(shù) 樹(shù)節(jié)點(diǎn)的樹(shù)節(jié)點(diǎn)的層次層次從根開(kāi)始定義，根從根開(kāi)始定義，根結(jié)點(diǎn)的層次為結(jié)點(diǎn)的層次為1 1 其它結(jié)點(diǎn)的層次等于它的父結(jié)其它結(jié)點(diǎn)的層次等于它的父結(jié)點(diǎn)層次加點(diǎn)層次加1

6、1 如：根節(jié)點(diǎn)層次為1，結(jié)點(diǎn)2、3、4的層次為2，結(jié)點(diǎn)5、6、7的層次為3，結(jié)點(diǎn)8、9的層次為4。 一棵樹(shù)中所有的結(jié)點(diǎn)的層次的最一棵樹(shù)中所有的結(jié)點(diǎn)的層次的最大值稱為樹(shù)的深度（或高度大值稱為樹(shù)的深度（或高度） 如：這棵樹(shù)的深度為4。14二叉樹(shù)二叉樹(shù) 二叉樹(shù)是一種特殊的樹(shù)型結(jié)構(gòu)，它是最大度數(shù)為最大度數(shù)為2 2的樹(shù)。 它的兩棵子樹(shù)分別稱為左子樹(shù)、右子樹(shù) 。 二叉樹(shù)的每個(gè)結(jié)點(diǎn)最多有兩個(gè)子結(jié)點(diǎn)。每個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)分別稱為左孩子、右孩子，。二叉樹(shù)有5中基本形態(tài)：15二叉樹(shù)的性質(zhì)二叉樹(shù)的性質(zhì)【性質(zhì)1】在二叉樹(shù)的第i層上最多有2i1個(gè)結(jié)點(diǎn)（i=1）。 【性質(zhì)2】深度（高度）為k的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)（k=

7、1）。16二叉樹(shù)的性質(zhì)二叉樹(shù)的性質(zhì)【性質(zhì)3】N=n0+n1+n2 【性質(zhì)4】n0=n2+1設(shè)二叉樹(shù)中度為0,1,2的結(jié)點(diǎn)分別有no,n1,n2個(gè),總結(jié)點(diǎn)數(shù)為N.17樹(shù)的遍歷樹(shù)的遍歷 在應(yīng)用樹(shù)結(jié)構(gòu)解決問(wèn)題時(shí)，往往要求按照某種在應(yīng)用樹(shù)結(jié)構(gòu)解決問(wèn)題時(shí)，往往要求按照某種次序獲得樹(shù)中全部結(jié)點(diǎn)的信息，這種操作叫作樹(shù)次序獲得樹(shù)中全部結(jié)點(diǎn)的信息，這種操作叫作樹(shù)的遍歷。遍歷的方法有多種，的遍歷。遍歷的方法有多種，以以二叉樹(shù)為例二叉樹(shù)為例18樹(shù)的遍歷 先序遍歷先序遍歷先序（根）遍歷： (1)先訪問(wèn)根結(jié)點(diǎn) 先序遍歷左子樹(shù) 先序遍歷右子樹(shù) 如右圖先序遍歷的結(jié)果為： a b d e h i c f g 19樹(shù)的遍歷 中

8、序遍歷中序遍歷中序（根）遍歷： 中序遍歷左子樹(shù) 訪問(wèn)處理根結(jié)點(diǎn) 中序遍歷右子樹(shù)如右圖中序遍歷的結(jié)果為：d b h e i a f c g 20樹(shù)的遍歷 后序遍歷后序遍歷后序（根）遍歷： 后序遍歷左子樹(shù) 后序遍歷右子樹(shù) 訪問(wèn)處理根結(jié)點(diǎn)如上圖后序遍歷的結(jié)果為：d h i e b f g c a 21樹(shù)的遍歷 層次遍歷層次遍歷層次遍歷： 按層次從小到大逐個(gè)訪問(wèn)，同一層次按照從左到右的次序。如右圖層次遍歷的結(jié)果為：h I d e f g b c a22練習(xí)1、二叉樹(shù)T，已知其前序遍歷序列為1 2 4 35 7 6，中序遍歷序列為4 2 1 5 7 3 6，則其后序遍歷序列為（ B ） 。 A. 4 2

9、 5 7 6 3 1 B. 4 2 7 5 6 3 1C. 4 2 7 5 3 6 1 D. 4 7 2 3 5 6 12223圖圖通俗說(shuō)，各頂點(diǎn)用邊連起來(lái)就叫做圖通俗說(shuō)，各頂點(diǎn)用邊連起來(lái)就叫做圖圖和樹(shù)的區(qū)別？圖和樹(shù)的區(qū)別？（1）樹(shù)形結(jié)構(gòu)中，每一個(gè)數(shù)據(jù)有可能有多個(gè)下層結(jié)點(diǎn)（孩子結(jié)點(diǎn)），但卻只與一個(gè)上層結(jié)點(diǎn)相關(guān)。（2）圖形結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中任意兩個(gè)數(shù)據(jù)之間都可能相關(guān)。 24圖圖 1 2 3 4 5 (a) 1 2 3 4 5 (b)(a)(a)有向圖：有向圖： 圖的邊有方向，只能按箭頭方向從一點(diǎn)到另一點(diǎn)。(a)就是一個(gè)有向圖。(b)(b)無(wú)向圖：無(wú)向圖： 圖的邊沒(méi)有方向，可

10、以雙向。(b)就是一個(gè)無(wú)向圖。25結(jié)點(diǎn)的度：結(jié)點(diǎn)的度： 無(wú)向圖中與結(jié)點(diǎn)相連的邊的數(shù)目，稱為結(jié)點(diǎn)的度。 有向圖中結(jié)點(diǎn)的度等于該結(jié)點(diǎn)的入度和出度之和結(jié)點(diǎn)的入度：結(jié)點(diǎn)的入度：在有向圖中，以這個(gè)結(jié)點(diǎn)為終點(diǎn)的有向邊的數(shù)目。結(jié)點(diǎn)的出度：結(jié)點(diǎn)的出度：在有向圖中，以這個(gè)結(jié)點(diǎn)為起點(diǎn)的有向邊的數(shù)目。 1 2 3 4 5 (a) 1 2 3 4 5 (b)26圖的遍歷圖的遍歷（1 1）深度優(yōu)先遍歷）深度優(yōu)先遍歷 從圖中某個(gè)頂點(diǎn)v0出發(fā)，然后搜索V0的一個(gè)鄰接點(diǎn)Vi,若Vi未被訪問(wèn)，則訪問(wèn)之.再搜索Vi的一個(gè)鄰接點(diǎn)按此方式訪問(wèn)。若某頂點(diǎn)的鄰接點(diǎn)全部訪問(wèn)完畢，則回到它的上一頂點(diǎn)，然后再?gòu)拇隧旤c(diǎn)又按深度優(yōu)先的方法搜索下去，直到訪問(wèn)完畢為止 深度優(yōu)先遍歷得到的序列為：深度優(yōu)先遍歷得到的序列為： 0-1-3-7-4-2-5-60-1-3-7-4-2-5-627圖的遍歷圖的遍歷（2 2）廣度優(yōu)先遍歷）廣度優(yōu)先遍歷類似樹(shù)的按層次遍歷，從圖的某個(gè)頂點(diǎn)v0出發(fā)，訪問(wèn)了v0之后，依次訪問(wèn)與v0相鄰的