用面向?qū)ο罄砟钤O(shè)計線性表的構(gòu)架

韓海 董蘊源

（江漢大學(xué)人工智能學(xué)院 湖北省武漢市 430056）

在掌握了一門計算機(jī)語言的語法規(guī)則和基本技巧之后，學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法是學(xué)生提升系統(tǒng)觀念和工程能力的關(guān)鍵。學(xué)習(xí)過程中，多數(shù)人比較注重插入、刪除、查找等功能函數(shù)的編寫，不能從總體上把握該章節(jié)中各個概念之間的關(guān)系[4,5]，因此，梳理各概念之間的關(guān)系是非常必要的。

1 線性表各概念間的關(guān)系

較有影響力的教材都按照線性表的基本概念、順序表、鏈表、棧、隊列的次序安排教學(xué)內(nèi)容[1‐3]，先講述線性表的定義和相關(guān)概念，說明線性表的結(jié)構(gòu)特點和應(yīng)具備的基本功能，包括創(chuàng)建、銷毀、判空、提取元素、插入元素、刪除元素、查找等等。從規(guī)范化的角度考慮，通常都為線性表定義相應(yīng)的抽象數(shù)據(jù)類型，描述數(shù)據(jù)元素之間的邏輯關(guān)系，并規(guī)定各個功能的函數(shù)名稱。這是線性表的邏輯結(jié)構(gòu)。然后，分別說明如何按兩種常用情況組織數(shù)據(jù)，在每一種數(shù)據(jù)組織方式之下如何實現(xiàn)前述功能。如圖1所示，線性表、順序表、鏈表之間的關(guān)系是清晰明確的：用順序結(jié)構(gòu)組織數(shù)據(jù)而實現(xiàn)的線性表稱為順序表，用鏈?zhǔn)浇Y(jié)構(gòu)組織數(shù)據(jù)而實現(xiàn)的線性表稱為鏈表。

但是，在后續(xù)章節(jié)講述棧和隊列時就遇到困難。各種教材把棧和隊列都定義為操作受限的線性表。因此，棧和隊列應(yīng)該添加到圖1 當(dāng)中。但是，把這些概念都簡單地添加到圖1 當(dāng)中作為由線性表直接派生出的形態(tài)顯然是不合適的，棧、隊列是邏輯結(jié)構(gòu)，而順序表、鏈表強(qiáng)調(diào)物理存儲，兩者并列會在概念上造成混亂。順序表、鏈表、棧和隊列都是線性表的具體表現(xiàn)，它們之間的關(guān)系如何，目前，還沒有任何教材或者文獻(xiàn)全面整理了線性表各個形態(tài)之間的關(guān)系。

圖1：順序表、鏈表與線性表的關(guān)系

各類教材中講解各種形態(tài)的線性表時，除了順序表、鏈表、棧和隊列之外，還包括環(huán)形鏈表。通常都把環(huán)形鏈表劃歸鏈表的一種形態(tài)，這更是讓學(xué)生難于理解：為什么要做成環(huán)形？做成環(huán)形之后還有表首、表尾嗎[6,7]？

2 面向?qū)ο罄砟钤诰€性表中的體現(xiàn)

面向?qū)ο蟪绦蛟O(shè)計以對象作為基本元素，核心理念包括抽象、封裝、繼承和多態(tài)。抽象是提取事物的屬性和行為特征，封裝是把屬性和行為組織在一起，并規(guī)定訪問權(quán)限，實施這種封裝的程序元素是類和實例。繼承是通過在已有的類的基礎(chǔ)上添加屬性、添加行為或者修改已有行為的表現(xiàn)方式而產(chǎn)生新的事物。描述原事物的類稱為基類，描述新事物的類稱為派生類。多態(tài)是指同一種行為在事物中可以有不同的表現(xiàn)形式，在同一個類當(dāng)中有不同的表現(xiàn)稱為函數(shù)重載或者方法重載，在基類與派生類之間的不同表現(xiàn)稱為函數(shù)覆蓋或者方法重寫。

圖1 是一種典型的繼承派生關(guān)系。線性表是基類，規(guī)定了這種結(jié)構(gòu)應(yīng)具備創(chuàng)建、插入、刪除等功能，順序表是以數(shù)組存儲數(shù)據(jù)元素的派生類，鏈表則是以鏈?zhǔn)浇Y(jié)構(gòu)存儲數(shù)據(jù)元素的派生類。經(jīng)典教材都用抽象數(shù)據(jù)類型規(guī)定了線性表的插入、刪除操作可以在任何合理的位置進(jìn)行，順序表、鏈表都必須為此編寫相應(yīng)的代碼。但是，在用繼承派生關(guān)系來處理棧和隊列時會遇到困難，棧和隊列是不允許在任意位置插入、刪除元素的，也就是說，棧和隊列關(guān)于插入和刪除操作與線性表有不同的規(guī)定，棧和隊列在線性表的基礎(chǔ)上減少了功能，那么，棧和隊列還是線性表嗎？目前，各類教材、文獻(xiàn)中都明確指出棧和隊列是特殊的線性表，卻沒有解釋如何在面向?qū)ο蟮木幊谭绞较缕帘蔚艟€性表規(guī)定的那些功能。

3 用面向?qū)ο罄砟顚€性表進(jìn)行頂層設(shè)計

為了解決這些問題，可以重新整理線性表的各形態(tài)，明確它們之間的關(guān)系。線性結(jié)構(gòu)的最根本特征是數(shù)據(jù)對象之間有一對一的相鄰關(guān)系，具有這種關(guān)系的數(shù)據(jù)對象形成線性結(jié)構(gòu)。相鄰關(guān)系分為左相鄰關(guān)系和右相鄰關(guān)系。對于線性結(jié)構(gòu)中的任意數(shù)據(jù)對象z，最多只有唯一數(shù)據(jù)對象x 與其左相鄰，也最多只有唯一數(shù)據(jù)對象y 與其右相鄰。如果x 是z 的左相鄰數(shù)據(jù)對象（簡稱左鄰），則z 是x 的右相鄰數(shù)據(jù)對象（簡稱右鄰）。左相鄰關(guān)系和右相鄰關(guān)系都是一對一關(guān)系。

在線性結(jié)構(gòu)的基礎(chǔ)上添加一些限制可以產(chǎn)生不同的形態(tài)，除了表、棧和隊列之外，環(huán)也是一種常用形態(tài)。每一種形態(tài)是一種邏輯結(jié)構(gòu)，它們具有若干共同的特征。

每一種邏輯結(jié)構(gòu)又分別可以采用順序存儲方式或者鏈?zhǔn)酱鎯Ψ绞剑话惆秧樞虼鎯?shù)據(jù)對象的表稱為順序表，鏈?zhǔn)酱鎯?shù)據(jù)對象的表稱為鏈表。相應(yīng)地有順序棧、鏈?zhǔn)綏！㈨樞蜿犃泻玩準(zhǔn)疥犃械雀拍睢Ｗ鳛榫€性結(jié)構(gòu)的第四種形態(tài)，可以把順序存儲數(shù)據(jù)對象的環(huán)稱為順序環(huán)，鏈?zhǔn)酱鎯Φ沫h(huán)稱為鏈?zhǔn)江h(huán)。上述所有概念的關(guān)系構(gòu)成非常明晰的層次關(guān)系，如圖2所示。

圖2：線性結(jié)構(gòu)各種形態(tài)之間的關(guān)系

記數(shù)據(jù)對象的類型為ElemType，可以為線性結(jié)構(gòu)定義抽象數(shù)據(jù)類型如下：

表是規(guī)定了方向和兩個端點的線性結(jié)構(gòu)。在具備線性結(jié)構(gòu)規(guī)定的各項運算的基礎(chǔ)上，表新增的運算包括求表長、取指定位置的元素、查找是否存在滿足條件的元素、刪除元素、排序等，插入和刪除操作可以在任何合理的位置上進(jìn)行。棧、隊列和環(huán)均是在具備線性結(jié)構(gòu)規(guī)定的各項運算的基礎(chǔ)上新增若干運算。

很明顯，抽象數(shù)據(jù)類型Linear 缺少了兩種重要的運算：刪除和查找。這是基于兩方面的考慮：一是由創(chuàng)建和插入兩種運算就可以搭建出一個線性結(jié)構(gòu)，這兩種運算是最根本的運算；二是線性結(jié)構(gòu)的不同形態(tài)在刪除、查找方面的要求并不一致，作為更高一層的抽象無法描述，只能在表、棧、隊列、環(huán)等形態(tài)中分別規(guī)定自己的刪除、查找運算及相應(yīng)的參數(shù)形式。

圖2 描述的各種線性結(jié)構(gòu)及相互關(guān)系與面向?qū)ο罄砟钪械睦^承是直接對應(yīng)的。針對最頂層的線性結(jié)構(gòu)可以編寫一個抽象類，這是其它所有類的基類。第二層的各個概念分別是在線性結(jié)構(gòu)之上添加了若干功能，并且只規(guī)定功能和相應(yīng)參數(shù)而不規(guī)定如何實現(xiàn)，它們是線性結(jié)構(gòu)的派生類，仍然是抽象類。第三層確定了數(shù)據(jù)的存儲方式，編寫的類不再是抽象類，需要為抽象類中規(guī)定的各項功能編寫函數(shù)代碼。

例如，位于第二層的環(huán)仍然是一個抽象類，對應(yīng)的抽象數(shù)據(jù)類型可以描述為：

通常，環(huán)是有方向的，在實際設(shè)計時做出相應(yīng)的規(guī)定。比如，對于旋轉(zhuǎn)運算Rotate(n)，可以規(guī)定在n>0 時把插入、刪除操作位置往右鄰方向移動，n<0 則向左鄰移動。添加新元素有多種做法，涉及把新元素添加為當(dāng)前位置的左鄰還是右鄰，以及當(dāng)前操作位置是否移動。可以在上述抽象數(shù)據(jù)類型中以說明的形式加以規(guī)定，也可以把這些細(xì)節(jié)留給派生類。

在確定了用數(shù)組或者鏈表作為數(shù)據(jù)對象的存儲方式之后，對圖2 當(dāng)中第三層的順序環(huán)或者鏈?zhǔn)江h(huán)可以編寫相應(yīng)的類，并在這種存儲方式之下實現(xiàn)創(chuàng)建、消除、插入、刪除、查找、旋轉(zhuǎn)等功能。

在線性結(jié)構(gòu)中添加環(huán)這種形態(tài)之后，就可以順理成章地解釋為什么需要有環(huán)形鏈表、雙向環(huán)形鏈表等形態(tài)。環(huán)的應(yīng)用則有著名的約瑟夫問題：n 個人排列成圓形，每個人用編號表示，第1 個人從1 開始報數(shù)，報到m 的人退出，下一個人重新從1 開始報數(shù)，如此反復(fù)。對于給定的正整數(shù)n 和m，求退出的次序。在編寫了圖2 第三層的順序環(huán)類或者鏈?zhǔn)江h(huán)類之后，利用環(huán)這種形態(tài)及動態(tài)聯(lián)編技術(shù)，可以很簡潔地實現(xiàn)約瑟夫問題。用C++語言編寫的核心代碼如下：

除此之外，檢索技術(shù)中的線性探查法是環(huán)的一個重要應(yīng)用。用散列表組織數(shù)據(jù)時，線性探查法是最常用的沖突處理方法，該方法把數(shù)組視為一個首尾相接的環(huán)，第0 號下標(biāo)與第n‐1 號下標(biāo)是相鄰元素，當(dāng)存儲新元素發(fā)現(xiàn)有沖突時，按環(huán)的形態(tài)進(jìn)行旋轉(zhuǎn)逐個查找下一位置，直至找到合適位置把新元素存入其中。

4 結(jié)語

線性結(jié)構(gòu)是最重要的邏輯結(jié)構(gòu)，除了表、棧和隊列之外，線性結(jié)構(gòu)還應(yīng)包含環(huán)作為第四種形態(tài)，每一種邏輯結(jié)構(gòu)又分別可以有兩種不同的數(shù)據(jù)存儲方式。按圖2 表述線性結(jié)構(gòu)的各種形態(tài)，使得各種形態(tài)及具體實現(xiàn)之間的關(guān)系清晰明了，也與自上而下的設(shè)計理念相對應(yīng)。按這種方式組織相關(guān)知識的教學(xué)，不僅讓學(xué)生掌握各個具體的知識點，更能讓學(xué)生站在更高的角度觀察問題，把握知識的總體構(gòu)架。