补全代码块中待补全的代码

Question

#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;
         }
     }  
 }

Answer 1

引自免费微信小程序：皆我百晓生

在提供的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;
}

这些代码段分别完成了首次适应、最佳适应和最坏适应算法中分配内存时对现有空闲分区的处理。现在代码应该可以正常工作了。记得在编译和运行之前检查其他可能存在的语法错误。如果你有其他问题或者需要进一步的帮助，请随时告诉我。