数据结构(3) - 双向链表
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。https://img2022.cnblogs.com/blog/1173820/202206/1173820-20220625141807347-732191168.jpg
代码如下：
double-list.c
1 /**
2* C data structure double linked list example.
3*
4* License - MIT.
5 */
6
7 #include "double-list.h"
8
9
10 /**
11* doulist_empty - Determine if the list is empty.
12 */
13 bool doulist_empty(LPDOUBLELIST lpHead)
14 {
15 return (lpHead == lpHead->next);
16 }
17
18
19 /**
20* doulist_show - Display list data.
21 */
22 int doulist_show(LPDOUBLELIST lpHead)
23 {
24 LPDOUBLELIST tmp;
25
26 for (tmp = lpHead->next; tmp != lpHead; tmp = tmp->next)
27 printf("%d ", tmp->data);
28
29 printf("\n");
30
31 return 0;
32 }
33
34
35 /**
36* doulist_insert - Add the specified data at specified node next location.
37 */
38 int doulist_insert(LPDOUBLELIST lpHead, LPDOUBLELIST lpNode)
39 {
40 lpNode->next = lpHead->next;
41 lpHead->next->prev= lpNode;
42 lpNode->prev = lpHead;
43 lpHead->next = lpNode;
44
45 return 0;
46 }
47
48
49 /**
50* doulist_insert_tail - Insert data to list tail.
51 */
52 int doulist_insert_tail(LPDOUBLELIST lpHead, LPDOUBLELIST lpNode)
53 {
54 lpNode->prev = lpHead->prev;
55 lpHead->prev->next= lpNode;
56 lpNode->next = lpHead;
57 lpHead->prev = lpNode;
58
59 return 0;
60 }
61
62
63 /**
64* doulist_del - Deletes the specified data by specified node next location.
65 */
66 int doulist_del(LPDOUBLELIST lpNode)
67 {
68 lpNode->prev->next = lpNode->next;
69 lpNode->next->prev = lpNode->prev;
70
71 return 0;
72 }
73
74
75 /**
76* doulist_init - Initialize double linked list.
77 */
78 int doulist_init(LPDOUBLELIST *lpHead)
79 {
80 *lpHead = (LPDOUBLELIST) malloc(sizeof(DOUBLELIST));
81 if (NULL == *lpHead) {
82 return -1;
83 }
84
85 (*lpHead)->next = *lpHead;
86 (*lpHead)->prev = *lpHead;
87
88 return 0;
89 }
90
91
92 /**
93* doulist_clear - clear double linked list.
94 */
95 int doulist_clear(LPDOUBLELIST lpHead)
96 {
97 LPDOUBLELIST tmp;
98
99 if (!doulist_empty(lpHead)) {
100 for (tmp = lpHead->next; tmp != lpHead; tmp = tmp->next) {
101 doulist_del(tmp);
102 free(tmp);
103 }
104 }
105
106 tmp = NULL;
107
108 free(lpHead);
109 lpHead = NULL;
110
111 return 0;
112 }
double-list.h
1 /**
2* C data structure double linked list example.
3*
4* License - MIT.
5 */
6
7 #ifndef __DOUBLE_LIST_H__
8 #define __DOUBLE_LIST_H__
9
10
11 #include <stdio.h>
12 #include <stdlib.h>
13 #include <stdbool.h>
14
15 typedef struct _DOUBLELIST{
16 int data;
17 struct _DOUBLELIST *prev, *next;
18 } DOUBLELIST, *LPDOUBLELIST;
19
20
21 bool doulist_empty (LPDOUBLELIST lpHead);
22 int doulist_show (LPDOUBLELIST lpHead);
23 int doulist_insert (LPDOUBLELIST lpHead, LPDOUBLELIST lpNode);
24 int doulist_insert_tail (LPDOUBLELIST lpHead, LPDOUBLELIST lpNode);
25 int doulist_del (LPDOUBLELIST lpNode);
26 int doulist_init (LPDOUBLELIST *lpHead);
27 int doulist_clear (LPDOUBLELIST lpHead);
28
29
30 #endif /* __DOUBLE_LIST_H__ */
main.c
1 /**
2* C data structure double linked list example.
3*
4* License - MIT.
5 */
6
7 #include <stdio.h>
8
9 #include "double-list.h"
10
11
12 #define MAX_TEST_NUM 10
13
14
15 /**
16* test_sort - Sort the data.
17 */
18 int test_sort(LPDOUBLELIST lpHead)
19 {
20 LPDOUBLELIST pos, tmp;
21
22 pos = lpHead->prev;
23
24 while (pos != lpHead)
25 {
26 if (1 == (pos->data % 2)) {
27 pos = pos->prev;
28 }
29 else {
30 tmp = pos;
31 pos = pos->prev;
32
33 doulist_del(tmp);
34 doulist_insert_tail(lpHead, tmp);
35 }
36 }
37
38 return 0;
39 }
40
41
42 /**
43* test_create - Create single list example.
44 */
45 int test_create(LPDOUBLELIST lpHead)
46 {
47 int i;
48 LPDOUBLELIST newNode;
49
50 for (i = 0; i < MAX_TEST_NUM; i++) {
51 newNode = (LPDOUBLELIST) malloc(sizeof(DOUBLELIST));
52 if (NULL == newNode) {
53 return -1;
54 }
55
56 newNode->data = i + 1;
57 doulist_insert_tail(lpHead, newNode);
58 }
59
60 return 0;
61 }
62
63
64 /**
65* Main function.
66 */
67 int main(void)
68 {
69 LPDOUBLELIST lphead = NULL;
70
71 doulist_init(&lphead);
72
73 test_create(lphead);
74 doulist_show(lphead);
75
76 test_sort(lphead);
77 doulist_show(lphead);
78
79 doulist_clear(lphead);
80
81 return 0;
82 }
Makefile
1 # Makefile
2 CC = gcc
3 CFLAGS = -Wall -g -O0
4
5 SRC = main.c double-list.c
6
7 OBJ = doulist-test
8
9 $(OBJ) : $(SRC)
10 $(CC) $(CFLAGS) -o $@ $^
11
12 clean:
13 $(RM) $(OBJ) *.o *.*.sw?
完整代码请参考Github: [Link]
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]