新建 文本文档 (2).txt

以c语言实现内存分配 算法较好

#include<stdio.h>
#include<string.h>
#define MaxT 10000
#define MaxE 20000
#define MaxNum(a,b) (a>b?a:b)

class Event
{public:
  int t,m,p;
};

class WaitQueue
{public:
  int m,p;
  WaitQueue* next;
};

class FreeBlock
{public:
  int s,m;
  FreeBlock* next;
};

class Queue
{public:
  WaitQueue *h,*t;
};

int n,ne;
Event e[MaxE];
Queue wq;
FreeBlock *fb;
int tot_t,wai_n;

template<class T>
void swap(T &a,T &b)
{ T c=a;
 a=b; b=c;
}

template<class T>
void HeapAdjustB(T *l,int s,int m)
{ int j;
  T t=l[s];
 for (j=2*s+1; j<=m; j=2*j+1)
  {if (j<m&&(l[j].t>l[j+1].t||(l[j].t==l[j+1].t&&l[j].m>l[j+1].m))) j++;
   if (t.t<l[j].t||(t.t==l[j].t&&t.m<=l[j].m)) break;
   l[s]=l[j]; s=j;
  }
 l[s]=t;
}

template<class T>
void HeapAdjustU(T *l,int p)
{ int fa;
 while (p>0)
  {fa=(p-1)/2;
   if (l[fa].t>l[p].t||(l[fa].t==l[p].t&&l[fa].m>l[p].m))
    {swap(l[fa],l[p]); p=fa;}
   else
    break;
  }
}

template<class T>
void HeapDel(T *l,int &len)
{len--;
 swap(l[0],l[len]);
 HeapAdjustB(l,0,len-1);
}

template<class T>
void HeapAdd(T *l,int &len,int t,int m,int p)
{e[len].t=t; e[len].m=m; e[len].p=p;
 HeapAdjustU(l,len);
 len++;
}

void init()
{ int t,m,p;
 scanf("%d",&n);
 do
  {scanf("%d %d %d",&t,&m,&p);
   if (t==0&&m==0&&p==0) break;
   e[ne].t=t; e[ne].m=m; e[ne].p=p; ne++;
  }
 while (1);
 wq.h=new WaitQueue; wq.h->next=0; wq.t=wq.h;
 fb=new FreeBlock; fb->s=-1; fb->m=-1;
 fb->next=new FreeBlock;  fb->next->s=0; fb->next->m=n; fb->next->next=0;
 tot_t=0; wai_n=0;
}

void DelHead(Queue &q)
{ WaitQueue *tmp;
 tmp=q.h->next; if (tmp==q.t) q.t=q.h;
 q.h->next=tmp->next;
 delete tmp;
}

void AddTail(Queue &q,int m,int p)
{ WaitQueue *tmp;
 tmp=new WaitQueue;
 tmp->m=m; tmp->p=p; tmp->next=0;
 q.t->next=tmp; q.t=tmp;
}

void DelBlock(FreeBlock *tp,FreeBlock *p)
{tp->next=p->next; delete p;}

int getmem(int m)
{ int tmp=-1;
  FreeBlock *p,*tp;
 tp=fb; p=fb->next;
 while (p)
  {if (p->m>=m) break;
   p=p->next; tp=tp->next;
  }
 if (p==0) return -1;
 if (p->m>m)
  {tmp=p->s; p->s+=m; p->m-=m; return tmp;}
 else if (p->m==m)
  {tmp=p->s; DelBlock(tp,p); return tmp;}
 else return tmp;
}

void freemem(int a,int m)
{ FreeBlock *tp,*p,*np;
 p=fb; np=fb->next;
 while (np)
  {if (p->s+p->m<=a&&np->s>=a) break;
   p=p->next; np=np->next;
  }
 if (p->s+p->m==a)
  {p->m+=m;
   if (np)
    if (p->s+p->m==np->s)
     {p->m+=np->m; DelBlock(p,np);}
  }
 else if (np)
  {if (a+m==np->s)
    {np->s=a; np->m+=m;}
   else
    {tp=new FreeBlock; tp->s=a; tp->m=m;
     tp->next=p->next; p->next=tp;
    }
  }
 else
  {tp=new FreeBlock; tp->s=a; tp->m=m;
   tp->next=p->next; p->next=tp;
  }
}

void search()
{ int freed,now,tmp,t,m,p;
 while (ne>0||wq.h->next)
  {freed=0; now=e[0].t; tot_t=MaxNum(tot_t,now);
   while (ne>0&&e[0].m<0&&e[0].t==now)
    {freemem(e[0].p,-e[0].m); HeapDel(e,ne); freed=1;}
   if (freed)
    while (wq.h->next)
     {t=now; m=wq.h->next->m; p=wq.h->next->p;
      tmp=getmem(m); if (tmp==-1) break;
      DelHead(wq);
      HeapAdd(e,ne,t+p,-m,tmp);
     }
   while (ne>0&&e[0].t==now)
    {t=e[0].t; m=e[0].m; p=e[0].p;
     tmp=getmem(m);
     if (tmp==-1)
      {AddTail(wq,m,p); wai_n++;}
     else
      HeapAdd(e,ne,t+p,-m,tmp);
     HeapDel(e,ne);
    }
  }
}

void show()
{printf("%d\n%d\n",tot_t,wai_n);}

int main()
{init();
 search();
 show();
 return 0;
}