用面向對象理念設計線性表的構架

韓海 董蘊源

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

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

1 線性表各概念間的關系

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

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

圖1：順序表、鏈表與線性表的關系

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

2 面向對象理念在線性表中的體現

面向對象程序設計以對象作為基本元素，核心理念包括抽象、封裝、繼承和多態。抽象是提取事物的屬性和行為特征，封裝是把屬性和行為組織在一起，并規定訪問權限，實施這種封裝的程序元素是類和實例。繼承是通過在已有的類的基礎上添加屬性、添加行為或者修改已有行為的表現方式而產生新的事物。描述原事物的類稱為基類，描述新事物的類稱為派生類。多態是指同一種行為在事物中可以有不同的表現形式，在同一個類當中有不同的表現稱為函數重載或者方法重載，在基類與派生類之間的不同表現稱為函數覆蓋或者方法重寫。

圖1 是一種典型的繼承派生關系。線性表是基類，規定了這種結構應具備創建、插入、刪除等功能，順序表是以數組存儲數據元素的派生類，鏈表則是以鏈式結構存儲數據元素的派生類。經典教材都用抽象數據類型規定了線性表的插入、刪除操作可以在任何合理的位置進行，順序表、鏈表都必須為此編寫相應的代碼。但是，在用繼承派生關系來處理棧和隊列時會遇到困難，棧和隊列是不允許在任意位置插入、刪除元素的，也就是說，棧和隊列關于插入和刪除操作與線性表有不同的規定，棧和隊列在線性表的基礎上減少了功能，那么，棧和隊列還是線性表嗎？目前，各類教材、文獻中都明確指出棧和隊列是特殊的線性表，卻沒有解釋如何在面向對象的編程方式下屏蔽掉線性表規定的那些功能。

3 用面向對象理念對線性表進行頂層設計

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

在線性結構的基礎上添加一些限制可以產生不同的形態，除了表、棧和隊列之外，環也是一種常用形態。每一種形態是一種邏輯結構，它們具有若干共同的特征。

每一種邏輯結構又分別可以采用順序存儲方式或者鏈式存儲方式，一般把順序存儲數據對象的表稱為順序表，鏈式存儲數據對象的表稱為鏈表。相應地有順序棧、鏈式棧、順序隊列和鏈式隊列等概念。作為線性結構的第四種形態，可以把順序存儲數據對象的環稱為順序環，鏈式存儲的環稱為鏈式環。上述所有概念的關系構成非常明晰的層次關系，如圖2所示。

圖2：線性結構各種形態之間的關系

記數據對象的類型為ElemType，可以為線性結構定義抽象數據類型如下：

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

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

圖2 描述的各種線性結構及相互關系與面向對象理念中的繼承是直接對應的。針對最頂層的線性結構可以編寫一個抽象類，這是其它所有類的基類。第二層的各個概念分別是在線性結構之上添加了若干功能，并且只規定功能和相應參數而不規定如何實現，它們是線性結構的派生類，仍然是抽象類。第三層確定了數據的存儲方式，編寫的類不再是抽象類，需要為抽象類中規定的各項功能編寫函數代碼。

例如，位于第二層的環仍然是一個抽象類，對應的抽象數據類型可以描述為：

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

在確定了用數組或者鏈表作為數據對象的存儲方式之后，對圖2 當中第三層的順序環或者鏈式環可以編寫相應的類，并在這種存儲方式之下實現創建、消除、插入、刪除、查找、旋轉等功能。

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

除此之外，檢索技術中的線性探查法是環的一個重要應用。用散列表組織數據時，線性探查法是最常用的沖突處理方法，該方法把數組視為一個首尾相接的環，第0 號下標與第n‐1 號下標是相鄰元素，當存儲新元素發現有沖突時，按環的形態進行旋轉逐個查找下一位置，直至找到合適位置把新元素存入其中。

4 結語

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