admin 管理员组文章数量: 887031
list
写贪吃蛇C语音代码,大多用到 双向链表 做蛇的数据结构体。如下:typedef struct node /* Snake_node structur*{int x_pos;int y_pos;struct node *prev;struct node *next;
} Snake_Node;
另在一篇博文看到有这个概念:Linux内核的“侵入式链表”list_head“。优点:不用管理大量的链表节点内存了,因为“本身即链表”。故百度终结用法如下:
相关头文件include/linux/list.h
/*结构体原型*/
struct list_head { struct list_head *next, *prev;
}; #define LIST_HEAD(name) //定义并初始化头结点head
#define INIT_LIST_HEAD(ptr) //初始化头结点ptr,因此需要首先定义ptr
_INLINE_ void list_add(struct list_head *add, struct list_head *head) //每次添加节点到head之后,始终都是添加到头结点之后
_INLINE_ void list_add_tail(struct list_head *add, struct list_head *head)//每次添加节点都是头结点之前,由于是循环链表,就是说添加到链表尾部
_INLINE_ void list_del(struct list_head *entry)//删除节点
_INLINE_ void list_del_init(struct list_head *entry)//删除节点,并初始化被删除的结点(也就是使被删除的结点的prev和next都指向自己) _INLINE_ int list_empty(struct list_head *head)//判断链表是否为空
_INLINE_ void list_splice(struct list_head *list, struct list_head *head)//通过两个链表的head,进行连接
#define list_entry(ptr, type, member) //通过偏移值取type类型结构体的首地址
#define list_for_each(pos, head) //遍历链表,循环内不可调用list_del()删除节点
#define list_for_each_safe(pos, pnext, head) //遍历链表,可以同时有删除节点的操作
struct person { int age; int weight; struct person *next, *prev;
};
采用
侵入式链表:
struct person {int age; int weight;struct list_head list;
};
可能又会有些人会问了,struct list_head都不是struct persionl类型,怎么可以 做链表的指针呢?其实,无论是什么样的指针,它的大小都是一样的,32位的系统中,指针的大小都是32位(即4个字节),只是不同类型的指针在解释的时候不一样而已,那么这个struct list_head又是怎么去做这些结构的链表指针呢,那么就请看下一节。
二、struct list_head结构的操作
首先,让我们来看下和struct list_head有关的两个宏,它们定义在list.h文件中。
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)
#define INIT_LIST_HEAD(ptr) do { \ (ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)
这两个宏是用了定义双向链表的头节点的,定义一个双向链表的头节点,我们可以这样:
struct list_head head;
LIST_HEAD_INIT(head);
又或者直接这样:
LIST_HEAD(head);
这样,我们就定义并初始化了一个头节点。
#define LIST_HEAD_INIT(name) { &(name), &(name) }
就是用head的地址初始化其两个成员next和prev ,使其都指向自己。
我们再看下和其相关的几个函数,这些函数都作为内联函数也都定义list.h中,这里要说明一下linux源码
的一个风格,在下面的这些函数中以下划线开始的函数是给内部调用的函数,而以符开始的函数就是对外使用
的函数,这些函数一般都是调用以下划线开始的函数,或是说是对下划线开始的函数的封装。
2.1 增加节点的函数
static inline void __list_add();
static inline void list_add();
static inline void list_add_tail();
其实看源代码是最好的讲解了,这里我再简单的讲一下。
/** * __list_add - Insert a new entry between two known consecutive entries. * @new: * @prev: * @next: * * This is only for internal list manipulation where we know the prev/next * entries */
static __inline__ void __list_add(struct list_head * new, struct list_head * prev, struct list_head * next)
{ next->prev = new; new->next = next; new->prev = prev; prev->next = new;
}
//这个函数在prev和next间插入一个节点new。 /** * list_add - add a new entry * @new: new entry to be added * @head: list head to add it after * * Insert a new entry after the specified head. * This is good for implementing stacks. */static __inline__ void list_add(struct list_head *new, struct list_head *head)
{ __list_add(new, head, head->next);
}
//这个函数在head节点后面插入new节点。 /** * list_add_tail - add a new entry * @new: new entry to be added * @head: list head to add it before * * Insert a new entry before the specified head. * This is useful for implementing queues. */
static __inline__ void list_add_tail(struct list_head *new, struct list_head *head)
{ __list_add(new, head->prev, head);
}
这个函数和上面的那个函数相反,它在head节点的前面插入new节点。
2.2 从链表中删除节点的函数
/** * __list_del - * @prev: * @next: * * Delete a list entry by making the prev/next entries point to each other. * * This is only for internal list manipulation where we know the prev/next * entries */
static __inline__ void __list_del(struct list_head * prev, struct list_head * next)
{ next->prev = prev; prev->next = next;
} /** * list_del - deletes entry from list. * @entry: the element to delete from the list. * * Note: list_empty on entry does not return true after this, the entry is in * an undefined state. */
static __inline__ void list_del(struct list_head *entry)
{ __list_del(entry->prev, entry->next);
} /** * list_del_init - deletes entry from list and reinitialize it. * @entry: the element to delete from the list. */
static __inline__ void list_del_init(struct list_head *entry)
{ __list_del(entry->prev, entry->next); INIT_LIST_HEAD(entry);
}
这里简单说一下,list_del(struct list_head *entry)是从链表中删除entry节点。
list_del_init(struct list_head *entry) 不但从链表中删除节点,还把这个节点的向前向后指针都指
向自己,即初始化。
那么,我们怎么判断这个链表是不是空的呢!上面我说了,这里的双向链表都是有一个头节点,而我们上面看到,定义一个头节点时我们就初始化了,即它的prev和next指针都指向自己。所以这个函数是这样的。
/** * list_empty - tests whether a list is empty * @head: the list to test. */
static __inline__ int list_empty(struct list_head *head)
{ return head->next == head;
}
讲了这几个函数后,这又到了关键了,下面讲解的一个宏的定义就是对第一节中,我们所要说的为什么在一个
结构中加入struct list_head变量就把这个结构变成了双向链表呢,这其中的关键就是怎么通过这个 struct list_head变量来获取整个结构的变量,下面这个宏就为你解开答案:
/** * list_entry - get the struct for this entry * @ptr: the &struct list_head pointer. * @type: the type of the struct this is embedded in. * @member: the name of the list_struct within the struct. */
#define list_entry(ptr, type, member) \ ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
乍一看下,不知道这个宏在说什么,没关系,我举个例子来为你一一解答 :)
首先,我们还是用上面的结构:
struct person
{ int age; int weight; struct list_head list;
};
我们一看到这样的结构就应该知道它定义了一个双向链表,下面来看下。
我们有一个指针:
struct list_head *pos; 现在有这个指针,我们怎么去获得这个指针所在的结构的变量(即是struct person变量,其实是struct person指针)呢?看下面这样使用:
struct person *one = list_entry(pos, struct person, list);
不明白是吧,展开一下 list_entry结构如下:
((struct person *)((char *)(pos) - (unsigned long)(&((struct person *)0)->list)))
用个图形来说(unsigned long)(&((struct person *)0)->list,如下: (char *)(pos):是将pos由struct list_head*转 成char* ,指向list_head的地址。 (unsigned long)(&((struct person *)0)->list):先看最里面的(struct person *)0),它是把0地址转 成struct person指针,然后(struct person *)0)->list就是指向list变量,之后是 &((struct person *)0)->list是取这个变量的地址,最后是(unsigned long)(&((struct person *)0)->list)把这个变量的地址值变成一个整形数! 这么复杂啊,其实说白了,这个(unsigned long)(&((struct person *)0)->list)的意思就是取list变量在struct person结构中的偏移量。 这里等于8。 知道这2个值即可得到person的地址了。
2.3 list_head 的遍历的宏
/** * list_for_each - iterate over a list * @pos: the &struct list_head to use as a loop counter. * @head: the head for your list. */
#define list_for_each(pos, head) \ for (pos = (head)->next; pos != (head); pos = pos->next) /** * list_for_each_safe - iterate over a list safe against removal of list entry * @pos: the &struct list_head to use as a loop counter. * @n: another &struct list_head to use as temporary storage * @head: the head for your list. */
#define list_for_each_safe(pos, n, head) \ for (pos = (head)->next, n = pos->next; pos != (head); \ pos = n, n = pos->next)
list_for_each(pos, head)是遍历整个head链表中的每个元素,每个元素都用pos指向。 list_for_each_safe(pos, n, head)是用于删除链表head中的元素,不是上面有删除链表元素的函数了 吗,为什么这里又要定义一个这样的宏呢。看下这个宏后面有个safe字,就是说用这个宏来删除是安全的, 直接用前面的那些删除函数是不安全的。这个怎么说呢,我们看下下面这个图,有三个元素a ,b ,c。
list_for_each(pos, myhead)
{ if (pos == b) { list_del_init(pos); //break; } 。。。 }
上面的算法是不安全的,因为当我们删除b后,如下图这样:
上删除pos即b后,list_for_each要移到下一个元素,还需要用pos来取得下一个元素,但pos的指向已 经改变,如果不直接退出而是在继续操作的话,就会出错了。 而 list_for_each_safe就不一样了,如果上面的代码改成这样:
struct list_head *pos, *n;
list_for_each_safe(pos, n, myhead)
{ if (pos == b) { list_del_init(pos); //break; } 。。。 }
这里我们使用了n作为一个临时的指针,当pos被删除后,还可以用n来获得下一个元素的位置。 三、 例子
我用一个程序来说明在struct person中增加了struct list_head变量后怎么来操作这样的双向链表。
#include <stdio.h>
#include "list.h" struct person
{ int age; int weight; struct list_head list;
}; int main(int argc, char* argv[])
{ struct person *tmp; struct list_head *pos, *n; int age_i, weight_j; // 定义并初始化一个链表头 struct person person_head; INIT_LIST_HEAD(&person_head.list); for(age_i = 10, weight_j = 35; age_i < 40; age_i += 5, weight_j += 5) { tmp =(struct person*)malloc(sizeof(struct person)); tmp->age = age_i; tmp->weight = weight_j; // 把这个节点链接到链表后面 // 这里因为每次的节点都是加在person_head的后面,所以先加进来的节点就在链表里的最后面 // 打印的时候看到的顺序就是先加进来的就在最后面打印 list_add(&(tmp->list), &(person_head.list)); } // 下面把这个链表中各个节点的值打印出来 printf("\n"); printf("=========== print the list ===============\n"); list_for_each(pos, &person_head.list) { // 这里我们用list_entry来取得pos所在的结构的指针 tmp = list_entry(pos, struct person, list); printf("age:%d, weight: %d \n", tmp->age, tmp->weight); } printf("\n"); // 下面删除一个节点中,age为20的节点 printf("========== print list after delete a node which age is 20
==========\n"); list_for_each_safe(pos, n, &person_head.list) { tmp = list_entry(pos, struct person, list); if(tmp->age == 20) { list_del_init(pos); free(tmp); } } list_for_each(pos, &person_head.list) { tmp = list_entry(pos, struct person, list); printf("age:%d, weight: %d \n", tmp->age, tmp->weight); } // 释放资源 list_for_each_safe(pos, n, &person_head.list) { tmp = list_entry(pos, struct person, list); list_del_init(pos); free(tmp); } return 0;
}
本文标签: list
版权声明:本文标题:list 内容由网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:http://www.freenas.com.cn/free/1698888430h317598.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论