头文件 LinkList.h

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
#define _CRT_SECURE_NO_WARNINGS
#pragma once

#include<stdlib.h>
#include<stdbool.h>
#include<stdio.h>

#ifdef __cplusplus
extern "C" {
#endif // __cplusplus


	//定义节点数据类型
	struct LinkNode
	{
		int val;
		struct LinkNode* next;
	};


	//初始化链表
	struct LinkNode* Init_LinkList();

	//在值oldval处插入一个新数据newval，oldval往后移
	void InsertByValue_LinkList(struct LinkNode* header,int oldval,int newval);

	//删除值为val的结点
	void RemoveByValue_LinkList(struct LinkNode* header, int delValue);
	//遍历
	void Foreach_LinkList(struct LinkNode* header);
	//销毁链表
	void Destroy_LinkList(struct LinkNode* header);
	//清空链表
	void Clear_LinkList(struct LinkNode* header);



#ifdef __cpluspus
}
#endif //

函数文件LinkList.c

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
#include"LinkList.h"

//初始化链表
struct LinkNode* Init_LinkList()
{
	//创建头结点
	struct LinkNode* header = malloc(sizeof(struct LinkNode));
	header->val = - 1;//默认数据不影响
	header->next = NULL;

	//尾部指针
	struct LinkNode* pRear = header;
	int data = -1;
	while (true)
	{
		printf("输入构成的数据：\n");
		scanf("%d", &data);
		//输入-1结束输入
		if (data == -1)
		{

			break;
		}
		//创建新节点
		struct LinkNode* newnode = malloc(sizeof(struct LinkNode));
		newnode->val = data;
		newnode->next = NULL;
		//新结点插入到链表中
		pRear->next = newnode;
		//更新尾部指针
		pRear = newnode;
	}
	//将链表返回
	return header;
}

//在值oldval处插入一个新数据newval，oldval向后移
void InsertByValue_LinkList(struct LinkNode* header, int oldval, int newval)
{
	if (header == NULL)
	{
		return;
	}

	//创建两个辅助指针变量
	struct LinkNode* pPrev=header->next;
	struct LinkNode* pCurrent = pPrev->next;
	while (pCurrent->val != oldval)
	{
		pPrev = pCurrent;
		pCurrent = pCurrent->next;
		if (pCurrent == NULL)
		{
			break;
		}
	}
#if 0

	//如果pCurrent为空，则没有链表中没有符合插入的位置，直接插入到最后

	if (pCurrent == NULL)
	{
		return;
	}
#endif
	struct LinkNode* newnode = malloc(sizeof(struct LinkNode));
	newnode->val = newval;
	newnode->next = pCurrent;
	pPrev->next = newnode;
	return header;

}

//删除值为val的结点
void RemoveByValue_LinkList(struct LinkNode* header, int delValue)
{
	if (header == NULL)
	{
		return;
	}

	struct LinkNode* pPrev = header;
	//创建用于查找要删除数据的指针
	struct LinkNode* Find = pPrev->next;
	while (Find->val != delValue)
	{
		pPrev = pPrev->next;
		Find = Find->next;
		//未找到直接返回
		if (Find == NULL)
		{
			return;
		}
	}
	//跳过要删除项，将要删除项前后连接
	pPrev->next = Find->next;
	//找到将此块(要删除项)内存域释放
	free(Find);
	Find = NULL;//防止Find成为野指针
	return header;
	
}
//遍历
void Foreach_LinkList(struct LinkNode* header)
{
	if (header == NULL)
	{
		return;
	}

	//辅助指针
	struct LinkNode* pCurrent = header->next;
	while(pCurrent)
	{
		printf("%d\n", pCurrent->val);
		pCurrent = pCurrent->next;
	}

}
//销毁链表
void Destroy_LinkList(struct LinkNode* header)
{
	if (header == NULL)
	{
		return;
	}

	//辅助指针
	struct LinkNode* pCurrent = header;
	struct LinkNode* pNext = pCurrent;
	while (pCurrent!=NULL)
	{
		pNext = pCurrent->next;
		printf("%d结点被销毁\n",pCurrent->val);
		free(pCurrent);
		pCurrent = pNext;
	}

}
//清空链表
void Clear_LinkList(struct LinkNode* header)
{
	if (header == NULL)
	{
		return;
	}

	//辅助指针
	struct LinkNode* pCurrent = header->next;

	while (pCurrent != NULL)
	{
		//先将pCrrent下一块域保存以便可以访问
		struct LinkNode* pNext = pCurrent->next;
		//释放当前节点内存
		free(pCurrent);
		//更新结点
		pCurrent = pNext;
	}

	header->next = NULL;

	return header;
}

主函数用于测试TestLinkList.c

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

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include"LinkList.h"

//测试函数
void test()
{
	//初始化链表,100,200,300,400,500   插入666，删除666
	struct LinkNode* header = Init_LinkList();
	//打印链表
	Foreach_LinkList(header);
	printf("--------------------------------\n");
	//插入数据
	InsertByValue_LinkList(header, 500, 111);
	Foreach_LinkList(header);
	printf("--------------------------------\n");
	//删除数据
	RemoveByValue_LinkList(header,111);
	Foreach_LinkList(header);
	printf("--------------------------------\n");
	//清空链表
	Clear_LinkList(header);
	Foreach_LinkList(header);
	printf("--------------------------------\n");
	//销毁链表
	Destroy_LinkList(header);
}
int main()
{
	printf("插入111，再删除111，清空链表并销毁\n");
	test();
	return 0;
}

输出结果展示

快慢指针

通过快慢指针可以快速确定链表的中间位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct LinkNode* middleSpot(struct LinkNode*head)
{
    struct LinkNode *Prev=head;
    struct LinkNode *Slow=head;
    while(Prev!=NULL)
    {
        Prev=
        if(Prev!=NULL)
        {
            Prev=Prev->next;
            Slow=Slow->next;
        }
    }
    return Slow;
}

效果