前言:
无链表,无指针,无解释,无检查,无正确性。
刚刚看了看算法原理,然后根据自己的理解就写了,没有具体的学过,所以不能保证一定正确。
如有错误,请各位大佬指正!
代码:
- /**
- * autor: 末语
- * created: 2022.12.1 12:20:01
- */
- #include
- using namespace std;
- #define ll long long
- struct block{
- int start;
- int size;
- int occupy;
- int id;
- int number;
- };
-
- ll ksm(ll a , ll b){
- ll kase = 1;
- while(b){
- if(b & 1)kase = kase * a ;
- a = a * a ;
- b >>= 1;
- }
- return kase ;
- }
-
- int main(){
- ios::sync_with_stdio(false);
- cin.tie(0);
- cout<<"请输入分配内存大小:"<<'\n';
-
- ll n ; // 内存大小
- cin>>n;
- bitset<64>b(n);
- for(int i = 0 ;i < n; i ++){
- if(!b[i])continue;
- b[i] = 0 ;
- if(b.to_ullong() == 0){b[i] = 1;break;}
- }
- n = b.to_ullong(); // 更正输入内存大小, 保证是2^x
- cout<<"设计内存大小:"<
'\n'; -
- int mxnumber = 0 ;
- while(((n >> mxnumber) & 1) == 0)mxnumber++;
- vector
>head(20 , vector()); // 模拟链表 - //cout<
- head[mxnumber].emplace_back(block{0 , (int)ksm(2 , mxnumber) , 0 , 1 , mxnumber});
-
- vector
>bit(20); - map
ma; - while(1){
- cout<<"请选择需要进行的操作:(0 : 添加进程 ,1:释放进程 ,2:查询进程 , 3:查看所有进程信息)"<<'\n';
-
- int op ;
- cin>>op; // op = 0 分配内存 op = 1 释放内存
-
- auto print = [&](block now){
- int start = now.start;
- int size = now.size;
- int occupy = now.occupy;
- cout<<"start:"<
" B"<<'\n'; - cout<<"block_size:"<
" B"<<'\n'; - cout<<"occupy_size:"<
" B"<<'\n'; -
- };
-
- if(op == 0){
-
- string name;
- int need ;
- cout<<"请输入进程名:"<<'\n';
- cin>>name;
- cout<<"请输入分配内存大小:"<<'\n';
- cin>>need;
- if(ma.find(name) != ma.end()){
- cout<<"该进程名已存在!"<<'\n';
- continue;
-
- }
- function
int , int )> put = [&](int i , int need ){ - if(i == 0 || ksm(2 , i - 1) < need){
- head[i].back().occupy = need;
- int id = head[i].back().id;
- ma[name] = head[i].back();
- head[i].pop_back();
- bit[i][id / 2] = bit[i][id / 2]^1;
- return ma[name];
- }
- else {
- int start = head[i].back().start;
- int size = head[i].back().size;
- int id = head[i].back().id;
- head[i - 1].emplace_back(block{start , size / 2 , 0 , id * 2 , i - 1});
- head[i - 1].emplace_back(block{start + size / 2 , size / 2 , 0 , id * 2 + 1 , i - 1});
- head[i].pop_back();
- bit[i][id / 2] = bit[i][id / 2] ^ 1;
- return put( i - 1 , need);
- }
-
- };
- bool ok = 0;
- block p ;
- for(int i = 0 ; i < mxnumber + 1; i ++){
- if(head[i].size() == 0 || ksm(2 , i) < need)continue;
- p = put(i , need);
- ok = 1;
- break;
- }
- if(ok){
-
- cout<<"成功分配!"<<'\n';
- cout<<"分配进程信息:"<<'\n';
- print(p);
- }
- else {
- cout<<"分配失败!"<<'\n';
-
- }
-
- }
- else if(op == 1){
- string name;
- cout<<"请输入需要释放的进程名"<<'\n';
- cin>>name;
- if(ma.find(name) == ma.end()){
- cout<<"无该进程!"<<'\n';
- continue;
- }
- block process = ma[name];
- function<void(block)>check = [&](block now){
- int id = now.id;
- int number = now.number;
- bit[number][id / 2] = bit[number][id / 2]^ 1;
- if(!bit[number][id / 2] && number != mxnumber){
- int target = (id % 2 == 0 ? id + 1 : id - 1);
- int start;
- for(int i = 0 ; i < head[number].size() ; i ++){
- if(head[number][i].id == target){
- start = min(head[number][i].start , now.start);
- head[number].erase(head[number].begin() + i);
- break;
- }
- }
-
-
- block fa = block{start , now.size * 2 , 0 , id / 2 , number + 1};
- check(fa);
-
- }
- else {
- head[number].emplace_back(now);
- }
- };
- check(process);
- ma.erase(ma.find(name));
-
- cout<<"释放成功!"<<'\n';
-
- }
- else if(op == 2){
- string name;
- cin>>name;
- if(ma.find(name) == ma.end()){
- cout<<"无该进程!"<<'\n';
- continue;
- }
- print(ma[name]);
- }
- else if(op == 3){
- cout<<"目前存在进程信息如下:"<<'\n';
- vector
>pre; - for(auto it : ma){
- pre.emplace_back(make_pair(it.first , it.second));
- }
- sort(pre.begin() , pre.end() , [&](pair
a , pair b){ - return a.second.start < b.second.start;
- });
-
-
- for(auto it : pre){
- cout<<"进程:"<
'\n'; -
- print(it.second);
- }
- }
- }
-
- return 0 ;
- }