最佳适应算法.cpp

首次（或最佳）适应分配算法设计主存分配和回收程序

#include <iostream.h>
#include <stdlib.h>
typedef struct LNode
{    int size;        //内存大小
    int state;   //0表示空闲，1表示已经装入作业
    char task_name;  //装入的作业名称
    struct LNode *next;
}LNode,*memoryspace;
void Init(memoryspace &L,int size); //初始化空间段
void choice(memoryspace &L);  //选择操作类型
void Add(memoryspace &L); //添加作业
void Display(const memoryspace L); //显示作业
void deltask(const memoryspace L); //删除作业
void setfree(memoryspace &L); //回收空闲空间
void main()
{
    memoryspace L=new LNode; //memoryspace
    int N;
    cout<<"初始多大空间,请输入一个整数:"<<endl;
    cin>>N;
    Init(L,N);    //初始化大小为1000的内存空间
    choice(L);    //进入操作
}
void Init(memoryspace &L,int size) //初始化空间段
{
    memoryspace p = new LNode;
    p->size = size;
    p->state = 0;
    p->task_name = 'n';
    p->next = NULL;
    L->next = p;
}
void setfree(memoryspace &L) //找出连续的空闲资源,回收空闲空间
{
    memoryspace p=L->next,q=p->next;
    while(p && q)
    {
        if(p->state == 0 && q->state == 0) //如果空间连续,则回收
        {
            p->size +=q->size;
            p->next = p->next->next;
            delete q;
            q=p->next;
        }
        else
        {
            p = q;
            q = q->next;
        }
    }
    cout<<"回收成功"<<endl;
}
void deltask(const memoryspace L) //删除作业
{
    char task_name;
    int flag=0;
    Display(L);
    cout<<"请输入需要回收的作业名称:";
    cin>>task_name;

    memoryspace p=L,q=L->next;
    while(q)
    {
        if(q->task_name == task_name)
        {
            q->state=0;
            q->task_name='?';
            flag=1;
            break;
        }
        else
        {
            p = q;
            q = q->next;  //找到要删除作业的下一个结点
        }
    }
    if(flag == 0)
        cout<<"删除作业不成功"<<endl;
    else
        cout<<"删除作业成功"<<endl;
}

void Display(const memoryspace L) //显示作业
{
    int count=1;
    memoryspace p = L->next;
    cout<<"结点号 作业 状态 大小"<<endl;
    while(p)
    {
        cout<<"结点"<<count<<"    "<<p->task_name<<"   ";
        cout<<p->state<<"   "<<p->size<<endl;
        p = p->next;
        count++;
    }
}

void Add(memoryspace &L) //添加作业
{
    int new_size;
    char new_name;
    memoryspace q=L,p = L->next;
    cout<<"请输入新任务的名称:";
    cin>>new_name;
    cout<<"请输入新任务的大小:";
    cin>>new_size;
    
    while(p) //查找空闲资源进行分配
    {
        if (new_size<=0)
        {
            cout<<endl<<"申请的空间不能小于1"<<endl;
            break;
        }
        if(p->state==0 && p->size >= new_size) 
        {   
        //****************************************************//
            memoryspace q = new LNode;
            q->size = p->size - new_size; 
            q->state = 0;
            q->task_name='?';
            q->next=NULL;
        //****************************************************//
            p->size = new_size;
            p->state = 1;
            p->task_name=new_name;
            q->next = p->next;
            p->next = q;
            break;  //分配完成便退出
        }
        else
        {
            p = p->next;  //移动到足够分配的空结点
        }
        if(!p)
        {
            cout<<"作业"<<new_name<<"内存分配不成功"<<endl;
            break;
        }
    }
    p = L->next;
    while(p) //删除大小为0的结点,当分配空间完时会出现0结点
    {
        if(p->size == 0)
        {
            q->next = q->next->next;
            delete p;
            p = q->next;
        }
        else 
        {
            q = p;
            p = p->next;
        }
    }
}
void choice(memoryspace &L)  //选择操作类型
    { 
      int choice;
      do
      {
        cout<<"0.退出本程序"<<endl;
        cout<<"1.添加新的作业"<<endl;
        cout<<"2.显示当前作业"<<endl;        
        cout<<"3.删除一条作业"<<endl;
        cout<<"4.回收空闲空间"<<endl;
        cout<<endl<<"输入你的选择:";
        cin>>choice;
        switch(choice)
        {
        case 0:
            exit(1);break;
        case 1:
            Add(L); break;
        case 2:
            Display(L); break;        
        case 3:
            deltask(L); break;
        case 4:
            setfree(L); break;
        default:
            cout<<"请输入正确的选择!"<<endl;
            break;
        }
        cout<<endl;
      }while(choice!=0 ||choice!=1 || choice !=2 || choice!=3 || choice!=4);
    }