这篇文章主要介绍了linux中的内核链表实例详解的相关资料,链表中一般都要进行初始化、插入、删除、显示、释放链表，寻找节点这几个操作，需要的朋友可以参考下
linux中的内核链表实例详解
链表中一般都要进行初始化、插入、删除、显示、释放链表，寻找节点这几个操作，下面我对这几个操作进行简单的介绍，因为我的能力不足，可能有些东西理解的不够深入，造成一定的错误，请各位博友指出。
A、Linux内核链表中的几个主要函数(下面是内核中的源码拿出来给大家分析一下)
1）初始化：
#define INIT_LIST_HEAD(ptr) do { (ptr)->next = (ptr); (ptr)->prev = (ptr); } while (0) // ptr为struct list_head，其中包括两个指针next和prev，这里已经可以看出内核链表是双向循环链表
2）尾部插入：
static inline void list_add_tail(struct list_head *new, struct list_head *head) { __list_add(new, head->prev, head); } //尾部插入,传入的参数是新节点中的两个指针和头结点中的两个指针
3）头部插入函数
static inline void list_add(struct list_head *new, struct list_head *head) { __list_add(new, head, head->next); } //头插入函数,传入的参数是新节点中的两个指针和头结点中的两个指针
4）删除节点函数
static inline void list_del(struct list_head *entry) //传入要删除节点中的指针域 { __list_del(entry->prev, entry->next);//两个参数分别为所删除节点前一个节点和后一个节点 entry->next = (void *) 0;//删除节点后置为空 entry->prev = (void *) 0; }
5）显示函数（如果要打印出链表中的信息的话要自己写成打印的函数，比如printf，因为这个其实是一个遍历的函数，没有显示的功能）
#define list_for_each_entry(pos, head, member) for (pos = list_entry((head)->next, typeof(*pos), member); &pos->member != (head); pos = list_entry(pos->member.next, typeof(*pos), member)) /* 这个函数用于遍历链表 pos为节点指针， head是头结点中的两个指针的地址 member为各节点中的指针域 */
6）删除链表
#define list_for_each_safe(pos, n, head) for (pos = (head)->next, n = pos->next; pos != (head); pos = n, n = pos->next) //这里面的pos和n都是list_head指针，n指针是用于在删除时不让链表断链
7）寻找节点（这也是用的内核中的遍历函数）
#define list_for_each_entry(pos, head, member) for (pos = list_entry((head)->next, typeof(*pos), member); &pos->member != (head); pos = list_entry(pos->member.next, typeof(*pos), member))
B.下面来段代码给大家看看具体的运用方法
#include"kernel.h" #include<errno.h> #include<stdio.h> #include<stdlib.h> typedef struct list_node { int data; struct list_head list;//节点的指针域是被封装在struct list_head这个结构体内 //这个结构体中包括struct list_head *next,*prev }*node,node1; node init_head(node head)//初始化空链表 { head = (node)malloc(sizeof(node1));//为节点分配空间 if(head == NULL) { perror("head"); return NULL; } INIT_LIST_HEAD(&(head->list));//#define INIT_LIST_HEAD(ptr) do { (ptr)->next = (ptr); (ptr)->prev = (ptr); } while (0)//调用内核中的初始化函数，传入的参数是 //节点的中两个指针，即struct list_head结构体中的两个指针 return head; } node insert_tail(node head,int data)//尾部插入函数 { node new = (node)malloc(sizeof(node1));//为新节点分配空间 if(new == NULL)//判断一下分配空间是否成功 { perror("new:"); return NULL; } new->data = data; list_add_tail(&(new->list),&(head->list));//调用内核中的从尾部插入的函数，传入的参数为新节点中的两个指针 //和头结点中的两个指针 return 0; } head_insert_node(node head,int data)//头插入函数 { node new;//创建一个新节点 new = (node)malloc(sizeof(node1));//为新节点分配空间 if(new == NULL)//判断一下分配空间是否成功 { perror("new:"); return 0; } new->data = data; list_add(&(new->list),&(head->list));//调用内核中从头插入的函数，传入的参数为新节点的两个指针和头结点的两个指针 return 0; } node search_node(node head,int data)//寻找节点函数 { node p = NULL; list_for_each_entry(p,&(head->list),list) //内核中的遍历函数 { if(p->data == data) //p即为需要找的节点 { printf("found the data:%dn",p->data); goto OK; } } puts("not found the data!"); return NULL; OK: return p; } int show_node(node tmp) { if(tmp == NULL) { puts("tmp is NULL!"); return -1; } printf("the data is %dn",tmp->data); return 0; } int delete_node(node head,int data) { node p = NULL; list_for_each_entry(p,&(head->list),list) { if(p->data == data) { printf("found the data which you want to delete!n"); goto f; } } f: list_del(&(p->list)); free(p); return 0; } int show_list(node head) { node p = NULL; list_for_each_entry(p,&(head->list),list) { printf("data:%dn",p->data); } return 0; } int delete_list(node head)//删除链表函数 { node p,q; list_for_each_entry_safe(p,q,&(head->list),list)//这是内核中的安全删除函数 { list_del(&(p->list)); free(p); } list_del(&(head->list)); free(head); return 0; } int main(int argc,char **argv) { node head; node tmp; head = init_head(head);//初始化空链表函数 insert_tail(head,45);//从末尾插入函数 insert_tail(head,55); insert_tail(head,65); head_insert_node(head,75);//从头插入函数 show_list(head); //显示链表函数 tmp = search_node(head,55);//寻找结点函数 show_node(head); delete_node(head,55); //show_list(head); delete_list(head);//删除链表函数 return 0; }</stdlib.h></stdio.h></errno.h>
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
