Data Structure in C: Singly Linked Lists

Overview

但凡提及Data Structure的学习总是从Single Linked List开始…之前看Data Structures and Algorithms in C++Singly Linked Lists写过一个Cpp版本的,实现的东西比较简单一些。后来有看了Data Structure Using C(一些笔记放在这里), 这书写的十分细致,而且代码比较好看懂(虽然偶尔Bug比较多…)。但是两本书写的东西都有些局限的地方,比如都只是“面向”Int类型给出的实现。这在Master Algorithms with C得到很好的实现,因为它把链表存储的对象换成了generic pointer,这就使得可以进行任何类型数据的存储。

下面首先结合前面两本书给出Int类型的实现,后给出generic pointer的实现。

Code

Int type version

singlelinkedlist.h

注意,下面的两个自定义的typeNode就是我们的链表元素,或者叫节点。List就是链表。

这里我们实现了大部分可以想到的操作…包括增[4]删[4]改[1]查[1],创建,打印,排序[Buble sort]

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

//
// Created by shensir on 19-2-14.
//

#ifndef TEST_SINGLELINKEDLIST_H
#define TEST_SINGLELINKEDLIST_H

// Node's data structure
typedef struct Node{
int data;
struct Node *next;
}Node;

// linked list's data structure
typedef struct List{
Node *head;
int length;
}List;

// create a single linked list with length n
void list_create(List *list, int n);
// print a single linked list
void list_print(List *list);
// add a Node to a list
void node_insert_begin(List *list, Node *new_element);
void node_insert_end(List *list, Node *new_element);
void node_insert_after(List *list, int given_node_data, Node *new_element);
void node_insert_before(List *list, int given_node_data, Node *new_element);
// delete Node in a list
void node_delete_begin(List *list);
void node_delete_end(List *list);
void node_delete_given_node(List *list, int data);
void list_delete_all(List *list);
// change node's data in a list
void node_change(List *list, int data, int new_data);
// search a number in a list
int node_search(List *list, int data);
// sort the list(increasing)
void list_sorted(List *list);
// test function
void run();
#endif //TEST_SINGLELINKEDLIST_H

main.c

几点注意:

1.为说明起见,这里没有处理重复数据的情况,重复情况下仅仅对第一个数据进行对应处理
2.多次出现的temp变量,其作用就是一个工具变量,用于定位与释放内存
3.在链表中,next的使用“代替”了数组中根据index的循环
4.我们必须注意对空表的处理,使用if或assert来控制这一情况

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

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include "singlelinkedlist.h"

/*StepINT SINGLE LINKED LIST*/
int main(){
run();
return 0;
}

void list_create(List *list, int n)
{
int i, data;
Node *new_element;
for(i=0; i<n; i++){
new_element = (Node*)malloc(sizeof(Node));
new_element->next = NULL;
printf("Enter the data: ");
scanf("%d", &data);
new_element->data = data;
node_insert_end(list, new_element);
}
}


void list_print(List *list){
if(list->length == 0)
printf("Empty List!");
else{
Node *temp;
temp = list->head;
while(temp!=NULL){
printf("%d ", temp->data);
temp = temp->next;
}
}
printf("\n");
}

// add a Node to a list
void node_insert_begin(List *list, Node * new_element){
// 从用户输入新元素的数据
if(new_element == NULL){
int data;
printf("Enter the data: ");
scanf("%d", &data);
new_element = (Node*)malloc(sizeof(Node));
new_element->next = NULL;
new_element->data = data;
}
// empty list or not
if(list->length == 0)
list->head = new_element;
else{
new_element->next = list->head;
list->head = new_element;
}
list->length++;
}

void node_insert_end(List *list, Node *new_element)
{
if(new_element == NULL){
int data;
printf("Enter the data: ");
scanf("%d", &data);
new_element = (Node*)malloc(sizeof(Node));
new_element->next = NULL;
new_element->data = data;
}
// empty list or not
if(list->length == 0)
list->head = new_element;
else{
// 找到最后的元素
int i;
Node *temp;
temp = list->head;
for(i=0; i < list->length-1; i++)
temp = temp->next;
// 确保找到的是尾节点
assert(temp->next == NULL);
temp->next = new_element;
}
list->length++;
}

void node_insert_after(List *list, int given_node_data, Node *new_element){
assert(list->length > 0);
if(new_element == NULL){
int data;
printf("Enter the data of new node: ");
scanf("%d", &data);
new_element = (Node*)malloc(sizeof(Node));
new_element->data = data;
new_element->next = NULL;
}
Node *temp;
temp = list->head;
while(1){
if(temp->data == given_node_data)
break;
temp = temp->next;
}
new_element->next = temp->next;
temp->next = new_element;
list->length++;
}

void node_insert_before(List *list, int given_node_data, Node *new_element) {
assert(list->length > 0);
if(new_element == NULL){
int data;
printf("Enter the data of new node: ");
scanf("%d", &data);
new_element = (Node*)malloc(sizeof(Node));
new_element->data = data;
new_element->next = NULL;
}
// before head or not
if(list->head->data == given_node_data)
node_insert_begin(list, new_element);
else{
Node *temp;
temp = list->head;
while(1){
if(temp->next->data == given_node_data)
break;
temp = temp->next;
}
new_element->next = temp->next;
temp->next = new_element;
}
list->length++;
}

// delete Node in a list
void node_delete_begin(List *list){
assert(list->length > 0);
Node*temp;
temp = list->head;
list->head = list->head->next;
free(temp);
list->length--;
}

void node_delete_end(List *list){
assert(list->length > 0);
// 仅有一个节点
if(list->length == 1){
free(list->head);
list->head = NULL;
}
else{
// 两个节点及以上
// 获取倒数第二个节点
Node*prev;
prev = list->head;
while(1){
if(prev->next->next == NULL)
break;
prev = prev->next;
}
free(prev->next);
prev->next = NULL;
}
list->length--;
}

void node_delete_given_node(List *list, int data){
assert(list->length > 0);
// if the node at 1st
if(list->head->data == data){
printf("Delete from head!\n");
node_delete_begin(list);
}
else{
// two nodes or more
// find the node before the given node
Node*prev, *node;
prev = list->head;
while(1){
if(prev->next->data == data)
break;
prev = prev->next;
}
node = prev->next;
prev->next = node->next;
free(node);
list->length--;
}
}


void list_delete_all(List *list){
Node*temp;
while(list->length > 0){
temp = list->head;
list->head = list->head->next;
free(temp);
list->length--;
}
}

// change node's data in a list(for simple: only change the first one)
void node_change(List *list, int data, int new_data){
assert(list->length > 0);
Node *temp;
temp = list->head;
while(1){
if(temp->data == data){
temp->data = new_data;
break;
}
temp = temp->next;
}
}

// search a number in a list
int node_search(List *list, int data){
assert(list->length > 0);
Node *temp;
temp = list->head;
int count = 0;
while(temp->next!=NULL){
if(temp->data == data)
count++;
temp = temp->next;
}
if(count>0){
printf("Get %d '%d'!", count, data);
return count;
}
else{
printf("There is not a %d\n", data);
return 0;
}
}
// sort the list(increasing)
void list_sorted(List *list){
if(list->length == 0){
printf("Empty list!");
return;
}
Node *ptr1, *lptr;
int temp, swapped;
do{
swapped = 0;
ptr1 = list->head;
lptr = NULL;
while (ptr1->next != lptr)
{
if (ptr1->data > ptr1->next->data)
{
temp = ptr1->data;
ptr1->data = ptr1->next->data;
ptr1->next->data = temp;
swapped = 1;
}
ptr1 = ptr1->next;
}
lptr = ptr1;
}
while (swapped);
}

void run(){
List * list;
list = (List *)malloc(sizeof(List));
list->head = NULL;
list->length = 0;
// 控制下面循环的选项; the length var
int option, n;
// 要用到的变量
int given_node_data, old_data, new_data;
do{
printf("*****MAIN MENU *****\n");
printf("1: Create a list\n");
printf("2: Display a list\n");
printf("3: Add a node at the beginning\n");
printf("4: Add a node at the end\n");
printf("5: Add a node before a given node\n");
printf("6: Add a node after a given node\n");
printf("7: Delete a node from the beginning\n");
printf("8: Delete a node from the end\n");
printf("9: Delete a given node\n");
printf("10: Delete the entire list\n");
printf("11: Change the number\n");
printf("12: Search a number\n");
printf("13: Sort the list\n");
printf("14: EXIT\n");
// 输入选项
printf("Enter your option: ");
scanf("%d", &option);
switch(option)
{
case 1:
printf("Enter the length of the list: ");
scanf("%d", &n);
list_create(list, n);
break;
case 2:
list_print(list);
break;
case 3:
// 我们从输入来进行新增元素的初始化
// 所以这里写为NULL,而非一个Node
// 下同
node_insert_begin(list, NULL);
break;
case 4:
node_insert_end(list, NULL);
break;
case 5:
printf("Enter the given node data(we will insert node before it): ");
scanf("%d", &given_node_data);
node_insert_before(list, given_node_data, NULL);
break;
case 6:
printf("Enter the given node data(we will insert node after it): ");
scanf("%d", &given_node_data);
node_insert_after(list, given_node_data, NULL);
break;
case 7:
node_delete_begin(list);
break;
case 8:
node_delete_end(list);
break;
case 9:
// 同插入时一样,我们从用户输入来
// 指定要删除的元素,故写为NULL
printf("Enter the given node data: ");
scanf("%d", &given_node_data);
node_delete_given_node(list, given_node_data);
break;
case 10:
list_delete_all(list);
break;
case 11:
printf("Change data.\nold data: ");
scanf("%d", &old_data);
printf("new data: ");
scanf("%d", &new_data);
node_change(list, old_data, new_data);
break;
case 12:
printf("Enter data to be searched: ");
scanf("%d", &given_node_data);
node_search(list, given_node_data);
break;
case 13:
list_sorted(list);
break;
}
}while(option != 14);
}


Generic pointer version

暂略.

Supplement

在CLion中写C的项目,直接把Cmake改一行比较好用。把CMAKE_CXX_FLAGS所在行改为set(CMAKE_C_FLAGS "${CMAKE_C_FLAGS} -Wall -Werror"),参考这里

Reference

Data Structure Using C
Master Algorithms with C
Data Structures and Algorithms in C++

本文标题:Data Structure in C: Singly Linked Lists

文章作者:不秩稚童

发布时间:2019年02月14日 - 16:12:36

最后更新:2019年02月14日 - 16:35:41

原始链接:http://datahonor.com/2019/02/14/Data-Structure-in-C-Singly-Linked-Lists/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

击蒙御寇