系统内存分配的首次适应算法和最佳适应算法链表模拟实现

本文主要是介绍系统内存分配的首次适应算法和最佳适应算法链表模拟实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include<iostream>
#include<stdlib.h>
using namespace std;

#define Free 0 //空闲状态
#define Busy 1 //已用状态
#define OK 1 //完成
#define ERROR 0 //出错
#define MAX_length 640 //最大内存空间为640KB
typedef int Status;

typedef struct freearea//定义一个空闲区说明表结构
{
int ID; //分区号
long size; //分区大小
long address; //分区地址
int state; //状态
}ElemType;

//---------- 线性表的双向链表存储结构 ------------
typedef struct DuLNode //double linked list
{
ElemType data;
struct DuLNode *prior; //前趋指针
struct DuLNode *next; //后继指针
}DuLNode, *DuLinkList;

DuLinkList block_first; //头结点
DuLinkList block_last; //尾结点

Status alloc(int);//内存分配
Status free(int); //内存回收
Status First_fit(int, int);//首次适应算法
Status Best_fit(int, int); //最佳适应算法
void show();//查看分配
Status Initblock();//开创空间表

Status Initblock()//开创带头结点的内存空间链表
{
block_first = (DuLinkList)malloc(sizeof(DuLNode));
block_last = (DuLinkList)malloc(sizeof(DuLNode));
block_first->prior = NULL;
block_first->next = block_last;
block_first->data.state = 3;
block_first->data.size = 0;
block_last->prior = block_first;
block_last->next = NULL;
block_last->data.address = 0;
block_last->data.size = MAX_length;
block_last->data.ID = 0;
block_last->data.state = Free;
return OK;
}

//----------------------- 分配主存 -------------------------
Status alloc(int ch)
{
int ID, request;
cout << "请输入作业(分区号（整数）)：";
cin >> ID;
cout << "请输入需要分配的主存大小(单位:KB)：";
cin >> request;
if (request<0 || request == 0)
{
cout << "分配大小不合适，请重试！" << endl;
return ERROR;
}

if (ch == 2) //选择最佳适应算法
{
if (Best_fit(ID, request) == OK) cout << "分配成功！" << endl;
else cout << "内存不足，分配失败！" << endl;
return OK;
}
else //默认首次适应算法
{
if (First_fit(ID, request) == OK) cout << "分配成功！" << endl;
else cout << "内存不足，分配失败！" << endl;
return OK;
}
}
//------------------ 首次适应算法 -----------------------
Status First_fit(int ID, int request)//传入作业名及申请量
{
DuLNode *p = block_first->next;
//请在此处添加为作业申请新空间且初始化的代码
//请在此处完成首次适应算法的代码，分两种情况：有大小恰好合适的空闲块和有空闲块能满足需求且有剩余。
//注意函数返回值。
DuLinkList block = (DuLinkList)malloc(sizeof(DuLNode));
memset(block, 0, sizeof(DuLNode));
block->data.ID = ID;
block->data.size = request;
block->data.state = Busy;
while (p)
{
if (p->data.state == Free && p->data.size >= request)
{
if ((p->data.size - request) > 1)
{

block->data.address = p->data.address;
p->data.address = p->data.address + request;
p->data.size = p->data.size - request;

p->prior->next = block;
block->next = p;
block->prior = p->prior;
p->prior = block;
return OK;
}
else
{
p->data.ID = ID;
p->data.state = Busy;
free(block);
return OK;
}
}
p = p->next;
}
free(block);
return ERROR;
}
//-------------------- 最佳适应算法 ------------------------
Status Best_fit(int ID, int request)
{
//请在此处添加为作业申请新空间且初始化的代码
DuLinkList block = (DuLinkList)malloc(sizeof(DuLNode));
memset(block, 0, sizeof(DuLNode));
block->data.ID = ID;
block->data.size = request;
block->data.state = Busy;
DuLNode *p = block_first->next;
DuLNode *q = NULL; //记录最佳插入位置
int i = 0;
int num = 0;
DuLNode *q1 = NULL;

while (p)
{

if (p->data.state == Free && p->data.size >= request)
{
if (num == 0)
{
q = p;
i = q->data.size - request;

}
else if (p->data.size - request < i)
{
q = p;
i = q->data.size - request;
}
num++;

}

p = p->next;
}

//请在此处完成最佳适应算法的代码，重点：要查找到最小剩余空间的分区，即最佳插入位置

if (q == NULL) return ERROR;//没有找到空闲块
else
{
//请插入找到了最佳位置并实现内存分配的代码！
if ((q->data.size - request) > 1)
{

block->data.address = q->data.address;
q->data.address = q->data.address + request;
q->data.size = q->data.size - request;

block->next = q;
block->prior = q->prior;
q->prior->next = block;
q->prior = block;
return OK;
}
else
{
q->data.ID = ID;
q->data.state = Busy;
free(block);
return OK;
}
}
}

//----------------------- 主存回收 --------------------
Status free(int ID)
{
DuLNode *p = block_first->next;
DuLNode *p1 = NULL;
while (p)
{
if (p->data.ID == ID)
{
p->data.state = Free;
p->data.ID = Free;
cout << "内存块找到，准备回收！" << endl;
if (p->next == NULL){
if ((p->prior->data.state == Free) && (p->prior->data.address + p->prior->data.size == p->data.address))
{
p->prior->data.size += p->data.size;
p->prior->next = NULL;
free(p);
}
cout << "内存块为最后一块！" << endl;
break;
}
//请在此处添加其他情况的回收的代码，主要包括要回收的分区与前面的空闲块相连或与后面的空闲块相连，或者与前后空闲块相连等。
if ((p->next->next == NULL) && (p->next->data.state == Free) && (p->data.address + p->data.size == p->next->data.address))
{
p->data.size += p->next->data.size;
free(p->next);
p->next = NULL;
if ((p->prior->data.state == Free) && (p->prior->data.address + p->prior->data.size == p->data.address))
{
p->prior->data.size += p->data.size;
p->prior->next = NULL;
free(p);

}
break;

}
else if ((p->prior->data.state == Free)&&(p->prior->data.address+p->prior->data.size == p->data.address))
{

if ( p->next->data.state == Free && (p->data.address + p->data.size == p->next->data.address))
{
p1 = p->next;
p->data.size += p->next->data.size;
p->next->next->prior = p;

p->next = p->next->next;
free(p1);

}
p->prior->data.size += p->data.size;
p->prior->next = p->next;
p->next->prior = p->prior;
free(p);
break;
}
else if ((p->next->data.state == Free) && (p->data.address + p->data.size == p->next->data.address))
{
p1 = p->next;
p->data.size += p->next->data.size;
p->next = p->next->next;
p->next->prior = p;
free(p1);
break;
}
break;
}
p = p->next;
}
cout << "回收成功！" << endl;
return OK;
}

//--------------- 显示主存分配情况 ------------------
void show()
{
cout << "+++++++++++++++++++++++++++++++++++++++\n";
cout << "+++ 主存分配情况 +++\n";
cout << "+++++++++++++++++++++++++++++++++++++++\n";
DuLNode *p = block_first->next;
while (p)
{
cout << "分区号：";
if (p->data.ID == Free) cout << "Free" << endl;
else cout << p->data.ID << endl;
cout << "起始地址：" << p->data.address << endl;
cout << "分区大小：" << p->data.size << " KB" << endl;
cout << "状态：";
if (p->data.state == Free) cout << "空闲" << endl;
else cout << "已分配" << endl;
cout << "——————————————" << endl;
p = p->next;
}
}

//----------------------- 主函数---------------------------
void main()
{
int ch;//算法选择标记
cout << " 动态分区分配方式的模拟 \n";
cout << "************************************\n";
cout << "** 1)首次适应算法 2)最佳适应算法 **\n";
cout << "************************************\n";
cout << "请选择分配算法：";
cin >> ch;
Initblock(); //开创空间表
int choice; //操作选择标记
while (1)
{
cout << "********************************************\n";
cout << "** 1: 分配内存 2: 回收内存 **\n";
cout << "** 3: 查看分配 0: 退出 **\n";
cout << "********************************************\n";
cout << "请输入您的操作：";
cin >> choice;
if (choice == 1) alloc(ch); // 分配内存
else if (choice == 2) // 内存回收
{
int ID;
cout << "请输入您要释放的分区号：";
cin >> ID;
free(ID);
}
else if (choice == 3) show();//显示主存
else if (choice == 0) break; //退出
else //输入操作有误
{
cout << "输入有误，请重试！" << endl;
continue;
}
}
}