五、为什么需要赋值函数指针assign
这里来说明一下,该链表的数据的插入方式,我们的插入方式是,新建一个结点,把data指向的数据复制到结点中,并把该结点插入到链表中。插入的函数定义如下:
Iterator Insert(List list, void *data, Iterator it_before,
void (*assign)(void*, const void*));
从上面的解说中,我们可以看到链表中的成员data_size指示了链表中的数据所占的内存大小,那我们们就可以使用函数memcpy把data指向的数据复制到新建的结点的data所指向的内存即可。为什么还需要一个函数指针assign,来指向一个定义数据之间如何赋值的函数呢 其实这和面向对象语言中常说到的深复制和浅复制有关。
注:memcpy函数的原型为: void * memcpy ( void * destination, const void * source, size_t num );
试想一下,假如你的链表的数据类型不是int型等基本类型,也不是不含有指针的结构体,而是一个这样的结构体,例如:
struct student
{
char *name;
char *no;
int age;
};
学生的姓名和学号都是能过动态分配内存而来的,并由student结构体中的name和no指针指向,那么当我们使用memcpy时,只能复制其指针,而不能复制其指向的数据,这样在很多情况下都会带来一定的问题。这个跟在C++中什么时候需要自己定义复制构造函数的情况类似。因为这种情况下,默认的复制构造函数并不能满足我们的需要,只能自己定义复制构造函数。
所以在插入一个结点时,需要assign函数指针的原理与C++中自己定义复制构造函数的原理一样。它用于定义如何根据一个已有的对象生成一个该对象的拷贝对象。当然,可能在大多数的情况下,我们需要用到的数据类型都没有包含指针,所以在Insert函数的实现中,其实我也是有用到memcpy函数的,就是当assign为NULL时,就使用memcpy函数进行数据对象间的赋值,它其实就相当于C++中的默认复制构造函数。assign为NULL表示使用默认的逐位复制方式。
六、为什么不用typedef
对于这个问题,其实很好回答。很多人实现一个通用链表是这样实现的,它们把node结构的实现如下:
typedef struct node
{
//循环双链表的结点结构
DataType data;//数据域指针
struct node *next;//指向当前结点的下一结点
struct node *last;//指向当前结点的上一结点
}Node;
然后,当需要使用整型的链表时,就把DataType用typedef为int。其实这样做的一个最大的缺陷就是一个程序中只能存在着一个数据类型的链表,例如,如果我需要一个int型的链表和一个float型的链表,那么该把DataType定义为int呢还是float呢 所以这种看似可行的方式,其实只是虚有其表,在现象中是行不能的,虽然不少的数据结构的书都是这样实现的,但是它却没有什么实用价值。
而其本质的原因是把结点的数据域的数据类型与某一种特定的数据类型DataType绑定在一起,从而让链表不能独立地变化。
七、为什么只把结点的指针定义为Iterator
在C++中iterator是一个类,为什么在这里,我只把结点的指针声明为一个Iterator呢 其实受STL的影响,我在一开始时,也是把Iterator实现为一个结构体,它只有一个数据成员,就是一个指向Node的指针。但在后来的实践中,发现其实并没有必要。在C++中为什么把iterator定义为一个类,是为了重载*,->等运行符,让iterator使用起来跟普通的指针一样。但是在C语言中,并没有重载运行符的做法,所以直接把Ierator声明为一个Node的指针最为方便、直接和好用,所有的比较运算都可以直接进行,而无需要借助函数。而把它声明为一个结构体反而麻烦、累赘。
八、为什么查找需要两个Iterator
其实这是参考了STL中的泛型算法的思想。而且本人觉得这是一种比较好的实现。为什么FindFirst的函数原型不是
Iterator FindFirst(List list, int (*condition)(const void*, const void*));
而是
Iterator FindFirst(Iterator begin, Iterator end, void *data,
int (*condition)(const void*, const void*));
我们可以试想一下,这个链表的为char链表,链表的元素为ABCBCBC,我们要在链表中找出所有的B,如果查找算法是使用第一种定义的话,它只能找出第一个B,而后面的两个B就无能为力了,而第二种定义,则可以通过循环改变其始末迭代器来在不同的序列段间查找目标字符B的位置。