在 C/C++中怎么样构造通用的对象链表

您是否做过这样一个项目，它要求您在内存中保存数目不定的若干不同对象？对于某些情况，二叉树是最佳选择，但在通常情况下，更简单的链表是显而易见的选择。

一个简化的问题示例

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

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 ); }

在每个链表节点中包含同一个解除函数的同一个指针似乎是浪费内存空间。确实如此，但只有链表始终包含相同的对象才属于这种情况。按这种方式编写链表允许您将任何对象放在链表中的任何位置。大多数链表函数要求对象总是相同的类型或类。虚拟链表则无此要求。它所需要的只是将对象彼此区分开的一种方法。要实现这一点，您既可以检测解除函数指针的值，也可以在链表中所用的全部结构前添加一个类型值并对它进行检测。当然，如果要将链表编写为一个 C++ 类，则对指向解除函数的指针的设置和存储只能进行一次。

 如果您对本文有任何疑问或者建议，请到讨论区发表您的意见: >> 论坛入口 <<