Latest Posts

##链表(2)##

我们在链表1中探讨了链表的一些最基本最简单的一些用法，只能用来讲讲链表操作的基本原理，不具有通用性。

事实上，我们在实际的项目中用的是在nginx内核中的一种通用的循环链表，其完全是由C语言的宏来定义的，设计非常的简洁巧妙，用在生产环境非常的健壮稳固。

在讲通用链表之前先讲一个宏:offsetof()

size_t offsetof(structName, memberName);

其表示为某结构体成员相对于其所在结构体的中偏移量。通用链表的实现就依赖于这个宏实现的。

下面来介绍nginx通用双向链表的结构体定义

typedef struct ngx_queue_s  ngx_queue_t;

struct ngx_queue_s {

    ngx_queue_t  *prev;

    ngx_queue_t  *next;

};

其定义非常的简单，仅仅是两个指向前节点和后节点的指针。ngx_queue_t 作为结构体的子成员，如：

struct userinfo{

	char * firstname;

    char * lastname;

    int age;

    int sex;

	ngx_queue_t queue;

}

所有关于链表的操作，都是对ngx_queue_t的操作，当我们要取得userinfo结构体地址时，就可以用上面的offsetof宏,根据queue的地址来取得了，理论上来说,一个ngx_queue_t的链表可以串起包含有ngx_queue_t的任意结构体类型，但是建议还是像C++或者java,csharp的泛型一样，一个链表中只包含一种结构体类型。

实际项目中，我们对其进行重新命名，并进行了封装，详见源码目录下的core/na_queue.h

其具体代码如下:

/*

 * Copyright(C) Neo

 * Thu Mar 28 11:30:44 2013

 * 对列定义（双向队列,环形队列） 参考nigix队列定义，以及Linux内核队列定义

 */

#ifndef _NA_QUEUE_H_

#define _NA_QUEUE_H_

#include "na_core.h"

typedef struct na_queue_s na_queue_t;

struct na_queue_s {

  na_queue_t * prev;

  na_queue_t * next;

};

/* 初始化队列 */

#define na_queue_init(q)                      \

  (q)->prev = (q);        \

  (q)->next = (q)

/* 判断队列是否为空 */

#define na_queue_empty(h) \

  ((h) == (h)->prev)

/* 从头插入节点 */

#define na_queue_insert_head(h,x)     \

  (x)->next = (h)->next;              \

  (x)->next->prev = (x);              \

  (x)->prev = (h);                    \

  (h)->next = (x)

#define na_queue_insert_after na_queue_insert_head

/* 从末尾插入节点 */

#define na_queue_insert_tail(h,x)      \

  (x)->prev = (h)->prev;               \

  (x)->prev->next = x;                 \

  (x)->next = h;                       \

  (h)->prev = x 

/* 头指针对应的头节点 */

#define na_queue_head(h) (h)->next

/* 最后一个节点 */

#define na_queue_last(h) (h)->prev

#define na_queue_sentinel(h) (h)

/*下一个节点*/

#define na_queue_next(q) (q)->next

/* 前一个节点 */

#define na_queue_prev(q) (q)->prev

/* 移除一个节点 */

#define na_queue_remove(x)             \

  (x)->next->prev = (x)->prev;         \

  (x)->prev->next = (x)->next;         \

  (x)->prev = NULL;                    \

  (x)->next = NULL

/* 切分一个队列

 * h 头指针

 * q 需要拆分的头指针

 * n 拆分完成后另外一个队列的头指针

 */

#define na_queue_split(h,q,n)           \

    (n)->prev = (h)->prev;              \

    (n)->prev->next = n;                \

    (n)->next = q;                      \

    (h)->prev = (q)->prev;              \

    (h)->prev->next = h;                \

    (q)->prev = n;

/* 合并两个队列 */

#define na_queue_add(h,n)               \

  (h)->prev->next = (n)->next;          \

  (n)->next->prev = (h)->prev;          \

  (h)->prev = (n)->prev;                \

  (h)->prev->next = (h);

/* 根据队列指针，得到包涵此队列指针的结构体

 * q 队列指针

 * type 返回的数据类型

 * link 数据项中对应的队列项名字

 */

#define na_queue_data(q, type, link)   \

    (type *) ((u_char *) q - offsetof(type, link))

/* 查找中间节点 */

na_queue_t *

na_queue_middle(na_queue_t * queue);

/* 对队列排序 */

void na_queue_sort(na_queue_t *queue,int (*cmp)(const na_queue_t *, const na_queue_t *));

/*遍历队列中节点的数据

 *q:传入的包含队列类型的结构体指针

 *s:队列的哨兵指针

 *type:包含队列的结构体类型

 *link:队列在结构体中的名字

*/

#define na_queue_foreach(q,s,type,link)          \

  na_queue_t * _head_ =NULL;                         \

  for(_head_=na_queue_head(s),q=na_queue_data(_head_,type,link);_head_!=s;_head_=na_queue_next(_head_),q=na_queue_data(_head_,type,link))

// add by hc

#define NA_QUEUE_INIT(name) {&(name),&(name)}

#define na_queue_is_last(head,node) ((node)->next == (head))

#define na_queue_for_each(pos,head) \

	for(pos = (head)->next;pos != head;pos = pos->next)

#define na_queue_for_each_safe(pos,n,head) \

	for(pos = (head)->next,n = pos->next;pos != (head);pos = n,n = pos->next)

#endif /* _NA_QUEUE_H_ */

其链表的操作

函数名

参数说明

函数执行意义

|——–|——–|———|

na_queue_init

哨兵节点

初始化链表的哨兵节点

na_queue_empty

同上

判断链表是否为空

na_queue_insert_head

在表头插入节点

na_queue_insert_after

在表尾插入节点

na_queue_head

取得链表表头

na_queue_last

取得表尾

na_queue_sentinel

取得哨兵节点

na_queue_next

取得下一个节点

na_queue_prev

取得前一个节点

na_queue_remove

移除一个节点

na_queue_split

拆分一个链表

na_queue_add

合并一个链表

na_queue_data

q 队列指针 type 返回的数据类型 link 数据项中对应的队列项名字

根据队列指针，得到包涵此队列指针的结构体

na_queue_middle

查找中间节点

na_queue_sort

对队列排序

na_queue_foreach

q:传入的包含队列类型的结构体指针 s:队列的哨兵指针 type:包含队列的结构体类型 link:队列在结构体中的名字

遍历队列中节点的数据

na_queue_for_each_safe

安全遍历队列中节点的数据

其他参数说明见源码说明,

这里重点讲两个宏 na_queue_date 和 ** na_queue_foreach **

** na_queue_date ** 是最上面offsetof宏的应用，功能是取得包含链表指针的结构体的地址。

** na_queue_foreach** 是遍历队列中的所有的节点

下面通过一个简单的插入排序来展示链表的用法:

#include <stdio.h>

#include <stdlib.h>

#include "na_queue.h"

#include <time.h>

typedef struct  number_s number_t;

typedef unsigned char u_char;

struct number_s{

        int value;

        na_queue_t queue;

};

//根据一个int值新建一个节点

number_t *

new_number_t(int v){

        number_t * n = calloc(sizeof(number_t),1);

        n->value = v;

        return n;

}

//释放一个number_t的链表中所有节点

void free_number_t(na_queue_t * h){

        na_queue_t * p = h->next;

        while(p!=h){

                na_queue_remove(p);

                number_t* q =na_queue_data(p,number_t,queue);

                free(q);

                p = h->next;

        }

}

//打印一个链表的所有节点值

void

print_queue(na_queue_t * h){

        na_queue_t * p = h->next;

        while(p!=h){

                number_t * q = na_queue_data(p,number_t,queue);

                printf("%d ",q->value);

                p=p->next;

        }

        printf("\n");

}

//在链表中插入一个值，使其按照从小到大顺序排列

void

insert_node(na_queue_t * h,int v){

        number_t * n= new_number_t(v);

        if(na_queue_empty(h)){

               na_queue_insert_tail(h,&n->queue);

               return;

        }

        na_queue_t * p = h->next;

        while(p!=h){

               number_t * num = na_queue_data(p,number_t,queue);

               if(num->value > v){

                       na_queue_t* q = na_queue_prev(p);

                       na_queue_t* c = &n->queue;

                       na_queue_next(q) = c;

                       na_queue_next(c) = p;

                       na_queue_prev(c) = q;

                       na_queue_prev(p) = c;

                       return;

               }

               p = na_queue_next(p);

        }

        na_queue_insert_tail(h,&n->queue);

}

//得到一个随机数

int get_random(){

        srand(time(0));

        return rand()/100000000;

}

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

{

        na_queue_t h;

        na_queue_init(&h);

        int i;

        for (i = 0; i < 10; i++) {

                int r = get_random();

                printf("add number:%d\n",r);

                insert_node(&h,r);

                print_queue(&h);

                sleep(1);

        }

        free_number_t(&h);

        return 0;

}

测试时一段插入排序程序,输出如下:

add number:10

add number:18

10 18

add number:4

4 10 18

add number:1

1 4 10 18

add number:20

1 4 10 18 20

add number:17

1 4 10 17 18 20

add number:3

1 3 4 10 17 18 20

add number:0

0 1 3 4 10 17 18 20

add number:18

0 1 3 4 10 17 18 18 20

add number:5

0 1 3 4 5 10 17 18 18 20

事实上最开始见到这个链表结构是从Linux内核代码中，位于<linux/list.h>

其更是广泛应用于Linux内核中，在Linux驱动程序设计的也会用到，有机会写关于Linux驱动设计的文章时，我们再举例了。

参考文献:

《Linux内核设计与实现》(Linux Kernel Development Third Edition) Robert Love
《深入理解Nginx》模块化开发与架构解析
《算法导论》

##链表（1）##

链表是一组数据项的集合，其中每个数据项都是一个节点的一部分，每个节点都包含指向下一个节点的链接。在链表中各个对象按线性顺序排序。与数组不同的是，数组的线性顺序是由数组的下标决定的，而链表中的顺序是由各个对象中的指针决定的。链表可以用来简单而灵活的表示动态集合。链表是最基本的数据结构之一，也是我们经常会用到的数据结构。链表又分为单向链表，双向链表，循环链表。

单向链表 顾名思义，其链接方向是单向的，对链表的访问要通过顺序的读取从头部开始。下面是一个简单的单向链表结构体定义

typedef struct struct_node{
 	int value;						//数据
    struct struct_node * next;		//指向下一个节点的指针
    }node_t;

双向链表 相对于单向链表，其多了一个指向前一个节点的指针，使其可以向前和向后访问节点，所以双向链表可以从任意一个节点开始读取链表的数据。下面是一个简单的双向链表结构

typedef struct struct_node{
 	int value;						//数据
    struct struct_node * prev;		//指向前一个节点的指针
    struct struct_node * next;		//指向下一个节点的指针
    }node_t;

循环链表 与双向链表相比，循环链表是双向链表的头尾相连，即双向链表的最后一个节点的next指针指向头节点，头节点的prev指针指向最后一个节点。由于是一个循环链表，这个时候表头和表尾的边界条件就很重要了， 哨兵节点的引入可以简化边界条件，哨兵节点是一个哑对象，其在表头和表尾之间，即哨兵节点的next指向头节点，哨兵节点的prev指向尾节点。这样一个空的循环链表就仅包含哨兵节点，其next和prev指针都指向自己本身. 循环链表的定义同双向链表一样，同上不在赘述。

#####链表的基本操作#####

链表的基本操作包括插入操作，删除操作，搜索操作等。这里以循环链表为例来讲链表的基本操作。

#include <stdio.h>

typedef struct struct_node_s{
        int value;
        struct struct_node_s * prev;
        struct struct_node_s * next;
}node_t;

//初始化哨兵节点
void
node_init(node_t * h){
        h->prev = h;
        h->next = h;
}

//创建一个节点
node_t *
node_new(int v){
        node_t * p = calloc(sizeof(node_t),1);
        p->value = v;
        p->next = p;
        p->prev = p;
        return p;
}

//在添加一个节点到链表头
void
node_insert_head(node_t * h,node_t * p){
        node_t * q = h->next;
        h->next = p;
        p->prev = h;
        p->next = q;
        q->prev = p;
}

//添加一个节点到表尾
void
node_insert_tail(node_t * h,node_t * p){
        node_t * q = h->prev;
        h->prev = p;
        p->next = h;
        q->next = p;
        p->prev = q;
}

//删除一个节点
void
node_remove(node_t * p){
        node_t * h = p->prev;
        node_t * q = p->next;
        h->next = q;
        q->prev = h;
}

//释放链表中所有节点（哨兵节点除外）
void
node_free(node_t * h){
        node_t * p = h->next;
        while(p != h){
                node_remove(p);
                free(p);
                p = h->next;
        }
}

//从表头开始打印链表
void
node_print(node_t * h){
        printf("list:");
        node_t * p = h->next;
        while(p != h){
                printf("%d ",p->value);
                p=p->next;
        }
        printf("\n");
}

int main(int argc, char *argv[])
{
        printf("node_init:\n");
        node_t h;
        node_init(&h);
        node_print(&h);
        printf("node_insert_tail:\n");
        for (int i = 0; i < 10; i++) {
                node_t * p = node_new(i);
                node_insert_tail(&h,p);
        }
        node_print(&h);
        printf("node_insert_head value 10 :\n");
        node_t * p = node_new(10);
        node_insert_head(&h,p);
        node_print(&h);
        printf("node_remove value 10 :\n");
        node_remove(p);
        node_print(&h);
        node_free(&h);
        printf("node_free:\n");
        node_print(&h);
        printf("----------------end---------------\n");
        return 0;
}

输出结果:

node_init:
list:
node_insert_tail:
list:0 1 2 3 4 5 6 7 8 9 
node_insert_head value 10 :
list:10 0 1 2 3 4 5 6 7 8 9 
node_remove value 10 :
list:0 1 2 3 4 5 6 7 8 9 
node_free:
list:

—————-end—————

上面的例子只是链表的一个基本用法，这里着重将循环链表拿出来举例，是因为它是我们在实际编程中用的最多的一种数据结构。但是通常在进行Linux环境下进行C程序设计的时候，我们常用的链表是在Linux内核中的链表，详见链表(2)

参考文献:

«算法导论»第10章，基本数据结构

程序运行环境：Ubuntu 12.04 LTS