僮飨低晨纬躺杓?最佳适应算法的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}}; // 初始化空闲分区
/*void print(struct list *p,int n) // print函数作用输出结果{ int flag1=1; int flag2=1; int i,j=0; cout<<"-------------------------------------\n"; for(i=0;i { if(p->size==0) // 控制不输出size=0的空闲块 { flag2=0; j++; continue; } else flag2=1; if(p->size!=0&&flag2!=0) { flag1=0; cout<<"序号:"
void link(struct list 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(struct list a[],int n) // order函数将空闲内存块按空间块起始地址大小排序{ int i,j,adr,end,size; for(i=1;i { 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(struct list a[],int n) // sort函数将空闲块按空间大小排序{ int i,j,size,adr,end; for(i=1;i { 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(struct list a[],int size){ int i,flag=0; for(i=0;i if(size<=a[i].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<<"\n没有合适的内存块可用！"< }}
void accept(struct list a[],int fadd,int size) // accept函数用于回收内存空间 { int i,j,flag; flag=0; // 当回收的内存不与其他已存在的内存空闲块相连的时候，设置flag=1 for(i=0;i { for(j=a[i].adr;j<=a[i].end;j++) { if(a[i].size==0) // 发现空闲块大小为空时跳出 break; if(j>=fadd&&j<=fadd+size-1)//当要回收的内存中有未用过的内存时，提示错误。 { cout<<"\n输入数据错误,回收内存块中有未使用的地址。\n\n"; flag=1; break; } } if(flag==1) break; } /* 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; break; } } */ 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<<"\n分配成功，新的内存块排列如下：\n"; } }
void main() { int size; int fadd ; // 回收区首地址 int i=1; // 选择操作的代码 cout<<"初始空闲内存块情况：\n"; print(s,k); cout< cout<<"初始空闲内存块排序（最佳适应算法）：\n"; sort(s,k); print(s,k); while(i) { cout<<"\n-------------------------------------\n选择操作：\n"; cout<<"1---分配,2---回收,3---退出\n"; cout<<"-------------------------------------\n"; cin>>i; if(i==1) { cout<<"\n分配内存块的操作，请输入需要分配的大小："; cin>>size; assign(s,size); } else if(i==2) { cout<<"\n回收内存块的操作，请输入首地址和大小："; cin>>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<<"错误的输入，请重新输入!\n"; }}
