1.2.3　數據結構的表示

1.數據的邏輯結構

對數據間關系的描述即對數據邏輯結構的描述，形式上可以用一個二元組來表示，即

B = （D，R）

其中，D為結點的有窮集合，即D是由有限個結點所構成的集合；R是體現結點間關系的有窮集合，即R是由有限關系所構成的集合，其中的每個關系都是從D集合中一個結點到另一個結點的關系。

結點的類型是指結點的值的組成方式，即數據的類型。設D是結點的有窮集合，且每個結點d（d∈D）的值可由n個字段組成，第i個字段記為Wid，則d可以表示為

d=（W1d，W2d，W3d，…，Wnd），n≥1

其中，每個Wid是一個組合項，它可由一個或多個初等項或組合項組成，也可為一個初等項。

結點可以分為兩大類型，即初等類型和組合類型。只包含一個初等項的結點屬于初等類型。初等類型有5種基本的數據類型，即整型、實型、布爾型、字符型及指針型。按指針的地址操作類型可分為絕對地址指針或相對地址指針。組合類型是由初等類型以某種方式組合而成的，如枚舉類型和結構類型等。

數據結構和結點之間具有整體與局部概念上的關聯。數據結構由若干結點及其相互關系所組成。一般把結點看作一個整體，重點討論結點之間的關系。當研究結點的內部結構時，有時可以把一個結點看作一個數據結構，而把組成該結點的數據項看成數據結構中的結點，但這時各結點可以是相同類型的，也可以是不同類型的。

2.數據的存儲結構

數據的存儲結構與數據的物理存儲方式是密切相關的。實際上，計算機的存儲器具有有限個存儲單元，每個單元用唯一的地址作為操作標識，各存儲單元的地址是人為連續編碼的。數據的邏輯結構向存儲結構的轉換是通過建立一個從結點到地址單元的映像來實現的，存儲結構要在物理層次上映射出數據結點間的關系。

有4種基本的物理存儲映像方法：順序方法、鏈接方法、索引方法和散列方法。一種具有特定邏輯結構的數據結構可以根據需要采用多種物理存儲映像方法來表達。

1）順序方法

使用順序方法存儲數據，所有數據元素存放在一片連續的存儲單元中，邏輯上相鄰的元素存放在計算機內仍然相鄰。順序方法主要用于線性數據結構。把邏輯上相鄰的結點存儲在物理上相鄰的存儲單元內，結點之間的關系由存儲單元的連接關系來體現。每個結點所占的存儲單元可以相同，也可以不同。但無論所占單元相同或不同，總體上都是一個個地填滿整個存儲區域。

2）鏈接方法

使用鏈接方法存儲數據，所有元素可以存放在不連續的存儲單元中，但元素之間的關系可以通過地址確定，邏輯上相鄰的元素存放到計算機內存后不一定是相鄰的。鏈接方法最大的特點就是每個數據結點都附有指針字段，即結點所占的存儲單元分為兩部分：存放結點本身的信息和存入后繼結點的存儲單元的一個或多個地址。通常鏈接的最后一個結點的指針可以通過置0而終結。

3）索引方法

使用索引方法存儲數據，還需建立一個附加的索引表。索引表中的每一項稱為索引項，索引項的一般形式為

（關鍵字，地址）

其中，關鍵字是能唯一標識一個結點的數據項。

在線性結構里，結點可以排成序列d1，d2，…，dn，每個di在序列里都有對應的位置i，這個位置為結點的索引。用結點的索引號i來確定結點的存儲地址有兩種方法：

（1）建立附加的索引表，索引表中第i項的值就是第i個結點的存儲地址。

（2）每個結點所占單元數相等時，可用結點位置值指出結點的存儲地址，即第i個結點di的地址為

LOCATION（di）=（i-1）?p+q

其中，p為結點所占單元數，q為d1的存儲地址。

4）散列方法

使用散列方法存儲數據，通過構造散列函數，用函數的值來確定元素存放的地址，根據結點的值來確定它的存儲地址。散列方法又稱關鍵碼-地址轉移法。在結點中取一個或幾個字段的值Wid做關鍵碼，結點d的存儲地址為

LOCATION（d）=f（Wid）

其中， f為散列函數。

散列方法關鍵的問題是要恰當地選擇散列函數以解決存儲地址沖突的問題。

一個數據結構的存儲映像都是以上4種基本映像之一或者它們的組合。一個邏輯結構可以有不同的存儲映像方法。邏輯結構相同但存儲結構不同視為不同的數據結構。例如，線性表為一邏輯結構，順序存儲時為順序表，鏈接存儲時稱為線性鏈表。具體選擇什么存儲方式，取決于算法和計算機資源等約束條件。

目前，數據結構的描述有兩類方法：一類是邏輯描述法，即采用數學或圖形描述的方法，這類方法主要用于數據邏輯結構的描述；另一類是采用具有面向對象特性的算法語言來描述，采用諸如Eiffel、C++等算法語言既能描述數據的邏輯結構，又能描述數據結構的具體實現過程。