一个简化的问题示例
链表的难点在于必须复制链表处理函数来处理不同的对象,即便逻辑是完全相同的。例如:
两个结构类似的链表
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 结构需要包含一个一般的解除函数指针,这个指针可用来在将节点从链表中删除并解除它之前释放内存(或者关闭文件,或者调用关闭方法)。