C语言实现单向链表_c语言单向链表

1.线性表

线性表可以分成两种 一种就是顺序表 也就是我们所熟知的数组 一种是今天的主角–链表
他们两者的区别在于 前者是顺序储存元素的 即数组元素的地址值是连续的
后者则是链式储存的 节点的地址值不一定连续

2.单向链表

链表中的节点是由两部分组成的 一部分是数据域 另外一部分是指针域
而且一般都是由虚拟头节点开头的 虚拟头节点的数据域储存的是链表的长度 指针域指向的是实际的头节点

#include <stdio.h> 
#include <stdlib.h>
// 定义一个节点的结构体
typedef struct Node{
	int data;// 数据域
	struct Node* next;// 指针域 由于这边还未起好别名 所以不能直接使用Node*
}Node;
// 定义一个函数 用于初始化链表
Ndoe* initList(){
	// 无非就是创建一个虚拟头节点 
	Node* list = (Node*)malloc(sizeof(Node));
	list->data = 0;
	list->next = NULL;
	return list;
}
// 定义一个函数 用于进行头插操作
void headInsert(Node* list, int data){
	// 一定要注意两个节点的指针域修改顺序 先改待插入节点的next 然后在修改虚拟头节点的next
	Node* newHead = (Node*)malloc(sizeof(Node));
	newHead->data = data;
	newHead->next = list->next;
	list->next = newHead;
	// 最后别忘了更新链表的长度
	list->data++;
}
// 定义一个函数 用于进行尾插操作
void tailInsert(Node* list, int data){
	// 你不要遍历过头了 如果当前节点的下一个节点为空的话 就停止遍历操作 而不是当前节点为空才停止遍历 因为你的目的是取出尾节点 而不是NULL
	// 保留你的虚拟头节点 因为list会随着遍历操作的进行而改变 
	Node* cur = list;
	while(cur->next){
		cur = cur->next;
	}
	Node* tail = (Node*)malloc(sizeof(Node));
	tail->data = data;
	tail->next = NULL;
	cur->next = tail;
	list->data++;
}
// 定义一个函数 用于删除指定元素对应的节点(删除第一个符合条件的节点就行了) 还得通过返回值表示删除成功与否
int delete(Node* list, int data){
	Node* pre = list->next;
	Node* cur = list->next;
	while(cur){
		// 这边的循环条件有别于tailInsert的原因在于 这边需要判断所有的节点是否和指定值相同 而tailInsert目的则是获取一个链表的尾节点而已
		if(cur->data == data){
			pre->next = cur->next;
			free(cur);
			// 更新链表长度
			list->data--;
			// 我们用1表示删除成功
			return 1;
		}
		// 如果当前节点不符合条件的话  则继续往下进行寻找
		pre = cur;
		cur = cur->next;
	}
	// 如果循环结束以后 都没有找到指定节点的话 说明删除失败
	return 0;// 我们用0表示删除失败
}
void printList(Node* list){
	Node* cur = list->next;
	while(cur){
		printf("%d ", cur->data);
		cur = cur->next;
	}
}
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

测试代码如下所示:

int main() {
	Node* list = initList();
	headInsert(list, 1);
	headInsert(list, 2);
	headInsert(list, 3);
	headInsert(list, 4);
	tailInsert(list, 5);
	printList(list);
	if (delete(list, 0)) {
		printf("删除成功\n");
	}
	else {
		printf("删除失败\n");
	}
	printList(list);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3.删除代码的优化

如果单向链表的删除操作中 需要将指定值对应的所有节点都进行删除的话 那么需要用一下代码进行代替

int delete(Node* list, int data){
	// 定义一个变量 用于储存所删除元素的个数 
	int deleted = 0;
	Node* pre = list->next;
	Node* cur = list->next;
	while(cur){
		if(cur->data == data){
			pre->next = cur->next;
			free(cur);
			list->data--;
			// 同时需要更新deleted变量 因为后面需要通过该变量进行删除成功与否的判断
			deleted++;
			// 但是现在pre所表示的节点不会变 但是cur表示的节点需要改变 cur需要更新为pre的下一个节点
			cur = pre->next;
		}else{
			// 如果没有找到指定值对应的节点的话 那么就更新pre为cur 然后更新cur为当前节点的下一个节点
			pre = cur;
			cur = cur->next;
		}
	}
	// 然后最后直接返回deleted 如果为0 说明删除失败 如果为1的话 那么说明删除成功 并且可以从中知道被删除元素的个数
	return deleted;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

测试代码如下所示:

int main() {
	Node* list = initList();
	headInsert(list, 1);
	headInsert(list, 1);
	headInsert(list, 2);
	headInsert(list, 3);
	headInsert(list, 4);
	tailInsert(list, 5);
	printList(list);
	int deleted = delete(list, 1);
	if (deleted) {
		printf("删除成功 并且被删除的元素个数为%d\n", deleted);
	}
	else {
		printf("删除失败\n");
	}
	printList(list);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

4.mj版本的单向链表(C语言实现)

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define ELEMENT_NOT_FOUND -1
// 定义一个节点类
typedef struct Node {
	int data;
	struct Node* next;
}Node;
// 初始化链表的方法
Node* initList() {
	// 创建一个虚拟头节点
	Node* list = (Node*)malloc(sizeof(Node));
	// 储存链表的长度
	list->data = 0;
	list->next = NULL;
	return list;
}
// 索引越界处理方法
void outOfBounds(int index) {
	printf("索引为%d 索引越界了", index);
}
// 边界检查方法
void rangeCheck(int index, Node* list) {
	if (index < 0 || index >= list->data)
		outOfBounds(index);
}
// 针对添加方法的边界检查方法
void rangeCheckForAdd(int index, Node* list) {
	if (index < 0 || index > list->data)
		outOfBounds(index);
}

// 获取指定索引处的节点
Node* node(int index, Node* list) {
	Node* cur = list->next;
	for (int i = 0; i < index; ++i) {
		cur = cur->next;
	}
	return cur;
}
// 添加方法
void add(int index, int data, Node* list) {
	// 对参数索引进行边界检查
	rangeCheckForAdd(index, list);
	Node* pre = index == 0 ? list : node(index - 1, list);
	Node* node = (Node*)malloc(sizeof(Node));
	node->data = data;
	node->next = pre->next;
	pre->next = node;
	// 更新链表长度
	list->data++;
}
// 删除方法
int delete(int index, Node* list) {
	// 对参数索引进行边界检查
	rangeCheck(index, list);
	Node* delete;
	Node* pre = index == 0 ? list : node(index - 1, list);
	delete = pre->next;
	pre->next = delete->next;
	// 更新链表长度
	list->data--;
	// 返回被删除的节点值
	return delete->data;
}
// 查找指定节点值的位置
int indexOf(int data, Node* list) {
	Node* cur = list->next;
	for (int i = 0; i < list->data; ++i) {
		if (cur->data == data) {
			return i;
		}
		cur = cur->next;
	}
	return ELEMENT_NOT_FOUND;
}
// 获取指定位置处的节点值
int get(int index, Node* list) {
	// 在get方法中无需进行边界检查操作 因为等一下的node方法的开头就会进行边界检查的操作了
	return node(index, list)->data;
}
// 重置指定位置处的节点值
int set(int index, int newData, Node* list) {
	int data = node(index, list)->data;
	node(index, list)->data = newData;
	return data;
}
// 清空方法
void clear(Node* list) {
	Node* cur = list->next;
	Node* next;
	while (cur) {
		next = cur->next;
		free(cur);
		cur = next;
	}
	list->data = 0;
	// 不仅仅需要将链表的长度置为0 而且还需要将虚拟头节点的下一个节点置为空才行
	list->next = NULL;
}
// 是否包含指定节点值的方法
bool contains(int data, Node* list) {
	return indexOf(data, list) != ELEMENT_NOT_FOUND;
}
// 链表是否为空
bool isEmpty(Node* list) {
	return list->data == 0;
}
// 获取链表长度
int size(Node* list) {
	return list->data;
}
// 打印方法
void printList(Node* list) {
	Node* cur = list->next;
	while (cur) {
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
int main() {
	Node* list = initList();
	add(0, 1, list);
	add(0, 2, list);
	add(0, 3, list);
	add(0, 4, list);
	add(size(list), 5, list);
	printList(list);
	printf("%d\n", get(0, list));
	printf("%d\n", set(0, 6, list));
	printf("%d\n", delete(0, list));
	printList(list);
	clear(list);
	printf("%d\n", size(list));
	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

通过结果查看 顺利通过测试