数据结构动态存储管理共29页

数据结构动态存储管理动态存储管理是计算机科学中一个重要的主题，它涉及到了如何有效地管理计算机内存的分配和释放。

在计算机程序中，为了存储数据和指令，计算机需要使用内存。

内存是计算机中最宝贵的资源之一，因此有效地管理内存是非常重要的。

本文将介绍几种常见的动态存储管理方法，包括分区分配、固定分区分配、动态分区分配和虚拟内存管理等。

首先，我们来介绍分区分配方法。

这种方法将内存划分为若干个固定大小的区域，每个区域只能分配给一个进程使用。

这种方法简单直接，但是会造成内存空间的浪费。

例如，一个进程可能只需要很小的内存空间，但是由于分区大小固定，它可能被分配一个较大的分区，导致其他进程无法得到足够的内存。

因此，分区分配方法适用于较小型的系统，对于大型系统来说不太适用。

接下来是固定分区分配方法。

这种方法将内存划分为若干个固定大小的区域，每个区域只能分配给一个进程使用。

不同于分区分配方法，固定分区分配方法中的分区大小可以根据不同的进程需求来设置。

这样可以减少内存空间的浪费，但是仍然存在固定分区大小可能不适应所有进程需求的问题。

然后是动态分区分配方法。

这种方法将内存划分为若干个不同大小的区域，每个区域可以根据需要分配给不同的进程使用。

与固定分区分配方法不同，动态分区分配方法中的分区大小可以根据进程需求动态调整。

当一个进程请求内存时，动态分区分配方法会根据可用内存的大小选择一个合适的分区来分配给该进程。

这样可以提高内存利用率，减少内存空间的浪费。

最后是虚拟内存管理方法。

虚拟内存是一种将物理内存和磁盘空间结合起来使用的技术。

虚拟内存管理方法将内存划分为若干个固定大小的页面或帧，并将磁盘空间划分为若干个固定大小的页面或块。

当一个进程请求内存时，虚拟内存管理方法会将页面从磁盘加载到内存中，并将多余的页面移出内存，存放在磁盘空间中。

这样可以实现多个进程共享物理内存，并且可以使得进程能够访问比物理内存更大的地址空间。

虚拟内存管理方法虽然复杂，但是可以提高内存利用率和系统的性能。

第6页/共118页
7.1.1自由存储区内存的分配与释放
动态分配数组的特点：
1. 变量n在编译时没有确定的值，而是在运行中输入，按运行 时所需分配空间，这一点是动态分配的优点，可克服数组 “大开小用”的弊端，在表、排序与查找中的算法，若用 动态数组，通用性更佳。delete [ ]pc是将n个字符的空间释 放，而用delete pc则只释放了一个字符的空间；
char *pName; //为了演示深复制，不用string类 public:
student(); //默认构造函数 student(char *pname); //带参数构造函数 student(student &s); //复制构造函数 ~student(); //析构函数 student & operator=(student &s); }; //复制赋值操作符
第12页/共118页
7.1.2自由存储区对象与构造函数
类对象初始化：
new后面类（class）类型可以有参数。这些参数即构造函数的 参数。但对创建数组，则无参数，只能调用默认的构造函数。
【例7.3】演示自由存储区对象分配和释放。
由自由存储区创建对象数组，只能调用默认 的构造函数，不能调用其他任何构造函数。如果 没有默认的构造函数，则不能创建对象数组。
第17页/共118页
7.1.3 浅复制与深复制
思考：
深入地考虑【例7.4】，如果数据域还有很多其他数 据，甚至有好几个是动态建立的C字符串，深复制是不是太 复杂了？如果使用C++标准字符串string作为成员对象（聚 合）是否就不需要考虑深复制了？ 的确是这样的，准确地说，string类的内部包含动态建立字 符数组的操作，其复制构造函数是深复制。如果在student 类中使用string类而不是C字符串，就不要再考虑深复制问 题了。也就是说，动态内存分配和深复制应该放在一个适当 的层面上，一个更单纯的类定义中，如string类。在使用中， 把它作为一个成员对象，就像使用string类对象那样。

第8章动态存储管理第8章动态存储结构8.1在伙伴系统中的伙伴是指任意两块大小相同、位置相邻的内存块。

这种说法对吗？【解答】不对。

只有同一内存块分裂的两块才互称伙伴。

8.2最佳适配法与最先适配法相比，前者容易增加闲置空间的碎片。

这种说法对吗？【解答】对。

8.3设内存中可利用空间已连成一个单链表，对用户的存储空间需求，一般有哪三种分配策略？【解答】首次拟合法；从链表头指针开始查找，找到第一个大于等于所需空间的结点即分配。

最佳拟合法：链表结点大小增序排列，找到第一个大于等于所需空间的结点即分配。

最差拟合法：链表结点大小逆序排列，总从第一个结点开始分配，将分配后结点所剩空间插入到链表适当位置。

首次拟合法适合事先不知道请求分配和释放信息的情况,分配时需查询,释放时插在表头。

最佳拟合法适用于请求分配内存大小范围较宽的系统,释放时容易产生存储量很小难以利用的内存碎片,同时保留那些很大的内存块以备将来可能发生的大内存量的需求，分配与回收均需查询。

最差拟合法适合请求分配内存大小范围较窄的系统,分配时不查询,回收时查询,以便插入适当位置。

8.4计算起始二进制地址为011011110000，长度为4（十进制）的块的伙伴地址是多少？【解答】0110111101008.5地址为（1664）10大小为（128）10的存储块的伙伴地址是什么？地址为（2816）10大小为（64）10的存储块的伙伴地址是什么？【解答】（1）buddy(1664,7)=1664-128=1536（2）buddy(2816,6)=2816+64=28808.6 试叙述动态存储分配伙伴系统的基本思想，它和边界标识法不同点是什么？【解答】动态存储分配伙伴系统的基本思想是：在伙伴系统中，无论占用块或空闲块，其大小均为2的k(k为≥0的正整数)次幂。

若内存容量为2m，则空闲块大小只能是20，21，22，…，2m。

由同一大块分裂而得的两个小块互称“伙伴空间”，如内存大小为210的块分裂成两个大小为29的块。

head
llink
tag
size
rlink
space
foot uplink tag
2. 分配算法： （采用首次拟合法） 约定（1）余量的处理 （2）PAV的移动 如图8.6所示。P200 算法描述： space allocboundtag(space *pav,int n) for(p=pav;p&&p->size<n &&p->rlink!=pav;p=p->link); if(!p|| p->size<n) return 0 else { f=footloc(p); pav=p->rlink; if(p->size-n<e) if(pav==p) pav=0
8.5 无用单收集 8.6 存储紧缩 略
else { pav->llink=p->link;p->llink->rlink=pav;} p->tag=f->tag=1;} else {f->tag=1; p->size-=n; f=footloc(p); f->tag=0,f->uplink=p; p=f+1; p->tag=1;p->size=n} return p }} 算法8.1
动态存储管理的基本问题：分配与回收 动态存储分配过程：
系统运行初期
系统运行一段时间后
分配处理：（1）从高地址空闲块中进行分配。 （2）在整个内存中找一合适的空闲块。
可利用空间表结构： （1）目录表 （2）链表
起始地址内存大小使用 Nhomakorabea况10，000 31，000 59，000
15，000 8，000 41，000