【数据结构】-----链表操作大全（包含完整代码） C语言_c链表操作代码

链表完整操作

头文件

#include<stdio.h>
#include<stdlib.h>
typedef int SqlElemType;
typedef int Status;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
1
2
3
4
5
6
7
8

单链表的存储结构

typedef struct L_list {
	SqlElemType data;//结点的数据域
	struct L_list* next;//结点的指针域
}Lnode, * LinkedList;//LinkedList为指向结构体L_list的指针类型
1
2
3
4

单链表的初始化

Status InitList(LinkedList* L)//L是个二级指针
{
	(*L) = (LinkedList)malloc(sizeof(Lnode));//生成新结点作头结点，用头指针指向头结点
	(*L)->next = NULL;//将头结点的指针域置空
	return OK;
}
1
2
3
4
5
6

判断链表是否为空

Status IsEmptyList(LinkedList L)//若L为空表，返回1，否则返回0
{
	if (L->next)//非空
	{
		return 0;
	}
	else
		return 1;
}
1
2
3
4
5
6
7
8
9

销毁单链表

Status DestroyList(LinkedList* L)
{
	LinkedList p;
	while (*L)
	{
		p = *L;
		(*L) = (*L)->next;
		free(p);
	}
	return OK;
}
1
2
3
4
5
6
7
8
9
10
11

清空链表

Status ClearList(LinkedList* L)
{
	LinkedList p = (*L)->next;
	LinkedList q;
	while (p)//没到表尾
	{
		q = p->next;
		free(p);
		p = q;
	}
	(*L)->next = NULL;//头结点指针域为空
	return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

求单链表的表长

int ListLength(LinkedList L)//返回L中数据元素个数
{
	LinkedList p;
	p = L->next;//P指向第一个结点
	int i = 0;
	while (p)//遍历单链表，统计结点数
	{
		i++;
		p = p->next;
	}
	return i;
}
1
2
3
4
5
6
7
8
9
10
11
12

取单链表中第i个元素的值

Status GetElem_L(LinkedList L, int i,SqlElemType *e) 
{
	int count = 1;
	LinkedList p=L->next;//初始化
	while (p && count<i)//向后扫描，直到p指向第i个元素或p为空
	{
		p = p->next;
		count++;
	}
	if (!p||count>i)//第i个元素不存在
        return ERROR;
	*e = p->data;//取第i个元素
	return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

按值查找–根据指定数据获取该数据所在位置（地址）

LinkedList LocateElem_L(LinkedList L, SqlElemType e)
{
	//在线性表中查找值为e的数据元素
	//找到，就返回L中值为e的数据元素的地址，查找失败返回NULL
	LinkedList p = L->next;
	while (p && p->data != e)
	{
		p = p->next;
	}
	return p;
}
1
2
3
4
5
6
7
8
9
10
11

按值查找–根据指定数据获取该数据位置序号

int LocateElem_LL(LinkedList L, SqlElemType e)
//在线性表L中查找值为e的数据元素的位置序号
{
	LinkedList p = L->next;
	int j = 1;
	while (p && p->data != e)
	{
		p = p->next;
		j++;
	}
	if (p)
		return j;
	else
		return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

插入

//在第i个结点前插入值为e的新结点
Status InsertList(LinkedList* L, int i, SqlElemType e)
{
	int count = 0;
	LinkedList p;
	p = (*L);
	while (p && count < i-1)//寻找第i-1个结点，p指向i-1结点
	{
		count++;
		p = p->next;
	}
	if (!p || count > i-1)//i大于表长+1或者小于1，插入位置非法
		return ERROR;
	LinkedList s = (LinkedList)malloc(sizeof(Lnode));//生成新结点s
	s->data = e;//将结点s的数据域置为e
	s->next = p->next;//将结点s插入L中
	p->next = s;
	return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

删除

//删除第i个结点
Status DeleteList(LinkedList* L, int i, SqlElemType* e)
{
	LinkedList p = (*L);
	int count = 0;
	while (p->next && count < i - 1)//寻找第i个结点，并令p指向其前驱
	{
		p = p->next;
		count++;
	}
	if (count > i - 1 || !(p->next))//删除位置不合理
		return ERROR;
	LinkedList q = p->next;//临时保存被删结点的地址以备释放
	*e = q->data;//保存删除结点的指针域
	p->next = q->next;//改变删除结点前驱结点的指针域
	free(q);//释放删除结点的空间
	return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

创建链表–头插法

//算法时间复杂度：O（n）
void CreateList_h(LinkedList* L, int n)
{
	(* L) = (LinkedList)malloc(sizeof(Lnode));
	(*L)->next = NULL;//先建立一个带头结点的单链表
	LinkedList p;
	for (int i = n; i > 0; i--)
	{
		p= (LinkedList)malloc(sizeof(Lnode));//生成新结点
		scanf("%d", &(p->data));
		p->next = (*L)->next;//插入到表头
		(*L)->next = p;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

创建链表–尾插法

//算法时间复杂度：O（n）
void CreateList_tail(LinkedList* L, int n)
{
	(*L) = (LinkedList)malloc(sizeof(Lnode));
	(*L)->next = NULL;
	LinkedList r = *L;//尾指针r指向头结点
	for (int i = 0; i < n; i++)
	{
		LinkedList p= (LinkedList)malloc(sizeof(Lnode));
		scanf("%d", &(p->data));//生成新结点，输入元素值
		p->next = NULL;
		r->next = p;//插入到表尾
		r = p;//r指向新的尾结点
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

带尾指针循环链表的合并

//算法时间复杂度：O（1）
LinkedList Connect(LinkedList Ta, LinkedList Tb)//假设Ta,Tb都是非空的单循环链表
{
	LinkedList p = Ta->next;//p存表头结点
	Ta->next = Tb->next->next;//Tb表头连接Ta表尾
	free(Tb->next);//释放Tb表头结点
	Tb->next = p;//修改指针
	return Tb;
}
1
2
3
4
5
6
7
8
9

双向链表

typedef struct DuLNode {
	SqlElemType data;
	struct DuLNode* prior, * next;
}DuLNode,*DuLinkedList;
1
2
3
4

双向链表的插入

void InsertList_Du(DuLinkedList* L, int i, SqlElemType e)//在带头结点的双向循环链表中第i个位置之前插入元素e
{
	DuLinkedList p = (*L);
	int count = 0;
	while (p->next && count < i - 1)
	{
		p = p->next;
		count++;
	}
	DuLinkedList s = (DuLinkedList)malloc(sizeof(DuLNode));
	s->data = e;
	s->next = p->next;
	s->prior = p;
	p->next->prior = s;
	p->next = s;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

双向链表的删除

void DeleteList_Du(DuLinkedList* L, int i, SqlElemType* e)
{
	//删除带头结点的双向循环链表L的第i个元素，并用e返回
	DuLinkedList p=(*L);
	int count = 0;
	while (p->next && count < i - 1)
	{
		p = p->next;
		count++;
	}

	*e = p->next->data;
	p->next = p->next->next;
	p->next->prior = p;
	free(p->next);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

输出链表

void OutputList(LinkedList L)
{
	LinkedList p = L;
	while (p->next)
	{
		printf("%d ", p->next->data);
		p = p->next;
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10

验证代码是否正确（主函数部分）

int main()
{
	int a,n;
	Lnode List;
	LinkedList LL = &List;
	LinkedList* L = ≪
	a=InitList(L);
	printf("单链表的初始化\n");
	printf("%d\n", a);
	printf("初始化完成\n");
	a=IsEmptyList(LL);
	printf("判断链表是否为空\n");
	printf("%d\n", a);
	printf("输入链表的值的个数\n");
	scanf("%d", &n);
	printf("创建链表--头插法，请倒序输入想要的值\n");
	CreateList_h(L, n);
	printf("输出链表\n");
	OutputList(LL);
	a = ListLength(LL);
	printf("求单链表的表长\n");
	printf("%d\n", a);
	printf("插入\n");
	printf("输入要在第几个结点前插入，插入的值为几\n");
	int i, e;
	scanf("%d%d", &i, &e);
	InsertList(L, i, e);
	printf("输出链表\n");
	OutputList(LL);
	printf("删除\n");
	printf("输入要删除第几个结点\n");
	scanf("%d", &i);
	DeleteList(L, i, &e);
	printf("删除的值为%d\n", e);
	printf("输出链表\n");
	OutputList(LL);
	printf("取单链表中第i个元素的值,输入i\n");
	scanf("%d", &i);
	GetElem_L(LL, i, &e);
	printf("第%d个元素的值为%d\n", i, e);
	printf("按值查找--根据指定数据获取该数据所在位置（地址）\n");
	printf("输入查找的值:\n");
	scanf("%d", &i);
	LinkedList p=LocateElem_L(LL, i);
	printf("该数据所在位置（地址）为%p\n", p);
	printf("按值查找--根据指定数据获取该数据位置序号\n");
	printf("输入查找的值:\n");
	scanf("%d", &i);
	int l = LocateElem_LL(LL, i);
	printf("该数据所在位置序号为%d\n", l);
    printf("清空链表\n");
	a=ClearList(L);
	printf("%d\n", a);
	printf("清空链表完成\n");
	a = IsEmptyList(LL);
	printf("判断链表是否为空\n");
	printf("%d\n", a);
	printf("链表为空\n");
	printf("输出链表\n");
	OutputList(LL);
	printf("销毁单链表\n");
	a=DestroyList(L);
	printf("%d\n", a);
	printf("链表销毁完成\n");
	return 0;
}
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

运行结果

完整代码

#include<stdio.h>
#include<stdlib.h>
typedef int SqlElemType;
typedef int Status;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
//链表
//单链表的存储结构
typedef struct L_list{
	SqlElemType data;//结点的数据域
	struct L_list* next;//结点的指针域
}Lnode,*LinkedList;//LinkedList为指向结构体L_list的指针类型
//单链表的初始化
Status InitList(LinkedList* L)//L是个二级指针
{
	(*L) = (LinkedList)malloc(sizeof(Lnode));//生成新结点作头结点，用头指针指向头结点
	(*L)->next = NULL;//将头结点的指针域置空
	return OK;
}
//判断链表是否为空
Status IsEmptyList(LinkedList L)//若L为空表，返回1，否则返回0
{
	if (L->next)//非空
	{
		return 0;
	}
	else
		return 1;
}
//销毁单链表
Status DestroyList(LinkedList* L)
{
	LinkedList p;
	while (*L)
	{
		p = *L;
		(* L) = (*L)->next;
		free(p);
	}
	return OK;
}
//清空链表
Status ClearList(LinkedList* L)
{
	LinkedList p=(*L)->next;
	LinkedList q;
	while (p)//没到表尾
	{
		q = p->next;
		free(p);
		p = q;
	}
	(*L)->next = NULL;//头结点指针域为空
	return OK;
}
//求单链表的表长
int ListLength(LinkedList L)//返回L中数据元素个数
{
	LinkedList p;
	p = L->next;//P指向第一个结点
	int i = 0;
	while (p)//遍历单链表，统计结点数
	{
		i++;
		p = p->next;
	}
	return i;
}
//取单链表中第i个元素的值
Status GetElem_L(LinkedList L, int i,SqlElemType *e) 
{
	int count = 1;
	LinkedList p=L->next;//初始化
	while (p && count<i)//向后扫描，直到p指向第i个元素或p为空
	{
		p = p->next;
		count++;
	}
	if (!p||count>i)//第i个元素不存在
        return ERROR;
	*e = p->data;//取第i个元素
	return OK;
}
//按值查找--根据指定数据获取该数据所在位置（地址）
LinkedList LocateElem_L(LinkedList L, SqlElemType e)
{
	//在线性表中查找值为e的数据元素
	//找到，就返回L中值为e的数据元素的地址，查找失败返回NULL
	LinkedList p = L->next;
	while (p && p->data != e)
	{
		p = p->next;
	}
	return p;
}
//按值查找--根据指定数据获取该数据位置序号
int LocateElem_LL(LinkedList L, SqlElemType e)
//在线性表L中查找值为e的数据元素的位置序号
{
	LinkedList p = L->next;
	int j = 1;
	while (p && p->data != e)
	{
		p = p->next;
		j++;
	}
	if (p)
		return j;
	else
		return 0;
}
//插入
//在第i个结点前插入值为e的新结点
Status InsertList(LinkedList* L, int i, SqlElemType e)
{
	int count = 0;
	LinkedList p;
	p = (*L);
	while (p && count < i-1)//寻找第i-1个结点，p指向i-1结点
	{
		count++;
		p = p->next;
	}
	if (!p || count > i-1)//i大于表长+1或者小于1，插入位置非法
		return ERROR;
	LinkedList s = (LinkedList)malloc(sizeof(Lnode));//生成新结点s
	s->data = e;//将结点s的数据域置为e
	s->next = p->next;//将结点s插入L中
	p->next = s;
	return OK;
}
//删除
//删除第i个结点
Status DeleteList(LinkedList* L, int i, SqlElemType* e)
{
	LinkedList p = (*L);
	int count = 0;
	while (p->next && count < i - 1)//寻找第i个结点，并令p指向其前驱
	{
		p = p->next;
		count++;
	}
	if (count > i - 1 || !(p->next))//删除位置不合理
		return ERROR;
	LinkedList q = p->next;//临时保存被删结点的地址以备释放
	*e = q->data;//保存删除结点的指针域
	p->next = q->next;//改变删除结点前驱结点的指针域
	free(q);//释放删除结点的空间
	return OK;
}
//创建链表--头插法
//算法时间复杂度：O（n）
void CreateList_h(LinkedList* L, int n)
{
	(* L) = (LinkedList)malloc(sizeof(Lnode));
	(*L)->next = NULL;//先建立一个带头结点的单链表
	LinkedList p;
	for (int i = n; i > 0; i--)
	{
		p= (LinkedList)malloc(sizeof(Lnode));//生成新结点
		scanf("%d", &(p->data));
		p->next = (*L)->next;//插入到表头
		(*L)->next = p;
	}
}
//创建链表--尾插法
//算法时间复杂度：O（n）
void CreateList_tail(LinkedList* L, int n)
{
	(*L) = (LinkedList)malloc(sizeof(Lnode));
	(*L)->next = NULL;
	LinkedList r = *L;//尾指针r指向头结点
	for (int i = 0; i < n; i++)
	{
		LinkedList p= (LinkedList)malloc(sizeof(Lnode));
		scanf("%d", &(p->data));//生成新结点，输入元素值
		p->next = NULL;
		r->next = p;//插入到表尾
		r = p;//r指向新的尾结点
	}
}
//带尾指针循环链表的合并
//算法时间复杂度：O（1）
LinkedList Connect(LinkedList Ta, LinkedList Tb)//假设Ta,Tb都是非空的单循环链表
{
	LinkedList p = Ta->next;//p存表头结点
	Ta->next = Tb->next->next;//Tb表头连接Ta表尾
	free(Tb->next);//释放Tb表头结点
	Tb->next = p;//修改指针
	return Tb;
}
//双向链表
typedef struct DuLNode {
	SqlElemType data;
	struct DuLNode* prior, * next;
}DuLNode,*DuLinkedList;
//双向链表的插入
void InsertList_Du(DuLinkedList* L, int i, SqlElemType e)//在带头结点的双向循环链表中第i个位置之前插入元素e
{
	DuLinkedList p = (*L);
	int count = 0;
	while (p->next && count < i - 1)
	{
		p = p->next;
		count++;
	}
	DuLinkedList s = (DuLinkedList)malloc(sizeof(DuLNode));
	s->data = e;
	s->next = p->next;
	s->prior = p;
	p->next->prior = s;
	p->next = s;
}
//双向链表的删除
void DeleteList_Du(DuLinkedList* L, int i, SqlElemType* e)
{
	//删除带头结点的双向循环链表L的第i个元素，并用e返回
	DuLinkedList p=(*L);
	int count = 0;
	while (p->next && count < i - 1)
	{
		p = p->next;
		count++;
	}

	*e = p->next->data;
	p->next = p->next->next;
	p->next->prior = p;
	free(p->next);
}
//输出链表
void OutputList(LinkedList L)
{
	LinkedList p = L;
	while (p->next)
	{
		printf("%d ", p->next->data);
		p = p->next;
	}
	printf("\n");
}
int main()
{
	int a,n;
	Lnode List;
	LinkedList LL = &List;
	LinkedList* L = &LL;
	a=InitList(L);
	printf("单链表的初始化\n");
	printf("%d\n", a);
	printf("初始化完成\n");
	a=IsEmptyList(LL);
	printf("判断链表是否为空\n");
	printf("%d\n", a);
	printf("输入链表的值的个数\n");
	scanf("%d", &n);
	printf("创建链表--头插法，请倒序输入想要的值\n");
	CreateList_h(L, n);
	printf("输出链表\n");
	OutputList(LL);
	a = ListLength(LL);
	printf("求单链表的表长\n");
	printf("%d\n", a);
	printf("插入\n");
	printf("输入要在第几个结点前插入，插入的值为几\n");
	int i, e;
	scanf("%d%d", &i, &e);
	InsertList(L, i, e);
	printf("输出链表\n");
	OutputList(LL);
	printf("删除\n");
	printf("输入要删除第几个结点\n");
	scanf("%d", &i);
	DeleteList(L, i, &e);
	printf("删除的值为%d\n", e);
	printf("输出链表\n");
	OutputList(LL);
	printf("取单链表中第i个元素的值,输入i\n");
	scanf("%d", &i);
	GetElem_L(LL, i, &e);
	printf("第%d个元素的值为%d\n", i, e);
	printf("按值查找--根据指定数据获取该数据所在位置（地址）\n");
	printf("输入查找的值:\n");
	scanf("%d", &i);
	LinkedList p=LocateElem_L(LL, i);
	printf("该数据所在位置（地址）为%p\n", p);
	printf("按值查找--根据指定数据获取该数据位置序号\n");
	printf("输入查找的值:\n");
	scanf("%d", &i);
	int l = LocateElem_LL(LL, i);
	printf("该数据所在位置序号为%d\n", l);
    printf("清空链表\n");
	a=ClearList(L);
	printf("%d\n", a);
	printf("清空链表完成\n");
	a = IsEmptyList(LL);
	printf("判断链表是否为空\n");
	printf("%d\n", a);
	printf("链表为空\n");
	printf("输出链表\n");
	OutputList(LL);
	printf("销毁单链表\n");
	a=DestroyList(L);
	printf("%d\n", a);
	printf("链表销毁完成\n");
	return 0;
}
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