【数据结构】链式家族的成员——循环链表与静态链表

循环链表与静态链表

导言
一、循环链表
- 1.1 循环单链表
- 1.2 循环双链表
二、静态链表
- 2.1 静态链表的创建
- 2.2 静态链表的初始化
- 2.3 小结
结语

导言

大家好！很高兴又和大家见面啦！！！

经过前面的介绍，相信大家对链式家族的成员——单链表与双链表的相关内容都已经熟练掌握了。前面我们重点介绍了通过C语言来实现单链表与双链表的一些基本操作，希望大家私下能够多多练习一下，帮助自己去吸收消化这些内容。

在今天的篇章中，我们要介绍的是线性表的链式存储另外两个成员——循环链表与静态链表，有了单链表与双链表的基础，相信大家应该能够很容易理解今天的内容。接下来我们就来一起看看吧！

一、循环链表

在前面介绍的单链表和双链表中，我们会发现，不管是单链表的表尾结点还是双链表的头结点和表尾结点，它们在创建好后指向的内容都是空指针，如下图所示：
单链表与双链表
正因为这种存储结构，导致我们在处理表头元素、表尾元素与表中元素时会有些许的差异，比如：

在双链表中，我们采用后插法插入元素时，就需要判断该结点的后继结点是否为空指针；
在单链表中，如果我们需要找到结点的前驱结点，我们只能通过从表头元素开始查找；

为了完善单链表与双链表的缺点，我们就可以将单链表与双链表做一个调整，如下所示：

循环链表

我们将单链表的表尾结点的指针域指向了头结点；
将双链表的表尾指针的后继指针指向了头结点，将双链表的头结点的前驱指针指向了表尾结点；

经过这个调整后我们会发现，此时的单链表和双链表都闭合起来了，这样闭合的链表我们将其称为循环链表。接下来我们就来分别介绍一下这两种循环链表相比于之前的改动；

1.1 循环单链表

循环单链表也就是表尾结点的指针域指向的是单链表的第一个结点，而头指针指向的也是单链表的第一个结点，所以我们可以认为，在循环单链表中，表尾结点的指针域指向的是头指针L。

正因为这个点所以在对循环单链表进行判空操作时我们就有了一个改动：

由原先的判断头结点的指针域指向指向的是不是NULL，改为指向的是不是L；

用C语言来表示则是：

//循环单链表的判空
bool Empty(LinkList L)
{
	assert(L);//当指针L为空指针时报错
	if (L->next == L)
		return true;
	else
		return false;
}

不管是单链表还是循环单链表，它们的插入、删除是一致的，唯一的区别就是，我们在对表尾结点的处理上会有差异：

单链表的表尾结点的指针域判断指向的是NULL；
循环单链表的表尾结点的指针域判断指向的是L；

用C语言来表式则是：

//循环链表的表尾结点判断
bool isTail(LinkList L,LNode* p)
{
	assert(L && p);//当指针L与指针p其中一个为空指针时报错
	if (p->next == L)
		return true;//当结点p的后继指针指向L时表明此时的结点p为表尾结点
	else
		return false;//当它们不相等时表明此时的结点p不是表尾结点
}

我们在对单链表进行遍历时，只能是从头结点开始往后进行遍历，但是在循环链表中，我们可以从任意结点往后遍历，用C语言来表示的话我们则可以写成：

//循环链表的遍历
bool Ergodic(LNode* p)
{
	assert(p);//当p为空指针时报错
	LNode* r = p->next;//进行遍历的指针r
	while (r->next != p)//判断结点r的指针域是否指向结点p
	{
		r = r->next;//往后进行遍历
	}
	return true;//完成遍历返回true
}

在单链表中，我们要想从头结点找到表尾结点的话，我们需要从头开始进行遍历，此时的时间复杂度为O(n)；但是在循环链表中，我们如果想通过表尾结点找到头结点的话，此时的时间复杂度则为O(1)。

由这个点，我们如果想对头结点或者表尾结点进行一些操作的话，我们则可以设置表尾指针r，这样我们就可以通过表尾指针来找到头指针，用C语言表示则是r->next即为头指针，这样我们要对表尾结点或者头结点进行插入或者删除元素的时间复杂度都是O(1)；

注：通过设置表尾指针对头结点或者表尾结点完成插入或删除操作后，需要对指针r指向的内容进行修改。

1.2 循环双链表

循环双链表也就是表尾结点的后继指针指向了链表的第一个结点，而链表第一个结点的前驱指针指向了表尾结点。因此如果我们要对循环双链表进行判空操作时，我们只需要判断第一个结点的后继指针与前驱指针是否相等并且都等于头指针。

用C语言表示则是：

//循环双链表的判空操作
bool Empty(DLinkList L)
{
	assert(L);//当L为空指针时报错
	if (L->prior == L->next && L->prior == L)//判断前驱指针与后继指针是否都等于头指针
		return true;
	else
		return false;
}

这里一定要注意如果仅仅判断头结点的前驱指针与后继指针相等的话，是不能确定是否为空表的，如下所示：

当双链表中有一个元素时，此时这个元素所在的结点既是表头结点又是表尾结点，因此在这种情况下循环双链表的头结点的前驱指针与后继指针都是指向这个结点的，所以在对循环双链表进行判空时一定要判断是否等于头指针；

循环双链表的其它变化与循环单链表类似，这里我就不再重复说明了，大家可以好好消化一下；

二、静态链表

静态链表我们可以理解为时顺序表与单链表的一个结合体。

静态链表是通过数组来描述线性表的链式存储结构，链表中的结点结构与单链表一致，都是由数据域与指针与构成；

但是不同的是，静态链表中的结点的指针域存储的是结点的相对地址，也就是在数组中的下标，这里我们将它称为游标，如下所示：

由图可知，静态链表在内存中也是需要先申请一块连续的空间，对应的数组下标表示的是链表中的各个元素在物理位置上的关系，而游标表示的是链表中各个元素在逻辑上的关系。

在静态链表中，下标为0的元素被作为静态链表的头结点，它的数据域中可以不用存放信息，它的游标存放的是链表首元素的数组下标；

虽然静态链表是申请的一块连续的空间，但是表中的各个元素与单链表相同，不需要满足物理位置上相邻，只需要满足逻辑上相邻即可；

因此对于静态链表而言，它也是不能进行随机存取的，要访问各个元素的话只能通过从头结点开始往后访问；

2.1 静态链表的创建

我们要创建一个静态链表的话，我们就可以像创建一个静态顺序表一样，如下所示：

//静态链表的创建格式
#define MaxSize 10//静态链表的最大表长
typedef struct SLinkList {
	ElemType data;//数据域
	int next;//指针域——游标
}SLinkList[MaxSize];
//静态链表的类型为结构体数组类型
//SLinkList——重命名后的类型名
//MaxSize——链表的最大表长，不可修改
//SLinkList<==>struct SLinkList [MaxSize]
int main()
{
	SLinkList a;//定义一个静态链表a
	struct SLinkList b[MaxSize];//定义一个静态链表b
	//两种定义方式都是可以的
	return 0;
}

因为静态链表是通过数组实现的一个单链表，因此数组内的元素类型都是结构体类型，所以静态链表的实质是一个结构体数组。

这里对typedef的使用，实质上就是对数组类型的重命名的使用，有兴趣的朋友可以回看一下【C语言必学知识点五】指针中的typedef的使用，这里我有介绍通过typedef对函数指针类型进行重命名，这里的对数组类型进行重命名也是同理，如下所示：
数组类型重命名
我们在声明静态链表的数据类型时实质上是在声明一个结构体类型的数组，这里的静态链表类型定义等价于先定义一个结构体，再将该结构体对应的数组类型通过typedef重命名，如下所示：

//静态链表的创建
#define MaxSize 10//静态链表的最大表长
typedef struct SLinkList {
	ElemType data;//数据域
	int next;//指针域——游标
};//声明结构体类型
typedef struct SLinkList SLinkList[MaxSize];
//struct SLinkList[MaxSize]——数组类型
//通过typedef将数组类型重命名为SLinkList

这个内容我们就先介绍到这里，接下来我们来看一下静态链表的初始化；

2.2 静态链表的初始化

有看过【函数栈帧的创建与销毁】的朋友应该就会知道，我们在内存中申请空间时，申请的空间中会有一些初始的数据，这些初始数据如果我们将它们打印出来的会，会是一些随机的数据，因此为了避免我们创建的静态链表中存在这些随机值，所以我们要对其进行初始化。

由于游标存储的是各个元素的数组下标，数组的下标是从0开始依次递增，我们可以通过将表尾结点的游标设置为-1，来表示这个结点为表尾结点，同样的，我们在对其进行初始化时，可以将其设为-2，来表示此时的空间未被使用，如下所示：

//静态链表的初始化格式
bool InitSLinkList(SLinkList a)
{
	assert(a);//当a为空指针时报错
	for (int i = 0; i < MaxSize; i++)
	{
		(a + i)->data = 0;//初始化数据域
		(a + i)->next = -2;//初始化游标
	}
	return true;
}

下面我们来测试一下初始化这个功能，这里我们还是以整型数据元素为例子，代码如下所示：

//静态链表的创建
#define MaxSize 10//静态链表的最大表长
typedef struct SLinkList {
	int data;//数据域
	int next;//指针域——游标
}SLinkList[MaxSize];
//静态链表的类型为结构体数组类型
//SLinkList——重命名后的类型名
//MaxSize——链表的最大表长，不可修改
//SLinkList<==>struct SLinkList [MaxSize]
//静态链表的初始化
bool InitSLinkList(SLinkList a)
{
	assert(a);//当a为空指针时报错
	for (int i = 0; i < MaxSize; i++)
	{
		(a + i)->data = 0;//初始化数据域
		(a + i)->next = -2;//初始化游标
	}
	return true;
}
//打印静态链表
void Print_SLinkList(SLinkList a)
{
	printf("\n打印静态链表的各个元素的数据:>");
	for (int i = 0; i < MaxSize; i++)
		printf("%2d ", (a + i)->data);
	printf("\n打印静态链表的各个元素的游标:>");
	for (int i = 0; i < MaxSize; i++)
		printf("%2d ", (a + i)->next);
	printf("\n");
}
int main()
{
	SLinkList a;//定义一个静态链表a
	struct SLinkList b[MaxSize];//定义一个静态链表b
	//两种定义方式都是可以的
	if (InitSLinkList(a))//a为数组名，因此我们在传参时只需要传入数组名就可以了
	{
		Print_SLinkList(a);
	}
	return 0;
}