首页 > 代码库 > 第十八天：双向链表与内核链表
第十八天：双向链表与内核链表
对于双向链表就是在单向链表的基础上加了一个向前的结构体指针。对于一些操作的思想更加的简单。麻烦的事情就是要判断的内容更多了。因为内核链表中运用到的都是双向链表。所以要学习内核链表。就先要会对双向链表进行基本的操作。比如新增和显示。
内核链表中的实现思想类似与面向对象的思想，成员和方法分开写。比如下面这个简单的代码：
1 #include<stdio.h> 2 3 struct boy; 4 struct file_operations; 5 6 struct boy{ 7 int age;//成员 8 char *gf; 9 struct file_operations *ops;10 };11 struct file_operations{ //方法12 void (*fp)(struct boy *);13 };14 void eat(struct boy *t)//t 为this指针15 {16 printf("please %s\n",t->gf);17 }18 int main()19 {20 struct file_operations file;21 file.fp = eat;22 23 struct boy tom;24 tom.gf = "lily";25 tom.ops = &file;26 tom.ops->fp(&tom);27 28 struct boy jim;29 jim.gf = "lucy";30 jim.ops = &file;31 jim.ops->fp(&jim);32 }
在这个函数中，定义了两个结构体，boy和file_operations ，在file_operations结构体中定义了函数指针，boy的结构体中定义了file_operations结构体。这样做，boy的成员就能过通过函数指针来访问函数。
下面的代码是今晚最终的作业，对内核链表进行排序。这个就是对前面知识的大综合了。没有什么新的内容。
1 #include<stdio.h> 2 #include<stdlib.h> 3 #define container_of(ptr,type,mem) (type*)((unsigned long)ptr - (unsigned long)&((type *)0)->mem) 4 5 struct list_head{ 6 struct list_head *pre; 7 struct list_head *next; 8 }; 9 struct person{ 10 struct list_head li; 11 int age; 12 }; 13 struct list_head *insert(struct list_head * head ,int age); 14 void show(struct list_head *head); 15 void show_pre(struct list_head *head); 16 struct list_head *sort(struct list_head *head); 17 int main() 18 { 19 struct list_head *head = NULL; 20 head = insert(head,10); 21 head = insert(head,12); 22 head = insert(head,13); 23 head = insert(head,19); 24 head = insert(head,21); 25 head = insert(head,20); 26 show(head); 27 printf("---------\n"); 28 show_pre(head); 29 printf("---------\n"); 30 head = sort(head); 31 show(head); 32 } 33 struct list_head *insert(struct list_head * head ,int age){ 34 35 struct person * p = (struct person *)malloc(sizeof(struct person)); 36 p->age = age; 37 if(head == NULL){ 38 p->li.pre = NULL; 39 p->li.next = NULL; 40 }else{ 41 p->li.pre = NULL; 42 p->li.next = head; 43 head->pre = &p->li; 44 } 45 return &p->li ; 46 } 47 48 void show(struct list_head *head){ 49 struct person *tmp; 50 while(head){ 51 tmp = container_of(head,struct person,li); 52 printf("age is %d\n",tmp->age); 53 head = head ->next; 54 } 55 } 56 void show_pre(struct list_head *head){ 57 if(head ==NULL) 58 return ; 59 struct list_head *tail = head; 60 while(tail->next) 61 tail = tail ->next; 62 struct person *tmp; 63 while(tail){ 64 tmp = container_of(tail,struct person,li); 65 printf("age is %d\n",tmp->age); 66 tail = tail->pre; 67 } 68 } 69 struct list_head *sort(struct list_head *head){ 70 71 if(head == NULL||head->next == NULL) 72 return head; 73 struct list_head *min = NULL; 74 struct list_head *oldhead = head; 75 struct list_head *newhead = NULL; 76 struct list_head *cur =NULL ; 77 struct list_head *tmp =NULL; 78 struct list_head *tail =NULL; 79 struct person *minvalue; 80 struct person *curvalue; 81 while(oldhead){ 82 //找到最小的 83 min = oldhead; 84 cur = oldhead; 85 tail = oldhead; 86 while(cur){ 87 minvalue = http://www.mamicode.com/container_of(min,struct person,li); 88 curvalue = http://www.mamicode.com/container_of(cur,struct person,li); 89 if(minvalue->age > curvalue->age){ 90 min = cur; 91 } 92 cur = cur->next; 93 } 94 //切下 分成四种情况 95 while(tail->next) 96 tail = tail->next; 97 if(oldhead ->next == NULL){ 98 oldhead = oldhead ->next; 99 }else if(min == oldhead){100 min->next->pre = NULL; 101 oldhead = oldhead ->next;102 }else if(min == tail){103 min->pre->next = NULL; 104 105 }else{106 min->pre->next = min->next;107 min->next->pre = min->pre;108 min->pre = NULL;109 }110 min->next = NULL; 111 //链接到新的链表中112 if(newhead ==NULL){113 newhead = min;114 tmp = newhead;115 }else{116 tmp ->next = min;117 min ->next = NULL;118 min->pre = tmp;119 tmp = tmp->next;120 }121 }122 return newhead;123 }
发现代码越写越长了。这个代码就是内核链表的实现。内核里面的链表结构大概如此。自己实现一遍后，对于以后的内核源码阅读会很有帮助。
这个代码就是将container_of宏和双链表的操作结合起来了。综合性比较强。
第十八天：双向链表与内核链表
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。