C++中如何构造通用的对象链表

在C/C++中如何构造通用的对象链表2009-10-26一个简化的问题示例

链表的难点在于必须复制链表处理函数来处理不同的对象，即便逻辑是完全相同的。例如两个结构类似的链表:

struct Struct_Object_A
{
  int a;
  int b;
  Struct_Object_A *next;
}OBJECT_A;
typedef struct Struct_Object_B
{
  int a;
  int b;
  int c;
  Struct_Object_B *next;
}OBJECT_B;

上面定义的两个结构只有很小的一点差别。OBJECT_B 和 OBJECT_A 之间只差一个整型变量。但是，在编译器看来，它们仍然是非常不同的。必须为存储在链表中的每个对象复制用来添加、删除和搜索链表的函数。为了解决这个问题，可以使用具有全部三个变量的一个联合或结构，其中整数 c 并不是在所有的情况下都要使用。这可能变得非常复杂，并会形成不良的编程风格。

C 代码解决方案：虚拟链表

此问题更好的解决方案之一是虚拟链表。虚拟链表是只包含链表指针的链表。对象存储在链表结构背后。这一点是这样实现的，首先为链表节点分配内存，接着为对象分配内存，然后将这块内存分配给链表节点指针，如下所示：

虚拟链表结构的一种实现

typedef struct liststruct
{
  liststruct *next;
}LIST, *pLIST;
pLIST Head = NULL;
pLIST AddToList（pLIST Head, void * data, size_t datasize）
{
  pLIST newlist = NULL;
  void *p;
  // 分配节点内存和数据内存
  newlist = （pLIST） malloc（datasize + sizeof（LIST））;
  // 为这块数据缓冲区指定一个指针
  p = （void *）（newlist + 1）;
  // 复制数据
  memcpy（p, data, datasize）;
  // 将这个节点指定给链表的表头
  if（Head）
    newlist->next = Head;
  else
    newlist->next = NULL;
  Head = newlist;
  return Head;
}

链表节点现在建立在数据值副本的基本之上。这个版本能很好地处理标量值，但不能处理带有用 malloc 或 new 分配的元素的对象。要处理这些对象，LIST 结构需要包含一个一般的解除函数指针，这个指针可用来在将节点从链表中删除并解除它之前释放内存（或者关闭文件，或者调用关闭方法）。

一个带有解除函数的链表

typedef void （*ListNodeDestructor）（void *）;
typedef struct liststruct
{
  ListNodeDestructor DestructFunc;
  liststruct *next;
}LIST, *pLIST;
pLIST AddToList（pLIST Head, void * data, size_t datasize, ListNodeDestructor Destructor）
{
  pLIST newlist = NULL;
  void *p;
  // 分配节点内存和数据内存
  newlist = （pLIST）malloc（datasize + sizeof（LIST））;
  // 为这块数据缓冲区指定一个指针
  p = （void *）（newlist + 1）;
  // 复制数据
  memcpy（p, data, datasize）;
  newlist->DestructFunc = Destructor;
  // 将这个节点指定给链表的表头
  if（Head）
    newlist->next = Head;
  else
    newlist->next = NULL;
  Head = newlist;
  return Head;
}
void DeleteList（pLIST Head）
{
  pLIST Next;
  while（Head）
  {
    Next = Head->next;
    Head->DestructFunc（（void *） Head）;
    free（Head）;
    Head = Next;
  }
}
typedef struct ListDataStruct
{
  LPSTR p;
}LIST_DATA, *pLIST_DATA;
void ListDataDestructor（void *p）
{
  // 对节点指针进行类型转换
  pLIST pl = （pLIST）p;
  // 对数据指针进行类型转换
  pLIST_DATA pLD = （pLIST_DATA）（pl + 1）;
  delete pLD->p;
}
pLIST Head = NULL;
void TestList（）
{
  pLIST_DATA d = new LIST_DATA;
  d->p = new char[24];
  strcpy（d->p, "Hello"）;
  Head = AddToList（Head, （void *）d, sizeof（pLIST_DATA）, ListDataDestructor）;
  // 该对象已被复制，现在删除原来的对象
  delete d;
  d = new LIST_DATA;
  d->p = new char[24];
  strcpy（d->p, "World"）;
  Head = AddToList（Head, （void *）d, sizeof（pLIST_DATA）, ListDataDestructor）;
  delete d;
  // 释放链表
  DeleteList（Head）;
}