在C/C++中如何構造通用的對象鏈表
2019-11-17 05:28:59
供稿：網友
一個簡化的問題示例
鏈表的難點在于必須復制鏈表處理函數來處理不同的對象，即便邏輯是完全相同的。例如兩個結構類似的鏈表:
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(voi
