c语言是如何实现泛型链表
2018-06-18 04:11:07来源:未知 阅读 ()
最近有看一点Linux内核源码,发现内核里大量使用了list_head结构体。百度查了一下,原来内核利用这个结构体实现了泛型。
自认为对链表已经很熟悉的我,决定自己实现一下。
下面以Node和list_head为例。
上图就是循环链大致思路了。(画的不好)
我们通过list_head对链表进行移动操作。
这里存在几个问题:
首先通过list_head得到的指针,它指向的list_head的结构体,但我们其实想要使用的是Node结构体。
再有,我们要设计一个泛型的链表,那么,我就不可以在实现链表时有任何对Node的操作。
解决办法:
1、通过计算,找到node结构体的首地址。(我们通过一个宏来实现)
1 #define list_entry(ptr, type, member) \ 2 ((type *)((char *)(ptr) - (char *)(&(((type *)0)->member))))
这个宏看起来可能点乱,但我们把思路缕清就不乱了。
我们只知道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
1 /************************************************************************* 2 > File Name: dlist_head.h 3 > Author: gaozy 4 > Mail: 44523253@qq.com 5 > Created Time: 2016年12月24日 星期六 10时11分22秒 6 ************************************************************************/ 7 8 /* 9 *这是我自己实现的一个泛型循环链表 10 *使用者只需要把dclist_head_t 这个结构体加入到自己的结构体中就可以使用这个链表了。 11 *在使用时,需要使用者创建一个头节点,之后使用init函数初始化。(当然,你也可以自己对他进行初始化操作) 12 *它很重要,否则无法使用这个链表。 13 *链表给使用者提供了四个函数 14 *init 刚刚已经说过了,我们用它初始化链表 15 *append 这是一个向链表中添加节点的函数,需要我们传入链表的头和新节点的dclist_head_t部分的指针 16 *treaverse 正如火函数名一样,它的作用是遍历链表,它需要我们提供一个函数指针 17 *这个指针的作用是对节点进行操作,参数是一个dclist_head_t 类型的指针,我们同过list_entry这个宏获取 18 *使用者自定义的数据类型。 19 *dc_remove这个函数用来释放链表,类似treaverse函数,需要我们自己实现删除j节点函数。 20 *它会释放链表中的所有节点,只有头结点例外,头需要我们自己释放 21 */ 22 23 #ifndef DLIST_HEAD 24 #define DLIST_HEAD 25 26 #define list_entry(ptr, type, member) \ 27 ((type *)((char *)(ptr) - (char *)(&(((type *)0)->member)))) 28 29 typedef struct dclist_head { 30 struct dclist_head * prev; 31 struct dclist_head * next; 32 } dclist_head_t; 33 34 void init(dclist_head_t *head); 35 void append(dclist_head_t *head, dclist_head_t *node); 36 void treaverse(dclist_head_t *head, void (*pfun)(dclist_head_t *node) ); 37 void dc_remove(dclist_head_t *head, void (*pfun)(dclist_head_t *node) ); 38 39 #endif
dclist_head.c
1 /************************************************************************* 2 > File Name: dclist_head.c 3 > Author: gaozy 4 > Mail: 44523253@qq.com 5 > Created Time: 2016年12月24日 星期六 10时19分49秒 6 ************************************************************************/ 7 8 #include <stdio.h> 9 #include <stdlib.h> 10 11 #include "dclist_head.h" 12 13 14 void init(dclist_head_t *head) 15 { 16 if ( head != NULL ) { 17 head->prev = NULL; 18 head->next = NULL; 19 } 20 } 21 22 void append(dclist_head_t *head, dclist_head_t *node) 23 { 24 if ( head == NULL ) { 25 printf("error\n"); 26 exit(1); 27 } 28 29 if ( head->prev == NULL && head->next == NULL ) { 30 head->prev = node; 31 head->next = node; 32 node->prev = head; 33 node->next = head; 34 } else { 35 dclist_head_t *tmp = head->prev; 36 tmp->next = node; 37 node->prev = tmp; 38 node->next = head; 39 head->prev = node; 40 } 41 } 42 43 void treaverse(dclist_head_t *head, void (*pfun)(dclist_head_t *node) ) 44 { 45 if ( head == NULL || head->next == NULL ) 46 return; 47 48 dclist_head_t *tmp = head->next; 49 while ( tmp != head ) { 50 pfun(tmp); 51 tmp = tmp->next; 52 } 53 } 54 55 void dc_remove(dclist_head_t *head, void (*pfun)(dclist_head_t *node) ) 56 { 57 treaverse(head, pfun); 58 }
测试代码
main.c
1 /************************************************************************* 2 > File Name: main.c 3 > Author: gaozy 4 > Mail: 44523253@qq.com 5 > Created Time: 2016年12月24日 星期六 11时11分25秒 6 ************************************************************************/ 7 8 #include <stdio.h> 9 #include <stdlib.h> 10 11 #include "dclist_head.h" 12 13 typedef struct { 14 int id; 15 dclist_head_t entry; 16 } student_t; 17 18 void print(dclist_head_t *ptr) 19 { 20 student_t *stu = list_entry(ptr, student_t, entry); 21 if ( stu == NULL ) 22 return; 23 printf("student id = %d\n", stu->id); 24 } 25 26 void free_node(dclist_head_t *ptr) 27 { 28 if (ptr == NULL ) 29 return; 30 31 student_t *node = list_entry(ptr, student_t, entry); 32 free(node); 33 } 34 35 student_t* make_node(int id) 36 { 37 student_t *stu = (student_t *)malloc(sizeof(student_t)); 38 if ( stu != NULL ) { 39 stu->id = id; 40 } 41 42 return stu; 43 } 44 45 int main(void) 46 { 47 dclist_head_t list; 48 49 init(&list); 50 51 int i; 52 student_t *stu; 53 for ( i=0; i<5; i++ ) { 54 stu = make_node(i); 55 if ( stu != NULL ) 56 append(&list, &stu->entry); 57 } 58 59 60 treaverse(&list, print); 61 dc_remove(&list, free_node); 62 63 64 return 0; 65 }
水平有限,还请大神多多指点。
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 关于各种不同开发语言之间数据加密方法(DES,RSA等)的互通的 2020-06-07
- 如何0基础学习C/C++? 2020-06-06
- C语言程序结构 2020-05-31
- C++冒泡排序 (基于函数模板实现) 2020-05-31
- opencv-12-高斯滤波-双边滤波(附C++代码实现) 2020-05-10
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash