1.4.2　抽象數(shù)據(jù)類型的描述

對(duì)于初學(xué)者來(lái)說(shuō)，抽象數(shù)據(jù)類型的概念及描述不太容易理解，這主要是由于很多讀者不清楚為什么要定義抽象數(shù)據(jù)類型，其作用類似于Python語(yǔ)言中的類，區(qū)別在于這里的數(shù)據(jù)類型是抽象的，不依賴具體語(yǔ)言實(shí)現(xiàn)，是更高層次的抽象描述，使用抽象數(shù)據(jù)類型描述的算法可通過(guò)任何語(yǔ)言實(shí)現(xiàn)。為方便讀者理解，本書(shū)盡量使用較為通俗的語(yǔ)言進(jìn)行描述，并通過(guò)具體的實(shí)例解釋。

抽象數(shù)據(jù)類型包括3個(gè)方面的內(nèi)容：數(shù)據(jù)對(duì)象、數(shù)據(jù)關(guān)系和基本運(yùn)算，通常采用三元組（D,SP）來(lái)表示，其中D表示數(shù)據(jù)對(duì)象，S是D上的關(guān)系集合，P是D中數(shù)據(jù)的基本運(yùn)算集合。其基本格式如下：

數(shù)據(jù)對(duì)象和數(shù)據(jù)關(guān)系的定義可采用數(shù)學(xué)符號(hào)和自然語(yǔ)言描述，基本操作的定義格式如下：

大多數(shù)教材用以下方式描述線性表的抽象數(shù)據(jù)類型。

有的教材把抽象數(shù)據(jù)類型分為兩個(gè)部分來(lái)描述，即數(shù)據(jù)對(duì)象集合和基本操作集合。其中，數(shù)據(jù)對(duì)象集合包括數(shù)據(jù)對(duì)象的定義及數(shù)據(jù)對(duì)象中元素之間關(guān)系的描述，基本操作集合是對(duì)數(shù)據(jù)對(duì)象的運(yùn)算的描述。

例如，線性表的抽象數(shù)據(jù)類型說(shuō)明如下。

1．?dāng)?shù)據(jù)對(duì)象集合

線性表的數(shù)據(jù)對(duì)象集合為{a₁,a₂,…,a_n}，每個(gè)元素的類型均為DataType。其中，除了第一個(gè)元素a₁外，每一個(gè)元素只有一個(gè)直接前驅(qū)元素，除了最后一個(gè)元素a_n外，每一個(gè)元素只有一個(gè)直接后繼元素。數(shù)據(jù)元素之間的關(guān)系是一對(duì)一的關(guān)系。

2．基本操作集合

線性表的基本操作如下所述。

（1）InitList(&L)：初始化操作，建立一個(gè)空的線性表L。這就像是在日常生活中，某院校為了方便管理建立一個(gè)教職工基本情況表，用于登記教職工信息。

（2）ListEmpty(L)：若線性表L為空，則返回1，否則返回0。這就像是剛剛建立了教職工基本情況表，還沒(méi)有登記教職工信息。

（3）GetElem(L,i,&e)：返回線性表L的第i個(gè)位置元素值給e。這就像在教職工基本情況表中，根據(jù)給定序號(hào)查找某個(gè)教師信息。

（4）LocateElem(L,e)：在線性表L中查找與給定值e相等的元素，如果查找成功，則返回該元素在表中的序號(hào)表示成功，否則返回0表示失敗。這就像在教職工基本情況表中，根據(jù)給出的姓名查找教師信息。

（5）InsertList(&L,i,e)：在線性表L中的第i個(gè)位置插入新元素e。這就類似于經(jīng)過(guò)招聘考試，引進(jìn)了一名教師，這個(gè)教師信息被登記到教職工基本情況表中。

（6）DeleteList(&L,i,&e)：刪除線性表L中的第i個(gè)位置元素，并用e返回其值。這就像某個(gè)教職工到了退休年齡或者被調(diào)入其他學(xué)校，需要將該教職工從教職工基本情況表中刪除。

（7）ListLength(L)：返回線性表L的元素個(gè)數(shù)。這就像查看教職工基本情況表中有多少個(gè)教職工。

（8）ClearList(&L)：將線性表L清空。這就像學(xué)校被撤銷，不需要再保留教職工基本信息，將這些教職工信息全部清空。

以上是抽象數(shù)據(jù)類型的兩種描述方式，本書(shū)沿用大多數(shù)教材的描述方式。

需要注意的是，在基本操作的描述過(guò)程中，參數(shù)傳遞有兩種方式：一種是數(shù)值傳遞，另一種是引用傳遞。前者僅僅是將數(shù)值傳遞給形參，并不返回結(jié)果；后者其實(shí)是把實(shí)參的地址傳遞給形參，實(shí)參和形參其實(shí)是同一個(gè)變量，被調(diào)用函數(shù)通過(guò)修改該變量的值返回給調(diào)用函數(shù)，從而把結(jié)果帶回。在描述算法時(shí)，在參數(shù)前加上&表示引用傳遞；如果參數(shù)前沒(méi)有&，表示是數(shù)值傳遞。