==============================================
先来个知识背景：
我们都知道数组是存储数据的一种方式，但是数组对里面数据的操作比较麻烦(插入、删除等)
所以，我们有了单链表，单链表对于数据的插入删除都比数组方便很多，但是还是不那么方便，为什么？
因为，我们只能从头节点(一般的链表都有头节点，当然了循环队列除外)查找数据，不能往上查找，只能往下查找。
所以，我们又有了双向链表，它集成了单向链表的优点，解决了单链表的不足，使数据的操作变得方便很多,但是这也不是很方便.......
看到这里也就引出了主角---内核链表....（掌声~~~~）
`
什么是内核链表？ 它解决了双链表什么问题？
#################################################################################
先说第一个:
内核链表是双向链表的变种，它将逻辑与数据分开，这里有两个结构体
// 自己定义的结构体typedef struct node{ datatype data; struct list_head list;}listnode, *linklist;// 内核代码提供struct list_head { struct list_head *next, *prev;}; 可以看到 listnode 这个结构体包含了 struct list_head 这种类型的结构体.
listnode是我们说的数据(大结构体)，struct list_head是我们说的逻辑(小结构体)------小结构体嵌到大结构体里面
###########################################################################
那第二个呢？ 内核链表有什么特殊的，它能解决传统的双向链表什么缺点。
内核链表的诀窍在于数据和逻辑分来！
如果是传统的双向链表，它是不能灵活处理因链表变化的需求，因为它和数据捆绑在一块，
链表里面的数据变了那整个链表都变了，处理它的函数都需要改(尽管实现的逻辑代码一样)。
内核链表数据和逻辑是分开的，所以大结构体的变化是不影响小结构体的逻辑代码的！
所以....................内核代码就是很厉害了 0``0..
那么我们先来欣赏下用内核代码实现的一道小题目吧
代码如下
/* XXX.c文件 */#include#include #include #include #include #include #include "kernel_list.h"#ifndef DATATYPE #define DATATYPE int#endiftypedef DATATYPE datatype;// 在一个特殊的节点中，包含通用的标准链表实现typedef struct node{ datatype data; struct list_head list;}listnode, *linklist;linklist init_list(void){ // 申请一个头节点 linklist head = calloc(1, sizeof(listnode)); if(head != NULL) { //head->list.next = head->list.prev = &head->list; INIT_LIST_HEAD(&head->list); (在内核头文件) } return head;}linklist new_node(int i){ linklist new = calloc(1, sizeof(struct node)); if(new == NULL) { printf("creat new failed\n"); exit(0); } new->data = i; new->list.next = new->list.prev = NULL; return new;}void show(linklist head){ struct list_head *pos; linklist tmp; list_for_each(pos, &head->list) (在内核头文件) { // 将小结构体转换成大结构体 tmp = list_entry(pos, listnode, list); (在内核头文件) printf("%d", tmp->data); } printf("\n");}void rearrange(linklist head){ struct list_head *tmp; struct list_head *pos; linklist p; bool first = true; // 遍历所有小节点 list_for_each_prev(pos, &head->list) (在内核头文件) { // 将小结构体转换成大结构体 p = list_entry(pos, listnode, list); (在内核头文件) // 这是一个偶数！并且不是第一个偶数！将他移动到链表的末尾 if(p->data % 2 == 0 && first != true) { // 将这个节点移到链表最后 list_move_tail(pos, &head->list); (在内核头文件) pos = tmp; } else // 遇到奇数，就记下这个位置 { tmp = pos; } first = false; } }int main(void){ // 搞一个空双向循环链表 linklist head = init_list(); if(head == NULL) { printf("init failed"); exit(0); } // 依次插入若干个节点 int n; scanf("%d", &n); int i; for(i=1; i<=n; i++) { linklist new = new_node(i); // 传入 小结构体节点的地址、小结构体头节点的地址 (在内核头文件) list_add_tail(&new->list, &head->list); } // 显示链表里面的所有节点看看是否正确 show(head); // 按照题目需要，奇偶数重新排列 rearrange(head); // 再次显示链表里面的所有节点看看是否正确 show(head); return 0;}
1 /*内核头文件 */ 2 #ifndef __DLIST_H 3 #define __DLIST_H 4 5 /* This file is from Linux Kernel (include/linux/list.h) 6 * and modified by simply removing hardware prefetching of list items. 7 * Here by copyright, credits attributed to wherever they belong. 8 * Kulesh Shanmugasundaram (kulesh [squiggly] isis.poly.edu) 9 */ 10 11 /* 12 * Simple doubly linked list implementation. 13 * 14 * Some of the internal functions (“__xxx”) are useful when 15 * manipulating whole lists rather than single entries, as 16 * sometimes we already know the next/prev entries and we can 17 * generate better code by using them directly rather than 18 * using the generic single-entry routines. 19 */ 20 /** 21 * container_of - cast a member of a structure out to the containing structure 22 * 23 * @ptr: the pointer to the member. 24 * @type: the type of the container struct this is embedded in. 25 * @member: the name of the member within the struct. 26 * 27 */ 28 #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) 29 30 #define container_of(ptr, type, member) ({ \ 31 const typeof( ((type *)0)->member ) *__mptr = (ptr); \ 32 (type *)( (char *)__mptr - offsetof(type,member) );}) 33 /* 34 * These are non-NULL pointers that will result in page faults 35 * under normal circumstances, used to verify that nobody uses 36 * non-initialized list entries. 37 */ 38 #define LIST_POISON1 ((void *) 0x00100100) 39 #define LIST_POISON2 ((void *) 0x00200) 40 41 struct list_head { 42 struct list_head *next, *prev; 43 }; 44 45 #define LIST_HEAD_INIT(name) { &(name), &(name) } 46 47 #define LIST_HEAD(name) \ 48 struct list_head name = LIST_HEAD_INIT(name) 49 50 #define INIT_LIST_HEAD(ptr) do { \ 51 (ptr)->next = (ptr); (ptr)->prev = (ptr); \ 52 } while (0) 53 54 /* 55 * Insert a new entry between two known consecutive entries. 56 * 57 * This is only for internal list manipulation where we know 58 * the prev/next entries already! 59 */ 60 static inline void __list_add(struct list_head *new, 61 struct list_head *prev, 62 struct list_head *next) 63 { 64 next->prev = new; 65 new->next = next; 66 new->prev = prev; 67 prev->next = new; 68 } 69 70 /** 71 * list_add – add a new entry 72 * @new: new entry to be added 73 * @head: list head to add it after 74 * 75 * Insert a new entry after the specified head. 76 * This is good for implementing stacks. 77 */ 78 static inline void list_add(struct list_head *new, struct list_head *head) 79 { 80 __list_add(new, head, head->next); 81 } 82 83 /** 84 * list_add_tail – add a new entry 85 * @new: new entry to be added 86 * @head: list head to add it before 87 * 88 * Insert a new entry before the specified head. 89 * This is useful for implementing queues. 90 */ 91 static inline void list_add_tail(struct list_head *new, struct list_head *head) 92 { 93 __list_add(new, head->prev, head); 94 } 95 96 /* 97 * Delete a list entry by making the prev/next entries 98 * point to each other. 99 *100 * This is only for internal list manipulation where we know101 * the prev/next entries already!102 */103 static inline void __list_del(struct list_head *prev, struct list_head *next)104 {105 next->prev = prev;106 prev->next = next;107 }108 109 /**110 * list_del – deletes entry from list.111 * @entry: the element to delete from the list.112 * Note: list_empty on entry does not return true after this, the entry is in an undefined state.113 */114 static inline void list_del(struct list_head *entry)115 {116 __list_del(entry->prev, entry->next);117 entry->next = (void *) 0;118 entry->prev = (void *) 0;119 }120 121 /**122 * list_del_init – deletes entry from list and reinitialize it.123 * @entry: the element to delete from the list.124 */125 static inline void list_del_init(struct list_head *entry)126 {127 __list_del(entry->prev, entry->next);128 INIT_LIST_HEAD(entry);129 }130 131 /**132 * list_move – delete from one list and add as another’s head133 * @list: the entry to move134 * @head: the head that will precede our entry135 */136 static inline void list_move(struct list_head *list,137 struct list_head *head)138 {139 __list_del(list->prev, list->next);140 list_add(list, head);141 }142 143 /**144 * list_move_tail – delete from one list and add as another’s tail145 * @list: the entry to move146 * @head: the head that will follow our entry147 */148 static inline void list_move_tail(struct list_head *list,149 struct list_head *head)150 {151 __list_del(list->prev, list->next);152 list_add_tail(list, head);153 }154 155 /**156 * list_empty – tests whether a list is empty157 * @head: the list to test.158 */159 static inline int list_empty(struct list_head *head)160 {161 return head->next == head;162 }163 164 static inline void __list_splice(struct list_head *list,165 struct list_head *head)166 {167 struct list_head *first = list->next;168 struct list_head *last = list->prev;169 struct list_head *at = head->next;170 171 first->prev = head;172 head->next = first;173 174 last->next = at;175 at->prev = last;176 }177 178 /**179 * list_splice – join two lists180 * @list: the new list to add.181 * @head: the place to add it in the first list.182 */183 static inline void list_splice(struct list_head *list, struct list_head *head)184 {185 if (!list_empty(list))186 __list_splice(list, head);187 }188 189 /**190 * list_splice_init – join two lists and reinitialise the emptied list.191 * @list: the new list to add.192 * @head: the place to add it in the first list.193 *194 * The list at @list is reinitialised195 */196 static inline void list_splice_init(struct list_head *list,197 struct list_head *head)198 {199 if (!list_empty(list)) {200 __list_splice(list, head);201 INIT_LIST_HEAD(list);202 }203 }204 205 /**206 * list_entry – get the struct for this entry207 * @ptr: the &struct list_head pointer.208 * @type: the type of the struct this is embedded in.209 * @member: the name of the list_struct within the struct.210 */211 #define list_entry(ptr, type, member) \212 ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))213 214 /**215 * list_for_each - iterate over a list216 * @pos: the &struct list_head to use as a loop counter.217 * @head: the head for your list.218 */219 #define list_for_each(pos, head) \220 for (pos = (head)->next; pos != (head); \221 pos = pos->next)222 /**223 * list_for_each_prev - iterate over a list backwards224 * @pos: the &struct list_head to use as a loop counter.225 * @head: the head for your list.226 */227 #define list_for_each_prev(pos, head) \228 for (pos = (head)->prev; pos != (head); \229 pos = pos->prev)230 231 /**232 * list_for_each_safe - iterate over a list safe against removal of list entry233 * @pos: the &struct list_head to use as a loop counter.234 * @n: another &struct list_head to use as temporary storage235 * @head: the head for your list.236 */237 #define list_for_each_safe(pos, n, head) \238 for (pos = (head)->next, n = pos->next; pos != (head); \239 pos = n, n = pos->next)240 241 /**242 * list_for_each_entry - iterate over list of given type243 * @pos: the type * to use as a loop counter.244 * @head: the head for your list.245 * @member: the name of the list_struct within the struct.246 */247 #define list_for_each_entry(pos, head, member) \248 for (pos = list_entry((head)->next, typeof(*pos), member); \249 &pos->member != (head); \250 pos = list_entry(pos->member.next, typeof(*pos), member))251 252 /**253 * list_for_each_entry_safe – iterate over list of given type safe against removal of list entry254 * @pos: the type * to use as a loop counter.255 * @n: another type * to use as temporary storage256 * @head: the head for your list.257 * @member: the name of the list_struct within the struct.258 */259 #define list_for_each_entry_safe(pos, n, head, member) \260 for (pos = list_entry((head)->next, typeof(*pos), member), \261 n = list_entry(pos->member.next, typeof(*pos), member); \262 &pos->member != (head); \263 pos = n, n = list_entry(n->member.next, typeof(*n), member))264 265 #endif 好吧，看的懂并且能从原理上理解这份代码、加上我那篇《写程序关于c语言语法的一些心得--内存和指针的正确认识》都理解了后
C语言语法就没问题了 0^0~...