首次适应算法和最佳适应算法-C++语言版.doc

#include#includeusing namespace std;#define Free 0 /空闲状态#define Busy 1 /已用状态#define OK 1 /完成#define ERROR 0 /出错#define MAX_length 512 /最大内存空间为512KBtypedef int Status;int flag;typedef struct freearea/定义一个空闲区说明表结构 long size; /分区大小 long address; /分区地址 int state; /状态ElemType;/ 线性表的双向链表存储结构typedef struct DuLNode ElemType data; struct DuLNode *prior; /前趋指针 struct DuLNode *next; /后继指针DuLNode,*DuLinkList;DuLinkList block_first; /头结点DuLinkList block_last; /尾结点Status alloc(int);/内存分配Status free(int); /内存回收Status First_fit(int);/首次适应算法Status Best_fit(int); /最佳适应算法void show();/查看分配Status Initblock();/开创空间表Status Initblock()/开创带头结点的内存空间链表 block_first=(DuLinkList)malloc(sizeof(DuLNode); block_last=(DuLinkList)malloc(sizeof(DuLNode); block_first-prior=NULL; block_first-next=block_last; block_last-prior=block_first; block_last-next=NULL; block_last-data.address=0; block_last-data.size=MAX_length; block_last-data.state=Free; return OK;/分配主存Status alloc(int ch) int request = 0; coutrequest; if(request0 |request=0) cout分配大小不合适，请重试！endl; return ERROR; if(ch=2) /选择最佳适应算法 if(Best_fit(request)=OK) cout分配成功！endl; else cout内存不足，分配失败！endl; return OK; else /默认首次适应算法 if(First_fit(request)=OK) cout分配成功！endl; else cout内存不足，分配失败！data.size=request; temp-data.state=Busy; DuLNode *p=block_first-next; while(p) if(p-data.state=Free & p-data.size=request) /有大小恰好合适的空闲块 p-data.state=Busy; return OK; break; if(p-data.state=Free & p-data.sizerequest) /有空闲块能满足需求且有剩余 temp-prior=p-prior; temp-next=p; temp-data.address=p-data.address; p-prior-next=temp; p-prior=temp; p-data.address=temp-data.address+temp-data.size; p-data.size-=request; return OK; break; p=p-next; return ERROR;/最佳适应算法Status Best_fit(int request) int ch; /记录最小剩余空间 DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode); temp-data.size=request; temp-data.state=Busy; DuLNode *p=block_first-next; DuLNode *q=NULL; /记录最佳插入位置 while(p) /初始化最小空间和最佳位置 if(p-data.state=Free & (p-data.size=request) ) if(q=NULL)q=p;ch=p-data.size-request;else if(q-data.size p-data.size)q=p;ch=p-data.size-request; p=p-next; if(q=NULL) return ERROR;/没有找到空闲块 else if(q-data.size=request) q-data.state=Busy; return OK; else temp-prior=q-prior; temp-next=q; temp-data.address=q-data.address; q-prior-next=temp; q-prior=temp; q-data.address+=request; q-data.size=ch; return OK; return OK;/主存回收Status free(int flag) DuLNode *p=block_first;for(int i= 0; i next;elsereturn ERROR;p-data.state=Free; if(p-prior!=block_first & p-prior-data.state=Free)/与前面的空闲块相连 p-prior-data.size+=p-data.size; p-prior-next=p-next; p-next-prior=p-prior;p=p-prior; if(p-next!=block_last & p-next-data.state=Free)/与后面的空闲块相连 p-data.size+=p-next-data.size; p-next-next-prior=p; p-next=p-next-next; if(p-next=block_last & p-next-data.state=Free)/与最后的空闲块相连 p-data.size+=p-next-data.size; p-next=NULL; return OK;/显示主存分配情况void show()int flag = 0; coutn主存分配情况:n; coutnext;cout分区号t起始地址t分区大小t状态nn; while(p) cout flag+t; cout data.addresstt; cout data.sizedata.state=Free) cout空闲nn; else coutnext; cout+nn;/主函数int main() int ch;/算法选择标记 cout请输入所使用的内存分配算法：n; coutch;while(ch2)coutch; Initblock(); /开创空间表 int choice; /操作选择标记 while(1) show();cout请输入您的操作：; coutchoice; if(choice=1) alloc(ch); / 申请内存 else if(choice=2) / 释放回收 int flag; coutflag; free(flag); else if(choice=0) break; /退出 else /输入操作有误 cout输入有误，请重试！endl; continue;