循环链表是首尾相连的单链表

计算机专业基础知识要点及习题第一章概论数据就是指能够被计算机识别、存储和加工处理的信息的载体。

数据元素是数据的基本单位，可以由若干个数据项组成。

数据项是具有独立含义的最小标识单位。

数据结构的定义：·逻辑结构：从逻辑结构上描述数据，独立于计算机。

·线性结构：一对一关系。

·线性结构：多对多关系。

·存储结构：是逻辑结构用计算机语言的实现。

·顺序存储结构：如数组。

·链式存储结构：如链表。

·索引存储结构：·稠密索引：每个结点都有索引项。

·稀疏索引：每组结点都有索引项。

·散列存储结构：如散列表。

·数据运算。

·对数据的操作。

定义在逻辑结构上，每种逻辑结构都有一个运算集合。

·常用的有：检索、插入、删除、更新、排序。

数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。

·原子类型：由语言提供。

·结构类型：由用户借助于描述机制定义，是导出类型。

抽象数据类型ADT：·是抽象数据的组织和与之的操作。

相当于在概念层上描述问题。

·优点是将数据和操作封装在一起实现了信息隐藏。

程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。

算法取决于数据结构。

算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。

评价算法的好坏的因素：·算法是正确的；·执行算法的时间；·执行算法的存储空间（主要是辅助存储空间）；·算法易于理解、编码、调试。

时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。

渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。

空间复杂度：是某个算法的空间耗费，它是该算法所求解问题规模n的函数。

算法的时间复杂度和空间复杂度合称算法复杂度。

第二章线性表线性表是由n≥0个数据元素组成的有限序列。

循环单链表特点
循环单链表的特点
•循环单链表是一种常见的数据结构，具有以下特点：
1.循环性：循环单链表与普通单链表的区别在于，循环
单链表的尾节点指向头节点，形成一个闭环结构。

这样可以实现循环访问列表的功能。

2.无限长度：由于尾节点指向头节点，循环单链表没有
固定的长度限制。

可以随时插入或删除节点，使列表的长度可以无限增长或缩小。

3.快速插入和删除：在循环单链表中，插入或删除节点
的操作相对快速。

因为只需要修改节点的指针，而不需要移动其他节点。

4.不支持随机访问：与数组不同，循环单链表不支持随
机访问。

如果要查找特定位置的节点，需要从头节点开始遍历链表，直到找到所需节点。

5.适用于循环操作：由于循环单链表的特点是循环性，
因此它适用于需要循环操作的场景。

例如，可以使用循环单链表来实现循环队列或循环缓冲区。

6.空间效率相对较高：相比于数组，循环单链表对内存
的利用率较高。

因为它具有动态性，只需要存储节点的数据和指针，没有额外的空间浪费。

7.存在环路问题：若链表中存在环路，即某个节点的指
针指向了已经遍历过的节点，就会导致循环单链表陷入死循环。

因此，需要在插入和删除节点时注意循环条件。

总结：循环单链表是一种具有循环性、无限长度、快速插入和删除的数据结构。

它适用于需要循环操作、空间效率较高的场景，但不支持随机访问，并需要注意处理环路问题。

非空的循环单链表
非空的循环单链表是一种常见的线性数据结构，是将数据元素组织成线性序列的一种方法之一。

它是在单链表的基础上，将最后一个节点的指针调整为指向头结点，形成一个环形结构，可以叫做以首尾相接的单链表。

它的端点为头指针，有一个弧箭头指向下一个节点，每一个节点都存储着一个数据元素，最后一个节点的弧箭头指向头节点。

非空的循环单链表有着多种优点。

首先，它是一种可以快速定位某一元素的线性数据结构，可以按照顺序查找，也可以跳转到指定位置查找。

其次，它可以满足在线性数据结构中元素的插入、删除操作，可以实现快速插入、删除操作，插入删除操作只需改动少量指针即可，操作较简单快捷，不需要移动很多元素。

最后，它的空间复杂度较低，只需要定义头指针和节点指针，不需要额外的存储空间，因此使用非空的循环单链表可以节省较多的存储空间。

在现实应用中，非空的循环单链表有着广泛的运用，主要用于实现一些特殊功能，如：操作系统的内存分配、高级语言的编译器的语法分析等；它也可以用于构造广义表；在环形缓冲区、游戏关卡的设计中也有重要的作用。

尽管非空的循环单链表有很多优点，但是，它也有一些缺点，比如说，判断一个节点是不是头结点比较困难，而且插入删除操作只能从头指针开始进行，另外，如果链表长度过长，可能会出现环路，从而导致拓扑排序出现问题。

总之，非空的循环单链表是一种灵活、高效的数据结构，它在现实应用中有很多应用，不仅可以用于解决实际问题，而且在学习数据结构的过程中也可以作为一个很好的实践练习。

循环单链表循环单链表是一种特殊的单链表，它的最后一个节点的指针指向第一个节点，形成一个环。

它具有单链表独有的优点，同时又克服了单链表存在的缺点。

因此，循环单链表在实际应用中受到了极大的欢迎。

本文介绍了循环单链表的概念，结构特性和实现功能，并分析了其与普通单链表的区别。

1.环单链表的概念循环单链表，也叫循环链表，是一种特殊的单链表，它的最后一个节点的指针指向第一个节点，形成一个环。

循环链表的结构比普通的单链表略有不同，其头结点的next域指向头节点，该结构最显著的特点就是头节点的“上一个”节点和最后一个节点“下一个”节点都是头结点，所以可以利用循环链表来实现双向链表的操作。

2.环单链表的结构特性循环单链表是一种特殊的单链表，其最后一个节点指针指向头结点，从结构上来看，它具有单链表的特点，如指针存储结构、节点为一个结构体成员以及只有单向指针，但又与普通单链表不同，它的结构特征有：（1）头结点的next域指向自身；（2）最后一个节点的next域也指向头结点；（3）整个结构类似一个拥有多叉指针的环形结构体。

3.环单链表的实现功能循环单链表的实现功能包括插入、删除、查找等，这些基本操作的实现和普通单链表的实现方法基本相同，只是有一些细节的不同。

例如，在普通单链表的删除操作中，如果需要删除的节点是链表的最后一个节点，则需要修改链表的尾指针，但是在循环单链表中，只需要修改头结点的next域指向，就可以实现操作。

4.与普通单链表的区别循环单链表有一些独特的结构特点，同时又克服了普通单链表的缺点，因此在实际应用中受到了极大的欢迎。

（1）普通单链表无法实现双向遍历，而循环单链表可以实现双向遍历和遍历，因为它有头结点和最后一个节点，所以可以实现双向遍历，再加上其结构特点，可以实现对双向链表的操作。

（2）普通单链表遍历需要维护一个辅助指针，而循环单链表则不需要，只需要从头结点开始，依次访问每一个节点，直到头结点。

结论：循环单链表是一种特殊的单链表，它的结构特征是头结点的next域指向头结点，最后一个节点的next域也指向头结点，它克服了普通单链表的缺点，可以实现双向遍历，同时又不需要维护辅助指针，因此广泛应用在实际工程中。

循环单链表的概念
循环单链表是一种链表的变体，它与普通的单链表最大的不同在于，循环单链表的尾节点指向链表的头节点，形成一个闭环。

具体来说，循环单链表中每个节点除了存储数据之外，还包括一个指向下一个节点的指针。

最后一个节点的指针不指向空，而是指向头节点，这样就形成了一个循环。

与普通的单链表相比，循环单链表可以更方便地实现某些操作，比如遍历整个链表。

因为链表的尾节点指向头节点，所以可以从任意节点出发，一直遍历到尾节点并回到头节点，实现循环遍历。

循环单链表的操作和普通的单链表类似，包括插入、删除、搜索等。

不过在插入和删除节点时，需要注意维护链表的循环性，即在插入新节点时将其指针设置为下一个节点，而在删除节点时需要更新前一个节点的指针。

循环单链表的一个应用场景是约瑟夫问题，即一群人围成一个环形，从某个位置开始报数，每报到某个数时，该人出列，然后下一个人继续从1开始报数。

通过循环单链表可以很方便地模拟这个过程。

图解Java数据结构之环形链表本篇⽂章介绍数据结构中的环形链表。

介绍环形链表，类似于单链表，也是⼀种链式存储结构，环形链表由单链表演化过来。

单链表的最后⼀个结点的链域指向NULL，⽽环形链表的建⽴，不要专门的头结点，让最后⼀个结点的链域指向链表结点。

简单点说链表⾸位相连，组成环状数据结构。

如下图结构：⽽在环形链表中，最为著名的即是约瑟夫环问题。

约瑟夫环问题问题介绍：设编号为1、2、3、... 、n的n个⼈围坐⼀圈，约定编号为k(1<=k<=n)的⼈从1开始报数，数到m的那个⼈出列，它的下⼀位⼜从1开始报数，数到m的那个⼈⼜出列。

依次类推，直到所有⼈出列为⽌，由此产⽣⼀个出队编号的序列。

我们可以举个例⼦来分析⼀下：假设⼀共有5个⼈，即n = 5；从第⼀个⼈开始报数，即k = 1；数到2的⼈出列，即m = 2。

⽰意图如下：出队列的顺序即为：2 -> 4 -> 1 -> 5 -> 3那么我们⾸先得构建出⼀个单向的环形链表。

实现分析：1. 先创建第⼀个节点，让first指向该节点，并形成环状2. 每创建⼀个新的节点就将该节点加⼊到已有的环形链表中分析完毕，我们⽤代码实现⼀下：//创建⼀个环形的单向链表class CircleSingleLinkedList {// 创建⼀个first节点，当前没有编号private Boy first = null;// 添加节点，构建成⼀个环形链表System.out.println("数据错误");return;}// 定义辅助节点Boy curBoy = null;// 使⽤循环创建环形链表for (int i = 1; i <= nums; i++) {// 根据编号创建节点Boy boy = new Boy(i);// 如果是第⼀个节点if (i == 1) {first = boy;first.setNext(first);curBoy = first;// 让curBoy指向第⼀个节点，帮助构建链表} else {curBoy.setNext(boy);boy.setNext(first);// 使其指向第⼀个节点，形成环状curBoy = boy;// curBoy后移}}}// 遍历当前环形链表public void list() {// 判断链表是否空if (first == null) {System.out.println("链表为空");return;}// 定义辅助节点Boy curBoy = first;while (true) {System.out.println("节点编号:" + curBoy.getNo());if (curBoy.getNext() == first) {// 此时说明遍历完毕break;}curBoy = curBoy.getNext();// curBoy后移}}}//创建⼀个Boy类，表⽰⼀个节点class Boy {private int no;// 编号private Boy next;// 指向下⼀个节点public Boy(int no) {this.no = no;}public int getNo() {return no;}public void setNo(int no) {this.no = no;}public Boy getNext() {return next;}public void setNext(Boy next) {this.next = next;}}这样就实现了⼀个环形链表，接下来测试⼀下：public static void main(String[] args) {CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList(); circleSingleLinkedList.addBoy(5);circleSingleLinkedList.list();}运⾏结果：节点编号:1运⾏结果也是没有问题的，接下来便是⽣成出圈序列。

二、填空题1. 线性表是一种典型的___线性______结构。

2. 在一个长度为n的顺序表的第i个元素之前插入一个元素，需要后移__n-i+1__个元素。

3. 顺序表中逻辑上相邻的元素的物理位置__相邻______。

4. 要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需向__前___移一个位置，移动过程是从_前____向_后____依次移动每一个元素。

5. 在线性表的顺序存储中，元素之间的逻辑关系是通过__物理存储位置_____决定的；在线性表的链接存储中，元素之间的逻辑关系是通过__链域的指针值_____决定的。

6. 在双向链表中，每个结点含有两个指针域，一个指向___前趋____结点，另一个指向____后继___结点。

7. 当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用___顺序__存储结构为宜。

相反，当经常进行的是插入和删除操作时，则采用__链接___存储结构为宜。

8. 顺序表中逻辑上相邻的元素，物理位置__一定_____相邻，单链表中逻辑上相邻的元素，物理位置___不一定____相邻。

9. 线性表、栈和队列都是__线性_____结构，可以在线性表的___任何___位置插入和删除元素；对于栈只能在___栈顶____位置插入和删除元素；对于队列只能在___队尾____位置插入元素和在___队头____位置删除元素。

10. 根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为__单链表_______和__双链表_____；而根据指针的联接方式，链表又可分为__循环链表______和__非循环链表______。

11. 在单链表中设置头结点的作用是__使空表和非空表统一______。

12. 对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为_o(1)_____，在给定值为x的结点后插入一个新结点的时间复杂度为__o(n)_____。

13. 对于一个栈作进栈运算时，应先判别栈是否为__栈满_____，作退栈运算时，应先判别栈是否为_栈空______，当栈中元素为m时，作进栈运算时发生上溢，则说明栈的可用最大容量为___m____。