一個(gè)簡(jiǎn)化的問(wèn)題示例
鏈表的難點(diǎn)在于必須復(fù)制鏈表處理函數(shù)來(lái)處理不同的對(duì)象，即便邏輯是完全相同的。例如兩個(gè)結(jié)構(gòu)類似的鏈表:
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; |
上面定義的兩個(gè)結(jié)構(gòu)只有很小的一點(diǎn)差別。OBJECT_B 和 OBJECT_A 之間只差一個(gè)整型變量。但是，在編譯器看來(lái)，它們?nèi)匀皇欠浅２煌?。必須為存?chǔ)在鏈表中的每個(gè)對(duì)象復(fù)制用來(lái)添加、刪除和搜索鏈表的函數(shù)。為了解決這個(gè)問(wèn)題，可以使用具有全部三個(gè)變量的一個(gè)聯(lián)合或結(jié)構(gòu)，其中整數(shù) c 并不是在所有的情況下都要使用。這可能變得非常復(fù)雜，并會(huì)形成不良的編程風(fēng)格。
C 代碼解決方案：虛擬鏈表
此問(wèn)題更好的解決方案之一是虛擬鏈表。虛擬鏈表是只包含鏈表指針的鏈表。對(duì)象存儲(chǔ)在鏈表結(jié)構(gòu)背后。這一點(diǎn)是這樣實(shí)現(xiàn)的，首先為鏈表節(jié)點(diǎn)分配內(nèi)存，接著為對(duì)象分配內(nèi)存，然后將這塊內(nèi)存分配給鏈表節(jié)點(diǎn)指針，如下所示：
虛擬鏈表結(jié)構(gòu)的一種實(shí)現(xiàn)
typedef struct liststruct
{
liststruct *next;
} LIST, *pLIST;
pLIST Head = NULL;
pLIST AddToList( pLIST Head,
void * data, size_t datasize )
{
pLIST newlist=NULL;
void *p;
// 分配節(jié)點(diǎn)內(nèi)存和數(shù)據(jù)內(nèi)存
newlist = (pLIST) malloc
( datasize + sizeof( LIST ) );
// 為這塊數(shù)據(jù)緩沖區(qū)指定一個(gè)指針
p = (void *)( newlist + 1 );
// 復(fù)制數(shù)據(jù)
memcpy( p, data, datasize );
// 將這個(gè)節(jié)點(diǎn)指定給鏈表的表頭
if( Head )
{
newlist->next = Head;
}
else
newlist->next = NULL;
Head = newlist;
return Head;
} |
鏈表節(jié)點(diǎn)現(xiàn)在建立在數(shù)據(jù)值副本的基本之上。這個(gè)版本能很好地處理標(biāo)量值，但不能處理帶有用 malloc 或 new 分配的元素的對(duì)象。要處理這些對(duì)象，LIST 結(jié)構(gòu)需要包含一個(gè)一般的解除函數(shù)指針，這個(gè)指針可用來(lái)在將節(jié)點(diǎn)從鏈表中刪除并解除它之前釋放內(nèi)存（或者關(guān)閉文件，或者調(diào)用關(guān)閉方法）。
一個(gè)帶有解除函數(shù)的鏈表
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;
// 分配節(jié)點(diǎn)內(nèi)存和數(shù)據(jù)內(nèi)存
newlist = (pLIST) malloc
( datasize + sizeof( LIST ) );
// 為這塊數(shù)據(jù)緩沖區(qū)指定一個(gè)指針
p = (void *)( newlist + 1 );
// 復(fù)制數(shù)據(jù)
memcpy( p, data, datasize );
newlist->DestructFunc = Destructor;
// 將這個(gè)節(jié)點(diǎn)指定給鏈表的表頭
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 )
{
// 對(duì)節(jié)點(diǎn)指針進(jìn)行類型轉(zhuǎn)換
pLIST pl = (pLIST)p;
// 對(duì)數(shù)據(jù)指針進(jìn)行類型轉(zhuǎn)換
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 );
// 該對(duì)象已被復(fù)制，現(xiàn)在刪除原來(lái)的對(duì)象
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 );
} |
在每個(gè)鏈表節(jié)點(diǎn)中包含同一個(gè)解除函數(shù)的同一個(gè)指針?biāo)坪跏抢速M(fèi)內(nèi)存空間。確實(shí)如此，但只有鏈表始終包含相同的對(duì)象才屬于這種情況。按這種方式編寫鏈表允許您將任何對(duì)象放在鏈表中的任何位置。大多數(shù)鏈表函數(shù)要求對(duì)象總是相同的類型或類。
虛擬鏈表則無(wú)此要求。它所需要的只是將對(duì)象彼此區(qū)分開的一種方法。要實(shí)現(xiàn)這一點(diǎn)，您既可以檢測(cè)解除函數(shù)指針的值，也可以在鏈表中所用的全部結(jié)構(gòu)前添加一個(gè)類型值并對(duì)它進(jìn)行檢測(cè)。
當(dāng)然，如果要將鏈表編寫為一個(gè) C++ 類，則對(duì)指向解除函數(shù)的指針的設(shè)置和存儲(chǔ)只能進(jìn)行一次。
C++ 解決方案：類鏈表
本解決方案將 CList 類定義為從 LIST 結(jié)構(gòu)導(dǎo)出的一個(gè)類，它通過(guò)存儲(chǔ)解除函數(shù)的單個(gè)值來(lái)處理單個(gè)存儲(chǔ)類型。請(qǐng)注意添加的 GetCurrentData() 函數(shù)，該函數(shù)完成從鏈表節(jié)點(diǎn)指針到數(shù)據(jù)偏移指針的數(shù)學(xué)轉(zhuǎn)換。一個(gè)虛擬鏈表對(duì)象
// 定義解除函數(shù)指針
typedef void (*ListNodeDestructor)
( void * );
// 未添加解除函數(shù)指針的鏈表
typedef struct ndliststruct
{
ndliststruct *next;
} ND_LIST, *pND_LIST;
// 定義處理一種數(shù)據(jù)類型的鏈表類
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;
};
// 用正確的起始值構(gòu)造這個(gè)鏈表對(duì)象
CList::CList(ListNodeDestructor Destructor)
: m_HeadOfList(NULL),
m_CurrentNode(NULL)
{
m_DestructFunc = Destructor;
}
// 在解除對(duì)象以后刪除鏈表
CList::~CList()
{
DeleteList(m_HeadOfList);
}
// 向鏈表中添加一個(gè)新節(jié)點(diǎn)
pND_LIST CList::AddToList
( void * data, size_t datasize )
{
pND_LIST newlist=NULL;
void *p;
// 分配節(jié)點(diǎn)內(nèi)存和數(shù)據(jù)內(nèi)存
newlist = (pND_LIST) malloc
( datasize + sizeof( ND_LIST ) );
// 為這塊數(shù)據(jù)緩沖區(qū)指定一個(gè)指針
p = (void *)( newlist + 1 );
// 復(fù)制數(shù)據(jù)
memcpy( p, data, datasize );
// 將這個(gè)節(jié)點(diǎn)指定給鏈表的表頭
if( m_HeadOfList )
{
newlist->next = m_HeadOfList;
}
else
newlist->next = NULL;
m_HeadOfList = newlist;
return m_HeadOfList;
}
// 將當(dāng)前的節(jié)點(diǎn)數(shù)據(jù)作為 void 類型返回，
以便調(diào)用函數(shù)能夠?qū)⑺D(zhuǎn)換為任何類型
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;
}
}
// 創(chuàng)建一個(gè)要在鏈表中創(chuàng)建和存儲(chǔ)的結(jié)構(gòu)
typedef struct ListDataStruct
{
LPSTR p;
} LIST_DATA, *pND_LIST_DATA;
// 定義標(biāo)準(zhǔn)解除函數(shù)
void ClassListDataDestructor( void *p )
{
// 對(duì)節(jié)點(diǎn)指針進(jìn)行類型轉(zhuǎn)換
pND_LIST pl = (pND_LIST)p;
// 對(duì)數(shù)據(jù)指針進(jìn)行類型轉(zhuǎn)換
pND_LIST_DATA pLD = (pND_LIST_DATA)
( pl + 1 );
delete pLD->p;
}
// 測(cè)試上面的代碼
void MyCListClassTest()
{
// 創(chuàng)建鏈表類
CList* pA_List_of_Data =
new CList(ClassListDataDestructor);
// 創(chuàng)建數(shù)據(jù)對(duì)象
pND_LIST_DATA d = new LIST_DATA;
d->p = new char[24];
strcpy( d->p, "Hello" );
// 創(chuàng)建指向鏈表頂部的局部指針
pND_LIST Head = NULL;
//向鏈表中添加一些數(shù)據(jù)
Head = pA_List_of_Data->AddToList
( (void *) d,
sizeof( pND_LIST_DATA ) );
// 該對(duì)象已被復(fù)制，現(xiàn)在刪除原來(lái)的對(duì)象
delete d;
// 確認(rèn)它已被存儲(chǔ)
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 ) );
// 該對(duì)象已被復(fù)制，現(xiàn)在刪除原來(lái)的對(duì)象
delete d;
// 確認(rèn)它已被存儲(chǔ)
p = ((pND_LIST_DATA)
pA_List_of_Data->GetCurrentData())->p;
// 刪除鏈表類，析構(gòu)函數(shù)將刪除鏈表
delete pA_List_of_Data;
} |
小結(jié)
從前面的討論來(lái)看，似乎僅編寫一個(gè)簡(jiǎn)單的鏈表就要做大量的工作，但這只須進(jìn)行一次。很容易將這段代碼擴(kuò)充為一個(gè)處理排序、搜索以及各種其他任務(wù)的 C++ 類，并且這個(gè)類可以處理任何數(shù)據(jù)對(duì)象或類（在一個(gè)項(xiàng)目中，它處理大約二十個(gè)不同的對(duì)象）。您永遠(yuǎn)不必重新編寫這段代碼。