c++ 实验：可变分区管理

【实例截图】

【核心代码】

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 128 //系统分配给用户的最大内存

typedef struct MCB{//内存控制块
	int add;       //分区起始地址
	int sta;       //分区状态，0为可用
	int size;      //分区大小
	int jno;       //分区装入作业号,作业号从1开始
	struct MCB* next; //链连指针
}MCB;
MCB *free_table,*ft;  //可用分区的头指针，尾指针
MCB *used_table,*ut;  //已分配分区的头指针，尾指针

void initFree_table()//初始化可用区链表,初始大小为整个用户分区
{
	if(!(free_table=(MCB*)malloc(sizeof(struct MCB))))
		exit(1);
	free_table->add = 0;
	free_table->size = MAX_SIZE;
	free_table->sta = 0;
	free_table->jno = 0;
	free_table->next = NULL;
	ft=free_table;
}

void initUsed_table()//初始化已分配分区链表
{
	if(!(used_table=(MCB*)malloc(sizeof(struct MCB))))
		exit(1);
	used_table->add = 0;
	used_table->size = 0;
	used_table->sta = 1;
	used_table->jno = 0;
	used_table->next = NULL;

	ut=used_table;
}

void add_ut(MCB *pf,int size,int jno)
{
	//修改已分配链表
	if(used_table->next == NULL && used_table->size == 0)
	{//已用分区表的第一块
		used_table->add = pf->add;
		used_table->size = size;
		used_table->jno = jno;
	}else{//将新增分区加到已分配链表末尾
		//pt为临时MCB
		MCB *pt;
		if(!(pt=(MCB*)malloc(sizeof(struct MCB))))
			exit(1);
		pt->size = size;
		pt->add = pf->add;
		pt->jno = jno;
		pt->sta = 1;
		pt->next = NULL;

		ut->next = pt;
		ut = ut->next;
	}
}

void allot(int jno,int size)//首次适应法为作业分配存储空间
{
	
	if(jno <= 0 ) /*|| jno有重复*/
	{
		printf("输入作业号有误,请重新输入!\n");
		return;
	}

	if(size > MAX_SIZE)
	{
		printf("作业太大，无法分配!\n");
		return;
	}
	if(size <= 0)
	{
		printf("作业大小不合法!\n");
	}

	//查空白分区链表
	MCB *pf = free_table;
	MCB *p=pf;
	while(pf != NULL && pf->size < size)
	{
		p = pf;
		pf = pf->next;
	}
	if(pf == NULL)
	{
		printf("未找到可用分区!\n");
		return;
	}

	if(pf->size == size){
		//把该分区从可用区链表中删除
		if(pf == free_table)
		{/*删除的是头结点*/
			free_table->sta = 1;
			if(free_table->next != NULL)
			{//存在后续结点,则头指针后移
				free_table = free_table->next;
			}else{//只有一个结点,则置空可用区
				free_table->size = 0;
			}
		}else{
			pf->sta = 1;
			p->next = pf->next;
			pf->next = NULL;
		}
		//将新增分区pf加到已分配链表
		add_ut(pf,size,jno);
	}else if(pf->size > size){
		//把空白分区一分为二
		//将新增分区pf加到已分配链表
	    add_ut(pf,size,jno);
	    //修改空闲分区链表
	    pf->add = pf->add   size;
	    pf->size -= size;
		pf->jno = 0;
	}

	printf("作业空间已成功分配...\n\n");
	return;//正常分配
}

void reclaim(int jno)//回收内存空间
{
	//从used_table中找到jno
	MCB *pu = used_table;
	MCB *p = pu;//指向要回收块,即回收作业的前一个项
	while(pu && pu->jno != jno)
	{
		p = pu;
		pu = pu->next;
	}
	if(pu == NULL)
	{
		printf("没有找到作业编号为%d的作业!\n\n",jno);
		return;
	}

	int size = pu->size;
	
	//删除used_table中的jno块,即pu
	if(pu == used_table) /*删除的是头结点*/
	{
		if(used_table->next != NULL)
		{
			used_table = used_table->next;
		}else{
			used_table->size = 0;
		}
	}else{
		p->next = pu->next;
	}

	//把jno块pu插入free_table
	if(free_table->next == NULL && free_table->size == 0)
	{//可用区为空,则创建新的可用区
		free_table->size = size;
		free_table->add = pu->add;
		free_table->sta = 0;
		free_table->next = NULL;
	}else{/*查到应插入的位置,分两大种情况:在头结点之前,之后*/
		MCB *pf=free_table;//下一个位置,或下邻区
		MCB *q=pf; //q为要插入的位置,或上邻区

		/*插入位置在可用区头结点之前*/
		if(pu->add size < free_table->add)
		{
			MCB *tmp;
			if(!(tmp=(MCB*)malloc(sizeof(struct MCB))))
				exit(1);
			tmp->next = free_table;
			tmp->jno = 0;
			tmp->add = pu->add;
			tmp->size = pu->size;
			tmp->sta = 0;

			free_table = tmp;
		}else if(pu->add size == free_table->add){
		/*插入位置和可用区头结点下邻*/
			free_table->add -= size;
			free_table->size  = size;
		}else{/*插入位置在可用区头结点之后*/
			//查找位置
			while(pf->next != NULL && pf->add pf->size <= pu->add)
			{
				q = pf;
				pf = pf->next;
			}

			if(q->add q->size == pu->add)/*有与归还区上邻的空闲区*/
			{
				//归还长度 下邻区长度
				q->size = q->size size;
				if(pf->add == pu->add size)/*有与归还区下邻的空闲区*/
				{
					//删除下邻链接点
					q->next = pf->next;
					//把上邻空闲节点的长度增加归还块长度
					q->size = q->size   pf->size;
					free(pf);
				}
			}else{
				q->next = pu;
				if(pf->add == pu->add size)/*有与归还区下邻的空闲区*/
				{
					//把上邻空闲节点的长度增加归还块长度
					pu->size = size   pf->size;
					pu->next = pf->next;
					free(pf);
				}else{//把归还块直接插入未分配链表中
					pu->next = pf;
					pu->jno = 0;
				}
			}
		}
	}
	printf("成功回收作业分区!\n");
}

void displayUt(MCB *pMCB)//显示已使用作业分区表
{
	if(pMCB == NULL || pMCB->size == 0)
	{
		printf("\t当前内存中没有任何作业!\n\n");
		return;
	}

	MCB *p=pMCB;
	printf("\t作业编号\t起始地址\t结束地址\t分区大小\n");
	while( p != NULL)
	{
printf("\t%d\t\t%d\t\t%d\t\t%d\n",p->jno,p->add,p->add p->size,p->size);
		p = p->next;
	}
	printf("\n");
}

void displayFt(MCB *pMCB)//显示空闲主存分区表
{
	if(pMCB->size == 0)
	{
		printf("\t当前主存没有可用分区!\n\n");
		return;
	}

	MCB *p=pMCB;
	printf("\t起始地址\t结束地址\t分区大小\n");
	while( p != NULL)
	{
		printf("\t%d\t\t%d\t\t%d\n",p->add,p->add p->size,p->size);
		p = p->next;
	}
	printf("\n");
}

int main()
{//菜单选择
	int select=0,jno=0,size=0;
	initFree_table();
	initUsed_table();
	printf("\t\t\t可变分区管理-首次适应算法实验\n");
	printf("\t\t\t\t--Powered by ZhangHua\n");
	printf("\t本程序为便于计算,0号分区不使用,默认分区编号为1~128\n\n");
	do{
		printf("\t\t\t请选择操作命令:\n");
		printf("\t\t\t1:分配作业存储空间\n");
		printf("\t\t\t2:回收作业存储空间\n");
		printf("\t\t\t3:显示可用主存信息\n");
		printf("\t\t\t4:显示已用主存信息\n");
		printf("\t\t\t0:退出\n\n");
		scanf("%d",&select);
		switch(select)
		{
		case 0:
			exit(0);
			break;
		case 1:
		printf("请输入作业编号(从1开始，请勿重复输入已存在的作业编号!):");
			scanf("%d",&jno);
			printf("请输入作业%d所需内存大小:",jno);
			scanf("%d",&size);
			allot(jno,size);
			break;
		case 2:
			printf("请输入要回收的作业空间编号:");
			scanf("%d",&jno);
			reclaim(jno);
			break;
		case 3:
			printf("\t\t\t可用分区情况如下：\n\n");
			displayFt(free_table);
			break;
		case 4:
			printf("\t\t\t已用分区情况如下：\n\n");
			displayUt(used_table);
			break;
		default:
			printf("输入字符无效，请请重新输入!\n");
		}
	}while(select);
	return 0;
}