由通用双向链表的实现浅谈库函数、头文件及通用的思想

    前一阵子OS组有这样一个任务，用c语言实现一个通用双向链表，要求：1、链表的数据可以是任意类型。2、包括基本的创建，销毁，添加，删除，遍历，对元素处理等基本操作。由于刚刚做完c语言课设（某信息管理系统，由三级链表实现），所以自然而然的以为这是要求做一个信息管理系统出来。于是先绕过链表数据为任意类型这个问题，做了一个数据类型为字符串的双向链表，刚刚做完课设不久，经验积累了不少，没多久就做完了。组长看到后说，双向链表倒是实现了，但是离通用二字实在是相去甚远。若要实现通用，就必须满足下面两个条件：1、将链表操作的函数独立出一个文件，并做一个头文件，在需要时进行include，相当于写库函数。2、实现链表数据可以为任意类型。

一、写库函数

1、函数库的内容

    为什么要写库函数，因为我们经常在不同程序中使用一些相同或相似的代码段，若将这些代码段单独放在一个函数库文件中，在需要时将其与主函数文件共同编译，就免去了重复写这段代码的麻烦，“极大地解放了生产力”。

    所以，函数库其实就是将一些常用函数放在一个文件中，这个文件没有主函数，也就是说函数库并不是为了实现某个目标而写的源代码文件，而仅仅是一些常用函数的集合。若在某个程序中需要用到这些函数，则将这个函数库与其共同编译即可。

2、头文件的内容

    由此可见，使用库函数实际上就是实现一个多文件的c程序。首先我们需要复习一下函数作用域的相关概念。函数存储类型分静态和外部，缺省为外部函数，即函数可被其他文件中的函数调用，在调用前需另加声明。静态函数需使用关键词static，其作用域为函数定义到文件结尾，可通过函数声明在文件内部范围内扩大作用域，其他文件无法使用该函数（即使声明了也不可以）。

    我们注意到上一段中有这样一句话，外部函数被其他文件调用时，需在文件中另加声明。也就是说，仅仅写好了函数库还不能直接使用，还要在调用它的文件中加上函数的声明。这个函数声明也就是传说中的“接口”，顾名思义，是两个文件相互交流的“通道”，其实说它是一个标准更为恰当。函数库中写好了函数的具体内容，调用的文件中需要知道这些函数的原型，包括函数名，参数类型，返回值类型。这样，在调用这些函数时，用户才能使用正确的函数名来找到函数的地址，传给函数正确的参数，并明确函数返回值的类型。

    这样的话，问题又出现了。如果函数库中有很多函数，那么每次要调用这些函数时，岂不是要都要将这些函数原型抄一遍，工作量依然不小。于是头文件出现了，头文件便是专门用来存储这些函数原型的文件，只要在调用函数前include一下，就可以免去重复书写函数原型的麻烦。与多文件c程序不同的是，include是在预编译阶段进行的机械的替换，其实与你自己写函数原型没有区别，虽然是放在不同的文件中，但经过编译预处理，实际上就成为一个文件了。

小结：函数库是一些常用函数的集合。头文件是其对应函数库中函数原型的集合。调用库函数前将头文件包含于其中是为了将库函数的作用域扩大至当前文件，编译时将函数库与当前文件共同编译。

    当然函数库与头文件实际上包含的内容不只有这些，但原理无非是函数库提供具体的函数定义，头文件存储一些通信的标准作为接口。

二、实现链表数据可为任意类型

    对链表的操作可分为创建、销毁、添加、删除、遍历、修改等。其中，添加、遍历、修改涉及到了链表的数据类型。添加节点需要同时将数据写入节点，修改同添加。遍历链表需要对节点中的数据进行某些操作。

1、添加或修改节点。

    在创建节点时，数据部分的大小就已经确定了，所以要想实现任意数据类型，就只有通过保存数据指针而不是数据本身一途。节点结构体定义如下：

struct DlistNode {

       void *data;

       struct DlistNode *prev, *next;

};

即数据由一个空指针表示。在添加或修改节点数据时，需要给函数传递数据指针作为参数，然后函数在节点中存储该指针代替数据。这样做的优点是消除了数据类型的限制，但还有不足是用户必须自己为每个变量分配独立的存储空间。

2、遍历链表并对节点中的数据进行操作

    遍历链表时需要对节点中的数据进行操作，而数据的类型及具体操作的步骤都不是遍历函数所能知道的，这里可以使用回调函数来实现这样的功能。即由用户定义对节点数据操作的函数，如一个打印节点数据的函数：

void int_print(void *data)

{

       printf(“%d\n”,*(int *)data); //用户是清楚自己数据的类型的，所以可以写出对应的函数

}

即函数至少要有一个参数，用来传递节点中数据的指针，这样函数才能对节点中的数据进行操作。

    然后将这个函数名（实际为函数指针）作为一个参数传递给遍历函数，设遍历函数中对应的形参名为func，则只要在遍历函数中加如下一句：

func(node->data); //node为当前节点的指针

就可以对节点中的数据进行遍历操作了。

    当然，这个函数的返回值和参数的类型需要作为接口的一部分写在头文件中，如：

typedef void (*Func)(void *);

因为在头文件中遍历函数的函数原型需要用Func这个函数指针类型来定义形参。

小结：若要实现通用，则必须消除数据类型的限制，方法是存储数据的指针而不是数据本身，并让具体对数据的操作由用户自己定义。库函数只提供数据结构而不涉及数据内容，用户则只提供数据内容而不需了解数据结构的细节。