最佳适应算法.cpp

模拟了操作系统里面的动态分配和回收内存空间的过程

// 首次适应算法.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"

#include <stdio.h>
#include <stdlib.h> 
#include <conio.h>
#include <string.h>

#define GetSpace(type) (type*)malloc(sizeof(type)) 

#define NULL 0
#define SIZE 0  //定义可以分割空闲块的差值 

struct mem {
		char Name[10];
		int MemAdr;  //内存块首地址
		int Lenth;   //块长度
		bool State;  //0 代表是空闲块，1 代表是已分配块
		mem *prior;
		mem *next;
		}*Head,*Tail;

typedef struct job JOB;
typedef struct mem MEM;

void DispFreeMem(MEM *pr) /*建立进程显示函数,用于显示当前进程*/ 
{ 
	int i=0;
	printf("\n******************************************");
	printf("\n\n The state of free memory:");
	printf("\n Chunk Num \t FirAddress \t Lenth(K)");  //显示空闲块的首地址以及大小
	while(pr!=Tail)
	{
		if(pr->State==0)
		{
			printf("\n %d \t\t %d \t\t %d K",i,pr->MemAdr,pr->Lenth);
			i++;
		}
		pr=pr->next;
	}
} 

void DispNotFreeMem(MEM *pr) /*建立进程显示函数,用于显示当前进程*/ 
{ 
	printf("\n******************************************");
	printf("\n\n The state of not free memory:");
	printf("\n Job Name \t FirAddress \t Lenth(K)");  //显示空闲块的首地址以及大小
	while(pr!=Tail)
	{
		if(pr->State==1)
		{
			printf("\n %s \t\t %d \t\t %d K",pr->Name,pr->MemAdr,pr->Lenth);
		}
		pr=pr->next;
	}
	printf("\n\n******************************************");
}

void Distribute()
{
	MEM *temp,*temp2,*p=NULL;
	char Name[10];
	int Lenth;
	int min=30000;

	printf("\n Name of the job:   "); 
	scanf("%s",Name);  
	printf("\n The space of this job:(K)   ");
	scanf("%d",&Lenth);
	getchar();
	temp2=Head->next;
	while(temp2!=Tail)  //查找足够大的空闲块来分配
	{	
		if(temp2->State==0&&temp2->Lenth>=Lenth)
		{
			if(temp2->Lenth<min)
			{
				p=temp2;
				min=temp2->Lenth;
			}
		}
		temp2=temp2->next;
	}
	if(p==NULL)     //没有足够的空间分配给当前作业
	{	
		printf("\n\t\tThe free memory is not enough for this job!!\n");
		printf("\nPlease press any key to continue......\n");
		getchar();
		return; 
	}
	if(p->Lenth-Lenth>SIZE)	//空闲块空间比所需空间大，则分裂为两个结点
	{
		temp=GetSpace(MEM);
		strcpy(temp->Name,Name);  //添加新结点的相关参数
		temp->MemAdr=p->MemAdr;
		//printf("\n \t\t!!!! The allotted address of job %s is: %d !!!!\n",Name,temp->MemAdr);
		temp->Lenth=Lenth;
		temp->State=1;

		p->prior->next=temp;  //插入新结点
		temp->prior=p->prior;
		temp->next=p;
		p->prior=temp;

		p->MemAdr=p->MemAdr+temp->Lenth; //修改分裂后的剩余结点信息
		p->Lenth -= temp->Lenth;
	}
	else	//否则只需直接把作业填进空闲块即可
	{
		strcpy(p->Name,Name);
		p->State=1;
	}
}

void Reclaim()
{
	MEM *temp1,*temp2,*p;
	char Name[10];
	printf("\n Name of the job:   "); 
	scanf("%s",Name);
	getchar();
	p=Head->next;
	while(p!=Tail&&strcmp(p->Name,Name)!=0)  //查找需要释放的作业
		p=p->next;	
	if(p==Tail)
	{
		printf("\n\t\tThis job is not in the memory!!");
		printf("\nPlease press any key to continue......\n");
		getchar();
		return; 
	}
	if(p->prior->State==0&&p->next->State==0)  
	{  //将要释放的内存块的前后内存块都为空闲，合并
		temp1=p;
		temp2=p->next;
		p->prior->next=temp2->next;
		temp2->next->prior=p->prior;
		p->prior->Lenth += temp1->Lenth + temp2->Lenth;
		free(temp1);
		free(temp2);
	}
	else if(p->prior->State==1&&p->next->State==0)
		{  //将要释放的内存块的后内存块为空闲，合并
			temp2=p->next;
			p->next=temp2->next;
			temp2->next->prior=p;
			strcpy(p->Name,"NULL");
			p->Lenth += temp2->Lenth;
			p->State=0;
			free(temp2);
		}
	else if(p->prior->State==0&&p->next->State==1)
		{  //将要释放的内存块的前内存块为空闲，合并
			temp1=p;
			p->prior->next=p->next;
			p->next->prior=p->prior;
			p->prior->Lenth += p->Lenth;
			free(temp1);
		}
	else if(p->prior->State==1&&p->next->State==1)
		{  //将要释放的内存块的前后内存块都不为空闲，无需合并
			strcpy(p->Name,"NULL");
			p->State=0;
		}
}

void Choice()
{
	char CH;
	MEM *temp1,*temp2;
	temp1=Head;
	temp2=Head->next;
	while(1)
	{
		printf("\n		------------------");
		printf("\n		| 1.Apply a job  |");
		printf("\n		| 2.Cancel a job |");
		printf("\n		| 3.Exit	 |");
		printf("\n		------------------");
		printf("\n\n	Please make a choice:	");
		scanf("%c",&CH);
		switch(CH)
		{
		case '1':	Distribute();
					DispFreeMem(Head->next);   //显示空闲链的状态
					DispNotFreeMem(Head->next);//显示作业占用内存状况
					break;
		case '2':	Reclaim();
					DispFreeMem(Head->next);   //显示空闲链的状态
					DispNotFreeMem(Head->next);//显示作业占用内存状况
					break;
		case '3':	while(temp1!=NULL)
					{
						free(temp1);
						temp1=temp2;
						if(temp2!=NULL)
							temp2=temp2->next;
					}
					return;
		}
		printf("\nPlease press any key to continue......\n");
		getchar();
	}
}

void main()/*主函数*/
{
	MEM *s;
	printf("Please input the total number the memory:(K)   ");
	s=GetSpace(MEM);     //创建空闲链表
	scanf("%d",&s->Lenth);
	getchar();
	strcpy(s->Name,"NULL");
	s->MemAdr=0;s->State=0;
	//初始化空闲链的头尾结点
	Head=GetSpace(MEM);	Tail=GetSpace(MEM);  
	Head->next=s;	Tail->next=NULL;
	s->prior=Head;	s->next=Tail;
	Tail->prior=s;
	Head->State=Tail->State=1;	
	Choice();	//进入主菜单进行相应操作	
}