循环链表的实现

循环单链表的基本算法实现几乎和单链表一致，所不同的时候就是表尾的判断其中会导致 *** 作不同，所要牢记的一点是正是因为

循环单链表是一个环，所以初始化的时候next指针要指向自己，同时任何位置上的插入和删除都是等价的，无需判断是否在表尾

这里主要实现一下几个和单链表有差别的地方

循环双链表的定义

typedef int ElemType;
//为什么交cs呢circularsingle，真是取名鬼才
typedef struct CsNode
{
	ElemType data;       // 存放结点的数据元素。
	struct CsNode* next;  // 指向下一个结点的指针。
}CsNode, * CLinkList;

初始化

//初始化链表，失败返回null，成功直接返回头结点
CsNode* InitList1()
{
	CsNode* head = (CsNode*)malloc(sizeof(CsNode));  // 分配头结点。

	if (head == NULL) return NULL;  // 内存不足，返回失败。

	head->next = head;  // 头结点的next指针指向自己。 // xxx

	return head;
}

摧毁链表

//摧毁链表
void DestroyList(CLinkList LL) {
	CsNode* head = LL;
	LL = LL->next;
	CsNode* tmp;
	while (LL != head) {
		//跟单链表不一样不是到null是到头结点未结束所以要从第二个结点开始遍历
		tmp = LL;
		LL = LL->next;
		free(tmp);
		
	}
	free(head);
	return;
}

清空链表

void ClearList(CLinkList LL) {
	if (LL == NULL) {
		return;
	}
	//清空链表指的是释放所有数据节点但不包括头结点
	//所以我们指向下一个

	CsNode* tmp = LL->next;
	CsNode* tmp2;
	//保留头结点
	while (tmp->next != LL) {
		tmp2 = tmp;
		tmp = tmp->next;
		free(tmp2);
	}
	//当到头结点出来了
	//所以指向自己即可
	tmp->next=tmp;
	return;
}

插入结点

//插入结点(失败-1，成功-1)
int InsertList(CLinkList LL, int i, ElemType* ee) {
	if ((LL != NULL) || (ee != NULL)) {
		return -1;
	}
	if (i < 1) {
		return -1;
	}
	//日常记忆结点留一个
	CsNode* tmp;
	if (i = 1) {
		//这种情况下就是指向第一个数据节点，前一个就是头结点
		tmp = LL;
	}
	else {
		tmp = LL->next;//指向第一个数据节点
		int count = 1;//第一个
		while ((tmp != LL) || (count < i - 1))
		{
			//当count最后++等于i-1退出循环
			tmp = tmp->next;
			count++;
		}
		if (tmp == LL) {
			return NULL;
		}
		CsNode* tmp2 = (CsNode*)malloc(sizeof(CsNode));
		if (tmp2 == NULL) {
			return -1;
		}
		memcpy(&tmp2->data, ee, sizeof(ElemType));
		tmp2->next = tmp->next;
		tmp->next = tmp2;
		return 1;
	}
}

删除结点

//删除结点中的第i个结点,删除成功但会1，失败则是-1
	int DeleteNode(CLinkList LL, unsigned int i) {
		if (LL == NULL) {
			return -1;
		}
		if (i < 1) {
			return -1;
		}
	//记忆节点
		CsNode* tmp;
		if (i == 1) {
			tmp = LL;
		}
		else
		{
			tmp = LL->next;
			int count = 1;
			while ((tmp!=LL)&&(count<i-1)) {
				tmp = tmp->next;
				count++;
			}
		}
		if (tmp == LL)
			return -1;
		CsNode* tmp2 = tmp->next;
		tmp->next = tmp->next->next;
		free(tmp2);
		return -1;
	}

其他 *** 作基本没啥差别，其实循环单链表唯一一个要注意的即是while中的判断要最后的结点不是指向null之前停下而是指向head的时候结束，还有就是插入和删除的时候要判断，插入或者删除的地址是不是第一个地址要额外进行判断，因为其点进入不了while循环。

循环双链表的实现：

这里就不实现了，因为真的和循环单链表的 *** 作实在是太相似了

它和循环单恋表的区别

1.多了个头结点 prior指针指向前驱结点

2.初始化的时候，其头结点的 prior与 next域的值都要等于链表L，也就是都指向自己

3.尾结点的 next指针指向的是 head结点（与循环单链表一样）

4.头结点的 prior 指针指向尾结点