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

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

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

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

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

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

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

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

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

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

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