最差適應演算法C語言演示

㈠ 求用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<stdio.h>
#defineMAX1000

intquick(int*a,intl,intr,intlength)
{
intcounter=0,i;
a[0]=a[l];
while(l<r)
{
while(l<r&&a[0]<=a[r])
r--;
a[l]=a[r];
while(l<r&&a[0]>a[l])
l++;
a[r]=a[l];
}
a[l]=a[0];
printf("Step%d:",++counter);
for(i=1;i<length;i++)
printf("%d",a[i]);
printf("%d
",a[length]);
returnl;
}

voidquicksort(int*a,intl,intr,intlength)//快速排序
{
intp;
if(l<r)
{
p=quick(a,l,r,length);
quicksort(a,l,p-1,length);
quicksort(a,p+1,r,length);
}
}

voidheap(int*a,intlength,inti)
{
ints=i,t;
if(2*i<=length&&a[2*i]>a[s])
s=2*i;
if(2*i+1<=length&&a[2*i+1]>a[s])
s=2*i+1;
if(s!=i)
{
t=a[i];
a[i]=a[s];
a[s]=t;
heap(a,length,s);
}
}

voidheapsort(int*a,intlength)//堆排序
{
inti,t,counter=0,k=length;
for(i=length/2;i>=1;i--)
heap(a,length,i);
while(length>1)
{
t=a[1];
a[1]=a[length];
a[length]=t;
heap(a,--length,1);
printf("Step%d:",++counter);
for(i=1;i<k;i++)
printf("%d",a[i]);
printf("%d
",a[k]);
}
}

voidinsertsort(int*a,intlength)//插入排序
{
inti,j,t,k,counter=0;
if(length==1)
{
printf("Step%d:%d
",++counter,a[1]);
return;
}
for(i=2;i<=length;i++)
{
t=a[i];
for(j=i-1;j>0&&a[j]>=t;j--);
for(k=i-1;k>=j+1;k--)
a[k+1]=a[k];
a[k+1]=t;
printf("Step%d:",++counter);
for(k=1;k<length;k++)
printf("%d",a[k]);
printf("%d
",a[length]);
}
}

intmain()
{
intn,i;
inta[MAX];
while(scanf("%d",&n)&&n)
{
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
quicksort(a,1,n,n);
}
return0;
}

㈢ 採用c語言實現首次適應演算法完成主存空間的分配和回收 急

有沒有具體的要求，比方說數據結構方面，我這有一個，你可以參考參考
#include"stdio.h"
#include"stdlib.h"
#define
n
10
/*假定系統允許的最大作業為n，假定模擬實驗中n值為10*/
#define
m
10
/*假定系統允許的空閑區表最大為m，假定模擬實驗中m值為10*/
#define
minisize
100
struct{
float
address;
/*已分分區起始地址*/
float
length;
/*已分分區長度，單位為位元組*/
int
flag;
/*已分配區表登記欄標志，用"0"表示空欄目*/
}used_table[n];
/*已分配區表*/
struct{
float
address;
/*空閑區起始地址*/
float
length;
/*空閑區長度，單位為位元組*/
int
flag;
/*空閑區表登記欄標志，用"0"表示空欄目，用"1"表示未分配*/
}free_table[m];
/*空閑區表*/
void
main(
)
{
int
i,a;
void
allocate(char
str,float
leg);//分配主存空間函數
void
reclaim(char
str);//回收主存函數
float
xk;
char
J;/*空閑分區表初始化：*/
free_table[0].address=10240;
free_table[0].length=102400;
free_table[0].flag=1;
for(i=1;i<m;i++)
free_table[i].flag=0;/*已分配表初始化：*/
for(i=0;i<n;i++)
used_table[i].flag=0;
while(1)
{
printf("\n選擇功能項（0-退出,1-分配主存,2-回收主存,3-顯示主存）\n");
printf("選擇功項(0~3)
:");
scanf("%d",&a);
switch(a)
{
case
0:
exit(0);
/*a=0程序結束*/
case
1:
/*a=1分配主存空間*/printf("輸入作業名J和作業所需長度xk:
");
scanf("%*c%c%f",&J,&xk);
allocate(J,xk);/*分配主存空間*/
break;
case
2:
/*a=2回收主存空間*/printf("輸入要回收分區的作業名");
scanf("%*c%c",&J);reclaim(J);/*回收主存空間*/
break;
case
3:
/*a=3顯示主存情況*//*輸出空閑區表和已分配表的內容*/
printf("輸出空閑區表：\n起始地址
分區長度
標志\n");
for(i=0;i<m;i++)
printf("%6.0f%9.0f%6d\n",free_table[i].address,free_table[i].length,
free_table[i].flag);
printf("
按任意鍵,輸出已分配區表\n");
getchar();
printf("
輸出已分配區表：\n起始地址
分區長度
標志\n");
for(i=0;i<n;i++)
if(used_table[i].flag!=0)
printf("%6.0f%9.0f%6c\n",used_table[i].address,used_table[i].length,
used_table[i].flag);
else
printf("%6.0f%9.0f%6d\n",used_table[i].address,used_table[i].length,
used_table[i].flag);
break;
default:printf("沒有該選項\n");
}/*case*/
}/*while*/
}/*主函數結束*/
int
uflag;//分配表標志
int
fflag;//空閑表標志
float
uend_address;
float
fend_address;
void
allocate(char
str,float
leg)
{
uflag=0;fflag=0;
int
k,i;float
ressize;
for(i=0;i<m;i++)
{
if(free_table[i].flag==1
&&
free_table[i].length>=leg)
{
fflag=1;break;
}
}
if(fflag==0)
printf("沒有滿足條件的空閑區\n");
else
{
ressize=free_table[i].length-leg;
for(k=0;k<n;k++)
{
if(used_table[k].flag==0)
{
if(ressize<minisize)//剩餘塊過小
{
used_table[k].length=free_table[i].length;
used_table[k].address=free_table[i].address;
used_table[k].flag=str;
free_table[i].length=0;
free_table[i].flag=0;
break;
}
else
{
used_table[k].address=free_table[i].address+ressize;
used_table[k].flag=str;
used_table[k].length=leg;
free_table[i].length=ressize;
break;
}
}
}//for結束
}
}
void
reclaim(char
str)
{
uflag=0;fflag=0;
int
k,i;
for(k=0;k<n;k++)
{
if(used_table[k].flag==str)
{
uflag=1;break;
}
}
if(uflag==0)
printf("\n找不到該作業!\n");
else
{
for(i=0;i<m;i++)
{
uend_address=used_table[k].address+used_table[k].length;
fend_address=free_table[i].address+free_table[i].length;
if(used_table[k].address==fend_address)//上鄰
{
fflag=1;
free_table[i].length=free_table[i].length+used_table[k].length;
free_table[i].flag=1;
used_table[k].flag=0;
used_table[k].length=0;
used_table[k].address=0;
printf("\n已回收!\n");
break;
}
else
{
if(free_table[i].address==uend_address)//下鄰
{
fflag=1;
free_table[i].address=used_table[k].address;
free_table[i].length=free_table[i].length+used_table[k].length;
free_table[i].flag=1;
used_table[k].flag=0;
used_table[k].length=0;
used_table[k].address=0;
printf("\n已回收!\n");
break;
}
}
}//for結束
if(fflag==0)
{
i=0;
for(i=0;i<m;i++)
{
if(free_table[i].flag==0)
{
free_table[i].address=used_table[k].address;
free_table[i].length=used_table[k].length;
free_table[i].flag=1;
used_table[k].length=0;
used_table[k].flag=0;
used_table[k].address=0;
break;
}
}
printf("\n已回收!\n");
}
}
}

㈣ 最差適配的平均查找長度

n個節點的二叉排序樹在最壞的情況下的平均查找長度為（n+1）/2。

二叉排序樹每個結點的C（i）為該結點的層次數。最壞情況下，當先後插入的關鍵字有序時，構成的二叉排序樹蛻變為單支樹，樹的深度為其平均查找長度（n+1）/2（和順序查找相同），最好的情況是二叉排序樹的形態和折半查找的判定樹相同，其平均查找長度和log 2 （n）成正比。

計算方法

最差適應演算法（Worst Fit）為適應此演算法，空閑分區表（空閑區鏈）中的空閑分區要按大小從大到小進行排序，自表頭開始查找到第一個滿足要求的自由分區分配。該演算法保留小的空閑區，盡量減少小的碎片產生。

最差適應演算法，也稱最差適配演算法，它從全部空閑區中找出能滿足作業要求的、且大小最大的空閑分區，從而使鏈表中的結點大小趨於均勻，適用於請求分配的內存大小范圍較窄的系統。

㈤ C＋＋　最壞適應演算法原代碼

考的是內存的動態劃分區域內容，很好寫啊
1.可以用數字來模擬內存區域劃分情況，比如建一個100大小的數組（結構為struc （區號，值），值為0表示空閑，值為1表示佔用，初始化幾個已確定佔有的分區，分區一，1-5 佔有，6-12 空閑，。。。。。。。，並建立空閑區域表，很簡單，從頭到尾對數組掃描下就知道了
2.最先適應：從內存開始地址找到第一個大於請求大小的連續空閑區域，如請求5個空間，那就在剛開始6-12空閑處建立分區二 ，6-11 ，佔用
3.最佳適應：指所有空閑塊最適應請求大小的那塊，min（空閑塊大小-請求大小）
4.最壞：指適應請求大小，且最大的那塊空閑區域

㈥ 【高分懸賞】用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語言實現七種排序演算法的演示代碼是什麼

（1）「冒泡法」
冒泡法大家都較熟悉。其原理為從a[0]開始，依次將其和後面的元素比較,若a[0]>a[i]，則交換它們，一直比較到a[n]。同理對a[1],a[2],...a[n-1]處理，即完成排序。下面列出其代碼：
void
bubble(int
*a,int
n)
/*定義兩個參數：數組首地址與數組大小*/
{
int
i,j,temp;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
/*注意循環的上下限*/
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
冒泡法原理簡單，但其缺點是交換次數多，效率低。
下面介紹一種源自冒泡法但更有效率的方法「選擇法」。
（2）「選擇法」
選擇法循環過程與冒泡法一致，它還定義了記號k=i,然後依次把a[k]同後面元素比較，若a[k]>a[j],則使k=j.最後看看k=i是否還成立，不成立則交換a[k],a[i],這樣就比冒泡法省下許多無用的交換，提高了效率。
void
choise(int
*a,int
n)
{
int
i,j,k,temp;
for(i=0;i<n-1;i++)
{
k=i;
/*給記號賦值*/
for(j=i+1;j<n;j++)
if(a[k]>a[j])
k=j;
/*是k總是指向最小元素*/
if(i!=k)
{
/*當k!=i是才交換，否則a[i]即為最小*/
temp=a[i];
a[i]=a[k];
a[k]=temp;
}
}
}
選擇法比冒泡法效率更高，但說到高效率，非「快速法」莫屬，現在就讓我們來了解它。
（3）「快速法」
快速法定義了三個參數，（數組首地址*a,要排序數組起始元素下標i,要排序數組結束元素下標j).
它首先選一個數組元素（一般為a[(i+j)/2],即中間元素）作為參照，把比它小的元素放到它的左邊，比它大的放在右邊。然後運用遞歸，在將它左，右兩個子數組排序，最後完成整個數組的排序。下面分析其代碼：
void
quick(int
*a,int
i,int
j)
{
int
m,n,temp;
int
k;
m=i;
n=j;
k=a[(i+j)/2];
/*選取的參照*/
do
{
while(a[m]<k&&m<j)
m++;
/*
從左到右找比k大的元素*/
while(a[n]>k&&n>i)
n--;
/*
從右到左找比k小的元素*/
if(m<=n)
{
/*若找到且滿足條件，則交換*/
temp=a[m];
a[m]=a[n];
a[n]=temp;
m++;
n--;
}
}while(m<=n);
if(m<j)
quick(a,m,j);
/*運用遞歸*/
if(n>i)
quick(a,i,n);
}
（4）「插入法」
插入法是一種比較直觀的排序方法。它首先把數組頭兩個元素排好序，再依次把後面的元素插入適當的位置。把數組元素插完也就完成了排序。
void
insert(int
*a,int
n)
{
int
i,j,temp;
for(i=1;i<n;i++)
{
temp=a[i];
/*temp為要插入的元素*/
j=i-1;
while(j>=0&&temp<a[j])
{
/*從a[i-1]開始找比a[i]小的數，同時把數組元素向後移*/
a[j+1]=a[j];
j--;
}
a[j+1]=temp;
/*插入*/
}
}
（5）「shell法」
shell法是一個叫
shell
的美國人與1969年發明的。它首先把相距k(k>=1)的那幾個元素排好序，再縮小k值（一般取其一半），再排序，直到k=1時完成排序。下面讓我們來分析其代碼：
void
shell(int
*a,int
n)
{
int
i,j,k,x;
k=n/2;
/*間距值*/
while(k>=1)
{
for(i=k;i<n;i++)
{
x=a[i];
j=i-k;
while(j>=0&&x<a[j])
{
a[j+k]=a[j];
j-=k;
}
a[j+k]=x;
}
k/=2;
/*縮小間距值*/
}
}
上面我們已經對幾種排序法作了介紹，現在讓我們寫個主函數檢驗一下。
#include<stdio.h>
/*別偷懶，下面的"..."代表函數體，自己加上去哦！*/
void
bubble(int
*a,int
n)
{
...
}
void
choise(int
*a,int
n)
{
...
}
void
quick(int
*a,int
i,int
j)
{
...
}
void
insert(int
*a,int
n)
{
...
}
void
shell(int
*a,int
n)
{
...
}
/*為了列印方便，我們寫一個print吧。*/[code]
void
print(int
*a,int
n)
{
int
i;
for(i=0;i<n;i++)
printf("%5d",a[i]);
printf("\n");
}
main()
{
/*為了公平，我們給每個函數定義一個相同數組*/
int
a1[]={13,0,5,8,1,7,21,50,9,2};
int
a2[]={13,0,5,8,1,7,21,50,9,2};
int
a3[]={13,0,5,8,1,7,21,50,9,2};
int
a4[]={13,0,5,8,1,7,21,50,9,2};
int
a5[]={13,0,5,8,1,7,21,50,9,2};
printf("the
original
list:");
print(a1,10);
printf("according
to
bubble:");
bubble(a1,10);
print(a1,10);
printf("according
to
choise:");
choise(a2,10);
print(a2,10);
printf("according
to
quick:");
quick(a3,0,9);
print(a3,10);
printf("according
to
insert:");
insert(a4,10);
print(a4,10);
printf("according
to
shell:");
shell(a5,10);
print(a5,10);
}

㈨ 最壞適應演算法 c語言

/**------------------------------------------------------
進入程序後可以根據菜單選項進入不同的模塊
1.使用首次適應演算法分配空間
2.使用最佳適應演算法分配空間
3.釋放一塊空間
4.顯示內存分配情況
5.退出系統
----------------------------------------------------------**/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>

#define MEMSIZE 100 /*定義內存大小為100*/
#define MINSIZE 2 /*如果小於此值 將不再分割內存*/

typedef struct _MemoryInfomation{/* 內存空間分區表 結構*/
int start; /*起始地址*/
int size; /*大小*/
char info; /*狀態 F:空閑(Free) U:佔用(Used) E 結束(end)*/
}MEMINFO;

MEMINFO MemList[MEMSIZE]; //內存空間信息表

void Display();

/*--------------------------------------------------------
函數名:InitALL()
功 能:初始化所有變數
--------------------------------------------------------*/
void InitAll(){
int i;
MEMINFO temp={0,0,'e'};
for(i=0;i<MEMSIZE;i++) //初始化空間信息表
MemList[i]=temp;
MemList[0].start=0; //起始地址為0
MemList[0].size=MEMSIZE;//空間初始為最大的
MemList[0].info='f'; //狀態為空閑
}
/*--------------------------------------------------------
函數名:FirstFit_new()
功 能:首次適應演算法分配內存
--------------------------------------------------------*/
void FirstFit_new(){
int i,j,size;
char temp[10];
printf("FirstFit_new:How many MEMORY requir?");
gets(temp);
size=atoi(temp); //將字元串轉化為整數
for(i=0; i < MEMSIZE-1 && MemList[i].info != 'e';i++) //到了空間尾且沒有空間分配
{
if(MemList[i].size >= size && MemList[i].info=='f') //滿足所需要的大小，且是空閑空間
{
if(MemList[i].size - size <= MINSIZE) //如果小於規定的最小差則將整個空間分配出去
MemList[i].info='u'; //標志為使用
else
{
for(j = MEMSIZE-2; j > i; j--) //將i後的信息表元素後移
{
MemList[j+1]=MemList[j];
}
//將i分成兩部分，使用低地址部分
MemList[i+1].start= MemList[i].start+size;
MemList[i+1].size = MemList[i].size-size;
MemList[i+1].info='f';
MemList[i].size=size;
MemList[i].info='u';
}
break;
}
}
if(i == MEMSIZE-1 || MemList[i].info=='e') //沒有找到符合分配的空間
{
printf("Not Enough Memory!!\n");
getchar();
}
Display();
}

/*--------------------------------------------------------
函數名:BestFit_new()
功 能:最佳適應演算法分配內存
--------------------------------------------------------*/
void BestFit_new()
{
int i,j,k,flag,size;
char temp[10];
printf("BestFit_new How many MEMORY requir?");
gets(temp);
size=atoi(temp); //將字元串轉化為整數
j=0;
flag=0; //標志是否有合適的空間分配，0無，1有
k=MEMSIZE; //用來保存滿足要求的最小空間

for(i=0;i<MEMSIZE-1 && MemList[i].info!='e';i++)
{
if(MemList[i].size >= size && MemList[i].info == 'f') //符合要求
{
flag=1;
if(MemList[i].size < k) //比符合要求的最小空間小，則交換
{
k=MemList[i].size;
j=i;
}
}
}
i=j;
if(flag == 0) //沒找到
{
printf("Not Enough Memory!\n");
getch();
j=i;
}
else if(MemList[i].size - size <= MINSIZE) //小於規定的最小差，將整個空間分配
MemList[i].info='u';
else
{
for(j = MEMSIZE-2; j > i; j--) //後移
MemList[j+1]=MemList[j];
MemList[i+1].start=MemList[i].start+size;
MemList[i+1].size=MemList[i].size-size;
MemList[i+1].info='f';
MemList[i].size=size;
MemList[i].info='u';
}
Display();
}

/*--------------------------------------------------------
最壞適應演算法
*/
void BadFit_new()
{
int i,j,k,flag,size;
char temp[10];
printf("BadFit_new How many MEMORY requir?");
gets(temp);
size=atoi(temp);
j=0;
flag=0;
k=0; //保存滿足要求的最大空間

for(i=0;i<MEMSIZE-1&&MemList[i].info!='e';i++)
{
if(MemList[i].size>=size&&MemList[i].info=='f')
{
flag=1;
if(MemList[i].size>k)
{
k=MemList[i].size;
j=i;
}
}
}
i=j;

if(flag=0)
{
printf("Not Enough Memory!\n");
getch();
j=i;
}
else if(MemList[i].size-size<=MINSIZE)
MemList[i].info='u';
else
{
for(j=MEMSIZE-2;j>i;j--)
MemList[j+1]=MemList[j];
MemList[i+1].start=MemList[i].start+size;
MemList[i+1].size=MemList[i].size-size;
MemList[i+1].info='f';
MemList[i].size=size;
MemList[i].info='u';
}
Display();
}

/*--------------------------------------------------------

函數名:del()
功 能:釋放一塊內存
--------------------------------------------------------*/
void del()
{
int i,number;
char temp[10];
printf("\nplease input the NUMBER you want stop:");
gets(temp);
number=atoi(temp);

if(MemList[number].info == 'u') //輸入的空間是使用的
{
MemList[number].info = 'f'; //標志為空閑
if(MemList[number+1].info == 'f') //右空間為空則合並
{
MemList[number].size+=MemList[number+1].size; //大小合並
for(i=number+1;i < MEMSIZE-1 && MemList[i].info !='e';i++)/* i後的空間信息表元素前移 */
if(i>0)
MemList[i]=MemList[i+1];
}
if(number > 0 && MemList[number-1].info=='f') //左空間空閑則合並
{
MemList[number-1].size+=MemList[number].size;
for(i=number;i<MEMSIZE-1&&MemList[i].info!='e';i++)
MemList[i]=MemList[i+1];
}
}
else
{
printf("Thist Number is Not exist or is Not used!\n ");
getchar();
}
Display();
}

/*--------------------------------------------------------
函數名:Display()
功 能:顯示內存狀態
--------------------------------------------------------*/
void Display(){
int i,
used=0; //記錄可以使用的總空間量

/* clrscr();*/
printf("\n----------------------------------------------\n");
printf("%5s%15s%15s","Number","start","size","Info");
printf("\n----------------------------------------------\n");
for(i=0;i < MEMSIZE && MemList[i].info != 'e';i++)
{
if(MemList[i].info == 'u')
used+=MemList[i].size;
printf("%5d%15d%15d%15s\n",i,MemList[i].start,MemList[i].size,MemList[i].info=='u'?"USED":"FREE");
}
printf("\n----------------------------------------------\n");
printf("Totalsize:%-10d Used:%-10d Free:%-10d\n",MEMSIZE,used,MEMSIZE-used);
printf("\n\n Press Any Key to return...");
getch();
}

/*--------------------------------------------------------
函數名:main()
功 能:主函數
--------------------------------------------------------*/
void main(){
char ch;
InitAll();
while(1){
printf("========================================================\n");
printf(" 1.Get a block use the FISTFIT method\n");
printf(" 2.Get a block use the BESTFIT method\n");
printf(" 3.Get a block use the BadFIT method\n");
printf(" 4.Free a block\n");
printf(" 5.Display Mem info \n");
printf(" 6.Exit \n");
printf("========================================================\n");
ch=getch();
switch(ch){
case '1':FirstFit_new();break; //首次適應演算法
case '2':BestFit_new();break; //最佳適應演算法
case '3':BadFit_new();break; //最壞適應演算法
case '4':del();break; //刪除已經使用完畢的空間
case '5':Display();break; //顯示內存分配情況
case '6':exit(0);
}
}
}