第2章數(shù)據(jù)結(jié)構(gòu)與

算法概述前言計(jì)算機(jī)是一門(mén)研究用計(jì)算機(jī)進(jìn)行信息表示和處理的科學(xué)。這里面涉及到兩個(gè)問(wèn)題：信息的表示，信息的處理。信息的表示和組織又直接關(guān)系到處理信息的程序的效率。

隨著應(yīng)用問(wèn)題的不斷復(fù)雜，使許多系統(tǒng)程序和應(yīng)用程序的規(guī)模很大，結(jié)構(gòu)又相當(dāng)復(fù)雜。因此，必須分析待處理問(wèn)題中的對(duì)象的特征及各對(duì)象之間存在的關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)這門(mén)課所要研究的問(wèn)題。

數(shù)據(jù)結(jié)構(gòu)與算法是介于數(shù)學(xué)、計(jì)算機(jī)硬件、計(jì)算機(jī)軟件三者之間的核心技術(shù)，不僅是一般程序設(shè)計(jì)的基礎(chǔ)，而且是設(shè)計(jì)和實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫(kù)系統(tǒng)及其他系統(tǒng)程序和大型應(yīng)用程序的重要基礎(chǔ)。2.1數(shù)據(jù)結(jié)構(gòu)基本知識(shí)2.1.1數(shù)據(jù)結(jié)構(gòu)的概念2.1.2數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)4數(shù)據(jù)結(jié)構(gòu)的例子姓名電話號(hào)碼陳四。。。。。例1：電話號(hào)碼查詢系統(tǒng)

設(shè)有一個(gè)電話號(hào)碼薄，它記錄了N個(gè)人的名字和其相應(yīng)的電話號(hào)碼，假定按如下形式安排：(a1,b1)，(a2,b2)，…(an,bn)，其中ai,bi(i=1，2…n)

分別表示某人的名字和電話號(hào)碼。本問(wèn)題是一種典型的表格問(wèn)題。如表1-1，數(shù)據(jù)與數(shù)據(jù)成簡(jiǎn)單的一對(duì)一的線性關(guān)系。表1-1

線性表結(jié)構(gòu)例2：磁盤(pán)目錄文件系統(tǒng)

磁盤(pán)根目錄下有很多子目錄及文件，每個(gè)子目錄里又可以包含多個(gè)子目錄及文件，但每個(gè)子目錄只有一個(gè)父目錄，依此類(lèi)推：本問(wèn)題是一種典型的樹(shù)型結(jié)構(gòu)問(wèn)題，如圖1-1

，數(shù)據(jù)與數(shù)據(jù)成一對(duì)多的關(guān)系，是一種典型的非線性關(guān)系結(jié)構(gòu)—樹(shù)形結(jié)構(gòu)。圖1-1

樹(shù)形結(jié)構(gòu)例3：交通網(wǎng)絡(luò)圖

從一個(gè)地方到另外一個(gè)地方可以有多條路徑。本問(wèn)題是一種典型的網(wǎng)狀結(jié)構(gòu)問(wèn)題，數(shù)據(jù)與數(shù)據(jù)成多對(duì)多的關(guān)系，是一種非線性關(guān)系結(jié)構(gòu)。佛山惠州廣州中山東莞深圳珠海圖1-2

網(wǎng)狀結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)主要研究諸如線性結(jié)構(gòu)，樹(shù)形結(jié)構(gòu)及圖形結(jié)構(gòu)等非數(shù)值性數(shù)學(xué)模型在計(jì)算機(jī)中的表示及操作。82.1.1數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)數(shù)據(jù)元素?cái)?shù)據(jù)對(duì)象數(shù)據(jù)結(jié)構(gòu)9

數(shù)據(jù)(Data)

數(shù)據(jù)是信息的載體對(duì)客觀事物的符號(hào)表示能輸入到計(jì)算機(jī)中能被計(jì)算機(jī)加工處理數(shù)據(jù)的形式可以是整數(shù),實(shí)數(shù),字符,圖像,聲音…10數(shù)據(jù)元素(dataelement)數(shù)據(jù)元素(DataElement)

：是數(shù)據(jù)的基本單位，在程序中通常作為一個(gè)整體來(lái)進(jìn)行考慮和處理。一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)(DataItem)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)項(xiàng)是對(duì)客觀事物某一方面特性的數(shù)據(jù)描述。11數(shù)據(jù)項(xiàng)學(xué)號(hào)姓名性別出生日期聯(lián)系電話入學(xué)成績(jī)數(shù)據(jù)元素?cái)?shù)據(jù)對(duì)象(DataObject)是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。如字符集合C={‘A’,’B’,’C,…}。12數(shù)據(jù)、數(shù)據(jù)元素與數(shù)據(jù)對(duì)象關(guān)系13數(shù)據(jù)數(shù)據(jù)元素?cái)?shù)據(jù)對(duì)象2.1.2

數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)指同一數(shù)據(jù)對(duì)象中各個(gè)數(shù)據(jù)元素間存在的一種或多種特定關(guān)系的集合主要研究：數(shù)據(jù)元素之間固有的邏輯關(guān)系——數(shù)據(jù)邏輯結(jié)構(gòu)；數(shù)據(jù)元素及關(guān)系在計(jì)算機(jī)內(nèi)的表示——數(shù)據(jù)物理結(jié)構(gòu)；對(duì)數(shù)據(jù)結(jié)構(gòu)的操作——算法。14

數(shù)據(jù)元素之間的關(guān)系可以是元素之間代表某種含義的自然關(guān)系，也可以是為處理問(wèn)題方便而人為定義的關(guān)系，這種自然或人為定義的“關(guān)系”稱(chēng)為數(shù)據(jù)元素之間的邏輯關(guān)系，相應(yīng)的結(jié)構(gòu)稱(chēng)為邏輯結(jié)構(gòu)。數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)有四種基本類(lèi)型①

集合：結(jié)構(gòu)中的數(shù)據(jù)元素除了“同屬于一個(gè)集合”外，沒(méi)有其它關(guān)系。②線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。③

樹(shù)型結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。④圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系。15物理結(jié)構(gòu)-存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的存儲(chǔ)包括數(shù)據(jù)元素的存儲(chǔ)和元素之間的關(guān)系的表示。元素之間的關(guān)系在計(jì)算機(jī)中有兩種不同的表示方法：順序表示和非順序表示。由此得出兩種不同的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)：用數(shù)據(jù)元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)(關(guān)系)。

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：在每一個(gè)數(shù)據(jù)元素中增加一個(gè)存放另一個(gè)元素地址的指針(pointer)，用該指針來(lái)表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)(關(guān)系)。例：設(shè)有數(shù)據(jù)集合A={3.0,2.3,5.0,-8.5,11.0}，兩種不同的存儲(chǔ)結(jié)構(gòu)。順序結(jié)構(gòu)：數(shù)據(jù)元素存放的地址是連續(xù)的；鏈?zhǔn)浇Y(jié)構(gòu)：數(shù)據(jù)元素存放的地址是否連續(xù)沒(méi)有要求。數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是密不可分的兩個(gè)方面，一個(gè)算法的設(shè)計(jì)取決于所選定的邏輯結(jié)構(gòu)，而算法的實(shí)現(xiàn)依賴(lài)于所采用的存儲(chǔ)結(jié)構(gòu)。在C語(yǔ)言中，用一維數(shù)組表示順序存儲(chǔ)結(jié)構(gòu)；用結(jié)構(gòu)體類(lèi)型表示鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)的三個(gè)組成部分：邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間邏輯關(guān)系的描述

D_S=（D，S）存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)及其邏輯關(guān)系的表現(xiàn)稱(chēng)為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)或物理結(jié)構(gòu)。數(shù)據(jù)操作：對(duì)數(shù)據(jù)要進(jìn)行的運(yùn)算。本課程中將要討論的三種邏輯結(jié)構(gòu)及其采用的存儲(chǔ)結(jié)構(gòu)如圖所示。數(shù)據(jù)的邏輯結(jié)構(gòu)非線性結(jié)構(gòu)集合圖狀結(jié)構(gòu)有向圖無(wú)向圖樹(shù)形結(jié)構(gòu)一般樹(shù)二叉樹(shù)線性結(jié)構(gòu)一般線性表線性表推廣廣義表數(shù)組串受限線性表?xiàng)：完?duì)列線性表樹(shù)圖順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)復(fù)合存儲(chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)物理結(jié)構(gòu)（3）數(shù)據(jù)的操作

數(shù)據(jù)的操作是在數(shù)據(jù)的邏輯結(jié)構(gòu)上定義的操作算法。數(shù)據(jù)結(jié)構(gòu)的主要運(yùn)算包括：⑴建立(Create)一個(gè)數(shù)據(jù)結(jié)構(gòu)；⑵消除(Destroy)一個(gè)數(shù)據(jù)結(jié)構(gòu)；⑶從一個(gè)數(shù)據(jù)結(jié)構(gòu)中刪除(Delete)一個(gè)數(shù)據(jù)元素；⑷把一個(gè)數(shù)據(jù)元素插入(Insert)到一個(gè)數(shù)據(jù)結(jié)構(gòu)中；⑸對(duì)一個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行訪問(wèn)(Access)；⑹對(duì)一個(gè)數(shù)據(jù)結(jié)構(gòu)(中的數(shù)據(jù)元素)進(jìn)行修改(Modify)；⑺對(duì)一個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行排序(Sort)；⑻對(duì)一個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行查找(Search)。

202.1.3數(shù)據(jù)類(lèi)型與抽象數(shù)據(jù)類(lèi)型數(shù)據(jù)類(lèi)型抽象數(shù)據(jù)類(lèi)型21數(shù)據(jù)類(lèi)型是一個(gè)值的集合和定義在這個(gè)集合上的一組操作的總稱(chēng)。抽象數(shù)據(jù)類(lèi)型(ADT)指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。特點(diǎn)僅取決于邏輯特性,而與計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無(wú)關(guān)。抽象數(shù)據(jù)類(lèi)型的分類(lèi)原子類(lèi)型：值不可再分固定聚合類(lèi)型：成分?jǐn)?shù)目固定可變聚合類(lèi)型：成分?jǐn)?shù)目可變抽象數(shù)據(jù)類(lèi)型的定義三元組表示：ADT=(D,S,P)ADT抽象數(shù)據(jù)類(lèi)型名{數(shù)據(jù)對(duì)象D：<數(shù)據(jù)對(duì)象的定義>數(shù)據(jù)關(guān)系S：<數(shù)據(jù)關(guān)系的定義>基本操作P：<基本操作的定義>}ADT抽象數(shù)據(jù)類(lèi)型名2.2算法與算法分析2.2.1算法的概念2.2.2算法分析262.2.1算法概念為解決特定問(wèn)題所采用的步驟描述，它是指令的有限序列，其中每條指令表示一個(gè)或多個(gè)操作。27算法特性有窮性：算法執(zhí)行有限步后,自動(dòng)停止確定性：含義確切,無(wú)二義性可行性：每個(gè)基本操作均可實(shí)現(xiàn)輸入：零個(gè)或多個(gè)輸入輸出：至少一個(gè)輸出28算法描述自然語(yǔ)言流程圖類(lèi)語(yǔ)言高級(jí)語(yǔ)言29BEGINi:=1；s:=0；WHILE(i<=10)DO[s:=s+i；i:=i+1;]END類(lèi)語(yǔ)言流程圖2.2.2時(shí)間復(fù)雜度和空間復(fù)雜度能完成任務(wù)不一定是最好的算法,不同算法可能用的時(shí)間,空間和效率是不同的。一個(gè)算法的優(yōu)劣可以用時(shí)間復(fù)雜度與空間復(fù)雜度來(lái)衡量。算法分析內(nèi)容時(shí)間復(fù)雜度空間復(fù)雜度算法復(fù)雜度的數(shù)學(xué)表示用數(shù)學(xué)符號(hào)O表示，n為問(wèn)題規(guī)模例：O（1）；O（nk）；O（en）302.2.2時(shí)間復(fù)雜度和空間復(fù)雜度算法的優(yōu)劣用頻度和時(shí)間復(fù)雜度衡量語(yǔ)句頻度某語(yǔ)句執(zhí)行的次數(shù)，記作F(n)時(shí)間復(fù)雜度以語(yǔ)句頻度最大的語(yǔ)句度量31時(shí)間復(fù)雜度舉例

for(i=1;i<=n;i++)for(j=1;j<=n;j++){

c[i][j]=0;

for(k=1;k<=n;k++)

c[i][j]+=a[i][k]*b[k][j]

}32n2n3語(yǔ)句頻度f(wàn)(n)=n3+n2時(shí)間復(fù)雜度O(n3)常見(jiàn)的時(shí)間復(fù)雜度O(1)O(n)O(n2)O(log2n)O(nlog2n)O(2n).....33Tn2nnlogn2a·2n+b·n3+c·n2+d·n·log2(n)+e·n+fa<>0時(shí)，時(shí)間復(fù)雜度就是O(2n);a=0,b<>0時(shí)間復(fù)雜度就是O(n3);a,b=0,c<>0時(shí)間復(fù)雜度就是O