信息學奧賽-數(shù)據(jù)結構-文檔資料

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

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

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

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

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

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

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

8、序遍歷中序遍歷中序（根）遍歷： 中序遍歷左子樹 訪問處理根結點 中序遍歷右子樹如右圖中序遍歷的結果為：d b h e i a f c g 20樹的遍歷 后序遍歷后序遍歷后序（根）遍歷： 后序遍歷左子樹 后序遍歷右子樹 訪問處理根結點如上圖后序遍歷的結果為：d h i e b f g c a 21樹的遍歷 層次遍歷層次遍歷層次遍歷： 按層次從小到大逐個訪問，同一層次按照從左到右的次序。如右圖層次遍歷的結果為：h I d e f g b c a22練習1、二叉樹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圖圖通俗說，各頂點用邊連起來就叫做圖通俗說，各頂點用邊連起來就叫做圖圖和樹的區(qū)別？圖和樹的區(qū)別？（1）樹形結構中，每一個數(shù)據(jù)有可能有多個下層結點（孩子結點），但卻只與一個上層結點相關。（2）圖形結構中，結點之間的關系可以是任意的，圖中任意兩個數(shù)據(jù)之間都可能相關。 24圖圖 1 2 3 4 5 (a) 1 2 3 4 5 (b)(a)(a)有向圖：有向圖： 圖的邊有方向，只能按箭頭方向從一點到另一點。(a)就是一個有向圖。(b)(b)無向圖：無向圖： 圖的邊沒有方向，可

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