数据结构笔记第五章（栈）

type

status

date

slug

summary

👉 推荐学习资料

《大话数据结构》——程杰

数据结构与算法基础（青岛大学-王卓）_哔哩哔哩

数据结构（浙江大学-陈越、何钦铭）_哔哩哔哩

📝 正文

第五章、其他链表

5.1 循环链表

5.1.1 循环链表的定义

上一章我们已经学习了单链表，那么这时候有人就提出了一个疑问了，如果我已经知道我想要的数据在链表的后半段，难道我也要从头开始一个个查找吗？这是一件很悲哀的事情，明知道从中间开始查找可以剩一半的时间，但是单链表怎样都只能从头开始遍历。

这时候，循环链表就出现了，它完美的解决了这个问题，下面是它的定义：

循环链表（Circular Linked List）：是另一种形式的链式存储结构，它的结点结构与单链表相同，不同的是链表中表尾结点的指针域不是NULL，而是指向头结点，整个单链表形成一个环，从表中任一结点出发均可以找到其他任意结点，包括该结点的前驱结点。

5.1.2 循环链表的合并

合并操作仅需改变两个指针值即可，主要代码段如下：

5.1.3 循环链表与单链表的区别

5.2 双向链表

5.2.1 双向链表的定义

这个是时候有人提出问题了：单链表只能从前往后查找，不能从后往前查找，我就喜欢反过来遍历，应该怎么办呢？（真就一身反骨呗 😅）

不管是单链表还是单循环链表，表中结点中只有一个指示其直接后继的指针域，因此，从某个结点出发只能循链向后寻查其他结点。若要寻查结点的直接前驱，则必须从表头指针出发。也就是说，在单链表中，查找结点直接后继的时间复杂度为O(1)，查找结点直接前驱的时间复杂度则为 O(n) 。为了克服单链表这种单向性的缺点，可以采用双向链表。

这时候我们的双向链表就登场了，下面是它的概念：

双向链表(double linked list):是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。

5.2.2 双向链表的类型定义

5.3 链表的应用：一元多项式的运算

5.3.1 为什么用链表解决一元多项式的运算

如果让你用代码去解决一元多项式的运算，你会怎么去解决。

第一种办法便是使用数组去解决，建立一个数组，就代表着常数项，代表着一次项的系数，代表着二次项的系数等等。

这种办法看似合理，但是有一种情况它解决不了，那便是稀疏多项式。就如下面这个例子：

如果还是用第一种方法的话，岂不是你的数组大小得有10000项，但这10000项却又只使用了两项，你不心疼计算机浪费了这么多空间，计算机自己都心疼呢！

所以这时候链表的用处就体现出来了，链表就擅长这种项少的活，所以下面就让我们来看看如何用链表来解决一元多项式的运算。

链表解决一元多项式的办法：只存储非零元素，通过改变线性表中的元素设定，对多项式的每一个非零项，可用系数和指数唯一确定。因此，就可以用线性表((1, 0), (3, 10000), (5, 20000))来表示。这种表示方法将大大节省空间。

其对应的数据结构：

那么让我们来举个例子，对于下面两个多项式：

对于这两多项式的单链表存储结构如图：

5.3.2 一元多项式的求和

假设头指针为polyA和polyB的单链表分别为一元多项式A和B的存储结构，链表中结点均按升幂排列，指针pa和指针pb分别指向A和B中当前进行比较的某个结点，则逐一比较两个结点中的指数项：

对于指数相同的项，应该合并同类项，对应系数相加，若和不为零，则作为“和多项式”中的一项插入到“和多项式”链表中去；

对于指数不相同的项，则通过比较先将指数值较小的项插入到“和多项式”链表中去，指数值较大的项继续参与后续比较。“和多项式”链表中的所有结点无需重新生成，而应该从两个多项式的链表中摘取。

📎 参考文章

《大话数据结构》——程杰

《数据结构》——陈志贤

💡

欢迎大佬指正笔记中的错误或者不足，对于文中例题有更好的解法也欢迎大佬留言！