數(shù)據(jù)結(jié)構(gòu)（Java版）課件 第1章 緒論

第1章緒論

目錄2引言基本概念算法小結(jié)第一部分第二部分第三部分第四部分學(xué)習(xí)目的課程內(nèi)容數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)類型與抽象數(shù)據(jù)類型算法的概念算法描述算法分析第一部分引言學(xué)習(xí)目的4抽象模型實(shí)踐積累信息處理從具體問題中抽象出適當(dāng)?shù)臄?shù)學(xué)模型：分析問題，提取操作的對象，找出操作對象之間的邏輯關(guān)系，給出相應(yīng)的數(shù)學(xué)模型。設(shè)計(jì)解決此數(shù)學(xué)模型的算法。編程、運(yùn)行、調(diào)試，得出結(jié)果設(shè)計(jì)算法學(xué)會(huì)使用計(jì)算機(jī)解決實(shí)際的應(yīng)用問題課程內(nèi)容5過程抽象實(shí)現(xiàn)評(píng)價(jià)邏輯結(jié)構(gòu)基本運(yùn)算數(shù)據(jù)表示數(shù)據(jù)處理儲(chǔ)存結(jié)構(gòu)算法不同數(shù)據(jù)結(jié)構(gòu)比較和算法性能分析第二部分基本概念數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)7數(shù)據(jù)

數(shù)據(jù)(Data)是能夠被計(jì)算機(jī)程序識(shí)別、存儲(chǔ)、加工和處理的描述客觀事物的數(shù)字等符號(hào)集合的總稱。數(shù)據(jù)項(xiàng)

數(shù)據(jù)項(xiàng)(DataItem)是具有獨(dú)立含義的、數(shù)據(jù)不可分割的最小標(biāo)識(shí)單位，是數(shù)據(jù)元素的組成部分，也可稱為字段和域。數(shù)據(jù)元素

數(shù)據(jù)元素(DataElement)是數(shù)據(jù)的基本單位，又可稱為元素、結(jié)點(diǎn)、頂點(diǎn)和記錄，是一個(gè)數(shù)據(jù)整體中可以標(biāo)識(shí)和訪問的數(shù)據(jù)單元。數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)8數(shù)據(jù)對象

數(shù)據(jù)對象(DataObject)是性質(zhì)相同的數(shù)據(jù)元素的集合，也叫數(shù)據(jù)元素類，是數(shù)據(jù)的一個(gè)子集，數(shù)據(jù)元素是數(shù)據(jù)對象的一個(gè)實(shí)例。數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)(DataStructure)是相互之間存在著一種或者多種關(guān)系的數(shù)據(jù)元素的集合，數(shù)據(jù)結(jié)構(gòu)概念包含3個(gè)方面的內(nèi)容，即數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的操作，只有3個(gè)方面的內(nèi)容相同才能稱為完全相同的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)的邏輯結(jié)構(gòu)9數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間存在的邏輯關(guān)系，由數(shù)據(jù)元素的集合和定義在此集合上的關(guān)系組成。兩要素：數(shù)據(jù)元素的集合、關(guān)系的集合。數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)的邏輯結(jié)構(gòu)分類10邏輯結(jié)構(gòu)樹形結(jié)構(gòu)商業(yè)策略集合圖形結(jié)構(gòu)線性結(jié)構(gòu)集合中元素的關(guān)系極為松散，關(guān)系為“屬于同一個(gè)集合”。線性結(jié)構(gòu)是數(shù)據(jù)元素中具有線性關(guān)系的數(shù)據(jù)結(jié)構(gòu)，線性結(jié)構(gòu)中的結(jié)點(diǎn)存在“一對一”的關(guān)系。樹形結(jié)構(gòu)是數(shù)據(jù)元素之間具有層次關(guān)系的一種非線性結(jié)構(gòu)，樹形結(jié)構(gòu)中的結(jié)點(diǎn)存在“一對多”的關(guān)系。圖形結(jié)構(gòu)也是一種非線性結(jié)構(gòu)，圖形結(jié)構(gòu)中的結(jié)點(diǎn)存在“多對多”的關(guān)系。數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)11邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)表示或?qū)崿F(xiàn)叫數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，也叫物理結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)從邏輯關(guān)系角度觀察數(shù)據(jù)，與數(shù)據(jù)的存儲(chǔ)無關(guān)，是獨(dú)立于計(jì)算機(jī)的；而數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)，依賴于計(jì)算機(jī)。12存儲(chǔ)結(jié)構(gòu)索引存儲(chǔ)結(jié)構(gòu)商業(yè)策略順序存儲(chǔ)結(jié)構(gòu)散列存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)在連續(xù)的存儲(chǔ)單元中存放數(shù)據(jù)元素，元素的物理存儲(chǔ)次序和邏輯次序一致，即物理位置相鄰的元素在邏輯上也相鄰，每個(gè)元素與其前驅(qū)元素和后繼元素的存儲(chǔ)位置相鄰，數(shù)據(jù)元素的物理存儲(chǔ)結(jié)構(gòu)體現(xiàn)它們之間的邏輯關(guān)系。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)使用地址分散的存儲(chǔ)單元存放數(shù)據(jù)元素，邏輯上相鄰的數(shù)據(jù)元素的物理位置不一定相鄰，數(shù)據(jù)元素間的邏輯關(guān)系通常由附加的指針表示，指針記錄前驅(qū)元素和后繼元素的存儲(chǔ)地址。索引存儲(chǔ)結(jié)構(gòu)在存儲(chǔ)數(shù)據(jù)元素的基礎(chǔ)上增加索引表。散列存儲(chǔ)結(jié)構(gòu)也叫哈希存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的具體存儲(chǔ)地址根據(jù)該數(shù)據(jù)元素的關(guān)鍵字值通過散列函數(shù)直接計(jì)算出來。數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)分類13數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)操作數(shù)據(jù)操作是指對數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素進(jìn)行運(yùn)算或處理。數(shù)據(jù)操作定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上，每種邏輯結(jié)構(gòu)都需要一組對其數(shù)據(jù)元素進(jìn)行處理以實(shí)現(xiàn)特定功能的操作，如插入、刪除、更新等。數(shù)據(jù)操作的實(shí)現(xiàn)依賴于數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。常用的數(shù)據(jù)操作：創(chuàng)建操作、插入操作、刪除操作、查找操作、修改操作、遍歷操作、銷毀操作數(shù)據(jù)類型

數(shù)據(jù)類型(DataType)是一組性質(zhì)相同的值的集合和定義在此集合上的一組操作的總稱。在用高級(jí)程序語言編寫的程序中必須對程序中出現(xiàn)的每個(gè)變量、常量明確說明它們所屬的數(shù)據(jù)類型。高級(jí)程序設(shè)計(jì)語言通常預(yù)定義基本數(shù)據(jù)類型和構(gòu)造數(shù)據(jù)類型。

基本數(shù)據(jù)類型：只能作為一個(gè)整體來進(jìn)行處理不可分解的數(shù)據(jù)類型。

構(gòu)造數(shù)據(jù)類型：使用已有的基本數(shù)據(jù)類型和已定義的構(gòu)造數(shù)據(jù)類型通過一定的語法規(guī)則組織起來的數(shù)據(jù)類型。數(shù)據(jù)抽象15

數(shù)據(jù)抽象是指“定義和實(shí)現(xiàn)相分離”，即將一個(gè)類型的數(shù)據(jù)及其上的操作的邏輯含義和具體實(shí)現(xiàn)相分離，只考慮執(zhí)行什么操作(做什么)，而不考慮怎樣實(shí)現(xiàn)這些操作(怎樣做)。

數(shù)據(jù)抽象是一種信息隱蔽技術(shù)，可利用數(shù)據(jù)抽象研究復(fù)雜對象，忽略次要和實(shí)現(xiàn)細(xì)節(jié)，抽象出本質(zhì)特征，抽象層次越高，復(fù)用程度越高。

數(shù)據(jù)抽象是通過抽象數(shù)據(jù)類型來實(shí)現(xiàn)的。抽象數(shù)據(jù)類型16

抽象數(shù)據(jù)類型(AbstractDataType，ADT)是從問題的數(shù)學(xué)模型中抽象出來的邏輯結(jié)構(gòu)及定義在邏輯結(jié)構(gòu)上的一組操作，僅描述了數(shù)據(jù)的特性和數(shù)據(jù)操作的語法規(guī)則，隱藏了數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和操作的實(shí)現(xiàn)細(xì)節(jié)。

抽象數(shù)據(jù)類型是實(shí)現(xiàn)軟件模塊化設(shè)計(jì)思想的重要手段，一個(gè)抽象數(shù)據(jù)類型是描述一種特定功能的基本模塊，由各種基本模塊可組織和構(gòu)造起來一個(gè)大型的軟件系統(tǒng)。

在一般的面向?qū)ο笳Z言中，抽象數(shù)據(jù)類型通?？梢圆捎贸橄箢惢蚪涌诘姆绞竭M(jìn)行描述。第三部分算法算法的概念算法的定義

算法是有窮規(guī)則的集合，其規(guī)則確定一個(gè)解決某一特定類型問題的指令序列，其中每一條指令表示計(jì)算機(jī)的一個(gè)或者多個(gè)操作。算法的概念算法必須滿足以下5個(gè)特性。有窮性：對于任意的合法輸入值，算法必須在執(zhí)行有窮步驟后結(jié)束，并且每一步都在有窮的時(shí)間內(nèi)完成。確定性：算法對各種情況下執(zhí)行的每個(gè)操作都有確切的規(guī)定，算法的執(zhí)行者和閱讀者都能明確其含義和如何執(zhí)行，并且在任何條件下算法都只有一條執(zhí)行路徑。可行性：算法中的操作必須都可以通過已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)，并且每一條指令都符合語法規(guī)則，滿足語義要求，都能被確切執(zhí)行。有輸入：輸入數(shù)據(jù)是算法的處理對象，一個(gè)算法具有零個(gè)或多個(gè)輸入數(shù)據(jù)，既可以由算法指定，也可以在算法執(zhí)行過程中通過輸入得到。有輸出：輸出數(shù)據(jù)是算法對輸入數(shù)據(jù)進(jìn)行信息加工后得到的結(jié)果，輸出數(shù)據(jù)和輸入數(shù)據(jù)具有確定的對應(yīng)關(guān)系，即算法的功能。一個(gè)算法有一個(gè)或多個(gè)輸出數(shù)據(jù)。20基本目標(biāo)高效率商業(yè)策略正確性可讀性健壯性算法應(yīng)滿足應(yīng)用問題的需求，這是算法設(shè)計(jì)最重要、最基本的目標(biāo)。算法應(yīng)具有良好的容錯(cuò)性，可以檢查錯(cuò)誤是否出現(xiàn)并且對錯(cuò)誤進(jìn)行適當(dāng)?shù)奶幚?，即使輸入的?shù)據(jù)不合適，也能避免出現(xiàn)不可控的結(jié)果。算法的執(zhí)行時(shí)間越短，時(shí)間效率越高；算法執(zhí)行時(shí)所占的存儲(chǔ)空間越小，空間效率越高。時(shí)間效率和空間效率往往不可兼得，用戶在解決實(shí)際問題時(shí)要根據(jù)實(shí)際情況權(quán)衡得失，進(jìn)行高效率算法的設(shè)計(jì)。算法的表達(dá)思路應(yīng)清晰，層次分明，易于理解，可讀性強(qiáng)，以便于后續(xù)對算法的使用和修改。算法的概念

算法設(shè)計(jì)的4個(gè)基本目標(biāo)算法的概念

算法與數(shù)據(jù)結(jié)構(gòu)21算法建立在數(shù)據(jù)結(jié)構(gòu)之上，對數(shù)據(jù)結(jié)構(gòu)的操作需要使用算法來描述。算法設(shè)計(jì)依賴于數(shù)據(jù)的邏輯結(jié)構(gòu)，算法實(shí)現(xiàn)依賴于數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。22算法描述010203自然語言用中文或英文對算法進(jìn)行表達(dá)，簡單易懂，但缺乏嚴(yán)謹(jǐn)性。自然語言使用某種具體的程序設(shè)計(jì)語言（如Python語言）對算法進(jìn)行描述。此種方式嚴(yán)謹(jǐn)，算法可直接在計(jì)算機(jī)上執(zhí)行，但算法復(fù)雜、不易理解，需要借助大量的外部注釋才能使用戶明白。程序設(shè)計(jì)語言偽代碼是介于自然語言和程序設(shè)計(jì)語言之間的算法描述語言，是將程序設(shè)計(jì)語言的語法規(guī)則用自然語言進(jìn)行表示，忽略了嚴(yán)格的語法規(guī)則和描述細(xì)節(jié)，更易被用戶理解，并且更容易轉(zhuǎn)換成程序設(shè)計(jì)語言執(zhí)行。偽代碼23算法描述

例題設(shè)計(jì)算法求兩個(gè)整數(shù)的最大公約數(shù)。假設(shè)c為兩個(gè)整數(shù)a和b的最大公約數(shù)。用數(shù)學(xué)方法求兩個(gè)數(shù)的最大公約數(shù)，分別將a和b兩個(gè)整數(shù)分解成若干質(zhì)因數(shù)的乘積，再從中選擇最大的公約數(shù)。此種方法很難用于實(shí)際計(jì)算之中，因?yàn)榇髷?shù)的質(zhì)因數(shù)很難進(jìn)行分解。質(zhì)因數(shù)分解法中國古代的數(shù)學(xué)經(jīng)典著作《九章算術(shù)》中寫道：“以少減多，更相減損，求其等也，以等數(shù)約之，即除也，其所以相減者皆等數(shù)之重疊，顧以等數(shù)約之?！逼渲校葦?shù)即指兩數(shù)的最大公約數(shù)。更相減損法實(shí)際上，輾轉(zhuǎn)相除法就是現(xiàn)代版的更相減損術(shù)，使用循環(huán)實(shí)現(xiàn)：輾轉(zhuǎn)相除法算法分析24算法分析技術(shù)主要是通過某種方法討論算法的復(fù)雜度，評(píng)價(jià)算法的效率，以便在解決實(shí)際問題時(shí)根據(jù)實(shí)際情況和算法的優(yōu)缺點(diǎn)對算法進(jìn)行取舍。算法的優(yōu)劣主要通過算法復(fù)雜度進(jìn)行衡量，復(fù)雜度的高低反映了所需計(jì)算機(jī)資源的多少。計(jì)算機(jī)資源主要包括時(shí)間資源和空間資源。因此算法的復(fù)雜度通常以時(shí)間復(fù)雜度和空間復(fù)雜度來體現(xiàn)。算法分析

算法的時(shí)間復(fù)雜度25R算法的時(shí)間復(fù)雜度(TimeComplexity)是指算法的執(zhí)行時(shí)間隨問題規(guī)模的變化而變化的趨勢，反映算法執(zhí)行時(shí)間的長短。

算法分析

算法的時(shí)間復(fù)雜度通常采用算法的漸進(jìn)分析中的大O表示法作為算法時(shí)間復(fù)雜度的漸進(jìn)度量值，稱為算法的漸進(jìn)時(shí)間復(fù)雜度。大O表示法是指當(dāng)且僅當(dāng)存在正整數(shù)c和n?0，使得0≤T(n)≤cf(n)對所有的n≥n0成立時(shí)，算法執(zhí)行時(shí)間的增長率與f(n)的增長率相同，記為T(n)=O(f(n))。一般地，如果f(n)=aknk+ak-1nk-1+…+a1n1+a0，且ai≥0，T(n)=O(nk)，即使用大O表示法時(shí)只需保留關(guān)于數(shù)據(jù)元素個(gè)數(shù)n的多項(xiàng)式的最高次冪的項(xiàng)并去掉其系數(shù)。比如，若算法的執(zhí)行時(shí)間是常數(shù)級(jí)，不依賴數(shù)據(jù)量的大小，則時(shí)間復(fù)雜度為O(1)；若算法的執(zhí)行時(shí)間與數(shù)據(jù)量為線性關(guān)系，則時(shí)間復(fù)雜度為O(n)；對數(shù)級(jí)、平方級(jí)、立方級(jí)、指數(shù)級(jí)的時(shí)間復(fù)雜度分別為O(log2n)、O(n2)、O(n3)、O(2n)。這些函數(shù)按數(shù)量級(jí)遞增排列具有下列關(guān)系：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)27R010203一個(gè)循環(huán)的時(shí)間代價(jià)=循環(huán)次數(shù)每次執(zhí)行的基本指令數(shù)目多個(gè)并列的循環(huán)的時(shí)間代價(jià)=每個(gè)循環(huán)的時(shí)間代價(jià)之和多層嵌套循環(huán)的時(shí)間代價(jià)=每層循環(huán)的時(shí)間代價(jià)之積算法分析

算法的時(shí)間復(fù)雜度循環(huán)語句的時(shí)間代價(jià)一般可用以下3條原則進(jìn)行分析：算法分析

算法的空間復(fù)雜度算法的空間復(fù)雜度(SpaceComplexity)是指算法執(zhí)行時(shí)所占用的額外存儲(chǔ)空間量隨問題規(guī)模的變化而變化的趨勢。執(zhí)行一個(gè)算法所需要的存儲(chǔ)空間主要包含以下兩個(gè)部分。(1)固定空間部分：主要包括算法的程序指令、常量、變量所占的空間，與所處理問題的規(guī)模無關(guān)。(2)可變空間部分：主要包括輸入的數(shù)據(jù)元素占用的空間和程序運(yùn)行過程中額外的存儲(chǔ)空間，與處理問題的規(guī)模有關(guān)。算法分析

算法的空間復(fù)雜度當(dāng)問題的規(guī)模為n時(shí)，S(n)表示此時(shí)算法占用的存儲(chǔ)空間量，稱為算法的空間復(fù)雜度，當(dāng)n增大時(shí)S(n)也隨之增大。通常采用算法的漸進(jìn)分析中的大O表示法作為算法空間復(fù)雜度的漸進(jìn)度量值，稱為算法的漸進(jìn)空間復(fù)雜度，記作S(n)=O(f(n))，其分析與算法的漸進(jìn)時(shí)間復(fù)雜度相同。算法描述

例題設(shè)n為正整數(shù)，試確定下列程序段中語句“x+=1”的頻度。算法描述

例題設(shè)n為正整數(shù)，試確定下列程序段中語句“x+=1”的頻度。算法描述

例題設(shè)n為正整數(shù)，試確定下列程序段中語句“x+=1”的頻度。解：(1)i為1時(shí)，j值只能取1，語句執(zhí)行一次；i為2時(shí)，j可取1或2，語句執(zhí)行兩次；i為n時(shí)，j可取1、2、…,n，語句執(zhí)行n次，所以語句頻度=1+2+…+n=n(n+1)/2。(2)i為1時(shí)，j值只能取1，k值可取1、2、…、n，語句執(zhí)行n次；i為2時(shí)，j可取1或2，k值可取1、2、…、n，語句執(zhí)行2n次；i為n時(shí)，j可取1、2、…、n，語句執(zhí)行n×n次，所以語句頻度=n2(n+1)/2。(3)i與j初始和為1，其后每循環(huán)一次i和j中有且僅有一個(gè)值增1，即i與j的和增1。由于循環(huán)條件為i+j<=n，因此循環(huán)共執(zhí)行n次。所以，語句頻度為n。(4)分析y的初始值為100，當(dāng)y≤0時(shí)循環(huán)結(jié)束，x++每執(zhí)行10次y減小1，所以x+=1的語句頻度為1000。第四部分小結(jié)34小結(jié)(1)數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)兩個(gè)方面。數(shù)據(jù)的邏輯結(jié)構(gòu)分為集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)4種。數(shù)據(jù)的