一、单向链表

链表结构体

1
2
3
4
5
6
typedef int DataType;
typedef struct Node
{
    DataType data;//数据域
    struct Node *next;//指针域
}linknode;

1、初始化链表

1
2
3
4
5
6
7
8
9
10
// 初始化链表
struct Node *init_list(void)
{
	struct Node *head = malloc(sizeof(struct Node));
	if(head != NULL) {
		head->next = NULL;
		return head;
	}
	return head;
}

2、创建一个节点

1
2
3
4
5
6
7
8
9
10
11
// 创建一个新节点
struct Node *create_node(DataType data)
{
	struct Node *new = malloc(sizeof(struct Node));
	if(new != NULL) {
		new->data = data;	// 类型都是DataType， 可以直接赋值
		new->next = NULL;
		return new;
	}
	return new;
}

3、在链表的尾部添加一个节点

1
2
3
4
5
6
7
8
9
10
11
// 在链表的尾部添加一个节点
void insert_tail(struct Node *new, struct Node *head)
{
	struct Node * tmp = head;
	// 1. 找到链表末尾
	while(tmp->next != NULL)
		tmp = tmp->next;
	
	// 2. 把新节点添加到末尾
	tmp->next = new;
}

4、在链表头部添加一个新节点

1
2
3
4
5
6
// 在链表头部添加一个新节点
void insert_head(struct Node *new, struct Node *head)
{
	new->next = head->next;
	head->next = new;
}

5、遍历链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 遍历函数
void display_list(struct Node *head)
{
	if(is_empty(head))
		return ;
	
	struct Node * tmp = head->next;
		
	// 遍历这个链表
	for(; tmp != NULL; tmp=tmp->next)
	{
		fprintf(stdout, "%d->", tmp->data);
	}
	fprintf(stdout, "\n");
}

6、查找节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 查找节点
struct Node *find_node(int data, struct Node *head)
{
	if(is_empty(head))
		return NULL;
	
	struct Node * tmp = head->next;
	
	// 遍历这个链表
	for(; tmp != NULL; tmp=tmp->next)
	{
		if(tmp->data == data)
			return tmp;
	}
	return tmp;
}

7、删除节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 删除节点
bool delete_node(int data, struct Node *head)
{
	if(is_empty(head))
		return false;
	
	struct Node * tmp = head;
	struct Node *dnode = NULL;
	
	// 遍历这个链表
	for(; tmp->next != NULL; tmp=tmp->next)
	{
		dnode = tmp->next;
		if(dnode->data == data)
		{
			tmp->next = dnode->next;
			free(dnode);
			return true;
		}
	}
	return false;
}

8、更新节点数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 更新节点数据
bool updeta_node(int olddata, int newdata, struct Node *head)
{
	if(is_empty(head))
		return false;
	
	struct Node * tmp = head->next;
	
	// 遍历这个链表
	for(; tmp != NULL; tmp=tmp->next)
	{
		if(tmp->data == olddata)
		{
			tmp->data = newdata;
			return true;
		}
	}
	return false;
}

9.1、移动节点 (把data所在的节点，移动到n节点之后)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 移动节点
// 把data所在的节点，移动到n节点之后
bool move_node(int data, struct Node *n, struct Node *head)
{
	if(is_empty(head))
		return false;
	
	struct Node * tmp = head;
	struct Node *mnode = NULL;
	
	// 遍历这个链表
	for(; tmp->next != NULL; tmp=tmp->next)
	{
		mnode = tmp->next;
		if(mnode->data == data)
		{
			tmp->next = mnode->next;
			insert_head(mnode, n);
			return true;
		}
	}
	return false;
}

9.2、移动节点 (把data1移动到data2之后)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 把data1移动到data2之后
bool move_d2d(int data1, int data2, struct Node *head)
{
	struct Node *fnode = find_node(data2, head);
	if(fnode != NULL)
	{
		if(move_node(data1, fnode, head) == 0)
		{
			return true;
		}
		else
			return false;
	}
	return false;
}

10、判断空链表

1
2
3
4
5
6
7
8
// 判断空链表
bool is_empty(struct Node *head)
{
	if(head == NULL || head->next == NULL)
		return true;

	return false;
}

11、销毁链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 销毁链表
// 反馈空地址，给到链表的头节点，防止内存泄漏
struct Node * destroy_list(struct Node *head)
{
	if(is_empty(head))
		return NULL;
	
	struct Node *tmp = head->next;
	for(; tmp!=NULL; tmp=head->next)
	{
		free(head);
		head = tmp;
	}
	free(head);
	return 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
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
typedef int DataType;
struct Node
{
    DataType data;//数据域
    struct Node *next;//指针域
}linknode;

// 初始化链表
struct Node *init_list(void)
{
	struct Node *head = malloc(sizeof(struct Node));
	if(head != NULL) {
		head->next = NULL;
		return head;
	}
	return head;
}

// 创建一个新节点
struct Node *create_node(DataType data)
{
	struct Node *new = malloc(sizeof(struct Node));
	if(new != NULL) {
		new->data = data;	// 类型都是DataType， 可以直接赋值
		new->next = NULL;
		return new;
	}
	return new;
}

// 判断空链表
bool is_empty(struct Node *head)
{
	if(head == NULL || head->next == NULL)
		return true;
	return false;
}

// 在链表的尾部添加一个节点
void insert_tail(struct Node *new, struct Node *head)
{
	struct Node * tmp = head;
	// 1. 找到链表末尾
	while(tmp->next != NULL)
		tmp = tmp->next;
	
	// 2. 把新节点添加到末尾
	tmp->next = new;
}

// 在链表头部添加一个新节点
void insert_head(struct Node *new, struct Node *head)
{
	new->next = head->next;
	head->next = new;
}

// 遍历函数
void display_list(struct Node *head)
{
	if(is_empty(head))
		return ;
	
	struct Node * tmp = head->next;
		
	// 遍历这个链表
	for(; tmp != NULL; tmp=tmp->next)
	{
		fprintf(stdout, "%d->", tmp->data);
	}
	fprintf(stdout, "\n");
}

// 查找节点
struct Node *find_node(int data, struct Node *head)
{
	if(is_empty(head))
		return NULL;
	
	struct Node * tmp = head->next;
	
	// 遍历这个链表
	for(; tmp != NULL; tmp=tmp->next)
	{
		if(tmp->data == data)
			return tmp;
	}
	return tmp;
}

// 删除节点
bool delete_node(int data, struct Node *head)
{
	if(is_empty(head))
		return false;
	
	struct Node * tmp = head;
	struct Node *dnode = NULL;
	
	// 遍历这个链表
	for(; tmp->next != NULL; tmp=tmp->next)
	{
		dnode = tmp->next;
		if(dnode->data == data)
		{
			tmp->next = dnode->next;
			free(dnode);
			return true;
		}
	}
	return false;
}

// 更新节点数据
bool updeta_node(int olddata, int newdata, struct Node *head)
{
	if(is_empty(head))
		return false;
	
	struct Node * tmp = head->next;
	
	// 遍历这个链表
	for(; tmp != NULL; tmp=tmp->next)
	{
		if(tmp->data == olddata)
		{
			tmp->data = newdata;
			return true;
		}
	}
	return false;
}

// 移动节点
// 把data所在的节点，移动到n节点之后
bool move_node(int data, struct Node *n, struct Node *head)
{
	if(is_empty(head))
		return false;
	
	struct Node * tmp = head;
	struct Node *mnode = NULL;
	
	// 遍历这个链表
	for(; tmp->next != NULL; tmp=tmp->next)
	{
		mnode = tmp->next;
		if(mnode->data == data)
		{
			tmp->next = mnode->next;
			insert_head(mnode, n);
			return true;
		}
	}
	return false;
}

// 把data1移动到data2之后
bool move_d2d(int data1, int data2, struct Node *head)
{
	struct Node *fnode = find_node(data2, head);
	if(fnode != NULL)
	{
		if(move_node(data1, fnode, head) == 0)
		{
			return true;
		}
		else
			return false;
	}
	return false;
}

// 销毁链表
// 反馈空地址，给到链表的头节点，防止内存泄漏
struct Node * destroy_list(struct Node *head)
{
	if(is_empty(head))
		return NULL;
	
	struct Node *tmp = head->next;
	for(; tmp!=NULL; tmp=head->next)
	{
		free(head);
		head = tmp;
	}
	free(head);
	return NULL;
}