一、双向循环链表

链表结构体

1
2
3
4
5
6
7
8
9
typedef int DataType;

//双向循环链表节点结构体声明
typedef struct Node
{
	DataType data;//数据域
	struct Node *prev;//指针域
	struct Node *next;
}linknode;

1、初始化链表

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

2、创建一个节点

1
2
3
4
5
6
7
8
9
10
11
12
// 创建一个节点
linknode *create_node(DataType data)
{
	linknode *new = malloc(sizeof(linknode));
	if(new == NULL)
		return NULL;
	
	new->next = new;
	new->prev = new;
	new->data = data;
	return new;
}

3、插入一个节点

1
2
3
4
5
6
7
8
// 插入节点
void insert_node(linknode *new, linknode *prev, linknode *next)
{
	prev->next = new;
	next->prev = new;
	new->prev = prev;
	new->next = next;
}

3.1头插

1
2
3
4
5
// 头插
void insert_head_node(linknode *new, linknode *head)
{
	insert_node(new, head, head->next);
}

3.2尾插

1
2
3
4
5
// 尾插
void insert_tail_node(linknode *new, linknode *head)
{
	insert_node(new, head->prev,head);
}

4、判断链表是否为空

1
2
3
4
bool is_empty(linknode *head)
{
	return (head->next == head) ? true : false;
}

5、遍历

5.1向后遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
// 向后遍历
void display_next_list(linknode *head)
{
	if(is_empty(head))
		return ;

	linknode *tmp = head->next;
	for(; tmp != head; tmp = tmp->next)
	{
		printf("%d->", tmp->data);
	}
	printf("\n");
}

5.2向前遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
// 向前遍历
void display_prev_list(linknode *head)
{
	if(is_empty(head))
		return ;

	linknode *tmp = head->prev;
	for(; tmp != head; tmp = tmp->prev)
	{
		printf("%d->", tmp->data);
	}
	printf("\n");
}

6、查找节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 查找节点
linknode *find_node(DataType data, linknode *head)
{
	if(is_empty(head))
		return NULL;
	
	linknode *tmp = head->next;
	for(; tmp != head; tmp = tmp->next)
	{
		if(tmp->data == data)
			return tmp;
	}
	
	return NULL;
}

7、删除节点

7.1从链表中取出一个节点

1
2
3
4
5
6
7
8
9
10
// 从链表中取出一个节点
linknode *remove_node(linknode *dnode)
{
	dnode->prev->next = dnode->next;
	dnode->next->prev = dnode->prev;
	dnode->prev = NULL;
	dnode->next = NULL;
	
	return dnode;
}

7.2传入数据删除一个节点(根据数据查找删除)

1
2
3
4
5
6
7
8
9
10
11
12
13
// 传入数据删除一个节点(根据数据查找删除)
bool delete_data_node(DataType data, linknode *head)
{
	linknode *find = NULL;
	
	find = find_node(data, head);
	if(find == NULL)
		return false;
	
	remove_node(find);
	free(find);
	return true;
}

7.3传入节点删除节点

1
2
3
4
5
6
// 传入节点删除节点
void delete_node(linknode *dnode)
{
	remove_node(dnode);
	free(dnode);
}

8、移动节点

8.1把mnode移动到next后面

1
2
3
4
5
6
// 移动节点（把mnode移动到next后面）
void move_next_node(linknode *mnode, linknode *next)
{
	remove(mnode); //先取出节点
	insert_node(mnode, next, next->next);
}

8.2把mnode移动到prev前面

1
2
3
4
5
6
// 移动节点（把mnode移动到prev前面）
void move_prev_node(linknode *mnode, linknode *prev)
{
	remove(mnode);
	insert_node(mnode, prev->prev, prev);
}

8.3把data1移动到data2后面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 移动节点
// 把data1移动到data2后面
void move_d2d(int data1, int data2, linknode *head)
{
	linknode *d1 = find_node(data1, head);
	linknode *d2 = find_node(data2, head);
	if(d1 && d2)
	{
		remove(d1);	//先把节点从链表中取出来
		insert_node(d1, d2, d2->next);
		return ;
	}
	return ;
}

9、更新数据

1
2
3
4
5
6
7
8
9
10
11
// 更新数据
void updata_node(int old, int new, linknode *head)
{
	linknode *d1 = find_node(old, head);
	if(d1 != NULL)
	{
		d1->data = new;
		return ;
	}
	return ;
}

二、接口汇总

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
typedef int DataType;
//双向循环链表节点结构体声明
typedef struct Node
{
	DataType data;//数据域
	struct Node *prev;//指针域
	struct Node *next;
}linknode;

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

// 创建一个节点
linknode *create_node(DataType data)
{
	linknode *new = malloc(sizeof(linknode));
	if(new == NULL)
		return NULL;
	
	new->next = new;
	new->prev = new;
	new->data = data;
	return new;
}

// 插入节点
void insert_node(linknode *new, linknode *prev, linknode *next)
{
	prev->next = new;
	next->prev = new;
	new->prev = prev;
	new->next = next;
}

// 尾插
void insert_tail_node(linknode *new, linknode *head)
{
	insert_node(new, head->prev,head);
}

// 头插
void insert_head_node(linknode *new, linknode *head)
{
	insert_node(new, head, head->next);
}

bool is_empty(linknode *head)
{
	return (head->next == head) ? true : false;
}

// 向后遍历
void display_next_list(linknode *head)
{
	if(is_empty(head))
		return ;
	linknode *tmp = head->next;
	for(; tmp != head; tmp = tmp->next)
	{
		printf("%d->", tmp->data);
	}
	printf("\n");
}

// 向前遍历
void display_prev_list(linknode *head)
{
	if(is_empty(head))
		return ;
	linknode *tmp = head->prev;
	for(; tmp != head; tmp = tmp->prev)
	{
		printf("%d->", tmp->data);
	}
	printf("\n");
}

// 查找节点
linknode *find_node(DataType data, linknode *head)
{
	if(is_empty(head))
		return NULL;
	
	linknode *tmp = head->next;
	for(; tmp != head; tmp = tmp->next)
	{
		if(tmp->data == data)
			return tmp;
	}
	
	return NULL;
}

// 从链表中取出一个节点
linknode *remove_node(linknode *dnode)
{
	dnode->prev->next = dnode->next;
	dnode->next->prev = dnode->prev;
	dnode->prev = NULL;
	dnode->next = NULL;
	
	return dnode;
}

// 传入数据删除一个节点(根据数据查找删除)
bool delete_data_node(DataType data, linknode *head)
{
	linknode *find = NULL;
	
	find = find_node(data, head);
	if(find == NULL)
		return false;
	
	remove_node(find);
	free(find);
	return true;
}

// 传入节点删除节点
void delete_node(linknode *dnode)
{
	remove_node(dnode);
	free(dnode);
}

// 移动节点（把mnode移动到next后面）
void move_next_node(linknode *mnode, linknode *next)
{
	remove(mnode); //先取出节点
	insert_node(mnode, next, next->next);
}

// 移动节点（把mnode移动到prev前面）
void move_prev_node(linknode *mnode, linknode *prev)
{
	remove(mnode);
	insert_node(mnode, prev->prev, prev);
}

// 移动节点
// 把data1移动到data2后面
void move_d2d(int data1, int data2, linknode *head)
{
	linknode *d1 = find_node(data1, head);
	linknode *d2 = find_node(data2, head);
	if(d1 && d2)
	{
		remove(d1);	//先把节点从链表中取出来
		insert_node(d1, d2, d2->next);
		return ;
	}
	return ;
}

// 更新数据
void updata_node(int old, int new, linknode *head)
{
	linknode *d1 = find_node(old, head);
	if(d1 != NULL)
	{
		d1->data = new;
		return ;
	}
	return ;
}