二、单向循环链表

链表结构体

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

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 = head;
		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 = new;
		return new;
	}
	return new;
}

3、尾插

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

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 != head; 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 != head; 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 != head; 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 != head; 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 != head; 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 != head)
	{
		if(move_node(data1, fnode, head) == 0)
		{
			return true;
		}
		else
			return false;
	}
	return false;
}

10、查找节点

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 != head; tmp=tmp->next)
	{
		if(tmp->data == data)
			return tmp;
	}
	return tmp;
}

11、判断空链表

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

	return false;
}

12、销毁链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 销毁链表
// 反馈空地址，给到链表的头节点，防止内存泄漏
struct Node * destroy_list(struct Node *head)
{
	if(is_empty(head))
		return NULL;
	
	struct Node *tmp1 = head->next;
	struct Node *tmp2 = head;
	for(; tmp1!=head; tmp1=tmp2->next)
	{
		free(tmp2);
		tmp2 = tmp1;
	}
	free(tmp2);
	return NULL;
}

图片#100%