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

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

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

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

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

寬wide，面積area；

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

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

楊潤(rùn)生男

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

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

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

82/07/12廣州

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

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

數(shù)據(jù)項(xiàng)4.數(shù)據(jù)對(duì)象具有相同特征的數(shù)據(jù)元素的有限集合。例如：某個(gè)學(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ù)元素的集合。

一、基本概念例如一個(gè)12位的十進(jìn)制數(shù)可以用三個(gè)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ù)對(duì)象)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)。通常簡(jiǎn)稱為數(shù)據(jù)結(jié)構(gòu)。一、基本概念7.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示，又稱物理結(jié)構(gòu)。是邏輯結(jié)構(gòu)在存儲(chǔ)器中的映像。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é)生基本情況登記表，記錄了每個(gè)學(xué)生的學(xué)號(hào)姓名專業(yè)政治面貌，表中的記錄是按學(xué)生的學(xué)號(hào)順序排列的。學(xué)號(hào)姓名 專業(yè) 政治面藐

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

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

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

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

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

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

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

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

001003002004006005008007學(xué)生間學(xué)號(hào)順序關(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個(gè)成員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)的存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)包括結(jié)點(diǎn)的值及結(jié)點(diǎn)之間的關(guān)系。1.順序存儲(chǔ)(順序映像)只存儲(chǔ)結(jié)點(diǎn)(數(shù)據(jù)元素)的值。結(jié)點(diǎn)之間的關(guān)系：由存儲(chǔ)單元的相鄰關(guān)系隱含地表示。適合于線性結(jié)構(gòu)。在高級(jí)語(yǔ)言中常用數(shù)組表示順序存儲(chǔ)結(jié)構(gòu)。1.2數(shù)據(jù)結(jié)構(gòu)的基本概念地址數(shù)據(jù)3142331566316783173431887例：23，66，78，34，87三、數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)2.鏈接存儲(chǔ)（非順序映像）存儲(chǔ)結(jié)點(diǎn)的值和結(jié)點(diǎn)之間的關(guān)系。用指針表示結(jié)點(diǎn)之間的關(guān)系，是各結(jié)點(diǎn)的后繼結(jié)點(diǎn)的地址。兩部分?jǐn)?shù)據(jù)域：存儲(chǔ)結(jié)點(diǎn)自身的值指針域：存儲(chǔ)該結(jié)點(diǎn)的各后繼結(jié)點(diǎn)的存儲(chǔ)單元的地址1.2數(shù)據(jù)結(jié)構(gòu)的基本概念地址

datalink0001630002000254000500038200040004660001000550^00030004000100020005存儲(chǔ)結(jié)構(gòu)8266546350三、數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)邏輯表示例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>}

邏輯表示：存儲(chǔ)結(jié)構(gòu)：三、數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)adddataLlinkRlink0000A000100020001B000300040002C0005^0003D^^0004E^^0005F0006^0006G^^1.2數(shù)據(jù)結(jié)構(gòu)的基本概念四、數(shù)據(jù)類型1.定義數(shù)據(jù)類型是一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱。具體到高級(jí)語(yǔ)言中，例如整型、字符型等。整形上的加、減、乘、除操作。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)的一個(gè)概念，最早出現(xiàn)在高級(jí)語(yǔ)言中，用以刻畫程序操作對(duì)象的特性。用高級(jí)語(yǔ)言編寫的程序中，每個(gè)變量、常量或表達(dá)式都有一個(gè)它所屬的數(shù)據(jù)類型。四、數(shù)據(jù)類型抽象數(shù)據(jù)類型-ADT(AbstractDataType)

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

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

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

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

數(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ù)對(duì)象：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)我們通過(guò)固有的數(shù)據(jù)類型（高級(jí)語(yǔ)言中已實(shí)現(xiàn)的數(shù)據(jù)類型）來(lái)表示和實(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ì)算機(jī)處理問(wèn)題編制的一組指令集數(shù)據(jù)結(jié)構(gòu)：?jiǎn)栴}的數(shù)學(xué)模型算法：處理問(wèn)題的策略，是對(duì)特定問(wèn)題求解步驟的一種描述，是有限長(zhǎng)的操作序列。

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

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

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

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

(1)程序中不含語(yǔ)法錯(cuò)誤

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

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

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

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

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

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

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

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

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

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

兩個(gè)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}

此時(shí)f(n)=n2

因此：

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

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

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

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

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

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

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

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

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

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

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

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