vfp(第3版)課件：公共基礎(chǔ) 數(shù)據(jù)結(jié)構(gòu)與算法

1、算法是指解題方案的準(zhǔn)確而完整的描述。 算法例：計算三角形的面積的算法1.輸入底的長度值a2.輸入高的長度值b3.如果底和高都大于0進入步驟4，否則進 入步驟7 4. 計算面積值c=a*b/2 5. 屏幕輸出面積c 6. 結(jié)束7.顯示出錯例：把大象放進冰箱的算法。1.把冰箱打開2.把大象放進去3.把冰箱門關(guān)上算法的基本要素：1.對數(shù)據(jù)的運算和操作(運算符號和函數(shù))算術(shù)、邏輯、關(guān)系、數(shù)據(jù)傳輸 2.算法的控制結(jié)構(gòu)順序、選擇、循環(huán)程序舉例!算法4個特征：可行性確定性有窮性擁有足夠的情報。評價算法的優(yōu)劣：時間復(fù)雜度和空間復(fù)雜度 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)概念包括3個內(nèi)容：數(shù)據(jù)之間的邏輯關(guān)系（邏輯結(jié)構(gòu)）數(shù)據(jù)在計算機

2、中的存儲方式（存儲結(jié)構(gòu)）以及在這些數(shù)據(jù)上定義的運算的集合（數(shù)據(jù)的運算） 數(shù)據(jù)結(jié)構(gòu)算法只是描述數(shù)據(jù)運算的方法和過程，其具體實現(xiàn)的效率要以數(shù)據(jù)結(jié)構(gòu)為基礎(chǔ)。程序數(shù)據(jù)結(jié)構(gòu)算法數(shù)據(jù)結(jié)構(gòu)舉例：處理N個學(xué)生的學(xué)號邏輯結(jié)構(gòu)線性表： 07020001 07020002 07020003存儲結(jié)構(gòu)順序表： 數(shù)據(jù)的運算有：新增、刪除、查找學(xué)號070200030702000207020001邏輯結(jié)構(gòu)（描述數(shù)據(jù)之間的邏輯關(guān)系）：分類： 線性結(jié)構(gòu)線性結(jié)構(gòu) 非線性結(jié)構(gòu)非線性結(jié)構(gòu)分類：線性表線性表 *集合集合樹樹 *圖或網(wǎng)圖或網(wǎng)前件、后件的各種對應(yīng)關(guān)系決定不同的邏輯結(jié)構(gòu)。線性表線性表（注意前后件特征）（注意前后件特征）、普通線

3、性表（不限制操作）、棧（以先進后出的原則，只能在一端插入或刪除元素）*、隊列（以先進先出的原則，只能在兩端插入或刪除元素）*對線性表常用操作：對線性表常用操作： 插入新元素、刪除元素、讀取元素值、查找元素等節(jié)點線性表分類：線性表分類：一、一、棧棧 棧是一種特殊的線性表，在這種線性表中，一端是封棧是一種特殊的線性表，在這種線性表中，一端是封閉的，不允許插入與刪除元素，另一端是開口的，允許插閉的，不允許插入與刪除元素，另一端是開口的，允許插入與刪除元素。入與刪除元素。 棧頂：允許插入與刪除的一端稱為棧頂。棧頂：允許插入與刪除的一端稱為棧頂。 棧底：不允許插入與刪除的一端稱為棧底。棧底：不允許插入與

4、刪除的一端稱為棧底。 棧是根據(jù)棧是根據(jù)“先進后出先進后出”或或“后進先出后進先出“的原則組織數(shù)的原則組織數(shù)據(jù)的。據(jù)的。ana1a0棧頂棧頂棧底棧底棧結(jié)構(gòu)舉例：練習(xí)題： 棧底至棧頂依次存放元素A、B、C、D，在第五個元素E入棧前，棧中元素可以出棧，則出棧序列可能是_。棧底E技巧：判斷連續(xù)的兩個元素的進棧和出棧順序是否違背“先進后處原則”，如果違背就淘汰該選項。二、隊列二、隊列 隊列是一種特殊的線性表，在這種線性表中，需隊列是一種特殊的線性表，在這種線性表中，需要加入的元素總是插入到線性表的末尾，并且又總要加入的元素總是插入到線性表的末尾，并且又總是從線性表的頭部取出元素。即一端插入，另一端是從線

5、性表的頭部取出元素。即一端插入，另一端刪除的線性表。刪除的線性表。 隊尾：允許插入的一端隊尾：允許插入的一端 隊頭：允許刪除的一端隊頭：允許刪除的一端 隊列是按照隊列是按照“先進先出先進先出”或或“后進后出后進后出”的原則的原則組織數(shù)據(jù)的，體出了組織數(shù)據(jù)的，體出了“先來先服務(wù)先來先服務(wù)”的思想。的思想。 CABD對頭對頭對尾對尾隊列結(jié)構(gòu)舉例： 樹與二叉樹樹與二叉樹（注意前后件特征）（注意前后件特征）一、樹一、樹 樹是一種簡單的非線性結(jié)構(gòu)。在這種結(jié)構(gòu)中，所有數(shù)據(jù)樹是一種簡單的非線性結(jié)構(gòu)。在這種結(jié)構(gòu)中，所有數(shù)據(jù)元素之間的關(guān)系具有明顯的層次特性。元素之間的關(guān)系具有明顯的層次特性。計算機軟件計算機軟件

6、計算機學(xué)科計算機學(xué)科計算機應(yīng)用計算機應(yīng)用計算機網(wǎng)絡(luò)計算機網(wǎng)絡(luò)人工智人工智能能軟件理論軟件理論安全學(xué)安全學(xué)系統(tǒng)結(jié)構(gòu)系統(tǒng)結(jié)構(gòu)說明：在樹的圖形表示中，省略表示前后關(guān)系的箭頭，總是認為上端結(jié)點說明：在樹的圖形表示中，省略表示前后關(guān)系的箭頭，總是認為上端結(jié)點是前件，下端結(jié)點是后件。是前件，下端結(jié)點是后件。計算機學(xué)科計算機學(xué)科計算機應(yīng)用計算機應(yīng)用計算機網(wǎng)絡(luò)計算機網(wǎng)絡(luò)人工智能人工智能軟件理論軟件理論安全學(xué)安全學(xué)系統(tǒng)結(jié)構(gòu)系統(tǒng)結(jié)構(gòu)樹基本概念：根節(jié)點父節(jié)點子節(jié)點葉子節(jié)點節(jié)點的度樹的度(最大的節(jié)點度)子樹節(jié)點的層次樹的深度 二叉樹及其基本性質(zhì)二叉樹及其基本性質(zhì)二叉樹是具有以下兩個特點的樹：（1）非空二叉樹只有一個根

7、結(jié)點（2）每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹和右子樹（其他定義：每個結(jié)點的度最大為2的樹）二叉樹的基本性質(zhì)：性質(zhì)1 在二叉樹的第k層上，最多有2(k-1)個結(jié)點例題：一棵二叉樹第六層（根結(jié)點為第一層）的結(jié)點數(shù)最多為 _ 個。性質(zhì)2 深度為m的二叉樹最多有2m-1個結(jié)點ABCDE性質(zhì)性質(zhì)3 在任意一棵二叉樹中，度為在任意一棵二叉樹中，度為0的結(jié)點（葉子結(jié)的結(jié)點（葉子結(jié)點）總比度為點）總比度為2的結(jié)點多一個。的結(jié)點多一個。例題：例題：某二叉樹中度為2的結(jié)點有18個，則該二叉樹中有 【1】 個葉子結(jié)點性質(zhì)性質(zhì)4 具有具有n個結(jié)點的二叉樹，其深度至少為個結(jié)點的二叉樹，其深度至少為log

8、2n+1完全二叉樹：完全二叉樹：除最后一層外，每一層上的結(jié)點數(shù)均達到最大值；且除最后一層外，每一層上的結(jié)點數(shù)均達到最大值；且在最后一層只在右邊連續(xù)缺少結(jié)點在最后一層只在右邊連續(xù)缺少結(jié)點。ABCDABCDEEABCDFDABCF 滿二叉樹：滿二叉樹：所有層的節(jié)點數(shù)都達到最大值所有層的節(jié)點數(shù)都達到最大值A(chǔ)BCDEFG性質(zhì)性質(zhì)5 具有具有n個結(jié)點的完全二叉樹，其深度為個結(jié)點的完全二叉樹，其深度為log2n+1例題：設(shè)一棵完全二叉樹共有700個結(jié)點， 則在該二叉樹中有_個葉子結(jié)點。完全二叉樹性質(zhì)：當(dāng)完全二叉樹節(jié)點個數(shù)為奇數(shù)時，度為完全二叉樹性質(zhì)：當(dāng)完全二叉樹節(jié)點個數(shù)為奇數(shù)時，度為1的節(jié)點有的節(jié)點有0個

9、；偶個；偶 數(shù)時有數(shù)時有1個。個。兩個特殊的二叉樹：完全二叉樹、滿二叉樹兩個特殊的二叉樹：完全二叉樹、滿二叉樹abcdef二叉樹二叉樹 遍歷遍歷從根節(jié)點開始，遇到每個節(jié)點時，都遞歸使用以下步驟。前序遍歷： 、訪問根節(jié)點2、前序遍歷左子樹3、前序遍歷右子樹中序遍歷： 、中序遍歷左子樹2、訪問根節(jié)點3、中序遍歷右子樹后序遍歷： 、后序遍歷左子樹2、后序遍歷右子樹3、訪問根節(jié)點前序遍歷：從上方進入節(jié)點時，訪問該節(jié)點中序遍歷： 從左子樹回到節(jié)點時，訪問該節(jié)點后序遍歷： 從右子樹回到節(jié)點時，訪問該節(jié)點前序、中序、后序abcdef練習(xí)題：寫出前、中、后序遍歷以下二叉樹的遍歷順序。 從根節(jié)點開始，遇到每個節(jié)

10、點時，都遞歸使用以下步驟：前序遍歷： 、訪問根節(jié)點2、前序遍歷左子樹3、前序遍歷右子樹中序遍歷： 、中序遍歷左子樹2、訪問根節(jié)點3、中序遍歷右子樹后序遍歷： 、后序遍歷左子樹2、后序遍歷右子樹3、訪問根節(jié)點內(nèi)存內(nèi)存 20 21 22 23 24 25 20 21 22 23 24 25順序存儲順序存儲 20 21 23 24 25 .26鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯€性表線性表線性表的線性表的順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)和和鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點的優(yōu)缺點 20 21 22 23 24 25順序存儲：利于直接（隨機）存取元素，但不利于插入和刪除操作順序存儲：利于直接（隨機）存取元素，但不利于插入和刪除操作鏈?zhǔn)酱鎯Γ豪诓迦牒蛣h