/************************************************************************//* 功能：  模拟实现可变分区存储管理的最佳适应算法的链表类时间：2014年9月1日21:57:21作者：信管1201 1205020116  肖锋										*//************************************************************************/#include "Link.h"#include <iostream>using namespace std;//freeLink的定义实现//void swap(int index1, int index2);	//交换连个节点的信息void freeLink::swap(int index1, int index2){	//交换这两个索引节点的所有信息	int i = 0;	Node* p1 = head;	while (i < index1)	{		p1 = p1->next;		++i;	}	int j = 0;	Node* p2 = head;	while (j < index2)	{		p2 = p2->next;		++j;	}	//p1和p2指向两个不同的节点，将要交换这两个节点，但是链表的位置不变	int size = p2->size;	int adress = p2->adress;	p2->size = p1->size;	p2->adress = p1->adress;		p1->size = size;	p1->adress = adress;}//Node* getNode(int index);freeLink::Node* freeLink::getNode(int index){	int i = 0;	Node* p=head;	while (i < index)	{		p = p->next;		++i;	}	return p;}//给自由链表前后的合并分区，循环首次适应算法//void pingJie2();void freeLink::pingJie2(){	//首先把链表按照地址的大小排序	//冒泡排序	int count = 0;	Node* p = head;	while (p != tail)	{		p = p->next;		++count;	}	//冒泡排序，吧链表按地址递增的方式存放	for (int i = 1; i <= count; ++i)	{		for (int j = 1; j <= count - i; ++j)		{			Node *p1, *p2;			p1 = getNode(j);			p2 = getNode(j + 1);			if (p1->adress > p2->adress)			{				swap(j, j + 1);			}		}	}	//排序完成之后考虑是否要合并	//考虑4种情况	Node *p1, *p2, *p3;	if (count == 1)		return;	//只有一个空闲的节点还合并个屁啊	else if (count == 2)	{//如果只有两个空闲的节点的话，那么就直接考虑向后合并		p1 = head->next;		p2 = p1->next;		if ((p1->adress + p1->size) == p2->adress)		{//如果成立就直接合并这两个节点			p1->size += p2->size;	//吧容量合并到p1上			delete p2;			p1->next = nullptr;			tail = p1;		}	}	else //这就一般的情况，那就要考虑四种情况了	{		p1 = head->next;		p2 = p1->next;		p3 = p2->next;	//指向前三个，以p2为操作对象，进行判断		//一直判断到链表尾部		while (p3 != nullptr)		{			if ((p1->adress + p1->size) == p2->adress || (p2->adress + p2->size) == p3->adress)	//要么前向，要么后巷，或者全要			{				if ((p1->adress + p1->size) == p2->adress && (p2->adress + p2->size) != p3->adress)				{//前向					//吧p2去除掉合并到p1里面去					p1->size += p2->size;					//去除p2,不用考虑为节点					p1->next = p3;					delete p2;					p2 = p3;					p3 = p2->next;				}				else if ((p1->adress + p1->size) != p2->adress && (p2->adress + p2->size) == p3->adress)				{//向后合并					//吧p3去掉合并到p2里面去,这个要考虑尾部节点					p2->size += p3->size;					if (p3 == tail)					{//去除p3						tail = p2;						delete p3;						p3 == nullptr;					}					else					{						p2->next = p3->next;						delete p3;						p3 = p2->next;					}				}				else if ((p1->adress + p1->size) == p2->adress && (p2->adress + p2->size) == p3->adress)				{//前后一起合并，去除p2,p3,考虑尾部节点					p1->size += p2->size + p3->size;					if (p3 == tail)					{						tail = p1;						p1->next = nullptr;						delete p2, p3;						p3 = nullptr;					}				}				else				{//什么也不干的类型					//移动一位					p1 = p2;					p2 = p3;					p3 = p3->next;	//整体下移一位				}			}		}	}}//首次循环适应算法的添加，就是尾部添加//void addNode2(gSize, gAdress)void freeLink::addNode2(int size, int adress){	//直接尾部插入这个回收的节点	//这块内存的起始地址	Node* newNode = new Node(size, adress, 'O', nullptr);	tail->next = newNode;	tail = newNode;   //添加到尾部}//循环首次适应//void setNeed(int index);void freeLink::setNeed(int index, int size){	Node* p;	Node* p2;   //就是要返回的索引对象	p = p2 = head->next;	int i = 1;	while (i < index)	{		p = p2;		p2 = p2->next;		++i;	}	p2->size -= size;   //把对应的空闲区间的大小修改	p2->adress += size;  //新的起始地址	if (p2->size == 0)	{		if (p2 == tail)		{			//重置尾节点，并且去除大小为0的节点			delete p2;			p->next = nullptr;			tail = p;		}		else		{			//不是尾部节点，就直接去除大小为0的节点就可以了			p->next = p2->next;			delete p2;		}	}}//删除尾部节点的函数//void popTail();void freeLink::popTail(){	//要去除尾部节点，就要重新给tail定位	Node* p;	Node* p2;	p = head;	p2 = p->next;	while (p2 != tail)	{		p = p2;		p2 = p2->next;    //循环直到指向最后一个	}	//此时p2指向tail	tail = p;	delete p2;	tail->next = nullptr;}//合并全部空闲的节点//void heBing();void freeLink::heBing(int allFreeAdress){	Node* p;	Node* p2;	p = head;	p2 = p->next;	int allFreeSize = 0;  //统计所有的空闲区间的大小	//int allFreeAdress=0;    //得到新的起始地址	while (head != tail)	{		allFreeSize += tail->size;		popTail();	}	//此时全部的节点都被删除,为空闲分区链添加一个最大的空间	addNode(allFreeSize, allFreeAdress);}//去除对应的节点//void popNeed(int index);void freeLink::popNeed(int index){	Node* p;	Node* p2;   //就是要返回的索引对象	p = p2 = head->next;	int i = 1;	while (i < index)	{		p = p2;		p2 = p2->next;		++i;	}	//去除p2	p = p2->next;	delete p2;}//得到index部节点的地址//int getNeedAdress(int index);int freeLink::getNeedAdress(int index){	Node* p;	Node* p2;   //就是要返回的索引对象	p = p2 = head->next;	int i = 1;	while (i < index)	{		p = p2;		p2 = p2->next;		++i;	}	return p2->getAdress();}//得到第index位的size//int getNeedSize(int index);int freeLink::getNeedSize(int index){	Node* p;	Node* p2;   //就是要返回的索引对象	p = p2 = head->next;	int i = 1;	while (i < index)	{		p = p2;		p2 = p2->next;		++i;	}	return p2->getSize();}//找到要修改的节点是第几位]//int getNeedGai(size);int freeLink::getNeedGai(int size){	int index = 1;    //返回索引	Node* p;	Node* p2;	p = p2 = head->next;    //p2指向要修改的节点	while (p2->size < size || p2 == nullptr)	{		p = p2;		p2 = p2->next;		++index;	}	if (p2 == nullptr)		return 0;	return index;       //返回当前位置的索引}//设置第i个节点//void setHeadNode(int index, int size, int adress);void freeLink::setNode(int index, int size, int adress){	Node* p; Node* p2;  //p2指向要修改的节点	p = head;	p2 = p->next;	for (int i = 1; i < index; ++i)	{		p = p2;		p2 = p2->next;    //要修改的对象	}	/*	p2->size = size;	p2->adress = adress;	*/	//吧原来的节点删除，重新插入到正确的位置	//Node* newPaiXu = new Node(size, adress, 'O', nullptr);	if (p2 == tail)	{		//如果p2是尾节点，那就重置为节点，在插入		delete p2;		p->next = nullptr;		tail = p;	}	else	{		//不是尾部节点那就直接断		p->next = p2->next;		delete p2;	}	//插入	addNode(size, adress);}//显示当前的分区//void show();void freeLink::show(){	Node* p;	p = head->next;	cout << "自由分区的链表是(剩余, 起始地址)" << endl;	while (p != nullptr)	{		cout << "(" << p->size << " , " << p->adress << ")->";		p = p->next;	}	cout << endl;}//内存地址相同的时候的碎片拼接//void pingJie();//2014年9月2日17:03:46有问题void freeLink::pingJie(){	Node* p;	Node* p2;	p = head;    //指向头结点	p2 = p->next;     //指向第一个节点	//int count=1;	int qiShiAdress;	//这样来合并，用起始地址加内存的值在链表中找，是不是有节点的起始和他相同，如果相同就向后合并,遍历整个链表	while (p2 != nullptr)	{		qiShiAdress = p2->adress + p2->size;		Node* p2_3 = head;		for (Node* p3 = head->next; p3 != nullptr; p3 = p3->next)    //p2_3指向p3的前面		{			if (qiShiAdress == p3->adress)			{				//找到了可以合并的那么就直接把这两个节点合并,把找到的这两个去掉重新插入				int newAdress = p2->adress;				int newSize = p2->size + p3->size;				//这里断掉链表要小心不是紧挨着,断开怎么断？				if (p2->next == p3)				{					p->next = p3->next;				}				else				{					p->next = p2->next;					p2_3->next = p3->next;				}				delete p2, p3;				p2 = p->next;				//Node* chaRu=new Node(newSize, newAdress, 'O', nullptr);				this->addNode(newSize, newAdress);				qiShiAdress = 0;  //重置，作为标准，以便后面判断是否还要到下一个节点				break;			}			p2_3 = p3;		}		if (qiShiAdress != 0)		{			p = p2;			p2 = p2->next;		}	}	/*	//!2014年9月3日09:19:37	//这里考虑到保持的时候是从小到大，而拼接是按地址重后到前的排序的	//把Node按地址的位置重新排序保存的vector里面去	//先知道一共有多少个节点	while(p2 != nullptr)	{	p=p2;	p2=p2->next;	++count;    //当p指向尾节点，那就结束，统计一共有多少个节点	}	//重置p,p2	p=head->next;	p2=p->next;	//直到全部按地址递增的方式全部放入到vector里面去	//然后按地址取出Node，按上面的方式合并	//找到可以拼接的地方进行拼接	//while(p2 != nullptr)   //重头找到尾，找到就直接跳出，找不到就到达尾部	//{//可能有多处要合并不止一处	if((p->adress+p->size) == p2->adress)	{	//如果是末尾的话，要重置尾指针	if(p2 == tail)	{	tail=p;	}	//如果有可以合并的区间的话	//1、吧p的内存大小改变成p和p2的内存和	p->size+=p2->size;	//2、吧p的指针指向p2的后面	p->next=p2->next;	//3、吧p2断开,然后释放p2	delete p2;	}	p=p2;	p2=p2->next;	//}	//如果是尾部节点的话，那么就是没有可以合并的区间	if(p == tail)	{//看是不是只有一个节点	cout<<"xxx"<<endl;	}	else	{	while(p->next != tail || (p->adress+p->size) != p2->adress) //找到可以合并的区间，或者到了尾部节点	{	//cout<<"xxx"<<endl;	p=p2;   //吧p和p2整体向前移动一位	p2=p2->next;	}	if((p->adress+p->size) == p2->adress && p->next == tail)	{	//如果有可以合并的区间的话	//1、吧p的内存大小改变成p和p2的内存和	p->size+=p2->size;	//2、吧p的指针指向p2的后面	p->next=p2->next;	//3、吧p2断开,然后释放p2	delete p2;	tail=p; //重置尾节点	}	}	*/}//添加一个Node,等会选择插入的地点//void addNode(int size, int adress);void freeLink::addNode(int size, int adress){	//1、先找到要插入的位置节点p指向前面的那个节点，p2指向后面那个节点	Node* p;	Node* p2;	p = head;	p2 = head->next;	if (p2 != nullptr)	{		while (p2->size < size)    //找到比size要大的第一个节点		{			p = p2;			p2 = p2->next;			if (p == tail)				break;		}	}	//判断是不是尾节点，不然要重置尾节点	if (p2 == nullptr)	{		//如果是尾部节点，那就直接加上去就可以了		Node* p3 = new Node(size, adress, 'O', nullptr);		tail->next = p3;		//重置尾节点		tail = p3;	}	else	{		//2、创建一个节点保存这个内存信息,这个节点插入到p和p2之间		//这块内存的起始地址		Node* newNode = new Node(size, adress, 'O', p2);		//3、插入链表		//就是把newNode插入到两点之间		p->next = newNode;	}}//删除Node//void popNode(char name);/*freeLink::Node* freeLink::popNode(char name){//空闲分区删除节点一般是改变节点的大小//判断是要改变还是要删除}*///busyLink类的定义//合并所有adress回收碎片//void reAdress();int busyLink::reAdress(){	Node* p;	Node* p2;	p = head;	p2 = p->next;	int endAdress = 0;	//循环到队尾，size不变，adress全部重置	while (p != tail)	{		p2->adress = p->adress + p->size;   //把这个节点的起始地址改为上个节点的结束		p = p2;		p2 = p2->next;    //指向下一个	}	//当最后一个也得到处理的时候	//重定位结束，	//后面再调用freeLink里面的函数，把所有的free节点收集起来做成一个大的空闲节点	endAdress = tail->adress + tail->size;	return endAdress;}//得到索引节点的adress//int getNeedAdress(int index);int busyLink::getNeedAdress(int index){	Node* p;	Node* p2;   //就是要返回的索引对象	p = p2 = head->next;	int i = 1;	while (i < index)	{		p = p2;		p2 = p2->next;		++i;	}	//cout<<"p2 name:"<<p2->name<<endl;	return p2->adress;  //记得加return 返回啊！！！！我的天浪费我半天}//得到索引节点的size//int getNeedSize(int index);int busyLink::getNeedSize(int index){	Node* p;	Node* p2;   //就是要返回的索引对象	p = p2 = head->next;	int i = 1;	while (i < index)	{		p = p2;		p2 = p2->next;		++i;	}	p2->getSize();	return p2->getSize();}//得到需要的该的节点的索引//int getNeedGai(char name);int busyLink::getNeedGai(char name){	int index = 1;    //返回索引	Node* p;	Node* p2;	p = p2 = head->next;    //p2指向要修改的节点	while (p2->name != name)	{		p = p2;		p2 = p2->next;		++index;		if (p == tail)			break;	}	if (p2 == nullptr)		return 0;	//cout<<index<<endl;	return index;       //返回当前位置的索引}//显示当前的分区//void show();void busyLink::show(){	Node* p;	p = head->next;	cout << "作业分区的链表是(剩余, 名字, 起始地址)" << endl;	while (p != nullptr)	{		cout << "(" << p->size << " , " << p->name << " , " << p->adress << ")->";		p = p->next;	}	cout << endl;}//内存地址相同的时候的碎片拼接//void pingJie();//添加一个Node,等会选择插入的地点//void addNode(int size, int adress, char name);void busyLink::addNode(int size, int adress, char name){	//工作链表添加的作业直接添加到尾部就可以了	Node* p;	//创建一个将要进入内存的作业	p = new Node(size, adress, name, nullptr);    //其实这里析构函数应该回收p的内存	tail->next = p;	tail = p;}//删除Node//void popNode(char name);void busyLink::popNode(char name){	Node* p;	Node* p2;	//1、找到名字为c的内存	p = p2 = head->next;	while (p2->name != name || p2 == nullptr)	{		p = p2;		p2 = p2->next;	}	if (p2 == nullptr)	{		std::cout << "不好意思，没有这个作业进入内存" << std::endl;		return;	}	//2、得到这块内存里面的值	//int oldAdd=p2->adress;	//int oldsize=p2->size;	//3、创建一个节点保存这个内存的值	//Node* p3=new Node(oldsize, oldAdd, name, nullptr);	//4、回收原来的这块内存	if (p->next == tail)	{		delete p2;		p->next = nullptr;		tail = p;	}	else	{		p->next = p2->next;		delete p2;	}}

【操作系统】Link.cpp