數(shù)據(jù)結(jié)構(gòu) Chap1學(xué)習(xí)資料

數(shù)據(jù)結(jié)構(gòu)Datastructures講課學(xué)時(shí)：36上機(jī)學(xué)時(shí)：12主講：陳琳教學(xué)安排課前說(shuō)明答疑chenlin1977@163.com2#實(shí)驗(yàn)樓303室計(jì)算機(jī)系軟件教研室上機(jī)與作業(yè)作業(yè)共交5次本學(xué)期共12課時(shí)上機(jī)成績(jī)?cè)u(píng)定卷面(70%)+上機(jī)(10%)+作業(yè)、點(diǎn)名(20%)犯規(guī)1次扣2分，3次扣10分，4次扣20分教材1.1數(shù)據(jù)結(jié)構(gòu)討論的范疇1.2基本概念1.3算法和算法的量度第一章緒論3NiklausWirth

Algorithm

+DataStructures=Programs程序設(shè)計(jì):算法:數(shù)據(jù)結(jié)構(gòu):為計(jì)算機(jī)處理問(wèn)題編制一組指令集

處理問(wèn)題的策略問(wèn)題的數(shù)學(xué)模型及定義在其上的一組操作41.1

數(shù)據(jù)結(jié)構(gòu)討論的范疇例:教材預(yù)定、采購(gòu)、發(fā)放算法:?模型：？圖書數(shù)據(jù)的增加、刪除、修改等線性表5概括地說(shuō)：

數(shù)據(jù)結(jié)構(gòu)是一門討論“描述現(xiàn)實(shí)世界實(shí)體的數(shù)學(xué)模型(非數(shù)值計(jì)算)及其上的操作在計(jì)算機(jī)中如何表示和實(shí)現(xiàn)”的學(xué)科。計(jì)算機(jī)的應(yīng)用已深入到世界的每一個(gè)角落。在計(jì)算機(jī)處理的問(wèn)題中，有些是數(shù)值型的計(jì)算，但越來(lái)越多的是非數(shù)值型的信息數(shù)據(jù)處理計(jì)算問(wèn)題。6《數(shù)據(jù)結(jié)構(gòu)》與其它課程關(guān)系圖：程序設(shè)計(jì)語(yǔ)言數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)庫(kù)人工智能專業(yè)基礎(chǔ)課操作系統(tǒng)編譯原理非線性程序設(shè)計(jì)離散數(shù)學(xué)計(jì)算機(jī)原理設(shè)計(jì)71.2

基本概念一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)二、數(shù)據(jù)類型三、抽象數(shù)據(jù)類型8一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)所有能被輸入到計(jì)算機(jī)中，且能被計(jì)算機(jī)處理的符號(hào)(數(shù)值、字符等)的集合。數(shù)據(jù):是計(jì)算機(jī)操作的對(duì)象的總稱。是計(jì)算機(jī)處理的信息的某種特定的符號(hào)表示形式。是數(shù)據(jù)（集合）中的一個(gè)“個(gè)體”,在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮和處理。是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位。數(shù)據(jù)元素:如:整數(shù)“5”,字符“N”等。

----是不可分割的“原子”9

其中每個(gè)款項(xiàng)稱為一個(gè)“數(shù)據(jù)項(xiàng)”它是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位數(shù)據(jù)元素也可以由若干款項(xiàng)構(gòu)成。例如：描述一個(gè)學(xué)生的數(shù)據(jù)元素稱之為組合項(xiàng)年月日姓名學(xué)號(hào)班號(hào)性別出生日期入學(xué)成績(jī)?cè)禹?xiàng)10數(shù)據(jù)結(jié)構(gòu)：帶結(jié)構(gòu)的數(shù)據(jù)元素的集合對(duì)于一個(gè)特性相同的數(shù)據(jù)元素的集合，如果在數(shù)據(jù)元素之間存在一種或多種特定的關(guān)系，則稱為一個(gè)數(shù)據(jù)結(jié)構(gòu)。指的是數(shù)據(jù)元素之間存在的關(guān)系11例如，當(dāng)用三個(gè)

4位的十進(jìn)制數(shù)表示一個(gè)含

12位數(shù)的十進(jìn)制數(shù)時(shí)，3214,6587,9345─a1(3214),a2(6587),a3(9345)則在數(shù)據(jù)元素a1、a2和a3

之間存在著“次序”關(guān)系

a1,a2

、

a2,a3

3214，6587，93456587，3214，9345a1a2a3a2a1a312又例，在2行3列的二維數(shù)組中六個(gè)元素{a1,a2,a3,a4,a5,a6}之間存在兩個(gè)關(guān)系:行的次序關(guān)系:row={<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}col={<a1,a4>,<a2,a5>,<a3,a6>}列的次序關(guān)系:

a1a2a3a4a5a6

若在

6個(gè)數(shù)據(jù)元素{a1,a2,a3,a4,a5,a6}之間存在如下的次序關(guān)系:{<ai,ai+1>|i=1,2,3,4,5}可見(jiàn)，不同的“關(guān)系”構(gòu)成不同的“結(jié)構(gòu)”則構(gòu)成一維數(shù)組的定義。13從關(guān)系或結(jié)構(gòu)分，數(shù)據(jù)結(jié)構(gòu)可歸結(jié)為以下四類:線性結(jié)構(gòu)樹(shù)形結(jié)構(gòu)圖狀結(jié)構(gòu)集合結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)是相互之間存在著某種邏輯關(guān)系的數(shù)據(jù)元素的集合。14數(shù)據(jù)結(jié)構(gòu)包括“邏輯結(jié)構(gòu)”

和“物理結(jié)構(gòu)”兩個(gè)方面:邏輯結(jié)構(gòu)

是對(duì)數(shù)據(jù)元素之間的邏輯關(guān)系的描述，它可以用一個(gè)數(shù)據(jù)元素的集合和定義在此集合上的若干關(guān)系來(lái)表示;物理結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示和實(shí)現(xiàn)，故又稱“存儲(chǔ)結(jié)構(gòu)”。15邏輯結(jié)構(gòu)的形式化描述為:Data_Structures=(D,S)其中:D是數(shù)據(jù)元素的有限集，

S是D上關(guān)系的有限集。16（一）邏輯結(jié)構(gòu)例如:定義“班集體”為一個(gè)數(shù)據(jù)結(jié)構(gòu)：Class=(D,S)D={a,b1,…,bn,c1,…cn,d1,…dn

}S={R1,R2}R1={<a,b1>,<a,c1>,<a,d1>}R2={<b1,bj>,<c1,cj>,<d1,dj>|j=2,3,…,n}班長(zhǎng)組長(zhǎng)17（二）存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）

定義：

存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)映象，是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)，它包括數(shù)據(jù)元素的表示(映像)和關(guān)系的表示(映像)。

數(shù)據(jù)元素的映象方法：用二進(jìn)制位(bit)的位串表示數(shù)據(jù)元素(321)10=(501)8=(101000001)2A=(101)8=(001000001)218關(guān)系的映象方法：（表示

x,y

的方法）順序映象以相對(duì)的存儲(chǔ)位置表示后繼關(guān)系令y的存儲(chǔ)位置和x的存儲(chǔ)位置之間差一個(gè)常量C，而C是一個(gè)隱含值，整個(gè)存儲(chǔ)結(jié)構(gòu)中只含數(shù)據(jù)元素本身的信息。xy鏈?zhǔn)接诚笠愿郊有畔?指針)表示后繼關(guān)系需要用一個(gè)和x在一起的附加信息指示y的存儲(chǔ)位置。yx19二、數(shù)據(jù)類型(DataType)

在編程時(shí),必須對(duì)程序中出現(xiàn)的每個(gè)變量、常量等說(shuō)明它們所屬的數(shù)據(jù)類型。不同類型的量，其所能取值的范圍是不同的，其所能進(jìn)行的操作也是不同的。數(shù)據(jù)類型:是一組性質(zhì)相同的值的集合以及定義在此集合上的一組操作的總稱。20例如在高級(jí)語(yǔ)言中：整型類型的取值范圍為：-32768~+32767；運(yùn)算符集合為：+、-、*、/、%。

事實(shí)上，與數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的是定義在數(shù)據(jù)結(jié)構(gòu)上的一組操作，即使數(shù)據(jù)的結(jié)構(gòu)相同，定義在其上的操作不同，數(shù)據(jù)類型則不同，其用途也大不相同。21三、數(shù)據(jù)抽象與抽象數(shù)據(jù)類型計(jì)算機(jī)語(yǔ)言中十進(jìn)制表示的數(shù)據(jù)98.65、9.6E3等,它們是二進(jìn)制數(shù)據(jù)的抽象;高級(jí)語(yǔ)言中，給出高一級(jí)的數(shù)據(jù)抽象，如整型、實(shí)型、字符型等;還可以進(jìn)一步定義更高級(jí)的數(shù)據(jù)抽象，如各種表、隊(duì)、棧、樹(shù)、圖、窗口、管理器等復(fù)雜的數(shù)據(jù)抽象。1.數(shù)據(jù)的抽象22各種高級(jí)程序設(shè)計(jì)語(yǔ)言中都擁有“整數(shù)”類型，盡管它們?cè)诓煌幚砥魃蠈?shí)現(xiàn)的方法不同，但對(duì)程序員而言是“相同的”，因?yàn)樗鼈兊臄?shù)學(xué)特性相同。從“數(shù)學(xué)抽象”的角度看，可稱它為一個(gè)“抽象數(shù)據(jù)類型”。23抽象數(shù)據(jù)類型(AbstractDataType

簡(jiǎn)稱ADT)

是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作例如:“整數(shù)”是一個(gè)抽象數(shù)據(jù)類型。其數(shù)學(xué)特性和具體的計(jì)算機(jī)或語(yǔ)言無(wú)關(guān)。

一個(gè)抽象數(shù)據(jù)類型確定了一個(gè)模型，但將模型的實(shí)現(xiàn)細(xì)節(jié)（存儲(chǔ)表示等）隱藏起來(lái)；它定義了一組操作，但將操作的實(shí)現(xiàn)過(guò)程（運(yùn)算處理等）隱藏起來(lái)。24數(shù)學(xué)模型抽象數(shù)據(jù)模型數(shù)據(jù)結(jié)構(gòu)非形式算法偽語(yǔ)言程序可執(zhí)行程序

用抽象數(shù)據(jù)類型的概念來(lái)指導(dǎo)問(wèn)題的求解過(guò)程為：1.選擇數(shù)學(xué)模型描述問(wèn)題，確定解決問(wèn)題的算法2.為模型定義抽象數(shù)據(jù)類型,并用偽語(yǔ)言描述算法3.確定抽象數(shù)據(jù)類型的實(shí)現(xiàn)方法,用程序?qū)崿F(xiàn)算法25ADT<ADT名>

{數(shù)據(jù)對(duì)象:<數(shù)據(jù)對(duì)象的定義>

結(jié)構(gòu)關(guān)系:<結(jié)構(gòu)關(guān)系的定義>

基本操作:<基本操作的定義>}ADT<ADT名>基本操作的定義：<操作名稱>(參數(shù)表)操作前提:<操作前提描述>操作結(jié)果:<操作結(jié)果描述>ADT的定義格式：26例如，抽象數(shù)據(jù)類型復(fù)數(shù)的定義：

數(shù)據(jù)對(duì)象：

D＝{(e1,e2)｜e1,e2∈RealSet}

數(shù)據(jù)關(guān)系：

R1＝{<e1,e2>|e1是復(fù)數(shù)的實(shí)數(shù)部分

|e2

是復(fù)數(shù)的虛數(shù)部分}ADTComplex{27基本操作：

AssignComplex(&Z,v1,v2)操作結(jié)果：構(gòu)造復(fù)數(shù)Z,其實(shí)部和虛部分別被賦以參數(shù)v1和v2的值。

DestroyComplex(&Z)操作結(jié)果：銷毀復(fù)數(shù)Z。

GetReal(Z,&realPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用realPart返回復(fù)數(shù)Z的實(shí)部值。

GetImag(Z,&ImagPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用ImagPart返回復(fù)數(shù)Z的虛部值。28

Add(z1,z2,&sum)初始條件：z1,z2是復(fù)數(shù)。操作結(jié)果：用sum返回兩個(gè)復(fù)數(shù)z1,z2的和值。}ADTComplex假設(shè):z1和z2是上述定義的復(fù)數(shù)則Add(z1,z2,&z3)操作的結(jié)果z3=z1+z2即為用戶要求的結(jié)果29用C語(yǔ)言實(shí)現(xiàn)ADT（1）用typedef定義所需的新類型結(jié)構(gòu)：

typedef可以用來(lái)創(chuàng)建新數(shù)據(jù)類型，也可以為新創(chuàng)建的數(shù)據(jù)類型命名，使用很方便，這在數(shù)據(jù)結(jié)構(gòu)的抽象描述方面很有用。（2）用子函數(shù)實(shí)現(xiàn)各個(gè)操作。要求：復(fù)習(xí)c語(yǔ)言，主要是數(shù)組、結(jié)構(gòu)體、函數(shù)和指針部分。301.3算法和算法的衡量一、算法二、算法設(shè)計(jì)的原則三、算法效率的衡量方法和準(zhǔn)則四、算法的存儲(chǔ)空間需求31

算法是為了解決某類問(wèn)題而規(guī)定的一個(gè)有限長(zhǎng)的操作序列。一個(gè)算法必須滿足以下五個(gè)重要特性：1．有窮性

2．確定性3．有輸入4．有輸出5．可行性一、算法32

算法的特性1.有窮性:算法應(yīng)在有限步驟之內(nèi)正常結(jié)束,且每步均能在有限時(shí)間內(nèi)完成。2.確定性:算法中的每一個(gè)步驟必須有確定含義，無(wú)二義性；

3.輸入:有多個(gè)或0個(gè)輸入；

4.輸出:至少有一個(gè)或多個(gè)輸出；5.可行性:算法中所有操作應(yīng)足夠基本，均可通過(guò)已實(shí)現(xiàn)的基本運(yùn)算經(jīng)過(guò)有限次執(zhí)行來(lái)完成。33

算法描述的語(yǔ)言選擇類語(yǔ)言：

類語(yǔ)言是接近于高級(jí)語(yǔ)言而又不是嚴(yán)格的高級(jí)語(yǔ)言，具有高級(jí)語(yǔ)言的一般語(yǔ)句結(jié)構(gòu)，忽略語(yǔ)言中的細(xì)節(jié)，以便把注意力主要集中在算法處理步驟本身的描述上。算法描述的常用工具

1.自然語(yǔ)言2.框圖3.類語(yǔ)言(偽語(yǔ)言)本課程使用類C語(yǔ)言34二、算法設(shè)計(jì)的原則算法的正確性算法原則：可讀性健壯性高效率和低存儲(chǔ)量例如要求n個(gè)數(shù)的最大值問(wèn)題給出算法如下：max=0;for（i=1；i<=n;i++）{scanf("%f",&x);if(x>max)max=x;}35

算法的正確性1.算法應(yīng)明確表述問(wèn)題的需求(嚴(yán)格描述)。2.對(duì)“正確”的理解可以有以下四個(gè)層次：a.程序中不含語(yǔ)法錯(cuò)誤；b.程序?qū)捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；c.程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)都能夠得出滿足要求的結(jié)果；通常以c層意義作為衡量一個(gè)算法是否合格的標(biāo)準(zhǔn)。d.對(duì)于一切合法輸入數(shù)據(jù)都能得出滿足要求的結(jié)果；36三、算法效率的度量

評(píng)價(jià)算法的標(biāo)準(zhǔn)：

評(píng)價(jià)一個(gè)算法主要看這個(gè)算法所占用機(jī)器資源的多少，而這些資源中時(shí)間代價(jià)與空間代價(jià)是兩個(gè)主要的方面，通常是以算法執(zhí)行所需的機(jī)器時(shí)間和所占用的存儲(chǔ)空間來(lái)判斷一個(gè)算法的優(yōu)劣。37對(duì)問(wèn)題規(guī)模n與該算法在運(yùn)行時(shí)所占的空間S與所耗費(fèi)的時(shí)間T給出一個(gè)數(shù)量關(guān)系的評(píng)價(jià)。問(wèn)題規(guī)模n—對(duì)不同的問(wèn)題其含義不同：

對(duì)矩陣是階數(shù)；

對(duì)多項(xiàng)式運(yùn)算是多項(xiàng)式項(xiàng)數(shù)；對(duì)圖是頂點(diǎn)個(gè)數(shù)；對(duì)集合運(yùn)算是集合中元素個(gè)數(shù)。38關(guān)于算法執(zhí)行時(shí)間語(yǔ)句頻度

算法的時(shí)間復(fù)雜度常用的時(shí)間復(fù)雜度頻率計(jì)數(shù)

最壞時(shí)間復(fù)雜度

算法的空間復(fù)雜度

391、關(guān)于算法執(zhí)行時(shí)間定義：一個(gè)算法的執(zhí)行時(shí)間大致上等于其所有語(yǔ)句執(zhí)行時(shí)間的總和，對(duì)于語(yǔ)句的執(zhí)行時(shí)間是指該條語(yǔ)句的執(zhí)行次數(shù)和執(zhí)行一次所需時(shí)間的乘積。分析：不是針對(duì)實(shí)際執(zhí)行時(shí)間的精確地算出算法執(zhí)行具體時(shí)間，而是針對(duì)算法中語(yǔ)句的執(zhí)行次數(shù)做出估計(jì)，從中得到算法執(zhí)行時(shí)間的信息。402、語(yǔ)句頻度定義：語(yǔ)句頻度是指該語(yǔ)句在一個(gè)算法中重復(fù)執(zhí)行的次數(shù)。例如：兩個(gè)矩陣相乘算法語(yǔ)句對(duì)應(yīng)的語(yǔ)句頻度

1for（i=0；i<n;i++）n2for（j=0；j<n;j++）n23{c[i][j]=0;n24for(k=0;k<n;k++)n3

c[i][j]=c[i][j]+a[i][k]*b[k][j];}n3

總執(zhí)行次數(shù)：Tn=2n3+2n2+n413、算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度，即算法的時(shí)間量度記做：

T(n)=O(f(n))例如計(jì)算X=X+1;（1）x=x+1；時(shí)間復(fù)雜度為O(1)，稱為常量階；（2）for(i=1;i<=n;i++)x=x+1;時(shí)間復(fù)雜度為O(n)，稱為線性階；（3）for(i=1;i<=n;i++) for(j=1;j<=n;j++)x=x+1;時(shí)間復(fù)雜度為O(n2),

稱為平方階。424、常用的時(shí)間復(fù)雜度頻率計(jì)數(shù)算法中常用的時(shí)間復(fù)雜度頻率計(jì)數(shù)有7種:O(1)常數(shù)型O(n)線性型O(n2)平方型O(n3)立方型O(2n)指數(shù)型O(log2n)對(duì)數(shù)型O(nlog2n)二維型常見(jiàn)函數(shù)的增長(zhǎng)率見(jiàn)下頁(yè)43程序運(yùn)行時(shí)間比較T（n）=O（f（n））T(n)n01000200030005101520252nn3100n5n2logn2100△n△

T(n)445、最壞時(shí)間復(fù)雜度定義：

算法在最壞情況下的時(shí)間復(fù)雜度，即為分析估計(jì)算法在最壞情況下執(zhí)行時(shí)間的上界。例如冒泡排序算法45voidbubble(inta[],intlength){/*將整數(shù)數(shù)組a重新排序，達(dá)到遞增有序*/

inti=0,j,temp，change;do{change=0;

for(j=1;j<length-i;j++) if(a[j]>a[j+1])

{temp=a[j];

a[j]=a[j+1];

a[j+1]=temp;

change=1;} i=i+1;}

while(i<length&&change==1)}466、算法的空間復(fù)雜度定義：

用空間復(fù)雜度作為算法所需存儲(chǔ)空間的量度，記做：

S(n)=O(f(n))47

編寫程序僅掌握程序語(yǔ)言是不夠的，還