C程序設計課程中的堆與棧

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

關鍵詞：程序設計；堆；棧；函數調用；遞歸

0 引 言

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

從大的方面來說，堆和棧實際上是屬于操作系統課程的內容，描述的是一個進程的內存空間分布情況。所謂進程，即一個程序的一次運行。當磁盤上的一個可執行程序運行時，它就會被裝入到計算機的內存，在內存中運行。一般來說，進程的內存空間分布情況如圖l所示。

從圖l可以看出，當一個可執行程序（EXE文件）被裝入到內存時，它主要包括兩個部分：代碼和數據。對于代碼，它會被裝入到內存中的代碼區，這部分內容是只讀的，不能被修改。對于數據，它又由3部分組成：①全局變量：根據其是否有初始值，被裝入到內存中的未初始化數據區和初始化數據區；②局部變量：在函數調用發生時存放在棧中；③動態內存空間：在程序運行時申請的動態內存空間存放在堆中。

代碼區和全局變量區也稱為靜態區域，這是因為在裝入這個可執行程序時，這部分內容的大小是已知、固定的，而棧和堆稱為動態區域，這是因為這部分內容的大小是動態可變的。

1 棧（ stack）

棧本質上是一種數據結構，其特點是后進先出。打個比方，教室中靠墻的一排座位，學生在進去時只能從靠過道的那一側進去，一個接一個往里走，先進去的人靠著墻坐，后進去的人靠著過道坐，但是在出來的時候卻是按照相反的順序，靠過道的學生先出來，然后才是靠墻的學生，這就是后進先出的特點。

在程序運行過程中，棧主要有兩個用途：一是用作暫存功能，用來保存程序運行時的上下文信息，即各個CPU寄存器的值；二是在函數調用發生時用來保存被調用函數的局部變量和形參。對于前者，主要體現在匯編語言級別，因此在學習C語言時不必關注，文中主要考察后者。

1.1 函數調用的執行過程

在C語言中，當一個函數被調用時，其執行過程如下：①在內存的棧空間中為其分配一個棧幀，用來存放該函數的形參和局部變量；②將實參的值復制給相應的形參變量；③控制流轉移到該函數的起始位置；④該函數開始執行；⑤控制流和返回值返回到函數調用點，棧幀釋放。

1

void main（）

2{

3 int num；

4 printf（“請輸入一個整數：”）；

5

scanf（“%d”，#）；

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

7 }

8 int Times2（int value）

9{

10 return（2* value）；

11}

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

在了解了函數調用的執行過程以及棧幀的原理后，學生就會對C語言程序有更深入的理解，對于一些C語言的語法，不僅能知其然，還能知其所以然。

在C語言的語法中，局部變量具有如下特點：①局部變量只在本函數范圍內有效；②在不同函數中可使用相同名字的局部變量；③形參也是局部變量，也只能在本函數中使用；④局部變量的生存期：當函數被調用時，其局部變量才被創建并分配相應內存空間；當函數調用結束后，局部變量即消亡，其空間被釋放。

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

1.2 代碼分析

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

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）；

}

該程序的輸出結果并非所預期的7和4，而是4和7，即swap函數根本沒有發生作用。如果用棧幀分析該程序，就會非常直觀、清晰。swap函數被調用時的棧幀情況如圖3所示。

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

1.3 函數的遞歸調用

函數調用有一個特例即遞歸調用，即在調用一個函數的過程中，又出現直接或間接地調用該函數本身的情形。在遞歸函數調用執行過程中，內存空間的分配以及代碼的執行過程是怎么樣的呢？筆者通過一個小例子進行闡釋。

1

void main（）

2{

3

int n：

4 printf（”請輸入一個整數：”）；

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}

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

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

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

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

通過上述分析可知，對于遞歸函數必須設定遞歸邊界，即在何種情形下遞歸調用結束，不允許無限次的遞歸調用。否則，由于每一次函數調用都要在棧中分配一塊棧幀，而棧的大小有l5艮，這樣，在遞歸調用了一定的次數后，?？臻g就滿了，就無法再進行遞歸調用。

2 堆（ heap）

在進程的地址空間中，除了棧以外，還有一塊內存空間是堆，它主要用于動態分配。所謂動態分配，即在程序運行時分配的內存空間。C語言可以通過malloc函數申請動態內存空間，其用法為“void *malloc（size_t size）；”。其中，size表示申請的字節數，如果申請成功，則返回相應內存空間的起始地址，否則返回一個常量NULL。

堆和棧是兩塊相對獨立的內存空間，如前所述，在調用一個函數時，棧中會分配一塊棧幀，用于存放該函數的形參和局部變量；然后在函數調用結束后，該棧幀就會被釋放，而那些形參和局部變量就無法再訪問，但是對于動態申請的堆空間來說，系統不會自動釋放，因此在函數調用結束以后，該部分空間依然存在，還可以繼續訪問。

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：

}

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

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

void main（）

{

char *p；

int size=0：

while（l）

{

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

if（p—NULL） break；

else

{

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

}

}

}

以上這段程序就是用來測試內存泄露。它每次只申請空間而不釋放空間，從而導致內存泄露，最終，當內存空間不夠時，malloc函數就無法再申請成功，從而返回一個NULL。

3 結語

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