大话数据结构与算法

目前更新到第 4 章。。。

第一章数据结构绪论¶

数据¶

数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算及处理的符号集合。

整型、实型等数值类型，还包括字符、声音、图像、视频等

数据元素：是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理，也被称为记录

人类中的人，动物中的牛、马、养、猪等。

数据项：一个数据元素可以由若干个数据项组成。数据项是数据不可分割的最小单位

人由眼睛、耳朵、鼻子、手、脚等组成。

数据对象：是性质相同的数据元素的集合，是数据的子集。

人都有姓名、生日、性别等

数据结构¶

不同数据元素之间不是独立的，而是存在特定的关系，我们将这些关系称为结构。

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

逻辑结构与物理结构¶

逻辑结构：是指数据对象中数据元素之间的相互关系。

集合机构：集合结构中的数据元素除了同属于一个集合外，他们之间没有其他关系。
线性结构：线性结构中的数据元素之间是一对一的关系。
树形结构：树形结构中的数据元素之间存在一种一对多的层次关系。
图形结构：图形结构的数据元素是多对多的关系。

物理结构：是指数据的逻辑结构在计算机中的储存形式。

顺序存储结构：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。
链式存储结构：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。

数据类型¶

数据类型：是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。

数据类型定义¶

数据类型是按照值的不同进行划分的。在高级语言中，每个变量、常量和表达式都有各自的取值范围。类型就用来说明变量或表达式的取值范围和所能进行的操作。

在 C 语言中，按照取值的不同，数据类型可以分为两类：

原子类型：是不可以再分解的基本类型，包括整型、实型、字符型等。
结构类型：由若干个类型组合而成，是可以再分解的。例如，整型数组是由若干整型数据组成的。

抽象数据类型¶

抽象数据类型（Abstract Data Type, ADT）：一个数学模型及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。

比如各个计算机，不管是大型机、小型机、PC、平板电脑、PDA，甚至智能手机都拥有 “整数” 类型，也需要整数间的运算，那么整型其实就是一个抽象数据类型，尽管它在上面提到的这些在不同计算机中实现方法上可能不一样，但由于其定义的数学特性相同，在计算机编程者看来，它们都是相同的。因此 “抽象” 的意义在于数据类型的数学抽象特性。

抽象数据类型体现了程序设计中问题分解、抽象和信息隐藏的特性。

由这些概念，给出了数据结构的定义：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

第二章算法¶

很多学生，学了四年计算机专业，很多程序员，做了很长时间的编程工作，却始终弄不明白算法的时间复杂度的估算，这是很可悲的一件事。因为弄不清楚，所以也就从不深究自己写的代码是否效率低下，是不是可以通过优化让计算机更加快速高效。

他们通常的借口是，现在 CPU 越来越快，根本不用考虑算法的优劣，实现功能即可，用户感觉不到算法好坏造成的快慢。可事实真是这样吗？还是让我们用数据来说话吧。

假设 CPU 在短短几年间，速度提高到了原来的 100 倍，这其实已经很夸张了。而我们的某个算法本可以写出时间复杂度是 O(1) 的程序，却写出了 O(n) 的程序。比如我们前面提到的高斯使用的算法和数字循环加和算法，仅仅因为后者容易想到，也容易写。那么结果就是同样计算结果，前者无论多大的数字都是零点几秒出答案，后者即使 CPU 提高 100 倍依然可能慢到无法忍受。

也就是说，一台老式 CPU 的计算机运行 O(1) 的程序和一台速度提高 100 倍新式 CPU 运行 O(n) 的程序，最终效率高的胜利方却是老式 CPU 的计算机。原因就在于算法的优劣直接决定了程序运行的效率。

算法的定义：算法是解决特定问题求解步骤的描述，在计算机中为指令的有限序列，并且每条指令表示一个或多个操作。

数据结构与算法的关系是相互依赖不可分割。

算法的特性¶

有穷性：指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。
确定性：算法的每一步骤都具有确定的含义，不会出现二义性。
可行性：算法的每一步都必须是可行的，也就是说，每一步都能够通过执行有限次数完成。
输入、输出：算法具有零个或多个输入，算法至少有一个或多个输出。

算法的设计的要求¶

正确性：算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性，能正确反映问题的需求，能够得到问题的正确答案。
可读性：算法设计的另一目的是为了便于阅读、理解和交流。
健壮性：当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果。
高效率和低存储量需求：设计算法应该尽量满足时间效率高和存储量低的需求。

算法的度量方法¶

事后统计方法：这种方法主要是通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较从而确定算法效率的高低。（不科学、不准确）
事前分析估算方法：在计算机程序编制前，依据统计方法对算法进行估算。

事前分析估算方法¶

一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：

算法采用的策略、方法。
编译产生的代码质量。
问题的输入规模。
机器执行指令的速度。

第 (1) 条当然是算法好坏的根本，第 (2) 条要由软件来支持，第 (4) 条要看硬件性能。

也就是说，抛开这些与计算机硬件、软件有关的因素，一个程序的运行时间，依赖于算法的好坏和问题的输入规模。所谓 问题输入规模是指输入量的多少。

函数的渐近增长¶

给定两个函数 f(n) 和 g(n)，如果存在一个整数 N，使得对于所有的 n > N，f(n) 总是比 g(n) 大，那么，我们说 f(n) 的增长渐近快于 g(n)。

判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注主项（最高阶项）的阶数。

于是我们可以得出一个结论，判断一个算法好不好，我们只通过少量的数据是不能做出准确判断的，如果我们可以对比算法的关键执行次数函数的 渐近增长性，基本就可以分析出：某个算法，随着 n 的变大，它会越来越优于另一算法，或者越来越差于另一算法。

算法时间复杂度¶

用 O() 来体现算法时间复杂度的记法，称之为 大 O 记法。

大 O 阶推导步骤：

用常数 1 取代运行时间中的所有加法常数。（可以忽略加法常数）
在修改后的运行次数函数中，只保留最高阶项。（与最高次项相乘的常数并不重要）
如果最高阶项存在且其系数不是 1，则去除与这个项相乘的系数。（最高次项的指数大的，函数随着 n 的增长，结果也会增长更快）

得到的结果就是大 O 阶。

其实理解大阶推导不算难，难的是对数列的一些相关运算，这更多的是考察你的数学知识和能力。

常见的时间复杂度：

阶	非正式术语
O(1)	常数阶
O(n)	线性阶
O(n²)	平方阶
O(logn)	对数阶
O(nlogn)	logn 阶
O(n³)	立方阶
O(2ⁿ)	指数阶

常用的时间复杂度所耗费的时间从小到大依次是：

O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)

像 O(n³)，过大的 n 都会使得结果变得不现实。同样指数阶 O(2ⁿ) 和阶乘阶 O(n!) 等除非是很小的 n 值，否则哪怕 n 只是 100，都是噩梦般的运行时间。所以这种不切实际的算法时间复杂度，一般我们都不去讨论。

最坏情况与平均情况¶

找东西有运气好的时候，也有怎么也找不到的时候。但在现实中，通常我们碰到的绝大多数既不是最好的也不是最坏的，所以算下来是平均情况居多。

算法的分析也是类似，我们查找一个有 n 个随机数字数组中的某个数字，最好的情况是第一个数字就是，那么算法的时间复杂度为 O(1)，但也有可能这个数字就在最后一个位置上待着，那么算法的时间复杂度就是 O(n)，这是最坏的一种情况了。

最坏情况运行时间是一种保证，那就是运行时间不会再坏了。在应用中，这是一种最重要的需求。通常，除非特别指定，我们提到的运行时间都是最坏情况的运行时间。

而平均运行时间也就是从概率的角度看，这个数字在每一个位置的可能性是相同的，所以平均的查找时间为 n/2 次后发现这个目标元素。

平均运行时间是所有情况中最有意义的，因为它是期望的运行时间。也就是说，我们运行一段程序代码时，是希望看到平均运行时间的。可现实中，平均运行时间很难通过分析得到，一般都是通过运行一定数量的实验数据后估算出来的。

对算法的分析：

一种方法是计算所有情况的平均值，这种时间复杂度的计算方法称为 平均时间复杂度。
另一种方法是计算最坏情况下的时间复杂度，这种方法称为 最坏时间复杂度。

一般在没有特殊说明的情况下，都是指最坏时间复杂度。

算法空间复杂度¶

我们在写代码时，完全可以用空间来换取时间。

以存储空间来换取计算时间的小技巧到底哪一个好，其实要看你用在什么地方。

算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：S(n)=O(f(n))，其中，n 为问题的规模，f(n) 为句关于 n 所占存储空间的函数。

一般情况下，一个程序在机器上执行时，除了需要存储程序本身的指令、常数、变量和输入数据外，还需要存储对数据操作的存储单元。若输入数据所占空间只取决于问题本身，和算法无关，这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常数，则称此算法为原地工作，空间复杂度为 O(1)。

通常，我们都使用 时间复杂度 来指运行时间的需求，使用 空间复杂度 指空间需求。当不用限定词地使用 复杂度 时，通常都是指 时间复杂度。

第三章线性表¶

线性表分为：
1. 顺序存储结构
2. 链式存储结构
  - 单链表
  - 静态链表
  - 循环链表
  - 双向链表

线性表¶

线性表的定义：

线性表（List）：零个或多个数据元素的有限序列。

若将线性表记为：a₁, …, a_i-1, a_i, a_i+1, a_n，

则表中 a_i-1 领先于 a_i，a_i 领先于 a_i+i，称 a_i-1 是 a_i 的 直接前驱元素，a_i+1 是 a_i 的 直接后继元素。
当 i 为 1、2、…、n-1 时（不包括最后一个元素），a_i 有且仅有一个直接后继，
当 i 为 2、3、…、n 时（不包括第一个元素），a_i 有且仅有一个直接前驱。

所以线性表元素的个数 n(n≥0) 定义为 线性表的长度，当 n=0 时，称为空表。

在非空表中的每个数据元素都有一个确定的位置，如 a₁ 是第一个数据元素，a_n 是最后一个数据元素，a_i 是第 i 个数据元素，称 i 为数据元素 a_i 在线性表中的位序。

顺序存储结构¶

顺序存储定义：

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据。

注意哦，这里有两个概念 数组的长度 和 线性表的长度 需要区分一下。

数组的长度是存放线性表的存储空间的长度，存储分配后这个量一般是不变的。一般高级语言，比如 C、VB、C++ 都可以用编程手段实现动态分配数组商长度，不过这会带来性能上的损耗；
线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的；
在任意时刻，线性表的长度应该小于等于数组的长度。

地址计算方法：

其实，内存中的地址，就和图书馆或电影院里的座位一样，都是有编号的。存储器中的每个存储单元都有自己的编号，这个编号称为地址。

假设占用的是 c 个存储单元，那么线性表中第 i+1 个数据元素的存储位置和第 i 个数据元素的存储位置满足下列关系。（LOC 表示获得存储位置的函数）

LOC(a_i+1)=LOC(a_i)+c

所以对于第 i 个数据元素 a_i 的存储位置可以由 a_i 推算得出:

LOC(a_i)=LOC(a₁)+(i-1)*c

通过这个公式，你可以随时算出线性表中任意位置的地址，不管它是第一个还是最后一个，都是相同的时间。那么我们对每个线性表位置的存入或者取出数据，对于计算机来说都是相等的时间，也就是一个常数，因此用我们算法中学到的时间复杂度的概念来说，它的存取时间性能为 O(1)，我们通常把具有这一特点的存储结构称为 随机存取结构。

线性表顺序存储结构的优缺点：

优点：

无须为表示表中元素之间的逻辑关系而增加额外的存储空间；
可以快速地存取表中任一位置的元素。

缺点：

插入和删除操作需要移动大量元素；
当线性表长度变化较大时，难以确定存储空间的容量；
造成存储空间的“碎片”。

链式存储结构¶

定义：

我们把存储数据元素信息的域称为 数据域，把存储直接后继位置的域称为 指针域。指针域中存储的信息称作指针或链。这两部分信息组成数据元素 a_i 的存储映像，称为结点 (Node)。

单链表¶

n 个结点（a 的存储映像）链结成一个链表，即为线性表（a₁, a₂, …, a_n) 的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做 单链表。单链表正是通过个结点的指针域将线性表的数据元素按其逻辑次序链接在一起。

对于线性表来说，总得有个头有个尾，链表也不例外。我们把链表中第一个结点的存储位置叫做 头指针，那么整个链表的存取就必须是从头指针开始进行了。之后的每个结点，其实就是上一个的后继指针指向的位置。

最后一个，当然就意味着直接后继不存在了，所以我们规定，线性链表的最后结点指针为“空”，通常用 NULL 或 ^ 符号表示。

有时，我们为了更加方便地对链表进行操作，会在单链表的第一个结点前附设一个结点，称为 头结点。头结点的数据域可以不存储任何信息，谁叫它是第一个呢，有这个特权。也可以存储如线性表的长度等附加信息，结点的指针域存储指向第一个结点的指针。

头指针与头结点的异同：

头指针：

头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针；
头指针具有标志作用，所以常用头指针冠以链表的名字；
无论链表是否为空，头指针均不为空。头指针是表的必要元素

头结点：

头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可存放链表的长度）；
有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其他结点的操作就统一了；
头结点不一定是链表必需要素。

单链表结构与顺序存储结构的优缺点¶

存储分配方式：

顺序存储结构用一段连续存储单元依次存储线性表的数据元素；
单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素。

时间性能：

查找
- 顺序存储结构 O(1)；
- 单链表 O(n)。
插入和删除
- 顺序存储结构需要平均移动表长一半的元素，时间复杂度为 O(n)；
- 单链表在找出位置的指针后插入和删除时间复杂度仅为 O(1)。

空间性能：

顺序存储结构需要预分配存储空间，分大了，浪费，分小了易发生上溢；
单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制。

通过上面的对比,我们可以得出一些经验性的结论：

若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构；
若需要频繁插入和删除时，宜采用单链表结构。

静态链表¶

对于一些语言，如 Basic、 Fortran 等早期的编程高级语言，由于没有指针，链表结构按照前面我们的讲法，它就没法实现了。怎么办呢？

有人就想出来用数组来代替指针描述单链表。我们看看他是怎么做到的。

首先我们让数组的元素都是由两个数据域组成，data 和 cur。也就是说，数组的每个下标都对应一个 data 和一个 cur。数据域 data，用来存放数据元素，也就是通常我们要处理的数据；而 cur 相当于单链表中的 next 指针，存放该元素的后继在数组中的下标，我们把 cur 叫做游标。

我们把这种用数组描述的链表叫做 静态链表。

静态链表的优缺点：

优点：

在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中插入和删除操作需要移动大量元素的缺点。

缺点：

没有解决连续存储分配带来的表长难以确定的问题失去了链式存储结构随机存取的特性。

总的来说，静态链表其实是为了给没有指针的高级语言设计的一种实现单链表能力的方法。尽管大家不一定会用得上，但这样的思考方式是非常巧妙的，应该理解其思想，以备不时之需。

循环链表¶

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为 单循环链表，简称循环链表(circular linked list)。

为了使空链表与非空链表处理一致，我们通常设一个头结点，当然，这并不是说循环链表一定要头结点，这需要注意。

循环链表带有头结点的空链表就像这样：


头指针   _____
-----> |头结点| ---
        -----     |
          ↑       |
          |       |
          --------

其实循环链表和单链表的主要差异就在于循环的判断条件上，原来是判断 p->next 是否为空，现在则是 p->next 不等于头结点，则循环未结束。

在单链表中，我们有了头结点时，我们可以用 O(1) 的时间访问第一个结点，但对于要访问到最后一个结点，却需要 O(n) 时间，因为我们需要将单链表全部扫描一遍。

有没有可能用 O(1) 的时间由链表指针访问到最后一个结点呢？当然可以。

不过我们需要改造一下这个循环链表，不用头指针，而是用指向终端结点的尾指针来表示循环链表，此时查找开始结点和终端结点都很方便了。

终端结点用尾指针 rear 指示，则查找终端结点的时间复杂度就是 0(1) 了，而开始结点，其实就是rear->next->next，其时间复杂也为 O(1)。

双向链表¶

我们在单链表中，有了 next 指针，这就使得我们要查找下一结点的时间复杂度为 O(1)。可是如果我们要查找的是上一结点的话，那最坏的时间复杂度就是 O(n) 了，因为我们每次都要从头开始遍历查找。

为了克服单向性这一缺点，我们的老科学家们，设计出了双向链表。双向链表（double linked list）是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。

好了，简单总结一下，双向链表相对于单链表来说，要更复杂一些，毕竟它多了 prior 指针，对于插入和删除，需要格外小心。另外它由于每个结点都需要记录两份指针，所以在空间上是要占用略多一些的。不过，由于它良好的对称性，使得为某个结点的前后结点的操作带来了方便，可以有效提高算法的时间性能。说白了，就是用空间来换时间。

第四章栈和队列¶

栈的定义：

桟（stack）是限定仅在表尾进行插入和删除操作的线性表。

我们把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），不含任何数据元素的栈称为空栈。栈又称为 后进先出（Last In First Out）的线性表，简称 LIFO 结构

首先它是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系。只不过它是一种特殊的线性表而已。定义中说是在线性表的表尾进行插入和删除操作，这里表尾是指栈顶，而不是栈底。

它的特殊之处就在于限制了这个线性表的插入和删除位置，它始终只在栈顶进行。

这也就使得：栈底是固定的，最先进栈的只能在栈底。

栈的插入操作，叫作进栈，也称压栈、入栈。类似子弹入弹夹。
栈的删除操作，叫作出栈，有的也叫作弹栈。如同弹夹中的子弹出夹。

栈的顺序存储结构¶

既然桟是线性表的特例，那么 栈的顺序存储 其实也是线性表顺序存储的简化，我们简称为 顺序栈。线性表是用数组来实现的，想想看，对于栈这种只能一头插入删除的线性表来说，用数组哪一端来作为栈顶和栈底比较好？

对，没错，下标为 0 的一端作为栈底比较好，因为首元素都存在栈底，变化最小，所以让它作栈底。

我们定义一个 top 变量来指示顶元素在数组中的位置，top 就如同中学物理学过的游标卡尺的游标，它可以来回移动，意味着栈顶的 top 可以变大变小，但无论如何游标不能超出尺的长度。同理，若存储栈的长度为 StackSize，则栈顶位置 top 必须小于 StackSize 当栈存在一个元素时，top 等于 0，因此通常把空栈的判定条件定为 top 等于 -1。

两栈共享空间¶

同一个数组内有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为 0 处，另一个栈为数组的末端，即下标为数组长度 n-1 处。这样，两个栈如果增加元素，就是两端点向中间延伸。

其实关键思路是：它们是在数组的两端，向中间靠拢。top1 和 top2 是栈 1 和栈 2 的栈顶指针，可以想象，只要它们俩不见面，两个栈就可以一直使用。

从这里也就可以分析出来，栈 1 为空时，就是 top 等于 -1 时；而当 top2 等于 n 时，即是栈 2 为空时，那什么时候栈满呢?

两个栈见面之时，也就是两个指针之间相差1时，即 top1+1=top2 为栈满。

事实上，使用这样的数据结构，通常都是当两个栈的空间需求有相反关系时，也就是一个栈增长时另一个栈在缩短的情况。就像买卖股票一样，你买入时，一定是有一个你不知道的人在做卖出操作。这样使用两栈共享空间存储方法才有比较大的意义。否则两个栈都在不停地增长，那很快就会因栈满而溢出了。

栈的链式存储结构¶

栈的链式存储结构，简称为链栈。

由于单链表有头指针，而栈顶指针也是必需的，那干嘛不让它俩合二为一呢？所以比较好的办法是把栈顶放在单链表的头部。另外，都已经有了栈顶在头部了，单链表中比较常用的头结点也就失去了意义，通常对于链栈来说，是不需要头结点的。

对于链栈来说，基本不存在栈满的情况，除非内存已经没有可以使用的空间，如果真的发生，那此时的计算机操作系统已经面临死机崩溃的情况，而不是这个链栈是否溢出的问题。

但对于空栈来说，链表原定义是头指针指向空，那么链的空其实就是 top=NULL 的时候。

链桟的进栈 push 和出栈 pop 操作都很简单，没有任何循环操作，时间复杂度均为 O(1)。

对比¶

对比一下 顺序栈 与链栈, 它们在时间复杂度上是一样的，均为 O(1)。对于空间性能，顺序栈需要事先确定一个固定的长度，可能会存在内存空间浪费的问题，但它的优势是存取时定位很方便，而链栈则要求每个元素都有指针域，这同时也增加了一些内存开销，但对于栈的长度无限制。

所以它们的区别和线性表中讨论的一样，如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些。

栈的作用¶

栈的引入简化了程序设计的问题，划分了不同关注层次，使得思考范围缩小，更加聚焦于我们要解决的问题核心。而像线性表顺序存储结构用到的数组，因为要分散精力去考虑数组的下标增减等细节问题，反而掩盖了问题的本质。

所以现在的许多高级语言，比如 Java、C# 等都有对栈结构的封装，你可以不用关注它的实现细节，直接使用 Stack 的 push 和 pop 方法，非常方便。

栈的应用 – 递归¶

斐波那契数列的实现¶

序号	1	2	3	4	5	6	7	8	9	10	11	12
值	1	2	3	4	6	8	13	21	34	55	89	244

当 n=0：f(n) = 0
当 n=1：f(n) = 1
当 n>1：f(n) = f(n-1) + f(n-2)

迭代的实现方法：

#include "stdio.h"

int main()
{
    int i;
    int a[40]；;
    printf("迭代显示斐波那契数列：\n");
    a[0]=0;
    a[1]=1;
    printf("%d ",a[0]);  
    printf("%d ",a[1]);  
    for(i = 2;i < 40;i++)  
    { 
        a[i] = a[i-1] + a[i-2];  
        printf("%d ",a[i]);  
    } 
    return 0;
}

递归函数的实现方法：

#include "stdio.h"

/* 斐波那契的递归函数 */
int Fbi(int i)  
{
    if( i < 2 )
        return i == 0 ? 0 : 1;  
    return Fbi(i - 1) + Fbi(i - 2);  /* 这里Fbi就是函数自己，等于在调用自己 */
}  

int main()
{
    int i;
    printf("递归显示斐波那契数列：\n");
    for(i = 0;i < 40;i++)  
        printf("%d ", Fbi(i));  
    return 0;
}

递归的定义¶

在高级语言中，调用自己和其他函数并没有本质的不同。我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称做递归函数。

当然，写递归程序最怕的就是陷入永不结束的无穷递归中，所以，每个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出。比如刚才的例子，总有一次递归会使得 i<2 的，这样就可以执行 return 的语句而不用继续递归了。

对比了两种实现斐波那契的代码。迭代和递归的区别是：迭代使用的是循环结构，递归使用的是循环结构。递归能使程序的结构更清晰、更简洁、更容易让人理解，从而减少读懂代码的时间。但是大量的递归调用会建立函数的副本，会耗费大量的时间和内存。迭代则不需要反复调用函数和占用额外的内存。因此我们应该视不同情况选择不同的代码实现方式。

栈的应用 – 四则运算表达式求值¶

后缀（逆波兰）表示法的定义：一种不需要括号的后缀表达法,我们也把它称为逆波兰（Reverse Polish Notation，RPN）表示。

正常数学表达式：9+(3-1)×3+10÷2
后缀表达式：9 3 1-3 * + 102 / +

叫后缀的原因在于 所有的符号都是在要运算数字的后面出现。显然这里没有了括号。对于从来没有接触过后缀表达式的同学来讲，这样的表述是很难受的。不过你不喜欢，有“人”喜欢，比如我们聪明的计算机。

后缀表达式的计算结果¶

我们先来看看计算机如何应用后缀表达式计算出最终的结果。

规则：从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。

中缀表达式如何转后缀表达式¶

我们把平时所用的标准四则运算表达式，叫做 中缀表达式。因为所有的运算符号都在两数字的中间，现在我们的问题就是中缀到后缀的转化。

规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级不高于栈顶符号（乘除优于加减），则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。

要想让计算机具有处理我们通常的标准(中缀)表达式的能力，最重要的就是以下两步:

将中缀表达式转化为后缀表达式（栈用来进出运算的符号）。
将后缀表达式进行运算得出结果（栈用来进出运算的数字）。

整个过程，都充分利用了的后进先出特性来处理，理解好它其实也就理解好了栈这个数据结构。

队列的定义¶

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列是一种先进先出（First In First Out）的线性表，简称 FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。

循环队列¶

队列顺序存储的不足：

假设一个队列有 n 个元素，则顺序存储的队列需建立一个大于 n 的数组，并把队列的所有元素存储在数组的前 n 个单元，数组下标为 0 的一端即是队头。所谓的入队列操作，其实就是在队尾追加一个元素，不需要移动任何元素，因此时间复杂度为 O(1)。

与栈不同的是，队列元素的出列是在队头，即下标为 0 的位置，那也就意味着，队列中的所有元素都得向前移动，以保证队列的队头，也就是下标为 0 的位置不为空，此时时间复杂度为 O(n)。

可有时想想，为什么出队列时一定要全部移动呢，如果不去限制队列的元素必须存储在数组的前 n 个单元这一条件，出队的性能就会大大增加。也就是说，队头不需要一定在下标为 0 的位置。

为了避免当只有一个元素时，队头和队尾重合使处理变得麻烦，所以引入两个指针， front 指针指向队头元素，rear 指针指向队尾元素的下一个位置，这样当 front 等于 rear 时，此队列不是还剩一个元素，而是空队列。

问题还不止于此。假设这个队列的总个数是 5 个，目前在下标为 3 和 4 的地方有数据，但目前如果接着入队的话，因数组末尾元素已经占用，再向后加，就会产生数组越界的错误，可实际上，我们的队列在下标为 0、1、2 的地方还是空闲的。我们把这种现象叫做 “假溢出”。

所以解决假溢出的办法就是后面满了，就再从头开始，形成一个头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为 循环队列。

队列空时，front 等于 rear；
队列满时，front 和 rear 中还有一个空闲单元。

由于 rear 可能比 front 大，也可能比 front 小，所以尽管它们只相差一个位置时就是满的情况，但也可能是相差整整一圈。所以若队列的最大尺寸为 QueueSize，那么 队列满的条件是：

(rear+1)%QueueSize == front(取模 “%” 的目的就是为了整合 rear 与 front 大小为一个问题)。

比如，QueueSize =5：

front=0，而 rear=4，那么 (4+1)%5=0，所以此时队列满；
front=2，而 rear=1，那么 (1+1)%5=2，所以此时队列满；
front=2，而 rear=0，那么 (0+1)%5=1，1≠2，所以此时队列没有满；

队列长度分为两段，一段是 QueueSize-front，另一段是 0+rear，加在一起，队列长度为 rear - front + QueueSize。因此 通用的计算队列长度的公式 为：

(rear - front + QueueSize)%QueueSize

队列的链式存储结构及实现¶

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。为了操作上的方便，我们将队头指针指向链队列的头结点，而队指针指向终端结点。空队列时，front 和 rear 都指向头结点。

对于循环队列与链队列的比较¶

可以从两方面来考虑，从时间上，其实它们的基本操作都是常数时间，即都为 O(1) 的，不过循环队列是事先申请好空间，使用期间不释放，而对于链队列，每次申请和释放结点也会存在一些时间开销，如果入队出队频繁，则两者还是有细微差异。对于空间上来说，循环队列必须有一个固定的长度，所以就有了存储元素个数和空间浪费的问题。而链队列不存在这个问题，尽管它需要一个指针域，会产生一些空间上的开销，但也可以接受。所以在空间上，链队列更加灵活。

总的来说，在可以确定队列长度最大值的情况下，建议用循环队列，如果你无法预估队列的长度，则用链队列。

总结¶

又到了总结回顾的时间。我们这一章讲的是栈和队列，它们都是特殊的线性表，只不过对插入和删除操作做了限制。

桟（stack）是限定仅在表尾进行插入和删除操作的线性表。
队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

它们均可以用线性表的顺序存储结构来实现，但都存在着顺序存储的一些弊端。因此它们各自有各自的技巧来解决这个问题。

对于栈来说，如果是两个相同数据类型的栈，则可以用数组的两端作栈底的方法来让两个栈共享数据，这就可以最大化地利用数组的空间。

对于队列来说，为了避免数组插入和删除时需要移动数据，于是就引入了循环队列，使得队头和队尾可以在数组中循环变化。解决了移动数据的时间损耗，使得本来插入和删除是 O(n) 的时间复杂度变成了 O(1)。

它们也都可以通过链式存储结构来实现，实现原则上与线性表基本相同。

栈：

顺序栈
- 两栈共享空间
链栈

队列：

顺序队列
- 循环队列
链队列

第一章 数据结构绪论¶

数据¶