第6章算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)(參考版)
2025-08-04 15:11本頁面
【正文】 依此類推 ， 直到最后一個元素插入到有序序列中 ， 形成 n個元素組成的有序序列 。 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 吉林大學公共計算機教學與研究中心制作 86/82 ① 將待排序序列中第一個元素作為有序序列 ， 將第二個元素插入到有序序列中 ，形成由兩個元素組成的有序序列 。 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 吉林大學公共計算機教學與研究中心制作 84/82 原序列： 42 23 16 27 11 45 13 49 選擇排序法 第 1遍選擇 42 23 16 27 11 45 13 49 11 23 16 27 42 45 13 49 第 2遍選擇 11 13 16 27 42 45 23 49 第 3遍選擇 11 13 16 27 42 45 23 49 第 4遍選擇 11 13 16 23 42 45 27 49 第 5遍選擇 11 13 16 23 27 45 42 49 第 6遍選擇 11 13 16 23 27 42 45 49 第 7遍選擇 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 吉林大學公共計算機教學與研究中心制作 85/82 3插入排序法 插入排序是不斷地將待排序的元素插入到前面的有序序列中 , 直至所有元素都進入有序序列 。 每次從 待 排序數(shù)據(jù)序列中 ， 選擇出 最小 元素并定位到待排序 (升序 )序列最前面 。 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 吉林大學公共計算機教學與研究中心制作 82/82 交換排序法 原序列： 42 23 16 47 11 45 13 49 42 23 16 47 11 45 13 49 第 1 遍 第 2遍 第 3遍 第 4遍 第 5遍 第 6遍 23 16 42 11 45 47 13 49 16 23 11 42 45 13 47 49 16 23 11 42 45 13 47 49 11 23 16 13 45 42 47 49 11 13 16 23 45 42 47 49 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 吉林大學公共計算機教學與研究中心制作 83/82 2選擇排序法 簡單選擇排序法 的基本思想是： 1掃描整個序列 ， 從中選出最小元素 ， 將它 交換到最前面； 2再從剩余子序列中 ， 選出最小元素 ， 交換 到子序列最前面 。 三 類基本排序方法 交換排序法 選擇排序法 插入排序法 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 吉林大學公共計算機教學與研究中心制作 81/82 1交換排序法 在排序過程中 , 通過數(shù)據(jù)元素之間不斷地進行 比較 與 交換 , 最終達到排序目的。 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 吉林大學公共計算機教學與研究中心制作 79/82 例：在 有序順序表 (8， 15， 23， 46， 63， 71，80， 86， 88， 101)中 ， 用折半查找法查找值為 71 的數(shù)據(jù)元素 。 此題比較了 9次 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 吉林大學公共計算機教學與研究中心制作 78/82 2 二分查找 又稱 折半查找 , 要求 被查找的表采用順序存儲結(jié)構(gòu)且數(shù)據(jù)元素按數(shù)據(jù)值升序或降序排列 , 即二分查找法只適用于 有序表 。 特點：順序查找算法簡單 ,但是執(zhí)行效率較低 在下列兩種情況下 ,只能使用順序查找法： ① 線性表是線性鏈表。 ?從線性表中第一個元素 88開始 , 依次將 線性表中元素與 71進行比較 。 ? 若相等 ， 則查找成功； ? 若直到最后一個元素 ， 還沒找到與給定值相等的元素 ， 則查找失敗 。 若存在這樣數(shù)據(jù)元素 ,則查找成功；否則 ， 查找失敗 。 其中 查找 和排序 是數(shù)據(jù)處理中比較重要的算法 。 根據(jù)對根訪問的次序，二叉樹的遍歷分為 先序遍歷 、 中序遍歷 和 后序遍歷 。 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 吉林大學公共計算機教學與研究中心制作 69/82 二叉樹鏈式存儲 二叉樹每個結(jié)點由數(shù)據(jù)域和指針域組成 。 A C B E G D F A B C D E F G 1 2 3 4 5 6 7 按照完全二叉樹每個結(jié)點編號的順序存放結(jié)點 ,通過結(jié)點的編號準確地反映結(jié)點之間的邏輯關(guān)系 。 A T X C R B P S E Q F Y 1 2 3 4 5 6 7 10 11 9 8 12 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 吉林大學公共計算機教學與研究中心制作 67/82 二叉樹的順序存儲 二叉樹順序存儲是指用一組連續(xù)存儲單元存儲二叉樹中的結(jié)點 。 ? 2k=n時 , 編號為 k的結(jié)點的左子結(jié)點編號為 2k, 否則無左子結(jié)點。 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 吉林大學公共計算機教學與研究中心制作 66/82 完全二叉樹性質(zhì)： 性質(zhì) 二： 在有 n個結(jié)點的完全二叉樹中 , 將所有結(jié)點按從上到下 , 從左到右的順序用自然數(shù) 1, 2, … , n進行編號 , 則對于編號為 k的結(jié)點有如下結(jié)論： ? k=1時 , 該結(jié)點為根結(jié)點。 A T X C E M B P 15個結(jié)點的滿二叉樹 S D N F R Y Q 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 吉林大學公共計算機教學與研究中心制作 65/82 完全二叉樹性質(zhì)： 12個結(jié)點的完全二叉樹 A T X C R B P S E G F Y 性質(zhì)一： 具有 n個結(jié)點的完全二叉樹的深度為 ?log2n」+1。 每一層的結(jié)點數(shù)都達到最大值 , 葉子結(jié)點都在最下面的同一層上 完全二叉樹 一棵深度為 k的二叉樹 , 如果第一層到第k1層是一棵滿二叉樹 , 第 k層上的結(jié)點數(shù)沒有達到最大值 2k1, 但這些結(jié)點都滿放在該層 最左邊 , 則稱此二叉樹為完全二叉樹 。 1 2 3 4 樹中結(jié)點的最大層次稱為樹的 深度 或 高度 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 吉林大學公共計算機教學與研究中心制作 60/82 二叉樹 ? 非空二叉樹有且只有一個根結(jié)點； ? 每個結(jié)點最多有兩棵子樹 , 且 有左右之分 二叉樹是另一種樹形結(jié)構(gòu)，每個結(jié)點最多只有兩個后件 (即 最大度為 2)。 樹是 遞歸 定義的 ， 即一棵樹由根及若干子樹構(gòu)成 ， 每棵子樹又是由更小的子樹構(gòu)成 。 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 吉林大學公共計算機教學與研究中心制作 57/82 樹 樹是一種常用的 非線性結(jié)構(gòu) ， 樹是由n(n≥ 0)個結(jié)點組成的有限集合 。 0 2 3 1 0 2 1 3 4 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 吉林大學公共計算機教學與研究中心制作 54/82 循環(huán)隊列的運算 創(chuàng)建一個空隊列 ,并令 front= rear=0 1 3 2 4 0 front rear 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 吉林大學公共計算機教學與研究中心制作 55/82 S1: 先判斷隊列是否已滿，若隊滿則入隊失敗，否則元素入隊 S2: (rear+1)%n?rear當rear+1=n時 ， 0 ? rear S3:將新元素放在當前隊尾位臵 （ rear） 。 S3： 取 front所指元素 front rear 1 2 0 1 A B C 此時雖然隊列有空位置，但也不能插入新結(jié)點。 a3 top a1 a2 bottom 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 吉林大學公共計算機教學與研究中心制作 46/82 例如，容量為 6的棧中已有 3個元素 ,如圖所示： 1 2 3 4 5 6 A C B bottom top X、 Y兩個元素先后入棧 X Y 元素 Y出棧 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 吉林大學公共計算機教學與研究中心制作 47/82 隊 列 允許在一端進行插入 、 而在另一端進行刪除的 線性表 ， 允許插入的一端稱為 隊尾 ， 允許刪除的一端稱為 隊頭 。 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 吉林大學公共計算機教學與研究中心制作 44/82 入棧運算 S1： 如果 top=n， 則棧已滿 ， 提示入棧失敗(棧
研究報告相關(guān)推薦
鄂ICP備17016276號-1