模拟指针及操作头文件

在大多数应用中，可以利用动态分配及C 指针来实现链表和间接寻址表。不过，有时候采用一个节点数组以及对该数组进行索引的模拟指针（ simulated pointer），可以使设计更方便、更高效。假定采用一个数组node，该数组的每个元素中都包含两个域： data和link。数组中的节点分别是：node[0]、node[1]、. . .、node[ NumberOfNodes-1]。以下用节点i来代表node[i]。如果一个单向链表c由节点1 0，5和2 4按序构成，将得到c = 10(指向链表c的第一个节点的指针是整数类型)，node[10].link= 5 (指向第二个节点的指针 )，node[5].link= 24 (指向下一个节点的指针 )，node[24].link = -1 (表示节点2 4是链表中的最后一个节点)。在绘制链表时，可以把每个链接指针画成一个箭头，与使用C 指针的时候一样。
为了实现指针的模拟，需要设计一个过程来分配和释放一个节点。当前未被使用的节点将被放入一个存储池（storage pool）之中。开始时，存储池中包含了所有节点 node[ 0：Number-OfNodes-1]。Allocate从存储池中取出节点，每次取出一个。 Deallocate则将节点放入存储池中，每次放入一个。因此，Allocate 和Deallocate 分别对存储池执行插入和删除操作，等价于 C 函数delete和new。用作存储池的链表被称之为可用空间表（ available space list），其中包含了当前未使用的所有节点。first 一个类型为int的变量，它指向可用空间表中的第一个节点。添加和删除操作都是在可用空间表的前部进行的。
SimSpace.h

#ifndef  SIMSPACE_H
#define SIMSPACE_H
#include <iostream>
using std::cout;
using std::endl;
using std::ostream;

template<typename T>
class SimSpace;

template<typename T>
class SimNode{
    friend SimSpace<T>;
private:
    T data;
    int link;
};

template<typename T>
class SimSpace{
public:
    SimSpace(int MaxSpaceSize = 100);
    ~SimSpace() {delete [] node;}
    int Allocate();
    void Deallocate(int & i);
private:
    int NumberOfNodes, first;
    SimNode<T> * node;
};

template<typename T>
SimSpace<T>::SimSpace(int MaxSpaceSize = 100)
{
    NumberOfNodes = MaxSpaceSize;
    node = new SimNode<T> [NumberOfNodes];

    for (int i = 0; i < NumberOfNodes - 1; i++)
    {
        node[i].link = i+1;
    }
    node[NumberOfNodes].link = -1;
    first = 0;
}

template<typename T>
int SimSpace<T>::Allocate() //Delete
{
    if (first == -1)
        cout<<"NoMem"<<endl;
    int i = first;
    first = node[i].link;
    return i;
}

template<typename T>
void SimSpace<T>::Deallocate(int & i) //new
{//释放节点i,使i成为可用空间表的第一个节点
    node[i].link = first;
    first = i;
    i = -1;

}
#endif