单链表的增删改查操作详解之C语言版_单链表的删除算法c语言

单链表在应用中经常用到增加新结点、删除结点、修改结点、查找结点等操作，本文针对上述基本操作做了简单汇总，并给出了详细的算法。

一、在单链表中增加结点

在链表中增加新结点是经常要用到的操作，增加新结点大致可以分为在链表末尾增加、在链表头增加、在中间某个位置增加等三种情形。增加新结点也称为插入新结点。链表结点的接头体如下：

typedef  struct  Lnode
{   
	int           data;     //数据域
	struct Lnode  *next;    //指针域
}LNode;
1
2
3
4
5

1.在链表尾插入新结点
假设有单链表如下：

增加元素为3的新结点，得到如下新链表：

算法流程：
1）生成新结点s存储元素3
2）让p指向表头h
3）让p依次后移到链表尾
4）将s链接到p之后
算法：

s = ( LNode* )malloc( sizeof( LNode ) ); 
s->data = 3;	 
s->next = NULL; 
p = h;
while( p->next != NULL )
{
	p = p->next;
	p->next = s;
}
1
2
3
4
5
6
7
8
9

2.在链表头插入新结点
在表头插入新结点比较简单，生成新结点之后挂在表头之后即可。

算法为：

s = ( LNode* )malloc( sizeof( LNode ) ); 
s->data = 3;	 
s->next = h->next; //此部关键，先把s和结点1链接上。
h->next = s;
1
2
3
4

3.在链表中间某个位置插入新结点
已有链表如下:

想在元素为4的结点之前插入新结点s，插入过程为：
1）生成新结点s；
2）引入两个临时指针p和q，p通过遍历指向4的结点，q作为p的直接前驱
3）把新结点s插入到q和p之间

算法实现（只考虑了插值成功未考虑失败）：

key = 4;
s = ( LNode* )malloc( sizeof( LNode ) ); 
s->data = 3;
q = h;
p = q->next;
while( p->data != key )
{
	q = p;
	p = p->next;
}
q->next = s;
s->next = p;
1
2
3
4
5
6
7
8
9
10
11
12

二、在单链表中删除结点

1.删除一个结点

删除元素为3的结点，其算法如下：

key = 3;
q = h;
p = q->next;
while( p != NULL && p->data != key )//当p结点的值不是key，则q和p平行后移，
{
	q = p;           //q先指向p，之后p再后移
	p = p->next;
}
if( p == NULL )
	输出链表中无目标结点
else
	q->next = p->next;
free( p );
1
2
3
4
5
6
7
8
9
10
11
12
13

2.删除与某个元素相同的全部结点

删除链表中元素为3的全部结点，则算法为：

	key = 3;
	q = head;
	p = head->next;
	//定位
	while( p != NULL)
	{
		if( p->data == key )
		{
			q->next = p->next;
			free(p);
			p = q->next;
		}
		else
		{
			q = p;
			p = p->next;
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3.删除单链表中所有相同的结点
删除单链表中所有值重复的结点，使得所有结点的值都不相同。
算法思路：从单链表的第一个结点开始，对每个结点进行检查：检查链表中该结点的所有后继结点，只要有值和该结点的值相同，则删除之；然后检查下一个结点，直到所有的结点都检查。
算法如下：

	ptr = head->next; 
	while( ptr!= NULL)    //检查链表中所有结点 
	{
		q = ptr;     
		p = ptr->next;
		while ( p != NULL )  //检查结点q的所有后继结点p
		{
			if( p->data == ptr->data )
			{
				q->next = p->next;  
				free(p);  
				p  = q->next;              
			}
			else   
            {
				q = p;  
				p = p->next;           
			}
		}//执行完一轮扫描(可以删除一个相同的值的所有结点)，开始下一轮 
		ptr = ptr->next ;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

三、修改某个结点

修改链表中第一个值为3的结点中的值为10。算法如下：

newData = 10;
key = 3;
p = h->next;
while( p != NULL && p->data != key )
	p = p->next;
if( p == NULL )
	输出链表中无目标结点
else
	p->data = newData;
	free( p );
1
2
3
4
5
6
7
8
9
10

四、查找某个结点

在单链表中查找值为2的结点

key = 2;
p = h->next;
while( p != NULL && p->data != key )
	p = p->next;
if( p == NULL )
	输出链表中无目标结点
else
	查找成功
1
2
3
4
5
6
7
8

五、完整的测试代码

1.代码

#include"stdio.h"
#include"malloc.h"
typedef  struct  Lnode
{   
	int           data;     //数据
	struct Lnode  *next;    //指针域
}LNode;
 
LNode *CreateLinkListTail( int a[], int n );
void display( LNode *head );
int SearchNode( LNode *head, int key );
void InsertNodeHead( LNode *head, int key );
void InsertNodeTail( LNode *head, int key );
void InsertNode( LNode *head, int key, int e );
void DeleteNode( LNode *head, int key );
void DeleteSameNode( LNode  *head, int key );
void DeleteAllSameNode( LNode  *head );
void ModifyNode( LNode *head, int key, int newKey );

int main()
{
	int a[] = { 1, 6, 4, 3, 5, 6, 1, 6 };
	int n = 8;
	LNode *head = CreateLinkListTail( a, n );
	display( head );
	int key = 5; 
	InsertNodeHead( head, key );
	display( head );
	InsertNodeTail( head, key );
	display( head );
	int e = 4;
	InsertNode( head, key, e );
	display( head );
	DeleteNode( head, key );
	display( head );
	DeleteSameNode( head, key );
	display( head );
	DeleteAllSameNode( head );
	display( head );

	int loc = SearchNode( head, key );
	if( loc == 0 )
	{
		printf( " 查找 %d 失败！！！\n", key );
	}
	else
	{
		printf( " 查找 %d 成功\n", key ); 
	}
	
	key = 3;
	int newKey = 10;
	ModifyNode( head, key, newKey );
	display( head );
	return 0;
}
LNode *CreateLinkListTail( int a[], int n )
{
	int i;
	LNode *head, *p, *s;
	head = (LNode*)malloc(sizeof(LNode));
	head->next = NULL;
	p = head;
	for( i = 0; i < n; i++ )
	{
		s = (LNode*)malloc(sizeof(LNode));
		s->data = a[i];
		s->next = NULL;
		p->next = s;
		p = s;
	} 
	return head;
}

void display( LNode *head )
{
	LNode *p;
	p = head->next;
	printf( " data in linklist: " );
	while( p != NULL )
	{
		printf( "%5d", p->data );
		p = p->next;
	}
	printf( "\n" );
}

int SearchNode( LNode *head, int key )
{
	int loc = 0;
	LNode  *p;
	p = head->next;
	while( p != NULL )
	{
		loc++;
		if( p->data  == key )
		{
			break;
		}
		p = p->next;
	}
	if( p == NULL )
		loc = 0;
	return loc;
} 

void ModifyNode( LNode *head, int key, int newKey )
{
	LNode  *p;
	p = head->next;
	while( p != NULL && p->data != key )
	{
		p = p->next;
	}
	if( p == NULL )
		printf( "%d 不在链表中\n", key );
	else
	{
		p->data = newKey;
	}
} 

void InsertNodeHead( LNode *head, int key )
{
	LNode *s = (LNode*)malloc(sizeof(LNode));
	s->data = key;
	s->next = head->next;
	head->next = s;
}
void InsertNodeTail( LNode *head, int key )
{
	LNode *p, *s;
	s = (LNode*)malloc(sizeof(LNode));
	s->data = key;
	s->next = NULL;
	p = head;
	while( p->next != NULL )
	{
		p = p->next;
	}
	p->next = s;
}
void InsertNode( LNode  *head, int key, int e )
{
	LNode *p, *q, *s;
	//先定位key所在的节点
	//插入新节点
	q = head; //q是p的直接前驱节点
	p = head->next;
	while( p != NULL )
	{
		if( p->data == e )
		{
			s= ( LNode * )malloc( sizeof( LNode ) );
			s->data = key;
			s->next = p->next;
			p->next = s;
			break;
		}
		q = p;
		p = p->next;
	}
	if( p == NULL )
	{
		s= ( LNode * )malloc( sizeof( LNode ) );
		s->data = e;
		s->next = NULL;
		q->next = s;
	}	
}

void DeleteNode( LNode  *head, int key )
{
	LNode *p, *q;
	q = head;
	p = head->next;
	//定位
	while( p != NULL )
	{
		if( p->data == key )
		{
			q->next = p->next;
			free(p);
			break;
		}
		q = p;
		p = p->next;
	}
}
void DeleteSameNode( LNode  *head, int key )
{
	LNode *p, *q;
	q = head;
	p = head->next;
	//定位
	while( p != NULL)
	{
		if( p->data == key )
		{
			q->next = p->next;
			free(p);
			p = q->next;
		}
		else
		{
			q = p;
			p = p->next;
		}
	}
}

void  DeleteAllSameNode( LNode  *head )
{
	LNode *ptr = head->next, *q, *p; 
	while( ptr!= NULL)    //检查链表中所有结点 
	{
		q = ptr;     
		p = ptr->next;
		while ( p != NULL )  //检查结点q的所有后继结点p
		{
			if( p->data == ptr->data )
			{
				q->next = p->next;  
				free(p);  
				p  = q->next;              
			}
			else   
            {
				q = p;  
				p = p->next;           
			}
		}//执行完一轮扫描(可以删除一个相同的值的所有结点)，开始下一轮 
		ptr = ptr->next ;
	}
}

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

2.测试结果