通用 XOR 编码列表

JorgeLuisOrejel

5.00/5 (7投票s)

2016年3月4日

CPOL

22分钟阅读

20927

214

本文基于我未出版的教科书《应用算法与数据结构》的第二章。

下载源代码 - 12.4 MB

本文基于我未出版的教科书《应用算法与数据结构》的第二章。这里介绍的所有代码以及可下载的ZIP文件中包含的代码，都是在Visual Studio 2010下用非托管C++编写的。（如每个文件中所示，这些代码是根据很久以前在Borland C++下开发的原始代码改编的。）

泛型单向链表

通过结合使用动态内存和结构体来存储数据和指向结构体的指针，可以维护长度仅受堆空间大小限制的链表。为了实现适用于不同数据类型的链表，我们可以定义泛型单向链表（GSLLs），如下图所示。

在泛型单向链表（GSLL）中，info 字段是一个泛型指针，指向某种类型的对象，而 next 字段的作用与通常一样。info 字段指向的对象在使用 GSLL 的特定派生实现的代码中创建。以下声明适用于操作 GSLL。

typedef void * genPtr;             // Generic pointer

typedef struct gSLLstruct gSLLstr; // gSLL structure
typedef gSLLstr * gSLLptr;         // Pointer to gSLL structure

struct gSLLstruct {                // gSLL structure
    genPtr info;                   // Pointer to object
    gSLLptr next;                  // Pointer to next element
};

使用GSLL的优点在于，操作链表的算法只需实现一次，便可一劳永逸。然后，针对每种特定的数据类型，定义单独的函数（在链表操作函数之外）来处理 info 字段指向的链表对象的打印、比较、分配和删除。这样，就可以在一个程序中同时支持多态的单向链表（SLLs）共存。

泛型双向链表

泛型双向链表（GDLLs）是对GSLLs的改进，因为它允许在常数时间内删除元素。以下定义适用于实现GDLLs。

typedef struct gDLLstruct gDLLstr;  // gDLL structure
typedef gDLLstr * gDLLptr;          // Pointer to gDLL structure
struct gDLLstruct {                 // gDLL structure
    genPtr info;                    // Pointer to object
    gDLLptr pred, succ;             // Pointers to predecessor and successor nodes
};

现在考虑这样一种情况：我们得到了一个指向链表中某个元素的指针 p，并要求删除它。如果这个元素在一个单向链表中，我们就必须从头开始遍历链表，直到找到一个节点 q，使得 q->next == p。找到这样的节点后，通过以下代码完成对 p 处元素的移除：

q->next = p->next;
free( p->info );
free( p );

（当然，也必须考虑 p 处的元素是头指针 head 指向的第一个元素的特殊情况。）

如果待删除的元素属于一个双向链表，那么通过精心实现该链表，就可以避免搜索其前驱元素。在一般情况下，如果元素位于链表的中间某处，该元素及其前驱和后继元素的逻辑关系可以用下图表示：

那么，通过以下代码就可以轻松实现对 p 处元素的移除和删除：

p->pred->succ = p->succ;
p->succ->pred = p->pred;
free( p->info );
free( p );

在实现 GDLLs 时，必须决定如何处理第一个和最后一个元素。特别是，第一个元素的 pred 字段和最后一个元素的 succ 字段应该赋什么值。如果我们都赋为 NULL，从而使链表在两端终止，如下所示：

我们将面临为有序插入和任意删除实现三种不同情况的问题，即第一个元素、链表中间的某个位置以及最后一个元素。显然，一定有更好的方法。

如果将 GDLL 做成循环的，使得第一个元素的前驱是最后一个元素，最后一个元素的后继是第一个元素，那么就可以用同样的代码来实现有序插入和任意删除。唯一的要求是，在链表上进行搜索时，我们有办法知道何时回到了起点。这可以通过维护一个指向虚拟头元素的 head 指针来轻松实现，如下图所示，其 info 字段为 NULL（用交叉阴影线表示）。插入和删除操作总是从虚拟元素的后继开始。

一个初始为空的 GDLL 由单个虚拟元素组成，其 pred 和 succ 字段都指向该元素自身。

泛型、双向、异或编码链表

使用显式的 pred 和 succ 指针实现 GDLLs 的缺点是由于指针的重复而浪费空间。对于任意两个逻辑上相邻的元素，分别位于 p 和 q，且 q 处的元素在 p 之后，断言 q == p->succ && p == q->pred 为真。此外，对于循环 GDLL 中的任何节点 q，q->pred->succ == q->succ->pred == q 也成立。这些断言只是说明每个元素的地址在链表中被存储了两次。

解决空间浪费的办法是，在每个元素的单个字段中编码其前驱和后继元素地址的适当组合。这种编码是通过对地址应用异或（xor, ^）函数来实现的（参见 Thomas A. Standish, Data Structure Techniques, Addison-Wesley 1980, pp. 196-198; Harry R. Lewis and Larry Denenberg, Data Structures and Their Algorithms, Harper Collins 1991, pp. 88-90。Standish, pp. 82-83, 也描述了这种技术在Siklossy遍历二叉树中的应用：L. Siklossy 1972, "Fast and Read-Only Algorithms for Traversing Trees Without an Auxiliary Stack," Inf. Proc. Letters 1, 149-152）。

对于两个逻辑变量 A 和 B，xor 函数定义为：若 A == B，则 xor( A, B ) == 0；若 A != B，则 xor( A, B ) == 1。此外，使用异或运算符 (^)，该函数具有以下性质：

交换律：A ^ B == B ^ A

结合律：A ^ (B ^ C) == (A ^ B) ^ C

自反消除：A ^ A == 0 [特别是 A ^ (A ^ B) == B]

当用作加法时，不产生进位。

为了简单说明异或函数自反消除性质的用处，我们可以编写一个宏来交换任何两个相同基本数据类型的变量，而无需使用临时变量，如下所示：

#define swap( x, y ) ( x ^= y, y ^= x, x ^= y )

要理解其工作原理，请看以下代码的执行过程：

int i = 12, j = 7;

swap( i, j )
// i == 7 && j == 12

将整数表示为四位二进制数，顺序执行的结果如下：

   i == 1100
^  j == 0111
=       1011  ==  i

   j == 0111
^  i == 1011
=       1100  ==  j

   i == 1011
^  j == 1100
=       0111  ==  i

赋给 i 和 j 的最终值（在最后两个语句中）清楚地显示了交换的正确结果。接下来将展示，异或函数的自反消除性质也允许对地址进行编码，从而实现不带重复指针的双向链表。

异或编码的 GDLLs 可以用一个结构体来表示，该结构体包含通常的 info 字段（一个 genPtr）和一个名为 link 的无符号长整型字段，其值将是两个地址的异或结果。

在循环 GDLL 中，每个元素都有一个前驱和一个后继。对于每个位于 q 的节点，设 p 和 s 分别表示其前驱和后继元素的地址。

赋值 q->link = p ^ s 允许通过以下方式检索地址 p 和 s：

给定 p 和 q，p ^ q->link == p ^ p ^ s == s；给定 q 和 s，s ^ q->link == s ^ p ^ s == p。

因此，每个链表元素中的 link 字段通过编码其地址来“指向”前驱和后继元素，这在上图中用虚线箭头表示。事实上，给定指向两个逻辑上相邻节点的指针，我们可以检索到其中任意一个节点的前驱或后继指针，这使我们能够实现对异或编码双向链表（xorDLLs）的遍历操作。

抽象地说，假设一个包含 n 个数据项的列表已使用这种表示法创建。设表示包含这些数据项的元素的地址，并设和表示另外两个头元素的地址（它们的 info 字段中不包含有用数据，即为 NULL 指针）。那么，对于地址为的任何节点，其中，

a_{i}->link = a_{i-1 mod(n+2)} \bigoplus a_{(i+1) mod(n+2)}

下图展示了一个包含三个数据项的 xorDLL，其中包括由 hdr1 和 hdr2 指向的两个头节点。图中明确显示了地址为的节点的链接箭头。

一个初始为空的 xorDLL 仅由两个头节点组成，它们的 link 字段等于 0L。这些值表明，位于 hdr1(hdr2) 的节点既是位于 hdr2(hdr1) 节点的前驱也是其后继，如下图所示。或者说，位于 hdr1(hdr2) 的节点位于 hdr2(hdr1) 节点和 hdr2(hdr1) 节点之间。

在 xorDLL 的实际实现中，必须满足以下要求：1) 链表由两个头节点界定，2) 链表从头节点开始遍历，3) 访问任何节点都需要指向两个逻辑上相邻节点的指针。

由于异或编码链表相对不为人所知，我将采用自底向上的方法来定义其操作。首先，我将提出一些简单的操作，然后用它们来实现更复杂的操作。但是，我必须强调，这些代码只能在非托管 C++ 中实现。人们可能会尝试在托管 C++/CLI 或 C# 中实现异或编码链表，但是，由于托管代码依赖于垃圾回收器（在回收过程中会移动对象引用），这样做是不可能的（实际上是非法的）。

一个最小的 xorList 可以定义如下。

typedef void * genPtr;              // Generic pointers
typedef unsigned long int Dword;    // Double words
typedef enum { LT, EQ, GT } RelVal; // Relational values

typedef struct {  // Structure for XOR-coded lists
   genPtr info;   // Pointer to information object of primitive type
    Dword link;   // Link encoding addresses of predecessor and successor nodes
} xorStr;
typedef xorStr * xorPtr;  // Pointers to XOR-coded list elements

xorPtr AllocXorStr() // Allocation of XOR-coded structures
{
   xorPtr p = (xorPtr)malloc( sizeof( xorStr ) );

   if ( p == NULL ) {
      printf( "heap exhausted\n" );
      exit( 0 );
   }
   return p;
}

class xorList {

protected:
   xorPtr hdr1, hdr2;                 // Pointers to header nodes

   void (*PrnFn)( genPtr, int );      // Pointer to info-print function
   RelVal (*CmpFn)( genPtr, genPtr ); // Pointer to info-comparison function

   xorPtr Successor( xorPtr, xorPtr );
   xorPtr Predecessor( xorPtr, xorPtr );

public:
   xorList() { Initialize(); }
   ~xorList();
   void Initialize();
   void Dispose();
   int IsEmpty();
   genPtr OrderedInsert( genPtr );
   void Print( int );
   genPtr Lookup( genPtr );
};

构造函数 xorList 调用 Initialize 函数来建立一个初始为空的列表，并初始化元素打印和元素比较的函数指针。

void xorList::Initialize()
{
   PrnFn = NULL;    CmpFn = NULL;   

   hdr1 = AllocXorStr();
   hdr2 = AllocXorStr();
   hdr1->info = hdr2->info = NULL;
   hdr1->link = hdr2->link = 0L;
}

请注意，由于 PrnFn 和 CmpFn 指针被初始化为 NULL，xorList 的行为类似于一个抽象类，也就是说，如果我们创建该类的一个实例，在不引起异常的情况下是无法调用这些函数的。在一个派生自 xorList 的类中，这些指针必须绑定到处理特定异或编码元素 info 字段的实际打印和比较函数。

析构函数 ~xorList 必须删除存储在列表中的所有元素。其定义将在稍后定义了几个附加函数之后给出。函数 xorList::IsEmpty 只是判断两个头节点的 link 是否等于 0L，这意味着在一个空的异或编码列表中，位于 hdr1(hdr2) 的节点位于 hdr2(hdr1) 节点和 hdr2(hdr1) 节点之间。

为了在异或编码列表中执行插入和删除元素的操作，我们可以设想一些基本操作，这些操作将有助于实现复杂的遍历。设 p 和 s 为指向两个逻辑上相邻节点的指针，其中 p 处的节点在 s 处的节点之前。我们可以定义一个受保护的函数 Predecessor，用于计算 p 处节点的前驱地址，以及一个类似的函数 Successor，用于计算 s 处节点的后继地址。

xorPtr xorList::Predecessor( xorPtr p, xorPtr s )
{
   // node at p precedes node at s

   return (xorPtr)( p->link ^ (Dword)s );
}

xorPtr xorList::Successor( xorPtr p, xorPtr s )
{
   // node at p precedes node at s

   return (xorPtr)( s->link ^ (Dword)p );
}

在函数 xorList::Predecessor 和 xorList::Successor 中，将指针类型强制转换为双字（double word），再将双字转换回指针是必要的，因为在 C/C++ 中，对指针应用异或运算符 (^) 是非法的。然而，这些类型转换仅仅是给编译器的解释性信息。与数值类型转换（比如从 int 到 float）会在运行时发生转换不同，指针类型转换不会在运行时引起任何显式转换。作为说明，下图显示了当我实现非类的等效函数 pred 和 succ 时，Borland C++ 编译器在大模式下生成的汇编代码。

汇编代码的含义将以函数 pred 为例进行解释。（类似的推理也适用于函数 succ。）汇编代码左侧的图示显示了函数执行期间其栈帧的内容。

前两条指令保存调用者的基址指针BP寄存器，并将BP设置为指向栈帧的基址。指令 `les bx, dword ptr [bp+6]` 将位于栈上BP+6位置的完整指针 `p`（`段:偏移`）加载到寄存器对 `ES:BX` 中。然后，`ES:BX` 指针在接下来的两条指令中用于分两步访问异或编码链表结构的 link 字段：寄存器 DX 获取高位字，寄存器 AX 获取低位字。这两个字构成一个32位数，它们（在接下来的两条指令中）分别与位于栈上 `BP+10` 位置的指针 s 的段部分和偏移部分进行 `XOR` 运算。返回时，函数恢复调用者的 `BP` 寄存器值，寄存器对 `DX:AX` 包含函数的返回值，即一个指向逻辑上在 p 节点之前的节点的指针。

作为对比，以下是 Visual Studio 2010 为非托管 C++ 版本的 xorList::Predecessor 生成的汇编代码。有趣的部分在第 356 行的 return 语句，我已用粗体标出。读者可以验证，这里没有发生类型转换。

; Listing generated by Microsoft (R) Optimizing Compiler Version 16.00.40219.01 

    TITLE    D:\XORstructures\MinGxorList\GxorList.cpp
    .686P
    .XMM
    include listing.inc
    .model    flat


;    COMDAT ?Predecessor@xorList@@IAEPAUxorStr@@PAU2@0@Z
_TEXT    SEGMENT
_this$ = -8                        ; size = 4
_p$ = 8                            ; size = 4
_s$ = 12                        ; size = 4
?Predecessor@xorList@@IAEPAUxorStr@@PAU2@0@Z PROC    ; xorList::Predecessor, COMDAT
; _this$ = ecx

; 353  : {

    push    ebp
    mov    ebp, esp
    sub    esp, 204                ; 000000ccH
    push    ebx
    push    esi
    push    edi
    push    ecx
    lea    edi, DWORD PTR [ebp-204]
    mov    ecx, 51                    ; 00000033H
    mov    eax, -858993460                ; ccccccccH
    rep stosd
    pop    ecx
    mov    DWORD PTR _this$[ebp], ecx

; 354  :    // node at p precedes node at s
; 355  : 
; 356  :    return (xorPtr)( p->link ^ (Dword)s );

    mov    eax, DWORD PTR _p$[ebp]
    mov    eax, DWORD PTR [eax+4]
    xor    eax, DWORD PTR _s$[ebp]

; 357  : }

    pop    edi
    pop    esi
    pop    ebx
    mov    esp, ebp
    pop    ebp
    ret    8
?Predecessor@xorList@@IAEPAUxorStr@@PAU2@0@Z ENDP    ; xorList::Predecessor
; Function compile flags: /Odtp /RTCsu /ZI
_TEXT    ENDS

有了 Predecessor 和 Successor 函数后，定义另外两个受保护的函数就变得很简单了，这两个函数可以使指向两个逻辑相邻节点的指针在列表中向前或向后移动一步。

void xorList::_1stepForward( xorPtr *ap, xorPtr *as )
{
   xorPtr p = *ap, s = *as;

   // p == Predecessor( s, Successor( p, s ) )

   *ap = s;
   *as = Successor( p, s );
}

void xorList::_1stepBackward( xorPtr *ap, xorPtr *as )
{
   xorPtr p = *ap, s = *as;

   // p == Predecessor( s, Successor( p, s ) )

   *ap = Predecessor( p, s );
   *as = p;
}

另一个支持有序插入实现的有用函数是在两个逻辑上相邻的节点之间插入一个节点（其 info 字段指向一个新的数据项）。给定指向节点 p 和 s 的指针，满足断言 p == pred( s, succ( p, s ) )，我们可以在它们之间插入一个由 q 指向的新元素。下图说明了插入这样一个元素前后的情况。（节点 x 和 y 的存在是有保证的，因为 xorList 是循环的。）

存储在节点 x 和 y 中的链接不需要考虑，因为这些链接对于插入操作是不必要的。值 p ^ s 存储在节点 q 的链接中，表示该节点位于节点 p 和 s 之间。由于新元素的插入，节点 p 和 s 中的链接必须更新。更新可以通过仅使用这些节点中的局部信息来完成。要更新节点 p 的链接，我们计算 p->link ^ s ^ q。根据异或函数的性质，结果为 x ^ q。要更新节点 s 中的链接，我们必须计算 s->link ^ p ^ q。执行插入的受保护函数如下：

void xorList::InsertBetween( xorPtr q, xorPtr p, xorPtr s )
{
   // q points to the new element to be inserted
   //   between the nodes at p and s
   //
   // p == Predecessor( s, Successor( p, s ) )

   Dword up = (Dword)p, us = (Dword)s, ur = (Dword)q;

   q->link = up ^ us;
   p->link = p->link ^ us ^ ur;
   s->link = s->link ^ up ^ ur;

   // p == pred( q, s ) && s == succ( q, s )
}

现在可以使用函数 _1stepForward 和 InsertBetween 来遍历 xorList 以实现有序插入。这个公共函数接收一个指向待存储对象的 genPtr，并遍历列表寻找插入位置。

genPtr xorList::OrderedInsert( genPtr gp )
{
   RelVal cmp;
   xorPtr q, p, s;

   p = hdr2;
   s = hdr1;
   do {
      _1stepForward( &p, &s );

   }  while ( s != hdr2
              &&
              ( cmp = (*CmpFn)( gp, s->info ) ) == GT );

   // s == hdr2 || cmp != GT

   if ( s == hdr2 || cmp != EQ ) 
   {
      q = AllocXorStr();
      q->info = gp;
      InsertBetween( q, p, s );
      return gp;
   }
   else // do not insert duplicates
   {
      return NULL;
   }
}

请注意函数指针 xorList::(*CmpFn) 的使用，它在遍历列表时，用于将被插入的元素与 s 指向的元素进行比较。由于 xorList 类的行为类似于一个抽象类，CmpFn 在该类中被绑定为 NULL，并且在未绑定到非 NULL 值之前不能被调用。稍后将展示，当从 xorList 派生一个特定类时，派生类的构造函数必须将 CmpFn（以及 PrnFn）绑定到非 NULL 值。还请注意，该函数返回 NULL 以表示插入重复项的请求被拒绝。

删除操作的实现方式与插入新元素类似。给定指向逻辑相邻节点 p 和 s 的指针，且断言 p == pred( s, succ( p, s ) ) 成立，我们可以删除其中一个，比如说 p 处的节点。下图说明了删除该元素前后的情况。（同样，请注意节点 x、y 和 z 的存在是有保证的，因为 xorList 是循环的。）实现移除的代码显示在图后。

genPtr xorList::RemoveAtP( xorPtr p, xorPtr s )
{
   xorPtr x;
   Dword up;
   genPtr gp;

   // p == Predecessor( s, Successor( p, s ) )

   x = Predecessor( p, s );
   up = (Dword)p;
   x->link = x->link ^ up ^ (Dword)s;
   s->link = s->link ^ up ^ (Dword)x;
   gp = p->info;
   free( p );
   return gp;
}

为方便起见，函数 RemoveAtP 返回一个指向已删除节点 info 字段中所存项目的 genPtr，以便支持在后续根据 xorList 定义的数据结构中进行移除操作。与函数 RemoveAtP 类似，也可以定义一个移除 s 处节点的函数。

genPtr xorList::RemoveAtS( xorPtr p, xorPtr s )
{
   xorPtr y;
   Dword us;
   genPtr gp;

   // p == Predecessor( s, Successor( p, s ) )

   y = Successor( p, s );
   us = (Dword)s;
   y->link = y->link ^ us ^ (Dword)p;
   p->link = p->link ^ us ^ (Dword)y;
   gp = s->info;
   free( s );
   return gp;
}

要打印一个异或编码的、双向的、循环的链表，我们可以运用愿望思维（wishful thinking）将问题分解成可管理的部分：

void xorList::Print( int brackets = 1 )
{
   xorPtr p;

   printf( "\n\n" );
   PrintHeader( "Header1", hdr1 );
   PrintHeader( "Header2", hdr2 );
   printf( "\n\n" );
   if ( brackets ) { printf( "[ " ); }

   p = StartTraversal();
   while ( !EndOfTraversal() ) 
   {
      PrintElement( p );
      p = NextElement();
   }
   if ( brackets ) { printf( "]" ); }
}

其意图是，将头节点打印在一行，然后是一个空行，接着在随后的行中打印元素列表。受保护的函数 xorList::PrintHeader 定义如下：

void xorList::PrintHeader( char *name, xorPtr headerPtr )
{
   printf( "%s: %08lX <!--, %08lX--> ", name, headerPtr, headerPtr->link );
}

打印头节点名称、其十六进制地址以及其内容，格式为 </, link>。“/” 表示头节点的 info 字段为 NULL，link 字段也以十六进制打印。

受保护的函数 xorList::StartTraversal，根据 xorList::StartForwardScan 定义，用于开始对 xorList 进行正向遍历；而函数 xorList::EndOfTraversal（同样是受保护的）则用于判断遍历是否已回到列表的起点。

xorPtr xorList::StartTraversal()
{
   return StartForwardScan();
}

函数 xorList::StartForwardScan 和 xorList::EndOfTraversal 可以通过向类中添加另外两个受保护的 xorPtr 字段来实现。

xorPtr E1, succE1,  // "Cursor" pointers to adjacent
                    // elements in forward traversals

xorPtr xorList::StartForwardScan()
{
   E1 = hdr1;
   succE1 = Successor( hdr2, hdr1 );
   return succE1;
}

int xorList::EndOfTraversal()
{
   return succE1 == hdr2;
}

受保护的函数 xorList::PrintElement 以 address< info, link > 的格式打印链表中的一个元素。节点的地址和链接以十六进制打印。info 字段通过调用绑定到 PrnFn 指针的函数来打印，如前所述，该指针在 xorList 这个类似抽象的类中为 NULL。PrintFlag 应该是类的一个公共数据成员，用于控制在每个元素后是否打印换行符。

void xorList::PrintElement( xorPtr p )
{
   printf( "%08lX<", p );
   (*PrnFn)( p->info, PrintFlag );
   printf( ",%08lX>", p->link );
   if ( !PrintFlag ) printf( " " );
}

受保护函数 xorList::NextElement 很容易通过一个辅助函数 MoveForward（也是受保护的）和 _1stepForward 来实现。设置这个辅助函数的原因将在后面阐明。

xorPtr xorList::NextElement()
{
   return MoveForward();
}

xorPtr xorList::MoveForward()
{
   // E1 != NULL && succE1 != NULL && !EndOfTraversal()

   _1stepForward( &E1, &succE1 );
   return succE1;
}

基于目前已经开发的函数，析构函数 xorList::~xorList 可以用递归方式实现。考虑一个典型的异或编码、循环、双向链表，如下所示。

我们不能简单地删除这个链表的一个节点，因为那样会失去遍历链表以删除后续节点的能力。解决这个问题的方法是，首先获取对列表中所有元素的访问权限，然后逐个删除它们。与处理递归结构的情况一样，我们可以依赖于支持递归执行的运行时堆栈。在递归“展开”过程中遍历链表，建立指向链表元素的指针。然后，在递归“收回”时可以执行元素的删除操作。

xorList::~xorList() {  Dispose();  }

void xorList::Dispose()
{
   DeleteAll( hdr2, hdr1 );
   DeleteElement( hdr1 );
}

void xorList::DeleteAll( xorPtr p, xorPtr s )
{
   // node at p precedes node at s
   // p == Predecessor( s, Successor( p, s ) )

   _1stepForward( &p, &s );
   if ( s != hdr2 )
   {
      DeleteAll( p, s );
   }
   DeleteElement( s );
}

void xorList::DeleteElement( xorPtr p )
{
   if ( verbose ) 
   {
      printf( "Deleting element: " );
      PrintElement( p );
      if ( p->info != NULL )
      {
         printf( " (info at %lX)", p->info );
      }
      printf( "\n" );
   }
   if ( p->info != NULL )
   {
      // This works ONLY for primitive-type objects.
      //
      // In the case of complex-structure objects,
      // a deletion function MUST be provided.
      // See *DelFn in GxorList\GxorList.cpp

      free( p->info );
   }
   free( p );
   --n;
}

请注意此函数中的注释。通过 free 函数删除 info 字段指向的对象，仅当这些对象是基本类型（int、char、float、byte 等）时才有效。对于更复杂的结构，必须提供一个删除函数。函数 Dispose 应该是公共的，而函数 DeleteAll 和 DeleteElement 应该是受保护的。

整数异或编码链表

为了操作异或编码链表的具体实例，必须从 xorList 派生出新的类。例如，假设我们希望维护一个整数的异或编码链表。为此，我们必须定义函数来打印和比较由链表元素的 info 字段（类型为 genPtr）指向的整数。如前所述，这些函数必须位于派生类和 xorList 类的外部。这些函数的合适定义如下。

typedef int * intPtr; // Pointer to int

int   icPrnW = 2;     // Default print width for int, char

void PrnInt( genPtr gp, int flag )
{
   if ( gp != NULL )
   {
      printf( "%*d", icPrnW, *((intPtr)gp) );
   }
   else // gp == NULL
   {
      printf( "%*c", icPrnW, '/' );
   }
   if ( flag )
   {
      printf( "\n" );
   }
}

RelVal CmpInts( genPtr gp1, genPtr gp2 )
{
   int i = *((intPtr)gp1), j = *((intPtr)gp2);

   return i < j ? LT : i == j ? EQ : GT;
}

有了这些函数，就可以编写一个用于整数异或编码链表的类和一个简单的测试程序，如下所示。（为了控制详细输出，向 xorList 类中添加了一个 verbose 数据成员。）

class IntXorList : public xorList {

public:
   IntXorList()
   {
      PrnFn = PrnInt; CmpFn = CmpInts;
      verbose = 1;
   }
};

int _tmain( int argc, _TCHAR* argv[] )
{
   int *ip, i;
   IntXorList list;

   list.Print();
   for ( i = 10; i > 6; --i ) 
   {
      ip = (int *)malloc( sizeof( int ) );
      *ip = i;
      list.OrderedInsert( (genPtr)ip );
      list.Print();
   }
   printf( "\n" );
   list.Reverse();
   printf( "\nReversed list:\n" );
   list.Print();
   return 0;
}

当构建为控制台应用程序时，函数 `_tmain` 中的示例测试代码会产生以下输出。（为方便验证链表节点中的链接，我添加了一个十六进制数的异或表。）

十六进制异或值表

	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
1	1	0	3	2	5	4	7	6	9	8	B	A	D	C	F	E
2	2	3	0	1	6	7	4	5	A	B	8	9	E	F	C	D
3	3	2	1	0	7	6	5	4	B	A	9	8	F	E	D	C
4	4	5	6	7	0	1	2	3	C	D	E	F	8	9	A	B
5	5	4	7	6	1	0	3	2	D	C	F	E	9	8	B	A
6	6	7	4	5	2	3	0	1	E	F	C	D	A	B	8	9
7	7	6	5	4	3	2	1	0	F	E	D	C	B	A	9	8
8	8	9	A	B	C	D	E	F	0	1	2	3	4	5	6	7
9	9	8	B	A	D	C	F	E	1	0	3	2	5	4	7	6
A	A	B	8	9	E	F	C	D	2	3	0	1	6	7	4	5
B	B	A	9	8	F	E	D	C	3	2	1	0	7	6	5	4
C	C	D	E	F	8	9	A	B	4	5	6	7	0	1	2	3
D	D	C	F	E	9	8	B	A	5	4	7	6	1	0	3	2
E	E	F	C	D	A	B	8	9	6	7	4	5	2	3	0	1
F	F	E	D	C	B	A	9	8	7	6	5	4	3	2	1	0

Header1: 00133228 </, 00000000> Header2: 00133260 </, 00000000> 

[ ]


Header1: 00133228 </, 000000A8> Header2: 00133260 </, 000000E0> 

[ 001332C8<10,00000048> ]


Header1: 00133228 </, 00000150> Header2: 00133260 </, 000000E0> 

[ 00133330< 9,000000E0> 001332C8<10,00000150> ]


Header1: 00133228 </, 000001F8> Header2: 00133260 </, 000000E0> 

[ 00133398< 8,00000118> 00133330< 9,00000150> 001332C8<10,00000150> ]


Header1: 00133228 </, 00000660> Header2: 00133260 </, 000000E0> 

[ 00133400< 7,000001B0> 00133398< 8,00000730> 00133330< 9,00000150> 001332C8<10,00000150> ]


Reversed list:


Header1: 00133228 </, 00000660> Header2: 00133260 </, 000000E0> 

[ 00133400<10,000001B0> 00133398< 9,00000730> 00133330< 8,00000150> 001332C8< 7,00000150> ]

~xorList called upon program termination

Deleting element: 00133260< /,000000E0> 
Deleting element: 001332C8< 7,00000150>  (info at 1333D0)
Deleting element: 00133330< 8,00000150>  (info at 133368)
Deleting element: 00133398< 9,00000730>  (info at 133300)
Deleting element: 00133400<10,000001B0>  (info at 133298)
Deleting element: 00133228< /,00000660>

正如预期的那样，当链表为空时，两个头节点的链接都是 0L。插入第一个元素 (10) 后，其节点位于两个头节点之间。因此，该节点的链接应为头节点地址的异或值，即 00133228 ^ 00133260。使用表格，结果是 00000048，这正是包含数字 10 的节点的 link 字段中显示的值。再举一个例子，在反转后的链表中，包含 9 的节点位于包含 10 和 8 的节点之间。因此，包含 9 的节点的链接应该是其前驱和后继节点地址的异或值，即 00133400 ^ 00133330 = 00000730，如节点所示。可以使用相同的过程在整个插入过程中验证所有链接。请注意，数字 10 到 7 是按该顺序插入的，并且由于插入是按升序进行的，函数 xorList::OrderedInsert 将它们插入到了正确的顺序中。

在 while 循环结束时，链表被反转。我们没有在派生类中实现 Reverse 函数，而是在基类中实现了它。算法很简单：由于链表是双向循环的，设置指向链表头和尾的指针，从两个方向遍历链表，交换每对节点的 info 字段内容，当遍历到达链表中间时停止。

void xorList::Reverse()
{
   xorPtr p, q;
   genPtr g;

   p = StartForwardScan();
   q = StartBackwardScan();
   while ( !EndOfDualScan() ) 
   {
      g = p->info;
      p->info = q->info;
      q->info = g;
      p = MoveForward();
      q = MoveBackward();
   }
}

向 xorList 基类添加另外两个受保护的指针变量：

xorPtr E2, succE2;  // "Cursor" pointers to adjacent
                    // elements in backward traversals

受保护的辅助函数如下：

xorPtr xorList::StartForwardScan()
{
   E1 = hdr1;
   succE1 = Successor( hdr2, hdr1 );
   return succE1;
}

xorPtr xorList::StartBackwardScan()
{
   E2 = Predecessor( hdr2, hdr1 );
   succE2 = hdr2;
   return E2;
}

int xorList::EndOfDualScan()
{
   return (E1 == E2) || (succE1 == E2);
}

xorPtr xorList::MoveBackward()
{
   // E2 != NULL && succE2 != NULL

   _1stepBackward( &E2, &succE2 );
   return E2;
}

函数 xorList::MoveForward 已经编写过了，而函数 xorList::Reverse 正是它存在的原因。此外，函数 xorList::_1stepBackward 也已经编写过了。

泛型、异或编码、双端队列

双端队列（deque，发音为 "deck"）是一种允许在两端进行入队和出队操作的队列。（参见 G.L. Lipovski Object-Oriented Interfacing to 16-BIT Microcontrollers, Prentice-Hall 1993, pp. 71-73; Mark A. Weiss Data Structures and Algorithm Analysis, Benjamin/Cummings 1992, p. 86 Exercise 3.26 and p. 443 Exercise 11.13; Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest Introduction to Algorithms, The MIT Press 1996, p.203 Exercise 11.1-5.）泛型双端队列可以基于 xorList 的功能来实现。

class xorDeck : public xorList {

public:
   void EnqueueAtHdr1( genPtr );
   void EnqueueAtHdr2( genPtr );
   genPtr DequeueFromHdr1();
   genPtr DequeueFromHdr2();
};

void xorDeck::EnqueueAtHdr1( genPtr gp )
{
   xorPtr r = AllocXorStr();

   r->info = gp;
   InsertBetween( r, hdr1, Successor( hdr2, hdr1 ) );
}

void xorDeck::EnqueueAtHdr2( genPtr gp )
{
   xorPtr r = AllocXorStr();

   r->info = gp;
   InsertBetween( r, Predecessor( hdr2, hdr1 ), hdr2 );
}

genPtr xorDeck::DequeueFromHdr1()
{
   if ( IsEmpty() )
   {
      printf( "\nThe deck is empty\n" );
      return NULL;
   }
   return RemoveAtS( hdr1, Successor( hdr2, hdr1 ) );
}

genPtr xorDeck::DequeueFromHdr2()
{
   if ( IsEmpty() )
   {
      printf( "\nThe deck is empty\n" );
      return NULL;
   }
   return RemoveAtP( Predecessor( hdr2, hdr1 ), hdr2 );
}

函数 xorDeck::DequeueFromHdr1 和 xorDeck::DequeueFromHdr2 解释了为什么函数 xorList::RemoveAtS 和 xorList::RemoveAtP 需要返回一个指向它们所移除元素的指针。

泛型、异或编码的栈和队列

鉴于泛型、异或编码、双端队列的实现，将泛型栈和队列实现为 xorDeck 类的特例就变得很简单了。

class xorStack : public xorDeck {

public:
   void Push( genPtr gp ) { EnqueueAtHdr1( gp ); }
   genPtr Pop() { return DequeueFromHdr1(); }
   genPtr Tos();
   genPtr Tos_1();
};

genPtr xorStack::Tos()
{
   if ( Length() >= 1 )
   {
      xorPtr q = Successor( hdr2, hdr1 );

      return q->info;
   }
   else
   {
      printf( "\nThe stack is empty\n" );
      return NULL;
   }
}

genPtr xorStack::Tos_1()
{
   if ( Length() >= 2 )
   {
      xorPtr q = Successor( hdr1, Successor( hdr2, hdr1 ) );

      return q->info;
   }
   else
   {
      printf( "\nNot enough elements on the stack\n" );
      return NULL;
   }
}

请注意，函数 xorStack::Tos 和 xorStack::Tos_1 不会移除栈元素。它们仅仅是“窥视”栈顶的两个元素（如果存在的话）。这两个函数对于使用显式堆栈来跟踪符号的编译器非常有用（参见 Alfred V. Aho 和 Jeffrey D. Ullman 的《编译器设计原理》，Addison-Wesley 1979，第五章）。

class xorQueue : public xorDeck {

public:
   void Enqueue( genPtr gp ) { EnqueueAtHdr2( gp ); }
   genPtr Dequeue() { return DequeueFromHdr1(); }
   void DeleteLast() { DequeueFromHdr2(); }
   int EQtoLast( genPtr );
};

int xorQueue::EQtoLast( genPtr gp )
{
   if ( Length() >= 1 )
   {
      xorPtr r = Predecessor( hdr2, hdr1 );

      return (*CmpFn)( gp, r->info ) == EQ;
   }
   else
   {
      printf( "\nThe queue is empty\n" );
      return NULL;
   }
}

整数异或编码栈和队列

正如处理整数异或编码列表一样，整数异或编码栈和队列可以分别作为 xorStack 和 xorQueue 类的具体实例来实现。对于每种情况，我将展示派生类的定义，以及一个编译为控制台应用程序的简单测试 _tmain 函数，其后是程序输出（省略析构函数打印的信息）。

class IntXorStack : public xorStack {

public:
   IntXorStack()
   {
      PrnFn = PrnInt; CmpFn = CmpInts;
      verbose = 1;
   }
};


int _tmain( int argc, _TCHAR* argv[] )
{
   int *ip, i;
   IntXorStack stack;

   stack.Print();
   for ( i = 10; i > 6; --i ) 
   {
      ip = (int *)malloc( sizeof( int ) );
      *ip = i;
      stack.Push( (genPtr)ip );
      stack.Print();
   }
   printf( "\n" );
   stack.Pop();
   stack.Pop();
   ip = (int *)malloc( sizeof( int ) );
   *ip = 25;
   stack.Push( (genPtr)ip );
   stack.Print();
   printf( "\n" );
   return 0;
}

程序输出

Header1: 002F3228 </, 00000000> Header2: 002F3260 </, 00000000> 

[ ]


Header1: 002F3228 </, 000000A8> Header2: 002F3260 </, 000000E0> 

[ 002F32C8<10,00000048> ]


Header1: 002F3228 </, 00000150> Header2: 002F3260 </, 000000E0> 

[ 002F3330< 9,000000E0> 002F32C8<10,00000150> ]


Header1: 002F3228 </, 000001F8> Header2: 002F3260 </, 000000E0> 

[ 002F3398< 8,00000118> 002F3330< 9,00000150> 002F32C8<10,00000150> ]


Header1: 002F3228 </, 00000660> Header2: 002F3260 </, 000000E0> 

[ 002F3400< 7,000001B0> 002F3398< 8,00000730> 002F3330< 9,00000150> 002F32C8<10,00000150> ]

removing element (at S)002F3228< /,00000660> 
removing element (at S)002F3228< /,000001F8> 


Header1: 002F3228 </, 00000660> Header2: 002F3260 </, 000000E0> 

[ 002F3400<25,00000118> 002F3330< 9,000006C8> 002F32C8<10,00000150> ]

class IntXorQueue : public xorQueue {

public:
   IntXorQueue()
   {
      PrnFn = PrnInt; CmpFn = CmpInts;
      verbose = 1;
   }
};


int _tmain( int argc, _TCHAR* argv[] )
{
   int *ip, i;
   IntXorQueue queue;

   queue.Print();
   for ( i = 10; i > 6; --i ) 
   {
      ip = (int *)malloc( sizeof( int ) );
      *ip = i;
      queue.Enqueue( (genPtr)ip );
      queue.Print();
   }
   printf( "\n" );
   queue.Dequeue();
   queue.Dequeue();
   ip = (int *)malloc( sizeof( int ) );
   *ip = 25;
   queue.Enqueue( (genPtr)ip );
   queue.Print();
   printf( "\n" );
   return 0;
}

程序输出

Header1: 00523228 </, 00000000> Header2: 00523260 </, 00000000> 

[ ]


Header1: 00523228 </, 000000A8> Header2: 00523260 </, 000000E0> 

[ 005232C8<10,00000048> ]


Header1: 00523228 </, 000000A8> Header2: 00523260 </, 00000118> 

[ 005232C8<10,00000118> 00523330< 9,000000A8> ]


Header1: 00523228 </, 000000A8> Header2: 00523260 </, 000001B0> 

[ 005232C8<10,00000118> 00523330< 9,00000150> 00523398< 8,00000150> ]


Header1: 00523228 </, 000000A8> Header2: 00523260 </, 00000628> 

[ 005232C8<10,00000118> 00523330< 9,00000150> 00523398< 8,00000730> 00523400< 7,000001F8> ]

removing element (at S)00523228< /,000000A8> 
removing element (at S)00523228< /,00000150> 


Header1: 00523228 </, 000001F8> Header2: 00523260 </, 000000E0> 

[ 00523398< 8,00000628> 00523400< 7,00000150> 005232C8<25,00000660> ]

运行代码

为了撰写本文，我将所有代码放在我电脑 D: 盘下一个名为 XORstructures 的顶层目录下。该目录包含在可下载的 ZIP 文件中，可以放置在任何位置，但前提是所有包含路径都必须相应更改。每个子目录（Common 除外）都包含一个非托管 C++ 解决方案，并且每个解决方案都是一个控制台应用程序。所有代码都是使用 Visual Studio 2010 编写、编译和构建的。这些解决方案按依赖顺序列出如下：

GxorList：泛型、双向、异或编码链表的完整实现。

GxorDeck：泛型双端队列的完整实现（依赖于 GxorList，并支持栈和队列作为特例）。

MinGxorList: GxorList 的最小化实现（包含本文中描述的代码）。

MinGxorDeck：符合 MinGxorList 的泛型双端队列的实现。

IntXorList：整数异或编码链表的实现（可以使用 GxorList 或 MinXorList）。

IntXorStack 和 IntXorQueue：整数异或编码栈和队列的实现（可以使用 GxorDeck 或 MinGxorDeck）。

	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
1	1	0	3	2	5	4	7	6	9	8	B	A	D	C	F	E
2	2	3	0	1	6	7	4	5	A	B	8	9	E	F	C	D
3	3	2	1	0	7	6	5	4	B	A	9	8	F	E	D	C
4	4	5	6	7	0	1	2	3	C	D	E	F	8	9	A	B
5	5	4	7	6	1	0	3	2	D	C	F	E	9	8	B	A
6	6	7	4	5	2	3	0	1	E	F	C	D	A	B	8	9
7	7	6	5	4	3	2	1	0	F	E	D	C	B	A	9	8
8	8	9	A	B	C	D	E	F	0	1	2	3	4	5	6	7
9	9	8	B	A	D	C	F	E	1	0	3	2	5	4	7	6
A	A	B	8	9	E	F	C	D	2	3	0	1	6	7	4	5
B	B	A	9	8	F	E	D	C	3	2	1	0	7	6	5	4
C	C	D	E	F	8	9	A	B	4	5	6	7	0	1	2	3
D	D	C	F	E	9	8	B	A	5	4	7	6	1	0	3	2
E	E	F	C	D	A	B	8	9	6	7	4	5	2	3	0	1
F	F	E	D	C	B	A	9	8	7	6	5	4	3	2	1	0

	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
1	1	0	3	2	5	4	7	6	9	8	B	A	D	C	F	E
2	2	3	0	1	6	7	4	5	A	B	8	9	E	F	C	D
3	3	2	1	0	7	6	5	4	B	A	9	8	F	E	D	C
4	4	5	6	7	0	1	2	3	C	D	E	F	8	9	A	B
5	5	4	7	6	1	0	3	2	D	C	F	E	9	8	B	A
6	6	7	4	5	2	3	0	1	E	F	C	D	A	B	8	9
7	7	6	5	4	3	2	1	0	F	E	D	C	B	A	9	8
8	8	9	A	B	C	D	E	F	0	1	2	3	4	5	6	7
9	9	8	B	A	D	C	F	E	1	0	3	2	5	4	7	6
A	A	B	8	9	E	F	C	D	2	3	0	1	6	7	4	5
B	B	A	9	8	F	E	D	C	3	2	1	0	7	6	5	4
C	C	D	E	F	8	9	A	B	4	5	6	7	0	1	2	3
D	D	C	F	E	9	8	B	A	5	4	7	6	1	0	3	2
E	E	F	C	D	A	B	8	9	6	7	4	5	2	3	0	1
F	F	E	D	C	B	A	9	8	7	6	5	4	3	2	1	0

	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
1	1	0	3	2	5	4	7	6	9	8	B	A	D	C	F	E
2	2	3	0	1	6	7	4	5	A	B	8	9	E	F	C	D
3	3	2	1	0	7	6	5	4	B	A	9	8	F	E	D	C
4	4	5	6	7	0	1	2	3	C	D	E	F	8	9	A	B
5	5	4	7	6	1	0	3	2	D	C	F	E	9	8	B	A
6	6	7	4	5	2	3	0	1	E	F	C	D	A	B	8	9
7	7	6	5	4	3	2	1	0	F	E	D	C	B	A	9	8
8	8	9	A	B	C	D	E	F	0	1	2	3	4	5	6	7
9	9	8	B	A	D	C	F	E	1	0	3	2	5	4	7	6
A	A	B	8	9	E	F	C	D	2	3	0	1	6	7	4	5
B	B	A	9	8	F	E	D	C	3	2	1	0	7	6	5	4
C	C	D	E	F	8	9	A	B	4	5	6	7	0	1	2	3
D	D	C	F	E	9	8	B	A	5	4	7	6	1	0	3	2
E	E	F	C	D	A	B	8	9	6	7	4	5	2	3	0	1
F	F	E	D	C	B	A	9	8	7	6	5	4	3	2	1	0