摘要：堆和棧是C語言程序設(shè)計(jì)課程中的兩個(gè)重要概念，在程序設(shè)計(jì)和代碼分析中應(yīng)用廣泛。文章首先介紹程序運(yùn)行時(shí)的內(nèi)存空間分布，包括代碼區(qū)、全局變量區(qū)、棧和堆，然后討論棧的基本原理和特點(diǎn)以及棧在函數(shù)調(diào)用執(zhí)行過程中的應(yīng)用，然后通過例子演示棧在代碼分析中的作用，詳細(xì)闡述在遞歸函數(shù)調(diào)用的執(zhí)行過程中控制流和數(shù)據(jù)流的變化過程，最后介紹堆的基本概念和應(yīng)用特點(diǎn)。

關(guān)鍵詞：程序設(shè)計(jì)；堆；棧；函數(shù)調(diào)用；遞歸

0 引 言

在講授C語言程序設(shè)計(jì)課程時(shí)，教師會(huì)碰上兩個(gè)頗有挑戰(zhàn)性的概念：堆（ heap）與棧（ stack）。一方面，這兩個(gè)概念非常重要，在程序設(shè)計(jì)和代碼分析中經(jīng)常要用到，只有理解了這兩個(gè)概念，才能對(duì)程序運(yùn)行時(shí)的一些規(guī)律和特點(diǎn)有著更深刻的認(rèn)識(shí)；另一方面，這麗個(gè)概念又有一定的難度，涉及程序設(shè)計(jì)課程以外的一些知識(shí)，如操作系統(tǒng)和編譯原理等，因此教師不太好講授這部分內(nèi)容，學(xué)生也不太容易理解。

從大的方面來說，堆和棧實(shí)際上是屬于操作系統(tǒng)課程的內(nèi)容，描述的是一個(gè)進(jìn)程的內(nèi)存空間分布情況。所謂進(jìn)程，即一個(gè)程序的一次運(yùn)行。當(dāng)磁盤上的一個(gè)可執(zhí)行程序運(yùn)行時(shí)，它就會(huì)被裝入到計(jì)算機(jī)的內(nèi)存，在內(nèi)存中運(yùn)行。一般來說，進(jìn)程的內(nèi)存空間分布情況如圖l所示。

從圖l可以看出，當(dāng)一個(gè)可執(zhí)行程序（EXE文件）被裝入到內(nèi)存時(shí)，它主要包括兩個(gè)部分：代碼和數(shù)據(jù)。對(duì)于代碼，它會(huì)被裝入到內(nèi)存中的代碼區(qū)，這部分內(nèi)容是只讀的，不能被修改。對(duì)于數(shù)據(jù)，它又由3部分組成：①全局變量：根據(jù)其是否有初始值，被裝入到內(nèi)存中的未初始化數(shù)據(jù)區(qū)和初始化數(shù)據(jù)區(qū)；②局部變量：在函數(shù)調(diào)用發(fā)生時(shí)存放在棧中；③動(dòng)態(tài)內(nèi)存空間：在程序運(yùn)行時(shí)申請(qǐng)的動(dòng)態(tài)內(nèi)存空間存放在堆中。

代碼區(qū)和全局變量區(qū)也稱為靜態(tài)區(qū)域，這是因?yàn)樵谘b入這個(gè)可執(zhí)行程序時(shí)，這部分內(nèi)容的大小是已知、固定的，而棧和堆稱為動(dòng)態(tài)區(qū)域，這是因?yàn)檫@部分內(nèi)容的大小是動(dòng)態(tài)可變的。

1 棧（ stack）

棧本質(zhì)上是一種數(shù)據(jù)結(jié)構(gòu)，其特點(diǎn)是后進(jìn)先出。打個(gè)比方，教室中靠墻的一排座位，學(xué)生在進(jìn)去時(shí)只能從靠過道的那一側(cè)進(jìn)去，一個(gè)接一個(gè)往里走，先進(jìn)去的人靠著墻坐，后進(jìn)去的人靠著過道坐，但是在出來的時(shí)候卻是按照相反的順序，靠過道的學(xué)生先出來，然后才是靠墻的學(xué)生，這就是后進(jìn)先出的特點(diǎn)。

在程序運(yùn)行過程中，棧主要有兩個(gè)用途：一是用作暫存功能，用來保存程序運(yùn)行時(shí)的上下文信息，即各個(gè)CPU寄存器的值；二是在函數(shù)調(diào)用發(fā)生時(shí)用來保存被調(diào)用函數(shù)的局部變量和形參。對(duì)于前者，主要體現(xiàn)在匯編語言級(jí)別，因此在學(xué)習(xí)C語言時(shí)不必關(guān)注，文中主要考察后者。

1.1 函數(shù)調(diào)用的執(zhí)行過程

在C語言中，當(dāng)一個(gè)函數(shù)被調(diào)用時(shí)，其執(zhí)行過程如下：①在內(nèi)存的棧空間中為其分配一個(gè)棧幀，用來存放該函數(shù)的形參和局部變量；②將實(shí)參的值復(fù)制給相應(yīng)的形參變量；③控制流轉(zhuǎn)移到該函數(shù)的起始位置；④該函數(shù)開始執(zhí)行；⑤控制流和返回值返回到函數(shù)調(diào)用點(diǎn)，棧幀釋放。

1

void main（）

2{

3 int num；

4 printf（“請(qǐng)輸入一個(gè)整數(shù)：”）；

5

scanf（“%d”，#）；

6 printf（”%d”， Times2（num））；

7 }

8 int Times2（int value）

9{

10 return（2* value）；

11}

例如，對(duì)于上述程序，在它的執(zhí)行過程中，棧幀的變化情況如圖2所示。當(dāng)main函數(shù)被執(zhí)行時(shí)，在棧當(dāng)中為它分配一塊棧幀，用來存放它的局部變量num。然后，當(dāng)執(zhí)行到該程序的第6行時(shí)調(diào)用Times2函數(shù)，因此在棧當(dāng)中又為這次函數(shù)調(diào)用分配一塊棧幀，用于存放它的形參value。接下來，進(jìn)行參數(shù)傳遞，將實(shí)參num的值傳給形參value，然后控制流跳轉(zhuǎn)到第8行Times2函數(shù)的起始地址，并開始逐條語句執(zhí)行當(dāng)Times2函數(shù)執(zhí)行完成后，其棧幀被釋放，棧幀中的變量也不能再訪問。

在了解了函數(shù)調(diào)用的執(zhí)行過程以及棧幀的原理后，學(xué)生就會(huì)對(duì)C語言程序有更深入的理解，對(duì)于一些C語言的語法，不僅能知其然，還能知其所以然。

在C語言的語法中，局部變量具有如下特點(diǎn)：①局部變量只在本函數(shù)范圍內(nèi)有效；②在不同函數(shù)中可使用相同名字的局部變量；③形參也是局部變量，也只能在本函數(shù)中使用；④局部變量的生存期：當(dāng)函數(shù)被調(diào)用時(shí)，其局部變量才被創(chuàng)建并分配相應(yīng)內(nèi)存空間；當(dāng)函數(shù)調(diào)用結(jié)束后，局部變量即消亡，其空間被釋放。

局部變量之所以具有上述這些特點(diǎn)，根本原因就是棧幀的工作原理。需要指出的是，在函數(shù)調(diào)用的執(zhí)行過程中，棧幀的申請(qǐng)和釋放由系統(tǒng)自動(dòng)完成，程序員并不知曉。具體來說，編洋器在編譯源代碼時(shí)，會(huì)在函數(shù)定義所在的位置加入一些匯編指令，將棧指針（ stack pointer， SP）移動(dòng)到合適的位置，從而創(chuàng)建棧幀并為形參和局部變量分配空間。

1.2 代碼分析

棧幀的原理還可以用來進(jìn)行代碼分析，例如，對(duì)于下列程序：

void swap（int x，int y）

{

int temp；

temp= X；

X =y；

y= temp；

}

void main（）

{

int a-b；

a=4：

b=7：

swap（a，b）；

printf（”%d，%d＼n”，a，b）；

}

該程序的輸出結(jié)果并非所預(yù)期的7和4，而是4和7，即swap函數(shù)根本沒有發(fā)生作用。如果用棧幀分析該程序，就會(huì)非常直觀、清晰。swap函數(shù)被調(diào)用時(shí)的棧幀情況如圖3所示。

從圖3可以看出，mam函數(shù)在調(diào)用swap函數(shù)時(shí)，會(huì)將實(shí)參a和b的值傳遞給形參x和y，因此x為4，y為7，然后在執(zhí)行完swap函數(shù)之后，這兩個(gè)變量的值的確被交換了，即x=7，y=4，但是在C語言中，函數(shù)的參數(shù)傳遞是單向的值傳遞，只能從實(shí)參傳給形參，而不能從形參反傳給實(shí)參。實(shí)際上，實(shí)參并不一定是變量，也可能是常量或表達(dá)式，換言之，它并不一定具有內(nèi)存空間以容納數(shù)據(jù)，因此當(dāng)swap函數(shù)運(yùn)行結(jié)束后，main函數(shù)中變量a和b的值沒有發(fā)生任何變化，并且隨著swap函數(shù)的棧幀被釋放，形參x和y也無法再訪問。

1.3 函數(shù)的遞歸調(diào)用

函數(shù)調(diào)用有一個(gè)特例即遞歸調(diào)用，即在調(diào)用一個(gè)函數(shù)的過程中，又出現(xiàn)直接或間接地調(diào)用該函數(shù)本身的情形。在遞歸函數(shù)調(diào)用執(zhí)行過程中，內(nèi)存空間的分配以及代碼的執(zhí)行過程是怎么樣的呢？筆者通過一個(gè)小例子進(jìn)行闡釋。

1

void main（）

2{

3

int n：

4 printf（”請(qǐng)輸入一個(gè)整數(shù)：”）；

5 scanf（”%d”，&n）；

6 printf（”%df=%d'’，n，fact（n））；

7}

8 int fact（intm）

9{

10 if（m一1）return （1）；

11 else return（m * fact（m-l》；

12}

以上程序的功能是采用遞歸方法計(jì)算一個(gè)整數(shù)的階乘，這個(gè)程序的執(zhí)行過程中會(huì)多次重復(fù)地調(diào)用fact函數(shù)。遞歸函數(shù)調(diào)用的棧幀變化如圖4所示。從控制流（指令的執(zhí)行流程）與數(shù)據(jù)流的配合情況來看，當(dāng)mam函數(shù)被調(diào)用時(shí)，棧會(huì)為它分配一塊棧幀用來存放局部變量n，如圖4（a）所示。假設(shè)在執(zhí)行時(shí)用戶輸入了一個(gè)整數(shù)3，因此n=3。接下來，當(dāng)執(zhí)行到程序的第6行時(shí)，第1次調(diào)用了fact函數(shù)，因此就在棧中為它分配一塊棧幀，用來存放它的形參變量m，隨后進(jìn)行參數(shù)傳遞，把實(shí)參n的值傳給形參m，因此m=3，如圖4 （b）所示。接下來，控制流跳轉(zhuǎn)到fact函數(shù)的代碼去運(yùn)行，即從程序的第8行開始運(yùn)行。

當(dāng)程序運(yùn)行到第1 1行時(shí)，第2次調(diào)用fact函數(shù)，即遞歸調(diào)用。此次函數(shù)調(diào)用與普通的函數(shù)調(diào)用完全相同，如圖4（c）所示，首先在棧中分配一塊棧幀，用來存放形參變量m，這個(gè)m與第1次fact調(diào)用中的m不同，兩者的變量名雖然相同，但是存放在內(nèi)存的不同位置，是兩個(gè)相互獨(dú)立的變量。事實(shí)上，所謂的變量名只是對(duì)程序員來說有意義，而在編譯時(shí)，所有的變量名都會(huì)被轉(zhuǎn)換為相應(yīng)的內(nèi)存地址。接下來是參數(shù)傳遞，實(shí)參是fact（3）（即第1次fact調(diào)用）中的表達(dá)式m-l，其值為2，形參為fact（2）（即第2次fact調(diào)用）中的變量m。

在參數(shù)傳遞完成后，控制流就會(huì)跳轉(zhuǎn)到fact函數(shù)的代碼去運(yùn)行，即再次從程序的第8行開始運(yùn)行，要注意控制流和數(shù)據(jù)流是相互獨(dú)立的。對(duì)于控制流，由于代碼指令是只讀的，只能讀不能寫，因此同一段代碼指令可以多次、反復(fù)地運(yùn)行，不會(huì)有任何沖突和混亂。因?yàn)樗^的指令執(zhí)行，無非把程序計(jì)數(shù)器（ program counter， PC）指向指令的起始地址，然后把指令裝入到CPU執(zhí)行，此過程并不會(huì)改變指令本身；而數(shù)據(jù)流則不同，在每一次調(diào)用fact函數(shù)時(shí)，訪問的是不同的數(shù)據(jù)，即不同棧幀中的變量m。換句話說，在第1次調(diào)用fact函數(shù)時(shí)，執(zhí)行的指令是程序中的8-12行語句，訪問的數(shù)據(jù)是棧中的第1塊fact棧幀；而在第2次調(diào)用fact函數(shù)時(shí)，執(zhí)行的指令仍然是程序中的8-12行語句，但訪問的數(shù)據(jù)是棧中的第2塊fact棧幀。打個(gè)比方，就好像用鍋炒菜，鍋是相同的，翻炒的過程也是相同的，但是每次放的原材料不同，因此炒出來的菜也不同。

后面的過程是類似的，每一次遞歸調(diào)用都會(huì)在棧中分配一塊空間，存放相應(yīng)的形參和局部變量，然后進(jìn)行參數(shù)傳遞并跳轉(zhuǎn)到函數(shù)的起始地址運(yùn)行。在第3次調(diào)用fact函數(shù)時(shí)，由于此時(shí)m=l，因此走到了遞歸邊界，直接返回一個(gè)1（即1?。?，不再進(jìn)行遞歸調(diào)用。當(dāng)這次函數(shù)調(diào)Hj結(jié)束后，其棧幀就會(huì)被釋放，如圖4 （e）所示；隨后控制流返回到程序的第1 1行，計(jì)算2 1并返回此結(jié)果。當(dāng)fact（2）執(zhí)行完后，其棧幀被釋放，如圖4 （f）所示，隨后控制流返回到fact（3），計(jì)算3 1并將結(jié)果返回到main函數(shù)。

通過上述分析可知，對(duì)于遞歸函數(shù)必須設(shè)定遞歸邊界，即在何種情形下遞歸調(diào)用結(jié)束，不允許無限次的遞歸調(diào)用。否則，由于每一次函數(shù)調(diào)用都要在棧中分配一塊棧幀，而棧的大小有l(wèi)5艮，這樣，在遞歸調(diào)用了一定的次數(shù)后，棧空間就滿了，就無法再進(jìn)行遞歸調(diào)用。

2 堆（ heap）

在進(jìn)程的地址空間中，除了棧以外，還有一塊內(nèi)存空間是堆，它主要用于動(dòng)態(tài)分配。所謂動(dòng)態(tài)分配，即在程序運(yùn)行時(shí)分配的內(nèi)存空間。C語言可以通過malloc函數(shù)申請(qǐng)動(dòng)態(tài)內(nèi)存空間，其用法為“void *malloc（size_t size）；”。其中，size表示申請(qǐng)的字節(jié)數(shù)，如果申請(qǐng)成功，則返回相應(yīng)內(nèi)存空間的起始地址，否則返回一個(gè)常量NULL。

堆和棧是兩塊相對(duì)獨(dú)立的內(nèi)存空間，如前所述，在調(diào)用一個(gè)函數(shù)時(shí)，棧中會(huì)分配一塊棧幀，用于存放該函數(shù)的形參和局部變量；然后在函數(shù)調(diào)用結(jié)束后，該棧幀就會(huì)被釋放，而那些形參和局部變量就無法再訪問，但是對(duì)于動(dòng)態(tài)申請(qǐng)的堆空間來說，系統(tǒng)不會(huì)自動(dòng)釋放，因此在函數(shù)調(diào)用結(jié)束以后，該部分空間依然存在，還可以繼續(xù)訪問。

void main（）

{

int a[5]_{1，一l，2，-2，0}；

int b[5]-{3，1，一2，4，1}；

int*C，i；

c= Add（a，b，5）；

if（c—NULL） return；

for（i=0；i<5； i++）

printf（”%d”，c[i]）；

}

int *Add（int a[]， int b[]，int num）

{

inti，*c；

c =（int*）malloc（5*sizeof（int》；

if（c—NULL） return（NULL）；

for（i=O；i

c[i]=a[i]+b[i]；

return C：

}

對(duì)于上面這個(gè)程序，其在mam函數(shù)中定義了兩個(gè)數(shù)組a和b，然后調(diào)用Add函數(shù)將這兩個(gè)數(shù)組的相應(yīng)元素相加，結(jié)果保存在一個(gè)動(dòng)態(tài)數(shù)組中并將其起始地址返回給mam函數(shù)，然后在maln函數(shù)中再訪問這個(gè)動(dòng)態(tài)數(shù)組。在該程序中，如果將Add函數(shù)中的動(dòng)態(tài)數(shù)組修改為靜態(tài)數(shù)組，即將語句“c =（int*）malloc（5*sizeof（int》；”修改為“int c[5]；”，則該程序就是錯(cuò)誤的，打印的結(jié)果將會(huì)出現(xiàn)異常。原因在于當(dāng)Add函數(shù)運(yùn)行結(jié)束后，其棧幀會(huì)被釋放，其內(nèi)部的形參和局部變量都無法再訪問；而如果是動(dòng)態(tài)數(shù)組，其空間是位堆而非棧當(dāng)中，因此當(dāng)Add函數(shù)運(yùn)行結(jié)束后該空間依然存在，程序在返回到mam函數(shù)后該數(shù)組仍然可以正常訪問。

對(duì)于malloc申請(qǐng)的動(dòng)態(tài)空間，系統(tǒng)會(huì)予以保留，不會(huì)主動(dòng)釋放。如果該空間使用完畢，程序員必須自己使用free函數(shù)進(jìn)行釋放，即malloc函數(shù)與free函數(shù)要配對(duì)使用，申請(qǐng)了多大的空間就必須釋放多大的空間。如果程序設(shè)計(jì)得不夠完善，就可能出現(xiàn)內(nèi)存泄露的情形。所謂內(nèi)存泄露，即分配出去的內(nèi)存無法回收回來。內(nèi)存泄漏的后果比較嚴(yán)重，隨著程序的不斷運(yùn)行，內(nèi)存越來越少，最后用malloc函數(shù)就申請(qǐng)不到存儲(chǔ)空間。當(dāng)然，這里所說的內(nèi)存泄漏不是指物理內(nèi)存的泄漏，而是指進(jìn)程的邏輯地址空間，因此并不會(huì)影響到系統(tǒng)中的其他進(jìn)程，而當(dāng)一個(gè)進(jìn)程運(yùn)行完成后，它的整個(gè)地址空間都會(huì)被釋放。

void main（）

{

char *p；

int size=0：

while（l）

{

p 2 （char *）malloc（1024*1024）；

if（p—NULL） break；

else

{

printf（“%dM＼n"，++size）；

}

}

}

以上這段程序就是用來測(cè)試內(nèi)存泄露。它每次只申請(qǐng)空間而不釋放空間，從而導(dǎo)致內(nèi)存泄露，最終，當(dāng)內(nèi)存空間不夠時(shí)，malloc函數(shù)就無法再申請(qǐng)成功，從而返回一個(gè)NULL。

3 結(jié)語

在C語言程序設(shè)計(jì)課程的講授中，大部分的語法知識(shí)點(diǎn)都較為簡(jiǎn)單，學(xué)生理解起來也不困難，但堆和棧是例外，它們是C程序設(shè)計(jì)中的兩個(gè)重要概念，由于涉及操作系統(tǒng)等其他課程的內(nèi)容，因此具有一定的難度，學(xué)生不容易理解。如何講好這部分內(nèi)容，值得教師認(rèn)真思考。筆者通過一些編程案例，詳細(xì)闡釋了棧與堆的基本原理以及在程序運(yùn)行過程中的應(yīng)用，尤其是對(duì)于函數(shù)的遞歸調(diào)用，學(xué)生經(jīng)常無法理解；描述了在遞歸函數(shù)調(diào)用過程中控制流和數(shù)據(jù)流的變化過程，清晰地闡述了遞歸調(diào)用的原理。在未來的工作中，我們將進(jìn)一步完善相關(guān)的工作，用更加形象、直觀的方式闡述棧和堆的基本原理。