再识数据结构之双向循环链表

当你想放弃的时候,就想想被别人拒绝的时候你的尴尬和无奈

双向循环链表的基本操作

main.cpp

1
2
3
4
5
6
7
#include "double_circular_list.h"

int main()
{
run();
return 0;
}

double_circular_list.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//
// Created by Gamelife on 2017/4/3.
//

#ifndef DATA_STRUCT_CLION_DOUBLE_CIRCULAR_LIST_H
#define DATA_STRUCT_CLION_DOUBLE_CIRCULAR_LIST_H

struct double_circular_list {
int data;
double_circular_list *prev, *next;
};

// initialize
double_circular_list * initialize(double_circular_list * & end, int length = 10);

// print double circular list
void print(const double_circular_list * head, const double_circular_list * end);

// get length of list
int length(const double_circular_list * head, const double_circular_list * end);

// insert new element
void insert(double_circular_list * & head, double_circular_list * & end, int data = 99, int pos = 0);

// delete an element of list
void delete_ele(double_circular_list * & head, double_circular_list * & end, int pos = 1);

void run();

#endif //DATA_STRUCT_CLION_DOUBLE_CIRCULAR_LIST_H

double_circular_list.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
//
// Created by Gamelife on 2017/4/3.
//

#include <iostream>
#include "double_circular_list.h"

using namespace std;

double_circular_list * initialize(double_circular_list * & end, int length)
{
double_circular_list * head;
head = NULL;

if (length > 0) {
for(int i = 0; i < length; i++) {
double_circular_list * new_ele = new double_circular_list;
new_ele->data = i;
new_ele->prev = new_ele->next = NULL;
if (i == 0) {
head = new_ele;
} else {
end->next = new_ele;
new_ele->prev = end;
}
end = new_ele;
}
end->next = head;
head->prev = end;
}
return head;
}

void print(const double_circular_list * head, const double_circular_list * end)
{
if (head != NULL) {
const double_circular_list * current = head;
int index = 1;
do
{
cout << "index:" << index ++ << ";data:" << current->data << endl;
current = current->next;
} while (current->prev != end);
}
}

int length(const double_circular_list * head, const double_circular_list * end)
{
int index = 0;
if (head != NULL) {
const double_circular_list * current = head;
do
{
++ index;
current = current->next;
} while (current->prev != end);
}
return index;
}

// 插入一个新元素,如果pos == 0,插入成为首元素,否则插入成为第pos+1个元素
void insert(double_circular_list * & head, double_circular_list * & end, int data, int pos)
{
int link_length = length(head, end);
if (pos >= 0 && pos <= link_length) {
double_circular_list * new_ele = new double_circular_list;
new_ele->data = data;
new_ele->next = new_ele->prev = NULL;
if (pos == 0) {
// 插入成为首元素
new_ele->next = head;
new_ele->prev = end;
head->prev = new_ele;
head = new_ele;
end->next = new_ele;
} else if (pos == link_length) {
// 插入成为新的尾元素
new_ele->next = head;
new_ele->prev = end;
end->next = new_ele;
end = new_ele;
head->prev = end;
} else {
double_circular_list * current;
current = NULL;
for (int i = 1; i <= pos; i++) {
if (current == NULL) {
current = head;
} else {
current = current->next;
}
}
if (current != NULL) {
new_ele->next = current->next;
new_ele->prev = current;
current->next = new_ele;
new_ele->next->prev = new_ele;
}
}
}
}

// 删除位置为pos的元素
void delete_ele(double_circular_list * & head, double_circular_list * & end, int pos)
{
int link_length = length(head, end);
double_circular_list * del;
del = NULL;
if (pos >= 1 && pos <= link_length) {
if (pos == 1) {
del = head;
head = head->next;
head->prev = end;
end->next = head;
}
else if (pos == link_length) {
del = end;
end = end->prev;
end->next = head;
head->prev = end;
}
else {
for (int i = 1; i <= pos; i++) {
if (del == NULL) {
del = head;
} else {
del = del->next;
}
}
if (del != NULL) {
del->prev->next = del->next;
del->next->prev = del->prev;
}
}
delete del;
}
}

void run()
{
double_circular_list * end;
end = NULL;
double_circular_list * head = initialize(end);
print(head, end);
cout << "the length of list is " << length(head, end) << endl;
insert(head, end, 99, 4);
delete_ele(head, end, 4);
print(head, end);
}

编译运行

g++ main.cpp double_circular_list.cpp -o main.out