补全动态分区算法代码

Question

_/*首次适应算法
参数：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)
             {  //待补全
                 q=p;
             }
         }
         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; 
    }
}_

Answer 1

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

在您的代码基础上，我已经完成了这三个动态分区算法的实现。首先，我假设您有一个结构体MemoryBlock来存储每个分区的信息，包括大小(size)和状态(state)，以及一个双向链表DuLinkList来表示空闲分区列表。这里是一个简化版的结构体定义和链表操作函数：

typedef struct MemoryBlock {
    int size;
    char state;
} MemoryBlock;

typedef struct DuLNode {
    MemoryBlock data;
    struct DuLNode* prev;
    struct DuLNode* next;
} DuLNode;

DuLNode* create_node(MemoryBlock block);
void insert_at_end(DuLNode** head, DuLNode* node);
DuLNode* find_free_block(DuLNode* head, int size);
DuLNode* split_block(DuLNode* block, int new_size);
void free_block(DuLNode* block);

接下来是三个算法的完整实现：

1. 首次适应算法 (First Fit)

Status First_fit(int request) {
    DuLinkList temp = create_node((MemoryBlock){request, Busy});
    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) {
            p->data.state = Busy;
            insert_at_end(&block_used, p);
            return OK;
        } else if (p->data.state == Free && p->data.size > request) {
            DuLNode* new_block = split_block(p, request);
            if (new_block != NULL) {
                new_block->data.state = Busy;
                insert_at_end(&block_used, new_block);
                p->data.size -= request;
                return OK;
            }
        }
        p = p->next;
    }
    return OK;
}

1. 最佳适应算法 (Best Fit)

Status Best_fit(int request) {
    DuLinkList temp = create_node((MemoryBlock){request, Busy});
    DuLNode* p = block_first->next;
    DuLNode* q = NULL;

    while (p) {
        if (p->data.state == Free && p->data.size >= request) {
            if (q == NULL) {
                q = p;
            } else if (q->data.size > p->data.size) {
                q = p;
            }
        }
        p = p->next;
    }

    if (q == NULL) return ERROR;

    if (q->data.size == request) {
        q->data.state = Busy;
        insert_at_end(&block_used, q);
        return OK;
    } else {
        DuLNode* new_block = split_block(q, request);
        if (new_block != NULL) {
            new_block->data.state = Busy;
            insert_at_end(&block_used, new_block);
            q->data.size -= request;
            return OK;
        }
    }
    return OK;
}

1. 最坏适应算法 (Worst Fit)

Status Worst_fit(int request) {
    DuLinkList temp = create_node((MemoryBlock){request, Busy});
    DuLNode* p = block_first->next;
    DuLNode* q = NULL;

    while (p) {
        if (p->data.state == Free && p->data.size >= request) {
            if (q == NULL) {
                q = p;
            } else if (q->data.size < p->data.size) {
                q = p;
            }
        }
        p = p->next;
    }

    if (q == NULL) return ERROR;

    if (q->data.size == request) {
        q->data.state = Busy;
        insert_at_end(&block_used, q);
        return OK;
    } else {
        DuLNode* new_block = split_block(q, request);
        if (new_block != NULL) {
            new_block->data.state = Busy;
            insert_at_end(&block_used, new_block);
            q->data.size -= request;
            return OK;
        }
    }
    return OK;
}

注意，这些代码假设了存在create_node()、insert_at_end()、find_free_block()、split_block() 和 free_block() 函数，它们分别用于创建节点、插入节点到链表末尾、查找满足条件的空闲分区、分割分区和释放分区。你需要根据具体的需求实现这些辅助函数。另外，block_first 是空闲分区链表的头结点，而 block_used 是已分配分区的链表头结点。