《《算法與數(shù)據(jù)結(jié)構(gòu)》PPT課件.ppt》由會員分享，可在線閱讀，更多相關(guān)《《算法與數(shù)據(jù)結(jié)構(gòu)》PPT課件.ppt（33頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、第七章 算法與數(shù)據(jù)結(jié)構(gòu),,數(shù)據(jù)結(jié)構(gòu),一、 數(shù)據(jù)結(jié)構(gòu)與算法 二、 數(shù)組與線性表 三、 棧 四、 隊(duì)列 五、 樹、二叉樹,一、 數(shù)據(jù)結(jié)構(gòu)與算法,數(shù)據(jù)(Data)： 一切能夠由計(jì)算機(jī)接受和處理的對象。 數(shù)據(jù)結(jié)構(gòu)(Data structure)： 數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。研究數(shù)據(jù)結(jié)構(gòu)，是指研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu) 邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系 線性結(jié)構(gòu)：線性表、堆棧、隊(duì)列、數(shù)組、串等都是線性結(jié)構(gòu)。 非線性結(jié)構(gòu)：如樹形結(jié)構(gòu)、圖等。 物理結(jié)構(gòu)：數(shù)據(jù)元素在計(jì)算機(jī)存儲器中是如何存儲的,,算法(Algorithm)：對特定問題求解步驟的一種描述。 算法是一個(gè)有窮的規(guī)則序列，這些規(guī)

2、則決定了解決某一特定問題的一系列運(yùn)算。由此問題相關(guān)的一定輸入，計(jì)算機(jī)依照這些規(guī)則進(jìn)行計(jì)算和處理，經(jīng)過有限的計(jì)算步驟后能得到一定的輸出。,算法的復(fù)雜度,算法的復(fù)雜性包括時(shí)間復(fù)雜性（所需運(yùn)算時(shí)間）和空間復(fù)雜性（所占內(nèi)存儲空間），重點(diǎn)是時(shí)間復(fù)雜性 。 一個(gè)算法所需的運(yùn)算時(shí)間通常與所解決問題的規(guī)模大小有關(guān)。用n 表示問題規(guī)模的量 ，把算法運(yùn)行所需的時(shí)間T表示為n的函數(shù)，記為T(n)。 不同的T(n)算法，當(dāng)n增長時(shí)，運(yùn)算時(shí)間增長的快慢很不相同。,算法的運(yùn)行時(shí)間往往還與具體輸入的數(shù)據(jù)有關(guān)，通常用以下兩種方法來確定一個(gè)算法的運(yùn)算時(shí)間： 1. 平均時(shí)間復(fù)雜性： 研究同樣的n值時(shí)各種可能的輸入，取它們

3、運(yùn)算時(shí)間的平均值。 2. 最壞時(shí)間復(fù)雜性： 研究各種輸入中運(yùn)算最慢的一種情況下的運(yùn)算時(shí)間。,評價(jià)算法的一般原則,正確性：算法應(yīng)能正確地實(shí)現(xiàn)處理要求 。 易讀性：有助于對算法的理解，便于糾正和擴(kuò)充 。 簡單性：使證明其正確性比較容易，對算法進(jìn)行修改也比較方便。 高效率：達(dá)到所需的時(shí)、空性能。,算法必須滿足以下準(zhǔn)則,有窮性：一個(gè)算法的執(zhí)行步驟必須是有限的。 確定性：算法中的每一個(gè)操作步驟的含義必須明確。 可行性：算法中的每一個(gè)操作步驟都是可以執(zhí)行的。 輸入：一個(gè)算法一般都要求有一個(gè)或多個(gè)輸入量(個(gè)別的算法不要求輸入量)。這些輸人量是算法所需的初始數(shù)據(jù)。,,1.下面敘述正確的是______。 A.

4、 算法的執(zhí)行效率與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)。 B. 算法的空間復(fù)雜度是指算法程序中指令（或語句）的條數(shù)（指的是算法所占用的空間）。 C. 算法的有窮性是指算法必須能在執(zhí)行有限個(gè)步驟之后終止。 D. 以上三種描述都不對。,答案 C,二、 數(shù)組與線性表,數(shù)組 數(shù)組是由一些單元組成的，每個(gè)單元對應(yīng)著一組下標(biāo)值和一個(gè)數(shù)組元素。在計(jì)算機(jī)中，表示數(shù)組是采用一組連續(xù)的存儲單元順序地存儲各數(shù)組元素。數(shù)組元素可以是基本數(shù)據(jù)類型，如整數(shù)型、實(shí)數(shù)型、字符型等，同一數(shù)組中各個(gè)元素必須是同一數(shù)據(jù)類型，每個(gè)數(shù)組元素都占有相同數(shù)量的存儲單元。,線性表,線性表是由有限數(shù)目的相同類型元素組成的序列。表中的數(shù)據(jù)元素，除了第一個(gè)和最

5、后一個(gè)以外，都有一個(gè)且只有一個(gè)前驅(qū)元素，同時(shí)也都有一個(gè)且只有一個(gè)后繼元素； 線性表的元素個(gè)數(shù)n稱為這個(gè)表的長度，當(dāng)n=0時(shí)，這個(gè)表叫做空表。,單鏈表,三、棧,1.定義：限定只在表的一端(表尾)進(jìn)行插入和刪除操作的線性表 特點(diǎn):后進(jìn)先出(LIFO)，允許插入和刪除的一端稱為棧頂 (top)，另一端稱為棧底(bottom),,,2. 棧底至棧頂依次存放元素A、B、C、D，在第五個(gè)元素E入棧前，棧中元素可以出棧，則出棧序列可能是______。A. ABCEDB. DBCEAC. CDABED. DCBEA,答案 D,四、隊(duì)列,限定在表的一端進(jìn)行刪除，在表的另一端進(jìn)行插入操作的線性表。 允許刪除

6、的一端叫做隊(duì)頭(front)，允許插入的一端叫做隊(duì)尾(rear)。特性：FIFO(First In First Out),,3 棧和隊(duì)列的共同點(diǎn)是______。 A. 都是先進(jìn)后出B. 都是先進(jìn)先出C. 只允許在端點(diǎn)處插入和刪除元素D. 沒有共同點(diǎn),答案 C,,4 下列關(guān)于隊(duì)列的敘述中正確的是______。A. 在隊(duì)列中只能插入數(shù)據(jù)B. 在隊(duì)列中只能刪除數(shù)據(jù)C. 隊(duì)列是先進(jìn)先出的線性表D. 隊(duì)列是先進(jìn)后出的線性表,答案 C,五、樹,樹是n個(gè)結(jié)點(diǎn)的有限集合T，在一棵非空樹中（n0）有且僅有一個(gè)稱作根的結(jié)點(diǎn)；其余結(jié)點(diǎn)可分為m個(gè)（m0）互不相交的集合T1，T2Tm，其中，每一個(gè)集合本身又是一棵樹,并

7、稱為根的子樹。,樹結(jié)構(gòu)的重要術(shù)語與概念,葉子 沒有后繼結(jié)點(diǎn)的結(jié)點(diǎn)稱為葉子（或終端結(jié)點(diǎn)），如圖中的D、E、F、G、H、I、J。 分支結(jié)點(diǎn) 非葉子結(jié)點(diǎn)稱為分支結(jié)點(diǎn),,結(jié)點(diǎn)的度 一個(gè)結(jié)點(diǎn)的子樹數(shù)目就稱為該結(jié)點(diǎn)的度。如圖中的結(jié)點(diǎn)B的度為2；結(jié)點(diǎn)C的度為3；結(jié)點(diǎn)D、J的度為0。 樹的度 樹中各結(jié)點(diǎn)的度的最大值稱為該樹的度，如圖所示樹的度為3。 子結(jié)點(diǎn) 某結(jié)點(diǎn)子樹的根稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。 樹的深度： 樹中節(jié)點(diǎn)的最大層數(shù)，圖所示的樹的深度為4。,1. 二叉樹,一個(gè)二叉樹是n個(gè)結(jié)點(diǎn)的有限集合(n0),此集合或者是空集（n=0），或者是由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的、分別稱為左子樹和右子樹的

8、二叉樹組成。,(a)空二叉樹 (b)僅有一個(gè)根結(jié)點(diǎn)的二叉樹 (c)右子樹為空的二叉樹 (d)左子樹為空的二叉樹 (e)左、右子樹均非空的二叉樹,二叉樹的基本形態(tài),2. 滿二叉樹,在一個(gè)二叉樹中，若第i層的結(jié)點(diǎn)數(shù)為2i-1，則稱此層的結(jié)點(diǎn)數(shù)是滿的，當(dāng)樹中的每一層都是滿的，則稱此二叉樹為滿二叉樹。,3. 完全二叉樹,如果一個(gè)二叉樹各層都是“滿”的，只是最下面一層從右邊起連續(xù)缺n個(gè)結(jié)點(diǎn)，這種二叉樹叫做完全二叉樹。,二叉樹的特性,性質(zhì)1 若二叉樹的層次從1開始, 則在二叉樹的第 i 層最多有 2i-1個(gè)結(jié)點(diǎn)。(i 1) 性質(zhì)2 深度為k的二叉樹最多有 2k-1個(gè)結(jié)點(diǎn)。(k 1) 性質(zhì)3 對

9、任何一棵二叉樹, 如果其葉結(jié)點(diǎn)個(gè)數(shù)為 n0, 度為2的非葉結(jié)點(diǎn)個(gè)數(shù)為 n2, 則有n0n21,,12. 設(shè)一棵完全二叉樹共有699個(gè)結(jié)點(diǎn)，則在該二叉樹中的葉子結(jié)點(diǎn)數(shù)為______。 A. 349B. 350C. 255D. 351,答案 B,二叉樹的遍歷,二叉樹遍歷是指按照某種搜索路線來巡訪每一個(gè)節(jié)點(diǎn)，分為深度優(yōu)先和廣度優(yōu)先。 二叉樹的深度優(yōu)先主要分為以下幾種： 1）先序遍歷 2）后序遍歷 3）中序遍歷,先序遍歷,先序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則 訪問根結(jié)點(diǎn) (D)； 先序遍歷左子樹 (L)； 先序遍歷右子樹 (R)。,中序遍歷,中序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則 中序遍歷左子樹 (L)； 訪問根結(jié)點(diǎn) (D)； 中序遍歷右子樹 (R)。,后序遍歷,后序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作； 否則 后序遍歷左子樹 (L)； 后序遍歷右子樹 (R)； 訪問根結(jié)點(diǎn) (D)。,,已知二叉樹后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是______。 A. cedbaB. acbedC. decabD. deabc,答案 A,,以下數(shù)據(jù)結(jié)構(gòu)中不屬于線性數(shù)據(jù)結(jié)構(gòu)的是______。A. 隊(duì)列B. 線性表C. 二叉樹D. 棧,答案 C,