19 双向链表

1，创建一个双向链表，并初始化赋值

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 typedef struct Link {
 5     int data;
 6     struct Link* prior;
 7     struct Link* next;
 8 }link;
 9 
10 
11 link* initLink(link* headNode) {
12     headNode = (link*)malloc(sizeof(link)); //头结点
13     headNode->prior = NULL;
14     headNode->next = NULL;
15     headNode->data = -1; //头结点的数据域给值是 -1
16 
17     link* headNode2 = headNode; //复制一个头结点
18 
19     for (int i = 1; i <= 5; i++) {
20         link* new_node= (link*)malloc(sizeof(link));
21         new_node->data = i;
22 
23         new_node->prior = headNode2;
24         headNode2->next = new_node;
25         new_node->next = NULL;
26 
27         headNode2 = new_node;
28     }
29 
30     return headNode;
31 }
32 
33 void showLink(link* headNode) {
34     link* temp = headNode;
35     while (temp!=NULL) {
36         printf("%d  ", temp->data);
37         temp = temp->next;
38     }
39     printf("
");
40 }
41 
42 void main() {
43     link* head_node = NULL; 
44     head_node = initLink(head_node); //获取经过初始化后的双向链表的头结点
45     printf("初始化双向链表是:
");
46     showLink(head_node);
47     printf("链表中第 2个节点的直接前驱是：%d", head_node->next->next->prior->data);
48 }

2，在指定结点前插入一个结点：（这里直接是第三个结点前插入一个结点）

 1 //双向链表在指定结点前插入一个结点，这里在第三个结点前插入
 2 #include <stdio.h>
 3 #include <stdlib.h>
 4 
 5 typedef struct Link {
 6     int data;
 7     struct Link* prior;
 8     struct Link* next;
 9 }link;
10 
11 
12 link* initLink(link* headNode) {
13     headNode = (link*)malloc(sizeof(link)); //头结点
14     headNode->prior = NULL;
15     headNode->next = NULL;
16     headNode->data = -1;
17 
18     link* headNode2 = headNode; //复制一个头结点
19 
20     for (int i = 1; i <= 5; i++) {
21         link* new_node= (link*)malloc(sizeof(link));
22         new_node->data = i;
23 
24         new_node->prior = headNode2;
25         headNode2->next = new_node;
26         new_node->next = NULL;
27 
28         headNode2 = new_node;
29     }
30 
31     return headNode;
32 }
33 
34 void  insertNode(link* headNode,int num) {
35     link* node2 = headNode->next->next;
36     link* node3 = headNode->next->next->next;
37     link* new_node = (link*)malloc(sizeof(link));
38     new_node->data = num;
39 
40     new_node->prior = node2;
41     node2->next = new_node;
42     new_node->next = node3;
43     node3->prior = new_node;
44 }
45 
46 void showLink(link* headNode) {
47     link* temp = headNode;
48     while (temp!=NULL) {
49         printf("%d  ", temp->data);
50         temp = temp->next;
51     }
52     printf("
");
53 }
54 
55 void main() {
56     link* head_node = NULL; 
57     head_node = initLink(head_node); //获取经过初始化后的双向链表的头结点
58     printf("初始化双向链表是:
");
59     showLink(head_node);
60 
61     printf("在第三个结点前插入99后的链表是：
");
62     insertNode(head_node, 99);
63     showLink(head_node);
64 
65 
66     printf("链表中第 3个节点的直接前驱是：%d", head_node->next->next->next->prior->data);
67 }

3，在指定结点后插入一个结点，（这里直接是第一个结点后插入新节点）

 1 //双向链表在指定结点后插入一个结点，这里在第一个结点后插入
 2 #include <stdio.h>
 3 #include <stdlib.h>
 4 
 5 typedef struct Link {
 6     int data;
 7     struct Link* prior;
 8     struct Link* next;
 9 }link;
10 
11 
12 link* initLink(link* headNode) {
13     headNode = (link*)malloc(sizeof(link)); //头结点
14     headNode->prior = NULL;
15     headNode->next = NULL;
16     headNode->data = -1;
17 
18     link* headNode2 = headNode; //复制一个头结点
19 
20     for (int i = 1; i <= 5; i++) {
21         link* new_node = (link*)malloc(sizeof(link));
22         new_node->data = i;
23 
24         new_node->prior = headNode2;
25         headNode2->next = new_node;
26         new_node->next = NULL;
27 
28         headNode2 = new_node;
29     }
30 
31     return headNode;
32 }
33 
34 void  insertNode(link* headNode, int num) {
35 
36     link* node1 = headNode->next;
37     link* node2 = headNode->next->next;
38     link* new_node = (link*)malloc(sizeof(link));
39     new_node->data = num;
40 
41     new_node->prior = node1;
42     node1->next = new_node;
43     new_node->next = node2;
44     node2->prior = new_node;
45 }
46 
47 void showLink(link* headNode) {
48     link* temp = headNode;
49     while (temp != NULL) {
50         printf("%d  ", temp->data);
51         temp = temp->next;
52     }
53     printf("
");
54 }
55 
56 void main() {
57     link* head_node = NULL;
58     head_node = initLink(head_node); //获取经过初始化后的双向链表的头结点
59     printf("初始化双向链表是:
");
60     showLink(head_node);
61 
62     printf("在第一个结点后插入99后的链表是：
");
63     insertNode(head_node, 99);
64     showLink(head_node);
65 
66 
67     printf("链表中第 2个节点的直接前驱是：%d", head_node->next->next->prior->data);
68 }

4，删除指定结点（这里直接删除第2个结点）

 1 //双向链表删除指定结点，这里删除第二个结点
 2 #include <stdio.h>
 3 #include <stdlib.h>
 4 
 5 typedef struct Link {
 6     int data;
 7     struct Link* prior;
 8     struct Link* next;
 9 }link;
10 
11 
12 link* initLink(link* headNode) {
13     headNode = (link*)malloc(sizeof(link)); //头结点
14     headNode->prior = NULL;
15     headNode->next = NULL;
16     headNode->data = -1;
17 
18     link* headNode2 = headNode; //复制一个头结点
19 
20     for (int i = 1; i <= 5; i++) {
21         link* new_node = (link*)malloc(sizeof(link));
22         new_node->data = i;
23 
24         new_node->prior = headNode2;
25         headNode2->next = new_node;
26         new_node->next = NULL;
27 
28         headNode2 = new_node;
29     }
30 
31     return headNode;
32 }
33 
34 void  delNode(link* headNode) {
35 
36     link* node1 = headNode->next;
37     link* node2 = headNode->next->next;
38     link* node3 = headNode->next->next->next;
39    
40     node1->next = node3;
41     node3->prior = node1;
42     free(node2);
43 }
44 
45 void showLink(link* headNode) {
46     link* temp = headNode;
47     while (temp != NULL) {
48         printf("%d  ", temp->data);
49         temp = temp->next;
50     }
51     printf("
");
52 }
53 
54 void main() {
55     link* head_node = NULL;
56     head_node = initLink(head_node); //获取经过初始化后的双向链表的头结点
57     printf("初始化双向链表是:
");
58     showLink(head_node);
59 
60     printf("删除第二个结点后的链表是：
");
61     delNode(head_node);
62     showLink(head_node);
63 
64 
65     printf("链表中第 2个节点的直接前驱是：%d", head_node->next->next->prior->data);
66 }

5，查询指定结点，根据用户的输入值，在链表查找是否存在这个结点，有就返回这个结点的位置，没有就提示没有找到

 1 //双向链表查询指定结点，根据用户输入数据，返回结点位置
 2 #include <stdio.h>
 3 #include <stdlib.h>
 4 
 5 typedef struct Link {
 6     int data;
 7     struct Link* prior;
 8     struct Link* next;
 9 }link;
10 
11 
12 link* initLink(link* headNode) {
13     headNode = (link*)malloc(sizeof(link)); //头结点
14     headNode->prior = NULL;
15     headNode->next = NULL;
16     headNode->data = -1;
17 
18     link* headNode2 = headNode; //复制一个头结点
19 
20     for (int i = 1; i <= 5; i++) {
21         link* new_node = (link*)malloc(sizeof(link));
22         new_node->data = i;
23 
24         new_node->prior = headNode2;
25         headNode2->next = new_node;
26         new_node->next = NULL;
27 
28         headNode2 = new_node;
29     }
30 
31     return headNode;
32 }
33 
34 int  queryNode(link* headNode,int num) {
35     link* tmp = headNode;
36     int count = 0;
37     while (tmp->next != NULL) {
38         if (tmp->data == num) {
39             return count;
40         }
41         count++;
42         tmp = tmp->next;
43     }
44     return -1;
45 }
46 
47 void showLink(link* headNode) {
48     link* temp = headNode;
49     while (temp != NULL) {
50         printf("%d  ", temp->data);
51         temp = temp->next;
52     }
53     printf("
");
54 }
55 
56 void main() {
57     link* head_node = NULL;
58     head_node = initLink(head_node); //获取经过初始化后的双向链表的头结点
59     printf("初始化双向链表是:
");
60     showLink(head_node);
61 
62     int num = 0;
63     printf("请输入你想要查找的结点: ");
64     scanf("%d", &num);
65     int isfind = queryNode(head_node, num);
66     if (isfind != -1) {
67         printf("找到这个结点，是第%d个结点
", isfind);
68     }
69     else {
70         printf("不存在这个结点
");
71     }
72 
73 }