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

T. W. Burger ([e-mail]), 老板, Thomas Wolfgang Burger Consulting 公司

2000 年 9 月 01 日

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

<!--START RESERVED FOR FUTURE USE INCLUDE FILES--><!-- include java script once we verify teams wants to use this and it will work on dbcs and cyrillic characters --><!--END RESERVED FOR FUTURE USE INCLUDE FILES-->

一个简化的问题示例

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

两个结构类似的链表

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++ 类，则对指向解除函数的指针的设置和存储只能进行一次。

C++ 解决方案：类链表

本解决方案将 CList 类定义为从 LIST 结构导出的一个类，它通过存储解除函数的单个值来处理单个存储类型。请注意添加的 GetCurrentData() 函数，该函数完成从链表节点指针到数据偏移指针的数学转换。

一个虚拟链表对象

// 定义解除函数指针
typedef void (*ListNodeDestructor)( void * );
// 未添加解除函数指针的链表
typedef struct ndliststruct
{
    ndliststruct *next;
} ND_LIST, *pND_LIST;
// 定义处理一种数据类型的链表类
class CList : public ND_LIST
{
public:
    CList(ListNodeDestructor);
    ~CList();
    pND_LIST AddToList( void * data, size_t datasize );
    void *GetCurrentData();
    void DeleteList( pND_LIST Head );
private:
    pND_LIST m_HeadOfList;
    pND_LIST m_CurrentNode;
    ListNodeDestructor m_DestructFunc;
};
// 用正确的起始值构造这个链表对象
CList::CList(ListNodeDestructor Destructor)
    : m_HeadOfList(NULL), m_CurrentNode(NULL)
{
    m_DestructFunc = Destructor;
}
// 在解除对象以后删除链表
CList::~CList()
{
    DeleteList(m_HeadOfList);
}
// 向链表中添加一个新节点
pND_LIST CList::AddToList( void * data, size_t datasize )
{
pND_LIST newlist=NULL;
void *p;
    // 分配节点内存和数据内存
    newlist = (pND_LIST) malloc( datasize + sizeof( ND_LIST ) );
    // 为这块数据缓冲区指定一个指针
    p = (void *)( newlist + 1 );
    // 复制数据
    memcpy( p, data, datasize );
    // 将这个节点指定给链表的表头
    if( m_HeadOfList )
    {
        newlist->next = m_HeadOfList;
    }
    else
        newlist->next = NULL;
    m_HeadOfList = newlist;
    return m_HeadOfList;
}
// 将当前的节点数据作为 void 类型返回，以便调用函数能够将它转换为任何类型
void * CList::GetCurrentData()
{
    return (void *)(m_CurrentNode+1);
}
// 删除已分配的链表
void CList::DeleteList( pND_LIST Head )
{
    pND_LIST Next;
    while( Head )
    {
        Next = Head->next;
        m_DestructFunc( (void *) Head );
        free( Head );
        Head = Next;
    }
}
// 创建一个要在链表中创建和存储的结构
typedef struct ListDataStruct
{
    LPSTR p;
} LIST_DATA, *pND_LIST_DATA;
// 定义标准解除函数
void ClassListDataDestructor( void *p )
{
    // 对节点指针进行类型转换
    pND_LIST pl = (pND_LIST)p;
    // 对数据指针进行类型转换
    pND_LIST_DATA pLD = (pND_LIST_DATA) ( pl + 1 );
    delete pLD->p;
}
// 测试上面的代码
void MyCListClassTest()
{
    // 创建链表类
    CList* pA_List_of_Data = new CList(ClassListDataDestructor);
    // 创建数据对象

    pND_LIST_DATA d = new LIST_DATA;
    d->p = new char[24];
    strcpy( d->p, "Hello" ); 
    // 创建指向链表顶部的局部指针
    pND_LIST Head = NULL;
    //向链表中添加一些数据
    Head = pA_List_of_Data->AddToList( (void *) d, 
    sizeof( pND_LIST_DATA ) );
    // 该对象已被复制，现在删除原来的对象
    delete d;
    // 确认它已被存储
    char * p = ((pND_LIST_DATA) pA_List_of_Data->GetCurrentData())->p;
    d = new LIST_DATA;
    d->p = new char[24];
    strcpy( d->p, "World" ); 
    Head = pA_List_of_Data->AddToList( (void *) d, sizeof( pND_LIST_DATA ) );
    // 该对象已被复制，现在删除原来的对象
    delete d;
    // 确认它已被存储
    p = ((pND_LIST_DATA) pA_List_of_Data->GetCurrentData())->p;
    // 删除链表类，析构函数将删除链表
    delete pA_List_of_Data;
}

小结

从前面的讨论来看，似乎仅编写一个简单的链表就要做大量的工作，但这只须进行一次。很容易将这段代码扩充为一个处理排序、搜索以及各种其他任务的 C++ 类，并且这个类可以处理任何数据对象或类（在一个项目中，它处理大约二十个不同的对象）。您永远不必重新编写这段代码。