直接贴代码:

  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
#pragma once

#include <stdio.h>
#include <stdlib.h>

/**
 * 单链表练习
 * -std=c99
 */

typedef int type;

struct SingleListNode {
    type data;
    struct SingleListNode *next;
};

struct SingleList {
    unsigned int size;
    struct SingleListNode *head;
};

/**
 * 函数声明
 */
struct SingleList* SingleListCreate();
void SingleListPushBack(struct SingleList *list, type data);
void SingleListPushFront(struct SingleList *list, type data);
struct SingleListNode* SingleListPopBack(struct SingleList *list);
struct SingleListNode* SingleListPopFront(struct SingleList *list);
struct SingleListNode* SingleListAt(struct SingleList *list, unsigned int index);
void SingleListInsert(struct SingleList *list, unsigned int pos, type data);
void SingleListRemove(struct SingleList *list, unsigned int pos);
void SingleListReverse(struct SingleList *list);
type* SingleListToArray(struct SingleList *list);
struct SingleList* SingleListFromArray(type* array, unsigned int len);
struct SingleList* SingleListSub(struct SingleList *list, unsigned int bpos, unsigned int epos);
void SingleListErase(struct SingleList *list);
void SingleListPrintNode(unsigned int index, struct SingleListNode *node);
void SingleListPrintList(struct SingleList *list);

/**
 * 创建并初始化一个链表
 */
struct SingleList* SingleListCreate() {
    struct SingleList *list = (struct SingleList*) malloc(sizeof(struct SingleList));
    list->head = NULL;
    list->size = 0;
    return list;
}

/**
 * 尾部追加一个节点
 */
void SingleListPushBack(struct SingleList *list, type data) {
    struct SingleListNode *node = (struct SingleListNode*)malloc(sizeof(struct SingleListNode));
    node->next = NULL;
    node->data = data;
    if (list->head == NULL) {
        list->head = node;
    } else {
        struct SingleListNode *temp = list->head;
        while(temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = node;
    }
    ++list->size;
}

/**
 * 头部增加一个节点
 */
void SingleListPushFront(struct SingleList *list, type data) {
    struct SingleListNode *node = (struct SingleListNode*)malloc(sizeof(struct SingleListNode));
    node->next = list->head;
    node->data = data;
    list->head = node;
    ++list->size;
}

/**
 * 尾部弹出一个节点,节点使用完后一定要free掉
 */
struct SingleListNode* SingleListPopBack(struct SingleList *list) {
    if (list->head == NULL) {
        return NULL;
    }
    struct SingleListNode *node = list->head;
    if (node->next == NULL) {
        list->head = NULL;
        --list->size;
        return node;
    }
    while (node->next->next != NULL) {
        node = node->next;
    }
    struct SingleListNode *temp = node->next;
    node->next = NULL;
    --list->size;
    temp->next = NULL;
    return temp;
}

/**
 * 头部弹出一个节点,节点使用完后一定要free掉
 */
struct SingleListNode* SingleListPopFront(struct SingleList *list) {
    if (list->head == NULL) {
        return NULL;
    }
    struct SingleListNode *node = list->head;
    list->head = list->head->next;
    --list->size;
    node->next = NULL;
    return node;
}

/**
 * 按索引获取某个节点
 */
struct SingleListNode* SingleListAt(struct SingleList *list, unsigned int index) {
    if (list->head == NULL || index >= list->size) {
        printf("ERROR: index out of list! [%d > %d]\n", index, list->size);
        return NULL;
    }
    struct SingleListNode *node = list->head;
    for (unsigned int i = 0; i < index; i++) {
        node = node->next;
    }
    return node;
}

/**
 * 指定位置插入数据
 * 思路:找到指定位置的前一个节点的后面加入节点
 */
void SingleListInsert(struct SingleList *list, unsigned int pos, type data) {
    if (pos > list->size) {
        printf("ERROR: index out of list! [%d > %d]\n", pos, list->size);
        return;
    }
    if (pos == 0) {
        SingleListPushFront(list, data);
        return;
    }
    struct SingleListNode *temp = SingleListAt(list, pos - 1);
    struct SingleListNode *node = (struct SingleListNode*)malloc(sizeof(struct SingleListNode));
    node->data = data;
    node->next = temp->next;
    temp->next = node;
    ++list->size;
}

/**
 * 移除指定位置的节点
 * 思路:找到指定位置的前一个节点指向后一个节点
 * TODO: 有BUG!
 */
void SingleListRemove(struct SingleList *list, unsigned int pos) {
    if (pos > list->size) {
        printf("ERROR: index out of list! [%d > %d]\n", pos, list->size);
        return;
    }
    struct SingleListNode *node;
    if (pos == 0) {
        node = SingleListPopFront(list);
        free(node);
        return;
    }
    if (pos == list->size - 1) {
        node = SingleListPopBack(list);
        free(node);
        return;
    }
    node = SingleListAt(list, pos - 1);
    struct SingleListNode *temp = node->next;
    temp->next = NULL;
    free(temp);
    node->next = node->next->next;
    --list->size;
}

/**
 * 反转链表
 * 思路:头插法,新开一个临时链表,将节点从老链表中移除依次插入新链表的头部
 */
void SingleListReverse(struct SingleList *list) {
    if (list->head == NULL || list->head->next == NULL) {
        return;
    }
    struct SingleList *tempList = SingleListCreate();
    struct SingleListNode *node = SingleListPopFront(list);
    while(node != NULL) {
        node->next = tempList->head;
        tempList->head = node;
        ++tempList->size;
        node = SingleListPopFront(list);
    }
    list->head = tempList->head;
    list->size = tempList->size;
    tempList->head = NULL;
    free(tempList);
}

/**
 * 链表转数组
 * 数组用完记得free掉!
 */
type* SingleListToArray(struct SingleList *list) {
    type *array = (type*)malloc(sizeof(type) * list->size);
    struct SingleListNode *node = list->head;
    for (unsigned int i = 0; i < list->size && node != NULL; i++) {
        array[i] = node->data;
        node = node->next;
    }
    return array;
}

/**
 * 数组转链表
 * 用完记得free掉!
 */
struct SingleList* SingleListFromArray(type* array, unsigned int len) {
    if (array == NULL) {
        return NULL;
    }
    struct SingleList *list = SingleListCreate();
    for (unsigned int i = 0; i < len; i++) {
        SingleListPushBack(list, array[i]);
    }
    return list;
}

/**
 * 截取子链表
 * 用完记得free掉!
 * 前闭后开区间
 */
struct SingleList* SingleListSub(struct SingleList *list, unsigned int bpos, unsigned int epos) {
    if (bpos > epos) {
        unsigned int tempInt = bpos;
        bpos = epos;
        epos = tempInt;
    }
    if (epos >= list->size) {
        printf("ERROR: index out of list! [%d > %d]\n", epos, list->size);
        return NULL;
    }
    struct SingleList *subList = SingleListCreate();
    struct SingleListNode *node = list->head;
    for (unsigned int i = 0; i < bpos; i++) {
        node = node->next;
    }
    for (unsigned int i = bpos; i < epos; i++) {
        SingleListPushBack(subList, node->data);
        node = node->next;
    }
    return subList;
}

/**
 * 清空链表
 */
void SingleListErase(struct SingleList *list) {
    while (list->head != NULL) {
        struct SingleListNode *node = list->head;
        list->head = list->head->next;
        node->next = NULL;
        free(node);
        --list->size;
    }
}

/**
 * 调测用,打印节点
 */
void SingleListPrintNode(unsigned int index, struct SingleListNode *node) {
    printf("%03d\taddr=%p\tnext=%p\tval=%d\n", index, node, node->next, node->data);
}

/**
 * 调测用,打印链表
 */
void SingleListPrintList(struct SingleList *list) {
    struct SingleListNode *temp = list->head;
    for(unsigned int i = 0; i < list->size && temp != NULL; temp = temp->next, ++i) {
        SingleListPrintNode(i, temp);
    }
    printf("list->size = %d\n", list->size);
}


void test() {
    printf("--PushFront--------------\n");
    struct SingleList *list = SingleListCreate();
    for (int i = 10; i < 20; i++) {
        SingleListPushFront(list, i);
    }
    SingleListPrintList(list);
    printf("--PopFront---------------\n");
    struct SingleListNode *node = NULL;
    node = SingleListPopFront(list);
    if (node != NULL) {
        SingleListPrintNode(0, node);
        free(node);
    }
    printf("--PopBack----------------\n");
    node = SingleListPopBack(list);
    if (node != NULL) {
        SingleListPrintNode(0, node);
        free(node);
    }
    printf("--At---------------------\n");
    for (unsigned int i = 0; i < list->size; i++) {
        SingleListPrintNode(i, SingleListAt(list, i));
    }
    printf("--Insert-----------------\n");
    SingleListInsert(list, 0, 22);
    SingleListInsert(list, 1, 23);
    SingleListInsert(list, list->size, 24);
    SingleListPrintList(list);
    printf("--Remove-----------------\n");
    SingleListRemove(list, 0);
    //SingleListRemove(list, 2);
    SingleListPrintList(list);
    printf("--Reverse----------------\n");
    SingleListReverse(list);
    SingleListPrintList(list);
    printf("--Sub--------------------\n");
    struct SingleList *subList = SingleListSub(list, 4, 18);
    if (subList != NULL) {
        SingleListPrintList(subList);
        SingleListErase(subList);
        free(subList);
    }
    printf("--ToArray----------------\n");
    type *arr = SingleListToArray(list);
    for (unsigned int i = 0; i < list->size; i++) {
        printf("%03d\t%d\n", i, arr[i]);
    }
    free(arr);
    printf("--FromArray--------------\n");
    type *arr2 = (type*)malloc(sizeof(type) * 4);
    for (int i = 0; i < 4; i++) {
        arr2[i] = 30 + i;
    }
    struct SingleList *newList = SingleListFromArray(arr2, 4);
    SingleListPrintList(newList);
    SingleListErase(newList);
    free(newList);
    printf("--Erase------------------\n");
    SingleListErase(list);
    SingleListPrintList(list);
}