《基本概念和術(shù)語》由會員分享,可在線閱讀,更多相關(guān)《基本概念和術(shù)語(29頁珍藏版)》請?jiān)谘b配圖網(wǎng)上搜索。
1、單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,第一章 緒論,1.1 什么是數(shù)據(jù)結(jié)構(gòu),1.2 基本概念和術(shù)語,1.4 算法和算法分析,1.3 抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn),1.2,基本概念和術(shù)語,一、數(shù)據(jù)、數(shù)據(jù)元素,三、數(shù)據(jù)類型,四、抽象數(shù)據(jù)類型,二、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù):,是對客觀事物的符號表示,在計(jì)算機(jī)科學(xué)中是指所有能,輸入,到計(jì)算機(jī)中且能被計(jì)算機(jī)程序,處理的符號(數(shù)值、字符等),的總稱。,例如,一個(gè)利用數(shù)值分析方法解代數(shù)方程的程序,其處理對象是整數(shù)和實(shí)數(shù);一個(gè)編譯程序或文字處理程序的處理對象是字符串。因此,對計(jì)算機(jī)科學(xué)而言,數(shù)據(jù)的含義極為廣泛,如圖
2、象、聲音等都可以通過編碼而歸之于數(shù)據(jù)的范疇。,一、數(shù)據(jù)、數(shù)據(jù)元素,數(shù)值性數(shù)據(jù),非數(shù)值性數(shù)據(jù),數(shù)據(jù)元素:,是數(shù)據(jù)的基本單位,在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮和處理。,例如,例12中的“樹”中的一個(gè)棋盤格局,例13中的“圖”中的一個(gè)圓圈都被稱為一個(gè)數(shù)據(jù)元素。有時(shí),,一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成,,例如,例11中一本書的書目信息中的每一項(xiàng)(如書名、作者名等)為一個(gè)數(shù)據(jù)項(xiàng),,數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。,如:整數(shù)“,5,”,字符“,N,”,等。,-是不可分割的“原子”,其中每個(gè)款項(xiàng)稱為一個(gè),“數(shù)據(jù)項(xiàng)”,它是數(shù)據(jù)結(jié)構(gòu)中討論的,最小,單位,數(shù)據(jù)元素也可以由若干款項(xiàng)構(gòu)成。,例如:,描述一個(gè)學(xué)生的
3、數(shù)據(jù)元素,稱之為組合項(xiàng),年 月 日,姓 名學(xué) 號班 號性別出生日期入學(xué)成績,原子項(xiàng),數(shù)據(jù)對象,是性質(zhì)相同的數(shù)據(jù)元素的集合,是數(shù)據(jù)的一個(gè)子集。,例如,,整數(shù)數(shù)據(jù)對象是集合,N=0,+/-1,+/-2,,字母字符數(shù)據(jù)對象是集合,C=A,B,Z。,數(shù)據(jù)結(jié)構(gòu),是相互之間存在的一種或多種特定的關(guān)系的數(shù)據(jù)元素的集合。,從上面中三個(gè)例子可以知道,在任何問題中,數(shù)據(jù)元素之間都不是孤立存在的,而是在它們之間存在著某種關(guān)系,這種數(shù)據(jù)元素相互之間關(guān)系稱為,結(jié)構(gòu),。,例如,當(dāng)用,三個(gè),4,位的十進(jìn)制數(shù),表示一個(gè)含,12,位數(shù)的十進(jìn)制數(shù)時(shí),,3214,6587,9345,a1,(3214),a2,(6587),a3,(
4、9345),則在數(shù)據(jù)元素,a1、a2,和,a3,之間存在著,“次序”關(guān)系,a1,a2,、,a2,a3,3214,6587,9345,6587,3214,9345,例如:,a1 a2 a3,a2 a1 a3,又例,在,2,行,3,列的二維數(shù)組,中六個(gè)元素,a1,a2,a3,a4,a5,a6,之間存在兩個(gè)關(guān)系:,行的次序關(guān)系,:,row=,col,=,a1 a2,a3,a4 a5 a6,列的次序關(guān)系,:,若在,6 個(gè)數(shù)據(jù)元素,a1,a2,a3,a4,a5,a6,之間存在如下的,次序關(guān)系,:,|i=1,2,3,4,5,數(shù)據(jù)結(jié)構(gòu),是,相互之間存在著某種邏輯關(guān)系的數(shù)據(jù)元素的集合,。,可見,不同的,“,關(guān)
5、系,”,構(gòu)成不同的,“,結(jié)構(gòu),”,則構(gòu)成,一維數(shù)組,的定義。,從,關(guān)系,或,結(jié)構(gòu),分,,數(shù)據(jù)結(jié)構(gòu),可歸結(jié)為以下,四類:,線性,結(jié)構(gòu),樹形,結(jié)構(gòu),圖狀,結(jié)構(gòu),集合,結(jié)構(gòu),集合:結(jié)構(gòu)中的數(shù)據(jù)元素之間除了“同屬于一個(gè)集合”的關(guān)系外,別無其他關(guān)系。,線性結(jié)構(gòu):結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個(gè)對一個(gè)的關(guān)系。,樹形結(jié)構(gòu):結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個(gè)對多個(gè)的關(guān)系。,圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu):結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多個(gè)對多個(gè)的關(guān)系。,6,)數(shù)據(jù)的物理結(jié)構(gòu)(又稱存儲結(jié)構(gòu)):是數(shù)據(jù)結(jié)構(gòu)在計(jì)算,機(jī)中的表示。它包括數(shù)據(jù)元素的表示和關(guān)系的表示。,數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中又有兩種不同的表示方法:,順序映像,特點(diǎn):借助元素在存
6、儲器中的相對位置來表示數(shù)據(jù),元素之間的邏輯關(guān)系。,非順序映像,特點(diǎn):借助指示元素存儲地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。,例如:假設(shè)用兩個(gè)字長的位串表示一個(gè)實(shí)數(shù),則可以用地址相鄰的,4,個(gè)字長的位串表示一個(gè)復(fù)數(shù),如圖,1.3(,a),為表示復(fù)數(shù),z13.02.3i,和,z20.7+4.8i,的順序存儲結(jié)構(gòu)。圖,1.3(,b),為表示復(fù)數(shù),z1,的鏈?zhǔn)酱鎯Y(jié)構(gòu),其中實(shí)部和虛部之間的關(guān)系用值為“,0415”,的指針來表示(,0415,是虛部的存儲地址)。,(,a),順序存儲結(jié)構(gòu),(,b),鏈?zhǔn)酱鎯Y(jié)構(gòu),圖1.3,復(fù)數(shù)存儲結(jié)構(gòu)示意圖,0300,0302,0632,0634,0415,0611,06
7、13,3.0,-2.3,-0.7,4.8,-2.3,3.0,0415,數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是密切相關(guān)的兩個(gè)方面。,在任何一個(gè)算法的設(shè)計(jì)取決于選定的數(shù)據(jù)(邏輯)結(jié)構(gòu),而算法的實(shí)現(xiàn)依賴于采用的存儲結(jié)構(gòu)。,7,)數(shù)據(jù)類型:是一個(gè)值的集合和定義在這個(gè)值集上的一組,操作的總稱。,按“值”的不同特性,在高級程序語言中可分為:,原子類型:其值不可分解。,例如,,C,語音中的基本類型(整型、實(shí)型、字符型,和枚舉類型)、指針類型和空類型。,結(jié)構(gòu)類型:其值是由若干成分按某種結(jié)構(gòu)組成的,故可分解,并且其,成分可以是非結(jié)構(gòu)的,也可以是結(jié)構(gòu)的。,例如,數(shù)組的值由若干分量組成,每個(gè)分量可以是整數(shù),也可以是數(shù),組等。,
8、8,)抽象數(shù)據(jù)類型(,ADT):,是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。,抽象數(shù)據(jù)類型的定義僅取決于它的一組邏輯特性,而與其在計(jì)算機(jī)內(nèi)部,如何表示和實(shí)現(xiàn)無關(guān),即不論其內(nèi)部結(jié)構(gòu)如何變化,只要它的數(shù)學(xué)特性,不變,都不影響其外部的使用。,其形式定義為:(一個(gè)三元組),(,D,S,P),其中,,D,是數(shù)據(jù)對象,,S,是,D,上的關(guān)系集,,P,是對,D,的基本操作集。,各種高級程序設(shè)計(jì)語言中都擁有“整數(shù)”類型,盡管它們在不同處理器上實(shí)現(xiàn)的方法不同,但對程序員而言是“相同的”,因?yàn)樗鼈兊臄?shù)學(xué)特性相同。,從“數(shù)學(xué)抽象”的角度看,可稱它為一個(gè)“抽象數(shù)據(jù)類型”。,按“值”的不同特性,可細(xì)分為:,原子類型
9、:屬原子類型的變量的值是不可分解的。,固定聚合類型:屬該類型的變量,其值由確定數(shù)目的,成分按某種結(jié)構(gòu)組成。,例如,復(fù)數(shù)是由兩個(gè)實(shí)數(shù)依確定的次序關(guān)系構(gòu)成。,可變聚合類型:和固定聚合類型相比較,構(gòu)成可變聚,合類型“值”的成分?jǐn)?shù)目不確定。,例如,可定義一個(gè)“有序整數(shù)序列”的抽象數(shù)據(jù)類型,其中序列的長度是可變的。,我們采用以下格式定義抽象數(shù)據(jù)類型:,ADT,抽象數(shù)據(jù)類型名,數(shù)據(jù)對象:,數(shù)據(jù)關(guān)系:,基本操作:,ADT,抽象數(shù)據(jù)類型名,其中,數(shù)據(jù)對象和數(shù)據(jù)關(guān)系的定義用偽碼描述,基本操作的定義格式為:,基本操作名(參數(shù)表),初始條件:,操作結(jié)果:,9,)多形數(shù)據(jù)類型:是指其值的成分不確定的數(shù)據(jù)類型。,例如,
10、,定義抽象數(shù)據(jù)類型,“,復(fù)數(shù),”,數(shù)據(jù)對象:,De1,e2e1,e2,RealSet,數(shù)據(jù)關(guān)系:,R1|e1,是復(fù)數(shù)的實(shí)數(shù)部分,|,e2,是復(fù)數(shù)的虛數(shù)部分,ADT Complex,基本操作:,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é)果
11、:用,ImagPart,返回復(fù)數(shù),Z,的虛部值。,Add(z1,z2,&sum),初始條件:,z1,z2,是復(fù)數(shù)。,操作結(jié)果:用,sum,返回兩個(gè)復(fù)數(shù),z1,z2,的,和值。,ADT Complex,void Assign(Complex*A,ItemType,real,ItemType,virtual),A-r=real;,A-v=virtual;,/*Assign()*/,void Add(Complex*A,Complex B),A-r+=B.r;,A-v+=B.v;,/*Add()*/,復(fù)數(shù)抽象數(shù)據(jù)類型的,C,語言實(shí)現(xiàn),#,include,#include,complex.h,void
12、 main,(),complex z1,z2,z3,z4,z;,float,RealPart,ImagPart,;,InitComplex,(z1,8.0,6.0);,InitComplex,(z2,4.0,3.0);,Add,(z1,z2,z3);,Multiply,(z1,z2,z4);,if(,Division,(z4,z3,z),GetReal,(z,RealPart,);,GetImag,(z,ImagPart,);,/if,ADT,有兩個(gè)重要特征:,數(shù)據(jù)抽象,用,ADT,描述程序處理的實(shí)體時(shí),強(qiáng)調(diào)的是其,本質(zhì)的特征,、,其所能完成的功能,以及它和,外部用戶的接口,(即,外界使用它的
13、方法,),數(shù)據(jù)封裝,將實(shí)體的,外部特性和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離,,并且,對外部用戶隱藏,其內(nèi)部實(shí)現(xiàn)細(xì)節(jié),抽象數(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)系的定義,基本操作:,基本操作的定義,ADT,抽象數(shù)據(jù)類型名,其中基本操作的定義格式為:,基本操作名,(參數(shù)表),初始條件:,初始條件描述,操作結(jié)果,:操作結(jié)果描述,賦值參數(shù),只為操作提供輸入值;,引用參數(shù),以,&,打頭,除可提供輸入值外,,還將返回操作結(jié)果。,初始條件,描述
14、了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件,若不滿足,則操作失敗,并返回相應(yīng)出錯(cuò)信息。,操作結(jié)果,說明了操作正常完成之后,數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若初始條件為空,則省略之。,例二 抽象數(shù)據(jù)類型三元組的定義:,ADT Triplet,數(shù)據(jù)對象:,D,e1,e2,e3e1,e2,e3,ElemSet,數(shù)據(jù)關(guān)系:,R1,基本操作:,InitTriplet,(,&T,v1,v2,v3),操作結(jié)果:構(gòu)造三元組,T,元素,e1,e2,和,e3,分別被賦以參數(shù),v1,v2,和,v3,的值。,DestroyTriplet,(,&T),操作結(jié)果:三元組,T,被銷毀。,Get(T,i,&e),初始條件:三
15、元組,T,已存在,1,i3。,操作結(jié)果:用,e,返回,T,的第,i,元的值。,Put(,&T,i,e),初始條件:三元組,T,已存在,1,i3。,操作結(jié)果:改變,T,的第,i,元的值為,e。,IsAscending,(T),初始條件:三元組,T,已存在。,操作結(jié)果:如果,T,的三個(gè)元素按升序排列,則返回1,否則返回0。,IsDescending,(T),初始條件:三元組,T,已存在。,操作結(jié)果:如果,T,的三個(gè)元素按降序排列,則返回1,否則返回0。,Max(T,&e),初始條件:三元組,T,已存在。,操作結(jié)果:用,e,返回,T,的三個(gè)元素中的最大值。,Min(T,&e),初始條件:三元組,T,已存在。,操作結(jié)果:用,e,返回,T,的三個(gè)元素中的最小值。,ADT Triplet,