#include
#include
#define NULL 0
#define LEN1 sizeof(struct job)//作业大小
#define LEN2 sizeof(struct idle)//空闲区单元大小
#define LEN3 sizeof(struct allocate)//已分配区单元大小
int SPACE=100;//定义内存空间大小
int ORIGI=1;//定义内存起始地址
struct job//定义作业
{
int name;
int size;
int address;
};
struct idle//定义空闲区
{
int size;
int address;
struct idle next;
};
struct allocate//定义已分配区
{
int name;
int size;
int address;
struct allocate *next;
};
struct idle *creatidle(void)//建立空闲表
{
struct idle *head;
struct idle *p1;
p1=(struct idle)malloc(LEN2);
p1->size=SPACE;
p1->address=ORIGI;
p1->next=NULL;
head=p1;
return(head);
}
struct allocate creatallocate(void)//建立已分配表
{
struct allocate *head;
head=NULL;
return(head);
}
struct job *creatjob(void)//建立作业
{
struct job *p;
p=(struct job)malloc(LEN1);
printf("请输入要运行的作业的名称与大小:\n");
scanf("%d%d",&p->name,&p->size);
return(p);
}
struct idle *init1(struct idle *head,struct job *p)//首次适应算法分配内存
{
struct idle *p0,*p1;
struct job *a;
a=p;
p0=head;
p1=p0;
while(p0->next!=NULL&&p0->sizesize)
{
p0=p0->next;
}
if(p0->size>a->size)
{
p0->size=p0->size-a->size;
a->address=p0->address;
p0->address=p0->address+a->size;
}
else
{
printf("无法分配\n");
}
return(head);
}
struct idle *init2(struct idle *head,struct job *p)//最优
{
struct idle *p0,*p1;
struct job *a;
a=p;
p0=head;
if(p0==NULL)
{
printf("无法进行分配!\n");
}
while(p0->next!=NULL&&p0->sizesize)
{
p0=p0->next;
}
if(p0->size>a->size)
{
p1=p0;
p0=p0->next;
}
else
{
printf("无法分配!\n");
}
while(p0!=NULL)
{
if(p0->size>p1->size)
{
p0=p0->next;
}
else if((p0->sizesize)&&(p0->size>a->size))
{
p1=p0;
p0=p0->next;
}
}
p1->size=(p1->size)-(a->size);
a->address=p1->address;
p1->address=(p1->address)+(a->size);
return(head);
}
struct idle *init3(struct idle *head,struct job *p)//最差
{
struct idle *p0,*p1;
struct job *a;
a=p;
p0=head;
if(p0==NULL)
{
printf("无法进行分配!");
}
while(p0->next!=NULL&&p0->sizesize)
{
p0=p0->next;
}
if(p0->size>a->size)
{
p1=p0;
p0=p0->next;
}
else
{
printf("无法分配!\n");
}
while(p0!=NULL)
{
if(p0->size<p1->size)
{
p0=p0->next;
}
else if(p0->size>p1->size)
{
p1=p0;
p0=p0->next;
}
}
p1->size=(p1->size)-(a->size);
a->address=p1->address;
p1->address=(p1->address)+(a->size);
return(head);
}
struct allocate reallocate(struct allocate *head,struct job *p)//重置已分配表
{
struct allocate *p0,*p1,*p2;//*p3,*p4;
struct job *a;
//struct idle *b;
a=p;
p0=(struct allocate)malloc(LEN3);
p1=(struct allocate*)malloc(LEN3);
if(head==NULL)
{
p0->name=a->name;
p0->size=a->size;
p0->address=ORIGI;
p0->next=NULL;
head=p0;
}
Else
{
p1->name=a->name;
p1->size=a->size;
p1->address=a->address;
p2=head;
while(p2->next!=NULL)
{
p2=p2->next;
} p2->next=p1;
p1->next=NULL;
}
return(head);
}
struct allocate del(struct allocate *head,struct job *p)//删除指定的作业
{
struct job *p1;
struct allocate *p2,*p3;
p2=head;
p1=p;
while((p1->name!=p2->name)&&(p2->next!=NULL))
{
p3=p2;
p2=p2->next;
}
if(p1->name==p2->name)
{
if(p2==head)
head=p2->next;
else
p3->next=p2->next;
}
return(head);
}
struct job *delejob(struct allocate *head)
{
struct job *p1;
struct allocate *p2;
int num;
p1=(struct job)malloc(LEN1);
printf("请输入要删除的作业的名称\n");
scanf("%d",&num);
p2=head;
while((num!=p2->name)&&(p2->next!=NULL))
{
p2=p2->next;
}
if(num==p2->name)
{
p1->name=p2->name;
p1->size=p2->size;
p1->address=p2->address;
}
return(p1);
}
struct idle unite(struct job *p,struct idle *head)//合并相邻内存空间
{
struct idle *p1,*p2,*p3;
struct job *m;
m=p;
p1=head;
p3=(struct idle)malloc(LEN2);
while((p1->addressaddress)&&(p1->next!=NULL))
{
p2=p1;
p1=p1->next;
}
if(m->addressaddress)
{
if(head==p1)
{
p3->size=m->size;
p3->address=m->address;
if((p1->address-p3->address)==(p3->size))
{
p1->address=p3->address;
p1->size=p3->size+p1->size;
}
else
{
head=p3;
p3->next=p1;
}
}
else
{
p3->size=m->size;
p3->address=m->address;
if((p1->address-p3->address)==(p3->size))
{
p1->address=p3->address;
p1->size=p3->size+p1->size;
if((p3->address-p2->address)==(p2->size))
{
p2->size=p1->size+p2->size;
p2->next=p1->next;
}
else
{
p2->next=p1;
}
}
else
{
if((p3->address-p2->address)==(p2->size))
{
p2->size=p2->size+p3->size;
}
else
{
p3->next=p1;
p2->next=p3;
}
}
}
}
else
{
p3->size=m->size;
p3->address=m->address;
if((p3->address-p1->address)==(p1->size))
{
p1->size=p1->size+p3->size;
}
else
{
p1->next=p3;
p3->next=NULL;
}
}
return(head);
}
void print(struct idle *h1,struct allocate *h2)
{
struct idle *m1;
struct allocate *n1;
m1=h1;
n1=h2;
if(m1==NULL)
{
printf("空闲表为空!\n");
}
else
{
while(m1!=NULL)
{
printf("空闲单元地址为%d,其大小为%d\n",m1->address,m1->size);
m1=m1->next;
}
}
if(n1==NULL)
{
printf("已分配表为空!\n");
}
else
{
while(n1!=NULL)
{
printf("已分配单元地址为%d,其大小为%d,其名称为%d\n",n1->address,n1->size,n1->name);
n1=n1->next;
}
}
}
void FF(void)
{
struct idle *p1;
struct allocate *p2;
struct job *p,*q;
int y=1;
int n=0;
int a=1;
int c;
p1=creatidle();
p2=creatallocate();
printf("初始情况为:\n");
print(p1,p2);
while(a==y)
{
printf("请输入要进行的操作:1.建立作业 2.删除作业 3.结束操作\n");
scanf("%d",&c);
switch(c)
{
case 1:
p=creatjob();
p1=init1(p1,p);
p2=reallocate(p2,p);
print(p1,p2);break;
case 2:
q=delejob(p2);
p2=del(p2,q);
//p2=reallocate(p2,q);
p1=unite(q,p1);
print(p1,p2);break;
case 3:
y=0;break;
}
}
}
void BF(void)
{
struct idle *p1;
struct allocate *p2;
struct job *p,*q;
int y=1;
int n=0;
int a=1;
int c;
p1=creatidle();
p2=creatallocate();
printf("初始情况为:\n");
print(p1,p2);
while(a==y)
{
printf("请输入要进行的操作:1.建立作业 2.删除作业 3.结束操作\n");
scanf("%d",&c);
switch(c)
{
case 1:
p=creatjob();
p1=init2(p1,p);
p2=reallocate(p2,p);
print(p1,p2);break;
case 2:
q=delejob(p2);
p2=del(p2,q);
//p2=reallocate(p2,q);
p1=unite(q,p1);
print(p1,p2);break;
case 3:
y=0;break;
}
}
}
void WF(void)
{
struct idle *p1;
struct allocate *p2;
struct job *p,*q;
int y=1;
int n=0;
int a=1;
int c;
p1=creatidle();
p2=creatallocate();
printf("初始情况为:\n");
print(p1,p2);
while(a==y)
{
printf("请输入要进行的操作:1.建立作业 2.删除作业 3.结束操作\n");
scanf("%d",&c);
switch(c)
{
case 1:
p=creatjob();
p1=init3(p1,p);
p2=reallocate(p2,p);
print(p1,p2);break;
case 2:
q=delejob(p2);
p2=del(p2,q);
//p2=reallocate(p2,q);
p1=unite(q,p1);
print(p1,p2);break;
case 3:
y=0;break;
}
}
}
