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