算法与数据结构——双向链表

删除结点函数的实现详见程序清单3.45。

程序清单3.45  dlist_del()函数实现

为了防止删除头结点，程序中对p_head与p_node进行了比较，当p_node为头结点时，则直接返回错误。

3.3.3  遍历链表

与单向链表类似，需要一个遍历链表各个结点的函数，其函数原型（dlist.h）为：

其中，p_head指向链表头结点，pfn_node_process为结点处理回调函数，每遍历到一个结点时，均会调用该函数，便于用户处理结点。dlist_node_process_t类型定义如下：

dlist_node_process_t类型参数为一个p_arg指针和一个结点指针，返回值为int类型的函数指针。每遍历到一个结点均会调用pfn_node_process指向的函数，便于用户根据需要自行处理结点数据。当调用该回调函数时，传递给p_arg的值即为用户参数，其值与dlist_traverse()函数的第3个参数一样，即该参数的值完全是由用户决定的；传递给p_node 的值即为指向当前遍历到的结点的指针。当遍历到某个结点时，如果用户希望终止遍历，此时，只要在回调函数中返回负值即可终止继续遍历。一般地，若要继续遍历，则函数执行结束后返回0即可。dlist_foreach()函数的实现详见程序清单3.46。

程序清单3.46  链表遍历函数的实现

为了便于查阅，如程序清单3.47所示展示了dlist.h文件的内容。

程序清单3.47  dlist.h文件内容

同样以int类型数据为例，来展示这些接口的使用方法。为了使用链表，首先应该定义一个结构体，将链表结点作为其一个成员，此外，再添加一些应用相关的数据，如定义如下包含链表结点和int型数据的结构体：

综合范例程序详见程序清单3.48。

程序清单3.48  综合范例程序

与单向链表的综合范例程序比较可以发现，程序主体是完全一样的，仅仅是各个结点的类型发生了改变。对于实际的应用，如果由使用单向链表升级为双向链表，虽然程序主体没有发生改变，但由于类型的变化，则不得不修改所有程序代码。这是由于应用与具体数据结构没有分离造成的，因此可以进一步将实际应用与具体的数据结构分离，将链表等数据结构抽象为"容器"的概念。