《基本概念和術語》由會員分享，可在線閱讀，更多相關《基本概念和術語（29頁珍藏版）》請在裝配圖網上搜索。

1、單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,第一章 緒論,1.1 什么是數(shù)據(jù)結構,1.2 基本概念和術語,1.4 算法和算法分析,1.3 抽象數(shù)據(jù)類型的表示與實現(xiàn),1.2,基本概念和術語,一、數(shù)據(jù)、數(shù)據(jù)元素,三、數(shù)據(jù)類型,四、抽象數(shù)據(jù)類型,二、數(shù)據(jù)對象、數(shù)據(jù)結構,數(shù)據(jù):,是對客觀事物的符號表示，在計算機科學中是指所有能,輸入,到計算機中且能被計算機程序,處理的符號(數(shù)值、字符等),的總稱。,例如，一個利用數(shù)值分析方法解代數(shù)方程的程序，其處理對象是整數(shù)和實數(shù)；一個編譯程序或文字處理程序的處理對象是字符串。因此，對計算機科學而言，數(shù)據(jù)的含義極為廣泛，如圖

2、象、聲音等都可以通過編碼而歸之于數(shù)據(jù)的范疇。,一、數(shù)據(jù)、數(shù)據(jù)元素,數(shù)值性數(shù)據(jù),非數(shù)值性數(shù)據(jù),數(shù)據(jù)元素:,是數(shù)據(jù)的基本單位，在計算機中通常作為一個整體進行考慮和處理。,例如，例12中的“樹”中的一個棋盤格局，例13中的“圖”中的一個圓圈都被稱為一個數(shù)據(jù)元素。有時，,一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成,，例如，例11中一本書的書目信息中的每一項（如書名、作者名等）為一個數(shù)據(jù)項，,數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。,如:整數(shù)“,5,”,字符“,N,”,等。,-是不可分割的“原子”,其中每個款項稱為一個,“數(shù)據(jù)項”,它是數(shù)據(jù)結構中討論的,最小,單位,數(shù)據(jù)元素也可以由若干款項構成。,例如：,描述一個學生的

3、數(shù)據(jù)元素,稱之為組合項,年 月 日,姓 名學 號班 號性別出生日期入學成績,原子項,數(shù)據(jù)對象,是性質相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。,例如，,整數(shù)數(shù)據(jù)對象是集合,N=0，+/-1，+/-2，,字母字符數(shù)據(jù)對象是集合,C=A，B，Z。,數(shù)據(jù)結構,是相互之間存在的一種或多種特定的關系的數(shù)據(jù)元素的集合。,從上面中三個例子可以知道，在任何問題中，數(shù)據(jù)元素之間都不是孤立存在的，而是在它們之間存在著某種關系，這種數(shù)據(jù)元素相互之間關系稱為,結構,。,例如，當用,三個,4,位的十進制數(shù),表示一個含,12,位數(shù)的十進制數(shù)時，,3214,6587,9345,a1,(3214),a2,(6587),a3,(

4、9345),則在數(shù)據(jù)元素,a1、a2,和,a3,之間存在著,“次序”關系,a1,a2,、,a2,a3,3214，6587，9345,6587，3214，9345,例如:,a1 a2 a3,a2 a1 a3,又例，在,2,行,3,列的二維數(shù)組,中六個元素,a1,a2,a3,a4,a5,a6,之間存在兩個關系:,行的次序關系,:,row=,col,=,a1 a2,a3,a4 a5 a6,列的次序關系,:,若在,6 個數(shù)據(jù)元素,a1,a2,a3,a4,a5,a6,之間存在如下的,次序關系,:,|i=1,2,3,4,5,數(shù)據(jù)結構,是,相互之間存在著某種邏輯關系的數(shù)據(jù)元素的集合,。,可見，不同的,“,關

5、系,”,構成不同的,“,結構,”,則構成,一維數(shù)組,的定義。,從,關系,或,結構,分,，數(shù)據(jù)結構,可歸結為以下,四類:,線性,結構,樹形,結構,圖狀,結構,集合,結構,集合：結構中的數(shù)據(jù)元素之間除了“同屬于一個集合”的關系外，別無其他關系。,線性結構：結構中的數(shù)據(jù)元素之間存在一個對一個的關系。,樹形結構：結構中的數(shù)據(jù)元素之間存在一個對多個的關系。,圖狀結構或網狀結構：結構中的數(shù)據(jù)元素之間存在多個對多個的關系。,6,）數(shù)據(jù)的物理結構（又稱存儲結構）：是數(shù)據(jù)結構在計算,機中的表示。它包括數(shù)據(jù)元素的表示和關系的表示。,數(shù)據(jù)元素之間的關系在計算機中又有兩種不同的表示方法：,順序映像,特點：借助元素在存

6、儲器中的相對位置來表示數(shù)據(jù),元素之間的邏輯關系。,非順序映像,特點：借助指示元素存儲地址的指針表示數(shù)據(jù)元素之間的邏輯關系。,例如：假設用兩個字長的位串表示一個實數(shù)，則可以用地址相鄰的,4,個字長的位串表示一個復數(shù)，如圖,1.3（,a）,為表示復數(shù),z13.02.3i,和,z20.7+4.8i,的順序存儲結構。圖,1.3（,b）,為表示復數(shù),z1,的鏈式存儲結構，其中實部和虛部之間的關系用值為“,0415”,的指針來表示（,0415,是虛部的存儲地址）。,(,a),順序存儲結構,(,b),鏈式存儲結構,圖1.3,復數(shù)存儲結構示意圖,0300,0302,0632,0634,0415,0611,06

7、13,3.0,-2.3,-0.7,4.8,-2.3,3.0,0415,數(shù)據(jù)的邏輯結構和物理結構是密切相關的兩個方面。,在任何一個算法的設計取決于選定的數(shù)據(jù)（邏輯）結構，而算法的實現(xiàn)依賴于采用的存儲結構。,7,）數(shù)據(jù)類型：是一個值的集合和定義在這個值集上的一組,操作的總稱。,按“值”的不同特性，在高級程序語言中可分為：,原子類型：其值不可分解。,例如，,C,語音中的基本類型（整型、實型、字符型,和枚舉類型）、指針類型和空類型。,結構類型：其值是由若干成分按某種結構組成的，故可分解，并且其,成分可以是非結構的，也可以是結構的。,例如，數(shù)組的值由若干分量組成，每個分量可以是整數(shù)，也可以是數(shù),組等。,

8、8,）抽象數(shù)據(jù)類型（,ADT）：,是指一個數(shù)學模型以及定義在該模型上的一組操作。,抽象數(shù)據(jù)類型的定義僅取決于它的一組邏輯特性，而與其在計算機內部,如何表示和實現(xiàn)無關，即不論其內部結構如何變化，只要它的數(shù)學特性,不變，都不影響其外部的使用。,其形式定義為：（一個三元組）,（,D,S,P）,其中，,D,是數(shù)據(jù)對象，,S,是,D,上的關系集，,P,是對,D,的基本操作集。,各種高級程序設計語言中都擁有“整數(shù)”類型，盡管它們在不同處理器上實現(xiàn)的方法不同，但對程序員而言是“相同的”，因為它們的數(shù)學特性相同。,從“數(shù)學抽象”的角度看，可稱它為一個“抽象數(shù)據(jù)類型”。,按“值”的不同特性，可細分為：,原子類型

9、：屬原子類型的變量的值是不可分解的。,固定聚合類型：屬該類型的變量，其值由確定數(shù)目的,成分按某種結構組成。,例如，復數(shù)是由兩個實數(shù)依確定的次序關系構成。,可變聚合類型：和固定聚合類型相比較，構成可變聚,合類型“值”的成分數(shù)目不確定。,例如，可定義一個“有序整數(shù)序列”的抽象數(shù)據(jù)類型，其中序列的長度是可變的。,我們采用以下格式定義抽象數(shù)據(jù)類型：,ADT,抽象數(shù)據(jù)類型名,數(shù)據(jù)對象：,數(shù)據(jù)關系：,基本操作：,ADT,抽象數(shù)據(jù)類型名,其中，數(shù)據(jù)對象和數(shù)據(jù)關系的定義用偽碼描述，基本操作的定義格式為：,基本操作名（參數(shù)表）,初始條件：,操作結果：,9,）多形數(shù)據(jù)類型：是指其值的成分不確定的數(shù)據(jù)類型。,例如，

10、,定義抽象數(shù)據(jù)類型,“,復數(shù),”,數(shù)據(jù)對象：,De1,e2e1,e2,RealSet,數(shù)據(jù)關系：,R1|e1,是復數(shù)的實數(shù)部分,|,e2,是復數(shù)的虛數(shù)部分,ADT Complex,基本操作：,AssignComplex,(&Z,v1,v2),操作結果：構造復數(shù),Z,其實部和虛部,分別被賦以參數(shù),v1,和,v2,的值。,DestroyComplex,(&Z),操作結果：復數(shù),Z,被銷毀。,GetReal,(Z,&,realPart,),初始條件：復數(shù)已存在。,操作結果：用,realPart,返回復數(shù),Z,的實部值。,GetImag,(Z,&,ImagPart,),初始條件：復數(shù)已存在。,操作結果

11、：用,ImagPart,返回復數(shù),Z,的虛部值。,Add(z1,z2,&sum),初始條件：,z1,z2,是復數(shù)。,操作結果：用,sum,返回兩個復數(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()*/,復數(shù)抽象數(shù)據(jù)類型的,C,語言實現(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,有兩個重要特征:,數(shù)據(jù)抽象,用,ADT,描述程序處理的實體時，強調的是其,本質的特征,、,其所能完成的功能,以及它和,外部用戶的接口,（即,外界使用它的

13、方法,）,數(shù)據(jù)封裝,將實體的,外部特性和其內部實現(xiàn)細節(jié)分離,，并且,對外部用戶隱藏,其內部實現(xiàn)細節(jié),抽象數(shù)據(jù)類型的描述方法,抽象數(shù)據(jù)類型可用,（,D，S，P）,三元組表示,其中，,D,是數(shù)據(jù)對象，,S,是,D,上的關系集，,P,是對,D,的基本操作集。,ADT,抽象數(shù)據(jù)類型名,數(shù)據(jù)對象：,數(shù)據(jù)對象的定義,數(shù)據(jù)關系：,數(shù)據(jù)關系的定義,基本操作：,基本操作的定義,ADT,抽象數(shù)據(jù)類型名,其中基本操作的定義格式為:,基本操作名,（參數(shù)表）,初始條件：,初始條件描述,操作結果,：操作結果描述,賦值參數(shù),只為操作提供輸入值；,引用參數(shù),以,&,打頭，除可提供輸入值外，,還將返回操作結果。,初始條件,描述

14、了操作執(zhí)行之前數(shù)據(jù)結構和參數(shù)應滿足的條件，若不滿足，則操作失敗，并返回相應出錯信息。,操作結果,說明了操作正常完成之后，數(shù)據(jù)結構的變化狀況和應返回的結果。若初始條件為空，則省略之。,例二 抽象數(shù)據(jù)類型三元組的定義：,ADT Triplet,數(shù)據(jù)對象：,D,e1,e2,e3e1,e2,e3,ElemSet,數(shù)據(jù)關系：,R1,基本操作：,InitTriplet,(,&T,v1,v2,v3),操作結果：構造三元組,T,元素,e1,e2,和,e3,分別被賦以參數(shù),v1,v2,和,v3,的值。,DestroyTriplet,(,&T),操作結果：三元組,T,被銷毀。,Get(T,i,&e),初始條件：三

15、元組,T,已存在，1,i3。,操作結果：用,e,返回,T,的第,i,元的值。,Put(,&T,i,e),初始條件：三元組,T,已存在，1,i3。,操作結果：改變,T,的第,i,元的值為,e。,IsAscending,(T),初始條件：三元組,T,已存在。,操作結果：如果,T,的三個元素按升序排列，則返回1，否則返回0。,IsDescending,(T),初始條件：三元組,T,已存在。,操作結果：如果,T,的三個元素按降序排列，則返回1，否則返回0。,Max(T,&e),初始條件：三元組,T,已存在。,操作結果：用,e,返回,T,的三個元素中的最大值。,Min(T,&e),初始條件：三元組,T,已存在。,操作結果：用,e,返回,T,的三個元素中的最小值。,ADT Triplet,