[数据结构与算法]7-1 内存分区分配--首次适应算法 (100 分)

一：题目7-1 内存分区分配–首次适应算法 (100 分) 宝 今天你看我博客了吗

输入内存的大小和阈值minsize，按照首次适应算法进行连续的分区分配。在划分时，若剩余的内存小于等于minsize，则将整块内存分配给该进程不再进行划分。 根据菜单选择相应的操作：

1.初始化：输入内存的大小和阈值minsize，初始状态下空闲分区名字为“void”。

2.分配：输入申请进程的名字、大小。

若可以分配，显示“分配成功！”；
若剩余空间不足，显示不分配原因“剩余空间不足，不予分配。”；
若剩余的空间通过紧凑技术，可以再分配，提示“是否通过紧凑技术，重新划分？(Y/N)”若选择“Y”，通过紧凑技术重新划分并分配，成功后，显示“分配成功！”若选择“N”，则输出“没有合适的剩余空间，不予分配。”
3.回收：输入回收进程的名字，若有相邻空闲分区，需要合并，并输出“回收成功！”；若输入错误，提示“查无此分区！” 4.显示：显示当前内存的分配状态。

0.退出

其他：输出“输入错误，请重新输入。”

输入格式:
先进行初始化后，按照菜单进行相应的操作。

输出格式:
菜单只显示一次，按照相应的选择输出。
输入样例1:
在这里给出一组输入。例如：

1
1024 5
4
0

结尾无空行
输出样例1:
在这里给出相应的输出。例如：

1.初始化
2.分配
3.回收
4.显示
0.退出
请选择：
分区号 分区 起始地址 结束地址 大小 当前状态
1 void 0 1023 1024 空闲
结尾无空行
输入样例2:
在这里给出一组输入。例如：

1
1000 5
2
A 100
2
B 200
2
C 150
2
D 250
2
E 200
2
F 95
4
0

结尾无空行
输出样例2:
在这里给出相应的输出。例如：

1.初始化
2.分配
3.回收
4.显示
0.退出
请选择：
分配成功！
分配成功！
分配成功！
分配成功！
分配成功！
分配成功！
分区号 分区 起始地址 结束地址 大小 当前状态
1 A 0 99 100 已分配
2 B 100 299 200 已分配
3 C 300 449 150 已分配
4 D 450 699 250 已分配
5 E 700 899 200 已分配
6 F 900 999 100 已分配

结尾无空行
输入样例3:
在这里给出一组输入。例如：

1
1000 5
2
A 100
2
B 200
2
C 150
2
D 250
2
E 200
2
F 150
4
0
结尾无空行

输出样例3:
在这里给出相应的输出。例如：

1.初始化
2.分配
3.回收
4.显示
0.退出
请选择：
分配成功！
分配成功！
分配成功！
分配成功！
分配成功！
剩余空间不足，不予分配。
分区号 分区 起始地址 结束地址 大小 当前状态
1 A 0 99 100 已分配
2 B 100 299 200 已分配
3 C 300 449 150 已分配
4 D 450 699 250 已分配
5 E 700 899 200 已分配
6 void 900 999 100 空闲

结尾无空行
输入样例4:
在这里给出一组输入。例如：

1
1000 5
2
A 100
2
B 200
2
C 150
2
D 250
2
E 200
2
F 150
3
A
4
0

结尾无空行
输出样例4:
在这里给出相应的输出。例如：

1.初始化
2.分配
3.回收
4.显示
0.退出
请选择：
分配成功！
分配成功！
分配成功！
分配成功！
分配成功！
剩余空间不足，不予分配。
回收成功！
分区号 分区 起始地址 结束地址 大小 当前状态
1 void 0 99 100 空闲
2 B 100 299 200 已分配
3 C 300 449 150 已分配
4 D 450 699 250 已分配
5 E 700 899 200 已分配
6 void 900 999 100 空闲

结尾无空行
输入样例5:
在这里给出一组输入。例如：

1
1000 5
2
A 100
2
B 200
2
C 150
2
D 250
2
E 200
2
F 150
3
A
2
X 150
Y
4
0

结尾无空行
输出样例5:
在这里给出相应的输出。例如：

1.初始化
2.分配
3.回收
4.显示
0.退出
请选择：
分配成功！
分配成功！
分配成功！
分配成功！
分配成功！
剩余空间不足，不予分配。
回收成功！
是否通过紧凑技术，重新划分？(Y/N)
分配成功！
分区号 分区 起始地址 结束地址 大小 当前状态
1 B 0 199 200 已分配
2 C 200 349 150 已分配
3 D 350 599 250 已分配
4 E 600 799 200 已分配
5 X 800 949 150 已分配
6 void 950 999 50 空闲

二:思路

思路：
1.解释算法：动态分区分配-首次适应算法:
<1>:动态分区分配是根据进程的实际需要，动态的为之分配内存的空间,
<2>:那么首次适应算法首次适应算法，要求空闲分区链以地址递增的次序链接，
在分配内存时，从链首开始顺序查找，直到找到一个大小能满足要求的
空闲分区为止，然后再按照作业的大小，
从该分区中划出一块内存空间分给请求者，余下的空闲分区仍停留在空闲链中。
2.写码思路：先将整个框架写好，然后挨个写功能
3.选择数据结构:因为每组数据有多个，所以我们选择结构体数组

4.输入的要求
<1>.初始化：输入内存的大小和阈值minsize，初始状态下空闲分区名字为“void”。
<2>.分配：输入申请进程的名字、大小。

若可以分配，显示“分配成功！”；
若剩余空间不足，显示不分配原因“剩余空间不足，不予分配。”；
若剩余的空间通过紧凑技术，可以再分配，提示“是否通过紧凑技术，
重新划分？(Y/N)”若选择“Y”，通过紧凑技术重新划分并分配，成功后，
显示“分配成功！”若选择“N”，则输出“没有合适的剩余空间，不予分配。”
<3>.回收：输入回收进程的名字，若有相邻空闲分区，需要合并，并输出“回收成功！”；
若输入错误，提示“查无此分区！”
<4>.显示：显示当前内存的分配状态。
<0>.退出
其他：输出“输入错误，请重新输入。”

5.注意如果输入的进程没有占满内存，需要将剩下的内存也得输出来 并表示为空闲状态；

三:演示流程

四：debug(贴心杰的建议方式)

1:每实现一个功能就测试，不要等都写完了在去测试

2:整个码都码完了，那就挨个测试给出的示例，

3:如果上方还为未测试出你的bug,那么你就还是用给出的示例 但有一点，每当我们测试完一个用例后，不要退出，直接用功能 3 回收各个进程，然后再测试下一个用例

4：如果还没有，那就用PTA自带的测试用例，可以测你的格式是否正确，这道题最狗的还有是你输出的一定要跟样例一样，包括标点符号

五：上码（有些没用的注解 懒得删了 嘻嘻）

/**
	思路：
		1.解释算法：动态分区分配-首次适应算法:
				  <1>:动态分区分配是根据进程的实际需要，动态的为之分配内存的空间,
				  <2>:那么首次适应算法首次适应算法，要求空闲分区链以地址递增的次序链接，
					在分配内存时，从链首开始顺序查找，直到找到一个大小能满足要求的
					空闲分区为止，然后再按照作业的大小，
					从该分区中划出一块内存空间分给请求者，余下的空闲分区仍停留在空闲链中。
		2.写码思路：先将整个框架写好，然后挨个写功能
		3.选择数据结构:因为每组数据有多个，所以我们选择结构体数组
		
		4.输入的要求
		<1>.初始化：输入内存的大小和阈值minsize，初始状态下空闲分区名字为“void”。
		<2>.分配：输入申请进程的名字、大小。

		若可以分配，显示“分配成功！”；
		若剩余空间不足，显示不分配原因“剩余空间不足，不予分配。”；
		若剩余的空间通过紧凑技术，可以再分配，提示“是否通过紧凑技术，
		重新划分？(Y/N)”若选择“Y”，通过紧凑技术重新划分并分配，成功后，
		显示“分配成功！”若选择“N”，则输出“没有合适的剩余空间，不予分配。”
		<3>.回收：输入回收进程的名字，若有相邻空闲分区，需要合并，并输出“回收成功！”；
		若输入错误，提示“查无此分区！” 
		<4>.显示：显示当前内存的分配状态。
		<0>.退出
		其他：输出“输入错误，请重新输入。” 
		
		5.注意如果输入的进程没有占满内存，需要将剩下的内存也得输出来 并表示为空闲状态； 
	
**/ 
#include<bits/stdc++.h>
using namespace std;

struct Node{
	int id;//id号 
    string partition = "void";//分区
	int start;//起始地址 
	int end; //结束地址
	int size;//大小 
    string state = "空闲";//当前的状态 
}node[1000];

int cnt = 0;
int memory,minsize;//内存的大小和阙值 
int sumSize = 0;//记录累计的容量 

//1.初始化
void Initialize(){
	
	cin >> memory >> minsize;
	
	node[cnt].id = 1;
	node[cnt].start = 0;
	node[cnt].end = memory - 1;
	node[cnt].size = memory;
		
} 

//2.分配

//分区号 分区 起始地址 结束地址 大小 当前状态			 
//1    void    0       1023    1024 空闲

//分区号 分区 起始地址 结束地址 大小 当前状态
//1    A     0         99      100 已分配
//2    B    100       299      200 已分配
//3    C    300       449      150 已分配
void distribution(){
	
	 string processName;
	 int processSize;
	 cin >> processName >> processSize;
	 
	 if(cnt == 0){//这里主要是处理首个进程的计算 
	 	node[cnt].end = -1;
	 } 
	 
		 
	 int temp1 = memory - node[cnt].end - 1;//这里是求出容器距离上一次的结束地址 还剩的空间大小
	 
	 int temp2 = memory - sumSize;//这里是总的剩余内存的大小  
	 
	 //考虑阙值
	 int temp3 = temp1 - processSize;
	 if(temp3 <= minsize && temp3 >= 0){ //如果剩余的空间小于阙值，那么的话我们就将剩下的空间全给其进程 
	 	processSize = temp1;
	 } 
	   
	 if(temp1 >= processSize){

	     cnt++;
		 node[cnt].id = cnt;
		 node[cnt].partition = processName;
		 if(cnt == 1){
		 	node[cnt].start = 0;
		 }else{
		 	node[cnt].start = node[cnt-1].start + node[cnt-1].size;//本次的开始地址等于上次的开始地址加其大小 	
		 }
		 node[cnt].end = node[cnt].start + processSize - 1;//本次的结束地址为开始地址+其大小减一  
		 node[cnt].size = processSize;
		 node[cnt].state = "已分配"; 
		 
		 sumSize += processSize;	   
		 
		 cout << "分配成功！" << endl; 
	 }else if(temp2 >= processSize){//如果第一个条件不满足，那么的话就判断剩余的总内存，也就是紧凑 
	 	 
	 	 cout << "是否通过紧凑技术，重新划分？(Y/N)" << endl;
		  
		 char ch;
		 cin >> ch;
		 
		 /*如果我们的第一个if条件已经满足的话根本就不用考虑是否紧凑，那么好，如果我们要
		 	紧凑的话，只能说明在这个容器的前面还有空间，那么容器的前面有空间就说明发生了回收
			这时候如果我们选择 Y 那么的话我们就要更新前面的id....,如果是 N,那就不用更新  
		 */ 
		 if(ch == 'Y'){
		 
		 	//更新前面的空闲区，将非空的进程赋值给前面空的进程，紧凑出空间给新的进程	 	
		 	for(int i = 1; i <= cnt; i++) {	 	
			 	if(node[i].partition == "void"){
				
					int value =  node[i].size;//记录下来空闲区的大小 
					int j = i;
					
					bool temp = false; 
					
					for( ; j < cnt; j++){
						node[j].id = j; 
						node[j].partition = node[j+1].partition;
						node[j].start = node[j+1].start - value;
						node[j].end = node[j+1].end - value;
						node[j].size = node[j+1].size;
						node[j].state = node[j+1].state;
						
						temp = true;		
					} 
									 						
					cnt--;//这时候腾出一个空间,所以结构体数组的大小减一	
					i = 0;//再从头开始遍历空闲区，因为空闲区可能不止一个			 	
					
					if(temp == false)//说明要紧凑的空间是最后一个，那么直接跳出循环 
					break;
				
				} 
			} 
			
			//这时候考虑我们的阙值 因为当没有紧凑的时候根本没有空间来判断剩余空间的大小
		    //跟阙值的关系
			
			int laterTemp1 = memory - node[cnt].end - 1;//紧凑后的空间大小
			
			int laterTemp3 = laterTemp1 - processSize;
			
			if(laterTemp3 <= minsize){
				
				processSize = laterTemp1;
						
			} 			
			//赋值，当上方完成后这时候就腾出一个大的size 		     
		    cnt++;			
			node[cnt].id = cnt;
			node[cnt].partition = processName;
			if(cnt == 1){
		 		node[cnt].start = 0;
		 	}else{
		 		node[cnt].start = node[cnt-1].start + node[cnt-1].size;//本次的开始地址等于上次的开始地址加其大小 	
		 	}
			node[cnt].end = node[cnt].start + processSize - 1;
			node[cnt].size = processSize;
			node[cnt].state = "已分配";
			
			sumSize += processSize; 
			
		 	cout << "分配成功！" << endl;
		 		
		 }else if (ch == 'N'){
		 	cout << "没有合适的剩余空间，不予分配。" << endl;
		 }  
		  		   
	 }else{
	 	cout << "剩余空间不足，不予分配。" << endl; 	
	 }	 	 
} 

//3.回收
void recycling(){
/*
	如果发生回收的话，要将 分区改为 void,其状态为空闲，其他均不变;
	分为四种情况：
	 <1>:如果其上下均无空闲区，那么该回收的进程就单独成一行
	 <2>:如果该回收的进程上放有一个空的空闲区，那么就要和其上方进行合并，修改上方的结束地址和空间大小
	 <3>:如果该回收的进程的下方有一个空闲区，那么就修改回收进程的大小和结束地址即可
	 <4>:如果该回收的进程上下都有空闲区，那么的话我们就修改最上方的空闲区的大小和结束地址即可 
	 
*/ 

	string processName;
	int flag = 0;	
	 
	cin >> processName;
	
	for(int i = 1; i <= cnt; i++) {
		if(processName == node[i].partition){
			
			node[i].partition = "void";
			node[i].state = "空闲"; 
			
			sumSize -= node[i].size;//一旦发生回收那么这个累计的容量就要减去回收的容量 
			
			flag = 1;
			break;
		}
	} 

	if(flag == 1){
		cout << "回收成功！" << endl;
		
		/*
		  这里我们在合并空闲区的时候只需要当发现一个空闲区的时候，看看下一个分区是否是空闲区
		  如果是就合并 
		*/
		for(int i = 1; i < cnt; i++){
			
			if(node[i].partition == "void" && node[i+1].partition == "void"){
				
				node[i].size += node[i+1].size;//其大小为两个分区的和 
				node[i].end = node[i+1].end;//其结束地址为下一个空闲区的结束地址
				
				//因为分区少了一个所以要更新后面分区的id号
				int j = i+2;
				for( ; j <= cnt; j++){
					  node[j-1].id = j - 1; 
					  node[j-1].partition = node[j].partition;
					  node[j-1].start = node[j].start;
					  node[j-1].end = node[j].end;
					  node[j-1].size = node[j].size;
					  node[j-1].state = node[j].state;					   
				} 
				
				cnt--;//分区少一个 
				i = 0;//再从头开始遍历 因为可能有多个空闲区 				
			}				 
		}	
	}else{
		cout << "查无此分区！" << endl;
	} 
} 

//4.显示
void show(){
	   cout << "分区号 分区 起始地址 结束地址 大小 当前状态" << endl;
	   
	   if (cnt == 0) {
	   		for(int i = 0; i <= cnt; i++){
			   	cout << node[i].id << ' ' 
				     << node[i].partition << ' ' 
					 << node[i].start << ' ' 
					 << node[i].end << ' '
					 << node[i].size << ' '
					 << node[i].state;
	   		} 
	   } else {
	   	    //这里需要将剩余的空间也得输出一下
			
			int remainTemp = memory - node[cnt].end - 1;   
			
			//这里写大于0 是因为上方我已经处理 minsize; 
			if(remainTemp > 0){
				cnt++;
				node[cnt].id = cnt;
				node[cnt].partition = "void";
				if(cnt == 1){
		 		    node[cnt].start = 0;
		 		}else{
		 		    node[cnt].start = node[cnt-1].start + node[cnt-1].size;//本次的开始地址等于上次的开始地址加其大小 	
		 		} 
		 		node[cnt].end = node[cnt].start + remainTemp - 1;
		 		node[cnt].size = remainTemp;
		 		node[cnt].state = "空闲"; 
			}
	
			    
	
	   		for(int i = 1; i <= cnt; i++){ 
	   		
					cout << node[i].id << ' ' 
				     << node[i].partition << ' ' 
					 << node[i].start << ' ' 
					 << node[i].end << ' '
					 << node[i].size << ' '
					 << node[i].state << endl;		
	   		}    		
	   }
} 

//菜单栏 
void menu(){
	cout <<	"1.初始化" << endl; 
	cout << "2.分配" << endl;
	cout << "3.回收" << endl;
	cout << "4.显示" << endl; 
	cout << "0.退出" << endl;
	cout << "请选择：" << endl; 
} 


int main(){
	
	bool flag = true;
	menu();
	
	while(flag){
		int option;
		cin >> option;
		
		switch(option){
			
			case 1: Initialize();
					break;
					
			case 2: distribution();
					break;
			
			case 3: recycling();
					break;
			
			case 4:	show();
					break;
			
			case 0 : flag = false;
					break;		
			
			default: cout << "输入错误，请重新输入。" << endl;							
				
		}		
	}	
}



//测试分配区 
//分区号 分区 起始地址 结束地址 大小 当前状态
//1      A     0       99      100 已分配
//2      B     100     299     200 已分配
//3      C     300     449     150 已分配
//4      D     450     699     250 已分配
//5      E     700     899     200 已分配
//6      F     900     999     100 已分配


//回收A之后 

//分区号 分区 起始地址 结束地址 大小 当前状态
//1      B     0       199     200 已分配
//2      C     200     349     150 已分配
//3      D     350     599     250 已分配
//4      E     600     799     200 已分配
//5      X     800     949     150 已分配
//6      void  950     999      50 空闲



//测试回收区 
//回收 A 和 B 
//分区号 分区 起始地址 结束地址 大小 当前状态
//1      void    0       99      100 空闲
//2      void    100     299     200 空闲
//3      C     300     449     150 已分配
//4      D     450     699     250 已分配
//5      E     700     899     200 已分配
//6      F     900     999     100 已分配


//测试分配区

//A 300
//B 200
//C 200
//
//回收 A
//
//D 500 
 

宝贝！！我让你把你不喜欢的博主取关了，你咋还把我给取关了呢！！ 赶紧嘚，给我关注回来，我天天给你写博客看！！！