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