4
．解释堆和栈的区别。
| | 区别 | 栈 | 堆 |
| OS意义上的区别 | 从内存上讲 | 由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。 | 一般由程序员分配释放，若程序员不释放，程序结束时可能由OS回收 。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表. |
| 申请方式 | 由系统自动分配。 例如，声明在函数中一个局部变量 int b; 系统自动在栈中为b开辟空间 | 需要程序员自己申请，并指明大小，如c中malloc函数，c++中的new. |
| 申请后系统响应 | 只要栈的剩余空间大于所申请空间，系统将为程序提供内存，否则将报异常提示栈溢出。 | 较复杂些，需要OS有一个记录空闲内存地址的链表 |
| 申请大小 | 在Windows下,栈是向低地址扩展的数据结构，是一块连续的内存的区域。空间限制在2M以内。 | 堆是向高地址扩展的数据结构，是不连续的内存区域。受虚存限制，空间可以很大（32位机4G）。 |
| 申请效率 | 栈由系统自动分配，速度较快。但程序员是无法控制的。 | 堆是由new分配的内存，一般速度比较慢，而且容易产生内存碎片,不过用起来最方便. |
| 存储内容 | 在函数调用时，第一个进栈的是主函数中后的下一条指令（函数调用语句的下一条可执行语句）的地址，然后是函数的各个参数，在大多数的C编译器中，参数是由右往左入栈的，然后是函数中的局部变量。注意静态变量是不入栈的。 | 一般是在堆的头部用一个字节存放堆的大小。堆中的具体内容有程序员安排。 |
| 存取效率 | 较快 | 较慢 |
| 数据结构意义上的区别 | 定义 | 堆是个有意思的数据结构，从逻辑上讲，它是个完全二叉树。它的两个基本特点:
一是，堆为顺序存储结构实现的完全二叉树；
二是，此树局部有序。
特点一大家都明白，特点二却是在说，比如最大堆，它不象排序二叉树那样是完全有序的，对于每一棵子树（当然也包括树本身）的根，其值总是在左、右孩子结点中为最大的，而左、右孩子结点却不一定有序。 | 栈（Stack）是限定只能在表的一端进行插入和删除操作的线性表。在表中，允许插入和删除的一端称作"栈顶(top)"，不允许插入和删除的另一端称作"栈底(bottom)" 。 |
| 用途 | 堆的用途，当然很多了，大家最容易想到的，就是堆排序。 | 常用于系统中。 |
posted on 2006-09-07 18:14
创建更好的解决方案 阅读(1057)
评论(0) 编辑 收藏 引用