計算機(jī)導(dǎo)論 第5章 算法與數(shù)據(jù)結(jié)構(gòu)

計算機(jī)導(dǎo)論教師：第5章算法與數(shù)據(jù)結(jié)構(gòu)05目錄CONTENTS1算法2數(shù)據(jù)結(jié)構(gòu)的概念3幾種常見的數(shù)據(jù)結(jié)構(gòu)4查找和排序本章學(xué)習(xí)目標(biāo)了解算法的概念了解算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系掌握數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)掌握數(shù)據(jù)結(jié)構(gòu)的存儲結(jié)構(gòu)了解常用的查找與排序算法本章學(xué)習(xí)目標(biāo)算法算法（Algorithm）是指對解題方案的準(zhǔn)確而完整的描述，是一系列解決問題的清晰指令，算法代表用系統(tǒng)的方法描述解決問題的策略機(jī)制。算法不是程序，但程序員可以使用某種編程語言來實現(xiàn)算法。算法被公認(rèn)為是計算機(jī)科學(xué)的靈魂。從理論角度來看，對算法的研究（有時稱為“算法學(xué)”）已經(jīng)被公認(rèn)為是計算機(jī)科學(xué)的基石。

算法的概念算法的基本特性一個算法必須在有限步驟之內(nèi)結(jié)束，不能形成死循環(huán)。這種有限性使算法不能保證一定有解。有限性算法中的每條指令必須有確定含義，無二義性，不會產(chǎn)生理解偏差。算法可以有多條執(zhí)行路徑，但是對某個確定的條件值只能選擇其中一條路徑執(zhí)行。確定性一個算法有多個或0個輸入，輸入取自某些特定對象的集合。有些輸入在算法執(zhí)行過程中輸入，有些算法不需要外部輸入。輸入至少有一個或多個輸出，輸出與輸入之間存在某些特定的關(guān)系。不同的輸入可以產(chǎn)生不同或相同的輸出，但是相同的輸入必須產(chǎn)生相同的輸出。輸出算法是可行的。描述的操作可通過已實現(xiàn)的基本運(yùn)算執(zhí)行有限次而完成。可行性用自然語言描述算法用自然語言描述算法的優(yōu)點是簡單，但容易出現(xiàn)歧義。例5-1用自然語言描述求兩個整數(shù)的最大公約數(shù)的算法。步驟1：輸入兩個整數(shù)x和y；步驟2：x和y整除余數(shù)為r；步驟3：判斷余數(shù)r是否為0，如果為0，則轉(zhuǎn)步驟5；否則轉(zhuǎn)步驟4；步驟4：x的值是y的值，y的值是r的值,轉(zhuǎn)步驟2；步驟5：輸出y。y為所求的兩個整數(shù)的最大公約數(shù)。

算法的描述用流程圖描述算法美國國家標(biāo)準(zhǔn)化協(xié)會（AmericanNationalStandardsInstitute,ANSI）曾規(guī)定了一些常用的流程圖符號，可以用這些流程圖符號描述算法的執(zhí)行步驟。例5-2用流程圖描述求兩個整數(shù)的最大公約數(shù)的算法：如圖5-2所示。

算法的描述用偽代碼描述算法偽代碼（Pseudocode）是一種非正式的，用介于自然語言和計算機(jī)語言之間的文字和符號（包括數(shù)學(xué)符號）來描述算法。使用偽代碼的目的是使被描述的算法可以容易地以任何一種編程語言（Pascal、C、Java等）來實現(xiàn)。因此，偽代碼必須結(jié)構(gòu)清晰、代碼簡單、可讀性好，并且類似自然語言。

算法的描述用類C語言描述算法

算法的描述算法設(shè)計要求算法的正確性是指在給定有效輸入后，經(jīng)過有限時間的計算并產(chǎn)生正確的答案。正確性算法的可讀性是指一個算法可供人們閱讀的容易程度?？勺x性算法的健壯性是指一個算法對不合理數(shù)據(jù)輸入的反應(yīng)能力和處理能力，也稱為容錯性。健壯性算法的效率通常是指算法的執(zhí)行時間。對于一個具體問題的解決，通常有多個算法，執(zhí)行時間短的算法其效率就高。計算機(jī)的另一個有限資源就是內(nèi)存，希望一個算法的執(zhí)行所需要的最大存儲空間盡可能得少。高效率和低存儲數(shù)據(jù)結(jié)構(gòu)的發(fā)展計算機(jī)加工處理對象范圍、類型不斷擴(kuò)展，由純數(shù)值發(fā)展到字符、表格、聲音和圖像的各種具有一定結(jié)構(gòu)的數(shù)據(jù)。為了應(yīng)對信息時代計算機(jī)處理對象特點的變化，迫切需要分析待處理數(shù)據(jù)對象的特性及其各處理對象間的關(guān)系。1968年，美國著名計算機(jī)科學(xué)家高德納（DonaldErvinKnuth）開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的《計算機(jī)程序設(shè)計藝術(shù)》第一卷《基本算法》是第一本系統(tǒng)闡述數(shù)據(jù)結(jié)構(gòu)的著作。瑞士計算機(jī)科學(xué)家尼古拉斯·沃斯（NiklausWirth）在1976年出版的著作中指出：“算法+數(shù)據(jù)結(jié)構(gòu)=程序”，可見數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計中的重要性。數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)（Data）是描述客觀事物的數(shù)值、字符及能輸入機(jī)器且能被處理的各種符號的集合。數(shù)據(jù)元素（DataElement）作為數(shù)據(jù)的基本單位。一個數(shù)據(jù)元素可由一個或多個數(shù)據(jù)項（DataItem）組成，數(shù)據(jù)項是具有獨立含義的數(shù)據(jù)最小單位。數(shù)據(jù)對象（DataObject）是指性質(zhì)相同的數(shù)據(jù)元素的集合，它是數(shù)據(jù)的一個子集。數(shù)據(jù)結(jié)構(gòu)（DataStructure）是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素集合，數(shù)據(jù)結(jié)構(gòu)應(yīng)該包括數(shù)據(jù)元素集合及元素間關(guān)系的集合。因此，我們可以把數(shù)據(jù)結(jié)構(gòu)看成帶結(jié)構(gòu)的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容通常包括3個方面：數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)的邏輯結(jié)構(gòu)由數(shù)據(jù)元素之間的邏輯關(guān)系構(gòu)成，是獨立于計算機(jī)的，因此數(shù)據(jù)邏輯結(jié)構(gòu)可以看作從具體問題抽象出來的數(shù)學(xué)模型。數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)元素及其關(guān)系在計算機(jī)存儲器中的存儲表示，也稱為數(shù)據(jù)的物理結(jié)構(gòu)。顯然，數(shù)據(jù)的存儲結(jié)構(gòu)是依賴于計算機(jī)的。數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的運(yùn)算是施加在數(shù)據(jù)上的操作，常用的有查找、插入、刪除、更新和排序等。數(shù)據(jù)的運(yùn)算需要在對應(yīng)的存儲結(jié)構(gòu)上用算法實現(xiàn)。數(shù)據(jù)的運(yùn)算邏輯結(jié)構(gòu)的定義邏輯結(jié)構(gòu)

基本的數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)集合結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間除“同屬于一個集合”的關(guān)系以外別無其他關(guān)系。線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的線性關(guān)系。其特點是，除第一個元素和最后一個元素外，每個元素都有且僅有一個前驅(qū)元素，有且僅有一個后繼元素。樹形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著一對多的層次關(guān)系。其特點是，如果數(shù)據(jù)元素集合非空，則有且僅有一個元素被稱為根元素，除根元素以外的其他元素有且僅有一個前驅(qū)元素。所有元素有0個或多個后繼。圖形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著多對多的任意關(guān)系。其特點是，每個元素的前驅(qū)元素和后繼元素的個數(shù)可以是任意的。邏輯結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)存儲結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)存儲器中的存儲表示被稱為數(shù)據(jù)的存儲結(jié)構(gòu)（也稱為映像），也就是邏輯結(jié)構(gòu)在計算機(jī)中的存儲實現(xiàn)，它包括數(shù)據(jù)對象的表示和數(shù)據(jù)對象中數(shù)據(jù)元素關(guān)系的表示。順序存儲結(jié)構(gòu)存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)采用一組連續(xù)的存儲單元存放所有的數(shù)據(jù)元素，并映射元素之間的邏輯關(guān)系。也就是說，所有的數(shù)據(jù)元素在計算機(jī)存儲器中占用一整塊存儲空間。一般來說，順序存儲結(jié)構(gòu)是高級語言的數(shù)組。鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)是指使用“鏈表”存儲映像數(shù)據(jù)的邏輯結(jié)構(gòu)，鏈表是由節(jié)點構(gòu)成的，每個節(jié)點對應(yīng)一個數(shù)據(jù)元素，每個節(jié)點是單獨分配的，所有節(jié)點的地址不一定是連續(xù)的。為了表示元素之間的邏輯關(guān)系，每個節(jié)點有一個或多個指針域，用于存儲邏輯上相鄰節(jié)點的地址，也就是通過指針域?qū)⑺泄?jié)點連接起來而形成鏈表。索引存儲結(jié)構(gòu)存儲結(jié)構(gòu)索引存儲結(jié)構(gòu)是指在存儲數(shù)據(jù)元素信息的同時還要建立附加的索引表。存儲所有數(shù)據(jù)元素信息的表稱為主數(shù)據(jù)表，其中每個數(shù)據(jù)元素有一個關(guān)鍵字和對應(yīng)的存儲地址。散列存儲結(jié)構(gòu)存儲結(jié)構(gòu)散列存儲也稱哈希存儲。散列存儲的基本思想是根據(jù)元素的關(guān)鍵字通過散列函數(shù)直接計算出一個值，并將這個值作為該元素的存儲地址。與前3種存儲結(jié)構(gòu)不同的是，散列存儲不涉及數(shù)據(jù)元素之間關(guān)系的映射，所以散列存儲主要應(yīng)用于元素間沒有邏輯關(guān)系的集合結(jié)構(gòu)，以便數(shù)據(jù)的查找和插入運(yùn)算。數(shù)據(jù)運(yùn)算數(shù)據(jù)運(yùn)算是指對數(shù)據(jù)實施的操作。每種數(shù)據(jù)結(jié)構(gòu)都有一組相應(yīng)的運(yùn)算，常用的運(yùn)算有查找、插入、刪除、遍歷、排序等。數(shù)據(jù)運(yùn)算分為運(yùn)算定義和運(yùn)算實現(xiàn)兩個層面。運(yùn)算定義是運(yùn)算功能的描述，是抽象的，基于邏輯結(jié)構(gòu)的。運(yùn)算實現(xiàn)是基于存儲結(jié)構(gòu)的，同樣的運(yùn)算定義，如果存儲結(jié)構(gòu)不同，運(yùn)算實現(xiàn)的算法基本不同。對于一種數(shù)據(jù)結(jié)構(gòu)，其邏輯結(jié)構(gòu)總是唯一的，但它可能對應(yīng)多種存儲結(jié)構(gòu)，并且在不同的存儲結(jié)構(gòu)中同一運(yùn)算的實現(xiàn)過程可能不同。線性表的定義線性表

線性表的存儲結(jié)構(gòu)線性表線性表的存儲結(jié)構(gòu)有兩種：順序存儲和鏈?zhǔn)酱鎯?。線性表的順序存儲，是把線性表中的所有元素按照邏輯順序依次存儲到一塊地址連續(xù)的存儲空間中，邏輯上相鄰的兩個元素，物理上也是相鄰的。線性表的順序存儲結(jié)構(gòu)簡稱為順序表。線性表的鏈?zhǔn)酱鎯σ卜Q鏈表。一般采用帶頭節(jié)點的單鏈表存儲線性表。操作受限的線性表線性表棧（Stack）是指將線性表的插入和刪除運(yùn)算限制為僅在表的一端進(jìn)行。通常將表中允許進(jìn)行插入、刪除操作的一端稱為棧頂，將表的另一端稱為棧底。當(dāng)棧中沒有元素時稱為空棧。棧的插入操作被形象地稱為進(jìn)?；蛉霔?，刪除操作被稱為出棧或退棧。隊列（Queue）是另一種限定性的線性表，它只允許在表的一端插入元素，而在另一端刪除元素，所以隊列具有先進(jìn)先出的特性。在隊列中，允許插入的一端叫作隊尾，允許刪除的一端叫作隊頭。樹的基本概念和特征樹型結(jié)構(gòu)

二叉樹樹型結(jié)構(gòu)二叉樹（BinaryTree）是一個有限的節(jié)點集合，這個集合或為空，或由一個根節(jié)點和兩棵不相交的稱為左子樹和右子樹的二叉樹構(gòu)成。二叉樹的定義也是遞歸定義。二叉樹有5種基本形態(tài)。二叉樹中的節(jié)點最多有兩個孩子，分別稱為左孩子和右孩子。滿二叉樹和完全二叉樹樹型結(jié)構(gòu)在一棵二叉樹中，如果所有分支節(jié)點都有兩個孩子節(jié)點，并且葉子節(jié)點都集中在二叉樹的最下面一層，這樣的二叉樹稱為滿二叉樹。若二叉樹中最多只有最下面兩層節(jié)點的度數(shù)可以小于2，并且最下面一層的葉子節(jié)點都排列在該層最左邊的位置上，則這樣的二叉樹被稱為完全二叉樹。二叉樹的二叉鏈表存儲結(jié)構(gòu)樹型結(jié)構(gòu)二叉樹也有順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，常用的是鏈?zhǔn)酱鎯Y(jié)構(gòu)。因為二叉樹最多有兩個孩子，因此鏈表節(jié)點有兩個指針域，分別指向左孩子和右孩子。二叉樹的順序存儲結(jié)構(gòu)樹型結(jié)構(gòu)二叉樹的順序存儲就是用一組地址連續(xù)的存儲單元來存放二叉樹的數(shù)據(jù)元素。對于完全二叉樹和滿二叉樹，樹中節(jié)點的層序編號可以唯一地反映節(jié)點之間的邏輯關(guān)系，所以可以用一維數(shù)組按從上到下，從左到右的順序存儲二叉樹中的所有節(jié)點的值，即編號為的節(jié)點存儲在下標(biāo)為的數(shù)組單元中。二叉樹的遍歷樹型結(jié)構(gòu)二叉樹的遍歷是指按照一定的次序訪問二叉樹中的所有節(jié)點，并且每個節(jié)點僅被訪問一次的過程。一棵二叉樹由3部分組成，即根節(jié)點、左子樹和右子樹，若規(guī)定遍歷時先左后右，則對于非空二叉樹，可以得到3種遞歸的遍歷方法，即先序遍歷、中序遍歷和后序遍歷。對于非空二叉樹：先序遍歷：訪問根節(jié)點、先序遍歷左子樹、先序遍歷右子樹。中序遍歷：中序遍歷左子樹、訪問根節(jié)點、中序遍歷右子樹。后序遍歷：后序遍歷左子樹、后序遍歷右子樹、訪問根節(jié)點除此之外，還可以對一棵二叉樹按層遍歷，即按照從上到下，從左到右的順序遍歷二叉樹。二叉樹的遍歷樹型結(jié)構(gòu)按層遍歷：ABCDEFG先序遍歷：ABDGCEF中序遍歷：BGDAECF后序遍歷：GDBEFCA圖的基本概念圖形結(jié)構(gòu)

圖的存儲結(jié)構(gòu)圖形結(jié)構(gòu)常用的兩種圖的存儲結(jié)構(gòu)是鄰接矩陣和鄰接表。鄰接矩陣：使用一個一維數(shù)組來存儲圖中的頂點信息，每個頂點都被分配了一個唯一的編號，該編號與數(shù)組下標(biāo)一一對應(yīng)。使用另一個二維數(shù)組，也即鄰接矩陣來存儲圖中頂點之間的連接關(guān)系，元素的值為0或1，1表示有邊或弧相連，而0則表示沒有。

圖的存儲結(jié)構(gòu)圖形結(jié)構(gòu)常用的兩種圖的存儲結(jié)構(gòu)是鄰接矩陣和鄰接表。鄰接表：使用一個一維數(shù)組存儲圖，一維數(shù)組元素包含兩個數(shù)據(jù)項：頂點信息及這個頂點所有鄰接點的單鏈表的頭指針。由于一個頂點的所有鄰接點以單鏈表存儲，因此這種存儲結(jié)構(gòu)是順序+鏈?zhǔn)酱鎯Y(jié)構(gòu)。圖的遍歷圖形結(jié)構(gòu)從圖中某一頂點出發(fā)訪問圖中的所有頂點，且每個頂點僅被訪問一次，這一過程就叫作圖的遍歷。通常有兩種遍歷策略：深度優(yōu)先遍歷和廣度優(yōu)先遍歷。深度優(yōu)先遍歷，也稱為深度優(yōu)先搜索(DepthFirstSearch,DFS)：從圖中某個頂點v出發(fā)，先訪問此頂點，然后從v的未被訪問的鄰接點出發(fā)進(jìn)行DFS，直至圖中所有和v有路徑相通的頂點都被訪問到。若圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點做起始點，重復(fù)上述過程，直至圖中的所有頂點都被訪問到為止。圖的遍歷圖形結(jié)構(gòu)從圖中某一頂點出發(fā)訪問圖中的所有頂點，且每個頂點僅被訪問一次，這一過程就叫作圖的遍歷。通常有兩種遍歷策略：深度優(yōu)先遍歷和廣度優(yōu)先遍歷。廣度優(yōu)先遍歷，又稱為廣度優(yōu)先搜索（BreathFirstSearch，BFS）：從圖中某頂點v出發(fā)，在訪問了v之后依次先訪問v的各個未曾訪問過的鄰接點，然后分別從這些鄰接點出發(fā)依次訪問它們的鄰接點，并使得“先被訪問的頂點的鄰接點先于后被訪問的頂點的鄰接點被訪問”，直至圖中所有已被訪問的頂點的鄰接點都被訪問到。如果此時圖中尚有頂點未被訪問，則需要另選一個未曾被訪問過的頂點作為新的起始點，重復(fù)上述過程，直至圖中所有頂點都被訪問到為止。查找查找和排序查找又稱檢索，是指在某種數(shù)據(jù)結(jié)構(gòu)中找出滿足給定條件的元素，主要有基于線性表的查找、基于樹的查找和哈希表查找。

查找查找和排序查找又稱檢索，是指在某種數(shù)據(jù)結(jié)構(gòu)中找出滿足給定條件的元素，主要有基于線性表的查找、基于樹的查找和哈希表查找。二分查找又稱折半查找，要求待查找的順序表是按關(guān)鍵字有序的。算法的思想是：將順序表中間位置的元素的關(guān)鍵字與查找關(guān)鍵字做比較，如果兩者相等，則查找成功；否則如果中間位置元素的關(guān)鍵字大于查找關(guān)鍵字，則在前半部分繼續(xù)查找，否則在后半部分繼續(xù)查找，重復(fù)以上過程，直到找到滿足條件的元素或查找范圍為空。因為每比較一次或會查找成功，或使查找范圍縮小一半，因此該算法稱為折半查找算法。排序查找和排序排序是將一個數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個按關(guān)鍵字有序的序列。學(xué)習(xí)和研究各種排序方法是計算機(jī)領(lǐng)域的重要課題之一。冒泡排序查找和排序冒泡排序算法是一種典型的交換排序算法，基本思想是通過無序區(qū)中相鄰元素關(guān)鍵字的比較和相鄰元素的交換使關(guān)鍵字小的元素如氣泡般往上“漂浮”?？焖倥判蛩惴ú檎液团判蚩焖倥判蛩惴ú捎梅种尾呗?，對無序區(qū)，首先選取某個稱為基準(zhǔn)的元素（一般為無序區(qū)的第1個元素），利用這個基準(zhǔn)元素，把無序區(qū)分成兩個子序列，第1個子序列的所有元素值都小于或等于這個基準(zhǔn)，第2個子序列的所有元素都大于或等于這個基準(zhǔn)。然后遞歸對兩個子序列采用同樣的算法劃分，子序列規(guī)模越來越小，直到每個子序列只有一個元素或空為止。這時整個序列也就有序了。直接插入排序查找和排序直接插入排序算法的思想：初始時，將序列中第一個元素作為有序區(qū)，剩下的n-1個元素作為無序區(qū)。每一次，把無序區(qū)的第一個元素插入有序區(qū)，每插入一個元素后依然保持有序區(qū)有序，有序區(qū)元素個數(shù)增一，無序區(qū)元素個數(shù)減一，經(jīng)過n-1趟后即成為有序序列。簡單選擇排序查找和排序簡單選擇排序算法的基本思想：每次總是從無序序列中選出最小元素并把其放在無序序列的起始位置。每選擇一次會使無序序列元素個數(shù)減一，使有序序列元素個數(shù)增一，共需要n-1趟選擇。初始時，無序序列元素個數(shù)為n。擴(kuò)展閱讀：密碼與安全一直在國際上廣泛