熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

嚴蔚敏《數據結構(c語言版)習題集》算法設計題第八章答案

2013-11-15 15:31:48  來源: 數據結構 

  第八章 動態存儲管理

  

  typedef struct {

  char *start;

  int size;

  } fmblock; //空閒塊類型

  char *Malloc_Fdlf(int n)//遵循最後分配者最先釋放規則的內存分配算法

  {

  while(Gettop(Sb)&&bsize

  {

  Pop(S,b);

  Push(T,b); //從棧頂逐個取出空閒塊進行比較

  }

  if(StackEmpty(S)) return NULL; //沒有大小足夠的空閒塊

  Pop(S,b);

  b.size-=n;

  if(b.size) Push(S,{b.start+n,b.size});//分割空閒塊

  while(!StackEmpty(T))

  {

  Pop(T,a);

  Push(S,a);

  } //恢復原來次序

  return b.start;

  }//Malloc_Fdlf

  mem_init()//初始化過程

  {

  ...

  InitStack(S);InitStack(T); //S和T的元素都是fmblock類型

  Push(S,{MemStart,MemLen}); //一開始,棧中只有一個內存整塊

  ...

  }//main

  8.12

  void Free_Fdlf(char *addr,int n)//與上一題對應的釋放算法

  {

  while(Gettop(S,b)&&b.start

  {

  Pop(S,b);

  Push(T,b);

  } //在按地址排序的棧中找到合適的插入位置

  if(Gettop(T,b)&&(b.start+b.size==addr)) //可以與上鄰塊合並

  {

  Pop(T,b);

  addr=b.start;n+=b.size;

  }

  if(Gettop(S,b)&&(addr+n==b.start)) //可以與下鄰塊合並

  {

  Pop(S,b);

  n+=b.size;

  }

  Push(S,{addr,n}); //插入到空閒塊棧中

  while(!StackEmpty(T))

  {

  Pop(T,b);

  Push(S,b);

  } //恢復原來次序

  }//Free_Fdlf

  8.13

  void Free_BT(Space &pav,Space p)//在邊界標識法的動態存儲管理系統中回收空閒塊p

  {

  n=p->size;

  f=p+n-1; //f指向空閒塊底部

  if((p-1)->tag&&(f+1)->tag) //回收塊上下鄰塊均為占用塊

  {

  p->tag=0;f->tag=0;

  f->uplink=p;

  if(!pav)

  {

  p->llink=p;

  p->rlink=p;

  }

  else

  {

  q=pav->llink;

  p->llink=q;p->rlink=pav;

  q->rlink=p;pav->llink=p;

  }

  pav=p;

  }//if

  else if(!(p-1)->tag&&(f+1)->tag) //上鄰塊為空閒塊

  {

  q=(p-1)->uplink;

  q->size+=n;

  f->uplink=q;

  f->tag=0;

  }

  else if((p-1)->tag&&!(f+1)->tag) //下鄰塊為空閒塊

  {

  q=f+1;

  s=q->llink;t=q->rlink;

  p->llink=s;p->rlink=t;

  s->rlink=p;t->llink=p;

  p->size+=q->size;

  (q+q->size-1)->uplink=p;

  p->tag=0;

  }

  else //上下鄰塊均為空閒塊

  {

  s=(p-1)->uplink;

  t=f+1;

  s->size+=n+t->size;

  t->llink->rlink=t->rlink;

  t->rlink->llink=t->llink;

  (t+t->size-1)->uplink=s;

  }

  }//Free_BT,該算法在課本裡有詳細的描述.

  8.14

  void Free_BS(freelist &avail,char *addr,int n)//伙伴系統的空閒塊回收算法

  {

  buddy=addr%(2*n)?(addr-n):(addr+n); //求回收塊的伙伴地址

  addr->tag=0;

  addr->kval=n;

  for(i=0;avail[i].nodesize

  if(!avail[i].first) //尚沒有該大小的空閒塊

  {

  addr->llink=addr;

  addr->rlink=addr;

  avail[i].first=addr; //作為唯一一個該大小的空閒塊

  }

  else

  {

  for(p=avail[i].first;p!=buddy&&p!=avail[i].first;p=p->rlink);//尋找伙伴

  if(p==buddy) //伙伴為空閒塊,此時進行合並

  {

  if(p->rlink==p) avail[i].first=NULL;//伙伴是此大小的唯一空閒塊

  else

  {

  p->llink->rlink=p->rlink;

  p->rlink->llink=p->llink;

  } //從空閒塊鏈中刪去伙伴

  new=addr>p?p:addr; //合並後的新塊首址

  Free_BS(avail,new,2*n); //遞歸地回收新塊

  }//if

  else //伙伴為占用塊,此時插入空閒塊鏈頭部

  {

  q=p->rlink;

  p->rlink=addr;addr->llink=p;

  q->llink=addr;addr->rlink=q;

  }

  }//else

  }//Free_BS

  8.15

  FBList *MakeList(char *highbound,char *lowbound)//把堆結構存儲的的所有空閒塊鏈接成可利用空間表,並返回表頭指針

  {

  p=lowbound;

  while(p->tag&&p

  if(p>=highbound) return NULL; //沒有空閒塊

  head=p;

  for(q=p;p

  if(!p->tag)

  {

  q->next=p;

  q=p;

  }//if

  p->next=NULL;

  return head; //返回頭指針

  }//MakeList

  8.16

  void Mem_Contract(Heap &H)//對堆H執行存儲緊縮

  {

  q=MemStart;j=0;

  for(i=0;i

  if(H.list[i].stadr->tag)

  {

  s=H.list[i].length;

  p=H.list[i].stadr;

  for(k=0;k

  H.list[j].stadr=q;

  H.list[j].length=s; //緊縮占用空間表

  j++;

  }

  }//Mem_Contract


From:http://tw.wingwit.com/Article/program/sjjg/201311/23561.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.