最佳适应算法的C++编程
一.程序说明：
本程序在vc++6.0上运行通过，考虑到很多种情况.
（1）、我发现书上所说的当回收块与空闲块相连的那些情况，没有必要每种情况都写一个条件语句，然后用不同的语句来连接那些相连的内存块（这种做法见下面源程序中黑体字部分）。我使用的方法是在accept 时不考虑是否会和已存在的空闲块相连，直接将它回收，然后按照首地址大小排序，再利用link 函数将只要是相连的内存块都连起来。
（2）、当使用assign 函数分配空闲块时，如果空闲块正好被分完（即空闲块的SIZE=0）时打印输出的数据会是一组首地址和尾地址相等，而size=0的数据，这显然不符合逻辑，因为首地址等于尾地址时size=1，而不是零！所以我想到了两种办法让刚好被分配完的空闲块不输出，第一种办法（见以下注释部分的print()函数部分的函数）只是屏蔽掉了SIZE=0的数据，而它们还是存在，即没有被真正的消灭掉，只是仅仅没被打印出来，这种做法将产生一种致命的后果，当SIZE=0的数据项非常多时将占用很多系统资源，运行程序时可能会死机！第二种做法（即源程序中所使用的print 函数）才真正的将SIZE=0的数据项消灭掉。
（3）、程序中的accept 函数回收内存时，只要输入的想回收的内存块中有一个区域（哪怕是SIZE=1的一小块）已经存在于空闲内存块中时就会输出提示错误的信息，我认为这样不是很合理，accept函数应该能避开输入的想回收的内存块中的已经是空闲的区域而只对非空闲区域作回收工作，这个功能在我的程序没有实现。
二、源程序：
#include
#include
int k=4;
struct list
{
int num;
int adr;
int end;
int size; //初始化数据的结构体
}s[]={{1,1000,2999,2000},{2,500,799,300},{3,3500,3699,200},{4,4000,4499,500}};//初始化空闲分区
/*voidprint(structlist *p,intn)
{
int flag1=1;
int flag2=1;
int i,j=0;//print 函数作用输出结果
cout
for(i=0;i
{
if(p->size==0)
{
flag2=0;
j++;
continue;
}
else
flag2=1;
if(p->size!=0&&flag2!=0)
{
flag1=0;
cout
*//*}
}
if(flag1==1)//当所有的空闲块正好被分配完时
cout
cout
}*/
void print(structlist a[],intn)
{
int i;
cout
if(a[0].size==0)
{
for(i=0;i
{
a[i].adr=a[i+1].adr;
a[i].size=a[i+1].size;
a[i].end=a[i+1].end;
}
k=k-1;
}
if(k==0)
cout
for(i=0;i
cout
置:?cout
}
void link(structlist a[])
它们合并成一块*/
{
int i;
for(i=0;i
{
if(a[i].end==a[i+1].adr-1)/*当一块空闲内存的尾地址和下一块的首地址相连时，将
a[i].size=a[i].size+a[i+1].size;
a[i].end=a[i+1].end;
for(i=i+1;i
{
a[i].adr=a[i+1].adr;
a[i].size=a[i+1].size;
a[i].end=a[i+1].end;
}
k=k-1;
}
}
}
void order(structlist a[],intn)
地址大小排序
{
int i,j,adr,end,size;
for(i=1;i
{//order 函数将空闲内存块按空间块起始
for(adr=a[i].adr,size=a[i].size,end=a[i].end,j=i-1;j>=0&&adr
a[j+1].size=a[j].size;
a[j+1].adr=a[j].adr;
a[j+1].end=a[j].end;
}
a[j+1].adr=adr;
a[j+1].size=size;
a[j+1].end=end;
}
void sort(structlist a[],intn)
{
int i,j,size,adr,end;
for(i=1;i
{//sort 函数将空闲块按空间大小排序
for(size=a[i].size,adr=a[i].adr,end=a[i].end,j=i-1;j>=0&&size
a[j+1].size=a[j].size;
a[j+1].adr=a[j].adr;
a[j+1].end=a[j].end;
}
a[j+1].size=size;
a[j+1].adr=adr;
a[j+1].end=end;
}
}
void assign(structlist a[],intsize)
{
int i,flag=0;
for(i=0;i
if(size
{
flag=1;
a[i].adr=a[i].adr+size-1;
a[i].size=a[i].size-size;
sort(s,k);
print(s,k);
break;
}
if(flag==0)
{
cout
}
}
void accept(structlist a[],intfadd,int size)
间
{
int i,j,flag;
flag=0;
设置flag=1
for(i=0;i
{
for(j=a[i].adr;j
{
if(a[i].size==0)
break; //accept 函数用于回收内存空//当回收的内存不与其他已存在的内存空闲块相连的时候，//发现空闲块大小为空时跳出
if(j>=fadd&&j
内存时，提示错误。
{
cout
flag=1;
break;
}
}
if(flag==1)
}
/*if(((a[i].end+1)!=fadd)&&((fadd+size)==a[i+1].adr))//回
收区与插入点的后一个分区相连
{
a[i+1].size=a[i+1].size+size;
a[i+1].adr=fadd;
flag=0;
break;
}
if(i==0&&((fadd+size)==a[i].adr))//回收区与起始地址最小的空闲块相连{
a[i].adr=fadd;
a[i].size=a[i].size+size;
flag=0;
break;
}
if(((a[i].end+1)==fadd)&&((fadd+size)==a[i+1].adr))//回收的内存夹在两个空闲块之间
{
a[i].size=a[i].size+size+a[i+1].size;
a[i].end=a[i].adr+a[i].size-1;
for(i=i+1;i
{
a[i].adr=a[i+1].adr;
a[i].size=a[i+1].size;
a[i].end=a[i+1].end;
}
k=k-1;
flag=0;
}
}
if(flag==0)
{
a[k].num=k+1;
a[k].size=size;
a[k].adr=fadd;
a[k].end=fadd+size-1;
k=k+1;*/
cout
}
}
void main()
{
int size;
int fadd ;
int i=1;
cout
print(s,k);
cout
cout
sort(s,k);
print(s,k);
while(i)
{
cout
cout>i;
if(i==1)
{
cout
cin>>size;
assign(s,size);
}
else if(i==2)
{
cout>fadd;
cin>>size;
order(s,k);
accept(s,fadd,size);
order(s,k);
for(i=0;i
link(s);
sort(s,k);
print(s,k);
}
else if(i==3)
break;
else
cout
}
}