1.1 數(shù)據(jù)結(jié)構(gòu)概述

1.1.1 什么是數(shù)據(jù)結(jié)構(gòu)

計算機數(shù)據(jù)運算的一般過程如圖1.1所示。數(shù)據(jù)是信息的載體，能夠被計算機識別、存儲和加工處理，數(shù)據(jù)包括文字、表格、圖像等。例如，某個班的全部學(xué)生記錄、a～z的字母集合、1～1000的所有素數(shù)等都是數(shù)據(jù)。信息是數(shù)據(jù)的內(nèi)涵，即數(shù)據(jù)所表達的意義，例如，通過統(tǒng)計后產(chǎn)生某課程的平均分85，這里85是數(shù)據(jù)，表示某課程平均分的信息。

數(shù)據(jù)的基本單位是數(shù)據(jù)元素（有時稱為元素、結(jié)點或記錄等），通常把數(shù)據(jù)元素作為一個整體進行處理。例如，一個班的學(xué)生數(shù)據(jù)包括張三、李四等數(shù)據(jù)元素。

數(shù)據(jù)對象是具有相同類型的數(shù)據(jù)元素的集合，因為所有數(shù)據(jù)元素類型相同時處理起來更加方便，所以在數(shù)據(jù)結(jié)構(gòu)中除特別指定外數(shù)據(jù)通常都是數(shù)據(jù)對象。

有時一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項（也可稱為字段、域、屬性）組成。數(shù)據(jù)項是具有獨立意義的不可分割的最小標識單位。例如，在1～100的整數(shù)數(shù)據(jù)中，10就是一個數(shù)據(jù)元素；又比如在一個學(xué)生表中，一個學(xué)生記錄可稱為一個數(shù)據(jù)元素，而這個元素中的某一字段（如姓名）就是一個數(shù)據(jù)項。

【例1.1】組成數(shù)據(jù)的基本單位是________。

A．數(shù)據(jù)項

B．數(shù)據(jù)類型

C．數(shù)據(jù)元素

D．數(shù)據(jù)變量

解：數(shù)據(jù)是由數(shù)據(jù)元素組成的，數(shù)據(jù)元素是數(shù)據(jù)的基本單位。本題答案為C。

數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，如圖1.2所示。這些數(shù)據(jù)元素不是孤立存在的，而是有著某種關(guān)系，這種關(guān)系構(gòu)成了某種結(jié)構(gòu)。在現(xiàn)實中，數(shù)據(jù)元素之間的關(guān)系多種多樣，在“數(shù)據(jù)結(jié)構(gòu)”課程中主要討論數(shù)據(jù)元素之間的相鄰關(guān)系。

歸納起來，數(shù)據(jù)結(jié)構(gòu)一般包括以下三個方面的內(nèi)容。

（1）數(shù)據(jù)元素之間的邏輯關(guān)系。所有元素的邏輯關(guān)系構(gòu)成了數(shù)據(jù)邏輯結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲無關(guān)，是獨立于計算機的。因此，數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)學(xué)模型。

（2）數(shù)據(jù)元素（有時簡稱為元素）及其邏輯關(guān)系在計算機存儲器內(nèi)的表示，構(gòu)成了數(shù)據(jù)存儲結(jié)構(gòu)。數(shù)據(jù)存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)用計算機語言實現(xiàn)的（也稱為映像），它是依賴于計算機語言的。一般只在高級語言的層次上討論存儲結(jié)構(gòu)。

（3）數(shù)據(jù)運算，即對數(shù)據(jù)施加的操作。數(shù)據(jù)運算的定義（指定運算的功能描述）是基于邏輯結(jié)構(gòu)的，每種邏輯結(jié)構(gòu)都有一組相應(yīng)的運算。例如，最常用的運算有檢索、插入、刪除、更新、排序等；而數(shù)據(jù)運算的實現(xiàn)是基于存儲結(jié)構(gòu)的，通常是采用某種計算機語言實現(xiàn)的。

例如，一個學(xué)生成績表Score如表1.1所示，它由多個學(xué)生成績記錄（即數(shù)據(jù)元素）組成，每個元素又包括多個數(shù)據(jù)項，其中，學(xué)號數(shù)據(jù)項是關(guān)鍵字，即學(xué)號唯一標識一個學(xué)生記錄，現(xiàn)要求計算所有學(xué)生的平均分。

在這個求解問題中，表1.1給出了數(shù)據(jù)的邏輯結(jié)構(gòu)，其數(shù)據(jù)運算是求所有學(xué)生的平均分。為了實現(xiàn)這個功能，先要設(shè)計對應(yīng)的存儲結(jié)構(gòu)，即把Score表存放到計算機內(nèi)存中，然后設(shè)計出實現(xiàn)求平均分的算法。

這里包含的學(xué)生成績表邏輯結(jié)構(gòu)，對應(yīng)的存儲結(jié)構(gòu)設(shè)計和求平均分運算的實現(xiàn)都是數(shù)據(jù)結(jié)構(gòu)所涉及的內(nèi)容。

1.1.2 邏輯結(jié)構(gòu)

數(shù)據(jù)元素之間的邏輯關(guān)系的整體稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。現(xiàn)實中，數(shù)據(jù)元素的邏輯關(guān)系千變?nèi)f化，而數(shù)據(jù)結(jié)構(gòu)課程中討論的邏輯關(guān)系主要是指數(shù)據(jù)元素之間的相鄰關(guān)系，如果兩個數(shù)據(jù)元素是相鄰的，說明它們之間是有關(guān)系的，否則它們之間沒有關(guān)系。實際上，這種相鄰關(guān)系處理方法很容易推廣到其他復(fù)雜關(guān)系的處理。

根據(jù)數(shù)據(jù)元素之間邏輯關(guān)系的不同特性，分為下列4類基本結(jié)構(gòu)。

（1）集合：包含的所有數(shù)據(jù)元素同屬于一個集合（數(shù)據(jù)元素之間沒有關(guān)系，集合是一種最松散的邏輯結(jié)構(gòu)）。

（2）線性結(jié)構(gòu)：包含的數(shù)據(jù)元素之間存在一對一的關(guān)系。（3）樹狀結(jié)構(gòu)：包含的數(shù)據(jù)元素之間存在一對多的關(guān)系。

（4）圖形結(jié)構(gòu)：包含的數(shù)據(jù)元素之間存在多對多的關(guān)系。也稱為網(wǎng)狀結(jié)構(gòu)。

數(shù)據(jù)的邏輯結(jié)構(gòu)可以采用多種方式描述，二元組是一種既常用也十分通用的數(shù)據(jù)邏輯結(jié)構(gòu)表示方式。二元組表示如下。

      S=(D,R)
      D={di|1≤i≤n}
      R={rj|1≤j≤m}

其中，D是數(shù)據(jù)元素的有限集合，即D是由有限個數(shù)據(jù)元素所構(gòu)成的集合，R是D上的關(guān)系的有限集合，即R是由有限個關(guān)系rj（1≤j≤m）所構(gòu)成的集合，而每個關(guān)系都是指D→D的關(guān)系。

每個關(guān)系rj用序偶集合來表示，一個序偶表示兩個元素之間的相鄰關(guān)系，用尖括號表示有向關(guān)系，如<a，b>表示存在元素a到b之間的關(guān)系；用圓括號表示無向關(guān)系，如（a，b）表示既存在元素a到b之間的關(guān)系，又存在元素b到a之間的關(guān)系。

設(shè)rj是一個D到D的關(guān)系，rj∈R，若元素d∈D，d′∈D，且<d，d′>∈rj，則稱d′是d的直接后繼元素（簡稱后繼元素），d是d′的直接前驅(qū)元素（簡稱前驅(qū)元素），這時d和d′是相鄰的元素（都是相對rj而言的）；如果不存在一個d′使<d，d′>∈rj，則稱d為rj的終端元素；如果不存在一個d′使<d′，d>∈rj，則稱d為rj的開始元素；如果d既不是終端元素也不是開始元素，則稱d是內(nèi)部元素。

例如，表1.1數(shù)據(jù)的邏輯結(jié)構(gòu)是怎么樣的呢？從該表中可以看出，學(xué)號為201201的元素為開始元素（沒有前驅(qū)元素），學(xué)號為201204的元素為終端元素（沒有后繼元素）。除此之外，所有元素都只有一個前驅(qū)元素和一個后繼元素，如學(xué)號為201205的學(xué)生記錄的唯一前驅(qū)元素為學(xué)號為201201的學(xué)生記錄，唯一后繼元素為學(xué)號為201206的學(xué)生記錄。由此可知，這個表的邏輯結(jié)構(gòu)為線性結(jié)構(gòu)。

實際上，Score表本身就完整地描述了該數(shù)據(jù)的邏輯結(jié)構(gòu)，也可以用如下二元組表示其邏輯結(jié)構(gòu)（用學(xué)號表示相應(yīng)的元素）。

      Score=(D,R)
      D={201201,201202,201204,201205,201206}
      R={r}        //這里只有一個邏輯關(guān)系，一些復(fù)雜的數(shù)據(jù)結(jié)構(gòu)中可以有多個邏輯關(guān)系
      r={<201201,201205>,<201205,201206>,<201206,201202>,<201202,201204>}

數(shù)據(jù)邏輯結(jié)構(gòu)的呈現(xiàn)形式稱為數(shù)據(jù)的邏輯表示，除二元組外，數(shù)據(jù)邏輯結(jié)構(gòu)還可以用相應(yīng)的關(guān)系圖來表示，稱為邏輯結(jié)構(gòu)圖。

【例1.2】設(shè)數(shù)據(jù)的邏輯結(jié)構(gòu)如下：

      B1=(D,R)
      D={1,2,3,4,5,6,7,8,9}
      R={r}
      r={<1,2>,<1,3>,<3,4>,<3,5>,<4,6>,<4,7>,<5,8>,<7,9>}

試畫出對應(yīng)的邏輯結(jié)構(gòu)圖，并指出哪些是開始結(jié)點，哪些是終端結(jié)點，說明是何種數(shù)據(jù)結(jié)構(gòu)。

解：B1對應(yīng)的邏輯結(jié)構(gòu)圖如圖1.3所示。其中，1是開始結(jié)點，2、6、8、9是終端結(jié)點，除開始結(jié)點外，每個結(jié)點有唯一的前驅(qū)結(jié)點，除終端結(jié)點外，每個結(jié)點有一個或多個后繼結(jié)點，所以它是一種樹狀結(jié)構(gòu)。

【例1.3】設(shè)數(shù)據(jù)的邏輯結(jié)構(gòu)如下：

      B2=(D,R)
      D={1,2,3,4,5,6}
      R={r}
      r={<1,2>,<2,4>,<1,3>,<3,4>,<3,5>,<3,6>,<5,6>}

試畫出對應(yīng)的邏輯結(jié)構(gòu)圖，說明是何種數(shù)據(jù)結(jié)構(gòu)。

解：B2對應(yīng)的邏輯結(jié)構(gòu)圖如圖1.4所示，其中每個結(jié)點都有零個或多個前驅(qū)結(jié)點，每個結(jié)點都有零個或多個后繼結(jié)點，所以它是一種圖形結(jié)構(gòu)。

1.1.3 存儲結(jié)構(gòu)

數(shù)據(jù)邏輯結(jié)構(gòu)在計算機存儲器中的表示稱為數(shù)據(jù)的存儲結(jié)構(gòu)（或存儲表示），也稱為物理結(jié)構(gòu)。通常情況下，同一種邏輯結(jié)構(gòu)可以設(shè)計多種存儲結(jié)構(gòu)，在不同的存儲結(jié)構(gòu)中，實現(xiàn)同一種運算的算法可能不同。

邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和運算三者之間的關(guān)系如圖1.5所示。

把數(shù)據(jù)對象存儲到計算機中時，通常要求既要存儲各數(shù)據(jù)元素，又要存儲數(shù)據(jù)元素之間的邏輯關(guān)系。在實際應(yīng)用中，數(shù)據(jù)的存儲方法是靈活多樣的，可根據(jù)問題規(guī)模（通常是指元素個數(shù)的多少）和運算種類等因素適當選擇。下面簡要介紹主要的幾種存儲結(jié)構(gòu)。

1．順序存儲結(jié)構(gòu)

順序存儲結(jié)構(gòu)是采用一組連續(xù)的存儲單元存放所有的數(shù)據(jù)元素，而且邏輯上相鄰的元素的存儲單元也相鄰。也就是說，元素之間的邏輯關(guān)系由存儲單元地址間的關(guān)系隱含表示，即順序存儲結(jié)構(gòu)將數(shù)據(jù)的邏輯結(jié)構(gòu)直接映射到存儲結(jié)構(gòu)。

對于前面的邏輯結(jié)構(gòu)Score，假設(shè)每個元素占用30B，且從100號單元開始由低地址向高地址方向存儲，對應(yīng)的順序存儲結(jié)構(gòu)如圖1.6所示。

順序存儲結(jié)構(gòu)的主要優(yōu)點是節(jié)省存儲空間。因為分配給數(shù)據(jù)的存儲單元全用于存放元素值，元素之間邏輯關(guān)系的表示沒有占用額外的存儲空間。用這種方法來存儲線性結(jié)構(gòu)的數(shù)據(jù)元素時，可實現(xiàn)對各數(shù)據(jù)元素的隨機存取（所謂隨機存取是指給定某元素的邏輯序號，能在常量時間內(nèi)查找到對應(yīng)的元素值）。

這是因為線性結(jié)構(gòu)中每個數(shù)據(jù)元素對應(yīng)一個序號（開始元素的序號為1，它的后繼元素的序號為2……），序號為i的元素ai，其存儲地址如下：

LOC（ai）=p+（i—1）×k

其中，k是每個元素所占的單元數(shù)，p是第一個元素所占單元的首地址。

順序存儲結(jié)構(gòu)的主要缺點是不便于修改，在對元素進行插入、刪除運算時，可能要移動一系列的元素。

2．鏈式存儲結(jié)構(gòu)

順序存儲結(jié)構(gòu)要求所有的元素在內(nèi)存中相鄰存放，因而需占用一片連續(xù)的存儲空間；而鏈式存儲結(jié)構(gòu)不是這樣，每個結(jié)點單獨存儲，無須占用一整塊存儲空間，但為了表示結(jié)點之間的關(guān)系，給每個結(jié)點附加指針字段，用于存放相鄰結(jié)點的存儲地址。

對于前面的邏輯結(jié)構(gòu)Score，在設(shè)計其鏈式存儲結(jié)構(gòu)時，每個結(jié)點存放一個學(xué)生成績記錄，每個結(jié)點附加一個“下一個結(jié)點地址”即后繼指針域，用于存放后繼結(jié)點的首地址，則可得到如圖1.7所示的Score的鏈式存儲表示，head作為第一個結(jié)點的地址來標識整個鏈式存儲結(jié)構(gòu)。從圖中可以看出，每個結(jié)點由兩部分組成，一部分用于存放結(jié)點的數(shù)據(jù)，另一部分用于存放后繼結(jié)點的首地址。

為了更清楚地反映鏈式存儲結(jié)構(gòu)，可采用更直觀的圖示來表示，如Score的鏈式存儲結(jié)構(gòu)可用如圖1.8所示的方式表示。如要查找某學(xué)號的結(jié)點，需從head所指結(jié)點開始比較，在沒有找到時依次沿后繼指針域繼續(xù)找下去。

鏈式存儲結(jié)構(gòu)的主要優(yōu)點是便于修改，在進行插入、刪除運算時，僅需修改結(jié)點的指針域，不必移動結(jié)點。

與順序存儲結(jié)構(gòu)相比，鏈式存儲結(jié)構(gòu)的主要缺點是存儲空間的利用率較低，因為分配給數(shù)據(jù)元素的存儲單元中有一部分被用來存放結(jié)點之間的邏輯關(guān)系了。另外，由于邏輯上相鄰的結(jié)點在存儲器中不一定相鄰，因此，在用這種方法存儲的線性結(jié)構(gòu)中不能對結(jié)點進行隨機存取。

3．索引存儲結(jié)構(gòu)

索引存儲結(jié)構(gòu)是在存儲數(shù)據(jù)（稱為主數(shù)據(jù)表）的同時，還建立附加的索引表。索引表中的每一項稱為索引項，索引項的一般形式如下：

      （關(guān)鍵字，對應(yīng)地址）

在索引表中，所有關(guān)鍵字有序排列（如遞增），每個關(guān)鍵字的對應(yīng)地址為該關(guān)鍵字的記錄在數(shù)據(jù)表中的存儲地址。

如圖1.9所示的是Score對應(yīng)的一種索引存儲結(jié)構(gòu)。在進行關(guān)鍵字（如學(xué)號）查找時，先在索引表中快速查找（因為索引表中按關(guān)鍵字有序排列，可以采用二分查找）到相應(yīng)的關(guān)鍵字，然后通過對應(yīng)地址在數(shù)據(jù)表中找到該記錄的數(shù)據(jù)。

索引存儲結(jié)構(gòu)的優(yōu)點是查找效率高，其缺點是需要建立索引表，從而增加了時間和空間開銷。

4．哈希（散列）存儲結(jié)構(gòu)

哈希存儲結(jié)構(gòu)根據(jù)元素的關(guān)鍵字來確定其存儲地址。具體做法是：以元素的關(guān)鍵字為自變量，通過某個哈希函數(shù)H（key）（或散列函數(shù)）計算出對應(yīng)的函數(shù)值，再把該函數(shù)值當作該元素的存儲地址。

對于前面的邏輯結(jié)構(gòu)Score，假設(shè)哈希表長度m=6（存儲單元的地址為0～5），記錄個數(shù)n=5，以學(xué)號作為自變量，選用哈希函數(shù)如下：

h（學(xué)號）=學(xué)號—201201

對于每個學(xué)生記錄，計算的存儲地址如下。

于是得到如圖1.10所示的哈希存儲結(jié)構(gòu)（其中2地址單元空閑）。如果要查找學(xué)號為id的學(xué)生記錄，只需要求出h（id），以它為地址在該哈希表中直接找到該學(xué)號的學(xué)生記錄。

哈希存儲結(jié)構(gòu)的優(yōu)點是查找速度快，只要給出待查找結(jié)點的關(guān)鍵字，就有可能立即計算出對應(yīng)記錄的存儲地址。

與前三種存儲方法不同的是，哈希存儲方法只存儲數(shù)據(jù)元素本身，不存儲數(shù)據(jù)元素之間的邏輯關(guān)系。哈希存儲結(jié)構(gòu)一般只用于要求對數(shù)據(jù)能夠進行快速查找、插入的場合。采用哈希存儲的關(guān)鍵是要選擇一個好的哈希函數(shù)和處理“沖突”的辦法。

1.1.4 數(shù)據(jù)運算

數(shù)據(jù)運算就是施加于數(shù)據(jù)的操作。數(shù)據(jù)運算包括運算定義和運算實現(xiàn)兩部分，前者描述運算的功能，是抽象的，后者是在存儲結(jié)構(gòu)上設(shè)計對應(yīng)運算的實現(xiàn)算法，是具體的。這種將運算定義和運算實現(xiàn)相互分離的做法即軟件工程的思想，更加便于軟件開發(fā)。

在數(shù)據(jù)結(jié)構(gòu)中，運算實現(xiàn)與數(shù)據(jù)存儲結(jié)構(gòu)密切相關(guān)，選用好的存儲結(jié)構(gòu)可以提高運算實現(xiàn)的效率。

1.1.5 數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型和抽象數(shù)據(jù)類型

1．數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)是指帶結(jié)構(gòu)的數(shù)據(jù)元素的集合。一個數(shù)據(jù)結(jié)構(gòu)包含數(shù)據(jù)邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)運算三個方面。

2．數(shù)據(jù)類型

數(shù)據(jù)類型是高級程序設(shè)計語言中的一個基本概念，它和數(shù)據(jù)結(jié)構(gòu)的概念密切相關(guān)。一方面，在程序設(shè)計語言中，每一個數(shù)據(jù)都屬于某種數(shù)據(jù)類型。數(shù)據(jù)類型顯式或隱含地規(guī)定了數(shù)據(jù)的取值范圍、存儲方式以及允許進行的運算。例如，在32位系統(tǒng)中，C語言的short int（短整型）數(shù)據(jù)類型隱含取值范圍為—32 768～32 767，其運算有+、—、?、/、%等。因此可以認為，數(shù)據(jù)類型是在程序設(shè)計語言中已經(jīng)實現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)。另一方面，在程序設(shè)計過程中，當需要引入某種新的數(shù)據(jù)結(jié)構(gòu)時，必須借助編程語言所提供的數(shù)據(jù)類型來描述數(shù)據(jù)的存儲結(jié)構(gòu)。

下面總結(jié)C/C++語言中常用的數(shù)據(jù)類型。

1）C/C++語言的基本數(shù)據(jù)類型

C/C++語言中的基本數(shù)據(jù)類型有int型、float型；double型和char型。int型可以有三個修飾符：short（短整數(shù)）、long（長整數(shù)）和unsigned（無符號整數(shù)）。

數(shù)據(jù)類型用于定義變量，如有定義語句：int n=10；在執(zhí)行該語句時系統(tǒng)自動為變量n分配一個固定長度（如4B）的內(nèi)存空間，如圖1.11所示，程序員通過變量名n對這個內(nèi)存空間進行存取操作（內(nèi)存分成許多單元，每個單元都有一個地址，可以通過地址來對指定的單元進行操作，但這樣做對于程序員來說十分麻煩，而通過變量名來操作內(nèi)存單元非常方便），當超出作用范圍時系統(tǒng)自動釋放其內(nèi)存空間，所以稱之為自動變量。

2）C/C++語言的指針類型

C/C++語言允許直接對存放變量的地址進行操作。例如有以下定義：

      int i, ? p;

其中，i是整型變量，p是指針變量（它用于存放某個整型變量的地址）。表達式&i表示變量i的地址，將p指向整型變量i的運算為：p=&i。

對于指針變量p，表達式?p是取p所指變量的值，例如：

      int i=2, ? p=&i;
      printf(＂%d\n＂,? p);

上述語句執(zhí)行后，其內(nèi)存結(jié)構(gòu)如圖1.12所示，通過表達式?p輸出變量i的值即2。

可以使用malloc（）函數(shù)為一個指針變量分配一片連續(xù)的空間（稱為動態(tài)空間分配）。例如：

上述代碼先定義字符指針變量p（此時它沒有指向有效的字符數(shù)據(jù)，即p中的地址值沒有意義），使用malloc（）函數(shù)為其分配長度為10個字符的空間，將該空間的首地址賦給p（盡管程序員不知道這個地址是多少，但p的值已經(jīng)有意義了），再將字符串＂China＂放到這個空間中，如圖1.13所示。p指向的是首字符'C'，所以第一個printf語句輸出的?p即字符'C'，而第二個printf語句輸出的是整個字符串即＂China＂。

p變量是自動變量，當超出范圍時，系統(tǒng)會自動釋放它的空間，但p所指向的空間（用malloc函數(shù)分配的空間）是不能被系統(tǒng)自動釋放的，所以必須顯式用free（p）語句來釋放p所指向的空間，這稱為銷毀，即垃圾回收。如果不做銷毀操作，p所指向的內(nèi)存空間在程序執(zhí)行完畢仍被占用，這樣可能很快造成內(nèi)存消耗完，稱為內(nèi)存泄漏。所以本書后幾章中介紹的每種數(shù)據(jù)結(jié)構(gòu)都包含創(chuàng)建和銷毀基本運算。

3）C/C++語言的數(shù)組類型

數(shù)組是同一數(shù)據(jù)類型的一組數(shù)據(jù)的有限序列。數(shù)組分為一維數(shù)組和多維數(shù)組。數(shù)組名標識一個數(shù)組，下標指示一個數(shù)組元素在該數(shù)組中的位置。

數(shù)組下標的最小值稱為下界，在C語言中總是為0。數(shù)組下標的最大值稱為上界，在C語言中數(shù)組上界為數(shù)組長度減1。例如，inta[10]語句定義了包含10個整數(shù)的數(shù)組a，其數(shù)組元素是a[0]～a[9]。

4）C/C++語言中的結(jié)構(gòu)體類型

結(jié)構(gòu)體是由一組稱為結(jié)構(gòu)體成員的數(shù)據(jù)項組成的，每個結(jié)構(gòu)體成員都有自己的標識符，也稱為數(shù)據(jù)成員域。例如，以下聲明了一個teacher結(jié)構(gòu)體類型：

結(jié)構(gòu)體類型是用于定義結(jié)構(gòu)體變量的，當定義一個結(jié)構(gòu)體類型的變量時，系統(tǒng)按照結(jié)構(gòu)體類型聲明為對應(yīng)的變量分配存儲空間。例如，定義一個結(jié)構(gòu)體變量t：

      struct teacher t;

t變量在內(nèi)存中的存放方式如圖1.14所示，引用no成員的方式是t.no，引用name成員的方式是t. name，引用age成員的方式是t.age，所有成員相鄰存放，t變量所分配的內(nèi)存空間大小為所有成員占用的內(nèi)存空間之和。

可以使用結(jié)構(gòu)體類型teacher定義其他變量，有以下代碼：

其執(zhí)行結(jié)果如下。

      1，陳華，34
      5，王強，48

5）C/C++語言中的共用體類型

共用體用于把不同的數(shù)據(jù)成員組織為一個整體，它們在內(nèi)存中共享一段存儲單元，但不同成員以不同的方式被解釋。例如，聲明一個共用體類型tag如下：

共用體類型是用于定義共用體變量的，當定義一個共用體類型的變量時，系統(tǒng)按照共用體類型聲明為對應(yīng)的變量分配存儲空間。例如，定義一個共用體變量u：

      union tag u;

u變量在內(nèi)存中的存放方式如圖1.15所示，引用n成員的方式是u.n，引用ch成員的ch[0]元素的方式是u.ch[0]，所有成員共享相同的內(nèi)存空間，u變量所分配的內(nèi)存空間大小為所有成員占用的成員空間的最大值。

可以使用共用體類型tag定義其他變量，有以下代碼：

通過賦值后，在共用體變量u的成員n的兩個字節(jié)中，高位為65（0x41），低位為66 （0x42），分別對應(yīng)u.ch[1]和u.ch[0]成員，所以printf輸出為A和B兩個字符（字符'A'的ASCII為十六進制數(shù)41，字符'B'的ASCII為十六進制數(shù)42）。

6）C語言中的自定義類型

C/C++語言中允許使用typedef關(guān)鍵字為一個數(shù)據(jù)類型指定一個別名，例如：

      typedef char ElemType;

該語句將char類型與ElemType等同起來。這樣做有兩個好處，一是方便程序調(diào)試，例如，將上述語句改為typedef int ElemType，則程序中所有ElemType都改為int類型了；二是可以簡化代碼，例如：

這樣，StudType等同于學(xué)生結(jié)構(gòu)體類型，可以使用該類型名定義變量：

      StudType s1,s2;

等同于：

      struct student s1,s2;

3．抽象數(shù)據(jù)類型

在數(shù)據(jù)結(jié)構(gòu)中，抽象數(shù)據(jù)類型（Abstract Data Type，ADT）是指一個數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)類型（高級編程語言中已實現(xiàn)的數(shù)據(jù)類型）來實現(xiàn)。對一個抽象數(shù)據(jù)類型進行定義時，必須給出抽象數(shù)據(jù)類型名稱和包含的運算名稱及其功能描述。一旦定義了一個抽象數(shù)據(jù)類型并具體實現(xiàn)，程序設(shè)計中就可以像使用基本數(shù)據(jù)類型那樣，十分方便地使用該抽象數(shù)據(jù)類型。

從數(shù)據(jù)結(jié)構(gòu)的角度看，一個求解問題可以通過抽象數(shù)據(jù)類型來描述，也就是說，抽象數(shù)據(jù)類型對一個求解問題從邏輯上進行了準確的定義，所以抽象數(shù)據(jù)類型由數(shù)據(jù)邏輯結(jié)構(gòu)和運算定義兩部分組成。從中看出，抽象數(shù)據(jù)類型是面向用戶的，而抽象數(shù)據(jù)類型的實現(xiàn)是面向程序員的。

【例1.4】定義單個集合的抽象數(shù)據(jù)類型ASet，其中所有元素為正整數(shù)，包含創(chuàng)建一個集合、輸出一個集合和判斷一個元素是否為集合中元素的基本運算。

在此基礎(chǔ)上再定義兩個集合運算的抽象數(shù)據(jù)類型BSet，包含集合的并集、差集和交集運算。

解：抽象數(shù)據(jù)類型ASet的定義如下：

抽象數(shù)據(jù)類型BSet的定義如下：

通過上述兩個抽象數(shù)據(jù)類型的定義，就將求解問題描述清楚了，下一步就是用C/C++等語言具體實現(xiàn)其功能。