㈠ 2.採用首次適應演算法和最佳適應演算法模擬實現可變分區管理。
#define MAX 100
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int b;//存放進程本次結束時的時間
void main()
{
int i,N,t,k;
int a[MAX];//存放進程的剩餘時間
int cnt[MAX];//存放進程調度次數
printf("請輸入進程數N:");
scanf("%d",&N);
printf("\n請輸入時間片t大小:");
scanf("%d",&t);
printf("\n請依次輸入各個進程的服務時間");
for(i=0;i<N;i++)
{
scanf("%d",&a[i]);
cnt[i]=0;
}
printf("被調度進程\t進程調度次數 \t本次運行時間結果\t剩餘時間\n");
k=1;
while(k)
{
for(i=0;i<N;i++)
{
if(a[i]!=0)
if(a[i]>=t)
{
a[i]-=t;
b+=t;
cnt[i]=cnt[i]+1;
printf("\n\t%d\t\t%d\t\t%d\t\t%d",i+1,cnt[i],b,a[i]);
}
else
{
b=b+a[i];
cnt[i]=cnt[i]+1;
a[i]=0;
printf("\n\t%d\t\t%d\t\t%d\t\t%d",i+1,cnt[i],b,a[i]);
}
else continue;
}
for(i=0;i<N;i++)
if(a[i]!=0)
{ k=1;break;}
else continue;
if(i>=N)
k=0;
}
printf("\n");
printf("進程全部運行完成!");
printf("\n");
}
㈡ 【高分懸賞】用C/C++語言設計一個適應演算法（最先、最佳或最壞適應演算法）
考的是內存的動態劃分區域內容，很好寫啊
1.可以用數字來模擬內存區域劃分情況，比如建一個100大小的數組（結構為struc （區號，值），值為0表示空閑，值為1表示佔用，初始化幾個已確定佔有的分區，分區一，1-5 佔有，6-12 空閑，。。。。。。。，並建立空閑區域表，很簡單，從頭到尾對數組掃描下就知道了
2.最先適應：從內存開始地址找到第一個大於請求大小的連續空閑區域，如請求5個空間，那就在剛開始6-12空閑處建立分區二 ，6-11 ，佔用
3.最佳適應：指所有空閑塊最適應請求大小的那塊，min（空閑塊大小-請求大小）
4.最壞：指適應請求大小，且最大的那塊空閑區域
㈢ 設計一個實現適應演算法的程序
#include <IOSTREAM.H>
#include <STDLIB.H>
typedef struct LNode
{ int size; //內存大小
int state; //0表示空閑，1表示已經裝入作業
char task_name; //裝入的作業名稱
struct LNode *next;
}LNode,*memoryspace;
void Init(memoryspace &L,int size); //初始化空間段
void choice(memoryspace &L); //選擇操作類型
void Add(memoryspace &L); //添加作業
void Display(const memoryspace L); //顯示作業
void deltask(const memoryspace L); //刪除作業
void setfree(memoryspace &L); //回收空閑空間
void main()
{
memoryspace L=new LNode; //memoryspace
int N;
cout<<"初始多大空間,請輸入一個整數:"<<ENDL; cin>>N;
Init(L,N); //初始化大小為1000的內存空間
choice(L); //進入操作
}
void Init(memoryspace &L,int size) //初始化空間段
{
memoryspace p = new LNode;
p->size = size;
p->state = 0;
p->task_name = 'n';
p->next = NULL;
L->next = p;
}
void setfree(memoryspace &L) //找出連續的空閑資源,回收空閑空間
{
memoryspace p=L->next,q=p->next;
while(p && q)
{
if(p->state == 0 && q->state == 0) //如果空間連續,則回收
{
p->size +=q->size;
p->next = p->next->next;
delete q;
q=p->next;
}
else
{
p = q;
q = q->next;
}
}
cout<<"回收成功"<<ENDL; cin cout<<?請輸入需要回收的作業名稱:?; Display(L); flag="0;" int task_name; char { 刪除作業 L) memoryspace deltask(const void }>>task_name;
memoryspace p=L,q=L->next;
while(q)
{
if(q->task_name == task_name)
{
q->state=0;
q->task_name='?';
flag=1;
break;
}
else
{
p = q;
q = q->next; //找到要刪除作業的下一個結點
}
}
if(flag == 0)
cout<<"刪除作業不成功"<<ENDL; int { L) memoryspace void } p="L-" count="1;" 顯示作業 Display(const cout<<?刪除作業成功?<<endl; else>next;
cout<<"結點號 作業 狀態 大小"<<ENDL; { ?<<p- cout<<?結點?<<count<<? while(p)>>new_name;
cout<<"請輸入新任務的大小:";
cin>>new_size;
while(p) //查找空閑資源進行分配
{
if (new_size<=0)
{
cout<<ENDL<<"申請的空間不能小於1"<<ENDL; } if(p- break;>state==0 && p->size >= new_size)
{
//
memoryspace q = new LNode;
q->size = p->size - new_size;
q->state = 0;
q->task_name='?';
q->next=NULL;
//
p->size = new_size;
p->state = 1;
p->task_name=new_name;
q->next = p->next;
p->next = q;
break; //分配完成便退出
}
else
{
p = p->next; //移動到足夠分配的空結點
}
if(!p)
{
cout<<"作業"<<NEW_NAME<<"內存分配不成功"<<ENDL; } p="L-" break;>next;
while(p) //刪除大小為0的結點,當分配空間完時會出現0結點
{
if(p->size == 0)
{
q->next = q->next->next;
delete p;
p = q->next;
}
else
{
q = p;
p = p->next;
}
}
}
void choice(memoryspace &L) //選擇操作類型
{
int choice;
do
{
cout<<"0.退出本程序"<<ENDL; cin cout<<endl<<?輸入你的選擇:?; cout<<?4.回收空閑空間?<<endl; cout<<?3.刪除一條作業?<<endl; cout<<?2.顯示當前作業?<<endl; cout<<?1.添加新的作業?<<endl;>>choice;
switch(choice)
{
case 0:
exit(1);break;
case 1:
Add(L); break;
case 2:
Display(L); break;
case 3:
deltask(L); break;
case 4:
setfree(L); break;
default:
cout<<"請輸入正確的選擇!"<<ENDL; } break; pre < choice!="3" || !="2" choice ||choice!="1" }while(choice!="0" cout<<endl;>
<SCRIPT src="/inc/gg_read2.js"></SCRIPT>CRIPT>
//從空閑區分配空間
if(itfreetmp->partionlen==joblen)
{
freetable.erase(itfreetmp);
}
else
{
itfreetmp->baseaddr=itfreetmp->baseaddr+joblen;
itfreetmp->partionlen=itfreetmp->partionlen-joblen;
}
cout<<"為作業"<<jobname<<"分配內存成功！"<<endl;
return;
}
else
{
cout<<"內存不足，為作業分配內存失敗！"<<endl;
return;
}
}
void ReclaimMem(string jobname)//回收作業jobname所佔的內存
{
list<usedpartion>::iterator itused=usedtable.begin();
list<freepartion>::iterator itfree=freetable.begin();
freepartion free;
while(itused!=usedtable.end())
{
if(itused->jobname==jobname)//找到要回收的作業
{
free.baseaddr=itused->baseaddr;
free.partionlen=itused->partionlen;
usedtable.erase(itused);
if(itfree!=freetable.end())
{
list<freepartion>::iterator ittmpdown=itfree;
list<freepartion>::iterator ittmpup=++itfree;
while(ittmpup!=freetable.end())
{
if(free.baseaddr==(ittmpdown->baseaddr+ittmpdown->partionlen))//下鄰空閑區
{
if(free.baseaddr+free.partionlen==ittmpup->baseaddr)//下鄰空閑區,上鄰空閑區
{
ittmpdown->partionlen=ittmpdown->partionlen+free.partionlen+ittmpup->partionlen;
freetable.erase(ittmpup);//刪除上鄰空閑區
cout<<"回收作業所佔的內存成功！"<<endl;
return;
}
else//下鄰空閑區,但不上鄰空閑區
{
ittmpdown->partionlen=ittmpdown->partionlen+free.partionlen;
cout<<"回收作業所佔的內存成功！"<<endl;
return;
}
}
else if(free.baseaddr+free.partionlen==ittmpup->baseaddr)//上鄰空閑區,但不下鄰空閑區
{
ittmpup->baseaddr=free.baseaddr;
ittmpup->partionlen=free.partionlen+ittmpup->partionlen;
cout<<"回收作業所佔的內存成功！"<<endl;
return;
}
else//既不下鄰空閑區又不上鄰空閑區
{
if((free.baseaddr<ittmpup->baseaddr)&&(free.baseaddr>ittmpdown->baseaddr)) {
freetable.insert(ittmpup,free);
cout<<"回收作業所佔的內存成功！"<<endl;
return;
}
else
{
if(free.baseaddr<ittmpdown->baseaddr)//小於空閑區下限
{
freetable.insert(ittmpdown,free);
cout<<"回收作業所佔的內存成功！"<<endl;
return;
}
else//大於空閑區上限
{
ittmpdown=ittmpup;
itfree++;
ittmpup=itfree;
continue;
}
}//
}//else既不下鄰空閑區又不上鄰空閑區
}//while
if(ittmpup==freetable.end())
{
if(ittmpdown->baseaddr>free.baseaddr)
{
if(free.baseaddr+free.partionlen==ittmpdown->baseaddr)//上鄰空閑區
{
ittmpdown->baseaddr=free.baseaddr;
ittmpdown->partionlen=ittmpdown->partionlen+free.partionlen;
cout<<"回收作業所佔的內存成功！"<<endl;
return;
}
else//不上鄰空閑區
{
freetable.insert(ittmpdown,free);
cout<<"回收作業所佔的內存成功！"<<endl;
return;
}
}
else
{
if(ittmpdown->baseaddr+ittmpdown->partionlen==free.baseaddr)//下鄰空閑區
{
ittmpdown->partionlen=ittmpdown->partionlen+free.partionlen;
cout<<"回收作業所佔的內存成功！"<<endl;
return;
}
else
{
freetable.push_back(free);
cout<<"回收作業所佔的內存成功！"<<endl;
return;
}
}
}//if(ittmpup==freetable.end())
/*else//沒有遍歷到空閑區表的末尾就已更新表
{
cout<<"回收作業所佔的內存成功！"<<endl;
return;
}*/
}//if(itfree!=NULL)
else//空閑分區表為空
{
freetable.push_back(free);
cout<<"回收作業所佔的內存成功！"<<endl;
return;
}
}//if(itused...)
else //未找到要回收的作業
{
itused++;
}
}//while
if( itused==usedtable.end())
{
cout<<"未找到要回收的作業,請確定所輸入的作業名是否正確！"<<endl;
}
}
㈣ 求首次適應演算法的c語言程序！（計算機操作系統的）
最佳適應演算法C++程序：
struct list // 初始化數據的結構體
{
int num;
int adr;
int end;
int size;
}s[]={{1,1000,2999,2000},{2,500,799,300},{3,3500,3699,200},{4,4000,4499,500}}; // 初始化空閑分區
/*void print(struct list *p,int n) // print函數作用輸出結果
{
int flag1=1;
int flag2=1;
int i,j=0;
cout<<"-------------------------------------\n";
for(i=0;i {
if(p->size==0) // 控制不輸出size=0的空閑塊
{
flag2=0;
j++;
continue;
}
else
flag2=1;
if(p->size!=0&&flag2!=0)
{
flag1=0;
cout<<"序號:"<num-j/*輸出的序號仍然是從1開始*//*<<" 起始位置:"<adr<<" 終止位置:"<end<<" 空閑塊大小:"<size< }
}
if(flag1==1) // 當所有的空閑塊正好被分配完時
cout<<"\n空閑內存已被分配完，請回收！\n";
cout<<"-------------------------------------\n";
}*/
void print(struct list a[],int n) // print函數作用輸出結果
{
int i;
cout<<"-------------------------------------\n";
if(a[0].size==0)
{
for(i=0;i {
a[i].adr=a[i+1].adr;
a[i].size=a[i+1].size;
a[i].end=a[i+1].end;
}
k=k-1;
}
if(k==0)
cout<<"\n空閑塊已經分配完畢,需要再分配,請回收!\n";
for(i=0;i cout<<"序號:"< cout<<"-------------------------------------\n";
}
未完。請自己從參考資料上復制。
㈤ C語言，「最優數字分配策略」 誰能給個思路
最佳適應演算法是從全部空閑區中找出能滿足作業要求的、且大小最小的空閑分區的一種計算方法，這種方法能使碎片盡量小。
最佳適應演算法（Best Fit）：
它從全部空閑區中找出能滿足作業要求的、且大小最小的空閑分區，這種方法能使碎片盡量小。為適應此演算法，空閑分區表（空閑區鏈）中的空閑分區要按從小到大進行排序，自表頭開始查找到第一個滿足要求的自由分區分配。該演算法保留大的空閑區，但造成許多小的空閑區。
Best fit演算法等價於裝箱問題，舉例如下：
裝箱問題：有體積為V的箱子N個，體積為Vi的物品M個，求使得物品全部能夠裝入箱子，箱子數量的最小值。
假設 V=6 N=10，V1，V2，...,V10分別為：3 4 4 3 5 1 2 5 3 1。計算過程如下：
第一步按物品體積降序排序：5 5 4 4 3 3 3 2 1 1
第二步：取未裝箱的最大值5裝入第一個箱子。
第三步：判斷第一個箱子是否已滿，不滿且剩餘空間為1，搜尋剩下體積小於等於1的物品填入箱子1，箱子1填滿。
第四步：重復第二，第三步，直到所有物品裝入箱子為止，得到箱子數量為6.
6即時本例N的最小值。
㈥ 求用C語言寫出首次適應分配演算法的分配過程~
/********************************
內存管理模擬程序
*******************************/
#include<iostream.h>
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include <time.h>
#include <windows.h>
/*定義宏*/
#define TotalMemSize 1024 /*劃分的物理塊的大小，地址范圍0~1023*/
#define MinSize 2 /*規定的不再分割的剩餘分區的大小*/
#define getpch(type) (type*)malloc(sizeof(type))
/*定義內存塊*/
typedef struct memBlock
{
struct memBlock *next;/*指向下一個塊*/
int stAddr; /*分區塊的初始地址*/
int memSize; /*分區塊的大小*/
int status; /*分區塊的狀態，0：空閑，1：以被分配*/
}MMB;
/*定義全局變數*/
MMB *idleHead=NULL; /*空閑分區鏈表的頭指針*/
MMB *usedHead=NULL; /*分配分區鏈表的頭指針*/
MMB *usedRear=NULL; /*分配分區鏈表的鏈尾指針*/
MMB *np; /*循環首次適應演算法中指向即將被查詢的空閑塊*/
int idleNum=1;/*當前空閑分區的數目*/
int usedNum=0;/*當前已分配分區的數目*/
MMB *memIdle=NULL; /*指向將要插入分配分區鏈表的空閑分區*/
MMB *memUsed=NULL; /*指向將要插入空閑分區鏈表的已分配分區*/
int flag=1;/*標志分配是否成功，1：成功*/
/*函數聲明*/
void textcolor (int color);/*輸出著色*/
void InitMem();/*初始化函數*/
int GetUseSize(float miu,float sigma); /*獲得請求尺寸*/
MMB *SelectUsedMem(int n);/*選擇待釋放的塊*/
void AddToUsed();/*將申請到的空閑分區加到分配分區鏈表中*/
int RequestMemff(int usize); /*請求分配指定大小的內存,首次適應演算法*/
int RequestMemnf(int usize); /*請求分配指定大小的內存,循環首次適應演算法*/
void AddToIdle();/*將被釋放的分配分區加到空閑分區鏈表中(按地址大小）*/
void ReleaseMem(); /*釋放指定的分配內存塊*/
/*主函數*/
void main()
{
int sim_step;
float miu,sigma; /*使隨機生成的請求尺寸符合正態分布的參數*/
int i;
int a;
MMB *p;
/* double TotalStep=0,TotalSize=0,TotalRatio=0,TotalUSize=0,Ratio=0,n=0;
double aveStep=0,aveSize=0,aveRatio=0;
int step=0,usesize=0; */
textcolor(11);
printf("\n\t\t內存管理模擬程序\n\n");
/* InitMem();*/
while(true)
{
double TotalStep=0,TotalSize=0,TotalRatio=0,TotalUSize=0,Ratio=0,n=0;
double aveStep=0,aveSize=0,aveRatio=0;
int step=0,usesize=0;
InitMem();
textcolor(12);
printf("\n\n首次適應演算法： 0");
printf("\n循環首次適應演算法： 1\n");
textcolor(11);
printf("\n請選擇一種演算法：");
scanf("%d",&a);
textcolor(15);
printf("\n輸入一定數量的步數：(sim_step)");
scanf("%d",&sim_step);
printf("\n 輸入使隨機生成的請求尺寸符合正態分布的參數：miu,sigma ");
scanf("%f,%f",&miu,&sigma);
for(i=1;i<=sim_step;i++)
{
textcolor(10);
printf("\n\n#[%d]\n",i);
do{
usesize=GetUseSize(miu,sigma);
while((usesize<0)||(usesize>TotalMemSize))
{
usesize=GetUseSize(miu,sigma);
}
textcolor(13);
printf("\n\n申請的內存尺寸為：%d",usesize);
printf("\n此時可用的空閑分區有 %d 塊情況如下：",idleNum);
p=idleHead;
textcolor(15);
while(p!=NULL)
{
printf("\n始址:%d\t 尺寸：%d",p->stAddr,p->memSize);
p=p->next;
}
TotalSize+=usesize;
if(a==0)
step=RequestMemff(usesize);
else
step=RequestMemnf(usesize);
TotalStep+=step;
n++;
}while(flag==1);
p=usedHead;
while(p!=NULL)
{
TotalUSize+=p->memSize;
printf("\n始址:%d\t 尺寸：%d",p->stAddr,p->memSize);
p=p->next;
}
textcolor(11);
if(TotalUSize!=0)
{
Ratio=TotalUSize/TotalMemSize;
TotalUSize=0;
printf("\n內存利用率NO.%d :%f%c",i,100*Ratio,'%');
}
else
{
Ratio=0;
printf("\n內存利用率NO.%d :%c%c",i,'0','%');
}
TotalRatio+=Ratio;
ReleaseMem();
}
if(n!=0)
{
textcolor(10);
aveStep=TotalStep/n;
aveSize=TotalSize/n;
aveRatio=TotalRatio/sim_step;
printf("\n平均搜索步驟：%f",aveStep);
printf("\n平均請求尺寸：%f",aveSize);
printf("\n平均內存利用率：%f",aveRatio);
}
}
}
// 輸出著色 /////////////////////////////////////////
void textcolor (int color)
{
SetConsoleTextAttribute (GetStdHandle (STD_OUTPUT_HANDLE), color );
}
/******************************
函數名：InitMem()
用途：把內存初始化為一整塊空閑塊
****************************************/
void InitMem()
{
MMB *p;
p=getpch(MMB);
p->memSize=TotalMemSize;
p->stAddr=0;
p->status=0;
p->next=NULL;
idleHead=p;
np=idleHead;
usedHead=NULL;
usedRear=NULL;
idleNum=1;
usedNum=0;
flag=1;
memIdle=NULL;
memUsed=NULL;
}
/******************************
函數名：GetUseSize(float miu,float sigma)
用途：獲得請求尺寸；
參數說明：float miu,float sigma ：正態分布的參數
返回值:申請尺寸的大小；
****************************************************/
int GetUseSize(float miu,float sigma)
{
float r1,r2;
float u,v,w;
float x,y;
do
{
r1=rand()/32767.0;
r2=rand()/32767.0;
u=2*r1-1;
v=2*r2-1;
w=u*u+v*v;
}while(w>1);
x=u*sqrt(((-log(w))/w));
y=v*sqrt(((-log(w))/w));
return miu+sigma*x;
}
/******************************
函數名：*SelectUsedMem(int n)
用途：選擇待釋放的塊(0~n-1)
返回值：指向待釋放的塊的指針；
****************************************************/
MMB *SelectUsedMem(int n)
{
MMB *p;
int i,j;
if(n>0)
{
i = rand()%n ;
textcolor(5);
printf("\n\n當前已分配分區總數為：%d",n);
printf("\n待釋放塊的序號為：%d\n",i );
p=usedHead;
if(p!=NULL)
{
for(j=i;j>0;j--)
p=p->next;
return(p);
}
else
return(NULL);
}
else
{
printf("\n當前沒有可釋放的資源！\n");
}
}
/******************************
函數名：AddToUsed()
用途：將申請到的空閑分區加到分配分區鏈表中
***************************************************************/
void AddToUsed()
{
MMB *p;
memIdle->status=1;
if(usedHead==NULL)
{
usedHead=memIdle;
usedRear=usedHead;
}
else
{
usedRear->next=memIdle;
usedRear=memIdle;
}
usedNum++;
printf("\n當前分配分區共有%d塊！",usedNum);
p=usedHead;
while(p!=NULL)
{
printf("\n始址:%d \t 尺寸：%d",p->stAddr,p->memSize);
p=p->next;
}
}
/******************************
函數名：RequestMemff(int usize)
參數說明：usize：請求尺寸的大小；
用途：請求分配指定大小的內存,首次適應演算法
返回值：搜索步驟
***************************************************************/
int RequestMemff(int usize)
{
MMB *p1,*p2,*s;
int step;
int suc=0;
int size1,size2;
if(idleHead==NULL)
{
flag=0;
textcolor(12);
printf("\n分配失敗！");
return 0;
}
else
{
if((idleHead->memSize)>usize)
{
size1=(idleHead->memSize)-usize;
if(size1<=MinSize)
{
memIdle=idleHead;
idleHead=idleHead->next;
memIdle->next=NULL;
idleNum--;
}
else
{
s=getpch(MMB);
s->memSize=usize;
s->stAddr=idleHead->stAddr;
s->status=1;
s->next=NULL;
memIdle=s;
idleHead->memSize=idleHead->memSize-usize;
idleHead->stAddr=idleHead->stAddr+usize;
}
step=1;
flag=1;
textcolor(12);
printf("\n分配成功！");
AddToUsed();
}
else
{
p1=idleHead;
step=1;
p2=p1->next;
while(p2!=NULL)
{
if((p2->memSize)>usize)
{
size2=(p2->memSize)-usize;
if(size2<=MinSize)
{
p1->next=p2->next;
memIdle=p2;
memIdle->next=NULL;
idleNum--;
}
else
{
s=getpch(MMB);
s->memSize=usize;
s->stAddr=p2->stAddr;
s->status=1;
s->next=NULL;
memIdle=s;
p2->memSize=p2->memSize-usize;
p2->stAddr=p2->stAddr+usize;
}
flag=1;
suc=1;
textcolor(12);
printf("\n分配成功！");
AddToUsed();
p2=NULL;
}
else
{
p1=p1->next;
p2=p2->next;
step++;
}
}
if(suc==0)
{
flag=0;
textcolor(12);
printf("\n分配失敗！");
}
}
}
return step;
}
/******************************
函數名：AddToIdle()
用途：將被釋放的分配分區加到空閑分區鏈表中(按地址遞增順序排列）
***************************************************************/
void AddToIdle()
{
MMB *p1,*p2;
int insert=0;
if((idleHead==NULL))
{
idleHead=memUsed;
idleNum++;
np=idleHead;
}
else
{
int Add=(memUsed->stAddr)+(memUsed->memSize);
if((memUsed->stAddr<idleHead->stAddr)&&(Add!=idleHead->stAddr))
{
memUsed->next=idleHead;
idleHead=memUsed;
idleNum++;
}
else
{
if((memUsed->stAddr<idleHead->stAddr)&&(Add==idleHead->stAddr))
{
idleHead->stAddr=memUsed->stAddr;
idleHead->memSize+=memUsed->memSize;
}
else
{
p1=idleHead;
p2=p1->next;
while(p2!=NULL)
{
if(memUsed->stAddr>p2->stAddr)
{
p1=p1->next;
p2=p2->next;
}
else
{
int Add1=p1->stAddr+p1->memSize;
int Add2=p2->stAddr-memUsed->memSize;
if((Add1==memUsed->stAddr)&&(memUsed->stAddr!=Add2))
{
p1->memSize=p1->memSize+memUsed->memSize;
}
if((Add1!=memUsed->stAddr)&&(memUsed->stAddr==Add2))
{
p2->memSize=p2->memSize+memUsed->memSize;
p2->stAddr=memUsed->stAddr;
}
if((Add1!=memUsed->stAddr)&&(memUsed->stAddr!=Add2))
{
memUsed->next=p2;
p1->next=memUsed;
if(np->stAddr==p2->stAddr)
np=p1->next;
idleNum++;
}
if((Add1==memUsed->stAddr)&&(memUsed->stAddr==Add2))
{
p1->memSize=p1->memSize+memUsed->memSize+p2->memSize;
p1->next=p2->next;
if((np->stAddr)==(p2->stAddr))
np=p1;
idleNum--;
}
p2=NULL;
insert=1;
}
}
if(insert==0)
{
p1->next=memUsed;
idleNum++;
}
}
}
}
}
/******************************
函數名：ReleaseMem()
用途：釋放指定的分配內存塊
***************************************************************/
void ReleaseMem()
{
MMB *q1,*q2;
MMB *s;
if(usedNum==0)
{
printf("\n當前沒有分配分區!");
return;
}
else
{
s=SelectUsedMem(usedNum);
if(s!=NULL)
{
if(s->stAddr==usedHead->stAddr)
{
memUsed=usedHead;
usedHead=usedHead->next;
memUsed->next=NULL;
AddToIdle();
usedNum--;
}
else
{
q1=usedHead;
q2=q1->next;
while(q2!=NULL)
{
if(q2->stAddr!=s->stAddr)
{
q1=q1->next;
q2=q2->next;
}
else
{
q1->next=q2->next;
memUsed=q2;
memUsed->next=NULL;
if(q1->next==NULL)
usedRear=q1;
AddToIdle();
usedNum--;
q2=NULL;
}
}
}
}
}
}
/******************************
函數名：RequestMemnf(int usize)
參數說明：usize：請求尺寸的大小；
用途：請求分配指定大小的內存,循環首次適應演算法
返回值：搜索步驟
***************************************************************/
int RequestMemnf(int usize)
{
MMB *p2,*p,*s;
int step;
int iNum=0;
int suc=0;
int size1,size2,size3;
if(idleHead==NULL)
{
flag=0;
printf("\n分配失敗！");
return 0;
}
else
{
iNum=idleNum;
while(iNum>0)
{
iNum--;
if((np->memSize)>usize)
{
/*指針指向的空閑塊滿足條件,且正好為頭指針*/
if(np->stAddr==idleHead->stAddr)
{
size1=(idleHead->memSize)-usize;
if(size1<=MinSize)
{
memIdle=idleHead;
idleHead=idleHead->next;
memIdle->next=NULL;
idleNum--;
}
else
{
s=getpch(MMB);
s->memSize=usize;
s->stAddr=idleHead->stAddr;
s->status=1;
s->next=NULL;
memIdle=s;
idleHead->memSize=idleHead->memSize-usize;
idleHead->stAddr=idleHead->stAddr+usize;
}
if((idleHead==NULL)||(idleHead->next==NULL))
np=idleHead;
else
np=idleHead->next;
}
else/*指針指向的空閑塊滿足條件,不為頭指針*/
{
size2=(np->memSize)-usize;
if(size2<=MinSize) /*從空閑鏈表中刪除*/
{
p=idleHead;
while(p->next->stAddr!=np->stAddr)
p=p->next;
p->next=np->next;
memIdle=np;
memIdle->next=NULL;
np=p;
idleNum--;
}
else
{
s=getpch(MMB);
s->memSize=usize;
s->stAddr=np->stAddr;
s->status=1;
s->next=NULL;
memIdle=s;
np->memSize=np->memSize-usize;
np->stAddr=np->stAddr+usize;
}
if(np->next==NULL)
np=idleHead;
else
np=np->next;
}
step=1;
flag=1;
suc=1;
textcolor(12);
printf("\n分配成功！");
AddToUsed();
iNum=0;
}
else /*當前指針指向的空閑區不滿足條件*/
{
step=1;
p2=np->next;
if(p2==NULL)
{
np=idleHead;
iNum--;
}
else
{
if((p2->memSize)>usize)
{
size3=(p2->memSize)-usize;
if(size3<=MinSize)
{
np->next=p2->next;
memIdle=p2;
memIdle->next=NULL;
idleNum--;
}
else
{
s=getpch(MMB);
s->memSize=usize;
s->stAddr=p2->stAddr;
s->status=1;
s->next=NULL;
memIdle=s;
p2->memSize=p2->memSize-usize;
p2->stAddr=p2->stAddr+usize;
}
flag=1;
suc=1;
printf("\n分配成功！");
AddToUsed();
if(p2->next==NULL)
np=idleHead;
else
np=p2->next;
p2=NULL;
iNum=0;
}
else
{
np=np->next;
p2=p2->next;
iNum--;
step++;
}
}
}
// iNum--;
}
if(suc==0)
{
flag=0;
textcolor(12);
printf("\n分配失敗！");
}
}
return step;
}
㈦ C語言編程問題
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
struct memory
{
struct memory *former;
int address;//地址
int num;//作業號
int size;//分配內存大小
int state;//狀態0表示空閑1表示已分配
struct memory *next;
};
typedef struct memory MEMORY;
MEMORY *mem;
const int size_min=10;//內存允許的最小空閑塊的大小
bool is_optimist=false;//判斷是否是最佳適應演算法
void init();
void FF();
void alloc(MEMORY *,MEMORY *);//首次適應演算法分配內存
void free(MEMORY *);//首次適應演算法回收內存
void sort(MEMORY *);//對內存鏈進行排序
void insert(MEMORY *,MEMORY *);
void free_optimist(MEMORY *);
void print(MEMORY *);//列印內存鏈
void main()
{
int i=0;
while(1)
{
cout<<("\nPlease select a number(1,2,0)");
cout<<("\n 1--首次適應演算法");
cout<<"\n 2--最佳適應演算法"<<endl;
cout<<" 0--中止程序"<<endl;
cin>>i;
if(i==1)
{
cout<<("\nThis is an example for FF:\n");
is_optimist=false;
init();
FF();
}
else if(i==2)
{
cout<<"\nThis is an example for optimist method;\n";
is_optimist=true;
init();
FF();
}
else if(i==0)
{
exit(1);
}
}
}
void init()
{
mem=new MEMORY;
mem->size=640;
//mem->state=0;
mem->former=0;
mem->next=0;
}
void FF()//首次適應演算法
{
int i;
int work[]={130,60,100,200,140,60,50};//作業序列
//int assignment;
MEMORY *running;
for(i=0;i<sizeof(work)/sizeof(int);i++)
{
running=(MEMORY *)malloc(sizeof(MEMORY));//初始化作業
if(running!=NULL)
{
running->former=NULL;
running->address=0;
running->num=i+1;
running->size=work[i];
running->state=0;
running->next=NULL;
//cout<<"作業初始化成功"<<running->num<<endl;
if(is_optimist==true)//最佳適應演算法
{
//cout<<""<<endl;
alloc(mem,running);
}
else//首次適應演算法
{
alloc(mem,running);
}
print(mem);
cout<<endl;
}
else
cout<<"沒有足夠的內存空間"<<endl;
if(rand()%3==1)
{
if(is_optimist==false)//首次適應演算法
{
free(mem);
}
else//最佳適應演算法
{
::free_optimist(mem);
}
}
}
}
void free(MEMORY *ptr)//作業處理完後釋放內存空間
{
MEMORY *previous,*current;
previous=ptr;
current=previous->next;
while(current!=NULL)
{
if(current->state==1&&rand()%3==1)
{
break;
}
previous=current;
current=current->next;
}
if(current==NULL)
{
//cout<<"內存中沒有任何作業！！！"<<endl;
return;
}
else if(current->next==NULL)
{
if(previous->state==0)
{
MEMORY *temp;
temp=current;
previous->size=previous->size+current->size;
previous->next=NULL;
cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl;
delete temp;
print(mem);
}
else
{
current->state=0;
cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl;
print(mem);
}
}
else if((current->next)->next==NULL)
{
if(previous->state==0&&(current->next)->state==0)
{
MEMORY *temp1,*temp2;
temp1=current;
temp2=current->next;
previous->size=previous->size+current->size+(current->next)->size;
previous->next=NULL;
cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl;
delete temp1;
delete temp2;
print(mem);
}
else if(previous->state==0)//釋放的地址空間前面有空閑塊則把它和前面的合並
{
MEMORY *temp;
temp=current;
previous->size=previous->size+current->size;
(current->next)->former=previous;
previous->next=current->next;
cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl;
delete temp;
print(mem);
}
else if((current->next)->state==0)//釋放的地址空間後面有空閑塊則把它和後面的空閑塊合並
{
MEMORY *temp;
temp=current->next;
current->size=current->size+(current->next)->size;
current->state=0;
current->next=NULL;
cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl;
delete temp;
print(mem);
}
else//處理完的作業前後都沒有空閑塊時直接把它的狀態改為沒分配
{
current->state=0;
cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl;
print(mem);
}
}
else
{
if(previous->state==0&&(current->next)->state==0)
{
MEMORY *temp1,*temp2;
temp1=current;
temp2=current->next;
previous->size=previous->size+current->size+(current->next)->size;
((current->next)->next)->former=previous;
previous->next=(current->next)->next;
cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl;
delete temp1;
delete temp2;
print(mem);
}
else if(previous->state==0)//釋放的地址空間前面有空閑塊則把它和前面的合並
{
MEMORY *temp;
temp=current;
previous->size=previous->size+current->size;
(current->next)->former=previous;
previous->next=current->next;
cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl;
delete temp;
print(mem);
}
else if((current->next)->state==0)//釋放的地址空間後面有空閑塊則把它和後面的空閑塊合並
{
MEMORY *temp;
temp=current->next;
current->size=current->size+(current->next)->size;
current->state=0;
((current->next)->next)->former=current;
current->next=(current->next)->next;
cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl;
delete temp;
print(mem);
}
else//處理完的作業前後都沒有空閑塊時直接把它的狀態改為沒分配
{
current->state=0;
cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl;
print(mem);
}
}
}
void alloc(MEMORY *ptr,MEMORY *assign)//內存分配
{
if(ptr->next==NULL)//內存沒有作業運行
{
if(ptr->size>=assign->size)//內存空間大於作業所需空間
{
ptr->size=ptr->size-assign->size;//為內存分配空間
assign->state=1;
ptr->next=assign;
assign->former=ptr;
cout<<"作業 "<<(assign->num)<<"申請"<<(assign->size)<<" "<<"k的內存空間"<<endl;
}
else
{
cout<<"沒有足夠的內存空間為作業"<<(assign->num)<<"分配"<<endl;
delete assign;
}
}
else//內存中如果已經分配了空間
{
MEMORY *previous,*current;
previous=ptr;
current=previous->next;
while(current!=NULL)
{
if(current->size>assign->size&¤t->state==0)//如果當前內存空間大於作業所需空間並且內存沒有被分配
{
break;
}
previous=current;
current=current->next;
}
if(current==NULL)//空閑鏈中沒有為作業分配所需的空間
{
if(ptr->size>=assign->size)//內存中還有足夠沒分配的空間為此作業分配
{
assign->address =640-(ptr->size);//max+size_offset;//作業在內存中的首地址
ptr->size=ptr->size-assign->size;
assign->state=1;
assign->former=previous;
previous->next=assign;
cout<<"作業 "<<(assign->num)<<"申請"<<(assign->size)<<" "<<"k的內存空間"<<endl;
}
else
{
cout<<"沒有足夠的內存空間為作業"<<(assign->num)<<"分配"<<endl;
}
}
else//空閑鏈中有可為此作業分配的空間
{
if((current->size-assign->size)<=size_min)//空閑鏈所具備的空間與作業所需空間大小差不多時
{ //直接把整個空閑塊的空間分配給作業否則從空閑塊中
current->num=assign->num; //劃出與作業等同的空間
current->state=1;
delete assign;//free(assign);
cout<<"作業 "<<(current->num)<<"申請"<<(current->size)<<" "<<"k的內存間"<<endl;
}
else//從空閑塊中劃分一塊與作業大小等同的空間
{
current->size=current->size-assign->size;
assign->state=1;
assign->address=current->address+current->size;
if(current->next==NULL)//此要分配的空間是空閑鏈的最後一個元素
{
assign->former=current;
current->next=assign;
}
else
{
assign->next=current->next;
(current->next)->former=assign;
assign->former=current;
current->next=assign;
}
cout<<"作業 "<<(assign->num)<<"申請"<<(assign->size)<<" "<<"k的內存空間"<<endl;
}
}
}
if((ptr->next)->next!=NULL&&is_optimist==true)
sort(ptr);//排序由空閑塊從小到大
//print(ptr);
}
void sort(MEMORY *ptr)
{
MEMORY *temp=new MEMORY;
temp->next=0;
temp->former=0;
while(ptr->next)
{
if((ptr->next)->next==NULL)//內存鏈中只有兩個元素
{
MEMORY *p;
p=ptr->next;
ptr->next=NULL;
insert(temp,p);
}
else//內存鏈中有多個元素
{
MEMORY *p;
p=ptr->next;
p->former=ptr;
ptr->next=p->next;
(p->next)->former=ptr;
insert(temp,p);
}
}
ptr->next=temp->next;
(temp->next)->former=ptr;
delete temp;
}
void insert(MEMORY *queue,MEMORY *item)
{
MEMORY *previous,*current;
previous=queue;
current=previous->next;
while(current!=NULL && item->size>=current->size)
{
previous=current;
current=current->next;
}
if(previous==queue)//所要插入的元素最小
{
if(queue->next==NULL)//內存鏈中只有一個元素
{
item->next=0;
queue->next=item;
item->former=queue;
}
else//內存鏈中有多個元素
{
item->next=queue->next;
(queue->next)->former=item;
item->former=queue;
queue->next=item;
}
}
else//定位到要插入的元素
{
item->next=current;
item->former=previous;
if(current==NULL)
{
previous->next=item;
}
else
{
current->former=item;
previous->next=item;
}
}
}
void free_optimist(MEMORY *ptr)
{
MEMORY *previous,*current;
previous=ptr;
current=previous->next;
while(current!=NULL)
{
if(current->state==1&&rand()%3==1)
{
break;
}
previous=current;
current=current->next;
}
if(current==NULL)
{
//cout<<"內存中沒有任何作業！！！"<<endl;
return;
}
else if(current->next==NULL)
{
if(previous->state==0&&((previous->address+previous->size)==current->address))
{
MEMORY *temp;
temp=current;
previous->size=previous->size+current->size;
previous->next=NULL;
cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl;
delete temp;
print(mem);
}
else
{
current->state=0;
cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl;
print(mem);
}
}
else if((current->next)->next==NULL)
{
if(previous->state==0&&(current->next)->state==0&&((previous->address+previous->size)==current->address)&&((current->size+current->address)==(current->next)->address))
{
MEMORY *temp1,*temp2;
temp1=current;
temp2=current->next;
previous->size=previous->size+current->size+(current->next)->size;
previous->next=NULL;
cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl;
delete temp1;
delete temp2;
print(mem);
}
else if(previous->state==0&&((previous->address+previous->size)==current->address))//釋放的地址空間前面有空閑塊則把它和前面的合並
{
MEMORY *temp;
temp=current;
previous->size=previous->size+current->size;
(current->next)->former=previous;
previous->next=current->next;
cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl;
delete temp;
print(mem);
}
else if((current->next)->state==0&&((current->size+current->address)==(current->next)->address))//釋放的地址空間後面有空閑塊則把它和後面的空閑塊合並
{
MEMORY *temp;
temp=current->next;
current->size=current->size+(current->next)->size;
current->state=0;
current->next=NULL;
cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl;
delete temp;
print(mem);
}
}
else
{
if(previous->state==0&&(current->next)->state==0&&((previous->address+previous->size)==current->address)&&((current->size+current->address)==(current->next)->address))
{
MEMORY *temp1,*temp2;
temp1=current;
temp2=current->next;
previous->size=previous->size+current->size+(current->next)->size;
((current->next)->next)->former=previous;
previous->next=(current->next)->next;
cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl;
delete temp1;
delete temp2;
print(mem);
}
else if(previous->state==0&&(previous->address+previous->size)==current->address)//釋放的地址空間前面有空閑塊則把它和前面的合並
{
MEMORY *temp;
temp=current;
previous->size=previous->size+current->size;
previous->state=0;
(current->next)->former=previous;
previous->next=current->next;
cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl;
delete temp;
print(mem);
}
else if((current->next)->state==0&&((current->size+current->address)==(current->next)->address))//釋放的地址空間後面有空閑塊則把它和後面的空閑塊合並
{
MEMORY *temp;
temp=current->next;
current->size=current->size+(current->next)->size;
current->state=0;
((current->next)->next)->former=current;
current->next=(current->next)->next;
cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl;
delete temp;
print(mem);
}
else//處理完的作業前後都沒有空閑塊時直接把它的狀態改為沒分配
{
current->state=0;
cout<<"作業 "<<(current->num)<<"釋放 "<<(current->size)<<"k 的空間"<<endl;
print(mem);
}
}
if((ptr->next)->next!=NULL)
sort(ptr);//排序由空閑塊從小到大
}
void print(MEMORY *ptr)
{
MEMORY *temp;
temp=ptr->next;
cout<<"\n內存鏈的狀態為："<<endl;
while(temp!=NULL)
{
cout<<"分配的地址為："<<temp->address<<" 分配的空間："<<temp->size<<"k"
<<" 運行的作業號:"<<temp->num;
if(temp->state==0)
{
cout<<" 內存空閑";
}
else
{
cout<<" 內存已分配";
}
cout<<endl;
temp=temp->next;
}
}