(轉(zhuǎn)載至：http://www.ibm.com/developerworks/cn/linux/l-tip-prompt/tip02/，感謝T. W. Burger先生)

一個(gè)簡(jiǎn)化的問題示例

鏈表的難點(diǎn)在于必須復(fù)制鏈表處理函數(shù)來處理不同的對(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è)整型變量。但是，在編譯器看來，它們?nèi)匀皇欠浅２煌摹１仨殲榇鎯?chǔ)在鏈表中的每個(gè)對(duì)象復(fù)制用來添加、刪除和搜索鏈表的函數(shù)。為了解決這個(gè)問題，可以使用具有全部三個(gè)變量的一個(gè)聯(lián)合或結(jié)構(gòu)，其中整數(shù) c 并不是在所有的情況下都要使用。這可能變得非常復(fù)雜，并會(huì)形成不良的編程風(fēng)格。

回頁(yè)首

C 代碼解決方案：虛擬鏈表

此問題更好的解決方案之一是虛擬鏈表。虛擬鏈表是只包含鏈表指針的鏈表。對(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;}elsenewlist->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è)指針可用來在將節(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;}elsenewlist->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)在刪除原來的對(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ì)象總是相同的類型或類。虛擬鏈表則無此要求。它所需要的只是將對(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)行一次。

回頁(yè)首

C++ 解決方案：類鏈表

本解決方案將 CList 類定義為從 LIST 結(jié)構(gòu)導(dǎo)出的一個(gè)類，它通過存儲(chǔ)解除函數(shù)的單個(gè)值來處理單個(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;}elsenewlist->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)在刪除原來的對(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)在刪除原來的對(duì)象delete d;// 確認(rèn)它已被存儲(chǔ)p = ((pND_LIST_DATA) pA_List_of_Data->GetCurrentData())->p;// 刪除鏈表類，析構(gòu)函數(shù)將刪除鏈表delete pA_List_of_Data; }

?

回頁(yè)首

小結(jié)

從前面的討論來看，似乎僅編寫一個(gè)簡(jiǎn)單的鏈表就要做大量的工作，但這只須進(jìn)行一次。很容易將這段代碼擴(kuò)充為一個(gè)處理排序、搜索以及各種其他任務(wù)的 C++ 類，并且這個(gè)類可以處理任何數(shù)據(jù)對(duì)象或類（在一個(gè)項(xiàng)目中，它處理大約二十個(gè)不同的對(duì)象）。您永遠(yuǎn)不必重新編寫這段代碼。

轉(zhuǎn)載于:https://www.cnblogs.com/yin-jingyu/archive/2012/03/06/2381315.html

總結(jié)

以上是生活随笔為你收集整理的技巧：在 C/C++中如何构造通用的对象链表的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。