-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathc-stl-list.html
More file actions
584 lines (544 loc) · 19.7 KB
/
c-stl-list.html
File metadata and controls
584 lines (544 loc) · 19.7 KB
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
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
<!DOCTYPE html>
<html lang="zh-CN">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>C语言实现STL：list（双向循环链表） - CoccusQ的博客</title>
<link href="https://cdnjs.cloudflare.com/ajax/libs/prism/1.24.1/themes/prism.min.css" rel="stylesheet">
<link rel="stylesheet" href="style.css">
</head>
<body class="layout-container">
<!-- 导航栏 -->
<nav class="navbar">
<div class="navbar-container">
<a href="https://coccusq.github.io" class="navbar-logo">CoccusQ</a>
<div class="navbar-links">
<a href="https://coccusq.github.io/about">关于本站✓</a>
<a href="https://github.com/CoccusQ/coccusq.github.io">GitHub↗</a>
</div>
</div>
</nav>
<!-- 左侧边栏 -->
<aside class="sidebar-left">
<!-- 左侧导航内容 -->
</aside>
<main class="main-content">
<header class="article-header">
<h1 class="article-title" id="headline">C语言实现STL：list（双向循环链表）</h1>
<div class="article-meta">
By <a href="https://github.com/CoccusQ">CoccusQ</a> · 2025.03.01 Update
</div>
</header>
<!-- 下面这个是占位符，不能去除 -->
<section class="section">
<h2 class="section-title" id="前言">前言</h2>
<p>有了之前使用C语言实现<code>vector</code>的经验，实现<code>list</code>双向循环链表就变得简单了很多，重点不再是使用<code>void*</code>类型实现任意类型数据的存储，而是双向循环链表的设计。</p>
<p>PS：<code>list</code> 的代码其实早在写好<code>vector</code>的当天已经写完，只是等到现在才开始写这篇介绍。</p>
</section>
<section class="section">
<h2 class="section-title" id="代码分析">代码分析</h2>
<p>以下是实现代码：</p>
</section>
<section class="section">
<h2 class="section-title" id=""></h2>
<div class="subsection">
<h3 class="subsection-title">初始化操作</h3>
<pre class="language-c"><code>/*listNode结构体*/
struct listNode {
void* item;
struct listNode* prev;
struct listNode* next;
};
/*创建新结点*/
struct listNode* createListNode(void* item, size_t sizeOfType) {
struct listNode* newNode = (struct listNode*)malloc(sizeof(struct listNode));
if (newNode == NULL) exit(errno);
newNode->item = malloc(sizeOfType);
if (newNode->item == NULL) exit(errno);
if (item != NULL) memcpy(newNode->item, item, sizeOfType);
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
/*list结构体*/
struct list {
struct listNode* head;
struct listNode* tail;
int size;
size_t sizeOfType;
};
/*构造函数，分配初始内存空间*/
void list_init(struct list* L, size_t sizeOfType) {
L->sizeOfType = sizeOfType;
L->head = createListNode(NULL, L->sizeOfType);
L->tail = createListNode(NULL, L->sizeOfType);
L->head->next = L->tail;
L->tail->next = L->head;
L->head->prev = L->tail;
L->tail->prev = L->head;
L->size = 0;
}</code></pre>
<p>在初始化时，就先分配头结点和尾结点的内存空间，在之后的插入删除操作中，头结点和尾结点是始终不存放数据的，这样可能导致了内存空间的浪费，但是能简化插入删除操作，不需要特别判断在头尾插入删除的操作。</p>
</div>
</section>
<section class="section">
<h2 class="section-title" id=""></h2>
<div class="subsection">
<h3 class="subsection-title">插入元素</h3>
<pre class="language-c"><code>/*在头部插入元素*/
void list_push_front(struct list* L, void* item) {
struct listNode* newNode = createListNode(item, L->sizeOfType);
L->head->next->prev = newNode;
newNode->next = L->head->next;
newNode->prev = L->head;
L->head->next = newNode;
L->size++;
}
/*在尾部插入元素*/
void list_push_back(struct list* L, void* item) {
struct listNode* newNode = createListNode(item, L->sizeOfType);
L->tail->prev->next = newNode;
newNode->next = L->tail;
newNode->prev = L->tail->prev;
L->tail->prev = newNode;
L->size++;
}
/*在给定位置插入元素*/
void list_insert(struct list* L, void* item, int index) {
if (index < 0 || index > L->size) return;
if (index == 0) {
list_push_front(L, item);
}
else if (index == L->size) {
list_push_back(L, item);
}
else if (index <= L->size / 2) {
struct listNode* p = L->head;
for (int i = 0; i < index; i++) {
p = p->next;
}
struct listNode* newNode = createListNode(item, L->sizeOfType);
p->next->prev = newNode;
newNode->next = p->next;
newNode->prev = p;
p->next = newNode;
L->size++;
}
else {
struct listNode* p = L->tail;
for (int i = L->size - 1; i > index - 1; i--) {
p = p->prev;
}
struct listNode* newNode = createListNode(item, L->sizeOfType);
p->prev->next = newNode;
newNode->prev = p->prev;
newNode->next = p;
p->prev = newNode;
L->size++;
}
}</code></pre>
</div>
</section>
<section class="section">
<h2 class="section-title" id=""></h2>
<div class="subsection">
<h3 class="subsection-title">删除元素</h3>
<pre class="language-c"><code>/*删除头部元素*/
void list_pop_front(struct list* L) {
struct listNode* toDelete = L->head->next;
L->head->next = toDelete->next;
toDelete->next->prev = L->head;
free(toDelete->item);
free(toDelete);
L->size--;
}
/*删除尾部元素*/
void list_pop_back(struct list* L) {
struct listNode* toDelete = L->tail->prev;
L->tail->prev = toDelete->prev;
toDelete->prev->next = L->tail;
free(toDelete->item);
free(toDelete);
L->size--;
}
/*删除给定位置的元素*/
void list_erase(struct list* L, int index) {
if (index < 0 || index >= L->size) return;
if (index == 0) {
list_pop_front(L);
}
else if (index == L->size - 1) {
list_pop_back(L);
}
else if (index <= L->size / 2) {
struct listNode* p = L->head;
for (int i = 0; i < index; i++) {
p = p->next;
}
struct listNode* toDelete = p->next;
p->next = toDelete->next;
toDelete->next->prev = p;
free(toDelete->item);
free(toDelete);
L->size--;
}
else {
struct listNode* p = L->tail;
for (int i = L->size - 1; i > index; i--) {
p = p->prev;
}
struct listNode* toDelete = p->prev;
p->prev = toDelete->prev;
toDelete->prev->next = p;
free(toDelete->item);
free(toDelete);
L->size--;
}
}</code></pre>
</div>
</section>
<section class="section">
<h2 class="section-title" id=""></h2>
<div class="subsection">
<h3 class="subsection-title">实现元素随机访问</h3>
<pre class="language-c"><code>/*访问头部元素*/
void* list_front(struct list* L) {
return L->head->next->item;
}
/*访问尾部元素*/
void* list_back(struct list* L) {
return L->tail->prev->item;
}
/*随机访问元素*/
void* list_get(struct list* L, int index) {
if (index < 0 || index > L->size - 1) return NULL;
if (index == 0) {
return list_front(L);
}
else if (index == L->size - 1) {
return list_back(L);
}
else if (index <= L->size / 2) {
struct listNode* p = L->head->next;
for (int i = 0; i < index; i++) {
p = p->next;
}
return p->item;
}
else {
struct listNode* p = L->tail->prev;
for (int i = L->size - 1; i > index; i--) {
p = p->prev;
}
return p->item;
}
}</code></pre>
<p>在随机访问元素时，根据索引的位置决定是从头部开始遍历还是从尾部开始遍历，能够在一定程度上减少遍历的时间。</p>
</div>
</section>
<section class="section">
<h2 class="section-title" id=""></h2>
<div class="subsection">
<h3 class="subsection-title">清零和析构操作</h3>
<pre class="language-c"><code>/*清空链表*/
void list_clear(struct list* L) {
struct listNode* p = L->head->next;
while (p != L->tail) {
struct listNode* toDelete = p;
p = p->next;
free(toDelete->item);
free(toDelete);
}
L->tail->prev = L->head;
L->size = 0;
}
/*析构函数，释放动态分配的内存*/
void list_free(struct list* L) {
struct listNode* p = L->head->next;
while (p != L->tail) {
struct listNode* toDelete = p;
p = p->next;
free(toDelete->item);
free(toDelete);
}
free(L->head);
free(L->tail);
}</code></pre>
</div>
</section>
<section class="section">
<h2 class="section-title" id=""></h2>
<div class="subsection">
<h3 class="subsection-title">一些宏定义</h3>
<pre class="language-c"><code>/*简化构造函数的调用*/
#define LIST(type, name) struct list name; list_init(&name, sizeof(type))
#define LIST_GET(type, name, index) *(type*)list_get(&name, index)
#define LIST_FRONT(type, name) *(type*)list_front(&name)
#define LIST_BACK(type, name) *(type*)list_back(&name)</code></pre>
<p>和之前的<code>vector</code>一样，利用宏的替换机制，实现类似于C++模板的编译时替换操作；同时将动态数组的随机访问函数的返回值进行操作，将原来的<code>void*</code>类型依据数据类型转换成数值，便于进行赋值操作。</p>
</div>
</section>
<section class="section">
<h2 class="section-title" id="小结一下">小结一下</h2>
<p>这是C语言实现STL系列的第二个成果，其中的关键技术，也就是实现不同类型数据的存储部分，已经在<code>vector</code>中大致搞清楚了，所以这次的<code>list</code>只是为了完善C语言实现STL的附加产物，这次的主要部分在于双向循环链表的设计与实现。</p>
<p>最后是完整的头文件代码：</p>
</section>
<section class="section">
<h2 class="section-title" id=""></h2>
<div class="subsection">
<h3 class="subsection-title">完整代码</h3>
<pre class="language-c"><code>#ifndef _LIST_H_
#define _LIST_H_
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#define LIST(type, name) struct list name; list_init(&name, sizeof(type))
#define LIST_GET(type, name, index) *(type*)list_get(&name, index)
#define LIST_FRONT(type, name) *(type*)list_front(&name)
#define LIST_BACK(type, name) *(type*)list_back(&name)
struct listNode {
void* item;
struct listNode* prev;
struct listNode* next;
};
struct listNode* createListNode(void* item, size_t sizeOfType) {
struct listNode* newNode = (struct listNode*)malloc(sizeof(struct listNode));
if (newNode == NULL) exit(errno);
newNode->item = malloc(sizeOfType);
if (newNode->item == NULL) exit(errno);
if (item != NULL) memcpy(newNode->item, item, sizeOfType);
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
struct list {
struct listNode* head;
struct listNode* tail;
int size;
size_t sizeOfType;
};
void list_init(struct list* L, size_t sizeOfType) {
L->sizeOfType = sizeOfType;
L->head = createListNode(NULL, L->sizeOfType);
L->tail = createListNode(NULL, L->sizeOfType);
L->head->next = L->tail;
L->tail->next = L->head;
L->head->prev = L->tail;
L->tail->prev = L->head;
L->size = 0;
}
void list_push_front(struct list* L, void* item) {
struct listNode* newNode = createListNode(item, L->sizeOfType);
L->head->next->prev = newNode;
newNode->next = L->head->next;
newNode->prev = L->head;
L->head->next = newNode;
L->size++;
}
void list_push_back(struct list* L, void* item) {
struct listNode* newNode = createListNode(item, L->sizeOfType);
L->tail->prev->next = newNode;
newNode->next = L->tail;
newNode->prev = L->tail->prev;
L->tail->prev = newNode;
L->size++;
}
void list_pop_front(struct list* L) {
struct listNode* toDelete = L->head->next;
L->head->next = toDelete->next;
toDelete->next->prev = L->head;
free(toDelete->item);
free(toDelete);
L->size--;
}
void list_pop_back(struct list* L) {
struct listNode* toDelete = L->tail->prev;
L->tail->prev = toDelete->prev;
toDelete->prev->next = L->tail;
free(toDelete->item);
free(toDelete);
L->size--;
}
void list_insert(struct list* L, void* item, int index) {
if (index < 0 || index > L->size) return;
if (index == 0) {
list_push_front(L, item);
}
else if (index == L->size) {
list_push_back(L, item);
}
else if (index <= L->size / 2) {
struct listNode* p = L->head;
for (int i = 0; i < index; i++) {
p = p->next;
}
struct listNode* newNode = createListNode(item, L->sizeOfType);
p->next->prev = newNode;
newNode->next = p->next;
newNode->prev = p;
p->next = newNode;
L->size++;
}
else {
struct listNode* p = L->tail;
for (int i = L->size - 1; i > index - 1; i--) {
p = p->prev;
}
struct listNode* newNode = createListNode(item, L->sizeOfType);
p->prev->next = newNode;
newNode->prev = p->prev;
newNode->next = p;
p->prev = newNode;
L->size++;
}
}
void list_erase(struct list* L, int index) {
if (index < 0 || index >= L->size) return;
if (index == 0) {
list_pop_front(L);
}
else if (index == L->size - 1) {
list_pop_back(L);
}
else if (index <= L->size / 2) {
struct listNode* p = L->head;
for (int i = 0; i < index; i++) {
p = p->next;
}
struct listNode* toDelete = p->next;
p->next = toDelete->next;
toDelete->next->prev = p;
free(toDelete->item);
free(toDelete);
L->size--;
}
else {
struct listNode* p = L->tail;
for (int i = L->size - 1; i > index; i--) {
p = p->prev;
}
struct listNode* toDelete = p->prev;
p->prev = toDelete->prev;
toDelete->prev->next = p;
free(toDelete->item);
free(toDelete);
L->size--;
}
}
void* list_front(struct list* L) {
return L->head->next->item;
}
void* list_back(struct list* L) {
return L->tail->prev->item;
}
void* list_get(struct list* L, int index) {
if (index < 0 || index > L->size - 1) return NULL;
if (index == 0) {
return list_front(L);
}
else if (index == L->size - 1) {
return list_back(L);
}
else if (index <= L->size / 2) {
struct listNode* p = L->head->next;
for (int i = 0; i < index; i++) {
p = p->next;
}
return p->item;
}
else {
struct listNode* p = L->tail->prev;
for (int i = L->size - 1; i > index; i--) {
p = p->prev;
}
return p->item;
}
}
void list_clear(struct list* L) {
struct listNode* p = L->head->next;
while (p != L->tail) {
struct listNode* toDelete = p;
p = p->next;
free(toDelete->item);
free(toDelete);
}
L->tail->prev = L->head;
L->size = 0;
}
void list_free(struct list* L) {
struct listNode* p = L->head->next;
while (p != L->tail) {
struct listNode* toDelete = p;
p = p->next;
free(toDelete->item);
free(toDelete);
}
free(L->head);
free(L->tail);
}
#endif</code></pre>
</div>
</section>
<!-- 索引部分 -->
<div class="guide-grid">
<article class="guide-card">
<div class="guide-card-left">
<span class="guide-date">Last post</span>
<a href="https://coccusq.github.io/c-stl-vector" class="guide-title-link">
<h2 class="guide-title">« C语言实现STL：vector（动态数组）</h2>
</a>
</div>
</article>
<article class="guide-card">
<div class="guide-card-right">
<span class="guide-date">Next post</span>
<a href="https://coccusq.github.io/build-tools" class="guide-title-link">
<h2 class="guide-title">模板化网页生成工具：MarkdownConverter&BlogGenerator——原理、功能与使用方法详解 »</h2>
</a>
</div>
</article>
</div>
</main>
<!-- 右侧边栏 -->
<aside class="sidebar-right">
<div class="sidebar-header">文档目录</div>
<nav class="sidebar-nav" id="sidebar-nav"></nav>
</aside>
<!-- 页脚内容 -->
<footer class="footer">
<div class="footer-container">
<div class="footer-column">
<h4 class="footer-title">About us</h4>
<div class="footer-links">
<a href="https://coccusq.github.io/about">✒️Learn More</a>
<a href="https://coccusq.github.io/build-tools">🛠️Build-tools</a>
</div>
</div>
<div class="footer-column">
<h4 class="footer-title">Useful Tools</h4>
<div class="footer-links">
<a href="https://chat.deepseek.com">🤖DeepSeek</a>
<a href="https://github.com/cayxc/Mdtht">📑Mdtht</a>
<a href="https://www.emojiall.com">😄EMOJIALL</a>
</div>
</div>
<div class="footer-column">
<h4 class="footer-title">Social</h4>
<div class="footer-links">
<a href="mailto:king_crab_cn@outlook.com">Email</a>
<a href="https://github.com/CoccusQ/coccusq.github.io">GitHub↗</a>
</div>
</div>
</div>
<div class="footer-divider"></div>
<div class="footer-copyright">
<p>© 2025 CoccusQ 🇨🇳. All rights reserved.</p>
</div>
</footer>
<div class="copy-feedback" id="copyFeedback"></div>
<script src="script.js"></script>
<!-- 代码高亮 -->
<script src="https://cdnjs.cloudflare.com/ajax/libs/prism/1.24.1/prism.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/prism/1.24.1/components/prism-c.min.js"></script>
</body>
</html>