上一篇: iOS 系统中的常用数据结构之查找
双向链表
功能: 对双向链表进行添加, 删除功能.
头文件:#include <search.h>
平台: POSIX
函数签名:
- // 将某个链表元素 element 插入到 pred 后面. 如果 pred 为 NULL 则表示 element 就是链表的头部.
- void insque(void *element, void *pred);
- // 将链表元素 element 从链表中删除.
- void remque(void *element);
参数:
element:[in] 要添加或者删除的链表元素.
pred:[in] 链表插入元素 element 的前缀元素.
描述:
系统并没有规定链表的数据结构, 但是要求链表元素结构体中的前面两个数据成员必须是分别指向后一个元素和前一个元素. 下面就是链表元素结构体模板:
- struct que_elem {
- struct que_elem *next;
- struct que_elem *prev;
- // 其他自定义数据成员
- };
上述的两个函数只负责将元素插入链表以及将元素从链表中删除, 至于维护链表的表头或者链表的数量以及链表元素的内存分配和销毁则需要我们自身去维护.
示例代码:
- //student 结构体必须要满足上面链表元素的结构体定义规则
- typedef student
- {
- struct student *next;
- struct student *prev;
- int age;
- char *name;
- }student_t;
- void traverse(student_t *head)
- {
- while (head->next != NULL)
- {
- printf("student's age = %d, name=%s\n",head->age, head->name);
- head = head->next;
- }
- }
- void main()
- {
- student_t *student1 = malloc(sizeof(student_t));
- student1->age = 10;
- student1->name = "Alex";
- student_t *student2 = malloc(sizeof(student_t));
- student2->age = 20;
- student2->name = "Bob";
- //student1 作为链表的表头
- insque(student1, NULL);
- //student2 插入到 student1 后面
- insque(student2, student1);
- // 遍历链表
- traverse(student1);
- // 删除 student1
- remque(student1);
- free(student1);
- // 删除 student2
- remque(student2);
- free(student2);
- }
来源: http://www.jianshu.com/p/708ecbe5e71a