aboutsummaryrefslogtreecommitdiff
path: root/dlist.c
diff options
context:
space:
mode:
authorThomas Schmucker <ts@its1.de>2022-04-09 09:43:53 +0200
committerThomas Schmucker <ts@its1.de>2022-04-09 09:43:53 +0200
commit154874afda4a8df885e51c01f7681f04fb0b8e61 (patch)
tree274817eb2793584b0e3d856de5504a614f2b4e89 /dlist.c
parent2863f4f1d2a6a6a8704454824d6c291d2e0d4b5c (diff)
downloaddata-structures-154874afda4a8df885e51c01f7681f04fb0b8e61.tar.gz
data-structures-154874afda4a8df885e51c01f7681f04fb0b8e61.tar.bz2
data-structures-154874afda4a8df885e51c01f7681f04fb0b8e61.zip
neue Verzeichnisstruktur
Diffstat (limited to 'dlist.c')
-rw-r--r--dlist.c504
1 files changed, 0 insertions, 504 deletions
diff --git a/dlist.c b/dlist.c
deleted file mode 100644
index 55e42d7..0000000
--- a/dlist.c
+++ /dev/null
@@ -1,504 +0,0 @@
1/* dlist -- double linked list */
2
3/* Standard C */
4#include <assert.h>
5#include <stdbool.h>
6#include <stdio.h>
7#include <stdlib.h>
8#include <time.h>
9
10/* Project */
11#include "util.h"
12
13/* --8<-- dlist_type */
14typedef int T;
15
16struct dlist {
17 struct dlist_element *head, *tail;
18};
19
20struct dlist_element {
21 struct dlist_element *prev, *next;
22 T data;
23};
24/* -->8-- */
25
26/* --8<-- dlist_init */
27void
28dlist_init(struct dlist *dlist)
29{
30 dlist->head = NULL;
31 dlist->tail = NULL;
32}
33/* -->8-- */
34
35/* --8<-- dlist_empty */
36bool
37dlist_empty(struct dlist *dlist)
38{
39 return dlist->head == NULL;
40}
41/* -->8-- */
42
43/* --8<-- dlist_create_element */
44static struct dlist_element *
45create_element(T data)
46{
47 struct dlist_element *element;
48
49 element = malloc(sizeof *element);
50 if ( element ) {
51 element->data = data;
52 }
53
54 return element;
55}
56/* -->8-- */
57
58/* --8<-- dlist_push_front */
59struct dlist_element *
60dlist_push_front(struct dlist *dlist, T data)
61{
62 struct dlist_element *element;
63
64 element = create_element(data);
65 if ( element ) {
66 element->prev = NULL; /* Vorgänger ist in jedem Fall NULL */
67
68 if ( dlist_empty(dlist) ) {
69 element->next = NULL;
70 dlist->tail = element;
71 }
72 else {
73 element->next = dlist->head;
74 element->next->prev = element;
75 }
76
77 dlist->head = element; /* Neues Element ist in jedem Fall der neue Anfang! */
78 }
79 else
80 ERROR("out of memory");
81
82 return element;
83}
84/* -->8-- */
85
86/* --8<-- dlist_push_back */
87struct dlist_element *
88dlist_push_back(struct dlist *dlist, T data)
89{
90 struct dlist_element *element;
91
92 element = create_element(data);
93 if ( element ) {
94 element->next = NULL; /* Nachfolger ist in jedem Fall NULL */
95
96 if ( dlist_empty(dlist) ) {
97 element->prev = NULL;
98 dlist->head = element;
99 }
100 else {
101 element->prev = dlist->tail;
102 element->prev->next = element;
103 }
104
105 dlist->tail = element; /* Neues Element ist in jedem Fall das neue Ende! */
106 }
107 else
108 ERROR("out of memory");
109
110 return element;
111}
112/* -->8-- */
113
114/* --8<-- dlist_pop_front */
115bool
116dlist_pop_front(struct dlist *dlist, T *data)
117{
118 if ( dlist->head ) {
119 struct dlist_element *element = dlist->head;
120
121 dlist->head = element->next;
122
123 if ( dlist->head == NULL )
124 dlist->tail = NULL;
125 else
126 element->next->prev = NULL;
127
128 if ( data ) {
129 *data = element->data;
130 }
131 free(element);
132
133 return true;
134 }
135 else
136 return false;
137}
138/* -->8-- */
139
140/* --8<-- dlist_pop_back */
141bool
142dlist_pop_back(struct dlist *dlist, T *data)
143{
144 if ( dlist->head ) {
145 struct dlist_element *element = dlist->tail;
146
147 dlist->tail = element->prev;
148
149 if ( dlist->tail == NULL )
150 dlist->head = NULL;
151 else
152 element->prev->next = NULL;
153
154 if ( data ) {
155 *data = element->data;
156 }
157 free(element);
158
159 return true;
160 }
161 else
162 return false;
163}
164/* -->8-- */
165
166/* --8<-- dlist_insert_next */
167struct dlist_element *
168dlist_insert_next(struct dlist *dlist, struct dlist_element *element, T data)
169{
170 struct dlist_element *new_element;
171
172 new_element = create_element(data);
173 if ( new_element ) {
174 if ( dlist->head == NULL ) {
175 dlist->head = new_element;
176 dlist->head->prev = NULL;
177 dlist->head->next = NULL;
178 dlist->tail = new_element;
179 }
180 else {
181 new_element->next = element->next;
182 new_element->prev = element;
183
184 if ( element->next == NULL )
185 dlist->tail = new_element;
186 else
187 element->next->prev = new_element;
188
189 element->next = new_element;
190 }
191 }
192 else
193 ERROR("out of memory");
194
195 return new_element;
196}
197/* -->8-- */
198
199/* --8<-- dlist_insert_prev */
200struct dlist_element *
201dlist_insert_prev(struct dlist *dlist, struct dlist_element *element, T data)
202{
203 struct dlist_element *new_element;
204
205 new_element = create_element(data);
206 if ( new_element ) {
207 if ( dlist->head == NULL ) {
208 dlist->head = new_element;
209 dlist->head->prev = NULL;
210 dlist->head->next = NULL;
211 dlist->tail = new_element;
212 }
213 else {
214 new_element->next = element;
215 new_element->prev = element->prev;
216
217 if ( element->prev == NULL )
218 dlist->head = new_element;
219 else
220 element->prev->next = new_element;
221
222 element->prev = new_element;
223 }
224 }
225 else
226 ERROR("out of memory");
227
228 return new_element;
229}
230/* -->8-- */
231
232/* --8<-- dlist_remove */
233void
234dlist_remove(struct dlist *dlist, struct dlist_element *element)
235{
236 if ( element == dlist->head ) {
237 dlist->head = element->next;
238
239 if ( dlist->head == NULL )
240 dlist->tail = NULL;
241 else
242 element->next->prev = NULL;
243 }
244 else {
245 element->prev->next = element->next;
246
247 if ( element->next == NULL )
248 dlist->tail = element->prev;
249 else
250 element->next->prev = element->prev;
251 }
252
253 free(element);
254}
255/* -->8-- */
256
257/* --8<-- dlist_free */
258void
259dlist_free(struct dlist *dlist)
260{
261 struct dlist_element *elem, *next;
262
263 for ( elem = dlist->head; elem; elem = next ) {
264 next = elem->next;
265 free(elem);
266 }
267
268 dlist_init(dlist);
269}
270/* -->8-- */
271
272void
273dlist_apply_rev(struct dlist *dlist, void (*visit)(T data, void *cl), void *cl)
274{
275 for ( struct dlist_element *elem = dlist->tail; elem; elem = elem->prev ) {
276 visit(elem->data, cl);
277 }
278}
279
280void
281print_list(const char *msg, struct dlist *dlist)
282{
283 printf("%s:", msg);
284
285 for ( struct dlist_element *elem = dlist->head; elem; elem = elem->next )
286 printf(" %d", elem->data);
287
288 putchar('\n');
289}
290
291void
292print_list_rev(const char *msg, struct dlist *dlist)
293{
294 printf("%s:", msg);
295
296 for ( struct dlist_element *elem = dlist->tail; elem; elem = elem->prev )
297 printf(" %d", elem->data);
298
299 putchar('\n');
300}
301
302void
303remove_if(struct dlist *list)
304{
305 struct dlist_element *elem, *next;
306
307 for ( elem = list->head; elem; elem = next ) {
308 next = elem->next;
309
310 if ( (elem->data & 1) == 1 ) {
311 dlist_remove(list, elem);
312 }
313 }
314}
315
316/* --8<-- dlist_merge */
317struct dlist *
318dlist_merge(struct dlist *list1, struct dlist *list2)
319{
320 struct dlist_element *head = NULL,
321 *cur = NULL,
322 *e1 = list1->head,
323 *e2 = list2->head;
324
325 while ( e1 && e2 ) // Solange in e1 UND e2 Elemente sind...
326 {
327 if ( e1->data < e2->data ) {
328 e1->prev = cur;
329 if ( cur )
330 cur->next = e1;
331 else
332 head = e1;
333 cur = e1;
334 e1 = e1->next;
335 }
336 else {
337 e2->prev = cur;
338 if ( cur )
339 cur->next = e2;
340 else
341 head = e2;
342 cur = e2;
343 e2 = e2->next;
344 }
345 }
346
347 if ( e1 ) // in e1 sind noch Elemente vorhanden!
348 {
349 assert(e2 == NULL);
350
351 e1->prev = cur;
352 if ( cur )
353 cur->next = e1;
354 else
355 head = e1;
356
357 // list1->tail zeigt bereits auf das letzte Element in list1
358 }
359 else /* if ( e2 ) */
360 {
361 assert(e1 == NULL);
362 assert(e2);
363
364 e2->prev = cur;
365 if ( cur )
366 cur->next = e2;
367 else
368 head = e2;
369
370 list1->tail = list2->tail; // list2->tail ist das Ende der Liste
371 }
372
373 // Kopf neu setzen...
374 list1->head = head;
375
376 // Liste2 ist leer
377 list2->head = NULL;
378 list2->tail = NULL;
379
380 // Zeiger auf Liste1 zurückliefern
381 return list1;
382}
383/* -->8-- */
384
385/* --8<-- dlist_sort */
386struct dlist *
387dlist_sort(struct dlist *list)
388{
389 if ( list->head == NULL || list->head->next == NULL ) // Leer oder nur ein Element? => Fertig
390 return list;
391
392 struct dlist_element *slow = list->head,
393 *fast = list->head->next;
394
395 while ( fast && fast->next )
396 slow = slow->next, fast = fast->next->next;
397
398 struct dlist list1 = { .head = list->head, .tail = slow },
399 list2 = { .head = slow->next, .tail = list->tail };
400
401 list1.tail->next = list2.head->prev = NULL;
402
403 dlist_merge(dlist_sort(&list1), dlist_sort(&list2));
404
405 list->head = list1.head;
406 list->tail = list1.tail;
407
408 return list;
409}
410/* -->8-- */
411
412void
413merge_test(void)
414{
415 struct dlist l1, l2;
416
417 dlist_init(&l1);
418 dlist_init(&l2);
419
420 dlist_push_back(&l1, 7);
421 dlist_push_back(&l1, 10);
422 dlist_push_back(&l1, 11);
423 dlist_push_back(&l1, 19);
424 dlist_push_back(&l1, 23);
425
426 dlist_push_back(&l2, 4);
427 dlist_push_back(&l2, 14);
428 dlist_push_back(&l2, 15);
429
430 struct dlist *ptr;
431 ptr = dlist_merge(&l1, &l2);
432
433 struct dlist_element *cur;
434 for ( cur = ptr->head; cur; cur = cur->next ) {
435 if ( cur->prev )
436 printf("%4d", cur->prev->data);
437 else
438 printf("xxx ");
439 printf("%4d", cur->data);
440 if ( cur->next )
441 printf("%4d", cur->next->data);
442 else
443 printf(" xxx");
444
445 puts("");
446 }
447
448 dlist_free(&l1);
449 dlist_free(&l2);
450}
451
452void
453ls()
454{
455 struct dlist list;
456
457 dlist_init(&list);
458
459 for ( int i = 0; i != 30000000; ++i )
460 dlist_insert_prev(&list, list.tail, rand() % 9999);
461
462 //print_list("Unsortiert:", &list);
463 printf("start\n");
464 clock_t start = clock();
465 dlist_sort(&list);
466 clock_t ende = clock();
467
468 printf("Dauer: %.3fsec\n", ((double) ende - start) / CLOCKS_PER_SEC);
469 //print_list("Sortiert:", &list);
470 //print_list_rev("Sortiert:", &list);
471
472 dlist_free(&list);
473}
474
475int
476main(void)
477{
478 ls();
479
480#if 0
481 merge_test();
482#endif
483
484#if 0
485 struct dlist list;
486
487 dlist_init(&list);
488
489 for ( int i = 0; i != 10; ++i )
490 dlist_insert_prev(&list, list.tail, i);
491
492 print_list("Ausgabe: ", &list);
493
494 remove_if(&list);
495
496 print_list("Ausgabe: ", &list);
497
498 dlist_free(&list);
499
500 ls();
501
502 return EXIT_SUCCESS;
503#endif
504}