|
<<同江职教网欢迎你---累了听会歌吧－－奥运主题歌 我和你>>
动态数据结构可以根据需要，从称之为堆的内存空间上分配和释放内存。动态数据结构在C程序中极其重要，因为通过动态数据结构，程序员能准确地控制内存消耗。
动态数据结构的内存，是根据需要从堆上成块分配的，这些内存块被指针链接成为某种数据结构。数据结构不再需要的内存块会被交还给堆，供别的程序重新使用。这种回收机制使内存的利用十分高效。
要彻底了解动态数据结构，我们需要从堆谈起。
堆
今天（译者注：本文成文于2000年）的个人电脑或工作站一般配备有16至64兆字节的RAM。系统通过使用虚拟内存技术将内存块和硬盘空间不断交换，从而为CPU制造假象使它认为有多得多的内存，如200至500兆字节。虽然CPU对此浑然不知，但是用户有时会察觉到处理速度的大幅下降。然而暇不掩瑜，虚拟内存是一项极有用的以廉价方式“扩充”计算机内存的技术。在本节的讨论中，我们不妨假设某个典型计算机的内存空间总大小是50兆字节（不论是使用真正的RAM还是虚拟内存）。
计算机的操作系统负责管理这50兆字节的内存空间。操作系统使用内存的方式有多种，如下所示：
操作系统和所有应用程序（包括它们的全局变量和栈空间）都需要占用部分内存。一个程序完成后会释放内存供其他程序使用。注意，任意时刻都有部分内存空间空闲。
|
当然图示的只是一种理想化的情况，但其基本原理是适用的。如您所见，内存存储了各种当前正在运行的应用程序的执行代码，也存储了操作系统自身的执行代码。每个应用程序都带有一些全局变量，它们也占用内存。最后，每个应用程序都要使用一块称为栈的内存区域。栈用于保存所有的局部变量和函数参数。栈还记录了函数调用的先后顺序，因此也可以保证函数按正确的顺序返回。当一个函数被调用的时候，其局部变量和参数被“压入”栈顶；函数返回时，这些局部变量和参数又被“弹出”。因此，在程序运行的时候，它的栈的大小一直是变化不定的，但是有一个上限。
程序完成时，操作系统会将它的代码、全局变量和栈空间从内存中卸载。以后的新程序就可以重用这些内存空间。这样，计算机系统中的内存就会因程序的执行和完成而不断被“回收”和重新使用。
一般说来，在任一时刻计算机大约有50%的内存空间是空闲的。空闲的内存由操作系统支配和管理，统称为堆。堆极其重要。通过在执行时调用C函数malloc（memory allocate，内存分配）和free，程序就可以使用堆了。这样，程序执行中的内存需求就可以准确地从堆上分配，而不必使用确定大小的数组声明预先分配好。
|
