c语言最佳适应算法结构体,操作系统——首次适应算法和最佳适应算法 实现（C++)...

算法结构体,操作系统——首次适应算法和最佳适应算法 实现（C++)..."/>

c语言最佳适应算法结构体,操作系统——首次适应算法和最佳适应算法 实现（C++)...

所谓动态分区分配 就是在处理作业的过程中，建立分区，依用户请求的大小分配分区。在分区回收的过程中会涉及一个空间利用效率相关的放置策略，即选择空闲区的策略。

常用的放置策略：

首次匹配(首次适应算法)

最佳匹配(最佳适应算法)

最坏匹配(最坏适应算法)

一、首次适应算法(First Fit)：该算法从空闲分区链首开始查找，直至找到一个能满足其大小要求的空闲分区为止。然后再按照作业的大小，从该分区中划出一块内存分配给请求者，余下的空闲分区仍留在空闲分区链    中。

特点： 该算法倾向于使用内存中低地址部分的空闲区，在高地址部分的空闲区很少被利用，从而保留了高地址部分的大空闲区。显然为以后到达的大作业分配大的内存空间创造了条件。

缺点：低地址部分不断被划分，留下许多难以利用、很小的空闲区，而每次查找又都从低地址部分开始，会增加查找的开销。

二、最佳适应算法(Best Fit)：该算法总是把既能满足要求，又是最小的空闲分区分配给作业。为了加速查找，该算法要求将所有的空闲区按其大小排序后，以递增顺序形成一个空白链。这样每次找到的第一个满足要求的空闲区，必然是最优的。孤立地看，该算法似乎是最优的，但事实上并不一定。因为每次分配后剩余的空间一定是最小的，在存储器中将留下许多难以利用的小空闲区。同时每次分配后必须重新排序，这也带来了一定的开销。

特点：每次分配给文件的都是最合适该文件大小的分区。

缺点：内存中留下许多难以利用的小的空闲区。

三、最坏适应算法(Worst Fit)：最坏适应算法是将输入的作业放置到主存中与它所需大小差距最大的空闲区中。空闲区大小由大到小排序。

特点：尽可能地利用存储器中大的空闲区。

缺点：绝大多数时候都会造成资源的严重浪费甚至是完全无法实现分配。

而在实现过程中，首次适应算法与最佳适应算法的区别在于：

首次适应算法中空闲区的排列顺序是按地址大小排列，小地址在前，大地址在后；而最佳适应算法中空闲区的队列排列是空闲区块的大小，小的在前，大的在后。

我在实现时用了一个结构体来存储空闲区的信息，然后再用双链表来实现空闲区队列(我本来是准备用单链表的，但是在遇到需要将空闲区块前插到链表中时不太方便，然后就换成双链表结果了)。

其次，空闲区合并问题有些许复杂，我一开始写了之后，运行发现出现上下两个都是空闲区时，程序并没有合并成功，而是只改变了空闲区块内的状态字，后来发现是条件的判断和退出出了问题。

具体操作详见代码：

#include using namespace std;

const int Max_length=640;//最大内存

int a, b;//a记录算法编号，b记录操作编号

struct freearea//空闲区的结构体

{

int ID;//分区号

int size;//分区大小

int address;//分区地址

bool flag;//使用状态，0为未占用，1为已占用

};

typedef struct DuNode//双向链表结点

{

freearea data;//数据域

DuNode *prior;//指针域

DuNode *next;

}*DuLinkList;

DuLinkList m_rid = new DuNode, m_last = new DuNode;//双向链表首尾指针

void init()//空闲区队列初始化

{

m_rid->