《基本概念和術(shù)語》由會(huì)員分享，可在線閱讀，更多相關(guān)《基本概念和術(shù)語（29頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),*,第一章 緒論,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ù)對(duì)象、數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù):,是對(duì)客觀事物的符號(hào)表示，在計(jì)算機(jī)科學(xué)中是指所有能,輸入,到計(jì)算機(jī)中且能被計(jì)算機(jī)程序,處理的符號(hào)(數(shù)值、字符等),的總稱。,例如，一個(gè)利用數(shù)值分析方法解代數(shù)方程的程序，其處理對(duì)象是整數(shù)和實(shí)數(shù)；一個(gè)編譯程序或文字處理程序的處理對(duì)象是字符串。因此，對(duì)計(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é) 號(hào)班 號(hào)性別出生日期入學(xué)成績(jī),原子項(xiàng),數(shù)據(jù)對(duì)象,是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。,例如，,整數(shù)數(shù)據(jù)對(duì)象是集合,N=0，+/-1，+/-2，,字母字符數(shù)據(jù)對(duì)象是集合,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è)對(duì)一個(gè)的關(guān)系。,樹形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個(gè)對(duì)多個(gè)的關(guān)系。,圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多個(gè)對(duì)多個(gè)的關(guān)系。,6,）數(shù)據(jù)的物理結(jié)構(gòu)（又稱存儲(chǔ)結(jié)構(gòu)）：是數(shù)據(jù)結(jié)構(gòu)在計(jì)算,機(jī)中的表示。它包括數(shù)據(jù)元素的表示和關(guān)系的表示。,數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中又有兩種不同的表示方法：,順序映像,特點(diǎn)：借助元素在存
6、儲(chǔ)器中的相對(duì)位置來表示數(shù)據(jù),元素之間的邏輯關(guān)系。,非順序映像,特點(diǎn)：借助指示元素存儲(chǔ)地址的指針表示數(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,的順序存儲(chǔ)結(jié)構(gòu)。圖,1.3（,b）,為表示復(fù)數(shù),z1,的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，其中實(shí)部和虛部之間的關(guān)系用值為“,0415”,的指針來表示（,0415,是虛部的存儲(chǔ)地址）。,(,a),順序存儲(chǔ)結(jié)構(gòu),(,b),鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),圖1.3,復(fù)數(shù)存儲(chǔ)結(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)依賴于采用的存儲(chǔ)結(jié)構(gòu)。,7,）數(shù)據(jù)類型：是一個(gè)值的集合和定義在這個(gè)值集上的一組,操作的總稱。,按“值”的不同特性，在高級(jí)程序語言中可分為：,原子類型：其值不可分解。,例如，,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ù)對(duì)象，,S,是,D,上的關(guān)系集，,P,是對(duì),D,的基本操作集。,各種高級(jí)程序設(shè)計(jì)語言中都擁有“整數(shù)”類型，盡管它們?cè)诓煌幚砥魃蠈?shí)現(xiàn)的方法不同，但對(duì)程序員而言是“相同的”，因?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ù)對(duì)象：,數(shù)據(jù)關(guān)系：,基本操作：,ADT,抽象數(shù)據(jù)類型名,其中，數(shù)據(jù)對(duì)象和數(shù)據(jù)關(guān)系的定義用偽碼描述，基本操作的定義格式為：,基本操作名（參數(shù)表）,初始條件：,操作結(jié)果：,9,）多形數(shù)據(jù)類型：是指其值的成分不確定的數(shù)據(jù)類型。,例如，
10、,定義抽象數(shù)據(jù)類型,“,復(fù)數(shù),”,數(shù)據(jù)對(duì)象：,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é)分離,，并且,對(duì)外部用戶隱藏,其內(nèi)部實(shí)現(xiàn)細(xì)節(jié),抽象數(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)系的定義,基本操作：,基本操作的定義,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ù)對(duì)象：,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,
基本概念和術(shù)語
