C语言简单的数据结构：单链表_c语言单链表

我们在使用顺序表的时候我们发现了一些问题：
1.涉及到中间插入和头插时会进行数据的移动，导致效率较低
2.增容的空间会进行数据的拷贝
3.每次申请的空间不一定被使用，导致空间浪费
以上都说明顺序表不是很完美的，那有什么解决方法呢？
没错那就是：链表

1. 单链表的概念及结构

概念：链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表
中的指针链接次序实现的。
所以链表也是线性表的一种（物理结构上不一定时线性的，逻辑结构是连续的）

这就是链表的结构，它是由存储的数据和指向下一个节点的指针组成的
那么链表的定义就可以写出来了：

2. 单链表的实现

2.1单链表的定义、创建和打印

2.11单链表的定义

首先是文件的创建和之前的一样：SList.h头文件，SList.c、test.c源文件
然后就是定义结构体了，这里用到的方法和顺序表的方法一样

2.12单链表的创建

接下来我们进行节点的创建，这里创建了四个节点

那我们如何让他们互相找到呢，这就是前面说的：放指向下一个节点的指针

这样就构成了一个链表

2.13单链表的打印

打印函数的函数的声明：

这里多创建一个指针防止对原来指针进行改变

我们在这里创建了一个pcur来接受传进来的传进来的地址接收，然后当pcur指向的不为NULL指针时，将数值打印出来，然后让pcur 指向下一个节点的地址，这就是链表的遍历

测试：

2.2单链表的头插和尾插

函数的声明（但这里有问题下文会改正）
既然要加数据就要先把数据放入节点中：

简单的空间开辟，将数值放入即可

2.21尾插

将我们最后的节点指向NULL改成限一个节点的地址，然后让下一个节点指向NULL即可

但是这个代码中有问题：
原链表如果是空链表，那么while语句就对NULL指针解引用，就会出现问题
解决方法：直接将新开辟的节点给phead即可

但还是有问题

这里并没有改变，我们进行调试：

发现形参变了而实参没有变化，就要传地址，而不是传值



这样就改完了
测试：

这样就正确了，在优化一下：

2.22头插

和尾插一样但是申请的节点要指向之前的链表头，然后成为链表头

这里如果phead是NULL也可以，直接会替换NULL
测试：

2.3单链表的头删和尾删

函数声明

2.31尾删

将指针到5位置的数据删除掉，好要将第四个节点指向NULL

用快慢指针进行更改即可
但这个代码还有问题：

这种情况就不用找尾部节点

测试：

此时在进行尾删就会报错

2.31头删

创建新指针接收，让后进行释放后再将保存的指针重新赋值即可
测试：

2.4单链表的查找

声明：

链表进行遍历，找不到就返回NULL，一个循环加判断就可以了
测试：

2.5单链表指定位置的插入和删除

2.51指定位置前插入数据

这里因为有pos就一定有数值所以pphead不能为NULL

这是pos在中间时可以使用，进行遍历然后让prev,newnode,pos相连接就可以了

代码在头部就行不通，因为在前面无法找到pos，在最后面时可以行的

这里加个判断进行头插的调用即可
测试：

2.52指定位置后插入数据

为什么没有头节点？
因为之后插入直接在pos进行操作即可不用对pos前的数据

这里连接的方法有两种：
1.是先蓝（尾部连接）再红（头部连接）
2.先红（头部连接）后蓝（尾部连接）
这里分析一下：

这里第二种pos的指针next已经先改变了，无法再给newnode

关系明了了，代码不难的
测试：

2.53删除pos节点

这里又涉及到找pos前的数据了，所以有pphead

这里先找pos将其的指向下个地址给prev，然后释放pos
但这里又有pos在首位的时候会查不到，和之前的解决方法一样

测试：

2.54删除pos之后节点

这里如果pos后没有节点就不可以删除，要用assert对pos->next进行断言
测试：

2.6单链表的销毁

要一个一个的释放掉，就要用指针保存下一个节点的地址

测试：

本文代码：

SList.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SLTDataType;
//定义节点的结构
typedef struct SListNode
{
	SLTDataType data;
	struct SLintNode* next;
}SLTNode;

void SLTPrint(SLTNode* phead);//打印链表

SLTNode* SLTBuyNode(SLTDataType x);//新节点存放数据
void SLTPushBack(SLTNode** pphead, SLTDataType x);//尾插
void SLTPushFront(SLTNode** pphead, SLTDataType x);//头插

void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);

SLTNode* SLTFind(SLTNode* phead, SLTDataType x);

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//指定位置前插入数据
void SLTInstertAfter(SLTNode* pos, SLTDataType x); //指定位置后插入数据

void SLTErase(SLTNode** pphead, SLTNode* pos);//删除pos节点
void SLTEraseAfter(SLTNode* pos);//删除pos之后节点

void SListDesTroy(SLTNode** pphead);
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

SList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"

void SLTPrint(SLTNode* phead)
{
	//打印链表
	SLTNode* pcur = phead;
	while (pcur)//pcur!=NULL
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL");
	printf("\n");
}

SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
}

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);//新节点的创建
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* ptail = *pphead;
		//找尾（patil的下一个节点为NULL）
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		ptail->next = newnode;
	}
}

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

void SLTPopBack(SLTNode** pphead)
{
	assert(pphead && *pphead);//链表和地址都不为NULL
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* prev = *pphead;
		SLTNode* ptail = *pphead;
		while (ptail->next)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		free(ptail);
		ptail = NULL;
		prev->next = NULL;
	}
}

void SLTPopFront(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* pcur = phead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead && *pphead);
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);
	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		newnode->next = pos;
		prev->next = newnode;
	}
}

void SLTInstertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

void SLTEraseAfter(SLTNode* pos)
{
	assert(pos && pos->next);
	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}

void SListDesTroy(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = 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
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

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"

void SListTest01()
{
	//定义节点
	SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
	node1->data = 1;
	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
	node2->data = 2;
	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
	node3->data = 3;
	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
	node4->data = 4;

	//将节点连接起来
	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = NULL;

	SLTNode* plist = node1;

	SLTPrint(plist);
	SListDesTroy(&plist);
}

void SListTest02()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
	//SLTPushFront(&plist, 5);
	//SLTPushFront(&plist, 7);
	//SLTPushFront(&plist, 8);
	//SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SListDesTroy(&plist);
}

void SListTest03()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
	SLTNode* find = SLTFind(plist, 1);
	SLTInstertAfter(find, 11);
	SLTPrint(plist);
	SLTNode* find1 = SLTFind(plist, 4);
	SLTInstertAfter(find1, 11);
	SLTPrint(plist);
	SListDesTroy(&plist);
}

void SListTest04()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
	SListDesTroy(&plist);
	SLTPrint(plist);
}

int main()
{
	/*SListTest01();*/
	/*SListTest03();*/
	SListTest04();
	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

以上就是本文的全部内容了，希望对大家有所帮助，大家加油！！！