本文實(shí)例為大家分享了c語(yǔ)言實(shí)現(xiàn)通用數(shù)據(jù)結(jié)構(gòu)之通用鏈表的具體代碼，供大家參考，具體內(nèi)容如下
忽然想起來(lái)，大概在兩年之前學(xué)習(xí)C語(yǔ)言的時(shí)候，曾經(jīng)用C語(yǔ)言寫過(guò)一些通用的數(shù)據(jù)結(jié)構(gòu)。主要也就實(shí)現(xiàn)了鏈表、隊(duì)列、椎、HashSet，還有HashMap。當(dāng)時(shí)只是知道標(biāo)準(zhǔn)的C語(yǔ)言中沒(méi)有這方面的類庫(kù)，后來(lái)才知道有很多第三方的類似這樣的類庫(kù)。廢話不多說(shuō)，先把代碼粘過(guò)來(lái)。
下面實(shí)現(xiàn)的是通用鏈表，注意鏈表中只存儲(chǔ)了指針，沒(méi)有儲(chǔ)存實(shí)際的數(shù)據(jù)。
頭文件
|
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
|
/**************************** File myList.h**************************/ #ifndef MYLIST_H_INCLUDED#define MYLIST_H_INCLUDED#include <stdio.h> typedef struct myNode{ void * data; struct myNode *next;} MyNode; typedef struct myList{ MyNode * first; MyNode * last; int count; int (*equal)(void * a, void * b);} MyList; typedef struct myListIterator{ MyNode * p; int count; int allSize;} MyListIterator; //創(chuàng)建鏈表MyList * createMyList(); //創(chuàng)建鏈表，帶有相等參數(shù)，用于查找MyList * createMySearchList(int(*equal)(void * a, void * b)); //釋放鏈表void freeMyList(MyList * list); //插入在尾部void myListInsertDataAtLast(MyList* const list, void* const data); //插入在首部void myListInsertDataAtFirst(MyList * const list, void* const data); //插入void myListInsertDataAt(MyList * const list, void* const data, int index); //刪除在尾部void* myListRemoveDataAtLast(MyList* const list); //刪除在首部void* myListRemoveDataAtFirst(MyList * const list); //刪除void* myListRemoveDataAt(MyList* const list, int index); //刪除對(duì)象,返回是否刪除成功int myListRemoveDataObject(MyList* const list, void * data); //長(zhǎng)度int myListGetSize(const MyList * const list); //打印void myListOutput(const MyList * const list, void(*pt)(const void * const)); //取得數(shù)據(jù)void* myListGetDataAt(const MyList * const list, int index); //取得第一個(gè)數(shù)據(jù)void* myListGetDataAtFirst(const MyList * const list); //取得最后一個(gè)數(shù)據(jù)void* myListGetDataAtLast(const MyList * const list); //查找某個(gè)數(shù)據(jù)的位置,如果equal方法為空，比較地址，否則調(diào)用equal方法//如果不存在返回-1，如果存在，返回出現(xiàn)的第一個(gè)位置int myListFindDataIndex(const MyList * const list, void * data); //創(chuàng)建遍歷器MyListIterator* createMyListIterator(const MyList * const list); //釋放遍歷器void freeMyListIterator(MyListIterator* iterator); //遍歷器是否有下一個(gè)元素int myListIteratorHasNext(const MyListIterator* const iterator); //返回遍歷器的下一個(gè)元素void * myListIteratorNext(MyListIterator* const iterator); #endif // MYLIST_H_INCLUDED |
源文件
|
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
|
/**************************** File myList.c**************************/ #include "myList.h"#include <stdlib.h>//創(chuàng)建鏈表MyList * createMyList(){ MyList * re = (MyList *) malloc(sizeof(MyList)); re->count = 0; re->first = NULL; re->last = NULL; re->equal = NULL; return re;} //釋放鏈表void freeMyList(MyList * list){ MyNode * p; while (list->first) { p = list->first->next; free(list->first); list->first = p; } free(list);} //插入在尾部void myListInsertDataAtLast(MyList * const list, void* const data){ MyNode * node = (MyNode *) malloc(sizeof(MyNode)); node->data = data; node->next = NULL; if (list->count) { list->last->next = node; list->last = node; } else { list->first = node; list->last = node; } (list->count)++;} //插入在首部void myListInsertDataAtFirst(MyList * const list, void* const data){ MyNode * node = (MyNode *) malloc(sizeof(MyNode)); node->data = data; node->next = NULL; if (list->count) { node->next = list->first; list->first = node; } else { list->first = node; list->last = node; } (list->count)++;} //長(zhǎng)度int myListGetSize(const MyList * const list){ return list->count;} //打印void myListOutput(const MyList * const list, void(*pt)(const void * const)){ MyNode * p = list->first; while (p) { (*pt)(p->data); p = p->next; }} //刪除在尾部void* myListRemoveDataAtLast(MyList* const list){ if (list->count == 1) { return myListRemoveDataAtFirst(list); } MyNode * p = list->first; while (p->next != list->last) { p = p->next; } void *re = list->last->data; free(list->last); p->next = NULL; list->last = p; (list->count)--; return re;} //刪除在首部void* myListRemoveDataAtFirst(MyList * const list){ MyNode *p = list->first; list->first = p->next; void * re = p->data; free(p); (list->count)--; if (list->count == 0) { list->last = NULL; } return re;} //插入void myListInsertDataAt(MyList * const list, void* const data, int index){ if (index == 0) { myListInsertDataAtFirst(list, data); return; } if (index == list->count) { myListInsertDataAtLast(list, data); return; } MyNode * node = (MyNode *) malloc(sizeof(MyNode)); node->data = data; node->next = NULL; MyNode * p = list->first; for (int i = 0; i < index - 1; i++) { p = p->next; } node->next = p->next; p->next = node; (list->count)++;} //刪除void* myListRemoveDataAt(MyList* const list, int index){ if (index == 0) { return myListRemoveDataAtFirst(list); } if (index == list->count - 1) { return myListRemoveDataAtLast(list); } MyNode * p = list->first; for (int i = 0; i < index - 1; i++) { p = p->next; } MyNode *tp = p->next; p->next = p->next->next; void * re = tp->data; free(tp); (list->count)--; return re;} //取得數(shù)據(jù)void* myListGetDataAt(const MyList * const list, int index){ if (index == list->count - 1) { return myListGetDataAtLast(list); } MyNode * p = list->first; for (int i = 0; i < index; i++) { p = p->next; } return p->data;} //取得第一個(gè)數(shù)據(jù)void* myListGetDataAtFirst(const MyList * const list){ return list->first->data;} //取得最后一個(gè)數(shù)據(jù)void* myListGetDataAtLast(const MyList * const list){ return list->last->data;} //查找某個(gè)數(shù)據(jù)的位置,如果equal方法為空，比較地址，否則調(diào)用equal方法//如果不存在返回-1，如果存在，返回出現(xiàn)的第一個(gè)位置int myListFindDataIndex(const MyList * const list, void * data){ MyNode * p = list->first; int re = 0; if (list->equal) { while (p) { if (p->data == data || (*(list->equal))(p->data, data)) { return re; } re++; p = p->next; } } else { while (p) { if (p->data == data) { return re; } re++; p = p->next; } } return -1;} //創(chuàng)建鏈表，帶有相等參數(shù)，用于查找MyList * createMySearchList(int(*equal)(void * a, void * b)){ MyList * re = createMyList(); re->equal = equal; return re;} //創(chuàng)建遍歷器MyListIterator* createMyListIterator(const MyList * const list){ MyListIterator * re = (MyListIterator *) malloc(sizeof(MyListIterator)); re->p = list->first; re->allSize = list->count; re->count = 0; return re;} //釋放遍歷器void freeMyListIterator(MyListIterator* iterator){ free(iterator);} //遍歷器是否有下一個(gè)元素int myListIteratorHasNext(const MyListIterator* const iterator){ return iterator->count < iterator->allSize;} //返回遍歷器的下一個(gè)元素void * myListIteratorNext(MyListIterator* const iterator){ void * re = iterator->p->data; iterator->p = iterator->p->next; (iterator->count)++; return re;} //刪除對(duì)象,返回是否刪除成功int myListRemoveDataObject(MyList* const list, void * data){ MyListIterator * it = createMyListIterator(list); int a = 0; while (myListIteratorHasNext(it)) { void * ld = myListIteratorNext(it); if (data == ld || (list->equal != NULL && (*(list->equal))(ld, data))) { a = 1; break; } } if (a) { myListRemoveDataAt(list, it->count - 1); } return a;} |
測(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
|
/**************************** File main.c*** test for MyList**************************/#include <stdio.h>#include <stdlib.h>#include "myList.h" typedef struct a{ int i; char c;} A; void ppt(const void* const p){ A * pp= p; printf("%d(%c) ", pp->i, pp->c);} int main(){ const int S =10; //創(chuàng)建并初始化數(shù)據(jù) A * data= malloc(sizeof(A)*S); for (int i=0; i< S; i++) { data[i].i=i; data[i].c=(char)('A'+0); } //創(chuàng)建鏈表 MyList * list= createMyList(); //測(cè)試三種插入方法 myListInsertDataAtLast( list, &data[0]); myListInsertDataAtFirst( list, &data[4]); myListInsertDataAt(list, &data[1], 1 ); //測(cè)試查找 int index = myListFindDataIndex(list, &data[2]); printf("%d\n", index); index = myListFindDataIndex(list, &data[4]); printf("%d\n", index); //輸出 myListOutput(list, ppt ); puts(""); //測(cè)試使用迭代器輸出 MyListIterator * it = createMyListIterator(list); while(myListIteratorHasNext(it)) { A * pp = myListIteratorNext(it); printf("%d[%c] ", pp->i, pp->c); } puts(""); //釋放迭代器 freeMyListIterator(it); //釋放鏈表 freeMyList(list); //釋放數(shù)據(jù) free(data); return 0;} |
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持服務(wù)器之家。
原文鏈接：https://blog.csdn.net/swwlqw/article/details/22498833
