從數(shù)組到C++順序表類的對比概述

徐陽　陳俐潔

摘 要：程序語言的矛盾實際上是程序設計的矛盾，而存儲與處理就是程序設計的基本矛盾。但是存儲中包含處理，而存儲中的數(shù)據(jù)就是被處理的對象。矛盾雙方既是對立的，同時又統(tǒng)一的。從而可以清晰地對比出從數(shù)組到順序表類的轉(zhuǎn)換而帶來的便利。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu) 數(shù)組 順序表

中圖分類號：TP311 文獻標識碼：A 文章編號：1672-3791（2018）02（c）-0001-02

Abstract：The contradiction of programming language is actually the contradiction of program design， and storage and processing is the basic contradiction of program design. But the storage contains processing， and the data stored is the object being processed. The two sides are both antagonistic and unified. This allows for a clear comparison of the convenience of converting from array to sequential table classes.

Key Words：Data structure；Arrya；Sequence table

數(shù)據(jù)結(jié)構(gòu)是一組有組織的數(shù)據(jù)和對數(shù)據(jù)的基本操作，而算法是用基本操作表示的對數(shù)據(jù)進行處理有限的步驟。所以說算法是要依賴于數(shù)據(jù)結(jié)構(gòu)的，而數(shù)組結(jié)構(gòu)是為算法提供支持的。

在C語言的基本類型中，例如：char類型、double類型、float類型、int類型等，都含有對數(shù)據(jù)的基本操作。圖1是刪除數(shù)組中的重復的數(shù)據(jù)元素來說明數(shù)組的局限性。

從函數(shù)purge_array中可以看出，在對數(shù)組插入、刪除、確定數(shù)組元素個數(shù)等的操作，都是經(jīng)常使用的操作，但是這些基本操作并不是數(shù)組所固有的，此時基本操作的代碼和算法的代碼混在一起難以維護和閱讀。我們需要做的就是把這些基本操作分別設計為基本函數(shù)。

1 C基本順序表的局限性

我們要把對數(shù)組的基本操作獨立出來和數(shù)組的定義綁定在一起，使它們近似成為一個類型來改進對數(shù)組的處理方式并不是一件容易的事情。比如往數(shù)組中插入一個數(shù)據(jù)元素需要經(jīng)過以下幾個步驟：（1）判斷數(shù)組空間是否已滿。需要確定數(shù)組元素的個數(shù)是否小于數(shù)組容量，如果數(shù)組已滿，那么不能再插入。（2）檢驗插入位置。要求要插入的位置的下標大于0，但是同時也要保證不大于數(shù)據(jù)元素的個數(shù)。（3）只要不是在數(shù)組的末位插入數(shù)據(jù)元素那么還需要移動現(xiàn)有的數(shù)據(jù)元素。（4）插入之后數(shù)據(jù)的個數(shù)要加1。

從以上的步驟可以看出數(shù)組作為參數(shù)傳遞的是數(shù)組的地址，但是數(shù)組長度和數(shù)據(jù)元素個數(shù)不包含在內(nèi)，還需要單獨傳遞。只有把數(shù)組的首元素指針、數(shù)組長度和數(shù)據(jù)元素的個數(shù)等基本特征組織為一個整體才能設計出對數(shù)組的基本操作函數(shù)。因此得到一個被稱作SeqList的結(jié)構(gòu)，如圖2所示。

我們要使這個SeqList結(jié)構(gòu)在處理數(shù)組中起到作用就要使它具備基本的處理。但是語言內(nèi)部類型的基本處理是用運算符來表示的，而SeqList結(jié)構(gòu)的處理受到C語言的局限性限制只能用函數(shù)來表示[1]。我們把SeqList這個結(jié)構(gòu)和基于SeqList結(jié)構(gòu)體來設計對數(shù)組的基本操作的函數(shù)作為一個整體形成的數(shù)據(jù)結(jié)構(gòu)叫做基本順序表。圖3為基本順序表的聲明。

從數(shù)組的角度來看，順序表是一種新的發(fā)展了的存儲結(jié)構(gòu)，圖4為刪除C順序表中的重復元素和刪除數(shù)組中重復的元素的對比。

經(jīng)過以上的對比我們會發(fā)現(xiàn)順序表提升了C語言數(shù)組的抽象層次但是也能看出其固有的局限性：（1）函數(shù)和表達式的矛盾。在順序表中，求長、判空等簡單的表達式為了封裝的原則都要用函數(shù)來表示，這樣既占空間又費時間，執(zhí)行速度慢。（2）數(shù)組元素的局限性。在順序表中的數(shù)組元素是結(jié)構(gòu)體時，如果含有邏輯運算符和關(guān)系運算符，那么基本操作函數(shù)都要修改，破壞了順序表的復用性[2]。（3）實例化的局限性。順序表只能實例化一次。（4）基本操作函數(shù)和算法很難區(qū)分。（5）結(jié)構(gòu)體變量是淺復制的。在順序表中，使用賦值運算符把一個順序表變量的值復制給另一個順序表變量會涉及到其包含的指針data。在復制時要把指針data本身的值和其所指向的空間同時復制給另一個指針。但是C語言只有淺復制，因此順序表是不可以作為函數(shù)的參數(shù)的。

2 C++順序表類的產(chǎn)生

由于C++編譯器克服了C語言固有的局限性，因此，我們把C順序表轉(zhuǎn)換為C++順序表類來使用。圖5為C++順序表類的聲明同時實現(xiàn)了類內(nèi)部分功能函數(shù)的實現(xiàn)。

通過以上的實例可以看出，在順序表的基本操作函數(shù)轉(zhuǎn)換成順序表的成員函數(shù)之后，在定義、聲明、調(diào)用等方面都能和算法區(qū)別開，由此可見C++順序表類解決了C基本順序表的局限性，突出了很多優(yōu)點：（1）實現(xiàn)了代碼和數(shù)據(jù)的抽象。C++是利用private、public、protected等不同關(guān)鍵字的訪問權(quán)限來實現(xiàn)數(shù)據(jù)的抽象的。私有成員對成員函數(shù)公開，只能由成員函數(shù)來訪問，因此對算法是不可見的。（2）從關(guān)鍵字struct到class的轉(zhuǎn)換。class的默認項的訪問權(quán)限是private的。（3）把Type值傳遞的方式改變?yōu)槭褂胏onst引用傳遞。（4）把函數(shù)返回值類型Type改變?yōu)閏onst引用的方式。

C++引入了類的創(chuàng)建機制，通過訪問權(quán)限把類的數(shù)據(jù)成員封裝起來，使數(shù)據(jù)的實際存儲形式對類的用戶是不可見的。

3 結(jié)語

程序是算法與數(shù)據(jù)結(jié)構(gòu)的組成，這說明程序與數(shù)據(jù)結(jié)構(gòu)是相輔相成不可分割的整體。順序表雖然在很大程度上克服了這種局限性，但是其基本函數(shù)和應用函數(shù)在聲明、實現(xiàn)、調(diào)用上沒有區(qū)分開來，因此，我們要根據(jù)實際情況來應用。

參考文獻

[1] 王立柱.C/C++與數(shù)據(jù)結(jié)構(gòu)（上冊）[M].3版.北京：清華大學出版社，2008：142，164.

[2] 嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)：C語言版[M].北京：清華大學出版社，2002.