[科普中国]-模拟指针

采用一个节点数组以及对该数组进行索引的模拟指针 ，可以使设计更方便、 更高效。模拟指针是使用一段连续的存储区来模拟指针的功能，可以有效的利用一段连续内存进行一定范围内可变的子链表的空间分配。1

简介假定采用一个数组node，该数组的每个元素中都包含两个域：data和link。数组中的节点分别是：node[0]、node[l]、...、node[Number Of Nodes-l]。以下用节点i来代表node[i]。如果一个单向链表c由节点10，5和24按序构成，将得到c=10(指向链表c的第一个节点的指针是整数类型)，node[10].link=5(指向第二个节点的指针)，node[5].link=24(指向下一个节点的指针)，node[24].link=-1(表示节点24是链表中的最后一个节点)。在绘制链表时，可以把每个链接指针画成一个箭头（如图所示），与使用C++指针的时候一样。

实现为了实现指针的模拟，需要设计一个过程来分配和释放一个节点。当前未被使用的节点将被放入一个存储池（storage pool）之中。开始时，存储池中包含了所有节点node[0：Number-OfNodes-l]。Allocate从存储池中取出节点，每次取出一个。Deallocate则将节点放入存储池中，每次放入一个。因此，Allocate和Deallocate分别对存储池执行插入和删除操作，等价于C++函数delete和new。如果存储池是一个节点链表（如图所示），这两个函数可以高效地执行。

用作存储池的链表被称之为可用空间表（available space list），其中包含了当前未使用的所有节点。first是一个类型为int的变量，它指向可用空间表中的第一个节点。添加和删除操作都是在可用空间表的前部进行的。2

模拟指针的类定义为了实现一个模拟指针系统，定义了SimNode类和SimSpace类，具体代码如下所示：

template class SimNode {friend SimSpace;private : T data; int link;};template class SimSpace {public : SimSpace (int MaxSpaceSize=100); ~SimSpace() {delete [] node;} int Allocate(); //分配一个节点 void Deallocate (int& i) ; //释放节点iprivate: int NumberOfNodes, first; SimNode *node;//节点数组} ;SimSpace****的操作

由于所有节点初始时都是自由的，因此在刚被创建的时候，可用空间表中包含NumberOfNodes个节点。用来对可用空间表进行初始化。如下两个程序分别实现Allocate和Deallocate操作。2

使用模拟指针分配一个节点

templateint SimSpace::Allocate(){// 分配一个自由节点 if (first == -1) throw NoMem(); int i = first; //分配第一个节点 first = node[i].link; //first指向下一个自由节点return i;}使用模拟指针释放一个节点templatevoid SimSpace::Deallocate(int& i){// 释放节点i ./ /使i 成为可用空间表的第一个节点node[i].link = first;first = i;i = -1;}采用模拟指针的链表可以使用模拟空间S来定义一个链表类。S被说明为一个static成员，目的是使所有类型为T的模拟链表共享相同的模拟空间。如下程序给出了除Search和Output之外的各共享函数的代码。这些代码假定SimChain已经被说明为SimNode和SimSpace的友元。

模拟链表的类定义templateclass SimChain{public: SimChain(){first=-1;} ~SimChain(){Destroy();}voidDestroy();// 使表为空 int Length()const;boolFind(intk,T&x)const; int Search(constT&x)const; SimChain&Delete(intk,T&x); SimChain&Insert(intk,constT&x); void Output(ostream&out)const;private: int first;// 第一个节点的索引staticSimSpaceS;};构造函数和Length函数templatevoid SimChain::Destroy(){// 释放链表节点 int next; while(first!=-1){ next=S.node[first].link; S.Deallocate(first); first=next;}}templateint SimChain::Length()const{// 返回链表的长度 int current=first；//链节点的当前位置 len=0;//元素计数 while(current!=-1){ current=S.node[current].link;len++;}return len;}Find函数templatebool SimChain::Find(intk,T&x)const{// 取第k个元素至x//如果不存在第k个元素，函数返回false，否则返回true if(k