再論C語言數組
C語言處理數組的方式是它廣受歡迎的原因之一。C語言對數組的處理是非常有效的,其原因有以下三點:第一,除少數翻譯器出于謹慎會作一些繁瑣的規定外,C語言的數組下標是在一個很低的層次上處理的。但這個優點也有一個反作用,即在程序運行時你無法知道一個數組到底有多大,或者一個數組下標是否有效。ANSI/ISOC標準沒有對使用越界下標的行為作出定義,因此,一個越界下標有可能導致這樣幾種后果:
??? (1) 程序仍能正確運行;
??? (2) 程序會異常終止或崩潰;
??? (3) 程序能繼續運行,但無法得出正確的結果;
??? (4) 其它情況。
換句話說,你不知道程序此后會做出什么反應,這會帶來很大的麻煩。有些人就是抓住這一點來批評C語言的,認為C語言只不過是一種高級的匯編語言。然而,盡管C程序出錯時的表現有些可怕,但誰也不能否認一個經過仔細編寫和調試的C程序運行起來是非常快的。
第二,數組和指針能非常和諧地在一起工作。當數組出現在一個表達式中時,它和指向數組中第一個元素的指針是等價的,因此數組和指針幾乎可以互換使用。此外,使用指針要比使用數組下標快兩倍。
第三,將數組作為參數傳遞給函數和將指向數組中第一個元素的指針傳遞給函數是完全等價的。將數組作為參數傳遞給函數時可以采用值傳遞和地址傳遞兩種方式,前者需要完整地拷貝初始數組,但比較安全;后者的速度要快得多,但編寫程序時要多加小心。C++和ANSIC中都有const關鍵字,利用它可以使地址傳遞方式和值傳遞方式一樣安全。
數組和指針之間的這種聯系會引起一些混亂,例如以下兩種定義是完全相同的:
??? void f(chara[MAX])
??? {
??????? /*...? */
??? }
??? void f(char *a)
??? {??? ·
??????? /*...? */
??? }
注意:MAX是一個編譯時可知的值,例如用#define預處理指令定義的值。
這種情況正是前文中提到的第三個優點,也是大多數C程序員所熟知的。這也是唯一一種數組和指針完全相同的情況,在其它情況下,數組和指針并不完全相同。例如,當作如下定義 (可以出現在函數說明以外的任何地方)時:
??? char??? a[MAX];
系統將分配MAX個字符的內存空間。當作如下說明時:
??? char?? *a;
系統將分配一個字符指針所需的內存空間,可能只能容納2個或4個字符。如果你在源文件中作如下定義:
??? char??? a[MAX];
但在頭文件作如下說明;
??? extern char?? *a;
就會導致可怕的后果。為了避免出現這種情況,最好的辦法是保證上述說明和定義的一致性,例如,如果在源文件中作如下定義:
??? char??? a[MAX];
那么在相應的頭文件中就作如下說明,
??? externchar??? a[];
上述說明告訴頭文件a是一個數組,不是一個指針,但它并不指示數組a中有多少個元素,這樣說明的類型稱為不完整類型。在程序中適當地說明一些不完整類型是很常見的,也是一種很好的編程習慣。是的,對數組a[MAX](MAX是一個編譯時可知的值)來說,它的第一個和最后一個元素分別是a[o]和aLMAX-1)。在其它一些語言中,情況可能有所不同,例如在BASIC語言中數組a[MAX]的元素是從a[1]到a[MAX],在Pascal語言中則兩種方式都可行。
注意:a[MAX]是一個有效的地址,但該地址中的值并不是數組a的一個元素。
上述這種差別有時會引起混亂,因為當你說“數組中的第一個元素”時,實際上是指“數組中下標為。的元素”,這里的“第一個”的意思和“最后一個”相反。
盡管你可以假造一個下標從1開始的數組,但在實際編程中不應該這樣做。下文將介紹這種技巧,并說明為什么不應該這樣做的原因。
因為指針和數組幾乎是相同的,因此你可以定義一個指針,使它可以象一個數組一樣引用另一個數組中的所有元素,但引用時前者的下標是從1開始的:
??? /*don't do this!!*/
??? int a0[MAX],
??? int *a1=a0-1; /*&a0[-1)*/
現在,a0[0]和a1[1)是相同的,而a0[MAX-1]和a1[MAX]是相同的。然而,在實際編程中不應該這樣做,其原因有以下兩點:
第一,這種方法可能行不通。這種行為是ANSI/ISOC標準所沒有定義的(并且是應該避免的),而&a0[-1)完全有可能不是一個有效的地址(見9.3)。對于某些編譯程序,你的程序可能根本不會出問題;在有些情況下,對于任何編譯程序,你的程序可能都不會出問題;但是,誰能保證你的程序永遠不會出問題呢????
第二,這種方式背離了C語言的常規風格。人們已經習慣了C語言中數組下標的工作方式,如果你的程序使用了另外一種方式,別人就很難讀懂你的程序,而經過一段時間以后,連你自己都可能很難讀懂這個程序了。
你可以使用數組后面第一個元素的地址,但你不可以查看該地址中的值。對大多數編譯程序來說,如果你寫如下語句:
??? int??? i,a[MAX],j;
那么i和j都有可能存放在數組a最后一個元素后面的地址中。為了判斷跟在數組a后面的是i還是j,你可以把i或j的地址和數組a后面第一個元素的地址進行比較,即判斷"&i==&a[MAX]"或"&j==&a[MAX]"是否為真。這種方法通常可行,但不能保證。
問題的關鍵是:如果你將某些數據存入a[MAX]中,往往就會破壞原來緊跟在數組a后面的數據。即使查看a[MAX]的值也是應該避免的,盡管這樣做一般不會引出什么問題。
為什么在C程序中有時要用到&a[MAX]呢?因為很多C程序員習慣通過指針遍歷一個數組中的所有元素,即用
??? for(i=0;i<MAX;++i)
??? {???
??????? /*do something*/
??? }
代替
??? for(p=a; p<&a[MAX];++p)
??? {
??????? /*do something*/
??? }
這種方式在已有的C程序中是隨處可見的,因此ANSIC標準規定這種方式是可行的。
如果你的程序是在理想的計算機上運行,即它的取址范圍是從00000000到FFFFFFFF,那么你大可以放心,但是,實際情況往往不會這么簡單。
在有些計算機上,地址是由兩部分組成的,第一部分是一個指向某一塊內存的起始點的指,針(即基地址),第二部分是相對于這塊內存的起始點的地址偏移量。這種地址結構被稱為段地址結構,子程序調用通常就是通過在棧指針上加上一個地址偏移量來實現的。采用段地址結構的最典型的例子是基于Intel 8086的計算機,所有的MS-DOS程序都在這種計算機上運行(在基于Pentium芯片的計算機上,大多數MS-DOS程序也在與8086兼容的模式下運行)。即使是性能優越的具有線性地址空間的RISC芯片,也提供了寄存器變址尋址方式,即用一個寄存器保存指向某一塊內存的起始點的指針,用另一個寄存器保存地址偏移量。
如果你的程序使用段地址結構,而在基地址處剛好存放著數組a0(即基地址指針和&a0[0]相同),這會引出什么問題呢?既然基地址無法(有效地)改變,而偏移量也不可能是負值,因此“位于a0[0]前面的元素”這種說法就沒有意義了,ANSIC標準明確規定引用這個元素的行為是沒有定義的,這也就是9.1中所提到的方法可能行不通的原因。
同樣,如果數組a(其元素個數為MAX)剛好存放在某段內存的尾部,那么地址&a[MAX]就是沒有意義的,如果你的程序中使用了&a[MAX],而編譯程序又要檢查&a[MAX]是否有效,那么編譯程序必然就會報告沒有足夠的內存來存放數組a。
盡管在編寫基于Windows,UNIX或Macintosh的程序時不會遇到上述問題,但是C語言不僅僅是為這幾種情況設計的,C語言必須適應各種各樣的環境,例如用微處理器控制的烤面包爐,防抱死剎車系統,MS-DOS,等等。嚴格按C語言標準編寫的程序能被順利地編譯并能服務于任何目的,但是,有時程序員也可以適度地背離C語言的標準,這要視程序員、編譯程序和程序用戶三者的具體要求而定。
不可以。當把數組作為函數的參數時,你無法在程序運行時通過數組參數本身告訴函數該數組的大小,因為函數的數組參數相當于指向該數組第一個元素的指針。這意味著把數組傳遞給函數的效率非常高,也意味著程序員必須通過某種機制告訴函數數組參數的大小。
為了告訴函數數組參數的大小,人們通常采用以下兩種方法:
第一種方法是將數組和表示數組大小的值一起傳遞給函數,例如memcpy()函數就是這樣做的:
??? char? source[MAX],dest[MAX];
??? /*...? */
??? memcpy(dest,source,MAX);
第二種方法是引入某種規則來結束一個數組,例如在C語言中字符串總是以ASCII字符NUL('\0')結束,而一個指針數組總是以空指針結束。請看下述函數,它的參數是一個以空指針結束的字符指針數組,這個空指針告訴該函數什么時候停止工作:
??? void printMany(char *strings口)???
??? {
??????? int? i;
??????? i=0;???
??????? while(strings[i]!=NULL)
??????? {
??????????? puts(strings[i]);
??????????? ++i;
??????? }
??? }
正象9.5中所說的那樣,C程序員經常用指針來代替數組下標,因此大多數C程序員通常會將上述函數編寫得更隱蔽一些:
??? void printMany(char *strings[])
??? {
??????? while(*strings)
??????? {
??????????? puts(*strings++);
??????? }
??? }
盡管你不能改變一個數組名的值,但是strings是一個數組參數,相當于一個指針,因此可以對它進行自增運算,并且可以在調用puts()函數時對strings進行自增運算。在上例中,while(*strings)
??? 就相當于
??? while(*strings !=NULL)
在寫函數文檔(例如在函數前面加上注釋,或者寫一份備忘錄,或者寫一份設計文檔)時,寫進函數是如何知道數組參數的大小是非常重要的,例如,你可以非常簡略地寫上“以空指針結束”或“數組elephants中有numElephants個元素”(如果你在程序中用數字13表示數組的大小,你可以寫進“數組arr中有13個元素”這樣的描述,然而用確切的數字表示數組的大小不是一種好的編程習慣)。
與使用下標相比,使用指針能使C編譯程序更容易地產生優質的代碼。假設你的程序中有這樣一段代碼:
/* X la some type */
X????? a[MAX];????????????
X????? *p;??? /*pointer*/
X????? x;???? /*element*/
int??? i;???? /*index*/
為了歷數組a中的所有元素,你可以采用這樣一種循環方式(方式a)
/*version (a)*/
for (i = 0; i<MAX;? ++i)
{
????? x=a[i];
????? /* do something with x * /
}
你也可以采用這樣一種循環方式(方式b)
/*veraion(b)*/
for (p = a; p<&a[MAX];? ++p?? )
{
????? x=*p;
????? /* do aomething with x * /
}
這兩種方式有什么區別呢?兩種方式中的初始情況和遞增運算是相同的,作為循環條件的比較表達式也是相同的(下文中將進一步討論這一點)。區別在于“x=a[]”和“x=*p”,前者要確定a[i]的地址,因此需要將i和類型x的大小相乘后再與數組a中第一個元素的地址相加;
后者只需間接引用指針p。間接引用是快速的,而乘法運算卻比較慢。
這是一種“微效率”現象,它可能對程序的總體效率有影響,也可能沒有影響。對方式a來說,如果循環體中的操作是將數組中的元素相加,或者只是移動數組中的元素,那么每次循環中大部分時間就消耗在使用數組下標上;如果循環體中的操作是某種I/O操作,或者是函數調用,那么使用數組下標所消耗的時間是微不足道的。
在有些情況下,乘法運算的開銷會降低。例如,當類型x的大小為1時,經過優化就可以將乘法運算省去(一個值乘以1仍然等于這個值);當類型x的大小是2的冪時(此時類型x通常是系統固有類型),乘法運算就可以被優化為左移位運算(就象一個十進制的數乘以10一樣)。
在方式b中,每次循環都要計算&a[MAX],這需要多大代價呢?這和每次計算a[i]的代價相同嗎?答案是不同,因為在循環過程中&a[MAX]是不變的。任何一種合格的編譯程序都只會在循環開始時計算一次&a[MAX],而在以后的每次循環中重復使用這次計算所得的值。
在編譯程序確認在循環過程中a和MAX都不變的前提下,方式b和以下代碼的效果是相同的:
/* how the compiler implements version (b) */
X????? *temp =? &a[MAX];???? /* optimization */
for (p = a; p< temp; ++p? )
{
??? x =*p;
??? /*do something with x * /
}
遍歷數組元素還可以有另外兩種方式,即以遞減而不是遞增的順序遍歷數組元素。對按順序打印數組元素這樣的任務來說,后兩種方式沒有什么優勢,但是對數組元素相加這樣的任務來說,后兩種方式比前兩種方式更好。通過下標并且以遞減順序遍歷數組元素的方式(方式c)如下所示(人們通常認為將一個值和。比較的代價要比將一個值和一個非零值比較的代價小:
/* version (c) */
for (i = MAX - 1; i>=0; --i)
{
????? x=a[i];
????? /* do aomcthing with x * /
}
?? ?通過指針并以遞減順序遍歷數組元素的方式(方式d)如下所示,其中作為循環條件的比較表達式顯得很簡潔:
/* version (d) */
for (p = &a[MAX - 1]; p>=a;? --p? )
{
????? x =*P;
????? /*do something with x * /
}
與方式d類似的代碼是很常見的,但不是絕對正確的,因為循環結束的條件是p小于a,而這有時是不可能的(見9.3)。
通常人們會認為“任何合格的能優化代碼的編譯程序都會為這4種方式產生相同的代碼”,但實際上許多編譯程序都沒能做到這一點。筆者曾編寫過一個測試程序(其中類型x的大小不是2的冪,循環體中的操作是一些無關緊要的操作),并用4種差別很大的編譯程序編譯這個程序,結果發現方式b總是比方式a快得多,有時要快兩倍,可見使用指針和使用下標的效果是有很大差別的(有一點是一致的,即4種編譯程序都對&a[MAX]進行了前文提到過的優化)。
那么在遍歷數組元素時,以遞減順序進行和以遞增順序進行有什么不同呢?對于其中的兩種編譯程序,方式c和方式d的速度基本上和方式a相同,而方式b明顯是最快的(可能是因為其比較操作的代價較小,但是否可以認為以遞減順序進行要比以遞增順序進行慢一些呢?);對于其中的另外兩種編譯程序,方式c的速度和方式a基本相同(使用下標要慢一些),但方式d的速度比方式b要稍快一些。
總而言之,在編寫一個可移植性好、效率高的程序時,為了遍歷數組元素,使用指針比使用下標能使程序獲得更快的速度;在使用指針時,應該采用方式b,盡管方式d一般也能工作,但編譯程序為方式d產生的代碼可能會慢一些。?
需要補充的是,上述技巧只是一種細微的優化,因為通常都是循環體中的操作消耗了大部分運行時間,許多C程序員往往會舍本求末,忽視這種實際情況,希望你不要犯相同的錯誤。不可以,盡管在一個很常見的特例中好象可以這樣做。
數組名不能被放在賦值運算符的左邊(它不是一個左值,更不是一個可修改的左值)。一個數組是一個對象,而它的數組名就是指向這個對象的第一個元素的指針。???
如果一個數組是用extern或static說明-的,則它的數組名是在連接時可知的一個常量,你不能修改這樣一個數組名的值,就象你不能修改7的值一樣。
給數組名賦值是毫無根據的。一個指針的含義是“這里有一個元素,它的前后可能還有其它元素”,一個數組名的含義是“這里是一個數組中的第一個元素,它的前面沒有數組元素,并且只有通過數組下標才能引用它后面的數組元素”。因此,如果需要使用指針,就應該使用指針。
有一個很常見的特例,在這個特例中,好象可以修改一個數組名的值:
??? void f(chara[12])
??? {
??????? ++a;? /*legal!*/
??? }
秘密在于函數的數組參數并不是真正的數組,而是實實在在的指針,因此,上例和下例是等價的:
??? void f(char *a)
??? {
??????? ++a;? /*certainlylegal*/
??? }
如果你希望上述函數中的數組名不能被修改,你可以將上述函數寫成下面這樣,但為此你必須使用指針句法:
??? void{(char *const a)
??? {
??????? ++a;? /*illegal*/
??? }
在上例中,參數a是一個左值,但它前面的const關鍵字說明了它是不能被修改的。
前者是指向數組中第一個元素的指針,后者是指向整個數組的指針。
注意;筆者建議讀者讀到這里時暫時放下本書,寫一下指向一個含MAX個元素的字符數組的指針變量的說明。提示:使用括號。希望你不要敷衍了事,因為只有這樣你才能真正了解C語言表示復雜指針的句法的奧秘。下文將介紹如何獲得指向整個數組的指針。
數組是一種類型,它有三個要素,即基本類型(數組元素的類型),大小(當數組被說明為不完整類型時除外),數組的值(整個數組的值)。你可以用一個指針指向整個數組的值:
??? char? a[MAX];??? /*arrayOfMAXcharacters*/
??? char??? *p;??? ? /*pointer to one character*/
??? /*pa is declared below*/
??? pa=&al
??? p=a;???????????? /* =&a[0] */
在運行了上述這段代碼后,你就會發現p和pa的打印結果是一個相同的值,即p和pa指向同一個地址。但是,p和pa指向的對象是不同的。
以下這種定義并不能獲得一個指向整個數組的值的指針:
??? char *(ap[MAX]);
上述定義和以下定義是相同的,它們的含義都是“ap是一個含MAX個字符指針的數組”;
??? char *ap[MAX];
并不是所有的常量都可以用來定義一個數組的初始大小,在C程序中,只有C語言的常量表達式才能用來定義一個數組的初始大小。然而,在C++中,情況有所不同。
一個常量表達式的值在程序運行期間是不變的,并且是編譯程序能計算出來的一個值。在定義數組的大小時,你必須使用常量表達式,例如,你可以使用數字:
??? char??? a[512];
或者使用一個預定義的常量標識符:
??? #define MAX??? 512
??? /*...? */
??? char??? a[MAX];
或者使用一個sizeof表達式:
??? char? a[sizeof(structcacheObject)];
或者使用一個由常量表達式組成的表達式:
??? char??? buf[sizeof(struct cacheObject) *MAX];
或者使用枚舉常量。
在C中,一個初始化了的constint變量并不是一個常量表達式:
??? int??? max=512;??? /* not a constant expression in C */
??? char? buffer[max];? /* notvalid C */
然而,在C++中,用const int變量定義數組的大小是完全合法的,并且是C++所推薦的。盡管這會增加C++編譯程序的負擔(即跟蹤const int變量的值),而C編譯程序沒有這種負擔,但這也使C++程序擺脫了對C預處理程序的依賴。
數組的元素可以是任意一種類型,而字符串是一種特殊的數組,它使用了一種眾所周知的確定其長度的規則。
有兩種類型的語言,一種簡單地將字符串看作是一個字符數組,另一種將字符串看作是一種特殊的類型。C屬于前一種,但有一點補充,即C字符串是以一個NUL字符結束的。數組的值和數組中第一個元素的地址(或指向該元素的指針)是相同的,因此通常一個C字符串和一個字符指針是等價的。
一個數組的長度可以是任意的。當數組名用作函數的參數時,函數無法通過數組名本身知道數組的大小,因此必須引入某種規則。對字符串來說,這種規則就是字符串的最后一個字符是ASCII字符NUL('\0')。
在C中,int類型值的字面值可以是42這樣的值,字符的字面值可以是‘*’這樣的值,浮點型值的字面值可以是4.2el這樣的單精度值或雙精度值。
注意:實際上,一個char類型字面值是一個int類型字面值的另一種表示方式,只不過使用了一種有趣的句法,例如當42和'*'都表示char類型的值時,它們是兩個完全相同的值。然而,在C++中情況有所不同,C++有真正的char類型字面值和char類型函數參數,并且通常會更仔細地區分char類型和int類型,整數數組和字符數組沒有字面值。然而,如果沒有字符串字面值,程序編寫起來就會很困難,因此C提供了字符串字面值。需要注意的是,按照慣例C字符串總是以NUL字符結束,因此C字符串的字面值也以NUL字符結束,例如,“six times nine”的長度是15個字符(包括NUL終止符),而不是你看得見的14個字符。
關于字符串字面值還有一條鮮為人知但非常有用的規則,如果程序中有兩條緊挨著的字符串字面值,編譯程序會將它們當作一條長的字符串字面值來對待,并且只使用一個NUL終止符。也就是說,“Hello,”world”和“Hello,world”是相同的,而以下這段代碼中的幾條字符串字面值也可以任意分割組合:
??? char??? message[]=
??? ”This is an extremely long prompt\n”
??? ”How long is it?\n”
??? ”It's so long,\n”
??? ”It wouldn't fit On one line\n”;
在定義一個字符串變量時,你需要有一個足以容納該字符串的數組或者指針,并且要保證為NUL終止符留出空間,例如,以下這段代碼中就有一個問題:
??? char greeting[12];
??? strcpy(greeting,”Hello,world”);? /*trouble*/
在上例中,greeting只有容納12個字符的空間,而“Hello,world”的長度為13個字符(包括NUL終止符),因此NUL字符會被拷貝到greeting以外的某個位置,這可能會毀掉greetlng附近內存空間中的某些數據。再請看下例:
??? char? greeting[12]=”Hello,world”;/*notastring*/
上例是沒有問題的,但此時greeting是一個字符數組,而不是一個字符串。因為上例沒有為NUL終止符留出空間,所以greeting不包含NUL字符。更好一些的方法是這樣寫:
??? char? greeting[]=”Hello,world”;
這樣編譯程序就會計算出需要多少空間來容納所有內容,包括NUL字符。
字符串字面值是字符(char類型)數組,而不是字符常量(const char類型)數組。盡管ANSIC委員會可以將字符串字面值重新定義為字符常量數組,但這會使已有的數百萬行代碼突然無法通過編譯,從而引起巨大的混亂。如果你試圖修改字符串字面值中的內容,編譯程序是
不會阻止你的,但你不應該這樣做。編譯程序可能會選擇禁止修改的內存區域來存放字符串字面值,例如ROM或者由內存映射寄存器禁止寫操作的內存區域。但是,即使字符串字面值被存放在允許修改的內存區域中,編譯程序還可能會使它們被共享。例如,如果你寫了以下代碼(并且字符串字面值是允許修改的):
??? char??? *p="message";
??? char??? *q="message";
??? p[4]='\0'; /* p now points to”mess”*/
編譯程序就會作出兩種可能的反應,一種是為p和q創建兩個獨立的字符串,在這種情況下,q仍然是“message”;一種是只創建一個字符串(p和q都指向它),在這種情況下,q將變成“mess”。
注意:有人稱這種現象為“C的幽默”,正是因為這種幽默,絕大多數C程序員才會整天被自己編寫的程序所困擾,難得忙里偷閑一次。