數(shù)據(jù)結(jié)構(gòu)與算法 課件 第1章 數(shù)據(jù)結(jié)構(gòu)概述

1.1數(shù)據(jù)結(jié)構(gòu)的基本概念

1.2算法1.1數(shù)據(jù)結(jié)構(gòu)的基本概念1.1.1為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)圖靈獎獲得者尼古拉斯·沃斯(NiklausWirth)提出程序就是“數(shù)據(jù)結(jié)構(gòu)?+?算法”，這說明了數(shù)據(jù)結(jié)構(gòu)和算法在程序設(shè)計中所起的重要作用。用計算機求解任何問題都離不開程序，程序設(shè)計的一般過程如圖1.1所示。我們通過程序設(shè)計解決某個實際問題一般需要經(jīng)過以下幾個階段：(1)分析階段：對問題進行分析，抽象出數(shù)據(jù)模型，形成求解問題的基本思路，確定解決問題的方案；(2)設(shè)計階段：將數(shù)據(jù)以及數(shù)據(jù)之間的關(guān)系存儲到計算機的內(nèi)存中，設(shè)計數(shù)據(jù)處理的算法；(3)實現(xiàn)階段：將算法轉(zhuǎn)換為用某種程序設(shè)計語言編寫的程序，并進行測試、修改，直到確定出合適的程序設(shè)計方法。

1.1.2什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)(Data)是信息的載體，它是描述客觀事物的數(shù)字、字符以及所有能輸入到計算機中并被計算機程序處理的符號的集合。例如，一個代數(shù)方程的求解程序中所用的數(shù)據(jù)是整數(shù)和實數(shù)；一個編譯程序或文本編輯程序中所使用的數(shù)據(jù)是字符串。隨著計算機應(yīng)用領(lǐng)域的擴大，數(shù)據(jù)的含義更為廣泛，如圖像、聲音等都可以通過編碼成為數(shù)據(jù)。數(shù)據(jù)元素(DataElement)是數(shù)據(jù)的基本單位。有些情況下，數(shù)據(jù)元素也稱為元素、結(jié)點、頂點、記錄。有時，一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項(DataItem)組成。數(shù)據(jù)項是具有獨立含義的、不可再分割的最小標識單位。例如，某校某專業(yè)的學(xué)生成績表如表1.1所示。我們把學(xué)生成績表稱為一個數(shù)據(jù)，表中的每一行是一個數(shù)據(jù)元素，它由學(xué)號、姓名、性別、各科成績及平均成績等數(shù)據(jù)項組成。數(shù)據(jù)結(jié)構(gòu)(DataStructure)是數(shù)據(jù)元素之間的相互關(guān)系，即數(shù)據(jù)的組織形式。一般來說，數(shù)據(jù)結(jié)構(gòu)所研究的主要內(nèi)容包括以下三個方面：(1)數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系。(2)數(shù)據(jù)的存儲結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計算機中的存儲方式。數(shù)據(jù)的存儲結(jié)構(gòu)又稱為數(shù)據(jù)的物理結(jié)構(gòu)。(3)數(shù)據(jù)的運算：對數(shù)據(jù)施加的操作。數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲無關(guān)，是獨立于計算機的。因此，數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)學(xué)模型。數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)用計算機語言的實現(xiàn)，它是依賴于計算機語言的。對機器語言而言，存儲結(jié)構(gòu)是具體的，但我們只在高級語言的層次上來討論存儲結(jié)構(gòu)。數(shù)據(jù)的運算定義在數(shù)據(jù)的邏輯結(jié)構(gòu)之上。每一種邏輯結(jié)構(gòu)都有一組基本運算，例如對數(shù)據(jù)進行查找、插入、刪除、排序等運算。在數(shù)據(jù)的邏輯結(jié)構(gòu)層面上，我們只需要知道這些基本運算“做什么”，而不需要考慮“如何做”。只有確定了數(shù)據(jù)的存儲結(jié)構(gòu)，我們才能夠具體實現(xiàn)這些基本運算。1.1.3數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)用于描述數(shù)據(jù)中各個元素的邏輯關(guān)系。如圖1.2所示，根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，數(shù)據(jù)的邏輯結(jié)構(gòu)可以分為以下四類：(1)集合：數(shù)據(jù)元素之間除了“屬于同一集合”的關(guān)系之外，沒有其他關(guān)系。(2)線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在“一對一”的前后順序關(guān)系，除第一個元素和最后一個元素之外，其余元素都有唯一的一個直接前驅(qū)元素和唯一的一個直接后繼元素。(3)樹形結(jié)構(gòu)：數(shù)據(jù)元素之間存在“一對多”的層次關(guān)系，除最頂層的元素之外，其余元素都有若干個直接后繼元素。(4)圖結(jié)構(gòu)：數(shù)據(jù)元素之間存在“多對多”的任意關(guān)系，每個元素都有若干個直接前驅(qū)元素和若干個直接后繼元素。由于集合具有簡單性和松散性，因此不在數(shù)據(jù)結(jié)構(gòu)課程的討論范圍內(nèi)。數(shù)據(jù)的邏輯結(jié)構(gòu)可以分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類。線性表、棧、隊列、串等屬于線性結(jié)構(gòu)，而樹形結(jié)構(gòu)和圖結(jié)構(gòu)屬于非線性結(jié)構(gòu)。1.1.4數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)又稱為數(shù)據(jù)的存儲方法，是數(shù)據(jù)及其邏輯結(jié)構(gòu)在計算機中的表示。也就是說，存儲結(jié)構(gòu)除了要存儲數(shù)據(jù)元素，還要隱式或者顯式地表示數(shù)據(jù)元素之間的邏輯關(guān)系。數(shù)據(jù)的存儲結(jié)構(gòu)分為以下四種：1)順序存儲結(jié)構(gòu)借助元素在存儲器的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系，元素之間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)，由此得到的存儲表示稱為順序存儲結(jié)構(gòu)(SequentialStorageStructure)。通常順序存儲結(jié)構(gòu)是借助于程序語言的數(shù)組(又稱為向量)來描述的。該方法主要應(yīng)用于線性數(shù)據(jù)結(jié)構(gòu)。非線性的數(shù)據(jù)結(jié)構(gòu)也可以通過某種線性化的方法來實現(xiàn)順序存儲。2)鏈式存儲結(jié)構(gòu)借助指示元素存儲地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系，即邏輯上相鄰的元素在物理位置上不一定相鄰，由此得到的存儲表示稱為鏈式存儲結(jié)構(gòu)(LinkedStorageStructure)，通常要借助于程序語言的指針類型來描述它。3)索引存儲結(jié)構(gòu)索引存儲結(jié)構(gòu)是指在存儲數(shù)據(jù)元素的同時，還建立附加的索引表。索引表中的每一項稱為索引項，其一般形式是(關(guān)鍵字，地址)，關(guān)鍵字是能夠唯一標識一個元素的那些數(shù)據(jù)項。若每個元素在索引表中都有一個索引項，則該索引表稱為稠密索引(DenseIndex)；若一組元素在索引表中對應(yīng)一個索引項，則該索引表稱為稀疏索引(SparseIndex)。稠密索引中索引項的地址指示元素所在的存儲位置，而稀疏索引中索引項的地址則指示一組元素的起始存儲位置。4)散列存儲結(jié)構(gòu)散列存儲結(jié)構(gòu)的基本思想是根據(jù)數(shù)據(jù)元素的關(guān)鍵字直接計算出該元素的存儲地址。上述四種基本的存儲方法既可以單獨使用，也可以組合起來對數(shù)據(jù)結(jié)構(gòu)進行存儲。同一種邏輯結(jié)構(gòu)采用不同的存儲方法，可以得到不同的存儲結(jié)構(gòu)。至于選擇何種存儲結(jié)構(gòu)來表示相應(yīng)的邏輯結(jié)構(gòu)，應(yīng)當考慮算法運算是否方便以及時間和空間要求等因素。1.2算法1.2.1算法的定義與性質(zhì)數(shù)據(jù)的運算是通過算法(Algorithm)描述的。對實際問題選擇一種好的數(shù)據(jù)結(jié)構(gòu)，設(shè)計一個好的算法，是程序設(shè)計的本質(zhì)。算法與數(shù)據(jù)結(jié)構(gòu)是互相依賴、互相聯(lián)系的。算法是對特定問題求解步驟的描述，是指令的有限序列。算法必須滿足以下性質(zhì)：(1)輸入性：0至多個輸入，這些輸入取自于某個特定的對象的集合。(2)輸出性：1至多個輸出，這些輸出是同輸入有著某種特定關(guān)系的量。(3)有窮性：對于合法的輸入值，算法在執(zhí)行有窮步之后結(jié)束。(4)確定性：對于相同的輸入執(zhí)行相同的路徑，即對于相同的輸入只能得出相同的輸出。(5)可行性：用于描述算法的操作都是足夠基本的，即算法中描述的操作都是可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)的。需要說明的是，算法與程序是有區(qū)別的。算法具有有窮性，而程序不一定具有有窮性。1.2.2描述算法的工具數(shù)最大公約數(shù)的算法算法設(shè)計者在構(gòu)思和設(shè)計了一個算法之后，必須清楚準確地將所設(shè)計的求解步驟記錄下來，即描述算法。常用的描述算法的工具有自然語言、流程圖、程序設(shè)計語言和偽代碼等。下面以求兩個正整數(shù)最大公約數(shù)的算法為例進行介紹。1.自然語言用自然語言描述算法的優(yōu)點是容易理解，缺點是不夠嚴謹，容易出現(xiàn)二義性，并且算法通常較為冗長。求兩個正整數(shù)最大公約數(shù)的算法用自然語言描述如下：步驟1：將m除以n得到余數(shù)r。步驟2：若r等于0，則n為最大公約數(shù)，算法結(jié)束；否則執(zhí)行步驟3。步驟3：將n的值賦給m，r的值賦給n，重復(fù)執(zhí)行步驟1。2．流程圖用流程圖描述算法的優(yōu)點是直觀易懂，缺點是嚴密性不如程序設(shè)計語言，靈活性不如自然語言。用流程圖描述的求兩個正整數(shù)最大公約數(shù)的算法如圖1.3所示。在計算機應(yīng)用早期，使用流程圖描述算法占據(jù)著統(tǒng)治地位，但實踐證明，這種描述方法使用起來非常不方便。3．程序設(shè)計語言用程序設(shè)計語言描述的算法能夠由計算機執(zhí)行，缺點是抽象性差。設(shè)計者在設(shè)計算法時由于受到程序設(shè)計語言的語法規(guī)則限制，往往忽視了算法的正確性和邏輯性。求兩個正整數(shù)最大公約數(shù)的算法用C語言描述時，所編寫的程序如下：4．偽代碼偽代碼(Pseudocode)是介于自然語言和高級語言之間的方法，它遵循某一程序設(shè)計語言的基本語法，但操作指令可以結(jié)合自然語言來設(shè)計。至于自然語言的成分有多少，取決于算法的抽象程度。抽象程度高，偽代碼中的自然語言就多一些，程序設(shè)計語言的語句就少一些；反之亦然。求兩個正整數(shù)最大公約數(shù)的算法用偽代碼描述如下：上述偽代碼可以再具體一些，即抽象程度低一些，也就是說程序設(shè)計語言的成分多一些。我們可用類C語言來描述算法。類C語言遵循C語言的語法規(guī)則，但不必拘泥于C語言的實現(xiàn)細節(jié)，又容易轉(zhuǎn)換為C程序。通常用類C語言的函數(shù)來描述算法，重點給出算法的邏輯，忽略局部變量的聲明，并且不在主函數(shù)中調(diào)用。求兩個正整數(shù)最大公約數(shù)的算法用類C語言描述如下：1.2.3對算法的評價標準我們通常從正確性、易讀性、健壯性和高效性等四個方面評價算法的質(zhì)量。正確性是指算法能夠完成預(yù)定的功能。易讀性決定了算法是否易于閱讀和理解，以便對程序進行調(diào)試、修改和擴充。健壯性體現(xiàn)在當環(huán)境發(fā)生變化時，算法能夠適當?shù)刈龀龇磻?yīng)或進行處理，不會產(chǎn)生不需要的運行結(jié)果。高效性是指算法在時間和空間兩個方面的效率。1．算法的高效性算法的時間特性是指執(zhí)行算法所需要的計算時間長短，算法的空間特性則是執(zhí)行算法所需要的輔助存儲空間大小。當然我們希望選用一個占用存儲空間小、運行時間短的算法。然而上述要求常常相互抵觸，要節(jié)約算法的執(zhí)行時間，往往要以犧牲更多的空間為代價；而為了節(jié)省空間，可能要耗費更多的計算時間。算法的時間特性和空間特性通常會與問題的規(guī)模有關(guān)，因此我們只能根據(jù)具體情況有所側(cè)重。一個算法所需的計算時間，應(yīng)當是該算法中每條語句的執(zhí)行時間之和，而每條語句的執(zhí)行時間是該語句的執(zhí)行次數(shù)(稱為頻度)與該語句執(zhí)行一次所需時間的乘積。但是，當算法轉(zhuǎn)換為程序之后，每條語句執(zhí)行一次所需的時間取決于機器的指令性能、速度以及編譯所產(chǎn)生的代碼質(zhì)量，這是很難確定的。我們假設(shè)每條語句執(zhí)行一次所需的時間均是一個單位時間，一個算法的計算時間就是該算法中所有語句的頻度之和。這樣，我們就可以獨立于機器的軟、硬件系統(tǒng)來分析算法的時間特性。一般情況下，算法中基本操作重復(fù)執(zhí)行的時間是問題規(guī)模n的某個函數(shù)f(n)，算法的漸進時間復(fù)雜度(簡稱時間復(fù)雜度(TimeComplexity))記為它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同，f(n)一般是算法中頻度最大的語句頻度。當有循環(huán)嵌套時，算法的時間復(fù)雜度是由最內(nèi)層語句的頻度f(n)決定的。對于某些算法，即使問題規(guī)模相同，如果輸入的數(shù)據(jù)不同，其時間開銷也不同。一般來說，最好情況作為算法性能的代表，沒有什么意義。將最壞情況作為計算時間復(fù)雜度的依據(jù)，能夠說明算法的運行時間最壞能壞到什么程度，這一點在實時系統(tǒng)中尤為重要。算法的空間復(fù)雜度是指在算法執(zhí)行過程中所需要的輔助存儲空間數(shù)量。輔助存儲空間是除算法本身和輸入輸出數(shù)據(jù)所占存儲空間之外，為算法臨時開辟的存儲空間，記為其中，n為問題的規(guī)模，其分析方法與算法的時間復(fù)雜度類似。2．算法的易讀性一個高質(zhì)量的算法除了正確和運行效率高之外，還對算法的易讀性有一定的要求。算法的易讀性主要體現(xiàn)在算法的結(jié)構(gòu)、代碼的書寫格式以及注釋等方面。