周立功阐释高效的双向链表如何用

4    }

>>>> 1.1.2 删除结点

基于添加结点到任意位置的思想，需要实现一个删除任意结点的函数。其函数原型为：

int dlist_del (dlist_head_t *p_head, dlist_node_t *p_node); 

其中，p_head为指向链表头结点的指针， p_node为指向待删除结点的指针，使用范例详见程序清单3.44。

程序清单3.44  dlist_del()使用范例程序

1    int main(int argc, char *argv[])

2    {

3         dlist_head_t head;

4         dlist_node_t node;

5         dlist_init(&head);

6         dlist_add_tail(&head, &node);

7         dlist_del(&head, &node);

8         //......

9         return 0;

10  } 

为了实现dlisd_del()函数，可以先查看删除任意结点的示意图，图 3.20（1）为删除节点前的示意图，图 3.20（2）为删除节点后的示意图。

图 3.20添加结点示意图

由此可见，仅需要修改两个指针的值：

● 将"删除结点"的前结点的p_next修改为指向"删除结点"的后结点；

● 将"删除结点"的后结点的p_prev修改为指向"删除结点"的前结点。

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

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

1    int dlist_del (dlist_head_t *p_head, dlist_node_t *p_node)

2    {

3         if ((p_head == NULL) || (p_node == NULL) || (p_node == p_head)){

4             return -1;

5         }

6         p_node->p_prev->p_next = p_node->p_next;               // 前结点的p_next修改为指向后结点

7         p_node->p_next->p_prev = p_node->p_prev;               // 后结点的p_prev修改为指向前结点

8

9         p_node->p_next = NULL;

10        p_node->p_prev = NULL;

11       return 0;

12  } 

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

>>>> 1.1.3 遍历链表

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

int dlist_foreach (dlist_head_t            *p_head,

              dlist_node_process_t      pfn_node_process,

              void                  *p_arg);

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

typedef int (*dlist_node_process_t) (void *p_arg, dlist_node_t *p_node);

dlist_node_process_t类型参数为一个p_arg指针和一个结点指针，返回值为int类型的函数指针。每遍历到一个结点均会调用pfn_node_process指向的函数，便于用户根据需要自行处理结点数据。当调用该回调函数时，传递给p_arg的值即为用户参数，其值与dlist_traverse()函数的第3个参数一样，即该参数的值完全是由用户决定的；传递给p_node 的值即为指向当前遍历到的结点的指针。当遍历到某个结点时，如果用户希望终止遍历，此时，只要