C语言：数据结构--单向链表详解_单向链表c语言

单向链表

（1）单向链表的基本了解

先是定义一个单向链表的节点结构体：

typedef struct Node{
    int data;
    struct Node *pNext;
}NODE, *PNODE;
1
2
3
4

那么整个结构体可以抽象成下图：

其中，一个空链表就只有一个头节点（在本篇文章中头节点用于数据的存储，只用于作为索引，当然，你也可以将它和普通节点一样存放数据等）：

而n个节点的链表如下（这里n=3）：

（2）增删改查

① 增——在尾部增加节点

② 增——在中间插入一个节点

③ 增——在链表头部插入一个节点

与“在中间插入一个节点”同样原理，所以这里省略过程：

④ 删——删除尾部节点

⑤ 删——删除中间节点

⑥ 删——删除第一个节点

⑦ 改

略。

⑧ 查

略。

（3）单向链表程序示例

注：程序仅作参考，不考虑严谨性。

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


typedef struct Node{
    int data;
    struct Node *pNext;
}NODE, *PNODE;


PNODE create_List(void);
int destory_list(PNODE pHead);
int list_is_empty(PNODE pHead);
int list_length(PNODE pHead);

int insert_node_to_list_head(PNODE pHead, PNODE node);
int insert_node_to_list_by_position(PNODE pHead, int position, PNODE node);
int insert_node_to_list_tail(PNODE pHead, PNODE node);

void remove_list_first_node(PNODE pHead);
void remove_list_node_by_position(PNODE pHead, int position);
void remove_list_tail_node(PNODE pHead);

int midify_list_node(PNODE pHead, int position, int val);
void show_all_list_node(PNODE pHead);


int main()
{
	PNODE pHead = NULL; /* 先定义一个头结点 */
	NODE tmpNode;
	int ret, pos, val;

	pHead = create_List();
	if(pHead == NULL){
		printf("创建链表失败！\n"); 
		return -1;
	}

	char ch;
	while(1){
		printf("------------------------------------\n"
			   "a) 添加节点到链表头部\n"
			   "b) 添加节点到链表尾部\n"
			   "c) 添加节点到链表指定位置\n"
			   "d) 删除链表第一个节点\n"
			   "e) 删除链表最后一个节点\n"
			   "f) 删除链表指定位置的节点\n"
			   "g) 修改节点内容\n"
			   "h) 查看链表长度\n"
			   "i) 查看链表内容\n"
			   "z) 退出\n"
			   "请输入你的选择: "
			);
		scanf("%c", &ch); getchar();

		switch(ch){
			case 'a':
				printf("请输入新增节点的值："); 
				scanf("%d", &tmpNode.data); getchar();
				ret = insert_node_to_list_head(pHead, &tmpNode);
				if(ret){
					printf("插入节点失败！\n");
					break;
				}
				printf("操作成功！\n");
				break;
			case 'b':
				printf("请输入新增节点的值："); 
				scanf("%d", &tmpNode.data); getchar();
				ret = insert_node_to_list_tail(pHead, &tmpNode);
				if(ret){
					printf("插入节点失败！\n");
					break;
				}
				printf("操作成功！\n");
				break;
			case 'c':
				printf("请输入节点插入的位置："); 
				scanf("%d", &pos);
				printf("请输入新增节点的值："); 
				scanf("%d", &tmpNode.data); getchar();
				ret = insert_node_to_list_by_position(pHead, pos, &tmpNode);
				if(ret){
					printf("插入节点失败！\n");
					break;
				}
				printf("操作成功！\n");
				break;
			case 'd':
				remove_list_first_node(pHead);
				printf("操作成功！\n");
				break;
			case 'e':
				remove_list_tail_node(pHead);
				printf("操作成功！\n");
				break;
			case 'f':
				printf("请输入需要删除的节点位置："); 
				scanf("%d", &pos); getchar();
				remove_list_node_by_position(pHead, pos);
				break;
			case 'g':
				printf("请输入需要修改的节点位置："); 
				scanf("%d", &pos); getchar();
				printf("请输入修改后的值："); 
				scanf("%d", &val); getchar();
				midify_list_node(pHead, pos, val);
				break;
			case 'h':
				printf("链表长度：%d\n", list_length(pHead)); 
				break;
			case 'i':
				show_all_list_node(pHead);
				break;
			case 'z':
				destory_list(pHead);
				return 0;
			default:
				printf("输入有误！请重新输入...\n");
				break;
		}
		
	}

	return 0;
} 


PNODE create_List(void)
{
	PNODE tmp = NULL;
	
	tmp = (PNODE)malloc(sizeof(NODE));
	if(tmp == NULL){
		printf("分配节点内存失败！\n"); 
		return NULL;
	}
	
	memset(tmp, 0, sizeof(*tmp));
	return tmp;
}


int destory_list(PNODE pHead)
{
	/* 将"第一个"释放掉，释放掉之后又生成新的"第1个" */ 
	while(pHead->pNext){
		remove_list_first_node(pHead);
	}
	
	/* 头节点也要释放掉 */
	free(pHead);
}


int list_is_empty(PNODE pHead)
{
	if(pHead->pNext)
		return 0;
	else
		return 1;
}


int list_length(PNODE pHead)
{
	PNODE tmp = pHead;
	int length = 0;
	
	while(tmp->pNext){
		length++;
		tmp = tmp->pNext;
	}
	return length;
}



int insert_node_to_list_tail(PNODE pHead, PNODE pNode)
{
	PNODE tmp = pHead;
	
	/* 找到尾节点 */
	while(tmp->pNext){
		tmp = tmp->pNext;
	}
	
	/* 在堆里分配一块内存，用于存放新节点 */
	PNODE pNew = (PNODE)malloc(sizeof(NODE));
	memcpy(pNew, pNode, sizeof(NODE));
	
	/* 原来的尾节点指向新节点 */
	tmp->pNext = pNew;
	
	/* 确保新的尾节点的指针为NULL */
	pNew->pNext = NULL;
	
	return 0; 
}


int insert_node_to_list_by_position(PNODE pHead, int position, PNODE pNode)
{
	PNODE tmp = pHead;
	int i = 0;
	
	/* 找出需要插入的前一个位置 */ 
	while(tmp->pNext && i < position-1){
		tmp = tmp->pNext;
		i++;
	}
	
	/* 如果链表没有那么长则返回 */
	if(tmp->pNext == NULL || i < position-1){
		printf("链表长度不够!\n"); 
		return -1; 
	}
	
	PNODE pNew = (PNODE)malloc(sizeof(NODE));
	memcpy(pNew, pNode, sizeof(NODE));
	
	pNew->pNext =  tmp->pNext;
	tmp->pNext = pNew;
	
	return 0;
}


int insert_node_to_list_head(PNODE pHead, PNODE pNode)
{
#if 1	
	PNODE pNew = (PNODE)malloc(sizeof(NODE));
	memcpy(pNew, pNode, sizeof(NODE));

	pNew->pNext =  pHead->pNext;
	pHead->pNext = pNew;
	
	return 0; 
#else
	return remove_list_node_by_position(pHead, 1, pNode);
#endif
}


void remove_list_first_node(PNODE pHead)
{
	/* 如果是空的链表则不需要操作 */ 
	if(list_is_empty(pHead)){
		printf("空链表，无需操作！\n");
		return;
	}
	
	/* 将头节点指向第1个节点先保存起来 */
	PNODE tmp = pHead->pNext;
	
	/* 将头节点指向第1个节点的下一个节点 */
	pHead->pNext = pHead->pNext->pNext;
	
	/* 释放刚才保存的tmp节点 */
	free(tmp);
}


void remove_list_node_by_position(PNODE pHead, int position)
{
	PNODE tmp = pHead;
	PNODE tofree = NULL;
	int i = 0;
	
	/* 如果是空的链表则不需要操作 */ 
	if(list_is_empty(pHead)){
		printf("空链表，无需操作！\n");
		return;
	}
	
	/* 找出需要删除的前一个位置 */ 
	while(tmp->pNext && i < position-1){
		tmp = tmp->pNext;
		i++;
	}
	
	/* 如果链表没有那么长则返回 */
	if(tmp->pNext == NULL || i < position-1){
		printf("链表长度不够!\n"); 
		return; 
	}
	
	/* 将要释放的节点先保存起来 */
	tofree = tmp->pNext;
	
	/* 指向下一个节点的下一个节点 */
	tmp->pNext = tmp->pNext->pNext;
	
	/* 释放资源 */
	free(tofree);
}


void remove_list_tail_node(PNODE pHead)
{
	int i = 0;
	int length = list_length(pHead);
	PNODE tmp = pHead->pNext;

	if(length >= 2){
		/* 先找到倒数第2个节点 */
		while(tmp->pNext && i < length-2){
			tmp = tmp->pNext;
			i++;
		}
		
		/* 将倒数第1个节点释放 */
		free(tmp->pNext);
		
		/* 将倒数第2个节点的指针指向NULL */
		tmp->pNext = NULL;
	}
	else{
		/* 只有一个节点；同时也能处理空链表 */ 
		remove_list_first_node(pHead);
	}

}


int midify_list_node(PNODE pHead, int position, int val)
{
	int i = 0;
	PNODE tmp = pHead;
	
	if(position > list_length(pHead)){
		printf("链表长度不够!\n"); 
		return -1; 
	}
	
	/* 找出需要修改的位置 */
	while(i < position){
		tmp = tmp->pNext;
		i++;
	}
	
	tmp->data = val;
	
	return 0;
}


void show_all_list_node(PNODE pHead)
{
	/* 从第一个节点开始而不是头节点 */ 
	PNODE tmp = pHead->pNext;
	
	printf("链表数据如下: \n");
	while(tmp != NULL){
		printf("%d\n", tmp->data); 	/* 打印节点的数据 */ 
		tmp = tmp->pNext; 			/* 切换到下一个节点 */
	}
}
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