谌卫军
（清华大学 计算机科学与技术系，北京 100084）
摘 要：堆和栈是C语言程序设计课程中的两个重要概念，在程序设计和代码分析中应用广泛。文章首先介绍程序运行时的内存空间分布，包括代码区、全局变量区、栈和堆，然后讨论栈的基本原理和特点以及栈在函数调用执行过程中的应用，然后通过例子演示栈在代码分析中的作用，详细阐述在递归函数调用的执行过程中控制流和数据流的变化过程，最后介绍堆的基本概念和应用特点。
教育期刊网 http://www.jyqkw.com
关键词 ：程序设计；堆；栈；函数调用；递归
作者简介：谌卫军，男，讲师，研究方向为计算机基础教学、计算机技术和网络学习，cwj@tsinghua.edu.cn。
0 引 言
在讲授C语言程序设计课程时，教师会碰上两个颇有挑战性的概念：堆（heap）与栈（stack）。一方面，这两个概念非常重要，在程序设计和代码分析中经常要用到，只有理解了这两个概念，才能对程序运行时的一些规律和特点有着更深刻的认识；另一方面，这两个概念又有一定的难度，涉及程序设计课程以外的一些知识，如操作系统和编译原理等，因此教师不太好讲授这部分内容，学生也不太容易理解。
从大的方面来说，堆和栈实际上是属于操作系统课程的内容，描述的是一个进程的内存空间分布情况。所谓进程，即一个程序的一次运行。当磁盘上的一个可执行程序运行时，它就会被装入到计算机的内存，在内存中运行。一般来说，进程的内存空间分布情况如图1所示。
从图1可以看出，当一个可执行程序（EXE文件）被装入到内存时，它主要包括两个部分：代码和数据。对于代码，它会被装入到内存中的代码区，这部分内容是只读的，不能被修改。对于数据，它又由3部分组成：①全局变量：根据其是否有初始值，被装入到内存中的未初始化数据区和初始化数据区；②局部变量：在函数调用发生时存放在栈中；③动态内存空间：在程序运行时申请的动态内存空间存放在堆中。
代码区和全局变量区也称为静态区域，这是因为在装入这个可执行程序时，这部分内容的大小是已知、固定的，而栈和堆称为动态区域，这是因为这部分内容的大小是动态可变的。
1 栈（stack）
栈本质上是一种数据结构，其特点是后进先出。打个比方，教室中靠墙的一排座位，学生在进去时只能从靠过道的那一侧进去，一个接一个往里走，先进去的人靠着墙坐，后进去的人靠着过道坐，但是在出来的时候却是按照相反的顺序，靠过道的学生先出来，然后才是靠墙的学生，这就是后进先出的特点。
在程序运行过程中，栈主要有两个用途：一是用作暂存功能，用来保存程序运行时的上下文信息，即各个CPU寄存器的值；二是在函数调用发生时用来保存被调用函数的局部变量和形参。对于前者，主要体现在汇编语言级别，因此在学习C语言时不必关注，文中主要考察后者。
1.1 函数调用的执行过程
在C语言中，当一个函数被调用时，其执行过程如下：①在内存的栈空间中为其分配一个栈帧，用来存放该函数的形参和局部变量；②将实参的值复制给相应的形参变量；③控制流转移到该函数的起始位置；④该函数开始执行；⑤控制流和返回值返回到函数调用点，栈帧释放。
1 void main （ ）
2 {
3 int num;
4 printf（"请输入一个整数："）;
5 scanf（"%d"， &num）;
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可以看出，main函数在调用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（"%d！ = %d"， n， fact（n））;
7 }
8 int fact（int m）
9 {
10 if（m == 1） return （1）;
11 else return（m * fact（m-1））;
12 }
以上程序的功能是采用递归方法计算一个整数的阶乘，这个程序的执行过程中会多次重复地调用fact函数。递归函数调用的栈帧变化如图4所示。从控制流（指令的执行流程）与数据流的配合情况来看，当main函数被调用时，栈会为它分配一块栈帧用来存放局部变量n，如图4（a）所示。假设在执行时用户输入了一个整数3，因此n=3。接下来，当执行到程序的第6行时，第1次调用了fact函数，因此就在栈中为它分配一块栈帧，用来存放它的形参变量m，随后进行参数传递，把实参n的值传给形参m，因此m=3，如图4（b）所示。接下来，控制流跳转到fact函数的代码去运行，即从程序的第8行开始运行。
当程序运行到第11行时，第2次调用fact函数，即递归调用。此次函数调用与普通的函数调用完全相同，如图4（c）所示，首先在栈中分配一块栈帧，用来存放形参变量m，这个m与第1次fact调用中的m不同，两者的变量名虽然相同，但是存放在内存的不同位置，是两个相互独立的变量。事实上，所谓的变量名只是对程序员来说有意义，而在编译时，所有的变量名都会被转换为相应的内存地址。接下来是参数传递，实参是fact（3）（即第1次fact调用）中的表达式m-1，其值为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=1，因此走到了递归边界，直接返回一个1（即1！），不再进行递归调用。当这次函数调用结束后，其栈帧就会被释放，如图4（e）所示；随后控制流返回到程序的第11行，计算2！并返回此结果。当fact（2）执行完后，其栈帧被释放，如图4（f）所示，随后控制流返回到fact（3），计算3！并将结果返回到main函数。
通过上述分析可知，对于递归函数必须设定递归边界，即在何种情形下递归调用结束，不允许无限次的递归调用。否则，由于每一次函数调用都要在栈中分配一块栈帧，而栈的大小有限，这样，在递归调用了一定的次数后，栈空间就满了，就无法再进行递归调用。
2 堆（heap）
在进程的地址空间中，除了栈以外，还有一块内存空间是堆，它主要用于动态分配。所谓动态分配，即在程序运行时分配的内存空间。C语言可以通过malloc函数申请动态内存空间，其用法为“void *malloc（size_t size）；”。其中，size表示申请的字节数，如果申请成功，则返回相应内存空间的起始地址，否则返回一个常量NULL。
堆和栈是两块相对独立的内存空间，如前所述，在调用一个函数时，栈中会分配一块栈帧，用于存放该函数的形参和局部变量；然后在函数调用结束后，该栈帧就会被释放，而那些形参和局部变量就无法再访问，但是对于动态申请的堆空间来说，系统不会自动释放，因此在函数调用结束以后，该部分空间依然存在，还可以继续访问。
void main（ ）
{
int a[5] = {1， -1， 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）
{
int i， *c;
c =（int*）malloc（5*sizeof（int））;
if（c == NULL） return（NULL）;
for（i = 0; i < num; i++）
c[i] = a[i] + b[i];
return c;
}
对于上面这个程序，其在main函数中定义了两个数组a和b，然后调用Add函数将这两个数组的相应元素相加，结果保存在一个动态数组中并将其起始地址返回给main函数，然后在main函数中再访问这个动态数组。在该程序中，如果将Add函数中的动态数组修改为静态数组，即将语句“c =（int*）malloc（5*sizeof（int））；”修改为“int c[5]；”，则该程序就是错误的，打印的结果将会出现异常。原因在于当Add函数运行结束后，其栈帧会被释放，其内部的形参和局部变量都无法再访问；而如果是动态数组，其空间是位于堆而非栈当中，因此当Add函数运行结束后该空间依然存在，程序在返回到main函数后该数组仍然可以正常访问。
对于malloc申请的动态空间，系统会予以保留，不会主动释放。如果该空间使用完毕，程序员必须自己使用free函数进行释放，即malloc函数与free函数要配对使用，申请了多大的空间就必须释放多大的空间。如果程序设计得不够完善，就可能出现内存泄露的情形。所谓内存泄露，即分配出去的内存无法回收回来。内存泄漏的后果比较严重，随着程序的不断运行，内存越来越少，最后用malloc函数就申请不到存储空间。当然，这里所说的内存泄漏不是指物理内存的泄漏，而是指进程的逻辑地址空间，因此并不会影响到系统中的其他进程，而当一个进程运行完成后，它的整个地址空间都会被释放。
void main（ ）
{
char *p;
int size = 0;
while（1）
{
p = （char *）malloc（1024*1024）;
if（p == NULL） break;
else
{
printf（“%dM\n”，++size）;
}
}
}
以上这段程序就是用来测试内存泄露。它每次只申请空间而不释放空间，从而导致内存泄露，最终，当内存空间不够时，malloc函数就无法再申请成功，从而返回一个NULL。
3 结 语
在C语言程序设计课程的讲授中，大部分的语法知识点都较为简单，学生理解起来也不困难，但堆和栈是例外，它们是C程序设计中的两个重要概念，由于涉及操作系统等其他课程的内容，因此具有一定的难度，学生不容易理解。如何讲好这部分内容，值得教师认真思考。笔者通过一些编程案例，详细阐释了栈与堆的基本原理以及在程序运行过程中的应用，尤其是对于函数的递归调用，学生经常无法理解；描述了在递归函数调用过程中控制流和数据流的变化过程，清晰地阐述了递归调用的原理。在未来的工作中，我们将进一步完善相关的工作，用更加形象、直观的方式阐述栈和堆的基本原理。
（编辑：宋文婷）