数据结构：单链表的实现(C语言)_设计一个单链表,要求编程实现

个人主页 ： 水月梦镜花
个人专栏 ： 《C语言》 《数据结构》

---

前言

本博客将要实现的无头单向不循环链表。

---

一、单链表实现思路和图解

1.节点的定义(SListNode)

我们将节点定义为如下结构：

其成员变量有data，next。

将int重命名为STLDataType，方便我们以后修改数据域的内容。

//无头单向不循环链表
typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SListNode;
1
2
3
4
5
6
7
8

2.申请一个节点(BuySListNode)

动态申明一个空间，来放置数据。如下：

将data的内容置成形参x，next置NULL。

//申请一个节点
SListNode* BuySListNode(SLTDataType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;

	retur
1
2
3
4
5
6
7
8
9
10
11
12
13

3.单链表打印(SListPrint)

循环遍历链表，直到尾节点。创建一个结构体指针变量cur，循环cur = cur->next，并打印cur->data的内容，直到cur == NULL。

//单链表打印
void SListPrint(SListNode* plist)
{
	SListNode* cur = plist;

	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
1
2
3
4
5
6
7
8
9
10
11
12

4.单链表尾插(SListPushBack)

• 如果链表不为NULL(链表中有元素)，要先遍历链表找到尾节点，在让尾节点指向新节点，完成尾插。
• 如果链表为NULL(链表中没有元素)，此时应该直接让新节点等于头结点，完成尾插。(本链表是无哨兵位的)
• 如果传入的头结点无效，直接判错。

当链表为NULL，我们就要修改头结点本身的内容，所以我们需要头结点的指针，而本文中头结点本身就是结构体指针，所以尾插函数参数我们需要二级指针。

//单链表尾插
void SListPushBack(SListNode** pplist, SLTDataType x)
{
	assert(pplist);

	SListNode* newnode =  BuySListNode(x);
	if (*pplist != NULL)
	{
		SListNode* cur = *pplist;
		while (cur->next != NULL)
		{
			cur = cur->next;
		}
		cur->next = newnode;
	}
	else
	{
		*pplist = newnode;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

5.单链表的头插(SListPushFront)

对于头插而言，链表是否有元素并不重要，我们只需要让新节点的指向头结点，并将头结点等于新节点。

因为头插链表，一定会改变头结点的内容，所以我们头插函数的形参也是二级指针。

//单链表的头插
void SListPushFront(SListNode** pplist, SLTDataType x)
{
	assert(pplist);

	SListNode* newnode = BuySListNode(x);
	
	newnode->next = *pplist;
	*pplist = newnode;
}
1
2
3
4
5
6
7
8
9
10

6.单链表的尾删(SListPopBack)

• 如果链表元素有两个及两以上，我们需要两个指针变量prev，next来找尾节点，循环prev = cur，cur = cur->next，使next指向尾节点，prev指向尾节点的前一个，free尾节点，prev指向的节点指向NULL。
• 如果链表元素只有一个，直接free头结点，使头结点置NULL。
• 如果链表没有元素，直接判错。

当链表元素只有一个时，此时尾删链表，要修改头结点的内容，尾删函数的形参需要二级指针。

//单链表的尾删
void SListPopBack(SListNode** pplist)
{
	assert(pplist);
	//链表为NULL
	assert(*pplist);

	if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SListNode* cur = *pplist;
		SListNode* prev = NULL;

		while (cur->next != NULL)
		{
			prev = cur;
			cur = cur->next;
		}
		prev->next = NULL;
		free(cur);
	}
}
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

7.单链表头删(SListPopFront)

我们需要一个结构体指针变量next，来保存头结点的下一个节点，然后free头结点，使头结点 = 指针变量next。

• 如果链表没有元素，直接判错。

//单链表头删
void SListPopFront(SListNode** pplist)
{
	assert(pplist);
	assert(*pplist);

	SListNode* next = (*pplist)->next;
	free(*pplist);
	*pplist = next;
}

1
2
3
4
5
6
7
8
9
10
11

8.单链表的查找(SListFind)

我们需要一个结构体指针变量cur，来遍历链表比较cur->data == x，如果相等，放回此时cur的内容(该节点的地址)。如果遍历完链表，并没有相等元素，放回NULL。

//单链表的查找
SListNode* SListFind(SListNode* plist, SLTDataType x)
{
	SListNode* cur = plist;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}

	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

9.单链表在pos位置之后插入x(SListInsertAfter)

我们让newnode指向pos下一个的节点，pos指向newnode。

• 如果我们先让pos指向newnode，newnode在指向pos的下一个节点，就会造成newnode指向自己，导致链表成环。
• 该函数不会影响头结点的内容，所以函数的形参不用二级指针。

//单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
	assert(pos);

	SListNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
1
2
3
4
5
6
7
8
9
10

10.单链表删除在pos位置之后的值(SListEraseAfter)

我们需要一个结构体指针变量next，记录pos下一个节点的地址，然后是pos指向next的下一个节点，接着free(next)。

• 如果链表只有一个元素，我们不能调用该函数，否则会导致NULL指针的解引用。
• 该函数不会改变头结点的内容，所以形参我们不用二级指针。

//单链表删除在pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
	assert(pos && pos->next);

	SListNode* next = pos->next;
	pos->next = next->next;
	free(next);
}

1
2
3
4
5
6
7
8
9
10
11

11.单链表的销毁(SListDestroy)

我们需要两个结构体指针prev，cur。先让prev = cur ，cur再指向下一个节点，free(prev)，重复上述操作，直到cur指向NULL。

需要我们在函数调用完后，自己对头结点置NULL。

//单链表的销毁
void SListDestroy(SListNode* plist)
{
	assert(plist);

	SListNode* cur = plist;
	while (cur != NULL)
	{
		SListNode* prev = cur;
		cur = cur->next;
		free(prev);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

二、代码实现

//slist.h  文件


#pragma once
#define _CRT_SECURE_NO_WARNINGS 1

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

//无头单向不循环链表
typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SListNode;


//申请一个节点
SListNode* BuySListNode(SLTDataType x);

//单链表打印
void SListPrint(SListNode* plist);

//单链表尾插
void SListPushBack(SListNode** pplist, SLTDataType x);

//单链表的头插
void SListPushFront(SListNode** pplist, SLTDataType x);

//单链表的尾删
void SListPopBack(SListNode** pplist);

//单链表头删
void SListPopFront(SListNode** pplist);

//单链表的查找
SListNode* SListFind(SListNode* plist, SLTDataType x);

//单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDataType x);

//单链表删除在pos位置之后的值
void SListEraseAfter(SListNode* pos);

//单链表的销毁
void SListDestroy(SListNode* plist);
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

//slist.c    文件


#include "slist.h"

//申请一个节点
SListNode* BuySListNode(SLTDataType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}


//单链表打印
void SListPrint(SListNode* plist)
{
	SListNode* cur = plist;

	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}


//单链表尾插
void SListPushBack(SListNode** pplist, SLTDataType x)
{
	assert(pplist);

	SListNode* newnode =  BuySListNode(x);
	if (*pplist != NULL)
	{
		SListNode* cur = *pplist;
		while (cur->next != NULL)
		{
			cur = cur->next;
		}
		cur->next = newnode;
	}
	else
	{
		*pplist = newnode;
	}
}


//单链表的头插
void SListPushFront(SListNode** pplist, SLTDataType x)
{
	assert(pplist);

	SListNode* newnode = BuySListNode(x);
	
	newnode->next = *pplist;
	*pplist = newnode;
}

//单链表的尾删
void SListPopBack(SListNode** pplist)
{
	assert(pplist);
	//链表为NULL
	assert(*pplist);

	if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SListNode* cur = *pplist;
		SListNode* prev = NULL;

		while (cur->next != NULL)
		{
			prev = cur;
			cur = cur->next;
		}
		prev->next = NULL;
		free(cur);
	}
}


//单链表头删
void SListPopFront(SListNode** pplist)
{
	assert(pplist);
	assert(*pplist);

	SListNode* next = (*pplist)->next;
	free(*pplist);
	*pplist = next;
}


//单链表的查找
SListNode* SListFind(SListNode* plist, SLTDataType x)
{
	SListNode* cur = plist;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}

	return NULL;
}

//单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
	assert(pos);

	SListNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}


//单链表删除在pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
	assert(pos && pos->next);

	SListNode* next = pos->next;
	pos->next = next->next;
	free(next);
}


//单链表的销毁
void SListDestroy(SListNode* plist)
{
	assert(plist);

	SListNode* cur = plist;
	while (cur != NULL)
	{
		SListNode* prev = cur;
		cur = cur->next;
		free(prev);
	}
}
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

---

总结

以上就是我对于无头单向不循环链表的实现！！！