/*
	循环单链表的基本操作(L指向表头):
	(1)、循环单链表的定义
	(2)、循环单链表的初始化
	(3)、循环单链表的建立:
		a、头插法建立
		b、尾插法建立 
	(4)、循环单链表的插入:
		a、后插
		b、前插
		c、指定位置插入 
	(5)、循环单链表删除:
		a、按位序删
		b、前删
		c、后删 
	(6)、循环单链表查找:
		a、按位查找
		b、按值查找 
	(7)、循环单链表长度 
	(8)、循环单链表输出 


*/

#include <stdio.h>
#include <stdlib.h>

typedef struct LNode {
	int data;
	struct LNode *next;
} LNode,*ListLink;

// 循环单链表的初始化
bool initListLink(ListLink &L) {
	L = (LNode *)malloc(sizeof(LNode));
	if(!L) return false;
	L->next = L;
	return true;
}

// 头插法建立循环单链表
ListLink headCreateListLink(ListLink &L) {
	initListLink(L);
	LNode *s,*r;
	bool isFirst = true;
	int x;
	while(scanf("%d",&x) != EOF) {
		if(x == -1) break;
		s = (LNode *)malloc(sizeof(LNode));
		s->data = x;
		s->next = L->next;
		L->next = s;
		if(isFirst) {
			r = s;
			isFirst = false;
		}
	}
	r->next = L;
	return L;
}

// 尾插法建立循环单链表
ListLink tailCreateListLink(ListLink &L) {
	initListLink(L);
	LNode *s,*r = L;
	int x;
	while(scanf("%d",&x) != EOF) {
		if(x == -1) break;
		s = (LNode *)malloc(sizeof(LNode));
		s->data = x;
		r->next = s;
		r = s;
	}
	r->next = L;
	return L;
}

// 循环单链表的长度
int length(ListLink &L) {
	LNode *p = L->next;
	int len = 0;
	while(p != L) {
		len ++;
		p = p->next;
	}
	return len;
}

// 判断循环单链表是否为 NULL
bool isEmpty(ListLink &L) {
	if(L->next == L) {
		return true;
	} else {
		return false;
	}
}

// 判断节点是否为尾节点
bool isTailNode(ListLink &L,LNode *p) {
	if(p->next == L) {
		return true;
	}
	return false;
}

// 按位查找 : 查找位序是 i 的循环单链表节点
LNode *getElem(ListLink &L,int i) {
	if(i < 0) return NULL;
	if(i == 0) return L;
	LNode *p = L->next;
	int j = 1;
	while(p != L && j < i) {
		p = p->next;
		j ++;
	}
	if(p->next != L) return p;
	return NULL;
}

// 按值查找 : 返回数据域是 e 的节点
LNode * locateElem(ListLink &L,int e) {
	LNode *p = L->next;
	while(p != L && p->data != e) {
		p = p->next;
	}
	return p;
}

// 后插 : 在节点 p 后面插入数据是 e 的节点
bool insertNextNodeE(LNode *p,int e) {
	if(!p) return false;
	LNode *s;
	s = (LNode *)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

// 后插 : 在节点 p 后面插入节点 s
bool insertNextNode(LNode *p,LNode *s) {
	if(!p || !s) return false;
	s->next = p->next;
	p->next = s;
	return true;
}

// 插入 : 在第 i 个位置插入节点 e
bool insertPosition(ListLink &L,int i,int e) {
	LNode *p = getElem(L,i - 1);
	if(!p) return false;
	return insertNextNodeE(p,e);
}

// 前插操作 : 在 p 节点前插入节点 e
bool insertPriorNodeE(LNode *p,int e) {
	LNode *s;
	s = (LNode *)malloc(sizeof(LNode));
	s->next = p->next;
	p->next = s;
	s->data = p->data;
	p->data = e;
	return true;
}


// 前插操作 : 在 p 节点前插入节点 s
bool inserPrionNode(LNode *p,LNode *s) {
	if(!p || !s) return false;
	s->next = p->next;
	p->next = s;
	int temp = s->data;
	s->data = p->data;
	p->data = temp;
	return true;
}

// 删除 : 删除位序 是 i 的节点 ,e 是 i 节点的值
bool deleteNode(ListLink &L,int i,int &e) {
	LNode *p = getElem(L,i - 1);
	if(!p) return false;
	LNode *q = p->next;
	e = q->data;
	p->next = q->next;
	free(q);
	return true;
}

// 删除 : 删除指定节点 p
bool deletePositionNode(ListLink &L,LNode *p) {
	LNode *q = p->next;
	p->next = q->next;
	p->data = q->data;
	free(q);
	return true;
}


// 输出循环单链表
void print(ListLink &L) {
	LNode *p = L->next;
	while(p != L) {
		printf("%d ",p->data);
		p = p->next;
	}
	printf("\n");
	return ;
}

int main() {
	ListLink L;
	// 头插法建立循环单链表
//	headCreateListLink(L);
	// 尾插法建立循环单链表
	tailCreateListLink(L);
	// 输出循环单链表
	print(L);

	printf("--------------循环单链表的长度-------------\n");
	int len = length(L);
	printf("循环单链表的长度是: %d\n",len);

	printf("--------------判断循环单链表是否为 NULL-------------\n");
	bool empty = isEmpty(L);
	if(empty) printf("NULL\n");
	else printf("NOT NULL\n");

	printf("--------------判断节点是否为尾节点-------------\n");
	LNode *no = getElem(L,4);
	bool tailNode = isTailNode(L,no);
	if(tailNode) printf("YES\n");
	else printf("NO\n");

	printf("--------------按位查找 : 查找位序是 3 的循环单链表节点-------------\n");
	LNode *p = getElem(L,3);
	printf("按位查找 : 查找位序是 3 的循环单链表节点 %d\n",p->data);


	printf("--------------按值查找 : 返回数据域是 999 的节点-------------\n");
	LNode *q = locateElem(L,999);
	if(q->data == 999) printf("已找到节点\n");
	else printf("未找到节点!\n");

	printf("--------------后插 : 在节点 p(3) 后面插入数据是 1000 的节点-------------\n");
	print(L);
	insertNextNodeE(p,1000);
	printf("--------------后插 : 在节点 p(3) 后面插入数据是 1000 的节点 后的链表 : -------------\n");
	print(L);

	printf("--------------后插 : 在节点 p 后面插入节点 s-------------\n");
	print(L);
	LNode *s;
	s = (LNode *)malloc(sizeof(LNode));
	s->data = 888;
	insertNextNode(p,s);
	printf("--------------后插 : 在节点 p 后面插入节点 888 的节点 后的链表 :-------------\n");
	print(L);

	printf("--------------插入 : 在第 2 个位置插入节点 666-------------\n");
	print(L);
	insertPosition(L,2,666);
	printf("--------------插入 : 在第 2 个位置插入节点 666 的节点后的链表 :-------------\n");
	print(L);

	printf("--------------前插操作 : 在 n 节点前插入节点 555-------------\n");
	print(L);
	LNode *n = getElem(L,2);
	insertPriorNodeE(n,555);
	printf("--------------前插操作 : 在 n 节点前插入节点 555 的节点后的链表:-------------\n");
	print(L);

	printf("--------------前插操作 : 在 p 节点前插入节点 u(333)-------------\n");
	LNode *u;
	u = (LNode *)malloc(sizeof(LNode));
	u->data = 333;
	inserPrionNode(p,u);
	printf("--------------前插操作 : 在 p 节点前插入节点 u(333) 的节点后的链表:-------------\n");
	print(L);

	printf("--------------删除 : 删除位序 是 4 的节点 ,e 是 4 节点的值-------------\n");
	print(L);
	int e;
	deleteNode(L,4,e);
	printf("删除节点的值是 %d\n",e);
	printf("--------------删除 : 删除位序 是 4 的节点 ,e 是 4 节点的值的节点后的链表 : -------------\n");
	print(L);
	
	printf("--------------删除 : 删除指定节点 p-------------\n");
	print(L);
	deletePositionNode(L,p);
	printf("--------------删除 : 删除指定节点 p 后的链表:-------------\n");
	print(L);
	
	return 0;
}