#define OK 1 //完成 #define ERROR 0 //出错 typedef int Status;
typedef struct free_table//定义一个空闲区说明表结构 {
int num; //分区序号 long address; //起始地址 long length; //分区大小 int state; //分区状态 }ElemType;
typedef struct Node// 线性表的双向链表存储结构 {
ElemType data;
struct Node *prior; //前趋指针 struct Node *next; //后继指针 }Node,*LinkList; LinkList first; //头结点 LinkList end; //尾结点 int flag;//记录要删除的分区序号
Status Initblock()//开创带头结点的内存空间链表 {
first=(LinkList)malloc(sizeof(Node)); end=(LinkList)malloc(sizeof(Node)); first->prior=NULL; first->next=end; end->prior=first; end->next=NULL; end->=1; end->=40; end->=600; end->=0; return OK; }
void sort()//分区序号重新排序 {
Node *p=first->next,*q; q=p->next;
for(;p!=NULL;p=p->next) {
for(q=p->next;q;q=q->next) {
if(p->>=q-> {
q->+=1;
} } } }
//显示主存分配情况 void show()
{ int flag=0;//用来记录分区序号 Node *p=first; p->=0; p->=0; p->=40; p->=1; sort();
printf(\"\\n\\》主存空间分配情况《\\n\");
printf(\"**********************************************************\\n\\n\"); printf(\"分区序号\起始地址\分区大小\分区状态\\n\\n\"); while(p) {
printf(\"%d\\%d\\%d\ if(p->==0) printf(\"\\空闲\\n\\n\"); else printf(\"\\已分配\\n\\n\"); p=p->next; }
printf(\"**********************************************************\\n\\n\"); }
//首次适应算法
Status First_fit(int request) {
//为申请作业开辟新空间且初始化 Node *p=first->next;
LinkList temp=(LinkList)malloc(sizeof(Node)); temp->=request; temp->=1; p->=1; while(p) {
if((p->==0)&&(p->==request)) {//有大小恰好合适的空闲块 p->=1; return OK; break; }
else if((p->==0) && (p->>request)) {//有空闲块能满足需求且有剩余
temp->prior=p->prior; temp->next=p; temp->=p->; temp->=p->;
p->prior->next=temp; p->prior=temp; p->=temp->+temp->; p->=request; p->+=1; return OK; break; } p=p->next; }
return ERROR; }
//最佳适应算法
Status Best_fit(int request) {
int ch; //记录最小剩余空间 Node *p=first;
Node *q=NULL; //记录最佳插入位置
LinkList temp=(LinkList)malloc(sizeof(Node)); temp->=request; temp->=1; p->=1;
while(p) //初始化最小空间和最佳位置 {
if((p->==0) && (p->>=request) ) {
if(q==NULL) { q=p; ch=p->; }
else if(q-> > p-> { q=p; ch=p->; } }
p=p->next; }
if(q==NULL) return ERROR;//没有找到空闲块
else if(q->==request) {
q->=1; return OK; } else {
temp->prior=q->prior; temp->next=q; temp->=q->; temp->=q->; q->prior->next=temp; q->prior=temp; q->+=request; q->=ch; q->+=1; return OK; } return OK; }
//最差适应算法
Status Worst_fit(int request) {
int ch; //记录最大剩余空间 Node *p=first->next;
Node *q=NULL; //记录最佳插入位置
LinkList temp=(LinkList)malloc(sizeof(Node)); temp->=request; temp->=1; p->=1;
while(p) //初始化最大空间和最佳位置 {
if(p->==0 && (p->>=request) ) {
if(q==NULL) { q=p; ch=p->; }
else if(q-> < p-> { q=p; ch=p->; }
} p=p->next; }
if(q==NULL) return ERROR;//没有找到空闲块 else if(q->==request) { q->=1; return OK; } else {
temp->prior=q->prior; temp->next=q; temp->=q->; temp->=q->; q->prior->next=temp; q->prior=temp; q->+=request; q->=ch; q->+=1; return OK; } return OK; }
//分配主存
Status allocation(int a) {
int request;//申请内存大小
printf(\"请输入申请分配的主存大小(单位:KB):\"); scanf(\"%d\ if(request<0 ||request==0) {
printf(\"分配大小不合适，请重试！\"); return ERROR; } switch(a) {
case 1: //默认首次适应算法
if(First_fit(request)==OK) printf(\"\****分配成功！****\"); else printf(\"\****内存不足，分配失败！****\"); return OK;
break;
case 2: //选择最佳适应算法
if(Best_fit(request)==OK) printf(\"\****分配成功！****\");
else printf(\"\****内存不足，分配失败！****\"); return OK; break;
case 3: //选择最差适应算法
if(Worst_fit(request)==OK) printf(\"\****分配成功！****\"); else printf(\"\****内存不足，分配失败！****\"); return OK; } }
Status deal1(Node *p)//处理回收空间 {
Node *q=first;
for(;q!=NULL;q=q->next) {
if(q==p) {
if(q->prior->==0&&q->next->!=0)
{
q->prior->+=q->;
break;
q->prior->next=q->next; q->next->prior=q->prior; q=q->prior; q->=0; q->=flag-1;
}
if(q->prior->!=0&&q->next->==0) {
q->+=q->next->;
q->next=q->next->next; q->next->next->prior=q; q->=0; q->=flag;
} {
q->prior->+=q->;
if(q->prior->==0&&q->next->==0)
q->prior->next=q->next; q->next->prior=q->prior; q=q->prior; q->=0; q->=flag-1;
}
if(q->prior->!=0&&q->next->!=0)
{
q->=0;
}
} } return OK; }
Status deal2(Node *p)//处理回收空间 {
Node *q=first;
for(;q!=NULL;q=q->next) {
if(q==p) {
if(q->prior->==0&&q->next->!=0)
{
q->prior->+=q->;
q->prior->next=q->next; q->next->prior=q->prior; q=p->prior; q->=0; q->=flag-1;
}
if(q->prior->!=0&&q->next->==0) { q->=0;
} {
q->prior->+=q->;
if(q->prior->==0&&q->next->==0)
q->prior->next=q->next; q->next->prior=q->prior; q=q->prior; q->=0; q->=flag-1;
} {
q->=0;
}
if(q->prior->!=0&&q->next->!=0)
} } return OK; }
//主存回收
Status recovery(int flag) {
Node *p=first;
for(;p!=NULL;p=p->next) {
if(p->==flag)
{
if(p->prior==first) {
if(p->next!=end)//当前P指向的下一个不是最后一个时 {
if(p->next->==0) //与后面的空闲块相连 {
p->+=p->next->; p->next->next->prior=p; p->next=p->next->next; p->=0; p->=flag; }
printf(\"\****回收成功****\"); return OK; } //主函数
} else p->=0; }
if(p->next==end)//当前P指向的下一个是最后一个时 { }
}//结束if(p->prior==block_first)的情况 else if(p->prior!=first) {
if(p->next!=end) {
deal1(p); } else { deal2(p); }
}//结束if(p->prior!=block_first)的情况
p->=0;
}//结束if(p->==flag)的情况
void main() {
int i; //操作选择标记 int a;//算法选择标记
printf(\"**********************************************************\\n\"); printf(\"\\用以下三种方法实现主存空间的分配\\n\");
printf(\"\(1)首次适应算法\(2)最佳适应算法\(3)最差适应算法\\n\");
printf(\"**********************************************************\\n\"); printf(\"\\n\");
printf(\"请输入所使用的内存分配算法:\"); scanf(\"%d\ while(a<1||a>3) {
printf(\"输入错误，请重新输入所使用的内存分配算法:\\n\"); scanf(\"%d\ }
switch(a) {
case 1:printf(\"\\n\****使用首次适应算法：****\\n\");break;
case 2:printf(\"\\n\****使用最佳适应算法：****\\n\");break; case 3:printf(\"\\n\****使用最坏适应算法：****\\n\");break;
}
Initblock(); //开创空间表 while(1) {
show();
printf(\"\1: 分配内存\2: 回收内存\0: 退出\\n\"); printf(\"请输入您的操作：\"); scanf(\"%d\ if(i==1)
allocation(a); // 分配内存 else if(i==2) // 内存回收 {
printf(\"请输入您要释放的分区号：\"); scanf(\"%d\ recovery(flag); }
else if(i==0)
{ }
printf(\"\\n退出程序\\n\"); break; //退出
else //输入操作有误 {
printf(\"输入有误，请重试！\"); continue; } } }
八、执行结果和结果分析 初始化首次适应算法：
当作业1、2、3顺利分配内存空间后： 回收序号2里面的内存： 分配作业4：
回收序号3里面的内存（与上邻序号2相连了） 回收序号1里的内存（与下邻序号2相连了）
继续分配（会发现总是按顺序查找满足要求的第一个空闲块，一旦发现就会分配）：
