链表最终章双向链表及其应用

1
typedef int Element;
2
typedef struct _node {
3
Element val;
4
struct _node *next;
5
struct _node *prev;
6
} DNode, DList;
7

8
/* 使用一个带头节点的双向循环链表，头节点让用户来管理，提供初始化接口 */
9
void initDList(DList *header);
10
void releaseDList(DList *header);
11

12
// 实现头插、尾插
13
void insertDListHeader(DList *header, Element val);
14
void insertDListRear(DList *header, Element val);
15
// 显示链表
16
void showDList(const DList *header);
17
// 删除一个元素
18
void delDList(DList *header, Element e);

1
//next是已知的待插入位置节点的下一个节点；
2
//prev是已知的待插入节点的上一个节点（前置节点）；
3

4
//插入
5
static void addDNode(DNode *new_node, DNode *prev, DNode *next) {
6
next->prev = new_node;//待插入节点下一个节点的上一个节点是新节点；
7
new_node->next = next;//新节点的下一个是上一个节点；
8
new_node->prev = prev;新节点上一个是前置节点
9
prev->next = new_node;前置节点下一个是新节点
10
}
11

12
//删除
13
static void delDNode(DNode *prev, DNode *next) {
14
next->prev = prev;//某节点下一个节点的前一个是某节点上一个节点；
15
prev->next = next;//某节点上一个节点的下一个是某节点下一个节点；
16
}

1
#ifndef DOUBLE_LIST_H
2
#define DOUBLE_LIST_H
3

4
typedef int Element;
5
typedef struct _node {
6
Element val;
7
struct _node *next;
8
struct _node *prev;
9
} DNode, DList;
10

11
/* 使用一个带头节点的双向循环链表，头节点让用户来管理，提供初始化接口 */
12
void initDList(DList *header);
13
void releaseDList(DList *header);
14

15
// 实现头插、尾插
16
void insertDListHeader(DList *header, Element val);
17
void insertDListRear(DList *header, Element val);
18
// 显示链表
19
void showDList(const DList *header);
20
// 删除一个元素
21
void delDList(DList *header, Element e);
22

23
#endif //DOUBLE_LIST_H

1
#include "doubleList.h"//doubleList.h文件封装的函数名
2
#include
3
#include
4

5
static void addDNode(DNode *new_node, DNode *prev, DNode *next) {
6
next->prev = new_node;
7
new_node->next = next;
8
new_node->prev = prev;
9
prev->next = new_node;
10
}
11

12
static void delDNode(DNode *prev, DNode *next) {
13
next->prev = prev;
14
prev->next = next;
15
}
16

17
void initDList(DList* header) {
18
header->val = 0;
19
header->next = header->prev = header;
20
}
21

22
void releaseDList(DList* header) {
23
DNode *pos = header->next;
24
DNode *tmp = NULL;
25
while (pos != header) {
26
tmp = pos;
27
delDNode(pos->prev, pos->next);
28
pos = pos->next;
29
free(tmp);
30
--header->val;
31
}
32
}
33

34
void insertDListHeader(DList* header, Element val) {
35
DNode *new_node = malloc(sizeof(DNode));
36
new_node->val = val;
37
addDNode(new_node, header, header->next);
38
++header->val;
39
}
40

41
void insertDListRear(DList* header, Element val) {
42
DNode *new_node = malloc(sizeof(DNode));
43
new_node->val = val;
44
addDNode(new_node, header->prev, header);
45
++header->val;
46
}
47

48
void showDList(const DList* header) {
49
DNode *pos = header->next;
50
printf("show: ");
51
while (pos != header) {
52
printf("\t%d", pos->val);
53
pos = pos->next;
54
}
55
printf("\n");
56
}
57

58
void delDList(DList* header, Element e) {
59
// 1. 找到这个元素，就可以删除，不需要再找到前置节点
60
DNode *pos = header->next;
61
while (pos != header && pos->val != e) {
62
pos = pos->next;
63
}
64
// 2. 找到没有？
65
if (pos != header) { // 找到
66
delDNode(pos->prev, pos->next);
67
pos->next = pos->prev = NULL;
68
free(pos);
69
--header->val;
70
} else {
71
printf("Not find %d element!\n", e);
72
}
73
}

1
#include
2
#include "doubleList.h"
3

4
DList stu_table;
5

6
int main() {
7
initDList(&stu_table);
8

9
for (int i = 0; i < 5; ++i) {
10
// insertDListHeader(&stu_table, i + 100);
11
insertDListRear(&stu_table, i + 100);
12
}
13
insertDListHeader(&stu_table, 60);
14
insertDListHeader(&stu_table, 80);
15
showDList(&stu_table);
16
printf("====================\n");
17
delDList(&stu_table, 102);
18
showDList(&stu_table);
19
releaseDList(&stu_table);
20
printf("num: %d\n", stu_table.val);
21
showDList(&stu_table);
22
return 0;
23
}