虛擬鏈表和類鏈表可以很好地實現這一點
T. W. Burger
Thomas Wolfgang Burger Consulting公司的老板
2000 年 9 月
內容：
簡化的問題
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 );
}
在每個鏈表節點中包含同一個解除函數的同一個指針似乎是浪費內存空間。確實如此，但只有鏈表始終包含相同的對象才屬於這種情況。按這種方式編寫鏈表答應您將任何對象放在鏈表中的任何位置。大多數鏈表函數要求對象總是相同的類型或類。虛擬鏈表則無此要求。它所需要的只是將對象彼此區分開的一種方法。要實現這一點，您既可以檢測解除函數指針的值，也可以在鏈表中所用的全部結構前添加一個類型值並對它進行檢測。當然，假如要將鏈表編寫為一個 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++ 類，並且這個類可以處理任何數據對象或類（在一個項目中，它處理大約二十個不同的對象）。您永遠不必重新編寫這段代碼。
參考資源
* The Linux C Programming Lists 旨在幫助人們用 C 語言進行 Linux 編程，其中包括許多到郵件列表、常見問題解答、教程以及其他內容的鏈接。
* Microsoft Foundation Class 在其 CList 類中提供了類似的功能。MFC 中的 CList 以及別的類要求類型或類只能是一種類型，程序員對代碼沒有控制權，這一點與從零開始構建鏈表不同。
作者簡介
Thomas Wolfgang Burger 是 Thomas Wolfgang Burger Consulting 公司的老板。自 1978 年以來，他做過咨詢人員、教師、分析員和應用程序開發員。可以通過
[email protected] 與他聯系。
您對這篇文章的看法如何？
真棒！ 好文章 一般，尚可 需提高 太差！
意見
(c) Copyright IBM Corp. 2001, (c) Copyright IBM China 2001, All Right Reserved
隱私 法律 聯系
