分享
 
 
 

技巧:在C/C++中如何构造通用的对象链表

王朝c/c++·作者佚名  2008-05-18
窄屏简体版  字體: |||超大  

虚拟链表和类链表可以很好地实现这一点

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 年以来,他做过咨询人员、教师、分析员和应用程序开发员。可以通过 twburger@bigfoot.com 与他联系。

您对这篇文章的看法如何?

真棒! 好文章 一般,尚可 需提高 太差!

意见

(c) Copyright IBM Corp. 2001, (c) Copyright IBM China 2001, All Right Reserved

隐私 法律 联系

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有