(整理)【Linux课程设计】可变分区最佳适应算法源代码.

1、精品文档精品文档#include<stdio.h>#include<malloc.h> #include<string.h>#include<stdlib.h>/ 采用最佳适应算法来实现可变分区的管理/ 数据结构的设计typedef struct node char name10;/ 作业的名字int start, length;/ 作业的起始地址和长度struct node *next;/ 链表结构体 *table;/ 为合并空闲区表而临时增加的一个数据结构/ 将空闲表中的数据项都存在这个结构的数组中/ 然对这个数组进行排序，最后得到从小到大的

2、空闲区表struct pnodeint start,length;/ 起始地址和长度;int menu()/ 选择菜单int n;for(; ;)n");最佳适应算法进行可变分区|*printf("printf("*|printf("*|*|*|*|*|*|*|*|*|*|*|*|*|*|*|*|*|*|*|*|*|*|*|*|*|*|*|*|*n");printf( printf( printf( printf( printf(printf("*|*|*|*|*|*|*|*|*| scanf("%d",&

3、n);while(n < 1 | n > 5) 1 输入作业数及大小(单位KB)2 查看内存使用情况3 释放内存4 查看空闲区表的情况5 退出程序请输入您的选择*|*|*|*|*|*|*|*|*|*|*|*|*n");*n");*n");*n");*n");*n");printf(" 输入有误请重新输入n");scanf("%d",&n);return n; / 要建立两张表，一张是进程占用分区状况表，一张是空闲区表table p;/ 占用表table f;/ 空闲表void

4、 init()/ 两张表的初始化p=(table)malloc (sizeof(struct node);/ 头结点p->next=NULL;/初始化是，占用表为空f=(table)malloc (sizeof(struct node);/ 头结点table f1=(table)malloc (sizeof(struct node);/ 初始定义为1K 的内存，有一个空闲空间f1->start=0;f1->length=1024;/ 定义内存为1k;f1->next=NULL;f->next=f1;/ 将 f1 插入表空闲中/ 输出内存使用表void printf

5、Use()table p1=p->next;/ 将使用表的所有内容显示出来printf(" 作业名起始地址长度 n");while(p1!=NULL)printf("%s ",p1->name);printf(" %d ",p1->start);printf("%dn",p1->length);p1=p1->next;/ 尚未使用的内存空闲表void printfNotUse()table f1=f->next;printf(" 起始地址空闲区大小n");wh

6、ile(f1!=NULL)printf("%d",f1->start);printf("%dn",f1->length);f1=f1->next;/ 将合并后的链表进行排序void sort()struct pnode a100;int i=0,temp,temp1;table f1;f1=f->next;while(f1!=NULL)/ 将空闲分区保存到数组中，进行排序。ai.length=f1->length;ai.start=f1->start;i+;f1=f1->next;/ 对数组进行排序,冒泡法for

7、(int k=0;k<i-1;k+)for(int j=0;j<=i-2-k;j+)if(aj.length>aj+1.length)temp=aj+1.length;temp1=aj+1.start;aj+1.length=aj.length;aj+1.start=aj.start;aj.length=temp;aj.start=temp1;f1=f->next;i=0;/ 按数组的顺序来排列while(f1!=NULL)/ 然后将排序的结果返还给空闲链表，也就是将链表按照分区大小排序f1->length=ai.length;f1->start=ai.st

8、art;f1=f1->next;i+;/ 分配空间算法int mallocmemory(char *name,int room)table p1,f1,f2,p2,f3,f4;f1=f->next;f2=f;/f2 始终指向f的前端while(f1!=NULL)if(room <= f1->length)break;f1=f1->next;f2=f2->next;if(f1=NULL)printf(" 对不起系统内存分配失败n");return -1;/ 生成新的占用结点p2=(table)malloc (sizeof(struct no

9、de);p2->start=f1->start;strcpy(p2->name, name);p2->length=room;p2->next=NULL;/ 链结到占用表的表尾p1=p->next;if(p1=NULL)/如果链表为空，则直接把p2 链接到尾部p->next=p2;elsewhile(p1->next!=NULL)/ 找到链表的表尾，将p2 放在上面p1=p1->next;p1->next=p2;/ 此时要修改空闲区表的结点f1->length -= room;f1->start += room;/ 如果是

10、 0 直接将其删除if(f1->length=0)f2->next=f1->next;free(f1);/ 否则要进行重新排序elsef3=f->next;f4=f;while(f3 && f3->length < f1->length)f3=f3->next;f4=f4->next;/ 如果 f1 不是最大就调换位置if(f3->next!=NULL)f4->next=f1;f2->next=f1->next;f1->next=f3;return p2->start;/ 回收空间算法依据

11、输入的程序名来找到其对应空间进行回收void freeblock(char *name)table p1,p2,f1,f2,f3,f4;int x=0;/ 标记位来判断是否进行了全并操作p1=p->next;/p1 为查找迭代器p2=p;/p2 为要查找的前驱while(p1!=NULL)if (!(strcmp(p1->name,name) break;p1=p1->next;p2=p2->next;if(p1=NULL)/如果未找到，提示错误。printf(" 程序输入有误n");return ;/ 否则要变动占用表p2->next=p1-

12、>next;/ 删除该进程/ 生成新的空闲区表结点f1=(table)malloc (sizeof(struct node);/f1 为释放的空闲区f1->length=p1->length;f1->start=p1->start;free(p1);/ 观察空闲表来进行合并操作f2=f->next;/f2 为索引迭代器f3=f;/f3 为查找前驱while(f2!=NULL)/ 和后一个空闲区进行合并if(f1->start + f1->length = f2->start)f1->length += f2->length;f4

13、=f2;/f2 赋值给 f4，临时变量？/ 已经和前面的相邻合并if(f3 = f1)/ 如果他的前驱就等于这个空闲区，合并f1->next=f2->next;f3=f3->next;f2=f2->next;/ 只与后面的合并else/ 不等于，则把此空闲区接在其前驱的后面f3->next=f1;f1->next=f2->next;f2=f2->next;f3=f1;/其前驱 f3 成为 f1free(f4);/ 释放掉 f4x=1;/ 和前一个空闲区else if(f2->start+f2->length=f1->start)

14、/ 起始地址+长度= 现在空闲区的起始地址，进行合并f2->length+=f1->length;f3=f2;f1=f3;f2=f2->next;x=1;else/没发现，进行迭代查找f2=f2->next;f3=f3->next;/ 重新改变空闲区表if(x=1)sort();/ 找合适的位置进行插入elsef2=f->next;f3=f;while(f2&&f2->length<=f1->length)/ 逐一查找，找到合适的位置 f2=f2->next;f3=f3->next;/ 添加到最后一个结点if(f

15、2=NULL)/进行插入f1->next=NULL;f3->next=f1;elsef3->next=f1;f1->next=f2;int main()char name20;int room,n,i=0,n1;init();/ 完成初始化for(; ;)switch(menu()case 1: printf(" 请输入作业的个数:n");scanf("%d",&n);for( i=0;i<n;i+) fflush(stdin);printf(" 请输入第%d 作业的名称和大小:n",i+1);scanf("%s",name);getchar();scanf("%d",&n1);mallocmemory(name,n1);break;case 2: p