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

徐陽(yáng)　陳俐潔

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

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

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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ù)和對(duì)數(shù)據(jù)的基本操作，而算法是用基本操作表示的對(duì)數(shù)據(jù)進(jìn)行處理有限的步驟。所以說(shuō)算法是要依賴于數(shù)據(jù)結(jié)構(gòu)的，而數(shù)組結(jié)構(gòu)是為算法提供支持的。

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

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

1 C基本順序表的局限性

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

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

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

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

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

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

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

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

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

3 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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