C语言实现单向链表详解

一,单向链表的简单示意

1
2
3
4
5
6
7
8
头指针-》头节点-》节点-》节点-》NULL

头指针:只保存指向头节点(第一个节点)的指针
节点:数据域和指针域组成
头节点: 数据域不存数据,指针域存指向第一个节点的指针
NULL: 最后一个节点数直接后继指针,则指针为NULL

注意:头指针必须有,而头结点可有可不有,加上头节点有利于处理节点问题

二,实现单向链表的重要几个步骤:

1
2
3
4
5
6
7
8
9
(1)创建节点,并且给当前节点数据结构配置定量的空间大小
malloc反回的是指向该内存地址的指针,其中node 就是我们说的头指针
   ep : struct list *node = malloc(sizeof(struct list));
(2)清节点数据(由于结构体变量在未初始化的时候,数据是脏的)
   ep : memset(node,0,sizeof(struct list));
(3)给节点初始化数据
   ep : node->id = data ; 
(4)将该节点的指针域设置为NULL。这里说明我创建了一个头结点,即同时运用了头指针和头结点。
   ep : node->next = NULL ;

三,具体实现代码如下:

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct slist
{
int id ; //数据区域
struct slist *next ; //指针区域
}L; //定义的链表结构体从命名为 L

//创建一个节点
L *create_node(int data)
{
//给每个节点分配结构体一样的空间大小
//用malloc向计算机申请一块内存,
//并定义一个指向与头节点数据类型相同的指针则定义LinkList L;时,L为链表的头指针。
L *p = (L *)malloc(sizeof(L));
if(NULL == p)
{
printf("malloc error!\n");
return NULL ;
}
//由于结构体在未初始化的时候一样是脏数据,所以要清
memset(p,0,sizeof(L));
//初始化第一个节点
p->id = data ;
//将节点的后继指针设置为NULL
p->next = NULL ;
}

//链表的尾插 *pH 为链表的最后一个指针,*newData 要插入的指针数据
void tail_insert(L *pH, L *newData)
{
//获取当前的位置
L *p = pH ;
//如果当前位置的下一个节点不为空
while(NULL != p->next)
{
//移动到下一个节点
p = p->next ;
}
//如果跳出以上循环,所以已经到了NULL的这个位置
//此时直接把新插入的节点赋值给NULL这个位置
p->next = newData ;
}

//链表的头插
void top_insert(L *pH , L *newData)
{
L *p = pH ;
newData->next = p->next ;
p->next = newData ;
}


//链表的遍历
void Print_node(L *pH)
{
//获取当前的位置
L *p = pH ;
//获取第一个节点的位置
p = p->next ;
//如果当前位置的下一个节点不为空
while(NULL != p->next)
{
//(1)打印节点的数据
printf("id:%d\n",p->id);
//(2)移动到下一个节点,如果条件仍为真,则重复(1),再(2)
p = p->next ;
}
//如果当前位置的下一个节点为空,则打印数据
//说明只有一个节点
printf("id:%d\n",p->id);
}


//删除链表中的节点
int detele_list_node(L * pH , int data)
{
//获取当前头节点的位置
L *p = pH ;
L *prev = NULL;
while(NULL != p->next)
{
//保存当前节点的前一个节点的指针
prev = p ;
//然后让当前的指针继续往后移动
p = p->next ;
//判断,找到了要删除的数据
if(p->id == data)
{
//两种情况,一种是普通节点,还有一种是尾节点
if(p->next != NULL) //普通节点的情况
{
prev->next = p->next ;
free(p);
}
else //尾节点的情况
{
prev->next = NULL ; //将这个尾节点的上一个节点的指针域指向空
free(p);
}
return 0 ;
}
}
printf("没有要删除的节点\n");
return -1 ;
}

int main(int argc , char **argv)
{
//创建第一个节点
int i ;
L *header = create_node(0);
for(i = 1 ; i < 10 ; i++)
{
top_insert(header,create_node(i));
}
Print_node(header);
detele_list_node(header,5);
putchar('\n');
Print_node(header);
return 0 ;
}

//打印的结果:
/*
id:9
id:8
id:7
id:6
id:5
id:4
id:3
id:2
id:1

id:9
id:8
id:7
id:6
id:4
id:3
id:2
id:1
*/

参考:https://blog.csdn.net/morixinguan/article/details/68951912
结构之美:http://www.nowamagic.net/librarys/veda/detail/1805