C语言深处

        在本节中，我们将学习并实现一个通用的单向链表。先来看一下单向链表在内存中的存储形式：

        链表中有3个属性，id为数据节点的唯一标识，在构建时按这个id来排序，也就是说我们要构建一个按id升序组成的单向链表。来看一下链表节点的数据结构：

//链表节点数据结构
typedef struct linknode
{
        //唯一标识，按大小升序
        int id;
        //数据通用指针
        void *node;
        //下一节点指针
        struct linknode *next;
} linknode;

        另外还要定义链表数据结构，链表头节点和其它个重要的内容都在这个结构中：

//链表数据结构
typedef struct linklist
{
        //链表头节点
        linknode *header;
        //取得数据唯一标识函数指针，回调函数
        int (*get_id)(void *);
        //显示数据的函数指针，回调函数
        void (*display)(void *);
        //销毁数据函数指针，回调函数
        void (*destructor)(void *);
} linklist;

        接下来，我们来实现构建和销毁链表的两个函数：

//构建链表函数
linklist* linklist_init(int (*get_id)(void *), void (*display)(void *), void (*destructor)(void *))
{
        //申请链表内存
        linklist *l = malloc(sizeof(linklist));
        //头节点
        l->header = NULL;
        //取得数据唯一标识函数指针，回调函数
        l->get_id = get_id;
        //显示数据的函数指针，回调函数
        l->display = display;
        //销毁数据函数指针，回调函数
        l->destructor = destructor;
        return l;
}

//销毁链表函数
void linklist_des(linklist *l)
{
        //取得头节点
        linknode *p = l->header;
        //循环销毁所有节点数据
        while (p != NULL)
        {
                //取得下一个节点
                linknode *pNext = p->next;
                //销毁节点数据
                l->destructor(p->node);
                //释放节点内存
                free(p);
                //下一个节点
                p = pNext;
        }
        //释放链表内存
        free(l);
}

        然后再来看一下链表的“插入”操作。为链表插入一个新的节点有以下几个步骤：

1. 从链表头节点开始向下遍历，并比较id的值。
2. 找到id所应该在的位置，找到前一个节点p和后一个节点pNext。
3. 断开p到pNext的next指针。
4. 让p的next指针指向新的节点newNode。
5. 让新节点newNode的next指针指向pNext。

        插入节点的函数如下：

//插入新节点
void linklist_insert(linklist *l, void *node)
{
	//取得id
	int id = l->get_id(node);
	//申请内存
	linknode *newNode = malloc(sizeof(linknode));
	newNode->id = id;
	newNode->node = node;
	newNode->next = NULL;

	//二级指针
	linknode **p = &l->header;
	//找到第一个大于key的节点
	while ((*p) != NULL && (*p)->id < id)
	{
		p = &(*p)->next;
	}
	//插入新节点
	newNode->next = *p;
	*p = newNode;
}

        删除节点操作与插入相反，执行下面步骤：

1. 从链表头节点开始向下遍历，并比较id的值。
2. 找到准备删除的节点delNode，其前一个节点p和下一个节点pNext。
3. 断开p指向delNode的next指针，断开delNode指向pNext的next指针。
4. 将p的next指针指向pNext。
5. 释放delNode节点。

        再来看一下实现函数：

//删除节点
void linklist_del(linklist *l, int id)
{
	//如果头节点为空
	if (l->header == NULL)
	{
		return;
	}

	//二级指针
	linknode **p = &l->header;
	while ((*p) != NULL && (*p)->id != id)
	{
		p = &(*p)->next;
	}

	//等待释放节点
	linknode *del = *p;
	if (del == NULL)
	{
		return;
	}

	//释放内存
	free(del);
	*p = (*p)->next;
}

        还有两个比较简单的“查找”函数和“显示”函数：

//查找
void* linklist_find(linklist *l, int id)
{
        //取得头节点
        linknode *p = l->header;
        //遍历链表
        while (p != NULL)
        {
                //如果id相等
                if (p->id == id)
                {
                        //返回数据节点
                        return p->node;
                }
                //下一个节点
                p = p->next;
        }
        return NULL;
}

//显示链表内容
void linklist_display(linklist *l)
{
        //取得头节点
        linknode *p = l->header;
        //遍历链表
        while (p != NULL)
        {
                //显示数据内容
                l->display(p->node);
                //下一个节点
                p = p->next;
        }
}

        最后通过一个例子来测试一下：

//学生数据结构
typedef struct
{
        //学号
        int no;
        //姓名
        char *name;
        //性别
        char sex;
        //年龄
        int age;
} student;

//取得学生学号，唯一id
int get_id_student(void *p)
{
        student *h = (student *) p;
        return h->no;
}

//显示学生信息
void display_student(void *p)
{
        student *h = (student *) p;
        printf("%d\t%s\t%c\t%d\n", h->no, h->name, h->sex, h->age);
}

//这是专门用于释放student类型元素的回调函数
void destructor_student(void *p)
{
        student *h = (student *) p;
        //释放名字属性
        free(h->name);
        //释放student
        free(h);
}

      主函数实现如下：

#define NAME_LEN         (20)

int main(int argc, char **args)
{
        linklist *link = linklist_init(&get_id_student, &display_student, &destructor_student);

        student *h1 = malloc(sizeof(student));
        h1->no = 20150501;
        h1->name = malloc(NAME_LEN);
        memcpy(h1->name, "Tomsen", NAME_LEN);
        h1->sex = 'F';
        h1->age = 22;
        linklist_insert(link, h1);

        student *h2 = malloc(sizeof(student));
        h2->no = 20150502;
        h2->name = malloc(NAME_LEN);
        memcpy(h2->name, "Jerry", NAME_LEN);
        h2->sex = 'M';
        h2->age = 21;
        linklist_insert(link, h2);

        student *h3 = malloc(sizeof(student));
        h3->no = 20150504;
        h3->name = malloc(NAME_LEN);
        memcpy(h3->name, "Lily", NAME_LEN);
        h3->sex = 'F';
        h3->age = 23;
        linklist_insert(link, h3);

        student *h4 = malloc(sizeof(student));
        h4->no = 20150503;
        h4->name = malloc(NAME_LEN);
        memcpy(h4->name, "Wellean", NAME_LEN);
        h4->sex = 'M';
        h4->age = 22;
        linklist_insert(link, h4);

        printf("\nDisplayer all: \n");
        linklist_display(link);

        printf("\nFind 20150502:\n");
        student *h = linklist_find(link, 20150502);
        display_student(h);

        printf("\nDelete 20150512:\n");
        linklist_del(link, 20150502);

        printf("\nDisplay all:\n");
        linklist_display(link);

        linklist_des(link);

        return 0;
}

        运行结果：

Displayer all: 
20150501        Tomsen        F        22
20150502        Jerry         M        21
20150503        Wellean       M        22
20150504        Lily          F        23

Find 20150502:
20150502        Jerry         M        21

Delete 20150512:

Display all:
20150501        Tomsen        F        22
20150503        Wellean       M        22
20150504        Lily          F        23