零、写在前面
数据结构与算法A是北京大学大二上学期信科人的必修课，教材是张铭老师等老师编著的《数据结构与算法》。
虽然全程用C++讲述，但这门课的核心思想并不受语言限制，而是注重抽象的算法思想。
其他我也不知道了，不管了冲！
一、概论
众所周知，Niklaus Wirth曾经提出过著名公式：“程序=数据结构+算法”。
程序是用来解决问题的，所谓问题就是从输入到输出的一种映射函数。数据结构是逻辑数据在计算机中的存储表达，它支持相应的操作。而算法是对特定问题求解的描述方法。至于程序，就是算法在程序语言中的实现。
如果说数据结构是建筑工程中的建筑设计图，那么算法就是工程中的施工流程图。所以计算机就是土木（对的）
为了解决问题，数据结构和算法缺一不可。我们不仅要选择最合适的数据结构，还要设计最为合理的算法。这门课的目的，就是提高我们程序设计的质量。
1. 问题求解
编写程序的目的，就是为了解决实际的应用问题。为此，我们需要：
- 问题抽象——抽象任务需求，建立问题模型
- 数据抽象——确定恰当的数据结构来表示数学模型
- 算法抽象——在数据模型的基础上设计合适的算法
我们先看一个例子，来看看在解决实际问题的时候，如何通过构建模型来解决问题。
这个经典的问题叫四色定理，它希望对国家区域平面图进行着色，要求相邻的区域用不同的颜色。
举这个例子是因为可以顺便科普一下，这个问题是NP复杂性问题。对于小型地图，可以用穷举或者回溯法；而地图太大的时候，时间复杂度会指数级上升。这时可以通过逼近方法求近似最优解。
我们现在当然不解决四色定理，而只是考虑：如何设计程序来解决简单的问题？
- 数据结构：平面图。把每个地区视作一个点，相邻的地区用线相邻。不要着急，以后会学的。
- 算法：最不用动脑子的方法就是列举。当然还有很多省时省力的操作，这个在AI引论课上亦有提到。
2. 数据结构
数据结构(data structure)涉及了数据的逻辑结构、存储结构与运算。
i.数据的逻辑结构
数据的逻辑结构是从具体问题抽象出来的数学模型。从集合论的观点来看，它可以用一个二元组 B = (K,R) 来表示。其中，K是结点(node) 组成的集合，R是关系集，其中的每个关系r都是一个二元关系。
我们从K中取出两个元素<k,k'>，这就是一个二元组，它是有序的。一些二元组组成集合，就叫一个关系。
二元组里面的元素也有名字，如果<k,k'>∈r，则k为k’在关系r上的前驱，k’为k在关系r上的后继。没有前驱的结点叫开始结点，没有后继的结点叫终止结点。
一下子来这么多概念真是太难记住了，举个例子吧：
就以最开始的四色定理为例，每个国家是一个节点k，它们组成了结点集K。只有一种关系，即R={相邻}。我们取两个国家A和B，如果相邻，则<A,B>∈相邻，<B,A>∈相邻，它们互为前驱和后继。那么自然也就没有开始结点与终止结点。
举一个有开始结点与终止结点的例子也很简单，比如取r=先修课程，那么<计算概论，程序设计实习>就是r上的二元组，计算概论就是开始结点，毕业论文就是终止结点。
既然逻辑结构包括结点和关系，那我们就分别简单介绍一下。
(1)结点是一种数据，可以是基本数据类型，例如：
- 整数(integer)
- 实数(real)
- 布尔类型(boolean)
- 字符类型(char)
- ASCII用单个字节（最高位为0）表示字符
- 汉字符号需要2个或更多字节（最高位为1）编码
- 指针类型(pointer)：指向某一内存单元的地址
- 32bit的机器，4个字节表示一个指针。64bit的机器则需要8个字节。
- 指针可以分配地址、赋值、比较、增减值。
也可以是复合数据类型，例如：
- 数组：int A[100];
- 结构：struct B{};
- 类：class C{};
(2)关系集R的分类决定了逻辑结构的分类。有三种结构分类：
- 线性结构：每个结点在关系r上最多只有一个前驱结点和一个后继结点。具体来说，K有唯一的开始结点，唯一的终止结点，其余都是内部结点。
- 树形结构：又称层次结构。只有一个结点没有前驱，叫做树根。其他结点有且仅有一个前驱，但可以有多个后驱。同时，每个结点都有一条连接树根的路径。
- 图结构：对前驱和后继的数目不加约束。
我们可以看出：
\[线性表 \subset 二叉树 \subset 树 \subset 图\]ii.数据的存储结构
要存储数据，实际上是实现从逻辑结构到物理存储空间的映射。在计算机的主存储器（内存）中，数据的存储有“空间相邻”和“随机访问”的特点：
- 基本的存储单元是字节；
- 用非负整数进行编码；
- 可以对相邻单元按照地址随机访问；
- 访问不同地址所需时间基本相同。
为了实现对逻辑结构(K, R)映射，不仅要对结点集K到存储器M建立映射：K->M，其中的每个结点j ∈ K都对应唯一的连续存储区域c ∈ M；还要对关系建立映射，其中每一个关系元组 $ <k_i, k_j> ∈ R, k_i, k_j∈K $ 映射为存储地址之间的关系。常见的方法有以下四种：
- 顺序方法：把一组节点放在一片地址相邻的存储单元中，存储单元的顺序表达了结点的后继关系。这种方法方便用整数编码访问数据，比如数组就可以通过下标访问数据。
- 链接方法：在数据域的基础上添加的指针域，指针的指向表达了结点的后继关系。优点是便于增删结点，缺点是访问结点必须要先获得前置指针，否则就只能从链头开始寻找。
- 索引方法：构建了一个索引函数 $ Y: Z → D $ （Z为整数域，D为存储地址域）。同时还有一个由一组指针组成的索引表，每个指针指向存储区的一个数据。优点是可以提高检索的效率（可以先通过索引表指向相应存储位置，在进行文件读写）；并且便于处理每个结点大小不同的情况。
- 散列方法：是索引方法的拓展，核心是利用散列函数 $ h: S → Z $ （S为关键码，Z为非负整数）实现把结点的关键码映射到地址，然后把结点存入单元中。
散列问题需要思考：
- 如何选择和设计恰当的散列函数
- 如何构造散列表
- 研究构造散列表时的碰撞解决方案
散列函数需要满足下列性质：
- 散列函数计算出的地址应该尽可能均匀地分布在散列表地址空间
- 计算应当简单化
评估一个存储方法的指标之一是存储密度ρ，其值为数据本身占整个结构的存储比率，在0到1之间。
比如，顺序方法中只有数据，因此ρ=1，也称为紧凑存储结构。链接方法中，$ ρ=\frac{数据域}{数据域+指针域} $，等等。显然，存储密度太小的存储结构，空间效率比较低。
iii.抽象数据类型
抽象数据类型（ADT）定义了一组运算的数学模型，与物理存储无关，使得软件系统能够建立在数据之上（面向对象编程）。这实际上是一种模块化思想，能够隐藏运算实现的细节与内部数据结构，并且实现软件复用。
一般而言，抽象数据结构可以用三元组<数据对象D，数据关系S，数据操作P>来表示。结合我们之前的知识，可以知道一个ADT其实是逻辑结构+运算。
在面向对象语言中，比如C++，就使用类（包括模板类） 来实现ADT。在未来的每个数据结构时，我们都会用如下的模板类来表示它们：
3. 算法
我们大一的时候经常说“这个算法容易超时”、“这个算法泰妙辣”，那么什么是算法呢？
简单来说，算法是对特定问题求解过程的描述。比如，为了求两个正整数的最大公约数，辗转相除法就是一种算法，它告诉了我们实现目标的过程，只要我们跟着做，就一定能求出结果。
i.算法的性质
- 通用性：不管数据是什么，都一定能求出正确解。
- 有效性：每一个步骤都能被确切执行。不存在不能理解或结果不确定的步骤（也就是，执行过程和执行结果都是可预期的）。大家可以思考一下，随机生成一个0到1之间的数字符合有效性吗？
- 确定性：一定有下一步指令。
- 有穷性：必须在有限步内结束，即不能有死循环。
ii.算法的设计方法
大部分大家都会，只是可能不知道名字。
- 穷举法：这需要我介绍吗？
- 回溯法：对于多个变量，向前试探，一个一个尝试候选解；当碰到一个候选解，对于剩下的任何情况都不成立时，回溯，尝试另一个候选解。大家在大一学深搜的时候都会了。
- 分治法和递归法：分治法就是把一个大问题拆成多个小问题，再把多个小问题的解合并。而为了不断把大问题拆解成小问题，就需要递归。这两种方法经常同时使用，很多高效算法都是以它们为底层思想。
- 贪心法：大一学过了。从问题的初始状态出发，每一步都按一定的标准选择收益最大的行动。贪心法不一定是全局最优解，这取决于这个标准是否合理。
- 动态规划法：这种题大一都讲烂了。类似于分治法。不过，如果一个题需要用动态规划，通常是因为分解出来的子问题不相互独立（重合度太高），每次都用分治法效率太低。为此我们记录每个子问题的结果，这样可以更快求其他的子问题。
4. 算法分析
总算到这一章的最后一节了，没想到概论这么难学（我太懒了）。这一节虽然非常重要，但是大家大一基本都熟悉了，所以问题应该不大。加油！
一般来说，一个问题可以有多个算法。因此，选择最好的算法就是很重要的课题。算法分析就是利用数学工具讨论一个算法的复杂度。
不过大家首先要明白，评价一个算法的好坏不能通过真实的时间单位来描述，因为不同的设备运行同一个算法的时间也有不同。因此，我们使用算法与输入规模之间的关系来描述时间效率，即“在一定规模的输入数据下，算法需要多少次基本操作才能得出结果”。
这里的“规模”指的是输入数据的数目，比如对n个数排序，n就是规模。
这里的“基本操作”指的是时间与数据大小无关的操作，比如两个数相加，1+1和114514+1919810所花的时间是一样的。具体来说，包括：
- 简单布尔或算术运算
- 简单I/O，这里指的是函数的输入和输出，不包括键盘文件的I/O。
- 函数返回
到此大家可能知道算法分析是干什么的了，但是具体怎么进行算法分析？分析不准怎么办？就需要我们更深入的探究了。
i.渐进分析
一般情况下，描述时间效率的函数都非常复杂。为此，我们只考虑数据非常大的时候能造成影响的部分，其他部分都可以忽略掉。这就是渐进分析。
比如，对于函数$ f(n)=n^2+100n+\log_{10}{n}+1000 $ ，当n取值很大时，只考虑 $ n^2 $ 项。不过大家也注意到了，当 $ n=1 $ 时，最重要的反而是常数项。因此，渐进分析得出的“最佳”算法可能对小规模数据反而不适用。
表示渐进分析结果的方法有三种：
大 $ O $ 表示法
这个应该是最常用的了，下文都假设 $ f $ 和 $ g $ 都是 $ N \rightarrow R^* $ 的函数：
定义：如果存在正数 $ c $ 和 $ N $ ，使得对任意的 $ n \ge N $ ，都有 $ f(n) \le cg(n) $ ，则称 $ f(n) $ 是 $ O(g(n)) $ 的。
这个定义表明，函数 $ f $ 的增长最多趋同于 $ g $ 的增长。因此，大 $ O $ 表示法提供了表达函数增长率上限的方法。
（这下知道高数没学好的坏处了吧）
从下图可以清晰地看出两个函数之间的关系：
在很远的地方，$ g(n) $ 就是 $ f(n) $ 的上界。
有些性质在计算算法效率的时候可能用到：
(1) 如果 $ f(n) $ 是 $ O(g(n)) $ 的，$ g(n) $ 是 $ O(h(n)) $ 的，则 $ f(n) $ 是 $ O(h(n)) $ 的。
(2)如果 $ f(n) $ 是 $ O(h(n)) $ 的，$ g(n) $ 是 $ O(h(n)) $ 的，则 $ f(n)+g(n) $ 是 $ O(h(n)) $ 的。
(3) 如果 $ f(n)=cg(n) $ ，则 $ f(n) $ 是 $ O(g(n)) $ 的。
(4) 对于任何正数a和b，$ \log_{a}{n} $ 是 $ O(\log_{b}{n}) $ 的。
(5) $ f_1(n)+f_2(n)=O(max(f_1(n),f_2(n))) $ 。
(6) $ f_1(n)f_2(n)=O(f_1(n)f_2(n)) $ 。
是不是看着这些数学符号头痛？（其实我也打的很累）其实说白了就下面这四条： (1)同样增长率的函数可以传递。 (2)同样增长率的函数可以相加。 (3)一个函数翻倍，不影响函数的增长率。 (4)所有对数函数增长率一样。因此我们把 $ \log_{2}{n} $ 简写为$ \log_{}{n} $ 。 而第(5)(6)说明了加法和乘法的规则，前者一般用于if结构，而后者一般用于for,while等循环结构。
有一些很常见的增长率：
(1)常数函数，不管数据规模多大，增长率都不变。 (2)线性函数，数据规模多大，增长率就有多大。 (3)对数函数 $ \log_{}{n} $ ，比线性函数慢。 (4)二阶增长 $ n^2 $ 。 (5)$ n\log_{}{n} $ 比二阶慢比线性快，一般在树形数据结构的算法中。 (6)指数级增长 $ a^n $ ，比任何多项式都要快。
$ \Omega $ 表示法
与上文唯一的区别在于，它规定的是下限。
定义：如果存在正数 $ c $ 和 $ N $ ，使得对任意的 $ n \ge N $ ，都有 $ f(n) \ge cg(n) $ ，则称 $ f(n) $ 是 $ \Omega(g(n)) $ 的。
从下图可以清晰地看出两个函数之间的关系：
在很远的地方，$ g(n) $ 就是 $ f(n) $ 的下界。
大 $ \Theta $ 表示法
当上下限相同时，可以用大 $ \Theta $ 表示法。
定义1：如果一个函数既是 $ O(g(n)) $ 又是 $ \Omega(g(n)) $ 的，则称其为 $ \Theta(g(n)) $ 。
定义2：如果存在正数 $ c_1,c_2 $ 和 $ N $ ，使得对任意的 $ n \ge N $ ，都有 $ c_1g(n) \le f(n) \le c_2g(n) $ ，则称 $ f(n) $ 是 $ \Theta(g(n)) $ 的。
还是挂个图给大家看看：
在未来，每碰到一个新算法，我们都会对算法进行渐进分析，所以我才说这个部分很重要。我们先拿两个简单的例子练练手。
先看一个超级简单的求和例子：
首先对i和sum进行了初始赋值；随后每循环一次都对i和sum重新赋值，因此总共进行了 $ 2n+2 $ 次赋值，渐进复杂度为 $ O(n) $ 。
如果循环嵌套，时间复杂度会更高。来看下面这个双重循环的例子：
这里，主要的基本操作还是赋值。最初对i单独赋了值0 。当 $ i = i_0 $ 时，首先对i、j、sum赋值；其次循环内进行了 $ 2i_0 $ 次赋值操作；即 $ 3 + 2i_0 $ 次操作。那么总共进行了 $ 1+3n+\sum_{i=1}^{n-1}2i=1+3n+n(n-1)=O(n^2) $ 次操作。
如果这一块你还没看明白，可以多看几遍。后面我还会补充几个例题，以便大家自测。
有一些问题的时间复杂度超级大：
- 不可解问题：虽然能够被准确定义，但不存在解决的算法。例如停机问题。
- 难解问题：所有算法都不能在多项式时间内解决。例如最优巡游路径问题、判断命题逻辑公式是否恒为真等。
- 组合爆炸型的难解问题：随着n增大，算法无法在多项式时间内解决。例如大一我们都很喜欢的八皇后问题。
ii.最差、最佳和平均情况
如果大家经常逛贴吧啥的，可能刷到过“猴子排序是理论最快排序方式”这种话题，所谓“猴子排序”其实就是每次把数据随机排列，直到刚好按大小排好序。理论上只要运气足够好，第一次就能排好。
这其实反映了一个问题——对于某些问题，算法的能力往往与所给的数据有关。这时我们就需要考虑不同的情况了。
其实猴子排序这个例子不太好，我们还是举一个比较恰当的例子吧：
输入是一个规模为n的一位数组，要求找出一个给定的k值。
这时，如果我们的算法是“按顺序搜索”，那么最佳情况是：第一个数字就是k；最坏情况是：最后一个数字是k。而平均情况下，如果k值在数组中等概率分布，平均代价是 $ \frac{n+1}{2} $ 。
还有一种比较骚的平均情况，假如k出现在不同位置的概率不同，最可能出现在第一个，概率为 $ \frac{1}{2} $ ；其他位置等概率，都为 $ \frac{1}{2(n-1)} $ 。那么大家可以算算平均代价。如果我没算错的话，应该是 $ \frac{1}{2} + \frac{2+3+…+n}{2(n-1)}=\frac{n+4}{4} $ 吧。可以看到比上文的平均代价小，比最佳情况代价大一点。
在未来我们学习二分检索以后，查找的速度可以提升至 $ O(\log_{}{n}) $ 。那时我们将清晰地感受到算法改变给我们的便利。
我不禁要问（意林音）：最佳最差情况对我们有什么意义呢？虽然它们发生的概率太小，但是最佳情况能让我们知道某种算法在何种情况下使用（有奇迹）；而最坏情况能让我们知道一个算法至少能做多快。
iii.时间/空间の权衡
我们早在动态规划和记忆化搜索的时候就学过“用空间换时间”的思想。简单来说，算法往往呈现 “时空折衷” 的性质，即为了改善一个算法的时间开销，往往可以增大空间开销为代价，反之亦然。这个大家都熟悉了。
iiii.数据结构与算法的选择
在解决一个问题的时候，首先要仔细分析，考虑清楚问题所涉及的数据类型与逻辑关系，数据结构的设计一般优于算法的设计；其次要注意数据结构的可拓展性，也就是输入规模增大时，该数据结构能否适用；最后注意时空开销的比较。
5.总结
一起来回顾一下吧！
首先我们知道了程序=数据结构+算法，为了用程序解决问题，必须从两个方面考虑。
关于数据结构，我们知道了：
- 从逻辑上，包括数据结点K和关系R，结点的类型很多样，关系决定逻辑结构的分类，包括线性、树形和图结构。
- 从存储上，数据结点会存储在唯一的连续存储区域，关系可以使用顺序方法、链接方法、索引方法、散列方法来存储。
- 从运算上、抽象数据类型可以同时定义数据对象、数据关系与基本操作。
关于算法，我们知道算法的四大性质与六个基本的设计方法，还知道了评价一个算法需要用到算法分析，可以用三种表示法来实现渐进分析。并且我们还知道了时空折衷的性质。
6.习题
课本的每一章后面都有小部分习题，以及我未来选课后会做很多题，我会把一些有价值的题归到这里。为了大家自己思考，我先展示所有题目，再附上我的答案。
- 指出算法A的功能和时间复杂度，其中h、g分别是单循环链表中两个结点指针。
- 设n是偶数，计算下面程序运行后m的值，并给出该程序段的时间复杂度。
- 求辗转相除法的时间和空间复杂度。
- 已知 $ f(n) $ 在 $ O(g(n)) $ 中，判断下面哪些正确哪些错误：
- $ \log_{2}{f(n)} $ 是 $ O(\log_{2}{g(n)}) $ 的
- $ 2^{f(n)} $ 是 $ O(2^{g(n)}) $ 的
- $ f(n)^2 $ 是 $ O(g(n)^2) $ 的
解答：
- A实际上执行了两次B，所以先看B干了什么：p一开始在s的位置，不断把p向后移直到p在q的前面，最后把原本该接q的地方改成接s。那么A第一次调用B，其实是把循环链表从g之前切断，直接连回h。第二次调用的时候，其实是把链表从h之前切断，直接连回g。最后的效果就是变成了两个循环链表。描述起来太抽象了，画个图大家就看清楚了：
功能清楚了，算算时间复杂度吧。进行第一次B时，做了1次声明，1次赋值，从h到g之前的每次循环做了一次布尔运算（循环判定条件）和一次赋值，但最后一次循环只做了布尔运算，最后做了1次赋值。第二次的3个操作仍然做了，唯一的区别是循环是从g到h之前。那么操作数是 $ 2n+4 $ ，其中n是链表长度。那显然时间复杂度是 $ O(n) $ 了。
其实算时间复杂度不一定要求操作次数，只要看它的多项式次数就行了。很明显，这两次B算法所做的只是从头到尾遍历了一遍整个链表，所以时间复杂度一定是 $ O(n) $ 。
- 时间复杂度很好求，明显是两层循环，复杂度一定是 $ O(n^2) $ 。至于求m的值，其实当 $ i > \frac{n}{2} $ 时，j的初始值就比n大了，第二层循环已经废了。而m的值每经过一次二层循环就会+1，那么 $ m = (n-1)+(n-3)+···+1=\frac{n^2}{4}$ ，这也验证了时间复杂度是对的。
- 以防大家忘记了辗转相除，以下是代码：
要算时间复杂度，关键在于：经过两次循环以后，y的值一定不超过原来的一半。 也就是说，求出最终结果的过程不会比n慢，当然也不会是常数，因此我们大胆猜想时间复杂度是 $ O(\log_{}{n}) $ 。不过其实从上面黑体字可以直接论证，至于为什么请看未来的笔记。
- 正确的有证明，错误的有反例。
- 正确，证明如下： \(存在正数 c>2 和 N ，使得对任意的 n \ge N ，都有 f(n) \le cg(n)。（定义）\\ 则\log_{2}{f(n)} \le \log_{2}{c}+\log_{2}{g(n)} \le \log_{2}{c}\log_{2}{g(n)}。（取对数，放缩）\\ 则存在正数c_1=\log_{2}{c}和N，使得对任意的n \ge N，都有\log_{2}{f(n)} \le c_1\log_{2}{g(n)}。\)
- 错误。取 $ f(n)=2n $ ，$ g(n)=n $ ，则 $ f(n)=O(g(n)) $ 。但是 $ 2^{f(n)}=4^n $ ，$ 2^{g(n)}=2^n $ ，显然 $ 4^n\ne O(2^n) $ 。
- 正确。这个比较好证： \(存在正数c和N，使得对任意的n \ge N，都有f(n) \le cg(n)。\\ 则存在正数c_1=c^2和N，使得对任意的n \ge N，都有f(n)^2 \le c_1g(n)^2。\)
二、线性表
在1.2数据结构一节，我们知道了线性结构，又称线性表。线性表有两个结构特点：
- 均匀性：同一线性表内的各个数据元素必定有相同的数据类型和长度。
- 有序性：各个数据元素在线性表中都有自己的位置，并且相对位置是线性的。
线性表有很多种表现方式，比如顺序表、链表、栈、串、顺序文件等；元素也有不同的叫法，比如表目、结点、记录等。根据元素的复杂程度，可以分为简单线性结构和高级线性结构。
我们先学习笼统的线性表，然后在学习它的多种形式。
1. 线性表
我们之前说过，一个抽象数据类型包括逻辑结构、存储结构和基本操作，你还记得吗？
线性表（linear list）是由称为元素（element）的数据项组成的有限且有序的序列，这些元素也可称为结点或表目。
从逻辑结构上看，如果用二元组表示，则 \(K=\{k_0,k_1,···,k_{n-1}\} \\ R=\{<k_i, k_{i+1}>|0 \le i \le n-2\}\) 其中，n称为线性表的长度，n=0时称为空表，n>0时称为非空表。$k_0$称为开始结点或表首，$k_{n-1}$称为终止结点或表尾。同时，$k_i$是$k_{i+1}$的前驱，$k_{i+1}$是$k_i$的后继。
线性表的前驱与后继关系具有反对称性和传递性。
线性表的存储结构在不同的形式下有所不同，主要有两类： (1)定长的顺序存储结构，即顺序表。在下一节会详细介绍。 (2)变长的线性存储结构，简称链表。在下下节会详细介绍。
对线性表的操作不外乎两大类，一类是对整个表的操作，另一类是对表内元素的操作。下面是一个抽象数据类型说明：
我们无需记忆这些函数，只需要大体了解线性表实现了什么功能即可。注意每一次操作时长度的变化！
2. 顺序表
按顺序方式存储的线性表称为顺序表（array-based list），又称向量（vector），通过数组建立。顺序表非常舒服的一点在于可以通过下标访问元素。大家刚学C++的时候肯定都学过数组了，这一节对大家来说肯定很简单。
为什么可以用下标实现随机访问元素呢？这就与顺序表的存储方式有关了。
在内存中，顺序表的每个元素是紧挨着存放的，并且存储顺序就是逻辑顺序。在1.2我们学了存储密度，顺序表的存储密度为1。
又因为每个元素占用的存储单元是一样多的，则每个元素的存储位置呈等差数列关系，具体为： \(loc(k_i)=loc(k_0)+i\times L\) 其中$k_i$是目标元素，$loc(k_0)$ 称为顺序表的首地址，$L$是每个元素占用的存储单元。
那么只要我们知道开始结点的地址和每个元素占用的长度，就可以求出需要的元素位置，也就实现随机访问了。
创建一个顺序表需要什么变量？我们用C++来示范：
由于我觉得大部分函数的实现都超级简单，我就只记录思路了，有兴趣的朋友可以自己尝试如何用代码实现。
- 获得下标k返回元素：
return aList[k];复杂度是$O(1)$。 - 获得值x返回位置：遍历比对，找到返回下标。复杂度明显是$O(n)$。
- 在p处插入元素：先要检查是否溢出，插入位置是否合法。如果可以插入，从表尾开始所有元素向后挪一位，腾出p处的位置。复杂度明显是$O(n)$。
- 删除p处元素：先要检查删除位置是否合法，再从p开始所有元素向前挪一位。复杂度仍是$O(n)$。
总结就是，顺序表访问元素很快，但是增删改查这一块都得遍历所有元素，慢的可怕。
顺序表的优点：
- 不需要附加空间
- 随机存取的效率为$O(1)$
缺点：
- 很难估计所需空间的大小，开局就要开很大的空间
- 更新很麻烦
3. 链表
为了克服顺序表无法改变长度，更新麻烦的缺点，链表（linked list）产生了。链表在计概A已经学过了，这一节对大家来说又很简单。
链表可以看成一组既存储数据又存储相互连接信息的结点信息，这样就不需要在存储中挨着了，可以分散在各处，通过指针域来链接各个结点。链表的特点是可以动态申请新的存储空间。
链接存储其实很常用，不只是线性表可以用，后文的树结构和图结构等都可以用链接存储。现在我们只聊用于线性表的链接存储结构，主要分为单链表、双链表和循环链表三类。
i. 单链表
单链表中每个结点只包含指向其后继的指针。
单链表的存储结点包括两部分，一部分叫data域，存放数据；另一部分叫指针域next，指针指向后继结点。对于终止结点，next域值为NULL。用代码表示结点为：
补充一个小知识点：Link的定义中有Link自身，这种类叫做自引用型。
单链表需要一个指向开始结点的指针，叫做*head。要访问链表中的某个节点，只能从head指针开始向下寻找，不能随机访问。还有一个指向终止结点的指针*tail，它可以让append()方法变为$O(1)$。用代码表示单链表为：
在介绍各种算法之前，先补充一点：之前*head指针直接指向第一个数据，但如果是空表，这个指针需要被特判。为了避免对这种特殊情况的处理，引入了一个叫头结点的表头。它没有值，是一个虚结点。
用代码实现头结点：
还是只讲述算法的思路，不写具体代码了。
- 检索：只能从head开始寻找。时间复杂度为$O(n)$。
- 插入：先得找到要插入的位置，时间复杂度为$O(n)$。但插入的过程是$O(1)$：如果要将q结点插入在p结点的后面，先new一个q结点，再接在p之后（
p->next = q;），最后如果插入在链尾则移动tail。 - 删除：时间复杂度和插入一样。如果要删除q结点，先找到q结点之前的p结点。如果q是尾结点，则tail变成p；如果q不是，则
p->next=q->next;。最后记得delete q指针。
对于插入和删除，如果在lnkList中保存了当前位置，就不需要找到需要操作的位置了，可以大大降低时间复杂度。
ii. 双链表
双链表的每个结点多了一个指向前驱的指针，代码表示为：
双链表增加了空间开销，但是减小了寻找前驱的时间开销，其实也反映了时空折衷的思想。
双链表的插入与删除的流程比单链表复杂一些，但是时间复杂度还是一样的。下面介绍定位后的操作流程：
插入： 假设在p结点后插入q结点 (1) 把q结点的next和prev分别接在相应位置。 (2) 把p结点和p->next结点之间的链接拆开，接在q身上。
删除：假设删除p结点 (1) 把p结点的前后结点分别连接起来。 (2) 把p结点的前后链接都指向NULL。如果马上就要delete p，则可以不进行这一步。
iii. 循环链表
把单链表爆改成循环链表，只需tail->next = head即可，然后head指针就可以丢掉了。同样地，把双链表的头尾连接起来，即可把双链表爆改成循环链表。至于插入和删除，与前文是一模一样的。
4. 线性表实现方法的比较
顺序表容易使用，空间开销小，支持随机访问。但是，它不方便插入与删除元素，并且长度较为固定。
链表方便插入删除元素，长度也可以改变。但是，它不方便访问，并且空间开销也更大。
总之，顺序表和链表各有优势，需要根据需求灵活使用。（经典客套话）
5. 总结
这一节真是水，都是大一讲过的东西，一下子就看完了。
本章的主角是大家最喜欢的线性表，以及它的两种表示方法顺序表和链表。线性表中的每个结点最多一个前驱和一个后继，并且可以对整个表或者表内元素进行运算。
顺序表的存储结构是紧挨着的，允许随机访问，但查找、插入、删除的时间复杂度均为$O(n)$。
链表有三种类型，但结点都是由数据和指针组成的，访问需要从头指针开始查找，插入、删除的操作便捷，但时间复杂度仍为$O(n)$。
两者特点互不相同，需要经常访问时用顺序表，需要插入删除时用链表。
6.习题
老规矩，先上题目，大家先思考一下再看答案。
- 假设有两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构。设计一个算法将A和B归并成一个按元素值递减有序排列的线性表C，并要求利用原表中的结点空间构造表C。
- 设计一个非递归算法在$O(n)$时间内将一个含有n个元素的单链表逆置，要求辅助空间为常量。
解答：
- 选这一道题是因为感觉这个要求很有趣，不过这个要求也恰恰是解决的突破口。既然要求用原表的结点，那只需要按照顺序连接这些结点，再把原来的连接切断即可。 但是怎么按照顺序连接呢？先取一个指针$p$，指向所有数据中的最小值。不妨假设最小值在A中。 然后，取两个指针$p_1$和$p_2$，一个指向A的第二，一个指向B的开头。 比较两个数据大小，取较小的一个，让它的next指向p，并把p移过去。 如果选择的是A上的元素，就把A上的指针$p_1$向后推一个；B同理。向后推的同时，解开原来的链接。 反复进行上述操作，直到全部连接起来。 有人可能会问：不是递减吗，为什么不是从最大值向下连接？因为$p_1$和$p_2$都只能从小往大移动，所以这是唯一操作。 这个方法是我能想到的最佳方案了，时间复杂度为$O(m+n)$，毕竟每个结点都需要重新连接，不可能比这个复杂度更小了。 我用代码来表示上述过程，因为前文没有提到过如何用代码构建链表。
这个代码中可以看出来，构建一个链表需要有两个指针，一个q在前面引路，另一个p负责构建连接。构建联系有三步：p->next = q; p = q; q = q->next。
- 大家的第一想法一定是让一个指针 $p$ 遍历链表，中间的每个结点的next都变成原来的前驱，首尾特判一下，解决。但是有两个问题：一是单链表不知道前驱，二是修改next以后就没法向下移动了。那也很简单，添加两个指针，一个 $p_{前驱}$ 在它前驱、一个 $p_{后继}$ 在它后继。这样，解决了第一个问题（$p$->$next=p_{前驱}$），解决了第二个问题（$p=p_{后继}$）。
三、栈与队列
这一章大家又学过了，在大一学习dfs和bfs的时候大家就知道，深度优先搜索可以用栈实现，广度优先搜索可以用队列实现。当然，栈（stack）与队列（queue）的作用远远远不止于此。本章还是详细介绍这两种数据结构，然后简单举例介绍一下它们的应用。
它们都是线性结构，与线性表不同的是，它们的操作受到一定的限制，只能在线性表的一端或两端进行。因此它们也被叫做操作受限的线性表。
1. 栈
栈是只能在一端进行插入和删除的线性表，能操作的这一端叫栈顶（top），另一端叫栈底（bottom）。栈的修改原则是后进先出，因此栈简称LIFO表（last in first out）。
栈有些特殊术语，比如插入元素叫push，简称压栈或入栈；删除栈顶元素叫pop，简称出栈。没有元素的栈叫空栈。
i. 栈的抽象数据类型
写代码没啥意义，大家只要知道栈一般要实现什么操作就行了。
void clear()：清空bool push(const T item)：压栈。bool返回值是判定是否成功。bool pop(T &item)：出栈。item是接收弹出值的变量。bool top(T &item)：只获取栈顶元素，不出栈。bool isEmpty()和bool isFull()字面意思。
栈作为线性表，自然有顺序表和链表两种表现形式。
ii. 顺序栈
用顺序表来储存栈，叫做顺序栈（array-based stack），本质上是简化的顺序表。
栈比顺序表多一个栈顶的定义，所以要确定栈顶的位置。有两种方法，第一种是定义开头是栈顶，这样的话每次添加元素是加在顺序表的开头，这会导致所有元素都要后移一位，时间复杂度为 $O(n)$ 。另一种方法就好使多了，定义结尾是栈顶，添加和删除元素不影响其他元素，时间复杂度为 $O(1)$ 。一般用后一种方法。
用C++实现的话，成员变量包括一个数组，一个整数表示栈顶的下标，还可以定义最大容量maxSize。大家可以考虑如何用代码实现它的构造函数、析构函数、复制构造函数、以及上述的操作。唯一需要注意的是记得特判一下空栈和满栈的情况。空栈出栈会导致下溢出（underflow），满栈入栈会导致上溢出（overflow）。
iii. 链式栈
用链表来储存栈，叫做链式栈（linked stack）。栈顶是表头。用链表就不用担心满栈的问题，所以成员变量中不需要最大容量。也不需要储存整个链表，只要指向表头的指针即可。仍然鼓励大家自己用代码实现上述操作。
与顺序栈相比较，时间效率都一样只需常数时间，但链式栈的空间开销更大，顺序栈需要提前固定长度。在实际应用中，顺序栈更常用。
iv. 栈的应用
栈的后进先出性质让它拥有了非常广泛的应用。下面举个非常经典的使用栈解决问题的例子。
表达式求值
为了讨论方便，表达式都是整型四则运算表达式。
首先我们要知道什么是表达式。表达式有一个基本符号集，包含0~9的数字，加减乘除括号，这十六个符号。（因为左括号和右括号算两个符号）还有一个语法成分集，包括 {表达式，项，因子，常数，数字}。还有一个语法公式集（BNF），它用于定义语法成分的构造。如果把表达式看成房子，基本符号集就是砖头水泥之类的，语法成分集就是框架，语法公式集就是告诉我们框架需要哪些材料搭成。结论是：计算机就是土木
表达式有中缀表达式和后缀表达式两种，中缀表达式就是我们平时看见的表达式，运算符在两个运算对象的中间，括号可以改变运算顺序。而后缀表达式不包含括号，运算符放在两个运算对象的后面，运算顺序是从左到右看，碰到运算符就对最后出现的两个运算对象做相应运算。
两种表达式的语法公式集也不一样，但是都是对语法成分集进行递归定义。例如，中缀表达式的BNF为：
表达式 ：：= 项 + 项 | 项 - 项 | 项
项 ：：= 因子 * 因子 | 因子 / 因子 | 因子
因子 ：：= 常数 | （表达式）
常数 ：：= 数字 | 数字 常数
数字 ：：= 0~9
其实我没有get到这个定义的意义，应该不用背吧。这个公式的离谱之处在于，用于加减的是项，用于乘除的是因子，而因子又可以由表达式组成。
而后缀表达式，在表达式和项的公式上，只是把运算符后置了；因子只能：：=常数；其他两个公式不变。原因大概是作为乘除对象的因子肯定是常数，不可能是别的表达式（后缀表达式保证没有括号改变运算顺序）。
后缀表达式求值就是一个用栈解决的问题。根据上文的运算顺序，很容易想到如何用栈实现： (1)碰到数字，就压栈。 (2)碰到运算符，就出栈两个数，进行相应运算，把结果压栈。 大家可以考虑如何用代码实现上述逻辑。我感觉挺简单的。
不过大家通常见到的都是中缀表达式，这个是难以直接处理的，因为括号会影响运算顺序。还好我们可以把中缀表达式转化成后缀表达式，这是一个比较复杂的问题，大家可以尝试思考一下，下面我将直接给出方法：以下假设输入的是一个字符串表示中缀表达式，输出的是表示后缀表达式的字符串。 (1)碰到数字，直接输出。 (2)碰到左括号，入栈。 (3)碰到右括号，如果栈是空的，说明缺少与之匹配的左括号；否则，反复出栈并输出（注意括号不用输出），直到遇到左括号为止。如果没遇到左括号，说明没有匹配的左括号。 (4)碰到运算符，反复出栈并输出，直到“栈空了”或“栈顶是左括号”或“栈顶运算符的优先级比输入的优先级低”。 (5)如果中缀表达式的符号扫描完毕，但栈还没空：如果栈内有左括号，说明括号没有成功匹配；如果没有，只需依次出栈输出。
2. 队列
队列是只能从表的一端加入元素，另一端删除元素的线性表。允许删除的一端叫队头（front），删除叫做出队（dequeue）；允许加入元素的叫队尾（rear），加入叫做入队（enqueue）。
队列是先进先出表，也称FIFO表（first in first out）。
i. 队列的抽象数据类型
和栈一样，只介绍一些操作，并且操作和栈几乎一模一样。
void clear()：清空bool enQueue(const T item)：入队。bool返回值是判定是否成功。bool deQueue(T &item)：出队。item是接收弹出值的变量。bool getFront(T &item)：只获取队头元素，不出队。bool isEmpty()和bool isFull()字面意思。
而且，队列也分为顺序队列和链式队列。
ii. 顺序队列
顺序队列（array-based queue）是用顺序存储结构实现的队列。需要分配一块连续的区域，需要事先知道队列的大小，需要小心溢出问题。
由于出队和入队不在同一端，哪端放在数组的初始位置就很重要了。
- 如果队头放在位置0，则入队的时间复杂度仅为 $O(1)$ ，而出队的复杂度为 $O(n)$ ，因为一旦有一个元素出队，则队伍中的所有元素都要往前挪一位。
- 如果队尾放在位置0，则正好相反。
- 但是，假设队头放在位置0，但出队时不挪动元素，只是把front向后挪一位，出队的时间复杂度就变成 $O(1)$ 了，大大提高了效率。
但是这又引出另一个问题：随着front的后移，数组的前面部分会有很多浪费的空间，但队列最终仍会上溢出，这种现象叫假溢出。解决的方式是使用循环队列，即把第一个元素当做最后一个元素的后继。实现起来挺简单的，取模即可（位置x的后继位置为 (x+1) % MaxSize）。现在，入队只需要增加rear的值，出队只需要增加front的值，两个时间复杂度都只有 $O(1)$ 了。只有一个元素的时候，rear的值+1，和front的值相同。
但是这又引出另一个问题：假设数组可以容纳n个元素，则队列有n+1种情况；但是如果固定住了front，那么rear的位置只有n种情况。Apparently，队列会有2种情况无法仅通过rear的位置区分（一般是空队列和满队列两种情况）。这有两种解决方案，第一种是记录队列中元素的个数，或至少记录队列是否为空。第二种方法是把数组大小设成n+1（哇塞好暴力的解决方法），这个方法是最常用的。font=rear时队列为空，rear为front前驱时队列为满。
iii. 链式队列
链式队列（linked queue）就没那么多屁事，反正每个结点是单开一个存储区域。成员包括长度size，队头指针和队尾指针。入队即rear后移，出队即front后移。但是注意处理空队列的情况。
链式队列与顺序队列相比，没有固定的存储空间，但可以满足大小无法估计的情况，本质上还是顺序表语链表的区别。两者都无法访问队内元素。
iv. 队列的应用
只要满足先来先服务特性的应用，都可以用队列作为存储方式。比如，消息缓冲器、打印缓冲器、计算机硬设备之间的通信缓冲、操作系统的资源管理等等调度或缓冲都需要队列进行。
在算法上，最需要队列的是广度优先搜索BFS。
农夫过河问题
人、狼、羊、菜一起过河，只有人能撑船，船上包括人只有两个位置，狼羊、羊菜不能在无人时共处。需要寻找一种运输方法，使得人顺利过河。
我们用一个四元向量表示状态，其中每个数字只有0和1两种取值，0为未过河，1为已过河。比如，最开始的状态为(0,0,0,0)，目标状态为(1,1,1,1)。
创建一个队列，首先把初始情况加入队列。然后循环：出队，将出队状态的所有合法的后继状态加入队列。直到出队的是目标状态时结束。
如果还需要记住操作步骤，就需要记住所有状态的能够被达到的路径。
至于如何用代码实现上述流程，可以留给大家思考。包括用函数实现状态转移、合法位置的判定、记录每个状态的路径等。
3. 栈的更深层次运用
用递归函数为例深入讨论栈的应用。
i. 递归函数的定义
一个递归定义是指用自己的简单情况来定义自己。比如阶乘 $n!$ 的定义就是 $n \times (n-1)!$ 。一个递归定义包括递归基础（最基本情况）与递归规则（怎么从复杂情况变为简单情况）。要判断一个问题能否递归实现，就要找到递归基础与递归规则。
有一种很特殊的递归叫尾递归，它的要求是函数的最后一个动作是调用自身。它的特点在于，由于最后一步是调用自己，因此不需要保存这一次调用的数据，仅占用常数栈空间。
ii. 递归函数在内存中的实现
在程序设计语言运行环境中，调用函数的机制是通过编译栈实现的。编译栈中的“运行时环境”指的是计算机上用来管理存储器并保存信息的寄存器及存储器的结构。一个函数调用时：先传入参数与返回地址，再分配局部数据区，最后进入函数；而函数返回时：先保存返回信息，再释放数据区，最后回到上级函数。
如果函数不是递归调用，数据区就采用静态分配：在程序运行前就分配存储空间，直到整个程序运行结束再释放。但递归调用时，由于没法提前知道调用多少次，必须进行动态分配：每调用一次就分配一份，以存放当前所使用的数据，返回时随即释放。
同样，存储器也需要分出栈（stack）区域和堆（heap）区域，前者用于分配后进先出的数据，比如函数的调用；后者用于不符合后进先出的数据，例如指针的分配。栈中的内存由编译器分配并自动释放，而堆的内存需要用new申请，手动释放。
在运行栈中，基本的存储单元是函数活动记录，它包括以下内容：
每次进栈时，被调用函数的活动信息压入栈顶；出栈时，恢复到初始情况。由于运行栈中储存的是被调用函数的运行记录，运行栈又被称为活动记录栈或调用栈。
iii. 递归转为非递归
我们这里直接给出一般情况，并以背包问题举例说明。
对于一个包含t个递归规则的算法，按照以下步骤转化为非递归算法：
(1)设置一个工作栈S。
(2)设置 t + 2 个语句标号：$ label_0 $ 标示第一个可执行语句；$ label_{t+1} $ 设置在函数体结束处；$ label_i (1 \le i \le t) $ 设置在第 i 个递归返回处理的语句。
(3)增加非递归的入口。
(4)替换第 i 个递归规则。
(5)所有递归出口处增加语句：goto label t + 1。
(6)标号为 t + 1 的语句格式是固定的。
(7)改写循环和嵌套中的递归。
(8)优化处理，消除冗余的进栈出栈操作，并消除goto语句。
这确实很复杂，而且现在讲的太抽象了，如果你没有看懂，可以先来看看如何把一个01背包问题转换成非递归算法。
[简化的0-1背包问题]我们有 n 件物品，物品 i 的重量为 w[i] 。每种物品只有放入背包和不放入背包两种情况。问：能否从 n 件物品中选择若干件放入背包，使其重量之和恰好为 s ？
以防大家已经忘记了，背包问题的递归算法是这样的：假设 $ knap(s,n) $ 表示前 n 件物品是否能凑出总重量为 s ，返回值为bool，那么：
大家可以自行考虑如何通过代码实现。
要把这个递归算法改为非递归，首先需要找到递归算法的递归出口和递归规则。递归出口是：s == 0 : true与s > 0 && n < 1 : false。递归规则有两个：背包装入物品 $ w[n-1] $ ，解 $ knap(s-w[n-1],n-1) $ ；或是不装入该物品，解 $ knap(s,n-1) $ 。
接下来就按照上述八个步骤，慢慢来。这真的太复杂了，但是坚持下去，马上就到大家喜欢的字符串了。
(1)设置一个工作栈。这个工作栈要能够表示函数中出现的所有参数和局部变量，比如，背包问题中，栈中的结点应该包括 $ s,n,i,bool $ 四个变量，分别表示两个参数、标号与返回值。
(2)设置语句标号。
(3)添加第一个结点，其中s, n, i = 0 。
(4)替换第 i 个递归规则 $ recf(a_1,a_2,···,a_m) $ ，变成向工作栈添加 $ (i,a_1,a_2,···,a_m) $ ，并goto label0，且增加label i: S.pop(&x)。抱歉我没有搞懂这是在干什么。
(5)所有递归出口都加上跳转到结尾 $label_{t+1}$ 的语句。
(6) $label_{t+1}$的语句长这样：
剩下的(7)(8)都是用于优化的，不需多解释了。其实到这里我依旧未能理解整个过程，以后再补充吧。如果理解了上述过程，你可以考虑如何用代码实现上述非递归逻辑。
4. 栈与队列的深入讨论
大家可以把这一节看成复习，主要是比较不同数据结构之间的优劣。
i. 顺序栈与链式栈的比较
二者的时间效率难分伯仲（都是常数时间完成基本操作），空间效率也各有缺陷，顺序栈可能因为没有满栈而浪费空间，链式栈的指针也会浪费空间。但是顺序栈的好处在于可以快速读取栈内部元素，因此顺序栈更常用。
在实际运用时，为了节省空间，常常使用多栈管理的方式。用一个数组存储两个栈，数组的两端设置为栈底。这种方法适用于两个栈的空间需求相反的情况。
ii. 顺序队列与链式队列的比较
关于空间和时间开销，和栈是一样的。但是，顺序队列无法满足队列规模无法预测的情况；而链式队列不太好访问队列中间的元素。其实这和栈也是一样的。
iii. 限制存取点的表
除了栈与队列以外，还有一些限制存取点的线性表：
双端队列：两端均可插入与删除。 双栈：两个底部相连的栈。每个元素要删除时只能在它插入的一端进行。 超队列：只能在一端删除，但是可以在两端插入。 超栈：只能在一端插入，但是可以在两端删除。
其实后面的三种都可以看做是受限的双端队列。在C++中的STL中提供的deque就是双端队列，栈与队列都是通过deque实现的。
5. 复习
这一节的重点仿佛不是栈与队列的实现，而是怎么利用它们解决实际问题。无论是顺序栈还是顺序队列，链式栈还是链式队列，它们的时间复杂度都很低，空间开销又各有缺陷。
顺序栈最好将数组开头设为栈底；链式栈实现非常简单；顺序队列依靠循环队列来降低时间复杂度；链式队列依靠队首指针与队尾指针实现存取。
在实际应用上，栈适用于后进先出的数据，队列适用于先进先出的数据。使用后缀表达式求值、实现递归算法、深度优先搜索等应用都需要依靠栈，而队列是广度优先搜索的重要数据结构。
6. 习题
- 进出栈问题：给定一组入栈序列和一组出栈序列，请给出一种算法判断出栈序列是否合法，并计算出该入栈序列对应了多少种合法的出栈序列。
- 栈和队列的模拟：如何用两个栈模拟一个队列？如何用两个队列模拟一个栈？
解答：（待完成）
四、字符串
字符串（string）是零个或多个字符按顺序排列的复合数据结构，是一种特殊的线性表。字符串包含的字符个数称为字符串的长度。
1. 字符串的基本概念
字符串就是由字符组成的线性表，一般记作 $ S:”c_0c_1···c_{n-1}” $ ，其中S是串名字，后者是串值，n是串长，n为0时叫空串。一个字符串中，所有字符取值情况的集合叫字符集∑。
要了解字符串，首先得了解字符（char）。字符在内存中需要用字节来表示。在C/C++等语言中，采用ASCII码对字符编码，每个字符用一个字节表示，最高位为0，因此包含128个字符。
稍微了解一下这128个字符：编号为0~32与127号为控制字符或通信专用字符，包括LF、CR、FF、DEL、BEL等控制符
Leave a comment