引入

今天，我们开始讲一种特殊的线性表，栈。既然是特殊的线性表，那么有哪些不一样的呢？我们一起来看看！

从弹夹说起

下面的图片是一个弹夹

我们知道，如果子弹没有了，那么我们需要一颗一个的将子弹装入弹夹

• 第一颗被装入的子弹在弹夹的最上方
• 第二颗则压在第一颗的上方，循环往复，直到装满
• 此时如果我们要射击，最上面的一颗子弹会首先被发射出去
• 然后弹夹下面的弹簧会将压在下面的子弹顶上来

也就是说，最后被装入的子弹，最先被发射出去。我们将这种情况称之为后进先出。

引入

前面我们简单了解了一下双链表，以及在插入和删除时的一些变化。这一节，我们就跟着一个凯撒密码，来看看双循环链表的初始化、插入、操作结点等过程。

凯撒密码

凯撒密码是一种代换密码。据说凯撒是率先使用加密函的古代将领之一，因此这种加密方法被称为凯撒密码。他的基本思想是

• 通过把字母移动一定的位数来实现加密和解密。
• 明文中的所有字母都在字母表上向后（或向前）按照一个固定数目进行偏移后被替换成密文。
• 当偏移量是4的时候，所有的字母A将被替换成E，B变成F，以此类推W将变成A，X变成B，Y变成C，Z 变成 D。
• 而这个偏移量就是凯撒密码加密和解密的密钥。

例题

有26个英文字母，我们需要设计一个程序

• 用户输入可为正负的正整数
• 如果是正数，那从左边取 N 位正整数移动到表尾
• 如果是负数，那从右边取 N 位正整数移动到表头

引入

我们介绍了单链表、介绍了将单链表头尾相连组成循环链表，又讲了循环链表中一些有趣得应用，现在是时候了解线性表中的大拿，双循环链表了。

为什么需要双链表

在单循环链表中，链表中的各个节点是这样的，一个结点指向下一个结点

A -> B -> C -> D -> E -> F

如果我们需要从 A 到达 D 结点，那么需要

A -> B -> C -> D

如果到了 D 之后，有需要到 C，那么就麻烦了

D -> E -> F -> A -> B -> C

明明相邻得两个结点，为什么要转一圈才能找到彼此呢？
答案很简单，因为结点都是向后指的，单循环链表嘛~
而解决这个问题的答案更简单，那我们就把结点
既指向它的前驱节点，也指向它的后继节点不就好了~
这就是双向链表。

发刊词

数学不好，加上有点强迫症，而又需要或者想学习数学的成年人。这是一个真正的给成年人看的低等数学，这是真的零基础，我们将从幼儿园的等级出发。你将以一个成年人的智慧，来重新看待这些「恼人的数学」，愿你我重新找回数学的乐趣。

引入

我们知道，数学最基础的是由数组成的，那么对于数你又知道多少呢？今天我们看看与数有关的基础知识。

阿拉伯数字

我们将现在使用的数字，称为阿拉伯数字

0 1 2 3 4 5 6 7 8 9

我们可以将这些数字从1数到9，例如下面的 # 号

1：#
2：# #
3：# # #
4：# # # #
5：# # # # #
6：# # # # # #
7：# # # # # # #
8：# # # # # # # #
9：# # # # # # # # #

引入

我们学习了这么多单循环链表的知识，那么该如何运用到生活中呢？或者该如何灵活的使用这些单循环链表的知识呢？

魔术师发牌问题

大概的情景是这样得

• 13张牌

• 从1~13，A~K

• 数一张，放下是 A，把 A 放桌面上

• 数两张，第一张放到牌堆最下面，第二张放下是2 ，把2放桌面上

• 数三张，第一张、第二张放到牌堆最下面，第三张放下是3 ，把3放桌面上

• 以此类推，所有13张牌都发完，桌面上正好是A~K

  大概思路

  • 跟约瑟夫问题类似
  • 移动指针，找到牌
  • 删除结点，重新构成链表
  • 再次移动指针，找到出牌顺序
  • 赋值 A~K，顺序输出即可

引入

上一节，我们学习了尾指针，并且利用尾指针。尾指针可以轻松的操作头结点和尾结点，可以将两个单循环链表组成了一个单循环链表，我们今天再看看，尾指针还有什么其它玩法。

单链表中的环

首先要明白，单链表有环的状态是什么样子得

其实就是，尾指针指向了链表中的某个结点。

如何判断单链表中是否有环

方法 1

• 设置 p 、q 两个指针
• p 向前走，q 从头走，p 向前走尾部应该会到 NULL。
• 每个结点，p 走的步数应该和 q 一样
• 如果不一样，就像上面的图，p 的地址等于 q
• 但是，p 走到3用了6步，q 则用了2步
• 步数不相等，那么就存在环

方法 2

• 设置 p 、q 两个指针
• p 每走一步，q 就走两步，快慢指针
• 快指针应该很快到 NULL
• 如果 p==q 了，则存在环

引入

我们学习了循环链表的基本操作，也学习了一个有趣的约瑟夫问题，我们之前说过有头指针也有尾指针，头指针指向头结点，尾指针指向尾结点。那么尾指针有哪些有趣的用法呢？

单循环链表的问题

我们知道，在单向循环链表中，我们有头指针

• O ( 1 ) 的时间去找到第一个结点，因为 next 就是头结点
• O ( n ) 的时间去找最后一个结点，因为第 n 个才是尾结点

如何在访问头结点和尾结点得时候，都是O( 1 )时间复杂度呢？

尾指针应运而生！

• 尾指针指向的是尾节点
• 而尾节点得下一个就是头结点

所以尾指针访问头结点和尾节点的时间都是 O ( 1 ) 。
撒花~~~

尾指针

引入

罗马占领乔塔帕特之后，39个犹太人与 Joseph 及1个朋友躲进山洞避难，39个人宁死也不愿意被敌人抓到，决定了一种自杀方式：

• 41 个人排成一个圆圈（39个犹太人 + Joseph + 1 个朋友）
• 第 1 个人开始报数，每报数到第3人，这个人就自杀
• 然后再从下一个，也就是原来的第 4 人开始，数到第 3 人自杀
• 直到所有人都自杀身亡为止

但是 Joseph 和朋友并不想死，所以就有如下那排

• 朋友去了 16 号
• Joseph 去了 31 号
• 于是，逃过了死亡游戏

约瑟夫问题

那么这个有趣得约瑟夫和朋友逃难的问题跟我们得循环链表有什么关系呢？我们想用计算机帮助我们把41个人的自杀编号输出出来：

代码实现

引入

我们讲了顺序存储结构、单链表、静态链表，今天我们学习一种新的链表，单循环链表，单循环链表很简单，其实就是在单链表的基础上，将头尾相连，形成一个单向环装循环。

单循环链表

我们知道，单链表非常有趣，虽然不连续，但却根据指针一个连着一个，但是单链表有一个问题，我们如果不从头结点出发，就无法访问所有结点。
解决方法也非常简单，就是把链表终端结点得指针由 NULL 改成指向头结点。也就是链表最后一个结点存储得指针为头结点得指针，也就是原来 head 存储的地址。
既然head 和 最后一个结点 都指向头结点，那么我们就称这种头尾相接得单链表位单循环链表。

单循环链表的特点

既然头尾相接，那么单循环链表有新增了下面几种特性

• head 指向头结点，尾部也指向头结点
• 判断空表得时候，只要头结点和头部指向得内容都是该结点本身，那么这个表就是空表。
• 头结点即尾部，头结点指向头结点，head 指向头结点
• 原来是 head->next 是否为 NULL，是就为空表。
• 现在是 head 是否等于 head->next，即头结点指针指向它自己
• 我们把最后一个结点得指针称为 rear

引入

按照惯例，我们学习了如何初始化、插入、删除一个静态链表，那么静态链表打底有什么优缺点呢？链表还有什么高级玩法呢？
我们一起来看看~

静态链表的优缺点

• **优点：**插入和删除时，只需要求改游标，不需要移动元素，从而改进了顺序存储结构中需要大量移动元素的缺点。
• **缺点：**没有解决连续存储分配带来得表长难以确定的问题。

总之，静态链表是一个很好的尝试，在没有动态创建、释放内存空间得情况下，利用数组，完成了静态链表。

练习

创建一个20个元素的动态链表，然后快速找到其中间结点。