Не по теме:
"аттракцион неслыханной щедрости" (с)
llist.h
| C | 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
| /* linked list with qsort function */
#ifndef LLIST_H
#define LLIST_H (1)
/* фнукции конструктора копирования, деструктора,
* обработки и сравнения для данных */
typedef void* (*data_copy_t)(const void*);
typedef void (*data_del_t)(void*);
typedef void (*data_proc_t)(const void*);
typedef int (*data_cmp_t)(const void*, const void*);
/* сам себе список */
typedef struct LLIST llist_t;
/* конструктор списка принимает указатели на конструктор копирования,
* деструктор и сравнение данных */
llist_t * llist_new(data_copy_t, data_del_t, data_cmp_t);
/* деструктор */
void llist_del(llist_t*);
/* добавление элемента в список
* в случае ошибки возвращает -1, при удаче 0 */
int llist_add(llist_t*, const void*);
/* поиск в списке данных по переданному шаблону
* если не найдёт, возвращает 0, найдёт - не 0 */
int llist_contains(llist_t*, const void*);
/* удаление данных по шаблону
* если переданные данные в списке не найдены, возвращает -1
* иначе 0 */
int llist_remove(llist_t*, const void*);
/* заменяет данные, если найдёт, на новые и возвращает 0,
* если не найдёт, возвращает -1 */
int llist_update(llist_t*, const void*, const void*);
/* выполнение переданной функции для каждого элемента списка
* функция должна возвращать void и не должна изменять элементы */
void llist_foreach(llist_t*, data_proc_t);
/* сортировка списка по функции сравнения
* функция должна работать так же, как передаваемая стандартной qsort() */
void llist_sort(llist_t*, data_cmp_t);
/* количество элементов в списке */
int llist_size(llist_t*);
#endif /* LLIST_H */ |
|
llist.c
| C | 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
| #include <stdlib.h>
#include "llist.h"
typedef struct LNODE {
void * data;
struct LNODE * prev;
struct LNODE * next;
} lnode_t;
lnode_t * lnode_new(void * data) {
lnode_t * node = malloc(sizeof(lnode_t));
if ( ! node )
return NULL;
node->data = data;
node->prev = NULL;
node->next = NULL;
return node;
}
void lnode_del(lnode_t * node) {
free(node);
}
void lnode_swap(lnode_t * a, lnode_t * b) {
if ( a != b ) {
void * tmp = a->data;
a->data = b->data;
b->data = tmp;
}
}
void lnode_sort(lnode_t * left, lnode_t * right, int (*cmp)(const void*, const void*)) {
if ( left == right )
return;
else if ( left->next == right ) {
if ( cmp(left->data, right->data) > 0 )
lnode_swap(left, right);
}
else {
lnode_t * last = left;
lnode_t * current = left;
do {
current = current->next;
if ( cmp(current->data, left->data) < 0 ) {
last = last->next;
lnode_swap(current, last);
}
} while ( current != right );
lnode_swap(last, left);
lnode_sort(left, last, cmp);
if ( last != right )
lnode_sort(last->next, right, cmp);
}
}
/******************************************************/
struct LLIST {
lnode_t * head;
lnode_t * tail;
data_copy_t data_copy;
data_del_t data_del;
data_cmp_t data_cmp;
int nodes;
};
llist_t * llist_new(data_copy_t data_copy, data_del_t data_del, data_cmp_t data_cmp) {
llist_t * list = malloc(sizeof(llist_t));
if ( ! list )
return NULL;
list->head = NULL;
list->tail = NULL;
list->data_copy = data_copy;
list->data_del = data_del;
list->data_cmp = data_cmp;
list->nodes = 0;
return list;
}
void llist_del(llist_t * list) {
while ( list->head ) {
list->tail = list->head->next;
list->data_del(list->head->data);
lnode_del(list->head);
list->head = list->tail;
}
free(list);
}
int llist_add(llist_t * list, const void * data) {
lnode_t * node = lnode_new(list->data_copy(data));
if ( ! node )
return -1;
node->prev = list->tail;
if ( ! list->head )
list->head = node;
else
list->tail->next = node;
list->tail = node;
list->nodes += 1;
return 0;
}
lnode_t * llist_find(llist_t * list, const void * data) {
lnode_t * current = list->head;
while ( current ) {
if ( list->data_cmp(current->data, data) == 0 )
break;
current = current->next;
}
return current;
}
int llist_contains(llist_t * list, const void * data) {
return ( llist_find(list, data) ) ? 1 : 0;
}
int llist_remove(llist_t * list, const void * data) {
lnode_t * node = llist_find(list, data);
if ( ! node )
return -1;
else {
if ( node == list->head ) {
list->head = list->head->next;
if ( list->head )
list->head->prev = NULL;
else
list->tail = NULL;
}
else if ( node == list->tail ) {
list->tail = list->tail->prev;
list->tail->next = NULL;
}
else {
node->prev->next = node->next;
node->next->prev = node->prev;
}
list->data_del(node->data);
lnode_del(node);
list->nodes -= 1;
}
return 0;
}
int llist_update(llist_t * list, const void * oldData, const void * newData) {
lnode_t * node = llist_find(list, oldData);
if ( ! node )
return -1;
list->data_del(node->data);
node->data = list->data_copy(newData);
return 0;
}
void llist_foreach(llist_t * list, data_proc_t data_proc) {
lnode_t * current = list->head;
while ( current ) {
data_proc(current->data);
current = current->next;
}
}
void llist_sort(llist_t * list, data_cmp_t data_cmp) {
if ( ! data_cmp )
data_cmp = list->data_cmp;
if ( ! list->nodes )
return;
lnode_sort(list->head, list->tail, data_cmp);
}
int llist_size(llist_t * list) {
return list->nodes;
} |
|
llist_test.c
| C | 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
| #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "llist.h"
#define NAME_LENGTH (32)
#define get_name(s) ( scanf("%31s", (s)) == 1 )
typedef struct DATA {
char name[NAME_LENGTH];
int value;
} data_t;
void * copy_data(const void * dataTemplate) {
void * ptr = malloc(sizeof(data_t));
assert(ptr);
return memcpy(ptr, dataTemplate, sizeof(data_t));
}
void destroy_data(void * dataPtr) {
free(dataPtr);
}
void print_data(const void * ptr) {
data_t * pData = (data_t*)ptr;
printf("%3d\t%s\n", pData->value, pData->name);
}
int compare_data(const void * pA, const void * pB) {
data_t * a = (data_t*)pA;
data_t * b = (data_t*)pB;
int ret = a->value - b->value;
return ( ret ) ? ret : strcmp(a->name, b->name);
}
void print_help(void) {
printf("1 - help\n"
"2 - add value\n"
"3 - delete value\n"
"4 - dump list\n"
"5 - sort list\n"
"6 - find data\n"
"7 - change data\n"
"8 - list size\n"
"0 - quit\n\n"
);
}
void flush_input(void) {
char c;
while ( scanf("%c", &c) == 1 && c != '\n' )
;
}
int fill_data(data_t * pData) {
memset(pData, 0, sizeof(data_t));
printf("Name: ");
if ( ! get_name(pData->name) )
return -1;
printf("Value: ");
if ( scanf("%d", &(pData->value)) != 1 )
return -1;
flush_input();
return 0;
}
int menu(void) {
int ret;
printf("[1 - help] > ");
if ( scanf("%d", &ret) != 1 ) {
flush_input();
return -1;
}
flush_input();
return ret;
}
int main(void) {
int ret, done = 0;
llist_t * list = llist_new(copy_data, destroy_data, compare_data);
assert(list);
while ( ! done ) {
switch ( menu() ) {
case 1:
print_help();
break;
case 2: {
data_t data;
ret = fill_data(&data);
assert(ret == 0);
ret = llist_add(list, &data);
assert(ret == 0);
printf("Ok\n");
break;
}
case 3: {
data_t data;
ret = fill_data(&data);
assert(ret == 0);
ret = llist_remove(list, &data);
if ( ret )
printf("Not in list!\n");
else
printf("Ok\n");
break;
}
case 4:
llist_foreach(list, print_data);
break;
case 5:
llist_sort(list, NULL);
printf("Ok\n");
break;
case 6: {
data_t data;
ret = fill_data(&data);
assert(ret == 0);
printf("%sound.\n", ( llist_contains(list, &data) ) ? "F" : "Not f");
break;
}
case 7: {
data_t oldData, newData;
printf("Old data\n");
ret = fill_data(&oldData);
assert(ret == 0);
printf("New data\n");
ret = fill_data(&newData);
assert(ret == 0);
ret = llist_update(list, &oldData, &newData);
printf("%s\n", ( ret ) ? "Error!\n" : "Ok");
break;
}
case 8:
printf("%d items in list.\n", llist_size(list));
break;
case 0:
done = 1;
break;
default:
printf("Wrong choice!\n");
break;
}
}
llist_del(list);
return 0;
} |
|
1
|
(
(из фильма).
