#include <stdio.h>
#include <stdlib.h>
#define Free 0
#define Busy 1
#define OK 1
#define ERROR 0
#define MAX_length 640
typedef int Status;
int flag;
typedef struct freearea //空闲区域
{
long size; //大小
long address; //首地址
long state; //状态
}ElemType;
typedef struct DuLNode //空闲链表
{
ElemType data;
struct DuLNode *prior;
struct DuLNode *next;
}
DuLNode,*DuLinkList; //双向链表指针
DuLinkList block_first,block_last; //空闲链表头指针和尾指针
Status alloc(int); //分配存储空间选择函数
Status freed(int); //回收存储空间
Status First_fit(int); //首次适应
Status Best_fit(int); //最佳适应
Status Worst_fit(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_last->prior=block_first;
block_last->next=NULL;
block_last->data.address=0; //空闲分区起始地址为0
block_last->data.size=MAX_length; //空闲分区大小(初始为整个可分配内存空间)
block_last->data.state=Free; //区域状态为空闲
return OK;
}
/*分配内存函数调用
参数:ch 表示选择的分配算法 2为最佳,3为最坏,其余为首次
*/
Status alloc(int ch)
{
int request = 0; //申请分配内存大小
printf("请输入需要分配的主存大小(单位:KB):");
scanf("%d",&request);
if(request<0 || request==0)
{
printf("分配大小不合适,请重试!\n");
return ERROR;
}
if(ch==2)
{
if(Best_fit(request)==OK) printf("分配成功!\n");
else printf("内存不足,分配失败!\n");
return OK;
}
if(ch==3)
{
if(Worst_fit(request)==OK) printf("分配成功!\n");
else printf("内存不足,分配失败!\n");
return OK;
}
else
{
if(First_fit(request)==OK) printf("分配成功!\n");
else printf("内存不足,分配失败!\n");
return OK;
}
}
/*首次适应算法
参数:request表示申请存储大小(KB)
*/
Status First_fit(int request)
{ //创建申请存储链表信息块
DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode));
temp->data.size=request;
temp->data.state=Busy;
//p为查找分配存储块
DuLNode *p=block_first->next;
DuLNode *q=NULL;
while(p)
{
if(p->data.state==Free && (p->data.size>=request))
{ //查找空闲分区
if(q==NULL)
q=p;
}
p=p->next;
}
if(q==NULL) return ERROR;
p=block_first->next;
while(p)
{
if(p->data.state==Free && p->data.size==request)
{
//待补全 当前存储块可分配
} else if(p->data.state==Free && p->data.size>request)
{
//待补全 分割当前存储块 (修改空闲链表,链入新空闲分区块)
}
p=p->next;
}
return OK;
}
/*最佳适应算法
参数:request表示申请存储大小(KB)
*/
Status Best_fit(int request)
{
DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode));
temp->data.size=request;
temp->data.state=Busy;
DuLNode *p=block_first->next;
DuLNode *q=NULL;
while(p)
{
if(p->data.state==Free && (p->data.size>=request))
{
//查找最小分区
if(q==NULL)
{ //待补全
}
else if(q->data.size > p->data.size)
{
//待补全
}
}
p=p->next;
}
if(q==NULL) return ERROR;
else if(q->data.size==request)
{
//待补全 如果当前空闲块等于申请大小直接分配
return OK;
} else
{
//待补全 如果空闲块大于申请大小分割当前块,添加分配项
return OK;
}
}
/*最坏适应算法
参数:request表示申请存储大小(KB)
*/
Status Worst_fit(int request)
{
DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode));
temp->data.size=request;
temp->data.state=Busy;
DuLNode *p=block_first->next;
DuLNode *q=NULL;
while(p)
{
if(p->data.state==Free && (p->data.size>=request))
{ //查找最大空闲分区
if(q==NULL)
{
//待补全
}
else if(q->data.size < p->data.size)
{
//待补全
}
}
p=p->next;
}
if(q==NULL) return ERROR;
else if(q->data.size==request)
{
//待补全
return OK;
}
else
{
//待补全
return OK;
}
}
/* 回收存储空间
参数:flag为回收分区块号
*/
Status freed(int flag)
{
DuLNode *p=block_first->next,*q=NULL;
//查找回收分区块号
for(int i=0; i < flag; i++)
if(p!=NULL)
p=p->next;
else
return ERROR; //未找到回收分区号
//回收区域为空闲区域
if (p->data.state==Free)
{
printf("该块本为空闲\n");
return ERROR;
}
//释放存储区前后都为已分配区域
p->data.state=Free;
//释放的是最后一个分区
if(p==block_last)
{ //空闲区只有一个分区
if(p->prior==block_first)
{
p->data.state=Free;
}
else
{ //回收区域前为已分配区域
if(p->prior->data.state==Busy)
{
p->data.state=Free;
}
else //回收区域前为空闲区域
{
p->prior->data.size+=p->data.size;
p->prior->next=p->next;
p->next->prior=p->prior;
p=p->prior;
}
}
return OK;
}
//释放的是不是第1块内存且其前面的内存为空闲
if(p->prior!=block_first && p->prior->data.state==Free)
{
p->prior->data.size+=p->data.size;
p->prior->next=p->next;
p->next->prior=p->prior;
p=p->prior;
//后面内存是否也为空闲
if(p->next->data.state==Free) {
q=p->next;
p->data.size+=q->data.size;
p->next=q->next;
free(q);
}
return OK;
}
//释放内存为中间块且其后存储块空闲
if(p->next!=block_last && p->next->data.state==Free)
{
p->data.size+=p->next->data.size;
p->next->next->prior=p;
p->next=p->next->next;
return OK;
}
//释放区域为倒数第2个区域
if(p->next==block_last && p->next->data.state==Free)
{
p->data.size+=p->next->data.size;
p->next=NULL;
return OK;
}
return OK;
}
/*显示内存分配情况*/
void show()
{
int flag=0;
printf("\n主存分配情况:\n");
printf("++++++++++++++++++++++++++++++++++++++++++\n\n");
DuLNode *p=block_first->next;
printf("分区号\t起始地址\t分区大小\t状态\n\n");
while(p)
{
printf(" %d\t",flag++);
printf(" %ld\t\t",p->data.address);
printf(" %ldKB\t\t", p->data.size);
if(p->data.state==Free) printf("空闲\n\n");
else printf("已分配\n\n");
p=p->next;
}
printf("++++++++++++++++++++++++++++++++++++++++++\n\n");
}
int main()
{
int ch;
printf("请输入所使用的内存分配算法:\n");
printf("(1)首次适应算法\n(2)最佳适应算法\n(3)最差适应算法\n");
scanf("%d",&ch);
while(ch<1||ch>3)
{
printf("输入错误,请重新输入所使用的内存分配算法:\n");
scanf("%d",&ch);
}
Initblock();
int choice;
while(1)
{
show();
printf("请输入您的操作:");
printf("1:分配内存\n2:回收内存\n0:退出\n");
scanf("%d",&choice);
if(choice==1)alloc(ch);
else if(choice==2)
{
int flag;
printf("请输入您要释放的分区号:");
scanf("%d",&flag);
freed(flag);
}
else if(choice==0) break;
else
{
printf("输入错误,请重试!\n");
continue;
}
}
}
补全代码块中待补全的代码
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
2条回答 默认 最新
关注 引自免费微信小程序:皆我百晓生
在提供的C语言代码中,我们正在实现一个简单的内存管理器,支持三种分配策略:首次适应、最佳适应和最坏适应。这里我会补充缺失的部分。首先,我们需要在
struct DuLNode
中增加一个指向前一块节点的指针,这样方便进行链表操作。typedef struct DuLNode { ElemType data; struct DuLNode *prior; // 前一个节点 struct DuLNode *next; // 后一个节点 };
接下来,我们逐个补充
First_fit()
、Best_fit()
和Worst_fit()
函数中的缺失部分。First_fit() 函数:
// 当前存储块可分配 if(p->data.state == Free && p->data.size == request) { p->data.state = Busy; return OK; } // 分割当前存储块 else if(p->data.state == Free && p->data.size > request) { DuLinkList new_block = (DuLinkList)malloc(sizeof(DuLNode)); new_block->data.size = request; new_block->data.state = Busy; new_block->address = p->data.address + request; p->data.size -= request; new_block->next = p->next; p->next->prior = new_block; p->next = new_block; new_block->prior = p; return OK; }
Best_fit() 函数:
// 查找最小分区 if(q == NULL || (p->data.state == Free && p->data.size < q->data.size)) { q = p; } // 分割当前存储块 else if(p->data.state == Free && p->data.size > request) { DuLinkList new_block = (DuLinkList)malloc(sizeof(DuLNode)); new_block->data.size = request; new_block->data.state = Busy; new_block->address = p->data.address + request; p->data.size -= request; new_block->next = p->next; p->next->prior = new_block; p->next = new_block; new_block->prior = p; q = new_block; }
Worst_fit() 函数:
// 查找最大空闲分区 if(q == NULL || (p->data.state == Free && p->data.size > q->data.size)) { q = p; } // 分割当前存储块 else if(p->data.state == Free && p->data.size > request) { DuLinkList new_block = (DuLinkList)malloc(sizeof(DuLNode)); new_block->data.size = request; new_block->data.state = Busy; new_block->address = p->data.address + request; p->data.size -= request; new_block->next = p->next; p->next->prior = new_block; p->next = new_block; new_block->prior = p; q = new_block; }
这些代码段分别完成了首次适应、最佳适应和最坏适应算法中分配内存时对现有空闲分区的处理。现在代码应该可以正常工作了。记得在编译和运行之前检查其他可能存在的语法错误。如果你有其他问题或者需要进一步的帮助,请随时告诉我。
解决 无用评论 打赏 举报 编辑记录
悬赏问题
- ¥15 JSzip压缩文件时如何设置解压缩密码
- ¥66 nuxtjs3 ,老是报错,内容:我有代码仓库,如何解决?
- ¥15 ocr识别纯数字会将数字翻转,并且会识别成字母
- ¥30 WPF如何实现动态Y轴
- ¥15 读取parquet文件某一列的数据但是输出是整个列名和格式
- ¥15 机动目标 制导律建模问题
- ¥100 求Java socks 转发实现Demo
- ¥20 随身WiFi移动网络访问不了
- ¥50 RAD_XE11.3获取android11手机的IMEI码
- ¥15 linux的gcc命令报错