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

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