1.2基本概念和術語
- 1.2.1前言
- 1.2.2基本概念和術語
1.2.1前言
??參照課本廊宪，在本節(jié)中矾瘾，將介紹一些概念和術語并確定其含義，請注意區(qū)分和理解這些含義和所應用的層次(數學層面箭启、計算機層面等)壕翩，以方便實際應用。
tips:數學層次是通用層次傅寡，在計算機層面是普適的放妈。
1.2.2基本概念和術語
數學層次
(1)數據(data):
??對客觀事物的符號表示，
??在計算機科學中荐操，指所有能被輸入到計算機中芜抒，并能被程序處理的符號的總稱。
(2)數據元素(data element):
??數據元素是數據的基本單位托启，在計算機程序中常作為一個整體處理宅倒。
??類似于節(jié)點(node)，也可以理解成向量組中的一個向量屯耸。
(3)數據項(data item):
??有時唉堪，單個數據元素可以由若干個數據項組成，例如書目信息的一項包含書名肩民、作者名唠亚、書號等等信息。
??數據項是數據的不可分割的最小單位持痰。
??數據項可以理解為數據元素(類似于向量)在不同維度的分量灶搜，而其值就是分量的值。
(4)數據對象(data object):
??數據對象是性質相同的數據元素的集合工窍。
??數據對象可以理解為一個向量組割卖，包含著許多相干的向量(數據元素)。
(5)數據結構(data structure):
??數據結構是指：相互之間存在一種或多種特定關系的數據元素的集合患雏。
??數據結構根據結構中元素之間的關系的特性不同鹏溯，通常有下列4類基本結構：
(1)集合：由離散的節(jié)點構成的集合體，數據元素除了同屬于一個集合外淹仑，無其它的關系丙挽。
(2)線性：節(jié)點間存在線性連接，數據元素之間存在前驅或者后繼的一對一的關系匀借。
(3)樹形結構：節(jié)點呈現樹狀颜阐，數據元素間存在類似于父節(jié)點與子節(jié)點的一對多的關系。
(4)圖狀結構或網狀結構：節(jié)點呈現網狀吓肋，數據元素間存在多對多的輻射狀關系凳怨。
??數據結構的形式定義為：數據結構是一個二元組
??Data_Structure = ( D , S )
其中：D是數據元素的有限集，S是D上的關系的有限集。
下面是一個例子:
??在計算機科學中肤舞，復數可取如下定義：復數是一種數據結構
????????Complex = ( C , R )
其中紫新，C是兩個實數的集合｛c1,c2｝;R={P}，而P是定義在集合C上的一種關系{<c1,c2>}李剖，其中弊琴，序偶<c1,c2>表示c1是實數的實部,c2是實數的虛部。
(5)邏輯結構：
??結構定義中的“關系”描述的是數據元素之間的邏輯關系杖爽，因此又稱為邏輯結構敲董。
??數據的邏輯結構是對數據之間關系的描述，有時就把邏輯結構簡稱為數據結構慰安。
根據數據元素間邏輯關系的不同腋寨，可以將數據結構按邏輯分為兩類:
線性數據結構：線性表、棧化焕、隊列萄窜、數組、字符串
非線性數據結構：樹撒桨、二叉樹查刻、圖
計算機層次
(1)存儲結構:
??數據結構在計算機中的表示(又稱映像)稱為數據的物理結構,又稱存儲結構。
??在計算機中凤类，可以用一個由若干位(bit)組合形成的一個位串表示一個數據元素穗泵，這個位串稱為元素(element)或是節(jié)點(node)。當數據結構由若干數據項組成時谜疤，位串中對應各個數據項的子位串稱為數據域(data filed)佃延。因此，元素或節(jié)點可以看成數據元素在計算機中的映像夷磕。
數據元素之間的關系在計算機中有兩種不同的表示方法:順序映像和非順序映像履肃，并得到兩種不同的存儲結構：順式存儲結構和鏈式存儲結構。
(1.1)順式存儲結構:
??順式存儲結構借助元素在存儲器中的相對位置來表示數據元素間的邏輯關系坐桩。
??其特點是：數據元素的地址是連續(xù)的尺棋。
(1.2)鏈式存儲結構:
??鏈式存儲結構借助指針(pointer)來表示元素間的邏輯關系。
??其特點是：數據元素間的地址不一定連續(xù)绵跷，每一個節(jié)點的數據域占用一片連續(xù)的存儲空間膘螟。(如鏈表）
數據類型(data type)
??(1)數據類型是一個值的集合和定義在這個值上的一組操作的總稱。
區(qū)別于高級程序語言中的定義抖坪，這里不僅僅是值的類型萍鲸，也包含值上的操作。
??(2)抽象數據類型(abstract data type擦俐，簡稱ADT)
??抽象數據類型是指一個數學模型以及定義在該模型上的一組操作。
注:抽象數據類型的定義僅取決于它的一組邏輯特性握侧，而與其在計算機內部的如何表示和實現無關蚯瞧，即不論其內部結構如何變化嘿期，只要它的數學特性不變，都不影響其外部使用埋合。
高級程序設計語言中數據類型可分為兩類备徐，一類是非結構的原子類型，另一類是結構類型甚颂，其中原子類型的值是不可分解的蜜猾，而結構類型的值是由若干成分按某種結構組成的，因此是可分解的振诬。
而抽象數據類型按其值的特性可以分為以下三類:
(2.1)原子類型(atomic data type):
??屬于原子類型的變量的值是不可分解的蹭睡，一般來說已有的原子類型已經足夠，但有時也有必要定義新的原子數據類型赶么，如上百位的整數或是新類型的指針肩豁。
(2.2)固定聚合類型(fixed-aggregate data type)：
??屬于該類型的變量，其值由確定數目的成分按某種結構組成辫呻。例如清钥，復數是由兩個實數按次序分別作為實部和虛部的系數而構成。
(2.3)可變聚合類型(variable-aggregate data type):
??和固定聚合類型相比放闺，其組成結構的成分的數目不固定祟昭。例如，定義一個有序整數列的抽象類型怖侦，序列的長度是可變的从橘。
顯而易見，后兩種抽象數據類型屬于結構類型础钠。
抽象數據類型和數據類型實質上是一個概念恰力，例如整數或是數組也可看做抽象數據類型。
下面給出抽象數據類型的形式定義：
????ADT = ( D , S , P )
??其中旗吁，Ｄ是數據對象踩萎，S是Ｄ上的關系集，P是對D的基本操作集很钓。
現采取以下格式定義抽象數據類型
??ADT 抽象數據類型名{
????數據對象：<數據對象的定義>
????數據關系：<數據關系的定義>
????數據操作：<基本操作的定義>
??}ADT 抽象數據類型名
??其中香府，數據對象和數據關系的定義用偽代碼表示，基本操作的定義格式為
??基本操作名(參數表)
????初始條件：<初始條件描述>
????操作結果：<操作結果描述>
??基本操作有兩種參數码倦，賦值參數只為操作提供輸入值企孩，引入參數以&前綴，除可提供輸入值外袁稽，還將返回操作結果勿璃。若初始條件為空，則省略初始條件。
下面是一個例子:
ADT Triplet{
??數據對象：D = {e1,e2,e3|e1,e2,e3∈Elemset (定義了關系運算的某個集合)}
??數據關系：R = {<e1,e2>,<e2,e3>}
??基本操作：
????InitTriplet( &T , v1 , v2 , v3 )
??????操作結果：構建了三元組T补疑，元素e1,e2,e3分別被賦以參數 v1, v2, v3的值歧沪。
????DestroyTriplet( &T )
??????操作結果：三元組T被銷毀。
????Get( T , i , &e )
??????初始條件：三元組T已存在莲组，1<= i <= 3诊胞。
??????操作結果：用 e 返回 T 的第 i 元的值。
????Put( &T , i , e )
??????初始條件：三元組T已存在锹杈，1<= i <= 3撵孤。
??????操作結果：改變T的第 i 元的值為 e。
????IsAscending( T )
??????初始條件：三元組T已存在竭望。
??????操作結果：如果T的3個元素按升序排列邪码，則返回1，否則返回0市框。
????IsDescending( T )
??????初始條件：三元組T已存在霞扬。
??????操作結果：如果T的3個元素按降序排列，則返回1枫振，否則返回0喻圃。
????Max( T , &e )
??????初始條件：三元組T已存在。
??????操作結果：用e返回T中三個元素的最大值粪滤。
????Min( T , &e )
??????初始條件：三元組T已存在斧拍。
??????操作結果：用e返回T中三個元素的最小值。
}ADT Triplet
(3)多形數據類型(polymorphic data type)是指其值的成分不確定的數據類型杖小。例如例子中的e1,e2,e3,可以是整數肆汹、字符、字符串予权，甚至是更復雜的結構類型昂勉，只需要能進行關系運算即可。然而扫腺，不論其元素具有何種特性岗照，元素之間的關系相同，基本操作也相同笆环。
