原创tanglinux 最后发布于2012-02-27 18:44:29 阅读数 4153
开发平台：Ubuntu11.04
编译器：gcc version 4.5.2 (Ubuntu/Linaro 4.5.2-8ubuntu4)
内核源码：linux-2.6.38.8.tar.bz2
据我们所知，单链表只有一个指向其直接后继的指针域，而且只能从某个结点出发顺着指针域往后寻查其他结点。若要寻查结点的直接前趋，则需要从头指针重新开始。为了克服单链表这种单向性的缺点，可利用双向链表。顾名思义，在双向链表的结点中有两个指针域，其一指向直接后继，另一个指向直接前趋。
双向循环链表指的是终止结点的next的指针域指向头结点，头结点的prior指针域指向终止结点，如下图所示：
1、一般双向循环链表的实现
例子所用的结构体如下：
#include <stdio.h>
#include <stdlib.h>
typedef int data_type;
typedef struct double_listnode {
data_type data;
struct double_listnode *prior, *next;
}double_listnode_t, *double_listnode_p;
双向循环链表的运算
（1）、创建（带头结点）
通过循环依次创建n个数据域为整数的结点，示例代码如下：
static double_listnode_t *init_double_list(int n)
{
int i;
double_listnode_p head, p, s;
head = (double_listnode_t *)malloc(sizeof(double_listnode_t));
head -> prior = head -> next = head;
p = head;
for (i = 0; i < n; i++) {
s = (double_listnode_t *)malloc(sizeof(double_listnode_t));
s -> data = i + 1;
s -> next = head;
head -> prior = s;
s -> prior = p;
p -> next = s;
p = s;
}
return head;
}
（2）、按结点在链表中的位置查找
示例代码如下：
static double_listnode_t *get_double_listnode(double_listnode_p head, int i)
{
double_listnode_p p = head;
int j = 0;
while (p -> next != head && j < i) {
p = p -> next;
j++;
}
if (i == j)
return p;
else
return NULL;
}
（3）、在链表中的i位置插入一个结点
首先要获得i-1结点的地址，然后初始化数据域并插入，示例代码如下：
static void insert_double_listnode(double_listnode_p head, int i, data_type data)
{
double_listnode_p tmp, p = NULL;
p = get_double_listnode(head, i - 1);
if (p == NULL) {
fprintf(stderr, "position error\n");
exit(-1);
}
tmp = (double_listnode_t *)malloc(sizeof(double_listnode_t));
tmp -> data = data;
tmp -> prior = p;
tmp -> next = p -> next;
p -> next -> prior = tmp;
p -> next = tmp;
}
（4）、删除链表的i结点
先获得i结点的地址，然后删除，示例代码如下：
static void delete_double_listnode(double_listnode_p head, int i)
{
double_listnode_p p = NULL;
p = get_double_listnode(head, i);
if (p == NULL || p == head) {
fprintf(stderr, "position error\n");
exit(-1);
}
p -> prior -> next = p -> next;
p -> next -> prior = p -> prior;
free(p);
}
（5）、打印链表
示例代码如下：
static void print_double_listnode(double_listnode_p head)
{
double_listnode_p p = head -> next;
while (p != head) {
printf("%d ", p -> data);
p = p -> next;
}
printf("\n");
}
（6）、销毁链表
示例代码如下：
static void destroy_double_list(double_listnode_p head)
{
double_listnode_p s, p = head -> next;
while (p != head) {
s = p;
p = p -> next;
free(s);
}
free(head);
}
综合测试上述所讲函数的代码如下：
int main(void)
{
int a = 10;
double_listnode_p head;
head = init_double_list(a);
print_double_listnode(head);
insert_double_listnode(head, 7, 11);
print_double_listnode(head);
delete_double_listnode(head, 5);
print_double_listnode(head);
destroy_double_list(head);
return 0;
}
综合测试代码的功能是先创建10个结点的双向循环链表，然后在链表的第7位插入一个数据域为11的结点，再然后删除链表的第5个结点，最后销毁整个链表。综合测试代码输出结果如下：
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 11 7 8 9 10
1 2 3 4 6 11 7 8 9 10
————————————————
版权声明：本文为CSDN博主「tanglinux」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/npy_lp/article/details/7294494
【資料引用資訊】
google關鍵字:详解Linux内核双向循环链表算法的实现（上）
google關鍵字:详解Linux内核双向循环链表算法的实现（上）
