在C/C++中如何结构通用的工具链表

副标题#e#

一个简化的问题示例

链表的难点在于必需复制链表处理惩罚函数来处理惩罚差异的工具，即便逻辑是完全沟通的。譬喻两个布局雷同的链表:

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

#p#副标题#e#

在每个链表节点中包括同一个清除函数的同一个指针好像是挥霍内存空间。确实如此，但只有链表始终包括沟通的工具才属于这种环境。按这种方法编写链表答允您将任何工具放在链表中的任何位置。大大都链表函数要求工具老是沟通的范例或类。

#p#分页标题#e#

虚拟链表则无此要求。它所需要的只是将工具互相区分隔的一种要领。要实现这一点，您既可以检测清除函数指针的值，也可以在链表中所用的全部布局前添加一个范例值并对它举办检测。

虽然，假如要将链表编写为一个 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++ 类，而且这个类可以处理惩罚任何数据工具或类（在一个项目中，它处理惩罚约莫二十个差异的工具）。您永远不必从头编写这段代码。