計算機導論教師：第5章算法與數據結構05目錄CONTENTS1算法2數據結構的概念3幾種常見的數據結構4查找和排序本章學習目標了解算法的概念了解算法與數據結構的關系掌握數據結構的邏輯結構掌握數據結構的存儲結構了解常用的查找與排序算法本章學習目標算法算法（Algorithm）是指對解題方案的準確而完整的描述，是一系列解決問題的清晰指令，算法代表用系統的方法描述解決問題的策略機制。算法不是程序，但程序員可以使用某種編程語言來實現算法。算法被公認為是計算機科學的靈魂。從理論角度來看，對算法的研究（有時稱為“算法學”）已經被公認為是計算機科學的基石。

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

算法的描述用流程圖描述算法美國國家標準化協會（AmericanNationalStandardsInstitute,ANSI）曾規定了一些常用的流程圖符號，可以用這些流程圖符號描述算法的執行步驟。例5-2用流程圖描述求兩個整數的最大公約數的算法：如圖5-2所示。

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

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

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

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

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

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

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

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

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