数据结构动态存储管理：Fdlf算法实现与分析

"严蔚敏 数据结构答案" 这段内容主要涉及数据结构中的动态存储管理，特别是内存分配和释放的算法。动态存储管理是计算机科学中一个重要的概念，它处理的是程序运行时内存的分配和回收，以确保有效利用内存资源。这里讨论了两种特定的算法：一种遵循“最后分配者最先释放”（First-Delivered-First-Served, FDLF）规则的内存分配算法，另一种则是与之对应的释放算法。 8.11 部分介绍了一个名为 Malloc_Fdlf 的内存分配函数。这个函数采用了FDLF策略，即最近分配出去的内存块在被释放后应优先考虑再次分配。函数首先检查栈S中的空闲块是否足够大以满足请求的内存大小。如果不够，就将这些小块移到栈T中，然后尝试从栈S中取出足够大的块。当找到合适的块时，它会分割出所需大小的内存并返回，剩余部分重新放入栈S。如果栈S为空，表示没有足够的空闲块，函数返回NULL。 8.12 部分给出了 Free_Fdlf，这是与 Malloc_Fdlf 相对应的内存释放函数。该函数在释放内存时，会检查释放的内存块是否能与其相邻的空闲块合并，以减少内存碎片。它通过遍历按地址排序的栈来找到合适的位置，并在找到相邻的空闲块时进行合并。最后，将合并或未合并的内存块插入到栈S中。 8.13 部分提到了在边界标识法（Boundary Tag Method）的动态存储管理系统中回收空闲块的函数 Free_BT。在这个方法中，每个内存块的边界都带有标记来指示其状态。函数 Free_BT 检查要回收的块是否能与前后块合并，如果可以，则进行合并操作，更新边界标记，并更新空闲块的信息。 这些算法都是为了提高内存管理的效率，减少内存碎片，并优化内存的使用。在实际的系统中，动态存储管理的实现可能更复杂，包括多种分配策略、内存碎片整理等技术。在学习数据结构时，理解这些基本的内存管理算法对于深入理解高级的内存管理机制，如虚拟内存、垃圾回收等至关重要。