數(shù)組和基本順序結(jié)構(gòu)

存儲和處理是程序設(shè)計的基本矛盾，但是存儲中有處理，可以稱為基本處理，例如機(jī)器指令中的操作碼，C語言內(nèi)部數(shù)值類型的運算符，而處理中也有存儲，處理的對象主要是存儲中的數(shù)據(jù)，處理的方法是存儲中的基本處理。

從它們這種既對立又統(tǒng)一的關(guān)系出發(fā)，可以清晰地描述出從數(shù)組到基本順序結(jié)構(gòu)的發(fā)展。

1 問題的提出

C語言基本類型，如整型、實型、字符型等，都含有對數(shù)據(jù)的基本操作，任何處理都以這些基本操作為方法，它們是類型的用戶，正是在這個意義上我們說，類型是重用的編程工具，程序是對特殊問題的解。

在數(shù)組處理中，往數(shù)組中插入一個數(shù)據(jù)、從數(shù)組中刪除一個數(shù)據(jù)、查找數(shù)組中的一個數(shù)據(jù)、查看數(shù)組中的數(shù)據(jù)個數(shù)等，是經(jīng)常使用的基本操作，但是這些基本操作并不是數(shù)組所固有的、用運算符來表示的、可以重用的處理，它們需要程序員自己來設(shè)計，這是“低級”的設(shè)計方法。如果這些操作重復(fù)摻雜在對數(shù)組的應(yīng)用程序中，就會妨礙針對問題的求解和對算法的分析。以表1為例，這是刪除數(shù)組的重復(fù)數(shù)據(jù)。陰影部分就是經(jīng)常使用的關(guān)于數(shù)組的基本操作。

表1 刪除數(shù)組中的重復(fù)數(shù)據(jù)

我們要做的是，把對數(shù)組的基本操作獨立出來，和數(shù)組定義“綁”在一起，使其近似一個類型，改進(jìn)我們對數(shù)組的處理方法。

還有，以字符數(shù)組為存儲空間的C串也遠(yuǎn)遠(yuǎn)不能滿足需要，這主要表現(xiàn)在兩個方面。一是存儲C串的數(shù)組容量不易確定。串的運算以串為對象，對空間的需求變化很大，例如，字符串的連接就要求第一個字符串的存儲空間能容下連接后的字符串。可是存儲C串的是靜態(tài)數(shù)組，其大小在編譯階段已確定，運行時無法改變，預(yù)留大了難免造成一部分閑置，預(yù)留不足可能導(dǎo)致“越界”。二是C串的基本運算函數(shù)的功能還不強(qiáng)，像子串連接、子串插入和子串刪除等運算還不屬于串的基本運算，這使實現(xiàn)像子串查找和替換這樣的處理還很困難。

為了彌補C串的不足，我們引入結(jié)構(gòu)串：使用動態(tài)字符數(shù)組，增強(qiáng)基本函數(shù)。結(jié)構(gòu)串的結(jié)構(gòu)如圖1。

圖1 結(jié)構(gòu)串存儲結(jié)構(gòu)

2基本順序表的設(shè)計

數(shù)組指針、數(shù)組長度和數(shù)組中數(shù)據(jù)元素個數(shù)是數(shù)組的整體特征，對數(shù)組的任何處理都與它們有關(guān)。例如，往數(shù)組中插入一個數(shù)據(jù)，需要判斷數(shù)組空間是否已滿，這需要判斷數(shù)組長度是否等于數(shù)組中數(shù)據(jù)元素個數(shù)；插入位置是否合法，這要求插入位置下標(biāo)不能小于0，也不能大于數(shù)據(jù)元素個數(shù)；插入后數(shù)據(jù)個數(shù)要增一。可是到目前為止，數(shù)組作為參數(shù)，傳遞的是數(shù)組地址，而數(shù)組長度和數(shù)據(jù)元素個數(shù)不含其中，需要單獨傳遞。例如起泡排序：

void Bubble (int *pa，int n);//起泡排序

形參pa指向整型數(shù)組，n表示數(shù)組中的數(shù)據(jù)個數(shù)。

如果一個算法需要改變數(shù)組中的數(shù)據(jù)個數(shù)，就需要以地址傳遞方式傳遞這個信息，以便主調(diào)函數(shù)可以得到改變后的數(shù)據(jù)個數(shù)值。例如表1的刪除數(shù)組的重復(fù)數(shù)據(jù)：

void Purge(int *pa，int *n);//刪除重復(fù)數(shù)據(jù)

往數(shù)組中插入一個數(shù)據(jù)，不僅要以地址傳遞方式傳遞數(shù)據(jù)個數(shù)，還要傳遞數(shù)組長度，以便在插入前判斷數(shù)組是否已滿和插入位置是否合法。

如上表明，應(yīng)該把數(shù)組指針、數(shù)組長度和數(shù)組中數(shù)據(jù)元素個數(shù)這些數(shù)組的特征“綁”在一起。一個具體做法是：建立一個結(jié)構(gòu)，包含數(shù)組和一個記錄數(shù)據(jù)個數(shù)的整型量；為了提高代碼復(fù)用率，用宏常量表示數(shù)組長度；以形式數(shù)據(jù)類型Type表示數(shù)組類型，執(zhí)行程序時，使用typedef命令將形式數(shù)據(jù)類型Type與一個具體類型等同起來，這樣可以提高代碼的復(fù)用性。于是我們得到下面的一個取名為SeqList的結(jié)構(gòu)：

typedef char Type;

//將形式數(shù)據(jù)類型Type等同于字符型

#define MaxSeqSize 100

//宏常量MaxSeqSize表示數(shù)組長度

struct SeqList

{

Type data[MaxSeqSize];

//形式數(shù)據(jù)類型Type表示數(shù)組類型

int size; //數(shù)據(jù)元素個數(shù)

};

這是表示數(shù)組整體特征的結(jié)構(gòu)，其中數(shù)組的大小和類型可以由用戶根據(jù)需要來設(shè)定。為了具體進(jìn)行討論，不失一般性，設(shè)定數(shù)組長度是100，數(shù)組類型是字符型。要使這個結(jié)構(gòu)在數(shù)組處理中發(fā)揮類似語言內(nèi)部類型的存儲的作用，就要使它具備基本處理。不過，語言內(nèi)部類型的基本處理是用運算符表示的，而結(jié)構(gòu)的基本處理受到C程序語言局限性的限制，還只能用函數(shù)來表示，我們稱之為基本函數(shù)。考慮到運算符的實質(zhì)是函數(shù)即運算符函數(shù)（參見上一期“指針和函數(shù)”一文），可以把基本函數(shù)看作是運算符的推廣。

⑴ 賦初值。對結(jié)構(gòu)的任何操作實際上都是對帶有整體特征的數(shù)組的操作。結(jié)構(gòu)的0元素其數(shù)據(jù)元素個數(shù)為0。與基本類型變量的初始化不同，0元素需要兩條語句共同創(chuàng)建：

SeqList L;①

L.size=0;②

它們是邏輯上的一條初始化語句。與以往結(jié)構(gòu)變量不同是，賦初值語句②還需要由下面的函數(shù)來完成：

void SetList(SeqList *l)

{

l->size=0;

}

該函數(shù)可以稱為構(gòu)造函數(shù)。于是，創(chuàng)建0元素的語句①和②轉(zhuǎn)為：

SeqList L;③

SetList(L);④

圖1語句③和④圖示

為什么要用函數(shù)替代一個簡單語句呢？為此，我們需要重新分析C語言固有類型，因為我們是在模仿它來創(chuàng)建類型。以整型為例，一般情況下，我們是通過諸如賦值、加、減、乘、除等運算符來引用整型數(shù)的，并不參與數(shù)據(jù)的內(nèi)部組織。一個整數(shù)占幾個字節(jié)，哪幾位表示符號，哪幾位表示數(shù)值，這是系統(tǒng)的事情。這不僅有利于保護(hù)數(shù)據(jù)的完整性，而且便于內(nèi)部擴(kuò)展或程序移植。例如從16位操作系統(tǒng)轉(zhuǎn)到32位操作系統(tǒng)，一個整數(shù)可能從2個字節(jié)轉(zhuǎn)到4個字節(jié)，都不影響程序的有效性。類似，結(jié)構(gòu)SeqList中存儲數(shù)據(jù)序列的是數(shù)組還是以后要講到的鏈表，用什么成員表示數(shù)據(jù)個數(shù)，是size還是last，對于這些，類型用戶都不需要了解。例如，如果我們把結(jié)構(gòu)成員size改為last，表示最后一個數(shù)據(jù)元素的下標(biāo)，那么數(shù)組為空時，last是-1：

void SetList(SeqList *l)

{

l->last=-1;

}

而對用戶來說，接口即函數(shù)名和參數(shù)表沒有變化，生成0元素的語句依然是③和④，這提高了代碼的復(fù)用率。不僅如此，數(shù)據(jù)個數(shù)是數(shù)組整體特征的一部分，0元素的size是0，有兩個數(shù)據(jù)時，size為2。不允許類型用戶直接訪問它，可以保證代表數(shù)組特征的成員數(shù)據(jù)的安全。

⑵ 基本操作。我們對結(jié)構(gòu)的任何處理都離不開一些基本操作，例如，插入一個數(shù)據(jù)、刪除一個數(shù)據(jù)、讀取一個數(shù)據(jù)等。這些基本操作的前后，其結(jié)構(gòu)都要代表數(shù)組整體特征，為此，基本操作就成為對結(jié)構(gòu)操作的“標(biāo)準(zhǔn)方法”。例如刪除一個元素，假設(shè)數(shù)組已有4個數(shù)據(jù)，現(xiàn)在要將某一下標(biāo)的元素刪除。步驟：

① 判斷數(shù)組空間是否為空，如果空，就要向調(diào)用這個基本操作的算法發(fā)出類似“空間已空”信息，而且可以終止程序。

② 判斷刪除元素的位置是否合法。數(shù)組中的數(shù)據(jù)是連續(xù)存放的，因此，被刪除元素的下標(biāo)不能小于0，也不能大于表中最后一個元素的下標(biāo)3（最后一個元素下標(biāo)是數(shù)組元素個數(shù)減1），否則也要發(fā)出類似“刪除位置不合法”信息，終止程序。

③ 假設(shè)刪除下標(biāo)為1的元素，那么下標(biāo)從2到3的元素都要依次向前拷貝。

④ 數(shù)據(jù)元素個數(shù)減1。

void Erase(SeqList *l，int id)//定點刪除。將下標(biāo)為id的元素刪除

{

if(l->size==0)//①

SeqError(\"Erase: an empty list!\");

if(id<0||id>l->size-1)//②

SeqError(\"Erase: Index is out of range!\");

for(int i=id+1;isize;i++)//③

->data[i-1]=l->data[i];

l->size--;//④

}

圖2 刪除示意圖

我們把SeqList結(jié)構(gòu)、構(gòu)造函數(shù)和基本函數(shù)當(dāng)作一個整體，稱為基本順序表。

基本順序表的聲明：[1]

typedef char Type;

#define MaxSeqSize 100

struct SeqList

{

Type data[MaxSeqSize];

int size;

};

void SetList(SeqList *l);

//構(gòu)造函數(shù)。給元素個數(shù)size賦值0

int ListSize(const SeqList *l);

//求長。取元素個數(shù)

int ListEmpty(const SeqList *l);

//判空。判斷表是否空

int ListFull(const SeqList *l);

//判滿。判斷表是否滿

Type GetData(const SeqList *l，int id);

//取值。取下標(biāo)為id的元素

int Find(const SeqList *l，Type item);

//查找。確定元素item在表中的下標(biāo)

void Replace(SeqList *l，Type item，int id);

//替換。用元素item替換表中下標(biāo)為id的元素

void Insert(SeqList *l，Type item，int id);

//插入。將元素item插入到表中下標(biāo)為id的位置

void InsertRear(SeqList *l， Type item);

//尾插。將元素item插到表的尾元素之后

void Erase(SeqList *l，int id);

//定點刪除。將表中下標(biāo)為id的元素刪除

void ClearList(SeqList *l);

//清表。將元素個數(shù)置0

void SeqError(const char *c);

//錯誤信息報告

對數(shù)組而言，基本順序表是發(fā)展了的存儲，在這個存儲上的刪除重復(fù)數(shù)據(jù)的處理見表2。

表2 刪除重復(fù)數(shù)據(jù)的兩種方法比較

3 結(jié)構(gòu)串的設(shè)計

結(jié)構(gòu)串結(jié)構(gòu)的聲明：[1]

#include

struct String

{

char *str;int size;

};

void SetString(String *s，const char *c);//構(gòu)造

void FreeString(String *s);//析構(gòu)

void StrAssign(String *s，const String *cs);

//將結(jié)構(gòu)串cs賦值給結(jié)構(gòu)串s

void CStrAssign(String *s，const char *c);

//將串c賦值給結(jié)構(gòu)串s

int StrCompare(const String *s，const String *cs);

//兩個結(jié)構(gòu)串比較

String* StrConcat(const String *s，const String *cs，String *w);

//結(jié)構(gòu)串s和cs連接為結(jié)構(gòu)串w

String* SubString(const String *s，String *cs，int id，int count);

//從結(jié)構(gòu)串s的下標(biāo)id開始連續(xù)

//取count個字符組成結(jié)構(gòu)串cs

String* StrInsert(String *s，const String *cs，int id);

//在結(jié)構(gòu)串s的下標(biāo)id插入結(jié)構(gòu)串cs

void StrErase(String *s，int id，int count);

//從結(jié)構(gòu)串s的下標(biāo)id開始連續(xù)刪除count個字符

void GetStr(String *s);//串輸入

void PutStr(const String *s);//串輸出

int StrLength(const String *s);//求串長

int StrEmpty(const String *s);//判串空

char StrGetData(const String *s，int id);

//返回下標(biāo)id處的字符

char *Char(String *s);//取C串指針

int Find(const String *s，char ch，int start);

//從start開始查找ch

void ClearString(String *s);//清為空串

void StrError(const char *c);//錯誤信息報告

對C串而言，結(jié)構(gòu)串是發(fā)展了的存儲，在這個存儲上的子串查找處理如下：

int FindPat(String *s，String *p，int start);

從位置start開始，在本串s中搜索模式串p，若找到，則返回模式串p第一個字符在本串s中的下標(biāo)，若沒有找到，則返回-1。步驟：

① 從start開始，在本串中確定模式串首字符第一次出現(xiàn)的位置matchStartId，和模式串尾字符可能出現(xiàn)的位置matchEndId。

② 若在本串matchStartId和matchEndId位置上的字符分別等于模式串的首尾字符，則取中間子串；若這個子串與模式串的首尾字符的中間子串相等，則返回matchStartId值。算法結(jié)束。

③ Start加1，重復(fù)步驟①。

int FindPat(const String *s，const String *p，int start)

{

int pLen=StrLength(p)， lastStrId=StrLength(s)-1; //模式串p長和本串尾字符的下標(biāo)

char pStartChar=StrGetData(p，0)，

//取模式串首字符

pEndChar=StrGetData(p，pLen-1);

//取模式串尾字符

int matchStartId，matchEndId;

//分別記錄本串中與模式串首尾字符匹配的字符下標(biāo)

String pIn，cs;

//分別存放模式串首尾字符中間的子串和本串的子串

SetString(pIn，\"\");

SetString(cs，\"\");

if(pLen>2)

//若模式長度大于2，取出模式串首尾字符中間的子串

SubString(p，pIn，1，pLen-2);

matchStartId=Find(s，pStartChar，start); //①

matchEndId=matchStartId+pLen-1;

while(matchStartId!= -1matchEndId<=lastStrId)

//與模式串首字符相同的本串子串

{

if(StrGetData(s，matchEndId)==pEndChar)//②如果尾字符相等

{

if(pLen<=2)

//若模式串長度小于2，則找到匹配子串

{

FreeString(pIn);

FreeString(cs);

Return(matchStartId);

}

SubString(s，cs，matchStartId+1，pLen-2);//取中間串

if(StrCompare(cs，pIn)==0)

{

FreeString(pIn);

FreeString(cs);

return(matchStartId);

}

}

start=matchStartId+1;//③

matchStartId=Find(s，pStartChar，start);

matchEndId=matchStartId+pLen-1;

}

FreeString(pIn);FreeString(cs);

return(-1);

}

圖3 模式匹配示意圖

4小結(jié)

存儲和處理這個程序設(shè)計的基本矛盾，在機(jī)器語言階段的表現(xiàn)是機(jī)器指令系統(tǒng)和處理的矛盾，在C語言階段，是內(nèi)部類型與處理的矛盾。C內(nèi)部類型的局限性是顯然的，上面例舉的數(shù)組和C串可以說明這一點。基本順序表和結(jié)構(gòu)串在很大程度上克服了這種局限性，而且在這個過程中，程序員起到了積極的、決定性的作用。為什么這樣說呢？因為對C編譯器來說，構(gòu)造函數(shù)、析構(gòu)函數(shù)、基本操作函數(shù)和求解特殊問題的函數(shù)（例如Purge）在聲明格式、實現(xiàn)步驟和調(diào)用方法上沒有區(qū)別，把它們從概念上和應(yīng)用方法上區(qū)分開來、分別作為存儲中的基本處理和應(yīng)用處理來對待的是程序員。每一個程序員在設(shè)計程序時，首先要選擇合適的類型，即編程工具，如果工具不夠好，就改進(jìn)工具，甚至重新創(chuàng)建工具。從這個意義上說，改進(jìn)或創(chuàng)建工具是程序設(shè)計的一部分。一個優(yōu)秀的程序員應(yīng)該自覺地意識到自己既是工具的創(chuàng)建者，又是工具的用戶。當(dāng)人們說，優(yōu)秀的語言并不能保證優(yōu)秀的代碼，而優(yōu)秀的程序員，不管使用什么語言，都能編寫出優(yōu)秀的程序，說的就是這一層意思。

基本順序結(jié)構(gòu)的局限性也是顯然的，不僅如上所說基本函數(shù)和應(yīng)用函數(shù)在聲明格式、實現(xiàn)步驟和調(diào)用方法上沒有區(qū)分，而且結(jié)構(gòu)串的賦值、連接和比較也不能用相應(yīng)的運算符表示。一句話，C結(jié)構(gòu)還不能像C內(nèi)部類型一樣使用，這實質(zhì)上是C語言的局限性。程序員不僅最大限度地克服了C語言局限性，而且也具體表達(dá)了對C語言未來發(fā)展的要求。這個要求的綜合實現(xiàn)產(chǎn)生了C++。

從C到C++是一個否定之否定過程。抓住存儲和處理這個矛盾，否定之否定這個過程就容易看出來了。

參考文獻(xiàn)

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