前言

本篇文章介绍数据结构中的循环链表和双向链表

一、循环链表

1.1 循环链表的介绍

将单链表的形式稍作改变，单链表的最后一个结点指向第一个结点
对第一个结点概念的说明：
对于不带头结点的链表，第一个结点指首元结点（如图1.1所示）

图1.1 不带头结点

对于带头结点的链表，第一个结点指头结点（如图1.2所示）

图1.2 带头结点

本篇文章以带头结点的循环链表为研究对象
与单链表相比，循环链表没有增加新的存储空间，但是，从循环链表中任一结点出发，都能访问到所有结点。
带头结点的循环链表又有两种表示方式，分别是
头指针表示循环链表：头指针指向头结点（如图1.3所示）

图1.3 头指针表示

$$头指针表示循环单链表\{\begin{array}{l}找a_1的时间复杂度O(1)\\ 找a_n的时间复杂度O(n)\end{array}$$

尾指针表示循环链表：尾指针指向最后一个结点（如图1.4所示）

图1.4 尾指针表示

$$头指针表示循环单链表\{\begin{array}{l}{a}_1的存储位置：R\to next\to next\\ a_n的存储位置：R\\ 找a_1和a_n的时间复杂度都为O(1)\end{array}$$

1.2 循环链表的实现

这里使用带头结点的循环链表，并且使用尾指针表示循环链表。
循环链表的定义和表示

//定义返回值常量
#define SUCCESS 1
#define ERROR 0


//假设数据元素类型为char
typedef char ElemType;

//定义结点类型
struct Node;				  	
typedef struct Node* PNode;   //假设作为结点指针类型
struct Node {
	ElemType data;   //数据域
	PNode next;		//指针域
};

typedef struct Node* LinkList;  //假设作为单链表类型

1. 创建空表
   step1 使用malloc()函数创建一个sizeof(struct Node)大小的空间作为头结点
   step2 将头结点的指针域指向自身，表示一个空表

   //4.1 创建一个空表，返回头指针
   LinkList createNullList_loopLink(void)
   {
   	LinkList linkList = (LinkList)malloc(sizeof(struct Node));
   	if (NULL == linkList)
   	{
   		printf("malloc fail!\n");
   		return NULL;
   	}
   	linkList->next = linkList;  //头结点的指针域指向自身表示空表
   	return linkList;
   }
   

2. 销毁循环链表
   step1 首先从头结点开始销毁
   step2 最后销毁尾指针指向的结点

   //4.2 销毁一个循环单链表
   void destroyList_loopLink(LinkList* R)
   {
   	assert(R && *R);
   	PNode phead = (*R)->next;
   	while (phead != *R)        //销毁除了尾结点的其余结点
   	{
   		PNode q = phead->next;
   		free(phead);
   		phead = q;
   	}
   	//销毁尾结点
   	free(*R);
   	*R = NULL;
   }
   

3. 循环链表的插入
   step1 查找$a_{i-1}$的存储位置p
   step2 使用flag标记$a_{i-1}$的存储位置是否恰好为尾指针*R指向的位置
   step3 生成一个数据域为e的结点newNode
   step4 插入新结点，newNode指针域指向$a_i$，$a_{i-1}$指针域指向newNode
   step5 根据flag的值改变R的指向，flag=1，*R = newNode

   //4.5 在第i个元素之前插入数据元素e
   int insertElem_loopLink(LinkList* R, int i, ElemType e)
   {
   	assert(R && *R);
   	PNode p = (*R)->next;          //头指针
   	int j = 0;
   	int flag = 0;				//用于标记位置i-1是否恰好等于尾指针指向的结点
   	while (p != *R && j < i - 1) //寻找第i-1位置的结点
   	{
   		p = p->next;
   		j++;
   	}
   	if (j > i - 1)           //判断i是否小于1
   		return ERROR;
   	if (p == *R)			//p==R ,条件成立有两种情况，第一，i-1是否恰好等于尾指针指向；第二，i-1大于表长
   	{ 
   		if (j != i - 1)    //如果i-1大于表长，返回ERROR
   			return ERROR;
   		else               //i-1位置恰好在尾指针指向的结点
   			flag = 1;
   	}
   	//新建结点
   	PNode newNode = (PNode)malloc(sizeof(struct Node));
   	if (NULL == newNode)
   	{
   		printf("malloc fail!\n");
   		return ERROR;
   	}
   	newNode->data = e;
   	newNode->next = p->next;
   	p->next = newNode;
   	if (flag)
   		*R = newNode;
   	return SUCCESS;
   }
   

4. 循环链表的删除
   step1 查找$a_{i-1}$的存储位置$p$
   step2 保存要删除的结点存储位置$q$，即$q=p\to next$
   step3 使结点$a_{i-1}$的指针域指向$a_{i+1}$，即$p\to next=q\to next$
   step4 判断$q$的指向是否与$\ast R$的指向相同，若相同，则$\ast R=p$
   step5 free(q)，返回SUCCESS

   //4.6 删除第i个元素
   int deleteElem_loopLink(LinkList* R, int i)
   {
   	assert(R && *R);
   	PNode p = (*R)->next;
   	int j = 0;
   	while (p != *R && j < i - 1)
   	{
   		p = p->next;
   		j++;
   	}
   	if (p == *R || j > i - 1)
   		return ERROR;
   	PNode q = p->next;
   	p->next = q->next;
   	if (q == *R)  //判断删除结点是否为尾指针指向的结点
   		*R = p;
   	free(q);
   	return SUCCESS;
   }
   

5. 循环链表的建立（头插法）
   step1 新建头结点phead并将phead的指针域指向自身
   step2 定义尾指针R，并指向phead
   step3 循环新建结点，插入头结点之后
   step4 判断插入的结点是否为第一个，若是，则R = newNode
   step5 最后返回R

   //4.7 循环单链表的建立(头插法)
   //带头结点
   //返回尾指针
   LinkList createLoopLinkList_head(ElemType* element, int length)
   {
   	assert(element);
   	//创建头结点
   	LinkList phead = (LinkList)malloc(sizeof(struct Node));
   	if (NULL == phead)
   	{
   		printf("malloc fail!\n");
   		return NULL;
   	}
   	phead->next = phead;
   	PNode R = phead;  //声明尾指针
   	int i = 0;
   	for (; i < length; i++)
   	{
   		//新建结点
   		PNode newNode = (PNode)malloc(sizeof(struct Node));
   		if (NULL == newNode)
   		{
   			printf("malloc fail!\n");
   			free(phead);
   			return NULL;
   		}
   		newNode->data = element[i];
   		newNode->next = phead->next;
   		phead->next = newNode;
   		if (newNode->next == phead)              //判断是否为第一个插入结点
   		{
   			R = newNode;
   		}
   	}
   	return R;
   }
   

6. 合并两个循环链表
   step1 保存Ta的头指针
   step2 Ta的尾指针指向Tb的首元结点
   step3 释放Tb的头结点
   step4 Tb的尾指针指向Ta的头结点

   //4.8 合并两个循环单链表（Tb合并在Ta之后）
   //返回合并后的尾指针
   LinkList mergeLoopLinkList(LinkList Ta, LinkList Tb)
   {
   	if (NULL == Ta)
   		return Tb;
   	if (NULL == Tb)
   		return Ta;
   	PNode head_Ta = Ta->next;		//保存Ta的头指针
   	Ta->next = Tb->next->next;		//Ta尾指针指向Tb的首元结点
   	free(Tb->next);					//释放Ta的头结点
   	Tb->next = head_Ta;				//Tb的指针域指向Ta的头结点
   	return Tb;
   }
   

二、双向链表

…待续

总结

…待续