【双向链表】
①.建立一个双向链表？
1 typedef struct DbNode
2 {
3 int data; //节点数据
4 DbNode *left; //前驱节点指针
5 DbNode *right; //后继节点指针
6 } DbNode;
（1）建立双向链表：为方便，这里定义了三个函数：
q CreateNode()根据数据来创建一个节点，返回新创建的节点。
q CreateList()函数根据一个节点数据创建链表的表头，返回表头节点。
q AppendNode ()函数总在表尾插入新节点（其内部调用CreateNode()生成节点），返回表头节点。
1 //根据数据创建创建节点
2 DbNode *CreateNode(int data)
3 {
4 DbNode *pnode = (DbNode *)malloc(sizeof(DbNode));
5 pnode->data = data;
6 pnode->left = pnode->right = pnode; //创建新节点时
7 //让其前驱和后继指针都指向自身
8 return pnode;
9}
10
11 //创建链表
12 DbNode *CreateList(int head) //参数给出表头节点数据
13 { //表头节点不作为存放有意义数据的节点
14 DbNode *pnode = (DbNode *)malloc(sizeof(DbNode));
15 pnode->data = head;
16 pnode->left = pnode->right = pnode;
17
18 return pnode;
19 }
20
21 //插入新节点,总是在表尾插入; 返回表头节点
22 DbNode *AppendNode(DbNode *head, int data) //参数1是链表的表头节点，
23 { //参数2是要插入的节点,其数据为data
24 DbNode *node = CreateNode(data); //创建数据为data的新节点
25 DbNode *p = head, *q;
26
27 while(p != NULL)
28 {
29 q = p;
30 p = p->right;
31 }
32 q->right = node;
33 node->left = q;
34
35 return head;
36 }
我们可以使用其中的CreateList()和AppendNode()来生成一个链表，下面是一个数据生成从0到9含有10个节点的循环链表。
1 DbNode *head = CreateList(0); //生成表头，表头数据为0
2
3 for (int i = 1; i < 10; i++)
4 {
5 head = AppendNode(head, i); //添加9个节点，数据为从1到9
6 }
②.计算双向链表长度？（或者打印）
为了得到双向链表的长度，需要使用right指针进行遍历，直到得到NULL为止。
1 //获取链表的长度
2 int GetLength(DbNode *head) //参数为链表的表头节点
3 {
4 int count = 1;
5 DbNode *pnode = NULL;
6
7 if (head == NULL) //head为NULL表示链表空
8 {
9 return 0;
10 }
11 pnode = head->right;
12 while (pnode != NULL)
13 {
14 pnode = pnode->right; //使用right指针遍历
15 count++; ///// 也可以打印
16 }
17
18 return count;
19 }
③.查找双向链表节点？
使用right指针遍历，直至找到数据为data的节点，如果找到节点，返回节点，否则返回NULL。
1 //查找节点，成功则返回满足条件的节点指针，否则返回NULL
2 DbNode *FindNode(DbNode *head, int data) //参数1是链表的表头节点
3 { //参数2是要查找的节点,其数据为data
4 DbNode *pnode = head;
5
6 if (head == NULL) //链表为空时返回NULL
7 {
8 return NULL;
9 }
10
11 /*找到数据或者到达链表末尾退出while循环*/
12 while (pnode->right != NULL && pnode->data != data)
13 {
14 pnode = pnode->right; //使用right指针遍历
15 }
16
17 //没有找到数据为data的节点，返回NULL
18 if (pnode->right == NULL)
19