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


单链表操作

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

单链表的创建

头插法

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
#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;
}

运行结果


 评论