循环首次适应算法、首次适应算法、最佳适应算法 C语言版.doc

#include#define getpch(type) (type*)malloc(sizeof(type) struct LNode int size; int start; int end; struct LNode *next; struct LNode *front;*L; /*L为头指针*/typedef struct LNode LN;LN *find;int n;void InsertList(int size,int start)/ 在带头结点的单链线形表头结点后插入LN *p,*s,*t;p=L;t=p-next; s=getpch(LN); /生成新结点s-size=size;s-start=start;s-end=start + size ;s-next=t; /插入L中p-next=s;if(t) t-front=s;s-front=p;/end of InsertListvoid PrintList() /*打印*/LN *p; int i;p=L-next;printf(n空闲区号 长度 起始位置 终止位置n);for(i=1;isize, p-start,p-end);p=p-next;void BFSortList() /*最佳适应算法的排序*/ LN *p,*s,*t;int min_size,i;int size,start,end;t=L-next; p=L-next;for(i=0;inext;min_size = p-size;while(s)if(min_size s-size)min_size=s-size;t=s;s=s-next;size=t-size;start=t-start;end=t-end;t-size=p-size;t-start=p-start;t-end=p-end;p-size=size;p-start=start;p-end=end;t=p-next; p=p-next; / end of BF_SortListvoid SortList() /*首次和循环首次适应算法的排序*/LN *p,*s,*t;int min_start,i;int size,start,end;t=L-next; p=L-next;for(i=0;inext;min_start = p-start;while(s)if(min_start s-start)min_start=s-start;t=s;s=s-next;size=t-size;start=t-start;end=t-end;t-size=p-size;t-start=p-start;t-end=p-end;p-size=size;p-start=start;p-end=end;t=p-next; p=p-next; / end of BF_SortListvoid GetFree() /*生成空闲分区链*/int size,start,i; L=getpch(LN); /*生成一个表头结点*/L-next=NULL;L-front=NULL;printf(请输入空闲区数:);scanf(%d,&n);for(i=1;inext;t=L;while(p)if(size p-size)p=p-next;t=t-next;if(!p) printf(没有足够大的空闲区分配！分配不成功); elsep-size = p-size - size;p-start= p-start + size ;if(p-size=0)t-next = p-next ; p-next-front=t;n-;free(p);printf(分配成功！n);printf(分配后的空闲链表情况如下:n);PrintList();break;/ end of FF_Assignint flag=-1;void NF_Assign(int size)/*循环首次适应算法的分配*/LN *p,*t;int i=n;p=find-next;t=find;while(p)if(size p-size)p=p-next;t=t-next;if(!p) printf(没有足够大的空闲区分配！分配不成功); elsep-size = p-size - size;p-start= p-start + size ;find=p;if(p-size=0)t-next = p-next; p-next-front=t;n-;free(p);printf(分配成功！n); flag=1;printf(分配后的空闲链表情况如下：n);Print(L);break; if(flag=-1) p=L-next;t=L;while(p!=find)if(size p-size)p=p-next;t=t-next;if(!p) printf(没有足够大的空闲区分配！分配不成功); elsep-size = p-size - size;p-start= p-start + size ;find=t;if(p-size=0)t-next = p-next ; p-next-front=t;n-;free(p);printf(分配成功！n);printf(分配后的空闲链表情况如下：);PrintList(L);break; / end of NF_Assignvoid Recover(int start, int end) /*回收*/LN *p,*t;int size,flag=0;size=end-start;p=L-next;t=p-next; while(p) if(t & p-end=start & t-start=end)/回收区在两个空闲区中间p-size = p-size + size + t-size;p-end = t-end;p-next=t-next; t-next-front=p;free(t);n-;SortList(L);flag=1; break;else if(p-end = start)/回收区在空闲区下方 flag=1;p-size = p-size + size;p-end = p-end + size ;SortList(L); break;else if( p-start = end)/回收区在空闲区上方p-size= p-size +size;p-start=start;SortList(L);flag=1; break; p=p-next; if(p) t=p-next; /回收区不与任何一个空闲区相邻if(flag=0) InsertList(size,start); n+; printf(回收后的空闲链表情况如下:); PrintList(); printf(n按任意键继续); void main()int start,end,size;int m;GetFree();getch(); system(cls);/*清屏*/ printf(请选择服务类型:n); printf(t1:首次适应算法n); printf(t2:循环首次适应算法n); printf(t3:最佳适应算法n); printf(t4:回收内存n); printf(t0:退出n); printf(t输入您要的选项:); scanf(%d,&m); if(m=2) find=L; while(m) switch(m) case 1: SortList(); printf(n空闲链表情况:n); PrintList(); printf(请输入进程需要的空闲区大小:); scanf(%d,&size); Assign(size); printf(n按任意键继续); break; case 2: SortList(); printf(n空闲链表情况:n); PrintList(); printf(请输入进程需要的空闲区大小:); scanf(%d,&size); NF_Assign(size);printf(n按任意键继续); break; case 3: BFSortList(); printf(n空闲链表情况:n); PrintList(); printf(请输入进程需要的空闲区大小:); scanf(%d,&size); Assign(size);printf(n按任意键继续); break; case 4: printf(请输入回收区的首地址和中止地址:); scanf(%3d,%3d,&start,&end); Recover(start,end); break; case 0: exit(0); default : printf(ntt输入错误,请重新