单向循环链表

单向循环链表就是单向链表基础上，最后一个节点的next指针指向头节点，形成一个环，方便从链尾再次遍历到链头，和单链表相比就是能通过循环一圈找到前面节点的地址，而不用借助头节点。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//单向循环链表
#define DEBUG_PRINTF

typedef int datatype;
typedef enum{
	false = 0,
	true = 1
}bool;

//设计节点
typedef struct slist{
	datatype  id;
	struct slist *next;
}L;
 
/*判断链表是否为空
true is empty
false is't empty
*/
bool list_is_empty(L * p)
{
	if(p->next == p)
		return true;
	return false;
}

/*创建一个节点 
success return p 
fail    return null
*/
L *create_slist(datatype data)
{

	L * p = malloc(sizeof(L)); //分配空间

	if(p == NULL)
	{
		#ifdef DEBUG_PRINTF
		printf("malloc error\n");
		#endif
		return NULL;
	}
	memset(p,0,sizeof(L));
	p->id = data;
	p->next = p;//注意是指向头节点自己
	return p;
}

//直接在链表最后位置插入一个节点new
//pH是头节点
bool tail_insert(L *pH,L *new)
{
	if(pH == NULL || new == NULL)
		return false;
		
	//获取当前位置
	L * p = pH;
	while(p->next != pH)
	{  //当前位置下一个节点不为空则移动到下一个节点
		p = p->next;
	}
	//循环跳出，则p->next == pH
	new->next = p->next;//
	p->next = new;//
	return true;
}

//在链表pH节点后插入一个节点new
bool node_insert(L *m,L *new)
{
	if(m == NULL || new == NULL)
		return false;
	
	new->next = m->next;
	m->next = new;
	return true;
}

//删除一个节点
bool delete_node(L *delete,int is_free)
{
	if(delete == NULL)
		return false;
	
	L *p = delete; //从delete开始找
	while(p->next != delete)
	{   //当前位置的下一个位置不为delete则绕一圈找到delete前节点
		p = p->next;
	}
	//循环跳出，则p->next == delete
	p->next = delete->next;
	delete->next == NULL;
	if(is_free) //如果要释放
	{
		free(delete);
		delete = NULL;
	}
	return true;
}

/*
移动一个节点
1.删除一个节点(不释放)
2.插入一个节点
*/
bool move_node(L * pH,L * m,L * a,int is_tail)
{
	if(pH == NULL || m == NULL)
		return false;
	
	//1.删除m节点(不释放)
	if(delete_node(m,0) == false)
		return false;	
	
	if(is_tail) //如果是直接移动m到链尾
	{
        //2.直接在链尾插入
        return tail_insert(pH,m);			
	}
	else //移动一个节点m节点到节点a之后
	{
		if(a == NULL) return false;
		
		//2.在链表a节点后插入m节点
		return node_insert(a,m);		
	}
}

//根据数据查找节点
L * find_node(L * pH,datatype data)
{
	if(pH == NULL)
		return NULL; 
	if(list_is_empty(pH) == true)
		return NULL; //空就直接返回NULL
	L * p;
	for(p=pH->next ; p != pH ; p=p->next)
	{
		if(data == p->id)
			break;
	}
	return p == pH ? NULL:p;//p==pH说明找不到,则返回null
}
/*分割成已逆序和未逆序2部分，
把未逆序的第一个节点插入已逆序的头节点之后*/
void revert_node(L *pH)
{
	L * p = pH->next;//未逆序
	
	pH->next = pH;//已逆序
	L * tmp;//标记未逆序
	while(p != pH)
	{
		tmp = p->next;
		
		p->next = pH->next;
		pH->next = p;
		
		p = tmp;
	}
}

void show_node(L * pH)
{
	//if(list_is_empty(pH) == true)
	//	return; //空就直接返回NULL
	
	L*p = pH->next;//第一个node位置
	int i=0;
	while(p != pH)
	{
		printf("addr:%p{id:%d next:%p}\n",p,p->id,p->next);
		//printf("%s%d",i==0?"":" -->",p->id);
		p = p->next;
		i++;
	}
	if(p == pH)//打印头节点
	  printf("addr:%p{id:header next:%p}\n",p,p->next);
	printf("\n");
}

int main()
{
	int i;
	L *header = create_slist(0);
	show_node(header); //1~10
	for(i=1;i<=10;i++)
	{
		tail_insert(header,create_slist(i));
	}
	show_node(header); //1~10
	
	delete_node(find_node(header,5),0);
	show_node(header);//1~4 6~10
	
	node_insert(find_node(header,4),create_slist(5));
	show_node(header);//1~10
	
	move_node(header,find_node(header,4),find_node(header,5),0);
	show_node(header);//4移到5后
	
	move_node(header,find_node(header,4),find_node(header,5),1);
	show_node(header);//4移到最后
	
	delete_node(find_node(header,4),1);
	show_node(header);//4删除并释放
	
	revert_node(header);
	show_node(header);//逆序
	printf("\n\n\n");
	
	return 0;
}

下面是地址打印输出

addr:0x9445008{id:header next:0x9445008} 头节点

addr:0x9445018{id:1 next:0x9445028}
addr:0x9445028{id:2 next:0x9445038}
addr:0x9445038{id:3 next:0x9445048}
addr:0x9445048{id:4 next:0x9445058}
addr:0x9445058{id:5 next:0x9445068}
addr:0x9445068{id:6 next:0x9445078}
addr:0x9445078{id:7 next:0x9445088}
addr:0x9445088{id:8 next:0x9445098}
addr:0x9445098{id:9 next:0x94450a8}
addr:0x94450a8{id:10 next:0x9445008}
addr:0x9445008{id:header next:0x9445018} 头节点

addr:0x9445018{id:1 next:0x9445028}
addr:0x9445028{id:2 next:0x9445038}
addr:0x9445038{id:3 next:0x9445048}
addr:0x9445048{id:4 next:0x9445068}
addr:0x9445068{id:6 next:0x9445078}
addr:0x9445078{id:7 next:0x9445088}
addr:0x9445088{id:8 next:0x9445098}
addr:0x9445098{id:9 next:0x94450a8}
addr:0x94450a8{id:10 next:0x9445008}
addr:0x9445008{id:header next:0x9445018}

addr:0x9445018{id:1 next:0x9445028}
addr:0x9445028{id:2 next:0x9445038}
addr:0x9445038{id:3 next:0x9445048}
addr:0x9445048{id:4 next:0x94450b8}
addr:0x94450b8{id:5 next:0x9445068}
addr:0x9445068{id:6 next:0x9445078}
addr:0x9445078{id:7 next:0x9445088}
addr:0x9445088{id:8 next:0x9445098}
addr:0x9445098{id:9 next:0x94450a8}
addr:0x94450a8{id:10 next:0x9445008}
addr:0x9445008{id:header next:0x9445018}

addr:0x9445018{id:1 next:0x9445028}
addr:0x9445028{id:2 next:0x9445038}
addr:0x9445038{id:3 next:0x94450b8}
addr:0x94450b8{id:5 next:0x9445048}
addr:0x9445048{id:4 next:0x9445068}
addr:0x9445068{id:6 next:0x9445078}
addr:0x9445078{id:7 next:0x9445088}
addr:0x9445088{id:8 next:0x9445098}
addr:0x9445098{id:9 next:0x94450a8}
addr:0x94450a8{id:10 next:0x9445008}
addr:0x9445008{id:header next:0x9445018}

addr:0x9445018{id:1 next:0x9445028}
addr:0x9445028{id:2 next:0x9445038}
addr:0x9445038{id:3 next:0x94450b8}
addr:0x94450b8{id:5 next:0x9445068}
addr:0x9445068{id:6 next:0x9445078}
addr:0x9445078{id:7 next:0x9445088}
addr:0x9445088{id:8 next:0x9445098}
addr:0x9445098{id:9 next:0x94450a8}
addr:0x94450a8{id:10 next:0x9445048}
addr:0x9445048{id:4 next:0x9445008}
addr:0x9445008{id:header next:0x9445018}

addr:0x9445018{id:1 next:0x9445028}
addr:0x9445028{id:2 next:0x9445038}
addr:0x9445038{id:3 next:0x94450b8}
addr:0x94450b8{id:5 next:0x9445068}
addr:0x9445068{id:6 next:0x9445078}
addr:0x9445078{id:7 next:0x9445088}
addr:0x9445088{id:8 next:0x9445098}
addr:0x9445098{id:9 next:0x94450a8}
addr:0x94450a8{id:10 next:0x9445008}
addr:0x9445008{id:header next:0x9445018}

addr:0x94450a8{id:10 next:0x9445098}
addr:0x9445098{id:9 next:0x9445088}
addr:0x9445088{id:8 next:0x9445078}
addr:0x9445078{id:7 next:0x9445068}
addr:0x9445068{id:6 next:0x94450b8}
addr:0x94450b8{id:5 next:0x9445038}
addr:0x9445038{id:3 next:0x9445028}
addr:0x9445028{id:2 next:0x9445018}
addr:0x9445018{id:1 next:0x9445008}
addr:0x9445008{id:header next:0x94450a8}