數(shù)據(jù)結(jié)構(gòu)-緒論

本課程教學(xué)內(nèi)容第一章緒論第二章線性表第三章棧和隊列第四章串第五章數(shù)組和廣義表第六章樹和二叉樹第七章圖第八章動態(tài)存儲管理第九章查找第十章內(nèi)部排序第十一章外部排序第十二章文件本課程內(nèi)容結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)線性結(jié)構(gòu)非線性結(jié)構(gòu)線性表?xiàng)ｊ犃写當(dāng)?shù)組和廣義表順序表鏈表單鏈表雙向鏈表循環(huán)鏈表兩種存儲結(jié)構(gòu)順序存儲鏈?zhǔn)酱鎯鋱D二叉樹的遍歷樹和森林哈夫曼樹及哈夫曼編碼圖的存儲圖的遍歷最小生成樹拓?fù)渑判蚝完P(guān)鍵路徑最短路徑查找排序靜態(tài)動態(tài)哈希表內(nèi)部外部第一章緒論1.1數(shù)據(jù)結(jié)構(gòu)的研究對象1.2數(shù)據(jù)結(jié)構(gòu)的基本概念1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)1.4算法和算法分析計算機(jī)的發(fā)展僅能進(jìn)行數(shù)值計算能處理各種非數(shù)值數(shù)據(jù)數(shù)據(jù)處理的種類數(shù)值數(shù)據(jù)

非數(shù)值數(shù)據(jù)

數(shù)(整數(shù),實(shí)數(shù))字符字符串文字圖形圖象聲音1.1數(shù)據(jù)結(jié)構(gòu)的研究對象

數(shù)值問題與非數(shù)值問題1）數(shù)值問題例1已知：游泳池的長len和寬wide，求面積area問題涉及的對象：游泳池的長len

寬wide，面積area；

對象之間的關(guān)系：area=lenwide1.1數(shù)據(jù)結(jié)構(gòu)的研究對象例2線性方程組求解

學(xué)號姓名性別出生日期籍貫入學(xué)成績所在班級 00201

楊潤生男

82/06/01廣州56100計算機(jī)2

00102石磊男83/12/21汕頭51200計算機(jī)1

00202李梅女83/02/23陽江53200計算機(jī)200301馬耀先男

82/07/12廣州

50900計算機(jī)32）非數(shù)值問題例1已知某年級學(xué)生情況,要求分班并按入學(xué)成績排列順序。在這類文檔管理的數(shù)學(xué)模型中,計算機(jī)處理的對象之間通常存在著一種最簡單的線性關(guān)系,這類數(shù)學(xué)模型稱為線性模型。1.1數(shù)據(jù)結(jié)構(gòu)的研究對象例2迷宮問題。1.1數(shù)據(jù)結(jié)構(gòu)的研究對象入口出口例3多岔路口交通燈的管理問題。1.1數(shù)據(jù)結(jié)構(gòu)的研究對象CDEAB數(shù)據(jù)結(jié)構(gòu)研究的問題：非數(shù)值數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系及如何表示，如何存儲，如何處理。1.1數(shù)據(jù)結(jié)構(gòu)的研究對象1.2數(shù)據(jù)結(jié)構(gòu)的基本概念一、基本概念二、數(shù)據(jù)結(jié)構(gòu)的分類三、數(shù)據(jù)結(jié)構(gòu)的存儲四、數(shù)據(jù)類型1.數(shù)據(jù)能被輸入計算機(jī)且能被計算機(jī)處理的一切對象。(是信息的載體，是客觀事物的符號表示。)

例如：整數(shù)，實(shí)數(shù)，字符串、圖象、聲音等都是數(shù)據(jù)。一、基本概念2.數(shù)據(jù)元素是現(xiàn)實(shí)世界中某獨(dú)立實(shí)體的數(shù)據(jù)描述。是數(shù)據(jù)結(jié)構(gòu)討論的基本單位，有時稱為結(jié)點(diǎn)、或記錄。一般由若干數(shù)據(jù)項(xiàng)組成。1.2數(shù)據(jù)結(jié)構(gòu)的基本概念3.數(shù)據(jù)項(xiàng)具有獨(dú)立意義的最小數(shù)據(jù)單位，是相對數(shù)據(jù)元素的，有時稱域或字段。一、基本概念姓名性別年齡專業(yè)班級

數(shù)據(jù)項(xiàng)4.數(shù)據(jù)對象具有相同特征的數(shù)據(jù)元素的有限集合。例如：某個學(xué)生信息(數(shù)據(jù)元素)1.2數(shù)據(jù)結(jié)構(gòu)的基本概念5.數(shù)據(jù)結(jié)構(gòu)結(jié)構(gòu)是數(shù)據(jù)元素之間的關(guān)系。數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)元素的集合。

一、基本概念例如一個12位的十進(jìn)制數(shù)可以用三個4位十進(jìn)制數(shù)表示：3214，6587，9345——a1(3214),a2(6587),a3(9345)在a1,a2,a3之間存在“次序”關(guān)系<a1,a2>,<a2,a3>3214,6587,9345≠6587,3214,9345a1a2a3a2a1a31.2數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的數(shù)學(xué)定義形式：

B=(D,R)二元組

D:數(shù)據(jù)元素的集合(數(shù)據(jù)對象)R:D上關(guān)系的集合，表示數(shù)據(jù)元素之間的前驅(qū)、后繼關(guān)系。一、基本概念1.2數(shù)據(jù)結(jié)構(gòu)的基本概念如：B=(D,R)D={a,b,c,d,e,f,g}R={<a,b>,<a,c>,<b,d>,<b,e>,<c,f>,<c,g>}cfbedag6.數(shù)據(jù)的邏輯結(jié)構(gòu)上述定義中“關(guān)系”描述的是數(shù)據(jù)元素之間的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。通常簡稱為數(shù)據(jù)結(jié)構(gòu)。一、基本概念7.數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的表示，又稱物理結(jié)構(gòu)。是邏輯結(jié)構(gòu)在存儲器中的映像。1.2數(shù)據(jù)結(jié)構(gòu)的基本概念1.集合二、數(shù)據(jù)結(jié)構(gòu)的分類2.線性結(jié)構(gòu)3.樹型結(jié)構(gòu)4.圖狀結(jié)構(gòu)1.2數(shù)據(jù)結(jié)構(gòu)的基本概念某班學(xué)生基本情況登記表，記錄了每個學(xué)生的學(xué)號姓名專業(yè)政治面貌，表中的記錄是按學(xué)生的學(xué)號順序排列的。學(xué)號姓名 專業(yè) 政治面藐

001 王洪 計算機(jī)黨員

002孫文計算機(jī)團(tuán)員

003 謝軍 計算機(jī)團(tuán)員

004 李輝 計算機(jī)團(tuán)員

005 沈祥福計算機(jī)黨員

006 余斌 計算機(jī)團(tuán)員

007 鞏力 計算機(jī)團(tuán)員

008 孔令輝計算機(jī)團(tuán)員學(xué)生基本情況登記表的圖示

001003002004006005008007學(xué)生間學(xué)號順序關(guān)系是一種線性結(jié)構(gòu)關(guān)系例一常用的數(shù)據(jù)結(jié)構(gòu)

1）線性結(jié)構(gòu)

2）非線性結(jié)構(gòu)

如樹、圖等二、數(shù)據(jù)結(jié)構(gòu)的分類家族的族譜

假設(shè)某家族有10個成員A，B，C，D，E，F(xiàn)，G，H，I，J，他們之間的血緣關(guān)系可以用如下圖表示。JIACBDHGFE例二、數(shù)據(jù)結(jié)構(gòu)的分類樹形結(jié)構(gòu)三、數(shù)據(jù)結(jié)構(gòu)的存儲數(shù)據(jù)結(jié)構(gòu)包括結(jié)點(diǎn)的值及結(jié)點(diǎn)之間的關(guān)系。1.順序存儲(順序映像)只存儲結(jié)點(diǎn)(數(shù)據(jù)元素)的值。結(jié)點(diǎn)之間的關(guān)系：由存儲單元的相鄰關(guān)系隱含地表示。適合于線性結(jié)構(gòu)。在高級語言中常用數(shù)組表示順序存儲結(jié)構(gòu)。1.2數(shù)據(jù)結(jié)構(gòu)的基本概念地址數(shù)據(jù)3142331566316783173431887例：23，66，78，34，87三、數(shù)據(jù)結(jié)構(gòu)的存儲2.鏈接存儲（非順序映像）存儲結(jié)點(diǎn)的值和結(jié)點(diǎn)之間的關(guān)系。用指針表示結(jié)點(diǎn)之間的關(guān)系，是各結(jié)點(diǎn)的后繼結(jié)點(diǎn)的地址。兩部分?jǐn)?shù)據(jù)域：存儲結(jié)點(diǎn)自身的值指針域：存儲該結(jié)點(diǎn)的各后繼結(jié)點(diǎn)的存儲單元的地址1.2數(shù)據(jù)結(jié)構(gòu)的基本概念地址

datalink0001630002000254000500038200040004660001000550^00030004000100020005存儲結(jié)構(gòu)8266546350三、數(shù)據(jù)結(jié)構(gòu)的存儲邏輯表示例1-1：有一線性結(jié)構(gòu)結(jié)點(diǎn)集合：

D={63，54，82，66，50}

關(guān)系為結(jié)點(diǎn)值的降序：

R={<82,66>,<66,63>,<63,54>,<54,50>}1.2數(shù)據(jù)結(jié)構(gòu)的基本概念例1-2：有一樹型結(jié)構(gòu)：

B=（D，R）

D={A，B，C，D，E，F(xiàn)，G}R={<A,B>,<A,C>,<B,D>,<B,E>,<C,F>,<F,G>}

邏輯表示：存儲結(jié)構(gòu)：三、數(shù)據(jù)結(jié)構(gòu)的存儲adddataLlinkRlink0000A000100020001B000300040002C0005^0003D^^0004E^^0005F0006^0006G^^1.2數(shù)據(jù)結(jié)構(gòu)的基本概念四、數(shù)據(jù)類型1.定義數(shù)據(jù)類型是一個值的集合和定義在這個值集上的一組操作的總稱。具體到高級語言中，例如整型、字符型等。整形上的加、減、乘、除操作。2.分類非結(jié)構(gòu)類型：原子類型結(jié)構(gòu)型：由一組原子類型或結(jié)構(gòu)類型按某種結(jié)構(gòu)組成1.2數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)類型是和數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的一個概念，最早出現(xiàn)在高級語言中，用以刻畫程序操作對象的特性。用高級語言編寫的程序中，每個變量、常量或表達(dá)式都有一個它所屬的數(shù)據(jù)類型。四、數(shù)據(jù)類型抽象數(shù)據(jù)類型-ADT(AbstractDataType)

是指一個數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。抽象數(shù)據(jù)類型和數(shù)據(jù)類型實(shí)質(zhì)上是一個概念。1.2數(shù)據(jù)結(jié)構(gòu)的基本概念抽象數(shù)據(jù)類型的描述抽象數(shù)據(jù)類型定義用三元組表示：（D，S，P），

其中，D是數(shù)據(jù)對象，

S是D上的關(guān)系集，

P是對D的基本操作集。定義格式：ADT抽象數(shù)據(jù)類型名{數(shù)據(jù)對象：<數(shù)據(jù)對象的定義>

數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系的定義>

基本操作：<基本操作的定義>（相當(dāng)于聲明若干函數(shù))}ADT抽象數(shù)據(jù)類型名

四、數(shù)據(jù)類型1.2數(shù)據(jù)結(jié)構(gòu)的基本概念如：用三元組定義出抽象數(shù)據(jù)類型復(fù)數(shù)ADTList{

數(shù)據(jù)對象：D={e1,e2|e1,e2∈實(shí)數(shù),e1,e2分別代表實(shí)部與虛部}

數(shù)據(jù)關(guān)系：R1={<e1,e2>|}

基本操作：復(fù)數(shù)相加復(fù)數(shù)相減

}四、數(shù)據(jù)類型1.2數(shù)據(jù)結(jié)構(gòu)的基本概念抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)我們通過固有的數(shù)據(jù)類型（高級語言中已實(shí)現(xiàn)的數(shù)據(jù)類型）來表示和實(shí)現(xiàn)抽象數(shù)據(jù)類型。

1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)1.2數(shù)據(jù)結(jié)構(gòu)的基本概念1.4算法和算法的衡量數(shù)據(jù)結(jié)構(gòu)+算法=程序程序：為計算機(jī)處理問題編制的一組指令集數(shù)據(jù)結(jié)構(gòu)：問題的數(shù)學(xué)模型算法：處理問題的策略，是對特定問題求解步驟的一種描述，是有限長的操作序列。

1.4算法和算法的衡量一、算法和算法的五個重要特性二、算法的設(shè)計原則三、時間復(fù)雜度和空間復(fù)雜度一、算法和算法的五個重要特性

算法有五個重要特性：1.有窮性2.確定性3.可行性4.輸入5.輸出1.3算法和算法的衡量一、算法和算法的五個重要特性1.有窮性：執(zhí)行有窮步后結(jié)束，且每一步在有窮時間內(nèi)完成。2.確定性：每一條指令必須有確切的含義，不會產(chǎn)生二義性。并且在任何條件下，算法都只有一條執(zhí)行的路徑。3.可行性：算法中描述的操作都是可以通過基本運(yùn)算執(zhí)行有

限次實(shí)現(xiàn)。4.輸入：有0個或多個輸入。作為算法加工對象的量值，通常體現(xiàn)為算法中的一組變量值，有些是算法執(zhí)行過程中輸入的，有些已被嵌入在算法中。5.輸出：有一個或多個輸出。是一組與輸入有確定關(guān)系的量值，是算法加工信息對象后得到的結(jié)果。這種確定關(guān)系即為算法的功能。

1.3算法和算法的衡量二、算法的設(shè)計原則衡量算法性能的標(biāo)準(zhǔn)。設(shè)計算法時，通常應(yīng)考慮達(dá)到以下目標(biāo)：1.正確性2.可讀性3.健壯性4.高效率與低存儲量的需求1.3算法和算法的衡量1.正確性（有效性）首先，算法能夠正確地實(shí)現(xiàn)預(yù)先規(guī)定的功能。其次，對正確性理解的四個層次：

(1)程序中不含語法錯誤

(2)程序?qū)捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果

(3)程序?qū)倪x擇的典型、苛刻而帶有刁難性的幾組輸入數(shù)據(jù)能得出滿足要求的結(jié)果

(4)對一切合法的輸入數(shù)據(jù)都能產(chǎn)生滿足要求的結(jié)果二、算法的設(shè)計原則1.3算法和算法的衡量2.可讀性可讀性好。算法的邏輯必須是清晰的、簡單的和結(jié)構(gòu)化的。有助于人對算法的理解，為了人的閱讀與交流。3.健壯性很好的容錯性，即提供例外處理，對不合理的數(shù)據(jù)作出反應(yīng)或進(jìn)行處理，而不會產(chǎn)生莫明其妙的結(jié)果或出現(xiàn)異常中斷、死機(jī)等現(xiàn)象，對于出錯應(yīng)報告出錯信息。三、算法的設(shè)計原則1.3算法和算法的衡量二、算法的設(shè)計原則4.高效率與低存儲量的需求

效率：指的是算法執(zhí)行的時間；

存儲量：指的是算法執(zhí)行過程中所需的最大存儲空間。通常，用時間復(fù)雜度來度量效率；用空間復(fù)雜度來試題存儲量。1.3算法和算法的衡量三、時間復(fù)雜度和空間復(fù)雜度1.時間復(fù)雜度(1)和算法執(zhí)行時間相關(guān)的因素：1.問題性質(zhì)

2.問題規(guī)模3.算法選用的策略4.編寫程序的語言5.編譯程序6.計算機(jī)執(zhí)行指令的速度(2)算法的時間復(fù)雜度與運(yùn)行算法的目標(biāo)計算機(jī)及描述算法的工具無關(guān)。取決于以下三方面：問題性質(zhì)問題規(guī)模算法性質(zhì)1.3算法和算法的衡量算法=控制結(jié)構(gòu)+原操作

三、時間復(fù)雜度和空間復(fù)雜度以基本操作重復(fù)執(zhí)行的次數(shù)作為算法的時間量度。重復(fù)執(zhí)行的次數(shù)是一個函數(shù)f(n)。自變量n稱做此算法的問題規(guī)模時間復(fù)雜度(漸進(jìn)時間復(fù)雜度)記作：

T(n)=O(f(n))

算法執(zhí)行時間的增長率和f(n)的增率相同。所研究的基本操作

1.3算法和算法的衡量例1-3

兩個n階矩陣相加，即C=A+B，其算法如下：#defineMAX20voidmatrixadd(int

n,int

a[MAX][MAX],int

b[MAX][MAX],int

c[MAX][MAX]){inti,j;for(i=0;i<n;i++)for(j=0;j<n;j++)

c[i][j]=a[i][j]+b[i][j];

//重復(fù)執(zhí)行的次數(shù)為n2}

此時f(n)=n2

因此：

T(n)=O(f(n))=O(n2)

三、時間復(fù)雜度和空間復(fù)雜度1.3算法和算法的衡量

基本操作大多在循環(huán)和遞歸中。時間復(fù)雜度通常具有的形式：

O(1)、O(log2n)、O(n)、O(n*log2n)、O(n2)、O(n3)、O(2n)、O(n!)

不同數(shù)量級對應(yīng)的值的關(guān)系：

O(1)<O(log2n)<O(n)<O(n*log2n)<O(n2)<O(n3)<O(2n)<O(n!)三、時間復(fù)雜度和空間復(fù)雜度1.3算法和算法的衡量

（1）有些算法，基本操作執(zhí)行次數(shù)難以確定，只考慮它的階數(shù)。（2）有些算法，基本操作執(zhí)行次數(shù)與問題的輸入數(shù)據(jù)有關(guān)，這時可考慮

算法平均時間復(fù)雜度

（3）算法在最壞情況下的時間復(fù)雜度三、時間復(fù)雜度和空間復(fù)雜度2．空間復(fù)雜度空間復(fù)雜度是算法在執(zhí)行過程中占用存儲容量的度量。算法的存儲量包含：輸入數(shù)據(jù)、程序和輔助變量所占的存儲空間。

空間復(fù)雜度是問題規(guī)模的函數(shù)，記為g(n)。

表示為：S(n)=O(g(n))

其中：n為問題的規(guī)模，g(n)與解決問題所用的存儲