一个简化的问题示例
链表的难点在于必须复制链表处理函数来处理不同的对象，即便逻辑是完全相同的。例如：
两个结构类似的链表
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 类，则对指向解除函数的指针的配置和存储只能进行一次。
文章整理：西部数码--专业提供域名注册、虚拟主机服务
http://www.west263.com
以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢!
