#define OK 1 // 完成#define ERROR 0 // 出错 typedef int Status; typedef struct free_table// 定义一个空闲区说明表结构{int num; // 分区序号 long address; // long length; //int state; // }ElemType; typedef struct Node// { ElemType data; struct Node *prior; // struct Node *next; // 起始地址分区大小 分区状态 线性表的双向链表存储结构 前趋指针 后继指针}Node,*LinkList;LinkList first; // 头结点LinkList end; // 尾结点int flag;// 记录要删除的分区序号Status Initblock()// 开创带头结点的内存空间链表{first=(LinkList)malloc(sizeof(Node));end=(LinkList)malloc(sizeof(Node));first->prior=NULL;first->next=end;end->prior=first;end->next=NULL;end->=1;end->=40;end->=600;end->=0;return OK;void sort()// 分区序号重新排序{Node *p=first->next,*q;q=p->next;for(;p!=NULL;p=p->next) {for(q=p->next;q;q=q->next){if(p->>=q->{q->+=1;}}}}// 显示主存分配情况void show(){ int flag=0;// 用来记录分区序号Node *p=first;p->=0;p->=0;p->=40;p->=1;sort();printf("\n\t\t 》主存空间分配情况《\n");printf("**********************************************************\n\n");printf（" 分区序号\t 起始地址\t 分区大小\t 分区状态\n\n"）;while(p){printf("%d\t\t%d\t\t%d",p->,p->,p->;if(p->==0) printf("\t\t 空闲\n\n");else printf("\t\t 已分配\n\n");{p=p->next; printf("**********************************************************\n\n"); }// 首次适应算法Status First_fit(int request){// 为申请作业开辟新空间且初始化Node *p=first->next;LinkList temp=(LinkList)malloc(sizeof(Node));temp->=request;temp->=1;p->=1;while(p)if((p->==0)&&(p->==request)){// 有大小恰好合适的空闲块p->=1;return OK;break;}else if((p->==0) && (p->>request)){// 有空闲块能满足需求且有剩余temp->prior=p->prior; temp->next=p;temp->=p->;temp->=p->;p->prior->next=temp; p->prior=temp;p->=temp->+temp->;p->=request;p->+=1;return OK;break;}p=p->next;}return ERROR;}// 最佳适应算法Status Best_fit(int request){int ch; // 记录最小剩余空间Node *p=first;Node *q=NULL; // 记录最佳插入位置LinkList temp=(LinkList)malloc(sizeof(Node)); temp->=request;temp->=1;p->=1;while(p) // 初始化最小空间和最佳位置{if((p->==0) && (p->>=request) ){if(q==NULL){q=p;ch=p->;}else if(q-> > p->{q=p;ch=p->;}p=p->next;}if(q==NULL) return ERROR;//没有找到空闲块else if(q->==request){q->=1;return OK;}else{temp->prior=q->prior;temp->next=q;temp->=q->;temp->=q->;q->prior->next=temp;q->prior=temp;q->+=request;q->=ch;q->+=1;return OK;}return OK;}// 最差适应算法Status Worst_fit(int request){int ch; // 记录最大剩余空间Node *p=first->next;Node *q=NULL; // 记录最佳插入位置LinkList temp=(LinkList)malloc(sizeof(Node));temp->=request;temp->=1;p->=1;while(p) // 初始化最大空间和最佳位置{if(p->==0 && (p->>=request) ){if(q==NULL){q=p;ch=p->;}else if(q-> < p->{q=p;ch=p->;}p=p->next;}if(q==NULL) return ERROR;//没有找到空闲块else if(q->==request){q->=1;return OK;}else{temp->prior=q->prior;temp->next=q;temp->=q->;temp->=q->;q->prior->next=temp;q->prior=temp;q->+=request;q->=ch;q->+=1;return OK;}return OK;}// 分配主存Status allocation(int a){int request;// 申请内存大小printf(" 请输入申请分配的主存大小(单位:KB):"); scanf("%d",&request);if(request<0 ||request==0){printf(" 分配大小不合适，请重试！");return ERROR;}switch(a){case 1: // 默认首次适应算法if(First_fit(request)==OK) printf("\t**** 分配成功！****");else printf("\t**** 内存不足，分配失败！****");return OK;break;case 2: // 选择最佳适应算法if(Best_fit(request)==OK) printf("\t**** 分配成功！****");else printf("\t**** 内存不足，分配失败！****");return OK;break;case 3: // 选择最差适应算法if(Worst_fit(request)==OK) printf("\t**** else printf("\t****分配成功！****");内存不足，分配失败！****"); return OK;break;}}Status deal1(Node *p)// 处理回收空间{Node *q=first;for(;q!=NULL;q=q->next){if(q==p){if(q->prior->==0&&q->next->!=0){q->prior->+=q->;q->prior->next=q->next;q->next->prior=q->prior;q=q->prior;q->=0;q->=flag-1;}if(q->prior->!=0&&q->next->==0) {q->+=q->next->;q->next=q->next->next;q->next->next->prior=q;q->=0;q->=flag;}if(q->prior->==0&&q->next->==0) {q->prior->+=q->;q->prior->next=q->next; q->next->prior=q->prior; q=q->prior;q->=0;q->=flag-1;}if(q->prior->!=0&&q->next->!=0){q->=0;}}}return OK;}Status deal2(Node *p)// 处理回收空间Node *q=first;for(;q!=NULL;q=q->next){if(q==p){if(q->prior->==0&&q->next->!=0){q->prior->+=q->;q->prior->next=q->next;q->next->prior=q->prior;q=p->prior;q->=0;q->=flag-1;}if(q->prior->!=0&&q->next->==0)q->=0;} if(q->prior->==0&&q->next->==0){q->prior->+=q->;q->prior->next=q->next;q->next->prior=q->prior;q=q->prior;q->=0;q->=flag-1;}if(q->prior->!=0&&q->next->!=0){q->=0;}}return OK;}// 主存回收Status recovery(int flag){Node *p=first;for(;p!=NULL;p=p->next){if(p->==flag){if(p->prior==first){if(p->next!=end)// 当前P 指向的下一个不是最后一个时{if(p->next->==0) // 与后面的空闲块相连{p->+=p->next->;p->next->next->prior=p;p->next=p->next->next;p->=0;p->=flag;}else p->=0;}if(p->next==end)// 当前P 指向的下一个是最后一个时{p->=0;}}// 结束if(p->prior==block_first) 的情况else if(p->prior!=first)if(p->next!=end){deal1(p);}else{deal2(p);}}// 结束if(p->prior!=block_first)的情况}// 结束if(p->==flag) 的情况}printf("\t**** 回收成功****");return OK;}// 主函数void main(){int i; // 操作选择标记int a;// 算法选择标记printf(" f******************************************************** **\n");printf("\t\t 用以下三种方法实现主存空间的分配\n");printf("\t(1) 首次适应算法\t(2) 最佳适应算法\t(3) 最差适应算法\n");printf(" f********************************************************* *\n");printf("\n");printf(" 请输入所使用的内存分配算法:");scanf("%d",&a);while(a<1||a>3){printf(" 输入错误，请重新输入所使用的内存分配算法:\n");scanf("%d",&a);}switch(a)case1:printf("\n\t**** case 2:printf("\n\t**** case 3:printf("\n\t**** 使用首次适应算法：使用最佳适应算法：使用最坏适应算法：}Initblock(); // 开创空间表while(1){show();printf("\t1: 分配内存\t2: 回收内存\t0: printf(" 请输入您的操作：");scanf("%d",&i);if(i==1)allocation(a); // 分配内存****\n");break; ****\n");break; ****\n");break;退出\n");else if(i==2) // 内存回收printf(" 请输入您要释放的分区号："); scanf("%d",&flag);recovery(flag);}else if(i==0){printf("\n 退出程序\n");break; // 退出}else // 输入操作有误{printf(" 输入有误，请重试！"); continue;八、执行结果和结果分析初始化首次适应算法：当作业1、2、3 顺利分配内存空间后：}回收序号 2 里面的内存：分配作业4：回收序号 3 里面的内存（与上邻序号2相连了）回收序号 1 里的内存（与下邻序号 2 相连了）继续分配（会发现总是按顺序查找满足要求的第一个空闲块，一旦发现就会分配）。