C语言数据结构----栈与递归

本节主要说程序中的栈函数栈的关系以及栈和递归算法的关系。

一、函数调用时的栈

1.程序调用时的栈是也就是平时所说的函数栈是数据结构的一种应用,函数调用栈一般是从搞地质向低地址增长的,栈顶为内存的低地址,栈底为内存的高地址。函数调用栈中存储的是数据的活动记录。活动记录是函数一些信息。如下如所所示:

C语言数据结构----栈与递归

2.假如有如下程序:

#include <stdio.h>
#include <stdlib.h> void fun(char* a)
{
char* b;
strcpy(b,a);
}
int main()
{
char a = '1';
fun(&a);
return 0;
}

那么在函数调用的过程中,函数栈的活动记录如下所示:

C语言数据结构----栈与递归

3.程序中的栈可以看做是顺序栈的一个应用,栈中保存了一个函数调用所需要的维护信息,包括函数参数,函数返回值地址,局部变量,函数调用上下文等。

4.具体的函数中的栈的实现请看另一篇博文:http://blog.csdn.net/cheyuxuan/article/details/9722463

二、程序中的栈

1.前一阶段在某实训机构做了一个所谓的项目时候,里面使用到了一个冒泡排序,但是排序的数据量很大,大约有6万个,程序的复杂度是O(n2),在程序运行一会后就会自动跳出,后来经过问大牛才知道这是因为栈溢出的原因。
2.程序在运行过程中,函数都是要被压入栈中的, 所以我们不断的调用函数,那么就会导致栈空间溢出,程序直接死掉。

3.造成栈溢出的原因通常有如下两点:①递归过深②局部数组过大,因为每一次递归都要调用函数,都要进行压栈的操作,所以这样会导致栈溢出,同时,如果我们定义的局部数组过大,数组也是在栈上分配空间的,那么也会造成栈上的空间不足,造成栈溢出。

三、程序中的栈的应用----递归调用

1.递归的算法是任何一门语言的基本功,但是理解起来其实也比较困难,这节先不说递归调用算法的实现,先来说一下递归和栈的关系。

2.例程:

#include <stdio.h>

void reverse(char* s)
{
if( (s != NULL) && (*s != '\0') )
{
reverse(s + 1); printf("%c", *s);
}
} int main()
{
reverse("12345"); printf("\n"); return 0;
}

程序打印的结果如下:

C语言数据结构----栈与递归

从程序大打印结果我们可以看出,我们实现了字符串"12345",最关键的是我们并没有使用我们惯用的for和count的方法。

解析:

我们从主函数调用reverse函数,向reverse函数传递的参数是字符串"12345"的首地址,然后进入子函数reverse,进行两个安全性的检测以后,我们再次调用reverse这个函数,这个时候向这个函数传递的是字符串"12345"的第二个元素的地址,依次类推,最后我们向reverse函数传递的是最后一个字符串的地址,这个时候程序中的栈被经历了5次reverse函数的压入,在第五次运行结束以后,栈中的值依次弹出,首先弹出的是第五个元素,然后以此类推。最后打印出我们上面的打印结果。

具体过程如下图所示:

C语言数据结构----栈与递归

程序在递归调用期间不断的向栈中压入每一次函数调用的记录,在递归调用结束后再从栈栈弹出每一次的记录,所以就打印出了我们看到的值。

四、总结

1.程序栈空间在本质上是一种顺序栈。

2.程序栈空间的访问是通过函数调用执行的。

3.程序栈空间仍然遵守后进先出的原则。

5.问题:①某实训机构的老师说程序的栈空间时从两侧增长的,我没有想懂,首先那那违背了栈的存储结构,其次同学早上和我说实际上栈的调度是CPU在控制的。

②程序中的栈空间,数据结构中的栈,还有真正的汇编硬件中的栈那个关系还需要深度学习,现在心里大概懂一点,但是无法形成一个整体的脉络。

上一篇:bzoj4873(最大权闭合子图)


下一篇:oracle数据库rman备份与还原