循环链表设计与API实现
基本概念
循环链表的定义:将单链表中最后一个数据元素的next指针指向第一个元素
循环链表拥有单链表的所有操作
- 创建链表
- 销毁链表
- 获取链表长度
- 清空链表
- 获取第pos个元素操作
- 插入元素到位置pos
- 删除位置pos处的元素
新增功能:游标的定义
在循环链表中可以定义一个“当前”指针,这个指针通常称为游标,可以通过这个游标来遍历链表中的所有元素。
循环链表新操作
将游标重置指向链表中的第一个数据元素
?
1
|
CircleListNode* CircleList_Reset(CircleList* list);
|
获取当前游标指向的数据元素
?
1
|
CircleListNode* CircleList_Current(CircleList* list);
|
将游标移动指向到链表中的下一个数据元素
?
1
|
CircleListNode* CircleList_Next(CircleList* list);
|
直接指定删除链表中的某个数据元素
?
1
2
|
CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node);
// 根据元素的值 删除 元素 pk根据元素的位置 删除 元素
|
最后加了一个循环链表的应用:求解约瑟夫问题
约瑟夫问题-循环链表典型应用
n 个人围成一个圆圈,首先第 1 个人从 1 开始一个人一个人顺时针报数,报到第 m 个人,令其出列。然后再从下一 个人开始从 1 顺时针报数,报到第 m 个人,再令其出列,…,如此下去,求出列顺序。
代码:
?
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
|
// circlelist.h
// 循环链表API声明
#ifndef _CIRCLELIST_H_
#define _CIRCLELIST_H_
typedef void CircleList;
typedef struct _tag_CircleListNode
{
struct _tag_CircleListNode *next;
}CircleListNode;
// 创建链表
CircleList* CircleList_Create();
// 销毁链表
void CircleList_Destroy(CircleList* list);
// 清空链表
void CircleList_Clear(CircleList* list);
// 获取链表的长度
int CircleList_Length(CircleList* list);
// 在pos位置插入结点node
int CircleList_Insert(CircleList* list,CircleListNode* node, int pos);
// 获取pos位置的结点
CircleListNode* CircleList_Get(CircleList* list, int pos);
// 删除pos位置的结点
CircleListNode* CircleList_Delete(CircleList* list, int pos);
// 根据结点的值进行数据删除
CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node);
// 重置游标
CircleListNode* CircleList_Reset(CircleList* list);
// 获取当前游标所指结点
CircleListNode* CircleList_Current(CircleList* list);
// 将原始游标所指结点返回给上层,然后让游标移到下一个结点
CircleListNode* CircleList_Next(CircleList* list);
#endif
|
?
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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
|