數(shù)據(jù)結(jié)構(gòu)（從概念到算法）課件

第1章緒論01020304目錄CONTENTS0506數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)的基本概念算法設(shè)計(jì)的一般步驟算法復(fù)雜度分析算法分析實(shí)例本章小結(jié)01PART數(shù)據(jù)結(jié)構(gòu)概述首先介紹數(shù)據(jù)結(jié)構(gòu)（DataStructure）。數(shù)據(jù)（Data）是指數(shù)字化后的能被計(jì)算機(jī)處理的符號(hào)，它可以是比較容易理解的數(shù)值型數(shù)據(jù)，如某位學(xué)生的年齡為20歲、在某門功課上取得成績(jī)?yōu)?0分等，也可以是其他相對(duì)難處理的非數(shù)值型數(shù)據(jù)，如文本、圖片、音頻、視頻等。結(jié)構(gòu)（Structure）即為事物之間的內(nèi)在關(guān)系，如一所大學(xué)包含若干學(xué)院，每個(gè)學(xué)院又包含若干研究所，這是一種層次結(jié)構(gòu)。其數(shù)據(jù)結(jié)構(gòu)示意圖如圖所示。數(shù)據(jù)結(jié)構(gòu)概述為了編寫(xiě)一個(gè)好的程序，開(kāi)發(fā)者必須分析待處理對(duì)象的特性以及各處理對(duì)象之間的內(nèi)在關(guān)系。構(gòu)建數(shù)據(jù)結(jié)構(gòu)的過(guò)程有下面幾個(gè)步驟：用計(jì)算機(jī)解決具體問(wèn)題時(shí)的主要步驟如下。（1）從具體問(wèn)題抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型。（2）設(shè)計(jì)一個(gè)解決此數(shù)學(xué)模型的算法。（3）編寫(xiě)程序，并進(jìn)行測(cè)試、調(diào)試，直至問(wèn)題得到最終解答。數(shù)據(jù)結(jié)構(gòu)概述其中建立數(shù)學(xué)模型即是分析具體問(wèn)題的過(guò)程，它包括以下兩個(gè)步驟。（1）分析具體問(wèn)題中的操作對(duì)象。（2）找出這些對(duì)象間的關(guān)系，并用數(shù)學(xué)語(yǔ)言描述。數(shù)學(xué)模型主要分為以下兩大類。第一類是數(shù)值計(jì)算類，數(shù)據(jù)類型基本都是整型、實(shí)型、浮點(diǎn)型等原子類型，可用已有的數(shù)學(xué)理論進(jìn)行建模，第二類是非數(shù)值計(jì)算類。02PART數(shù)據(jù)結(jié)構(gòu)的基本概念（1）數(shù)據(jù)。數(shù)據(jù)即是所有能輸入計(jì)算機(jī)中并被計(jì)算機(jī)程序加工、處理符號(hào)的總稱，如整數(shù)、實(shí)數(shù)、字符、音頻、圖片、視頻等。（2）數(shù)據(jù)元素。數(shù)據(jù)元素是數(shù)據(jù)的基本單位。在不同的數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素有不同的稱呼，如記錄、結(jié)點(diǎn)或頂點(diǎn)。它在計(jì)算機(jī)程序中通常被作為一個(gè)整體進(jìn)行考慮和處理。（3）數(shù)據(jù)項(xiàng)。數(shù)據(jù)項(xiàng)是數(shù)據(jù)不可分割的最小單位。一個(gè)數(shù)據(jù)元素可由一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)組成，如數(shù)據(jù)元素(姓名、年齡)由兩個(gè)數(shù)據(jù)項(xiàng)“姓名”和“年齡”組成。（4）數(shù)據(jù)對(duì)象。數(shù)據(jù)對(duì)象是由性質(zhì)相同（或者說(shuō)類型相同）的數(shù)據(jù)元素組成的集合，數(shù)據(jù)對(duì)象是數(shù)據(jù)的一個(gè)子集。實(shí)例說(shuō)明如下。由4個(gè)整數(shù)組成的數(shù)據(jù)對(duì)象：D1={20,-

30,88,45}由正整數(shù)組成的數(shù)據(jù)對(duì)象：D2={1,2,3,…}數(shù)據(jù)結(jié)構(gòu)的基本概念（5）數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)元素之間的關(guān)系稱為結(jié)構(gòu)，主要有4類基本結(jié)構(gòu)，如下圖所示。①集合：數(shù)據(jù)元素之間的關(guān)系比較松散。②線性結(jié)構(gòu)：數(shù)據(jù)元素之間有嚴(yán)格的先后次序關(guān)系。③樹(shù)狀結(jié)構(gòu)：數(shù)據(jù)元素之間是一對(duì)多的層次關(guān)系。④圖結(jié)構(gòu)：數(shù)據(jù)元素之間是多對(duì)多的關(guān)系。數(shù)據(jù)結(jié)構(gòu)的基本概念（6）存儲(chǔ)結(jié)構(gòu)。所有的數(shù)據(jù)輸入計(jì)算機(jī)后都必須存儲(chǔ)在計(jì)算機(jī)中才能進(jìn)行相關(guān)操作。數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的映像（mapping）稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，也稱為存儲(chǔ)表示、物理結(jié)構(gòu)、物理表示。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)分為以下兩大類。①順序存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)元素順序存放在內(nèi)存儲(chǔ)器的連續(xù)存儲(chǔ)單元中。例如線性表L=('A','B','C','D')存放在內(nèi)存儲(chǔ)器中，首地址是a，接下來(lái)是a+1、a+2、a+3，如下圖所示。數(shù)據(jù)結(jié)構(gòu)的基本概念②非順序存儲(chǔ)結(jié)構(gòu)（也稱為鏈接存儲(chǔ)結(jié)構(gòu)）：數(shù)據(jù)元素存放在非連續(xù)的存儲(chǔ)空間中。例如單鏈表中的數(shù)據(jù)元素'A'、'B'、'C'、'D'分別存放在地址a、地址b、地址c、地址d中，而這4個(gè)地址是分散的。但為了表示這4個(gè)元素有前驅(qū)和后繼的線性關(guān)系，我們用指針來(lái)構(gòu)建元素之間的聯(lián)系。例如，一個(gè)頭指針Head指向數(shù)據(jù)'A'的結(jié)點(diǎn)地址，數(shù)據(jù)'A'的指針指向數(shù)據(jù)'B'的結(jié)點(diǎn)地址，數(shù)據(jù)'B'的指針指向數(shù)據(jù)'C'的結(jié)點(diǎn)地址，數(shù)據(jù)'C'的指針指向數(shù)據(jù)'D'的結(jié)點(diǎn)地址，具體如圖所示。數(shù)據(jù)結(jié)構(gòu)的基本概念上圖數(shù)據(jù)元素存儲(chǔ)的地址在整體上具有前后次序，但實(shí)際對(duì)單鏈表數(shù)據(jù)元素所分配的存儲(chǔ)空間是隨機(jī)的。如下圖所示，數(shù)據(jù)元素'A'在物理存儲(chǔ)地址上可能位于數(shù)據(jù)元素'B'和'D'存儲(chǔ)地址之后。（7）數(shù)據(jù)類型。數(shù)據(jù)類型（DataType）是一個(gè)所有可能取值構(gòu)成的集合和定義在這些值上的一組操作的總稱。數(shù)據(jù)類型主要分為兩類：一類是原子類型，如int、char、float等；另一類是結(jié)構(gòu)類型，如基于線性、樹(shù)狀、圖等結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)定義。數(shù)據(jù)結(jié)構(gòu)的基本概念（8）抽象數(shù)據(jù)類型。抽象數(shù)據(jù)類型（AbstractDataType，ADT）是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。它是對(duì)數(shù)據(jù)結(jié)構(gòu)邏輯上的定義，與計(jì)算機(jī)的實(shí)現(xiàn)無(wú)關(guān)。一個(gè)抽象數(shù)據(jù)類型可以用一個(gè)三元組來(lái)表示，如(D,S,P)，其中D表示數(shù)據(jù)對(duì)象，S是D中數(shù)據(jù)元素之間的關(guān)系集，P是對(duì)D中數(shù)據(jù)元素的基本操作。一般形式如下。03PART算法設(shè)計(jì)的一般步驟好的程序需要有好的數(shù)據(jù)結(jié)構(gòu)和算法。選擇好的數(shù)據(jù)結(jié)構(gòu)可以為算法設(shè)計(jì)打下良好基礎(chǔ)，數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)密不可分。算法是對(duì)特定問(wèn)題求解步驟的一種描述。換言之，算法給出了求解一個(gè)問(wèn)題的思路和策略。一個(gè)算法應(yīng)該具有以下5個(gè)特征。（1）有窮性，即算法的最基本特征，要求算法必須在有限步（或有限時(shí)間）之后執(zhí)行完成。（2）確定性，即每條指令或步驟都無(wú)二義性，具有明確的含義。（3）可行性，即算法中的操作都可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)。（4）有0或多個(gè)輸入。（5）至少有一個(gè)輸出。1.3.1算法定義與性質(zhì)算法設(shè)計(jì)的一般步驟針對(duì)算法的5個(gè)特征，現(xiàn)給出算法的設(shè)計(jì)要求如下。（1）正確性：算法有4個(gè)不同層次的正確性，即無(wú)語(yǔ)法錯(cuò)誤。對(duì)n組輸入能產(chǎn)生正確結(jié)果，對(duì)特殊輸入能產(chǎn)生正確結(jié)果，對(duì)所有輸入能產(chǎn)生正確結(jié)果（理想狀態(tài)）。（2）可讀性：算法的變量命名、格式符合行業(yè)規(guī)范，并在關(guān)鍵處給出注釋，以提升算法的可理解性。（3）健壯性：算法能對(duì)不合理的輸入給出相應(yīng)的提示信息，并做出相應(yīng)處理。（4）高執(zhí)行效率與低存儲(chǔ)量開(kāi)銷：涉及算法的時(shí)間復(fù)雜度和空間復(fù)雜度評(píng)判。1.3.1算法定義與性質(zhì)算法設(shè)計(jì)的一般步驟算法設(shè)計(jì)出來(lái)后有多種表述方法，一般有如下幾種描述工具：第一種是自然語(yǔ)言；第二種是程序設(shè)計(jì)語(yǔ)言；第三種是程序流程圖；第四種是偽碼語(yǔ)言，它是一種包括高級(jí)程序設(shè)計(jì)語(yǔ)言3種基本結(jié)構(gòu)（順序、選擇、循環(huán)）和自然語(yǔ)言成分的“面向讀者”的語(yǔ)言；第五種是類C語(yǔ)言，其是介于偽碼語(yǔ)言和程序設(shè)計(jì)語(yǔ)言之間的一種表示形式，保留了C語(yǔ)言的精華，不拘泥于C語(yǔ)言的語(yǔ)法細(xì)節(jié)，同時(shí)添加一些C++的成分，特點(diǎn)是便于理解、閱讀且能方便地轉(zhuǎn)換成C語(yǔ)言。1.3.1算法定義與性質(zhì)算法設(shè)計(jì)的一般步驟算法設(shè)計(jì)的一般過(guò)程可以歸納為以下幾個(gè)步驟。（1）分析問(wèn)題：通過(guò)對(duì)問(wèn)題進(jìn)行詳細(xì)的分析，確定算法主要策略。（2）確定數(shù)據(jù)結(jié)構(gòu)與算法：確定使用的數(shù)據(jù)結(jié)構(gòu)，并在此基礎(chǔ)上設(shè)計(jì)對(duì)此數(shù)據(jù)結(jié)構(gòu)實(shí)施各種操作的算法。（3）選用語(yǔ)言：選用某種高級(jí)程序設(shè)計(jì)語(yǔ)言將算法轉(zhuǎn)換成程序。（4）調(diào)試并運(yùn)行：測(cè)試修正語(yǔ)法錯(cuò)誤和邏輯錯(cuò)誤，保證程序可運(yùn)行。1.3.2算法設(shè)計(jì)步驟04PART算法復(fù)雜度分析同一個(gè)算法用不同的語(yǔ)言實(shí)現(xiàn)、用不同的編譯程序進(jìn)行編譯或在不同的計(jì)算機(jī)上運(yùn)行時(shí)，執(zhí)行時(shí)間可能不相同。因此，我們很難以算法的實(shí)際執(zhí)行時(shí)間來(lái)評(píng)判算法的效率，而是往往比較關(guān)注算法的時(shí)間開(kāi)銷相對(duì)于問(wèn)題規(guī)模變化的趨勢(shì)，也就是時(shí)間復(fù)雜度。設(shè)n為求解問(wèn)題的規(guī)模，即為數(shù)據(jù)量的大小。首先，不區(qū)分算法中基本操作或語(yǔ)句執(zhí)行時(shí)間開(kāi)銷上的差異，計(jì)算算法（或程序）中基本操作或語(yǔ)句重復(fù)執(zhí)行次數(shù)總和，記作f(n)，稱為語(yǔ)句頻度。1.4.1算法時(shí)間復(fù)雜度分析算法復(fù)雜度分析在此基礎(chǔ)上，需要執(zhí)行下面步驟來(lái)計(jì)算算法時(shí)間復(fù)雜度。（1）只保留問(wèn)題規(guī)模n的最高階項(xiàng)。（2）去掉f(n)中的所有常量系數(shù)。所得算法的時(shí)間復(fù)雜度，記作T(n)，用O

表示。對(duì)于一個(gè)函數(shù)f

(n)，當(dāng)n

趨于無(wú)窮大時(shí)，若T

(n)/

f

(n)的極限值為不等于0

的常數(shù)，則稱f

(n)是T

(n)的同數(shù)量級(jí)函數(shù)，記作T

(n)=O

(f

(n))，稱O

(f

(n))為算法的漸進(jìn)時(shí)間復(fù)雜度（簡(jiǎn)稱時(shí)間復(fù)雜度）。也就是說(shuō)，只求出T

(n)的最高階（數(shù)量級(jí)），忽略其低階項(xiàng)和常系數(shù)，這樣既可以簡(jiǎn)化T

(n)的計(jì)算，又能客觀反映出針對(duì)問(wèn)題規(guī)模n

的算法時(shí)間性能。1.4.1算法時(shí)間復(fù)雜度分析算法復(fù)雜度分析

1.4.1算法時(shí)間復(fù)雜度分析在該算法中，問(wèn)題規(guī)模為n，即算法中涉及的數(shù)據(jù)量大小，如n=10表示計(jì)算10個(gè)數(shù)的和，n=100表示計(jì)算100個(gè)數(shù)的和。無(wú)論n取什么值，都是通過(guò)以下3條語(yǔ)句完成其計(jì)算：一條輸入n，一條計(jì)算s，最后一條輸出s。每條語(yǔ)句執(zhí)行1次，這樣，語(yǔ)句頻度為f(n)=3，時(shí)間復(fù)雜度為T(n)=O(f(n))=O(3)=O(1)，O(1)稱為常量階或常量數(shù)量級(jí)。算法復(fù)雜度分析常見(jiàn)的時(shí)間復(fù)雜度有O(1)、O(logn)、O(n)、O(nlogn)、O(n2)、O(n3)和

O(2n)，滿足關(guān)系O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)。常見(jiàn)時(shí)間復(fù)雜度的曲線圖如圖所示。1.4.1算法時(shí)間復(fù)雜度分析算法復(fù)雜度分析一個(gè)算法在計(jì)算機(jī)存儲(chǔ)器上所占用的存儲(chǔ)空間由存儲(chǔ)算法本身所占用的存儲(chǔ)空間、算法輸入及輸出數(shù)據(jù)所占用的存儲(chǔ)空間和為求解問(wèn)題所需要的輔

助空間組成。其中，空間復(fù)雜度是對(duì)算法運(yùn)行過(guò)程中所開(kāi)辟輔助空間大小的

度量。與時(shí)間復(fù)雜度類似，空間復(fù)雜度通常用O表示法來(lái)描述，如O(n)、O(nlogn)、O(nα)、O(2n)等。其中，n是問(wèn)題的規(guī)模。1.4.2算法空間復(fù)雜度分析算法復(fù)雜度分析計(jì)算斐波那契數(shù)列的第n項(xiàng)。斐波那契數(shù)列中第一項(xiàng)為1，第二項(xiàng)為1，從第三項(xiàng)開(kāi)始，每一項(xiàng)的值是它前兩項(xiàng)數(shù)值之和。用變量f表示第n項(xiàng)，f1和f2分別表示第n項(xiàng)的前2項(xiàng)，算法如下。1.4.2算法空間復(fù)雜度分析由于此例函數(shù)中變量個(gè)數(shù)固定，因此空間大小不隨n的改變而發(fā)生變化。當(dāng)一個(gè)算法的輔助空間為一個(gè)常量，即不隨著處理數(shù)據(jù)量n的大小變化而改變，算法的空間復(fù)雜度是O(1)。算法復(fù)雜度分析同前例問(wèn)題，采用遞歸的方式計(jì)算斐波那契數(shù)列。其遞歸算法如下。1.4.2算法空間復(fù)雜度分析在遞歸算法中，空間復(fù)雜度=遞歸的深度×每次遞歸空間的大小。其中遞歸過(guò)程可抽象為右圖所示的二叉樹(shù)，因此本例中遞歸的深度就是該“遞歸樹(shù)”的高度。如圖所示，當(dāng)輸入變量為4時(shí)，該遞歸樹(shù)的高度為4，此時(shí)空間復(fù)雜度為4×每次遞歸空間的大小。依此類推，當(dāng)輸入變量為n時(shí)，該遞歸樹(shù)的高度為n，空間復(fù)雜度為n×每次遞歸空間的大小。每次遞歸所需輔助空間大小為O(1)。該算法的空間復(fù)雜度隨變量n的改變而改變，因此空間復(fù)雜度是O(n)。05PART算法分析實(shí)例例：冒泡排序是一個(gè)經(jīng)典的排序算法。假定按遞增次序?qū)Υ判驍?shù)組中的n個(gè)數(shù)進(jìn)行排序，則需要對(duì)這n個(gè)數(shù)進(jìn)行n-1趟冒泡處理。第一趟中，首先將這n個(gè)數(shù)中的第1個(gè)數(shù)與第2個(gè)數(shù)進(jìn)行比較，如果前面的數(shù)大于后面的數(shù)，就將這兩個(gè)數(shù)進(jìn)行交換；接著第2個(gè)數(shù)與第3個(gè)數(shù)進(jìn)行比較，如果前面的數(shù)大于后面的數(shù)，也將這兩個(gè)數(shù)進(jìn)行交換；……最后第n-1個(gè)數(shù)與第n個(gè)數(shù)進(jìn)行比較，如果前面的數(shù)大于后面的數(shù)，同樣將這兩個(gè)數(shù)進(jìn)行交換，完成排序的第一趟冒泡處理。第一趟中共進(jìn)行了n-1對(duì)相鄰數(shù)的比較，這n個(gè)數(shù)中最大的數(shù)被交換到最后的目標(biāo)位置。第二趟中，需要對(duì)剩下的n-1個(gè)數(shù)采用相同的處理方法，每經(jīng)過(guò)一趟冒泡排序處理，待處理的數(shù)就少一個(gè)。這樣，在第n-1趟時(shí)，就還剩下2個(gè)數(shù)據(jù)需要處理。對(duì)這一對(duì)數(shù)進(jìn)行比較，并將較大數(shù)交換到后面后，就有n-1個(gè)數(shù)到達(dá)了目標(biāo)位置，這樣最后一個(gè)數(shù)自然也在目標(biāo)位置上，完成了排序操作。算法分析實(shí)例根據(jù)上述算法思想，給出如下冒泡排序算法。算法分析實(shí)例在該算法中，外層循環(huán)控制冒泡排序的趟數(shù)，執(zhí)行了n-1次，內(nèi)層循環(huán)控制每趟冒泡排序時(shí)相鄰兩個(gè)數(shù)的比較，第一趟有n-1對(duì)、第二趟有n-2對(duì)……最后一趟有1對(duì)，這樣內(nèi)層循環(huán)控制一共執(zhí)行n(n-1)/2次，內(nèi)層循環(huán)體的比較語(yǔ)句也要執(zhí)行n(n-1)/2次。接下來(lái)對(duì)用于交換數(shù)據(jù)的3條賦值語(yǔ)句需要進(jìn)行最好情況和最壞情況分析。最好情況下，即待排序的n個(gè)數(shù)，初始狀態(tài)就是遞增有序的，則交換數(shù)據(jù)的語(yǔ)句一次都不執(zhí)行；最壞情況下，即待排序的n個(gè)數(shù)，初始狀態(tài)是遞減的，則每次比較后都會(huì)發(fā)生數(shù)據(jù)交換，語(yǔ)句執(zhí)行次數(shù)為3n(n-1)/2次。排序后用循環(huán)語(yǔ)句輸出n個(gè)數(shù)，語(yǔ)句執(zhí)行次數(shù)為2n次。這樣整個(gè)算法的語(yǔ)句頻度在最好情況下為f(n)=n-1+n(n-1)+2n=n2+2n-1，在最壞情況下為f(n)=5n2/2+n/2-1。時(shí)間復(fù)雜度T最好(n)=T最壞(n)=O(n2)，即在任何情況下，時(shí)間復(fù)雜度都為平方數(shù)量級(jí)。算法在執(zhí)行過(guò)程中，需要一個(gè)temp變量輔助空間來(lái)進(jìn)行相鄰數(shù)據(jù)的交換，因此空間復(fù)雜度為O(1)。算法分析實(shí)例下面對(duì)該算法進(jìn)行改進(jìn)。在第i趟冒泡排序中，對(duì)n-i+1個(gè)數(shù)進(jìn)行兩兩比較，共有n-i對(duì)，如果前面的數(shù)大于后面的數(shù)，就需要進(jìn)行數(shù)據(jù)的交換；如果在這趟排序中沒(méi)有發(fā)生數(shù)據(jù)的交換，表示這n-i+1個(gè)數(shù)已經(jīng)有序，沒(méi)有必要再做下一趟冒泡排序。所以每一趟開(kāi)始時(shí)，設(shè)置一個(gè)變量change=false;，一旦發(fā)生數(shù)據(jù)交換，就將change修改成true。結(jié)束時(shí)，若change未變，表示未發(fā)生數(shù)據(jù)交換，即已遞增有序。算法分析實(shí)例下面給出冒泡排序改進(jìn)算法。算法分析實(shí)例在改