可利用空间表 ava ■把存储器看成一组变长块数组 些块是已分配的 链接空闲块,形成可利用空间表 freelist 存储分配和回收 a new p从可利用空间分配 delete p把p指向的数据块返回可利用空间 表 2)氯能适行一段对闻 1)初地状态的可利用型同表 ■空间不够,则求助于失败策略 点等长的可利用空间变 帖國写 4可利用空间表的函数重载4 template <class Elem> class LinkNodel ∥载new运算符实现 private: template <class Elem> static LinkNode* avail;川可利用空间表头指针 void* Link Node<Elem>:: operator new(size t)i public: avl-NULL)/可利用空间表为空 Elem value;∥结点值 return: new LinkNode;/利用系统的new分配空间 LinkNode*next;∥指向下一结点的指针 LinkNodecElem> 否则从可利用 空间表中取走一个结点 NULL);∥造函数 availe avail->next t;/载new运算符 return temp; →p)/载 delete运算符 北京大息啦_张铭写 权有。印乡究 北大啦孔写 叔新有命剑 载 delete运算符实现 可利用空间表:单链表栈 gnew即栈的删除操作 void LinkNode<Elem>:: operator delete(void* p)i delete即栈的插入操作 ((LinkNode<Elem>*)p)->next=avail; avail=(LinkNode<Elem>*) 襄用系统的p7和1:作 ■例如,程序运行完毕时,把avai1所占用的 空间都交还给系统(真正释放空间) 北大学到9 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 49 可利用空间表 „ 把存储器看成一组变长块数组 „ 一些块是已分配的 „ 链接空闲块，形成可利用空间表(freelist) „ 存储分配和回收 „ new p 从可利用空间分配 „ delete p 把p指向的数据块返回可利用空间 表 „ 空间不够，则求助于失败策略 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 50 avail avail （1）初始状态的可利用空间表 （2）系统运行一段时间后 的可利用空间表 结点等长的可利用空间表 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 51 可利用空间表的函数重载 template <class Elem> class LinkNode{ private: static LinkNode *avail; //可利用空间表头指针 public: Elem value; //结点值 LinkNode * next; //指向下一结点的指针 LinkNode(const Elem & val, LinkNode * p); LinkNode(LinkNode * p = NULL);//构造函数 void * operator new(size_t);//重载new运算符 void operator delete(void * p);//重载delete运算符 }; 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 52 //重载new运算符实现 template <class Elem> void * LinkNode<Elem>::operator new(size_t){ if(avail == NULL) //可利用空间表为空 return ::new LinkNode;//利用系统的new分配空间 LinkNode<Elem> * temp = avail; //否则从可利用 空间表中取走一个结点 avail = avail->next; return temp; } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 53 //重载delete运算符实现 template <class Elem> void LinkNode<Elem>::operator delete(void * p){ ((LinkNode<Elem> *) p)->next = avail; avail = (LinkNode<Elem> *)p; } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 54 „ 可利用空间表：单链表栈 „ new即栈的删除操作 „ delete即栈的插入操作 „ 直接引用系统的new和delete操作符，需 要强制用“::new p”和“::delete p” „ 例如，程序运行完毕时，把avail所占用的 空间都交还给系统（真正释放空间）