首次适应算法.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;
				}
				else {
					pr->state='N';
					pr->prev->size+=pr->size;
					pr->next->prev=pr->prev;
					pr->prev->next=pr->next;
					return 0;
				}
			}
			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;
			}
		}
	}
	if(pr==NULL) printf("错误!此分区不存在或未分配作业或前后分区都不空闲!\n");
    else printf("分区%s回收完毕!\n",pr->name);
	return 0;
}
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;
		}
	}/*for*/
	printf("没有合适的分区,此次分配失败!\n");
	return 0;
}
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;
}

sorttable(){            /*分区按升序排列*/
    TABLE *first, *second;
    if(tab==NULL){
        p->next=tab;
        tab=p;
    }
    else{
       first=tab;
       second=first->next;
       while(second!=NULL){
              first=first->next;
              second=second->next;
          }
       first->next=p;
    }
}

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;
        sorttable();    /* 按分区起始地址排序*/
    }

}

main(){	
	int ch=1;
	int size;
	char name[10],c='y';
	UI();
    InitTab();
	system("cls");
	UI();
    display();
    getch();
	system("cls");
	while(c!='n'&&c!='N'){ 
		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 :exit(0);
		}
		display();
		printf("是否继续?y/n\n");
	    c=getch();
		system("cls");
	}
}