模拟指针是用数组元素来模拟链表的一种数据结构。其中，数组的每一个元素都分成了数据域data和指针域link。data的数据类型根据需要而定（即链表要存储的数据的类型），而link为整型，用于指出在链表中的下一个元素的数组下标。一下是模拟指针类的声明： template class SimNode { friend SimSpace; //空闲指针存储池 private: T data; int link; };        除此之外，还需要一个存储池来存放未被使用的元素（即以上代码中的SimSpace）。类声明如下： template class SimSpace { public: SimSpace (int MaxSpaceSize=100); ~SimSpace () {delete [] node}; int Allocate (); void Deallocate (int& i); private: int NumberOfNodes, first; SimNode *node; }; template SimSpace::SimSpace (int MaxSpaceSize) { NumberOfNodes = MaxSpaceSize; node = new SimNode [NumberOfNodes]; for (int i = 0; i < NumberOfNodes; i++) node[i].link = i+1; node[NumberOfNodes-1] = -1; first = 0; } template int SimSpace::Allocate () { int i = first; first = node[i].link; //first指向下一个空闲节点 return i; } template void SimSpace::Deallocate (int& i) { node[i].link = first; first = i; i=-1; }        释放操作（即Deallocate函数）中，将参数i的值设为-1，是因为一般在调用这个函数的时候，有可能将一个类似于指针的、用于访问各个节点的整型变量作为参数传入。将它设为-1以防错误地继续用它对链表进行操作（会访问到存储池，存储池是不应该被访问的）。另外，存储池的构造函数中用了一个循环，将每一个节点的link设为紧邻的下一个节点的下标，使得函数的时间复杂度达到了O(n)。设置这个循环的原因要到Allocate和Deallocate两个函数中去寻找：在分配新节点时，程序从first所指链表的头部取出一个节点，而释放节点时，程序又将释放的节点插入到first所指的链表的头部。如果不设置这个循环，在分配节点时，程序就需要变成： template int SimSpace::Allocate () { int i = first++; return i; }
也就是每次分配节点都是按照数组的顺序。如此一来，虽然在程序刚刚开始时，节点分配不会有问题，但是，如果有节点释放，first所指的节点在数组中的下一个就有可能不在存储池中，而是正在被使用，程序就会出错。因此，在这种数据结构中，分配和释放节点的方式不便改变（我没想到其他方法）。既然如此，要缩减时间开销，就要另寻他法。        第二种存储池的定义如下： template class SimSpace { public: SimSpace (int MaxSpaceSize=100); ~SimSpace () {delete [] node}; int Allocate (); void Deallocate (int& i); private: int NumberOfNodes, firstNew, firstOld; SimNode *node; }; template SimSpace::SimSpace (int MaxSpaceSize) { NumberOfNodes = MaxSpaceSize; node = new SimNode [NumberOfNodes]; firstNew = 0; firstOld = -1; } template int SimSpace::Allocate () { if (firstOld == -1) return firstNew++; int i = firstOld; firstOld = node[i].link; //firstOld指向下一个空闲节点 return i; } template void SimSpace::Deallocate (int& i) { node[i].link = firstOld; firstOld = i; i=-1; }        与之前不同的是，这种定义有两个存储池（即两个first），其中firstNew用来存储未被分配过的节点，firstOld用来存储至少被用过一次的节点。这种方法实际上是让firstNew顺着数组遍历，firstOld和之前的first的功能比较类似。第二种方式中，被释放的节点不影响firstNew的顺序，也就不必将每个节点的link初始化，省下了构造函数的时间开销。