最佳适应算法.c

主存空间的分配与回收．采用可变分区存储管理

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<string.h>
#define getpch(type) (type*)malloc(sizeof(type))
/*/#define NULL 0*/

struct table
{
    char name[10];
    char state;    /* D(分配) or N(空闲)*/
    int  size;    /*分区大小*/
    int  addr;  /*起始地址*/
    struct table *next;
    struct table *prev;
}*tab=NULL,*p;
typedef struct table TABLE;

UI()
{
	printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
    printf("                 最佳适应算法                               \n");
    printf("                                                            \n");
    printf("  网络工程4班        罗志恒          3104007319             \n");
    printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
}
recycle(char n[10])
{
	TABLE *pr=NULL;
	for(pr=tab;pr!=NULL;pr=pr->next)
	{
		if(!strcmp(pr->name,n)&&pr->state=='D')
		{
			if(pr->prev!=NULL&&pr->prev->state=='N')       /*回收区的前一分区空闲*/
			{
				if(pr->next->state=='N')   /*回收区的前后分区都空闲*/
				{
					pr->state='N';
					pr->prev->size+=(pr->size+pr->next->size);     /*合并分区大小*/
					pr->prev->next=pr->next->next;      /*删除回收分区及其后一空闲分区表项*/
					pr->next->next->prev=pr->prev;
					return 0;
				}/*if*/
				else 
				{
					pr->state='N';
					pr->prev->size+=pr->size;
					pr->next->prev=pr->prev;
					pr->prev->next=pr->next;
					return 0;
				}/*else*/
			}/*if*/
			else if(pr->next!=NULL&&pr->next->state=='N')
			{
				pr->state='N';
				pr->size+=pr->next->size;
				if(pr->next->next!=NULL)
				{					
					pr->next->next->prev=pr;
					pr->next=pr->next->next;
				}
				else pr->next=NULL;
				return 0;
			}/* else if */
		}/*if*/
	}/*for*/
	if(pr==NULL) printf("错误!此分区不存在或未分配作业或前后分区都不空闲!\n");
    else printf("分区%s回收完毕!\n",pr->name);
	return 0;
}/*recycle*/
display()
{
    TABLE *pt=tab;
    if(pt==NULL) return 0;
    printf("---------空闲分区情况---------\n");
    printf("ID\t状态\t大小\t起始地址\n");
    while(pt!=NULL)
    {
        printf("%2s\t%3c\t%3d\t%5d\n",pt->name,pt->state,pt->size,pt->addr);
        pt=pt->next;
    }
    return 0;
}/*disptable*/

sort() 
{
    TABLE *first, *second;
    if(tab==NULL||p->size<tab->size)
    {
        p->next=tab;
        tab=p;
    }
    else
    {
       first=tab;
       second=first->next;
       while(second!=NULL)
          {
             if(p->size>=second->size)
             {
                first=first->next;
                second=second->next;
             }
             else
                break;
          }
        p->next=first->next;
        first->next=p;
    }
}
allocate(int s)
{
	TABLE *pt=NULL,*q;
	for(pt=tab;pt!=NULL;pt=pt->next)
	{
		if(pt->size>=s&&pt->state=='N')
		{
			pt->state='D';			
			if(pt->size>s)
			{
				q=getpch(TABLE);
				printf("请输入分割出的分区ID:\n");
			    scanf("%s",q->name);
				q->size=pt->size-s;         /*分割分区*/
				pt->size-=q->size;
				q->state='N';
				q->addr=pt->addr+pt->size;
				if(pt->next!=NULL)
				{
					pt->next->prev=q;        //在空闲链中插入新的分区
					q->next=pt->next;
					pt->next=q;
					q->prev=pt;
					return 0;
				}
				pt->next=q;
				q->prev=pt;
				q->next=NULL;
			}			
			return 0;
		}/*if*/
	}/*for*/
	printf("没有合适的分区,此次分配失败!\n");
	return 0;
}/*allocate*/

InitTab()
{
    int num;
    int i,paddr=0; 
	TABLE *pn;     /*指向前一结点*/
    pn=NULL;
    printf("\t-------Initialize table-------\n\n");
    printf("请输入分区个数:\n");
    scanf("%d",&num);
    for(i=0;i<num;i++)
    {
        p=getpch(TABLE);
        printf("输入分区NO.%d的ID:\n",i);
        scanf("%s",p->name);
        p->state='N';
        printf("输入分区大小:\n");
        scanf("%d",&p->size);
        p->addr=paddr;
        paddr=p->addr+p->size;
        p->prev=pn;
        pn=p;
        p->next=NULL;
        sort();    /* 按分区起始地址排序*/
    }

}/*InitTab*/

main()
{
	int ch=1;
	int size;
	char name[10],c='y';
	UI();
    InitTab();
	system("cls");
	UI();
    display();
    getch();
	while(c!='n'&&c!='N')
	{
		system("cls");
		UI();
		printf("选择你要进行的操作\n1--分配作业\n2--回收分区\n0/其他--退出\n\n");
		scanf("%d",&ch);
		system("cls");
		switch(ch)
		{
		case 1: 
			UI();
			display();
			printf("请输入作业大小:\n");
			scanf("%d",&size);
			allocate(size);
			break;
		case 2:
			UI();
			display();
			printf("请输入待回收分区的ID:\n");
			scanf("%s",name);
			recycle(name);
			break;
		case 0:
		default : printf("程序运行完毕!退出程序!\n");exit(0);
		}
		display();
		printf("是否继续?y/n\n");
	    c=getch();
	}


}