国庆前第二波：学C语言再谈链表学习，果断送分帖。
学C语言再谈链表学习：相信学习过C语言和数据结构的人，都会学习链表。N多的同学都会做链表练习。不过都是基于现成数据结构一书提示的代码，不过它们并不通用，表现在一个程序中你不能使用包含多数固定格式结构的链表。现在，让我们百尺竽头，更进一步学习C中的链表，让我们一起来看看C中的通用链表的一种做法：
一、用面象对象的思想重新设计我们的链表：
试想想链表中哪些成为我们的设计要素呢？观察一下链表，链表的元素个数是链表的一个组成部分，链表的节点指针也是链表的一个组成部分，链表中的节点数据中包含我们的真实数据，从这些现象，我们上升到一个层次来看刚才所说有这三点，元素个数、节点指针、节点数据成了我们关注的对象，抽象的提炼就是这么来的，所以根据这些抽象的结果，我们可以这样用C来定义节点，放入list.h中：
/**
* 链表结点定义
*/
typedef struct tag_node
{
void *data; //结点数据指针
struct tag_node *next; //结点指针
}node, *Node;
二、void指针在链表中的应用：
我们学习过C语言指针的同学都知道，在C指针中有一个特殊的东西，void*，这个东西可以保存任意类型数据的地址，所以它就是我们通用链表的核心部件，void指针在没有附值初始化前，是指向没有意义的数据的，另外我们也要注意的是，使用void*做为我们的结点数据指针所带来的一个问题，如何保证客户添加进链表中的元素是同一类元素？这个问题我先提在这里，大家思考一下。
三、数据隐藏与封装：
链表中的一些元素，我们不希望用户进行修改，怎么办？把它们隐藏进来！如元素个数，这是表示链表元素的属性，不能让用户随意修改，节点指针，我们也不希望用户直接访问，所以我们用一个如下的结构来进行数据隐藏，本例中我们把它放入一个叫list_impl.h的头文件中，并不提供给最终的用户，所以用户其实不知道我们的链表有些什么属性，我们只提供公用接口函数用于访问链表的各种功能。
－－－－－－－－－－－－－－－－－－－－－－－－
/**
* 链表私有数据，对用户隐藏
*/
typedef struct list_private
{
Node head; //头节点
Node tail; //尾节点
unsigned int size; //元素个数
unsigned int data_size; //元素数据大小
} lpri, *Lpri;
－－－－－－－－－－－－－－－－－－－－－－－－－－－－
为了让我们的链表知道结点指针所指向的数据，它的大小是多少，需要一个新的成员来描述，也就是上面的data_size。
四、将上面两个部分集合进来，型成我们的通用链表，放入list.h中：
请看下面的结构定义：
typedef struct tag_list
{
void *lprivate; //私有数据
}clist, *List;
看起来是不是怪怪的？呵呵，对于用户来说，只需要使用这个自定义类型List既可。它可以做什么？可以让你的程序使用多个带数据的结构体，所有的链表操作如创建、添加、删除、排序这些过程在代码中都是相用的，但你没有写重复代码就实现了，这就是程序设计的思考所带来的 效果。下面让我们看一看链表是如何创建和销毁的。
#include "list.h"
#include "list_impl.h"
/**
* 功能：链表创建
* 参数：data_size -- 元素数据大小，必须大于0
* destructor -- 元素析构函数指针，用于释放动态元素分配.
* 返回：已初始化链表指针
* 备注：链表本身动态分配，由list_destroy函数管理释放, 在元素
* 内数据为非动态分配情况下，destructor 可为空指针，
*/
List list_create(unsigned int data_size, list_destructor destructor)
{
List list = NULL;
assert(data_size > 0);
list = NEWC(1, clist);
if(list != NULL)
{
Lpri lp; //链表私有数据
Node head; //空的头节点
lp = NEWC(1, lpri);
head = NEWC(1, node);
if( head && lp ) //头节点和私有数据内存分配成功, 初始化私有数据
{
lp->head = head;
lp->tail = head;
lp->data_size = data_size;
lp->destruct_func = destructor;
list->lprivate = lp;
//set_error(LIST_OK);
return list;
}
}
//set_error(LIST_MEM_FAILE);
return list;
}
-----------------------------------------------------------------
/**
* 功能：释放链表占用的内存
* 参数：list -- 链表指针
* 返回：空链表指针。
*/
List list_destroy(List list)
{
assert(list);
if(list != NULL)
{
Node next;
Lpri lp = (Lpri) list->lprivate;
assert(lp);
while( lp->head )
{
next = lp->head->next;
if( lp->head->data ) //如果是头节点就不释放数据空间
{
if( lp->destruct_func )
{
lp->destruct_func( lp->head->data ); //调用元素析构函数
}
free(lp->head->data); //先释放节点数据
}
free(lp->head); //再释放节点
lp->head = next;
}
free(list->lprivate); //释放私有数据空间，及链表本身
free(list);
list = NULL;
set_error(LIST_OK);
return list;
}
set_error(LIST_IS_NULL);
return list;
}
五、回调函数与链表：
由于使用的是void指针，所以所指向的数据有可能是使用malloc动态分配的，为了避免链表释放时产生内存泄露问题，我们使用了回调函数来解决这个问题，看下面的定义：
/**
* 回调函数定义
* compare -- 数据比较函数指针
* foreach_func -- 遍历时处理节点数据函数指针
*
* 参数：ndata -- 节点数据指针
* param -- list_for_each函数附加参数指针
*/
typedef int (*compare)(const void *ndata, const void *data);
typedef void (*list_destructor)(void *ndata);
typedef void (*foreach_func)(void *ndata, void *param);
通过typedef void (*list_destructor)(void *ndata);这句指名一个函数指针，让用户自定义一个函数用于释放动态分配的数据，这个指针也可以指向空，表示用户的数据结构中不含有动态分配的数据，注意看list_destroy是如何处理这个问题的，相当于C++的析构函数。
六、插入元素与遍历示例代码：
/**
* 功能：添加链表结点 (后插法)
* 参数：list -- 链表指针，data -- 链表数据指针，任意数据类型
* 返回：int值，0表示成功，1表示失败
* 备注：不能添加不同类型的元素，否则链表操作会崩溃
*/
int list_add_back(List list, const void *data)
{
assert(list);
assert(data);
if( list && data )
{
Lpri lp = (Lpri) list->lprivate;
assert(lp);
if( lp )
{
Node new_node = NEWC(1, node);
if( new_node )
{
new_node->data = NEW(lp->data_size, char); //分配节点数据
if( new_node->data )
{
memcpy(new_node->data, data, lp->data_size); //拷贝数据
lp->tail->next = new_node; //添加节点
lp->tail = new_node; //记录尾节点位置
lp->size ++; //链表元素总数加1
set_error(LIST_OK);
return 0;
}
}
set_error(LIST_MEM_FAILE);
return 1;
}
}
set_error(LIST_IS_NULL);
return 1;
}
注意上面memcpy的这行，是如何拷贝结点数据到结点中的，如果你真的理解了这行，表示你明白"对象"在C中是如何表现的。
---------------------------------------------------------------------------------------
/**
* 函数：list_for_each
* 功能：遍历链表元素
* 参数：list -- 链表指针，pfunc为指向遍历处理数据的函数指针,
* param -- 附加参数指针。可以为空指针
* 返回：int值，0表示成功，1表示失败
* 备注：doit申明为void (*foreach_func)(void *ndata, void *param)原型
* param参数传到处理函数中。
*/
int list_for_each(List list, foreach_func pfunc, void *param)
{
assert(list);
if( list )
{
Lpri lp = (Lpri) list->lprivate;
assert(lp);
if( lp )
{
Node i;
for(i = lp->head->next; i; i = i->next)
{
pfunc(i->data, param);
}
set_error(LIST_OK);
return 0;
}
}
set_error(LIST_IS_NULL);
return 1;
}
详细代码请见附件。
总结：通过本通用链表一些知识学习，我们可以学习到C语言接口与实现的分开，面象对象的抽象思维方式，丰富我们的程序视野，学习代码背后的思想，是每个程序员应该去思考的事情，不能光看代码的表面。最后说一下第二点的思考，使用void指针创建的通用链表可能存在的问题 ，如果用户添加进链表中的元素不是同一类的结构体，那么程序将可能出错，例如一个4字节的结构体的链表，添加了一个32位指针元素进来， 我们可以在链表中添加一个属性int type_id，在创建和添加链表中进行验证，强制用户提供元素必须是同一类型的元素，这样就解决了void指 针所带有的这个问题。OK，感谢你观看本文，如果你能从文章中学到一些什么你感兴趣的东西，本人将不慎荣幸。
Genral_list.rar
(8.2 KB)
