大兴网站建设首选公司,泉州市建设局网站,网站建设管理工作总结,站长之家ip查询工具循环链表与静态链表 导言一、循环链表1.1 循环单链表1.2 循环双链表 二、静态链表2.1 静态链表的创建2.2 静态链表的初始化2.3 小结 结语 导言
大家好#xff01;很高兴又和大家见面啦#xff01;#xff01;#xff01;
经过前面的介绍#xff0c;相信大家对链式家族的… 循环链表与静态链表 导言一、循环链表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;elsereturn false;
}不管是单链表还是循环单链表它们的插入、删除是一致的唯一的区别就是我们在对表尾结点的处理上会有差异
单链表的表尾结点的指针域判断指向的是NULL循环单链表的表尾结点的指针域判断指向的是L
用C语言来表式则是
//循环链表的表尾结点判断
bool isTail(LinkList L,LNode* p)
{assert(L p);//当指针L与指针p其中一个为空指针时报错if (p-next L)return true;//当结点p的后继指针指向L时表明此时的结点p为表尾结点elsereturn false;//当它们不相等时表明此时的结点p不是表尾结点
}我们在对单链表进行遍历时只能是从头结点开始往后进行遍历但是在循环链表中我们可以从任意结点往后遍历用C语言来表示的话我们则可以写成
//循环链表的遍历
bool Ergodic(LNode* p)
{assert(p);//当p为空指针时报错LNode* r p-next;//进行遍历的指针rwhile (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;elsereturn false;
}这里一定要注意如果仅仅判断头结点的前驱指针与后继指针相等的话是不能确定是否为空表的如下所示 当双链表中有一个元素时此时这个元素所在的结点既是表头结点又是表尾结点因此在这种情况下循环双链表的头结点的前驱指针与后继指针都是指向这个结点的所以在对循环双链表进行判空时一定要判断是否等于头指针
循环双链表的其它变化与循环单链表类似这里我就不再重复说明了大家可以好好消化一下
二、静态链表
静态链表我们可以理解为时顺序表与单链表的一个结合体。
静态链表是通过数组来描述线性表的链式存储结构链表中的结点结构与单链表一致都是由数据域与指针与构成
但是不同的是静态链表中的结点的指针域存储的是结点的相对地址也就是在数组中的下标这里我们将它称为游标如下所示 由图可知静态链表在内存中也是需要先申请一块连续的空间对应的数组下标表示的是链表中的各个元素在物理位置上的关系而游标表示的是链表中各个元素在逻辑上的关系。
在静态链表中下标为0的元素被作为静态链表的头结点它的数据域中可以不用存放信息它的游标存放的是链表首元素的数组下标
虽然静态链表是申请的一块连续的空间但是表中的各个元素与单链表相同不需要满足物理位置上相邻只需要满足逻辑上相邻即可
因此对于静态链表而言它也是不能进行随机存取的要访问各个元素的话只能通过从头结点开始往后访问
2.1 静态链表的创建
我们要创建一个静态链表的话我们就可以像创建一个静态顺序表一样如下所示
//静态链表的创建格式
#define MaxSize 10//静态链表的最大表长
typedef struct SLinkList {ElemType data;//数据域int next;//指针域——游标
}SLinkList[MaxSize];
//静态链表的类型为结构体数组类型
//SLinkList——重命名后的类型名
//MaxSize——链表的最大表长不可修改
//SLinkListstruct SLinkList [MaxSize]
int main()
{SLinkList a;//定义一个静态链表astruct 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——链表的最大表长不可修改
//SLinkListstruct 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;//定义一个静态链表astruct SLinkList b[MaxSize];//定义一个静态链表b//两种定义方式都是可以的if (InitSLinkList(a))//a为数组名因此我们在传参时只需要传入数组名就可以了{Print_SLinkList(a);}return 0;
}我们来看一下测试结果 当我们要对其进行插入或删除元素时需要从头结点开始通过修改对应结点的游标来进行插入或者删除操作这里我就不进行演示了有兴趣的朋友可以自己下去试着编写一下对应的代码
2.3 小结
对于静态链表我们需要掌握以下内容
静态链表时通过数组实现的一个单链表在静态链表中下标为0的首元素作为静态链表的头结点数据域中不需要存放任何内容与静态顺序表一致静态链表的大小是不可改变的与单链表一致静态链表不支持随机存取只能从头结点开始往后查找静态链表中的指针域存储的是下一个元素的数组下标我们通过游标-1来表示链表的表尾结点为了避免静态链表中未使用的空间的游标存储的是随机值我们需要对其初始化为-2静态链表的插入与删除操作与单链表的插入删除操作相同只需要修改指针不需要移动元素静态链表适用于一些不支持指针的高级语言如Basic静态链表还适用于数据元素数量固定不变的场景如操作系统中的文件分配表FAT
结语
今天的内容到这里就全部结束了有了顺序表、单链表与双链表这些知识点的基础对于循环链表与静态链表的理解上就会相对容易一点希望大家能够通过今天的内容强化对链表相关知识点的理解与使用。
在下一篇内容中我们将对顺序表与链表的相关知识点做个回顾、对比与总结大家记得关注哦
最后感谢大家的翻阅咱们下一篇再见
