c语言是如何实现泛型链表

  最近有看一点Linux内核源码,发现内核里大量使用了list_head结构体。百度查了一下,原来内核利用这个结构体实现了泛型。

  自认为对链表已经很熟悉的我,决定自己实现一下。

  下面以Node和list_head为例。

c语言是如何实现泛型链表

  上图就是循环链大致思路了。(画的不好)

  我们通过list_head对链表进行移动操作。

  这里存在几个问题:

    首先通过list_head得到的指针,它指向的list_head的结构体,但我们其实想要使用的是Node结构体。

    再有,我们要设计一个泛型的链表,那么,我就不可以在实现链表时有任何对Node的操作。

  解决办法:

    1、通过计算,找到node结构体的首地址。(我们通过一个宏来实现)

 #define list_entry(ptr, type, member) \
((type *)((char *)(ptr) - (char *)(&(((type *))->member))))

    这个宏看起来可能点乱,但我们把思路缕清就不乱了。

c语言是如何实现泛型链表

我们只知道entry的指针,如何求出Node的指针呢?

如果我们可以知道entry的相对位置,那么

  Node的实际位置  = entry的实际位置 - entry的相对位置。

  entry的相对位置 =  (&(((Node *)0)->entry))   又蒙了么?  这里,我们先将 0转换为(Node *)类型的指针,再用这个指针指向entry,最后取它的地址。这时我们就得到了entry的相对位置。

  宏中把他们强转成char * 是为了进行减法。最后再强转成Node类型,这时我就得到了Node的指针。

2、让用户自己定义特定数据的操作,我们只提供一个函数接口(我们通过函数指针来实现)

  在我们的链表里,只涉及到了list_head 里的内容,所以,不能对Node进行操作。参数也都是list_head的指针。这就需要用户在使用时,通过上面的宏来完成从list_head 到 Node的转换。在稍后例子中会了解到。

源码

dclist_head.h

 /*************************************************************************
> File Name: dlist_head.h
> Author: gaozy
> Mail: 44523253@qq.com
> Created Time: 2016年12月24日 星期六 10时11分22秒
************************************************************************/ /*
*这是我自己实现的一个泛型循环链表
*使用者只需要把dclist_head_t 这个结构体加入到自己的结构体中就可以使用这个链表了。
*在使用时,需要使用者创建一个头节点,之后使用init函数初始化。(当然,你也可以自己对他进行初始化操作)
*它很重要,否则无法使用这个链表。
*链表给使用者提供了四个函数
*init 刚刚已经说过了,我们用它初始化链表
*append 这是一个向链表中添加节点的函数,需要我们传入链表的头和新节点的dclist_head_t部分的指针
*treaverse 正如火函数名一样,它的作用是遍历链表,它需要我们提供一个函数指针
*这个指针的作用是对节点进行操作,参数是一个dclist_head_t 类型的指针,我们同过list_entry这个宏获取
*使用者自定义的数据类型。
*dc_remove这个函数用来释放链表,类似treaverse函数,需要我们自己实现删除j节点函数。
*它会释放链表中的所有节点,只有头结点例外,头需要我们自己释放
*/ #ifndef DLIST_HEAD
#define DLIST_HEAD #define list_entry(ptr, type, member) \
((type *)((char *)(ptr) - (char *)(&(((type *))->member)))) typedef struct dclist_head {
struct dclist_head * prev;
struct dclist_head * next;
} dclist_head_t; void init(dclist_head_t *head);
void append(dclist_head_t *head, dclist_head_t *node);
void treaverse(dclist_head_t *head, void (*pfun)(dclist_head_t *node) );
void dc_remove(dclist_head_t *head, void (*pfun)(dclist_head_t *node) ); #endif

dclist_head.c

 /*************************************************************************
> File Name: dclist_head.c
> Author: gaozy
> Mail: 44523253@qq.com
> Created Time: 2016年12月24日 星期六 10时19分49秒
************************************************************************/ #include <stdio.h>
#include <stdlib.h> #include "dclist_head.h" void init(dclist_head_t *head)
{
if ( head != NULL ) {
head->prev = NULL;
head->next = NULL;
}
} void append(dclist_head_t *head, dclist_head_t *node)
{
if ( head == NULL ) {
printf("error\n");
exit();
} if ( head->prev == NULL && head->next == NULL ) {
head->prev = node;
head->next = node;
node->prev = head;
node->next = head;
} else {
dclist_head_t *tmp = head->prev;
tmp->next = node;
node->prev = tmp;
node->next = head;
head->prev = node;
}
} void treaverse(dclist_head_t *head, void (*pfun)(dclist_head_t *node) )
{
if ( head == NULL || head->next == NULL )
return; dclist_head_t *tmp = head->next;
while ( tmp != head ) {
pfun(tmp);
tmp = tmp->next;
}
} void dc_remove(dclist_head_t *head, void (*pfun)(dclist_head_t *node) )
{
treaverse(head, pfun);
}

测试代码

main.c

 /*************************************************************************
> File Name: main.c
> Author: gaozy
> Mail: 44523253@qq.com
> Created Time: 2016年12月24日 星期六 11时11分25秒
************************************************************************/ #include <stdio.h>
#include <stdlib.h> #include "dclist_head.h" typedef struct {
int id;
dclist_head_t entry;
} student_t; void print(dclist_head_t *ptr)
{
student_t *stu = list_entry(ptr, student_t, entry);
if ( stu == NULL )
return;
printf("student id = %d\n", stu->id);
} void free_node(dclist_head_t *ptr)
{
if (ptr == NULL )
return; student_t *node = list_entry(ptr, student_t, entry);
free(node);
} student_t* make_node(int id)
{
student_t *stu = (student_t *)malloc(sizeof(student_t));
if ( stu != NULL ) {
stu->id = id;
} return stu;
} int main(void)
{
dclist_head_t list; init(&list); int i;
student_t *stu;
for ( i=; i<; i++ ) {
stu = make_node(i);
if ( stu != NULL )
append(&list, &stu->entry);
} treaverse(&list, print);
dc_remove(&list, free_node); return ;
}

水平有限,还请大神多多指点。

上一篇:对C语言中递归算法的分析


下一篇:ADO中最重要的对象有三个:Connection、Recordset和Command