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

中文名

模拟指针

外文名

simulated pointer

优势

使设计更方便、更高效

应用学科

计算机科学、测绘科学、通信工程

简介

用一个节点数组并对数组进行索引

简介

模拟指针的链表

假定采用一个数组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的变量，它指向可用空间表中的第一个节点。添加和删除操作都是在可用空间表的前部进行的。

模拟指针的类定义

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

SimSpace的操作

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

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

采用模拟指针的链表

可以使用模拟空间S来定义一个链表类。S被说明为一个static成员，目的是使所有类型为T的模拟链表共享相同的模拟空间。如下程序给出了除Search和Output之外的各共享函数的代码。这些代码假定SimChain已经被说明为SimNode和SimSpace的友元。