抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

线性表的链式存储-单链表

数据结构

发布于：2018年12月15日

次浏览

单链表操作

  • 单链表的创建（尾插法、头插法）
  • 单链表的查找操作
  • 单链表的删除操作
  • 单链表的逆置操作(使用头插法)
  • 单链表表长的计算
  • 打印单链表

单链表的创建

头插法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
forward_list* creat_3()    //头插法
{
    forward_list *head,*s;
	int num;
	head = NULL;//链表初始状态为空
	while(scanf("%d",&num) && num)
	{
		s = (forward_list*)malloc(sizeof(forward_list));
		s->data = num;

		s->next = head;

		head = s;//将新结点插入到表头
	}
	return head;
}

尾插法（不含头结点）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//尾插法建表
forward_list* creat_1()
{
    forward_list *head=NULL;//头指针，初始状态为空
	forward_list *rear=NULL;//尾指针，初始状态为空
	int num;
	forward_list *s;
	while(scanf("%d",&num) == 1 && num)//输入0结束
	{
		s = (forward_list*)malloc(sizeof(forward_list));

		s->data = num;
		if(head == NULL)//将新节点加入空表
	        head = s;
	    else            //原表非空，将新节点链接到表尾之后
	        rear->next = s;
		rear = s;//尾指针指向新的表尾
    }
    if(rear!= NULL)//对于非空表，将尾结点的下一个结点置空
	    rear->next = NULL;

	return head;
}

尾插法（含头结点）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//尾插法建表,包含头结点
forward_list* creat_2()
{
	forward_list *s;
	forward_list *head, *rear;
	int num;

	head = (forward_list*)malloc(sizeof(forward_list));
	rear = head;

	while(scanf("%d",&num)==1 && num)
	{
		s = (forward_list*)malloc(sizeof(forward_list));

		s->data = num;
	    rear->next = s;
		rear = s;//表指针指向新的表尾
	}
	rear->next = NULL;

	return head;
}

单链表的查找操作

按值查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void search_1(forward_list *s, int x)
{
	forward_list *p;
	p = s;
	while(p != NULL)
	{
		if(p->data == x)
		{
		    printf("\nthe value : %d is exist !\n",x);
		    return ;
		}
		p = p->next;
	}
	printf("\nthe value : %d is not fonud !\n",x);
}

按值查找（包含头结点）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void search_2(forward_list *s, int x)//带头节点
{
	forward_list *p;
	p = s->next;//emmmm
	while(p != NULL)
	{
		if(p->data == x)
		{
		    printf("\nthe value : %d is exist !\n",x);
		    return ;
		}
		p = p->next;
	}
	printf("\nthe value : %d is not fonud !\n",x);
}

单链表的删除操作

按给定结点的位置删除（带头结点）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void delete_1(forward_list *head,int i)        //删除第i个节点(单链表包含头节点)
{
	int j=0;
	forward_list *p,*q;
	p=head;
	j=0;
	while((p->next!=NULL)&&(j<i-1))
	{
		p=p->next;
		j++;
	}
	if(p->next!=NULL)
	{
		q=p->next;
		p->next=p->next->next;
		free(q);
	}
	else
		printf("illegal delete position,delete failed!");
}

按照指定值删除结点(不带头结点)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void forward_list_delete_1(forward_list *s,int x)//删除链表（不带头节点）中指定值的元素
{
    forward_list *p;
    forward_list *temp;//用来存放被删除元素的前一个结点
	p = s;
	if(x == p->data)
	    free(p);

	temp = p;
	p = p->next;
    while(p != NULL)
	{
	    if(p->data == x)
		{
            temp->next = p->next;
            free(p);
            return ;
		}
		temp = p;
		p = p->next;
	}
	printf("\n你要删除的元素 %d 不在表中\n",x);
	return ;
}

单链表的逆置

头插法逆置(带头结点)

1
2
3
4
5
6
7
8
9
10
11
12
13
void reverse_2(forward_list *head)//头插法逆置,带头节点
{
    forward_list *p,*q;
    p=head->next;
    head->next=NULL;
    while(p)
    {
        q=p;
        p=p->next;
        q->next=head->next;
        head->next=q;
    }
}

计算单链表的表长

*** 带头结点 ***

1
2
3
4
5
6
7
8
9
10
11
void list_length_2(forward_list *s)
{
	int count;
	forward_list *p=s->next;
	while(p)
	{
		count++;
		p = p->next;
	}
	printf("\nlist length: %d\n",count);
}

*** 不带头结点 ***

1
2
3
4
5
6
7
8
9
10
11
void list_length_1(forward_list *s)
{
	int count;
	forward_list *p=s;
	while(p)
	{
		count++;
		p = p->next;
	}
	printf("\nlist length: %d\n",count);
}

打印单链表

*** 带头结点 ***

1
2
3
4
5
6
7
8
9
10
11
void print_forward_list_2(forward_list *s)//打印含头节点的单链表
{
	forward_list *p;
	p = s->next;//因为含有头节点，head->data的数据域的数据未知
	while(p != NULL)
	{
		printf("%-3d",p->data);
		p = p->next;
	}
	return ;
}

*** 不带头结点 ***

1
2
3
4
5
6
7
8
9
10
11
void print_forward_list_1(forward_list *s)//打印单链表
{
	forward_list *p;
	p = s;
	while(p != NULL)
	{
		printf("%4d",p->data);
		p = p->next;
	}
	return ;
}

试试

源程序

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
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

//定义单链表结点类型
typedef struct node{
	int data;                         //结点数据域
	struct node *next;                //结点指针域

}forward_list;

//尾插法建表
forward_list* creat_1()
{
    forward_list *head=NULL;//头指针，初始状态为空
	forward_list *rear=NULL;//尾指针，初始状态为空
	int num;
	forward_list *s;
	while(scanf("%d",&num) == 1 && num)//输入0结束
	{
		s = (forward_list*)malloc(sizeof(forward_list));

		s->data = num;
		if(head == NULL)//将新节点加入空表
	        head = s;
	    else            //原表非空，将新节点链接到表尾之后
	        rear->next = s;
		rear = s;//尾指针指向新的表尾
    }
    if(rear!= NULL)//对于非空表，将尾结点的下一个结点置空
	    rear->next = NULL;

	return head;
}

//尾插法建表,包含头结点
forward_list* creat_2()
{
	forward_list *s;
	forward_list *head, *rear;
	int num;

	head = (forward_list*)malloc(sizeof(forward_list));
	rear = head;

	while(scanf("%d",&num)==1 && num)
	{
		s = (forward_list*)malloc(sizeof(forward_list));

		s->data = num;
	    rear->next = s;
		rear = s;//表指针指向新的表尾
	}
	rear->next = NULL;

	return head;
}

forward_list* creat_3()    //头插法
{
    forward_list *head,*s;
	int num;
	head = NULL;//链表初始状态为空
	while(scanf("%d",&num) && num)
	{
		s = (forward_list*)malloc(sizeof(forward_list));
		s->data = num;

		s->next = head;

		head = s;//将新结点插入到表头
	}
	return head;
}

void search_1(forward_list *s, int x)
{
	forward_list *p;
	p = s;
	while(p != NULL)
	{
		if(p->data == x)
		{
		    printf("\nthe value : %d is exist !\n",x);
		    return ;
		}
		p = p->next;
	}
	printf("\nthe value : %d is not fonud !\n",x);
}

void search_2(forward_list *s, int x)//带头节点
{
	forward_list *p;
	p = s->next;//emmmm
	while(p != NULL)
	{
		if(p->data == x)
		{
		    printf("\nthe value : %d is exist !\n",x);
		    return ;
		}
		p = p->next;
	}
	printf("\nthe value : %d is not fonud !\n",x);
}

void reverse_1(forward_list *head)//头插法逆置单链表
{
	forward_list *p;
	forward_list *temp;

	p = head;//存好之前的单链表
	//printf("\n%d\n",p->data);
	head->next = NULL;
	while(p)
	{
	    temp = p;
	    //printf("1");
	    p = p->next;
	    temp->next = head->next;
		head = temp;
		printf("\n%d\n",head->data);
	}
}

void reverse_2(forward_list *head)//头插法逆置,带头节点
{
    forward_list *p,*q;
    p=head->next;
    head->next=NULL;
    while(p)
    {
        q=p;
        p=p->next;
        q->next=head->next;
        head->next=q;
    }
}


void forward_list_delete_1(forward_list *s,int x)//删除链表（不带头节点）中指定值的元素
{
    forward_list *p;
    forward_list *temp;//用来存放被删除元素的前一个结点
	p = s;
	if(x == p->data)
	    free(p);

	temp = p;
	p = p->next;
    while(p != NULL)
	{
	    if(p->data == x)
		{
            temp->next = p->next;
            free(p);
            return ;
		}
		temp = p;
		p = p->next;
	}
	printf("\n你要删除的元素 %d 不在表中\n",x);
	return ;
}

void delete_1(forward_list *head,int i)        //删除第i个节点(单链表包含头节点)
{
	int j=0;
	forward_list *p,*q;
	p=head;
	j=0;
	while((p->next!=NULL)&&(j<i-1))
	{
		p=p->next;
		j++;
	}
	if(p->next!=NULL)
	{
		q=p->next;
		p->next=p->next->next;
		free(q);
	}
	else
		printf("illegal delete position,delete failed!");
}




/*//不对
void list_delete(forward_list *s, int i)//删除单链表(不带头节点)的第i个结点
{
    int count=1;
	forward_list *p,*q;
	p=s;

	//将p移动到被删除结点的前一个结点

	while((p!=NULL)&&(count<i-1))
	{

		p=p->next;
		count++;
	}

	if(i == count)
	{
		q = p;
		p = p->next;
		free(q);
		return ;
	}
   	if(p->next!=NULL)
	{
		q=p->next;
		p->next=p->next->next;
		free(q);
	}
	else
		printf("illegal delete position,delete failed!");

}
*/
void list_length_1(forward_list *s)
{
	int count;
	forward_list *p=s;
	while(p)
	{
		count++;
		p = p->next;
	}
	printf("\nlist length: %d\n",count);
}

void list_length_2(forward_list *s)
{
	int count;
	forward_list *p=s->next;
	while(p)
	{
		count++;
		p = p->next;
	}
	printf("\nlist length: %d\n",count);
}

void print_forward_list_1(forward_list *s)//打印单链表
{
	forward_list *p;
	p = s;
	while(p != NULL)
	{
		printf("%4d",p->data);
		p = p->next;
	}
	return ;
}

void print_forward_list_2(forward_list *s)//打印含头节点的单链表
{
	forward_list *p;
	p = s->next;//因为含有头节点，head->data的数据域的数据未知
	while(p != NULL)
	{
		printf("%-3d",p->data);
		p = p->next;
	}
	return ;
}

int main()
{
	/*不带头结点的单链表*/
	printf("使用不带头结点的单链表:\n");
	forward_list *p;
	printf("尾插法建表:\n");
	p = creat_1();//尾插法建表
	print_forward_list_1(p);
	list_length_1(p);

	//查找是否存在值为6的结点
	search_1(p,6);
	printf("\n删了个5后，表变为\n");
	forward_list_delete_1(p,5);
	print_forward_list_1(p);

	//头插法建表
	forward_list *s;
	printf("\n头插法建表:\n");
	s = creat_3();
	print_forward_list_1(s);
	list_length_1(s);

	/*带头结点的单链表*/
	printf("\n\n使用带头结点的单链表:\n");
	forward_list *t;
	t = creat_2();
	print_forward_list_2(t);

	search_2(t,6);
	list_length_2(t);
	printf("\n逆置:\n");
	reverse_2(t);
	print_forward_list_2(t);
	list_length_2(t);

	return 0;
}

运行结果

相关文章
线性表之顺序存储-顺序表顺序表的操作 向有序顺序表插入一个元素 顺序表的冒泡排序 顺序表的删除操作 顺序表中元素的查找 顺序表的逆置 ...竖式问题字符串处理函数strchr() && 竖式问题 竖式问题

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://yeshan333.github.io/2018/12/15/线性表的链式存储-单链表/

可以通过下方二维码支持下我哦~

更新于：2018年12月15日

C

数据结构

评论