第5章 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ).ppt

1、第5章 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ),5.1 引言 5.2 線性結(jié)構(gòu) 5.3 樹形結(jié)構(gòu) *5.4 圖形結(jié)構(gòu) 5.5 內(nèi)部排序 5.6 檢索（查找）,5.1 引言,5.1.1 什么是數(shù)據(jù)結(jié)構(gòu) 5.1.2 數(shù)據(jù)的邏輯結(jié)構(gòu) 5.1.3 數(shù)據(jù)的存儲結(jié)構(gòu) 5.1.4 數(shù)據(jù)的運(yùn)算,應(yīng)用舉例學(xué)籍檔案管理,學(xué)生信息表： 每個學(xué)生的信息占一行，結(jié)構(gòu)類型 表中依據(jù)學(xué)號的大小存在著一種前后關(guān)系，即線性結(jié)構(gòu) 操作通常是插入、刪除、更新某個學(xué)生的信息，和按條件檢索某個學(xué)生的信息等,其它應(yīng)用舉例,計算機(jī)和人對奕問題 對弈的規(guī)則和策略-算法 棋盤及棋盤的格局-模型、樹 多叉路口交通燈的管理問題 路口、通路、交通燈顏色-圖,5.1.1 什么

2、是數(shù)據(jù)結(jié)構(gòu),研究數(shù)據(jù)之間的相互關(guān)系 邏輯結(jié)構(gòu) 存儲結(jié)構(gòu)（物理結(jié)構(gòu)） 數(shù)據(jù)的運(yùn)算 數(shù)據(jù)類型 原子類型 - 不可分解 結(jié)構(gòu)類型 - 原子類型構(gòu)造而成,5.1.2數(shù)據(jù)的邏輯結(jié)構(gòu),5.1.3 數(shù)據(jù)的存儲結(jié)構(gòu),數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)存儲器中的實現(xiàn)，也稱物理結(jié)構(gòu) 順序映射方式 鏈接映射方式 索引映射方式 散列映射方式,1、 順序存儲,用一組連續(xù)地址依次存儲類型相同、有序的數(shù)據(jù)元素的集合 可以采用索引的方式訪問其中的元素 一維數(shù)組描述 數(shù)組名稱為b 用b0表示第一個元素 用b1表示第二個元素 內(nèi)的數(shù)是元素的索引下標(biāo) 可以是常量也可以是變量 也可以用循環(huán)結(jié)構(gòu)訪問數(shù)組元素,插入,刪除,2、鏈?zhǔn)酱鎯?鏈表是一個鏈

3、式存儲的線性表 鏈表將物理上不連續(xù)的結(jié)點連接起來 鏈表中的每個元素習(xí)慣上被稱為結(jié)點，結(jié)點包含兩部分： 數(shù)據(jù) 指針(指針即是存儲下一個相同類型元素的地址) 鏈表包括單鏈表、雙鏈表、循環(huán)鏈表，在此只討論單鏈表,單鏈表,即每個節(jié)點僅有一個指向后繼節(jié)點的鏈 通常使用一個指針變量指向第一個元素，稱為鏈表的頭指針 通過頭指針可以順序訪問其后的所有節(jié)點 鏈表的最后一個元素包含一個空指針，標(biāo)識鏈表的結(jié)束,鏈表的操作,對鏈表的操作很多： 插入節(jié)點 刪除節(jié)點 查找列表 檢索列表 遍歷列表 ,注意： （1）當(dāng)向表尾插入、向表頭插入、向空表插入節(jié)點時，要做特殊處理 （2）刪除第一個節(jié)點、只有一個節(jié)點時，要做特殊處理,

4、5.1.4 數(shù)據(jù)的運(yùn)算,5.2 線性結(jié)構(gòu),5.2.1 線性表 5.2.2 棧 5.2.3 隊列,5.2.1 線性表,線性表是一個列表，列表內(nèi)每個元素都有唯一的前驅(qū)和后繼元素(除去最開始和末尾的元素) 線性表具有順序結(jié)構(gòu) 存儲 順序、鏈表 計算機(jī)應(yīng)用 一元多項式，如7+3x+9x8,5.2.2 棧,棧是一種線性表，對棧的添加和刪除只能在“棧頂”進(jìn)行 棧頂、棧底 “后進(jìn)先出”原則,棧的“后進(jìn)先出”原則,1、入棧push 若沒有足夠的空間，不能添加元素（溢） 棧頂添加新的元素 新的元素成為棧頂,2、出棧pop 當(dāng)棧為空時不能執(zhí)行出棧操作 將棧頂元素移走并返回給用戶,棧的應(yīng)用,代數(shù)表達(dá)式中的括號匹配的

5、檢驗 遇到左括號時入棧，遇到右括號時讓左括號出棧并刪除 如果棧最后非空，表明左括號多了 如果遇到右括號而棧已經(jīng)空了，表明右括號多了 迷宮求解 表達(dá)式求值,5.2.3 隊列,隊列也是一種線性表 數(shù)據(jù)只能在稱為“尾部”的一端插入，只能從稱為“頭部”的一端刪除 “先進(jìn)先出”原則,5.3 樹形結(jié)構(gòu),5.3.1 樹及其遍歷 5.3.2 二叉樹 5.3.3 遍歷二叉樹,5.3.1 樹及其遍歷,樹包括一組有限的元素，這些元素稱為結(jié)點；同時包括一組有向線段，用來連接結(jié)點，稱為分支。 一個結(jié)點的子樹個數(shù)稱為該結(jié)點的度數(shù),度為0的結(jié)點 稱為葉子,父：A 子：C、D 兄弟：E、F,數(shù)的遍歷,遍歷就是按一定的次序系統(tǒng)

6、地訪問樹的所有結(jié)點，并且只訪問一次 樹的線性化 遍歷方法： 深度優(yōu)先 先根次序 后根次序 廣度優(yōu)先 按層次遍歷,5.3.2 二叉樹,二叉樹是結(jié)點的有限集合，它或為空集，或為由一個根結(jié)點和兩棵互不相交的稱為左右的二叉樹構(gòu)成 樹至少有一個結(jié)點，而二叉樹可以為空 樹的子樹不分次序，二叉樹的子樹有左右之分 二叉樹的任何一個節(jié)點只能有0、1或2棵子樹 二叉樹的存儲：鏈接方式 一般先把樹或森林轉(zhuǎn)換為一顆二叉樹，再進(jìn)行存儲和運(yùn)算 只保留父到第一個子結(jié)點的連線，作為左子樹 子結(jié)點的兄弟依次連線，作為右子樹,基本形態(tài),二叉樹的性質(zhì),深度：樹中結(jié)點的最大層次 深度為k的二叉樹的結(jié)點總數(shù)最大為2k-1 第i層的結(jié)點

7、數(shù)最大為2i-1 具有n個結(jié)點的完全二叉樹的深度為 int（log2n）+1 任何一個二叉樹T，若其葉子為n0個，而度數(shù)為2的結(jié)點數(shù)為n2，則n0=n2+1,特殊的二叉樹,1.平衡二叉樹 平衡因子：二叉樹中任一結(jié)點的右子樹與左子樹的深度之差 平衡二叉樹：所有結(jié)點的平衡因子為0,1,-1 2.滿二叉樹 一個深度為k的二叉樹有2k-1個結(jié)點 3.完全二叉樹 n個結(jié)點有k+1層，其中2k-1個結(jié)點在前k層，剩下的結(jié)點從左向右排列在第k+1層,5.3.3 遍歷二叉樹,遍歷二叉樹是按照預(yù)定的順序處理每一個節(jié)點且僅處理一次 先根順序遍歷：中左右 中根順序遍歷：左中右 后根順序遍歷：左右中,先根遍歷(DLR

8、),首先訪問根，再訪問左子樹，最后訪問右子樹。,ABCDEF,中序遍歷(LDR),首先處理左子樹，再訪問根，最后訪問右子樹。,CBDAEF,后序遍歷(LRD),首先處理左子樹，再訪問右子樹，最后訪問根。,CDBFEA,練習(xí),一棵二叉數(shù)共有10個節(jié)點（分別用A、BJ表示），已知樹的中序遍歷結(jié)果為：DHBEAFCIGJ，先序遍歷結(jié)果為：ABDHECFGIJ?；卮鹣铝袉栴}。 請畫出這棵二叉樹。 寫出該樹的后序遍歷結(jié)果。,HDEBFIJGCA,*5.4 圖形結(jié)構(gòu),5.4.1 圖的概念 5.4.2 圖的存儲表示法 5.4.3 圖的遍歷和生成樹,5.4.1 圖的概念,圖：節(jié)點和線段的集合，節(jié)點稱為頂點，線

9、段稱為線，線用于連接一對頂點。 有向圖：每條線有一個方向(箭頭)指向后繼節(jié)點，有向圖中線稱為弧，弧的流向只能朝一個指定的方向。 無向圖：線是沒有方向的，線被稱為邊，頂點間的流向可以是任意方向。,術(shù)語,結(jié)點的度是連接到結(jié)點的線的數(shù)量。有向圖中出度是離開結(jié)點的弧的數(shù)量，入度是進(jìn)入結(jié)點的弧的數(shù)量。 如果兩個結(jié)點之間有路徑相連，則稱它們是連通的。如果所有結(jié)點之間都是連通的，不考慮方向，則該圖稱為連通的。 在有向圖中，如果每個結(jié)點都有通往其它結(jié)點的路徑，稱該圖是強(qiáng)連通的。 在有向圖中，如果至少兩個結(jié)點是不連通的，則有向圖是弱連通的。,5.4.2 圖的存儲表示法,邊上的值表示權(quán)，如表示距離、成本等含義,5

10、.4.3 圖的遍歷和生成樹,在給定的圖中從任一結(jié)點出發(fā)，系統(tǒng)地訪問圖中的每一個結(jié)點一次，稱為圖的遍歷 1、深度優(yōu)先遍歷 有向圖 ， 無向圖 ， 2、廣度優(yōu)先遍歷 從結(jié)點出度：、 從結(jié)點出度：、,5.5 內(nèi)部排序,5.5.1 簡單插入排序 5.5.2 簡單選擇排序 5.5.3 冒泡排序,5.5.1 簡單插入排序,列表被分成兩個子列表：已排序和未排序的 初始時已排序部分為空 每次掃描過程中： 取出未排序列表中的第一個元素 然后轉(zhuǎn)到已排序列表中，將其插入到合適的位置上 每次掃描后，未排序列表增加1個，已排序列表減少1個 對于n個數(shù)據(jù)，需要進(jìn)行n-1次掃描,插入排序示意,5.5.2 簡單選擇排序,列表

11、被分成兩個子列表：已排序和未排序的；初始時已排序部分為空。 排序時，從未排序列表中找到最小元素，與第一個元素交換。 經(jīng)過選擇和交換后，將未排序列表中的第一個元素劃入排序列表中，這一過程稱為一次掃描。 每次掃描后，未排序列表減少一個元素，已排序列表增加一個元素。 對于n個數(shù)據(jù)，需要進(jìn)行n-1次掃描。,選擇排序示意,5.5.3 冒泡排序,列表被分成兩個子列表：已排序和未排序的；初始時已排序部分為空。 在未排序的子列表中，最小的元素通過冒泡的方法選出來并移動到已排序子列表中，這一過程稱為一次掃描。每次掃描，未排序元素增加1個，已排序元素減少1個。 冒泡時，進(jìn)行兩兩比較，如果前者較大，則交換數(shù)據(jù)。 對

12、于n個數(shù)據(jù)，需要進(jìn)行n-1次掃描。,冒泡排序示意,5.6 檢索（查找）,查找實現(xiàn)在列表中確定目標(biāo)所在位置。查找通常返回具有要查找目標(biāo)值的第一個元素的位置(索引) 5.6.1 順序檢索 5.6.2 二分法檢索 5.6.3 分塊檢索* 5.6.4 散列表檢索*,5.6.1 順序檢索（查找）,用于查找無序列表，一般用這種方法查找規(guī)模較小的列表。 順序查找從表頭開始逐個元素查找，當(dāng)找到目標(biāo)元素或查找完整個列表時，查找過程結(jié)束。,順序查找示意,順序查找示意,5.6.2 二分法檢索（折半查找）,順序查找很慢，尤其當(dāng)列表中數(shù)據(jù)非常多時，逐個元素比較非常費(fèi)時。當(dāng)列表有序時，可采用效率非常高的折半查找算法。 折半查找時，先測試中間元素，可以判斷出目標(biāo)在列表的前半部分還是后半部分。如果在前半部分，則不用比較后半部分?jǐn)?shù)據(jù)，排除掉一