T. W. Burger (twburger@bigfoot.com), 老板, Thomas Wolfgang Burger Consulting 公司
2000 年 9 月 01 日
您是否做过这样一个项目,它要求您在内存中保存数目不定的若干不同对象?对于某些情况,二叉树是最佳选择,但在通常情况下,更简单的链表是显而易见的选择。
<!--START RESERVED FOR FUTURE USE INCLUDE FILES--><!-- include java script once we verify teams wants to use this and it will work on dbcs and cyrillic characters --><!--END RESERVED FOR FUTURE USE INCLUDE FILES-->
一个简化的问题示例
链表的难点在于必须复制链表处理函数来处理不同的对象,即便逻辑是完全相同的。例如:
两个结构类似的链表
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++ 类,并且这个类可以处理任何数据对象或类(在一个项目中,它处理大约二十个不同的对象)。您永远不必重新编写这段代码。
分享到:
相关推荐
复杂的C/C++声明并不是好的编程风格;这里仅仅是教你如何去理解这些声明。注意:为了保证能够在同一行上显示代码和相关注释,本文最好在至少1024x768分辨率的显示器上阅读。链表的难点在于必须复制链表处理函数来...
技巧:在 C-C++中如何构造通用的对象链表
复杂的C/C++声明并不是好的编程风格;这里仅仅是教你如何去理解这些声明。注意:为了保证能够在同一行上显示代码和相关注释,本文在至少1024x768分辨率的显示器上阅读。链表的难点在于必须复制链表处理函数来处理...
这些关键字能作为函数和变量的标识符在C程序中使用,尽管C++包含了所有的C,但显然没有任何C++编译器能编译这样的C程序。 C程序员可以省略函数原型,而C++不可以,一个不带参数的C函数原型必须把void写出来。而C++...
这样声明之后,相当于告诉C, 函数const void f(void)是在C++语言的文件中声明或者实现的,c程序可以使用这个C++中的函数了,从而实现C++和c的混合编程。 13、编写一个函数,作用是把一个char组成的字符串...
C语言和C++语言中是用指针来实现链表结构的,由于Java语言不提供指针,所以有人认为在Java语言中不能实现链表,其实不然,Java语言比C和C++更容易实现链表结构。Java语言中的对象引用实际上是一个指针(本文中的...
在Windows中有各种GUI对象(不要和C++对象混淆),当你在进行绘图就需要利用这些对象。而各种对象都拥有各种属性,下面分别讲述各种GUI对象和拥有的属性。 字体对象CFont用于输出文字时选用不同风格和大小的字体。可...
本书系统地介绍Visual C++ 2005进行流媒体编程的基本思路和方法,采用案例为主的叙述方式,将大量的技术理论融入具体的案例剖析中。采用的案例均来源于作者实际开发工作,具有很好的实用价值,可以帮助读者在开发中...
本书系统地介绍Visual C++ 2005进行流媒体编程的基本思路和方法,采用案例为主的叙述方式,将大量的技术理论融入具体的案例剖析中。采用的案例均来源于作者实际开发工作,具有很好的实用价值,可以帮助读者在开发中...
本书系统地介绍Visual C++ 2005进行流媒体编程的基本思路和方法,采用案例为主的叙述方式,将大量的技术理论融入具体的案例剖析中。采用的案例均来源于作者实际开发工作,具有很好的实用价值,可以帮助读者在开发中...
本书系统地介绍Visual C++ 2005进行流媒体编程的基本思路和方法,采用案例为主的叙述方式,将大量的技术理论融入具体的案例剖析中。采用的案例均来源于作者实际开发工作,具有很好的实用价值,可以帮助读者在开发中...
本书系统地介绍Visual C++ 2005进行流媒体编程的基本思路和方法,采用案例为主的叙述方式,将大量的技术理论融入具体的案例剖析中。采用的案例均来源于作者实际开发工作,具有很好的实用价值,可以帮助读者在开发中...
本书系统地介绍Visual C++ 2005进行流媒体编程的基本思路和方法,采用案例为主的叙述方式,将大量的技术理论融入具体的案例剖析中。采用的案例均来源于作者实际开发工作,具有很好的实用价值,可以帮助读者在开发中...
本书系统地介绍Visual C++ 2005进行流媒体编程的基本思路和方法,采用案例为主的叙述方式,将大量的技术理论融入具体的案例剖析中。采用的案例均来源于作者实际开发工作,具有很好的实用价值,可以帮助读者在开发中...
1.1 MFC与C++ 1.2 VC++组件 1.3 安装 1.3.1 环境 1.3.2 安装过程 第2章 开发环境 2.1 主窗口 2.2 工具栏 2.2.1 Shaod工具栏 2.2.2 Build Mini-bar工具栏 2.3 菜单栏 2.3.1 File菜单 ...
然而一但掌握了基于接口的设计方法,就能够在服务于众多应用程序的通用接口基础上建立应用程序,从而加速开发,在一些c++环境中的基础类库就体现了这种效果。 增加对现有软件的重用---接口实现库,能够减少初始...
2.7.4 C语言中的简写形式 29 第3章 程序控制语句 31 3.1 程序的三种基本结构 31 3.2 数据的输入与输出 31 3.2.1 scanf()函数 31 3.2.2 printf()函数 33 3.2.3 getchar()函数与putchar()函数 36 3.2.4 程序...
本教程共分为5个部分,第一部分是C语言提高部分,第二部分为C++基础部分,第三部分为C++进阶部分,第四部分为C、C++及数据结构基础部分,第五部分为C_C++与设计模式基础,内容非常详细. 第一部分 C语言提高部分目录...
1.1 MFC与C++ 1.2 VC++组件 1.3 安装 1.3.1 环境 1.3.2 安装过程 第2章 开发环境 2.1 主窗口 2.2 工具栏 2.2.1 Shaod工具栏 2.2.2 Build Mini-bar工具栏 2.3 菜单栏 2.3.1 File菜单 ...
2.5 在C语言中是否有模拟继承等面向对象程序设计特性的好方法? 2.6 为什么声明extern f(struct x *p); 给我报了一个晦涩难懂的警告信息? 2.7 我遇到这样声明结构的代码:struct name {int namelen; char namestr[1...