绪论

基础概念和术语

数据

数据：数据是描述客观事物的符号，是计算机可以操作的对象。
- 数据不仅仅包括整型实型等数值类型，还包括字符及声音、图像等非数值类型。
- 对于整型、实型等数据类型，可以进行数值计算
- 对于字符数据类型，就需要进行非数值的处理，而声音、图像、视频等可以通过编码的手段变为字符数据来处理

数据元素

数据元素：是组成数据的、有一定意义的基本单位，在计算机中通常作为一个整体处理
- 在人类中，数据元素为人
- 在畜类中，数据元素是牛、马、羊等动物

数据项

数据项：数据项是数据元素的组成部分，一个数据元素可以由多个数据项组成。
- 人如果作为数据元素，那么人的眼、耳、鼻、手、等部位就可以作为数据项，姓名，年龄，联系电话等也可以作为数据项，具体哪些作为数据项应当根据所处系统来决定
- 数据项是数据不可分割的最小单位，但在真正讨论问题时，数据元素才是数据结构建立数据模型的着眼点。就像讨论电影角色时，是针对角色整体讨论，而不是针对角色的姓名或年龄这样的“数据项”

数据对象

数据对象：是性质相同的数据元素的集合，是数据的子集
性质相同：数据元素具有相同数量和类型的数据项即为性质相同。比如，人都有名字、性别、年龄等相同的数据项
数据对象是数据的子集，在实际应用中，处理的数据元素通常有相同性质，在不产生混淆的情况下，我们习惯将数据对象简称为数据

数据结构

数据结构：是指数据元素之间的关系，它是数据的组织形式。数据结构可以分为逻辑结构和物理结构。

逻辑结构与物理结构

逻辑结构

逻辑结构：是指数据对象中数据元素之间的相互关系
逻辑结构分为四类：
- 集合结构
  - 元素之间的共同属性只有同属一个集合
- 线性结构
  - 元素之间关系一对一，呈线状
- 树形结构
  - 元素之间关系一对多，比如一个上司有多位下属
- 图形结构
  - 元素之间关系多对多，比如一个人有多个朋友

物理结构

物理结构也称为存储结构，指数据的逻辑结构在计算机中的存储形式
数据的存储形式有两种：
- 顺序存储
  - 将数据元素存放在地址连续的存储单元
- 链式存储
  - 将数据元素存放在任意的存储单元，通过指针连接起来

逻辑结构是面向问题的，而物理结构是面向计算机的，其基本目标是将数据及其逻辑关系存储到计算机内存中

算法

数据结构与算法的关系

举个栗子

今天是你女友生日，你打算请女友去看爱情音乐剧，到了戏院，抬头一看——《梁山伯》18：00开演。嗯，怎么会是这样？一问才知，今天饰演祝英台的演员生病，所以梁山伯唱独角戏。真是搞笑了，这还有什么看头。于是你们打算去看爱情电影。到了电影院，一看海报——《罗密欧》，是不是名字写错了，问了才知，原来饰演朱丽叶的演员因为嫌弃演出费用太低，中途退演了。制片方考虑到已经开拍，于是就把电影名字定为《罗密欧》，主要讲男主角的心路旅程。哎，这电影还怎么看啊？

数据结构是存储和组织数据的方式
- 比如数组、链表、栈、队列等
- 它决定了数据在计算机内存里的排布方式，以及访问、插入、删除等操作的效率
算法是操作数据的步骤和方法
- 比如排序算法(快排，归并)、查找算法(二分查找)等
- 它决定了数据的操作效率，是解决问题的基础

算法需要依赖数据结构来实现，数据结构的设计往往也是为了支撑高效的算法

特性和要求

算法是描述解决问题的方法
算法具有五个基本特性：
- 输入
- 输出
- 有穷性
  - 主要指算法在执行有限的步骤会自动结束，且这个时间不应很长，否则算法的意义也就不大了
- 确定性
  - 算法每一步都有确定的含义，不会出现二义性，相同的输入应当得到唯一的输出
- 可行性
算法的设计要求:
- 正确性
  - 算法应当满足问题定义的要求，即算法的输出应当是满足问题要求的
  - 但正确也有很大区别，大致分为四个层次
    - 第1层：没有语法错误
    - 第2层：对于合法的输入数据能产生满足要求的结果
    - 第3层：对于非法的输入数据能返回规格说明的结果
    - 第4层：即使面对精心选择的，甚至刁难的测试数据也有满足要求的输出结果
  - 一般情况下,以层次三作为判断算法是否正确的标准
- 可读性
  - 算法应当是容易理解的，能够被人阅读和理解
- 健壮性
  - 算法应当对非法输入有良好的处理能力，即当输入数据不满足问题定义的要求时，算法应当能够正确地处理，而不是崩溃或产生莫名其妙的结果
- 时间效率高
  - 算法应当在执行时间方面尽可能地高效
- 存储量低
  - 算法应当在存储量方面尽可能地低

算法效率的度量方法

事后统计方法

这种方法主要是通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低。但这种方法显然有很大的缺陷：
- 必须依据算法实现编制好测试程序
- 时间的比较可能会因为计算机硬件和软件等环境因素而掩盖算法本身的优劣
- 算法测试数据设计困难，数据规模的不同对于算法的效率也有很大的影响

事前分析估算法

事前分析估算法：在计算机程序编制前，依据统计方法对算法进行估算。

经过分析，我们发现，一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：

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

第1条当然是算法好坏的根本，第2条要由软件来支持，第4条要看硬件性能。也就是说，抛开这些与计算机硬件、软件有关的因素，一个程序的运行时间，依赖于算法的好坏和问题的输入规模。所谓问题输入规模是指输入量的多少。

分析两种求和的算法：

第一种算法：

int i,sum 0,n 100;
/*执行1次*/
for(i=1;i<=n;i++) /* 执行了n+1次 */
{
    sum sum +i;   /*执行n次*/
}
printf ("&d",sum);/*执行1次*/

第二种算法：

1
2
3

int sum=0,n=100;  /*执行1次*/
sum=(1+n)*n/2;    /*执行1次*/
printf("%d", sum);/*执行1次*/

显然第一种算法，执行了更多次才得到结果，两种算法的第一条和最后一条语句一致，我们重点关注的是算法的中间部分，故忽略头尾的开销，那么这两个算法其实就是n次与1次的差距，算法好坏显而易见。
继续延伸：

int i,j x 0,sum 0,n 100; /*执行一次*/
for (i 1;i <n;i++){
    for (j=1;j<=n;j++){
        X++;            /*执行n×n次*/
        sum+=x;
    }
}
printf("%d",sum);       /*执行一次*/

可以看到在这个算法中，循环部分代码整体执行n²次，显然对同样的输入规模n = 100，该算法运算次数更多，执行时间随着n增加也远远多于前面两个。
我们在分析算法的运行时间时，重要的是把基本操作的数量与输入规模关联起来。

衡量方式

不同的算法面对不同规模的输入数据，执行效率也有很大的差别。我们对算法引入复杂度的概念，
衡量一个算法的复杂程度用到以下两个指标
- 时间复杂度
- 空间复杂度
- 我们在描述一个算法的复杂度时，其实不需要计算精确的执行次数，算出大概次数即可，这里我们使用0渐进表示法
  - 大O符号：用于描述函数渐进行为的数学符号
推导大O阶
1. 用常数1取代运行时间中的所有加法常数。
2. 在修改后的运行次数函数中，只保留最高阶项。
3. 如果最高阶项存在且不是1，则去除与这个项相乘的常数。
在不同的复杂度下，可能n小的时候还没什么感觉，但是当n变得非常大时，差距就不是一点半点了，我们来看看常用函数的增长曲线：
常用的时间复杂度所耗费的时间从小到大依次是：

总结回顾

算法的定义：算法是解决特定问题求解步骤的描述，在计算机中为指令的有限序列，并且每条指令表示一个或多个操作。
算法的特性：有穷性、确定性、可行性、输入、输出。
算法的设计的要求：正确性、可读性、健壮性、高效率和低存储量需求。
算法特性与算法设计容易混，需要对比记忆。
算法的度量方法：事后统计方法（不科学、不准确）、事前分析估算方法。
推导大O阶：
- 用常数1取代运行时间中的所有加法常数。
- 在修改后的运行次数函数中，只保留最高阶项。
- 如果最高阶项存在且不是1，则去除与这个项相乘的常数。

有的人认为现在CPU越来越快，根本不用考虑算法的效率优劣，实现功能即可，用户感觉不到算法好坏造成的快慢。事实是这样的吗？

答案是否定的，算法的效率是非常重要的，因为算法的效率直接影响到程序的运行时间，而程序的运行时间直接影响到用户的体验。
假设在短短几年内CPU速度提高了100倍，而我们的某个程序原本可以用时间复杂度为O(n)的算法实现，却写出了O(n²
)的程序,仅仅是因为容易写。即在O(n²)的时间复杂度算法程序下，速度其实只是提高了10倍，但在对于O(n)时间复杂度的算法是真正的提高了100倍

线性表

blue 举个栗子

在幼儿园放学时，经常能看到老师带着小朋友们，一个拉着另一个的衣服，依次从教室出来。而且观察几次便能发现，每次小朋友的排列次序都是一样的。比如小明排在第五个，每次他便都是第五个，前面一直是那个小女孩，后面一直是那个小男孩。为什么一定要这样？
老师解释道，这样可以保证小朋友的安全，避免遗漏。事先规定好了，谁在谁的前面，谁在谁的后面。这样养成习惯后，如果有谁没有到位，他前面和后面的小朋友就会主动报告老师，某人不在。即使以后如果要外出到公园或博物馆等情况下，老师也可以很快地清点人数，万一有人走丢，也能在最快时间知道，及时去寻找。
这种排好队的组织方式，便是线性表。

定义

线性表（List）：零个或多个数据元素的有限序列。从名字上就能理解到，线性表是“线性”的，即数据元素之间是线性的
- 线性表是一个序列，也就是说元素之间是有序，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且只有一个前驱和后继。
- 如果一个小朋友去拉两个小朋友后面的衣服，那就不可以排成一队了；同样，如果一个小朋友后面的衣服，被两个甚至多个小朋友拉扯，这其实是在打架，而不是有序排队。
- 线性表是有限的,小朋友班级人数是有限的，元素个数当然也是有限的。事实上，在计算机中处理的对象都是有限的，那种无限的数列，只存在于数学的概念中。

cyan yellow 判断是否为线性表

公司的组织架构，总经理管理几个总监，每个总监管理几个经理，每个经理都有各自的下属和员工。这样的组织架构是不是线性关系呢？
- 不是，为什么不是呢？哦，因为每一个元素，都有不只一个后继，所以它不是线性表。那种让一个总经理只管一个总监，一个总监只管一个经理，一个经理只管一个员工的公司，俗称皮包公司，岗位设置等于就是在忽悠外人。
班级同学之间的友谊关系，是不是线性关系？
- 不是，因为每个人都可以和多个同学建立友谊，不满足线性的定义。嗯？有人说爱情关系就是了。胡扯，难道每个人都要有一个爱的人和一个爱自己的人，而且他们还都不可以重复爱同一个人这样的情况出现，最终形成一个班级情感人物串联？这怎么可能，也许网络小说里可能出现，但现实中是不可能的。
班级同学的点名册，是不是线性表？
- 是，这和刚才的友谊关系是完全不同了，因为它是有限序列，也满足类型相同的特点。这个点名册（如表3-2-1所示）中，每一个元素除学生的学号外，还可以有同学的姓名、性别、出生年月什么的，这其实就是我们之前讲的数据项。在较复杂的线性表中，一个数据元素可以由若干个数据项组成。
一群同学排队买演唱会门票，每人限购一张，此时排队的人群是不是线性表？
- 是，对的。此时来了三个同学要插当中一个同学A的队，说同学A之前拿着的三个书包就是用来占位的，书包也算是在排队。如果你是后面早已来排队的同学，你们愿不愿意？肯定不愿意，书包怎么能算排队的人呢，如果这也算，我浑身上下的衣服裤子都在排队了。于是不让这三个人进来。
- 这里用线性表的定义来说，是什么理由？嗯，因为要相同类型的数据，书包根本不算是人，当然排队无效，三个人想不劳而获，自然遭到大家的谴责。

基础功能

线性表一般需要包含以下功能：
- 初始化线性表： 将一个线性表进行初始化，得到一个全新的线性表。
- 获取指定位置上的元素： 直接获取线性表指定位置i上的元素。
- 获取元素的位置： 获取某个元素在线性表上的位置i。
- 插入元素： 在指定位置i上插入一个元素。
- 删除元素： 删除指定位置i上的一个元素。
- 获取长度： 返回线性表的长度。
简单来说它就是列表，比如我们的菜单，我们在点菜时就需要往菜单列表中添加菜品或是删除菜品，这时列表就很有用了，因为数组长度固定、操作简单，而我们添加菜品、删除菜品这些操作又要求长度动态变化、操作多样。
实现线性表的结构一般有两种，一种是顺序存储实现，还有一种是链式存储实现，我们先来看第一种，也是最简单的的一种。

顺序存储结构

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素
顺序存储是在内存中找了一部分空间，通过“占位”的方式，占据一定的内存空间，然后将相同数据类型的数据元素依次放到这块空地。
因为线性表的每个数据元素类型相同，所以可以使用一维数组来实现顺序存储结构。
存储方式
举个栗子
在图书馆给朋友占座时，如果图书馆里空座很多，不必一定要选择第一排第一个位子，而是可以选择风水不错、适合自己的地儿。找到后，放一个书包在第一个位置，就表示从这开始，这地方暂时归我了。为了建立一个线性表，要在内存中找一块地，于是这块地的第一个位置就非常关键，它是存储空间的起始位置。
因为一共要帮五个朋友占座，所以需要占六个座。线性表中，我们估算这个线性表的最大存储容量，建立一个数组，数组的长度就是这个最大存储容量。
可现实中，总有那么几个不是很好学的人，为了游戏，为了恋爱，就不去图书馆自习了。假设我们六个人，去了四个，真正被使用的座位也就只是四个，另两个是空的。同样的，我们已经有了起始的位置，也有了最大的容量，于是我们可以在里面增加数据了。随着数据的插入，我们线性表的长度开始变大，不过线性表的当前长度不能超过存储容量，即数组的长度。想想也是，如果我们有九个人，只占了六个座，自然是坐不下的。

线性表顺序存储的结构代码

#define MAXSIZE 20
/*存储空间初始分配量*/
typedef int ElemType;
/*ElemType类型根据实际情况而假设为int*/
typedef struct
E1 emType data[MAXSIZE];/*数组存储数据元素，最大值为MAXSIZE*/
int length;
/*线性表当前长度*/

顺序存储结构需要三个属性：

存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置。
线性表的最大存储容量：数组长度MaxSize。
线性表的当前长度：length。

地址计算方式

线性表的起始是1，可C语言中数组的下标是从0开始的，于是线性表的第i个元素实际是存储在数组下标为i-1的位置

用数组存储顺序表意味着要分配固定长度的数组空间，由于线性表中可以进行插入和删除操作，因此分配的数组空间要大于等于当前线性表的长度。
内存中的地址，就和图书馆或电影院里的座位一样，都是有编号的。存储器中的每个存储单元都有自己的编号，这个编号称为地址。当我们占座后，占座的第一个位置确定后，后面的位置都是可以计算的。试想一下，我是班级成绩第五名，我后面的10名同学成绩名次是多少呢？当然是6，7，…、15，因为5+1，5+2，…，5+10。由于每个数据元素，不管它是整型、实型还是字符型，它都是需要占用一定的存储单元空间的。假设占用的是c个存储单元，那么线性表中第i+1个数据元素的存储位置和第i个数据元素的存储位置满足下列关系（LOC表示获得存储位置的函数）。
- LOC（i+1）=LOC（i）+c
所以对于第i个数据元素，其位置为：
- LOC（i）=LOC（i）+（i-1）*c

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

顺序存储结构的插入和删除

插入操作的事例

在春运时去买火车票，大家都排队排的好好的。这时来了一个美女，对着队伍中排在第三位的你说，“大哥，求求你帮帮忙，我家母亲有病，我得急着回去看她，这队伍这么长，你可否让我排在你的前面？”你心一软，就同意了。这时，你必须得退后一步，否则她是没法进到队伍来的。这可不得了，后面的人像蠕虫一样，全部都得退一步。骂声四起。但后面的人也不清楚这加塞是怎么回事，没什么办法。

插入算法的思路：
- 如果插入位置不合理，抛出异常；
- 如果线性表长度大于等于数组长度，则抛出异常或动态增加容量；
- 从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置；
- 将要插入元素填入位置i处；
- 表长加1。

删除操作的事例

接着刚才的例子。此时后面排队的人群意见都很大，都说怎么可以这样，不管什么原因，插队就是不行，有本事，找火车站开后门去。就在这时，远处跑来一胖子，对着这美女喊，可找到你了，你这骗子，还我钱。只见这女子二话不说，突然就冲出了队伍，胖子追在其后，消失在人群中。哦，原来她是倒卖火车票的黄牛，刚才还装可怜。于是排队的人群，又像蠕虫一样，均向前移动了一步，骂声渐息，队伍又恢复了平静。

删除算法的思路：
- 如果删除位置不合理，抛出异常；
- 取出删除元素；
- 从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置；
- 表长减1。
分析插入和删除的时间复杂度
- 最好的情况：如果元素要插入到最后一个位置，或者删除最后一个元素，此时时间复杂度为O(1)，因为不需要移动元素的，就如同来了一个新人要正常排队，当然是排在最后，如果此时他又不想排了，那么他一个人离开就好了，不影响任何人。
- 最坏的情况：如果元素要插入到第一个位置，或者删除第一个元素，此时时间复杂度为O(n)，因为需要移动n个元素。
- 平均情况：如果元素要插入到中间位置，或者删除中间位置的元素，此时时间复杂度为O(n)，因为需要移动n/2个元素。
顺序存储结构的优缺点：

这说明线性表的顺序存储结构，在存、读数据时，不管是哪个位置，时间复杂度都是O(1)；而插入或删除时，时间复杂度都是O(n)。这就说明，它比较适合元素个数不太变化，而更多是存取数据的应用。

顺序存储结构的实现

创建一个顺序存储结构的线性表

首先定义一个结构体类型，将用到的数据保存在一起，以int类型为例

typedef int E;  //这里我们的元素类型就用int为例吧，先起个别名

struct List {
    E array[10];   //实现顺序表的底层数组
    int capacity;   //表示底层数组的容量
    int size;   //表示当前线性表中的元素个数
};

为了使用方便，为结构体的指针取别名

1 2	//因为是数组实现，所以就叫ArrayList，这里直接将List的指针起别名 typedef struct List* ArrayList;

编写线性表的初始化操作，初始化数组容量

void initList(ArrayList list){
    list->capacity = 10;   //直接将数组的容量设定为10即可
    list->size = 0;   //初始时，表中没有元素，所以元素数量为0
}

刚才是直接将顺序表长度设置为10，但顺序表的长度一般为动态的，所以我们选择直接用一个指针来指向底层数组的内存区域，当装不下的时候，我们可以创建一个新的更大的内存空间来存放数据，这样就可以实现扩容了
同时初始化顺序表还有申请内存失败的可能，应当返回一个结果告诉调用者，修改一下之前的代码

struct List {
    E * array;   //指向顺序表的底层数组
    int capacity;   //数组的容量
    int size;   //表中的元素数量
};

_Bool initList(ArrayList list){
    list->array = malloc(sizeof(int) * 10);
    if(list->array == NULL) return 0;  //需要判断如果申请的结果为NULL的话表示内存空间申请失败
    list->capacity = 10;
    list->size = 0;
    return 1;   //正常情况下返回true也就是1
}

编写插入操作

先设计好对应的函数

1
2
3

void insertList(ArrayList list, E element, int index){
    	//list就是待操作的表，element就是需要插入的元素，index就是插入的位置（注意顺序表的index是按位序计算的，从1开始，一般都是第index个元素）
}

按照先前的思路编写代码

void insertList(ArrayList list, E element, int index){
    for (int i = list->size; i > index - 1; i--)  //先使用for循环将待插入位置后续的元素全部丢到后一位
        list->array[i] = list->array[i - 1];
    list->array[index - 1] = element;    //挪完之后，位置就腾出来了，直接设定即可
    list->size++;   //插入之后相当于多了一个元素，记得size + 1
}

测试插入函数

void printList(ArrayList list){   //编写一个函数用于打印表当前的数据
    for (int i = 0; i < list->size; ++i)   //表里面每个元素都拿出来打印一次
        printf("%d ", list->array[i]);
    printf("\n");
}

int main() {
    struct List list;
    if(initList(&list)){
        insertList(&list, 666, 1);  //每次插入操作后都打印一下表，看看当前的情况 
        printList(&list);
        insertList(&list, 777, 1);
        printList(&list);
        insertList(&list, 888, 2);
        printList(&list);
    } else{
        printf("顺序表初始化失败，无法启动程序！");
    }
}

判断数据合法性

此时正常插入便能成功进行，但如果我们在非法的位置插入元素依旧会有问题,比如这个位置小于0或者大于现在的元素数量，故我们应当检查插入位置是否合法

转换成位序，也就是[1, size + 1]这个闭区间，所以我们在一开始的时候进行判断：

_Bool insertList(ArrayList list, E element, int index){
    if(index < 1 || index > list->size + 1) return 0;   //如果在非法位置插入，返回0表示插入操作执行失败
    for (int i = list->size; i > index - 1; i--)
        list->array[i] = list->array[i - 1];
    list->array[index - 1] = element;
    list->size++;
    return 1;   //正常情况返回1
}

扩容顺序表

如果我们的表已经装满了，也就是说size已经达到申请的内存空间最大的大小了，那么此时我们就需要考虑进行扩容了，否则就没办法插入新的元素了：

_Bool insertList(ArrayList list, E element, int index){
    if(index < 1 || index > list->size + 1) return 0;
    if(list->size == list->capacity) {   //如果size已经到达最大的容量了，肯定是插不进了，那么此时就需要扩容了
        int newCapacity = list->capacity + (list->capacity >> 1);   //我们先计算一下新的容量大小，这里我取1.5倍原长度，当然你们也可以想扩多少扩多少
        E * newArray = realloc(list->array, sizeof(E) * newCapacity);  //这里我们使用新的函数realloc重新申请更大的内存空间
        if(newArray == NULL) return 0;   //如果申请失败，那么就确实没办法插入了，只能返回0表示插入失败了
        list->array = newArray;
        list->capacity = newCapacity;
    }
    for (int i = list->size; i > index - 1; i--)
        list->array[i] = list->array[i - 1];
    list->array[index - 1] = element;
    list->size++;
    return 1;
}

realloc函数可以做到控制动态内存开辟的大小，重新申请的内存空间大小就是我们指定的新的大小，并且原有的数据也会放到新申请的空间中，所以非常方便。当然如果因为内存不足之类的原因导致内存空间申请失败，那么会返回NULL，所以别忘了进行判断。

链式存储结构

链式存储结构的引入

顺序存储结构最大的缺点是插入和删除操作时需要移动大量的元素，操作的时间复杂度为O(n)，这是为什么？
- 时间复杂度这么高的原因是在顺序存储结构中，相邻两元素的存储位置也有邻居关系，编号是1,2,3,…,n,他们在内存中的位置也是紧挨着，中间没有空隙，当然不能快速介入，删除后，留下的空隙也需要马上填补上，所以需要频繁操作。
如何解决问题？
- A 同学思路:让当中每个元素之间都留有一个空位置,这样要插入时,就不至于移动。可一个空位置如何解决多个相同位置插入数据的问题呢?所以这个想法显然不行。
- B 同学思路:那就让当中每个元素之间都留足够多的位置,根据实际情况制定空隙大小,比如10个,这样插入时,就不需要移动了。万一 10 个空位用完了,再考虑移动使得每个位置之间都有10个空位置。如果删除,就直接删掉,把位置留空即可。这样似乎暂时解决了插入和删除的移动数据问题。可这对于超过10个同位置数据的插入,效率上还是存在问题。对于数据的遍历,也会因为空位置太多而造成判断时间上的浪费。而且显然这里空间复杂度还增加了,因为每个元素之间都有若干个空位置。
- C 同学思路:我们反正也是要让相邻元素间留有足够余地,那干脆所有的元素都不要考虑相邻位置了,哪有空位就到哪里,而只是让每个元素知道它下一个元素的位置在哪里,这样,我们可以在第一个元素时,就知道第二个元素的位置(内存地址),而找到它;在第二个元素时,再找到第三个元素的位置(内存地址)。这样所有的元素我们就都可以通过遍历而找到。

这里C同学的思路便是链表的雏形，链式存储结构就是基于这个思路的。
链式存储结构中，每个结点都存储一个数据，以及一个指向下一个元素的指针。这样，我们只需要一个指针就可以找到任意一个元素，从而实现数据的遍历。

链表结构

链表中，对于数据元素a_i来说，除了存储其本身的数据信息，还需要存储一个指示其直接后继的信息，我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素a_i的存储映像，称为结点（Node）。
对于线性表来说，总得有头有尾，链表也不例外，我们通常将链表中第一个结点的存储位置叫做头指针，整个链表的存取必须是从头指针开始进行。之后的每一个结点，其实就是上一个的后继指针指向的位置,知到最后一个检点指针为”空”(通常用NULL或“^”符号表示)
同时为了更方便的对链表进行操作，在单链表的第一个节点前还会添加一个头结点，这个头结点不存储数据，只存储一个指针域，这个指针域指向第一个结点。

单链表的读取

在线性表的顺序存储结构中，我们要计算任意一个元素的存储位置非常容易。但在单链表中，由于第i个元素到底在哪个位置，没办法一开始就知道，必须得从头开始找。因此，对于单链表实现获取第i个元素的数据的操作GetElem，在算法上，相对要麻烦一些。

获得链表第i个数据的算法思路：

声明一个指针p指向链表第一个结点，初始化j从1开始；
当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1；
若到链表末尾p为空，则说明第i个结点不存在；
否则查找成功，返回结点p的数据。

说白了，就是从头开始找，直到第i个结点为止。所以最坏情况的时间复杂度是O(n)。
此时就有人说，这么麻烦，这数据结构有什么用！还不如顺序存储结构呢。
哈，世间万物总是两面的，有好自然有不足，有差自然就有优势。下面来看一下在单链表中的如何实现“插入”和“删除”。

单链表的插入和删除

此处想在节点p的后方插入一个节点s，使其成为p的后继节点，该如何操作？

用不着更改其他节点，只需要让s->next和p->next的指针做一点改变即可。
1
2
s->next=p->next;
p->next=s;

这两句的顺序可以交换吗？

一定不能交换
交换后会将p->next的指针指向s，而s->next的指针指向p，这样p就无法找到它的后继节点了。后面的节点相当于断掉了。

单链表第i个数据插入结点的算法思路：

声明一指针p指向链表头结点，初始化j从1开始；
当j < i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1；
若到链表末尾p为空，则说明第i个结点不存在；
否则查找成功，在系统中生成一个空结点s；
将数据元素e赋值给s->data；
单链表的插入标准语句s->next=p->next;p->next=s；
返回成功。

现在我们再来看单链表的删除。设存储元素a_i的结点为q实现将结点q删除单链表的操作，其实就是将它的前继结点的指针绕过，指向它的后继结点即可

只需要将p的指针指向q的指针，即p->next=q->next即可

1	p->next=q->next;

单链表第i个数据删除结点的算法思路：

声明一指针p指向链表头结点，初始化j从1开始；
当j < i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1；
若到链表末尾p为空，则说明第i个结点不存在；
否则查找成功，将欲删除的结点p->next赋值给q；
单链表的删除标准语句p->next=q->next；
将q结点中的数据赋值给e，作为返回；
释放q结点；
返回成功。

单链表整表创建

回顾一下，顺序存储结构的创建，其实就是一个数组的初始化，即声明一个类型和大小的数组并赋值的过程。而单链表和顺序存储结构就不一样，它不像顺序存储结构这么集中，它可以很散，是一种动态结构。
创建单链表的过程就是一个动态生成链表的过程。即从“空表”的初始状态起，依次建立各元素结点，并逐个插入链表。

单链表整表创建的算法思路：

声明一指针p和计数器变量i；
初始化一空链表L；
让L的头结点的指针指向NULL，即建立一个带头结点的单链表；
循环：
- 生成一新结点赋值给p；
- 随机生成一数字赋值给p的数据域p->data；
- 将p插入到头结点与前一新结点之间。

这个算法思路中，其实用的是插队的方法，始终让新节点在第一的位置，这种方法也叫做头插法

事实上，我们完全可以把新结点插入到最后，这才符号排队的正常思维，所谓的先来后到。我们把每次新结点都插在终端结点的后面，这种算法称为尾插法。

单链表尾插法的算法思路：

声明一指针p和计数器变量i；
初始化一空链表L；
让L的头结点的指针指向NULL，即建立一个带头结点的单链表；
循环：
- 生成一新结点赋值给p；
- 随机生成一数字赋值给p的数据域p->data；
- 将表尾终端节点的指针指向新节点
- 将当前新节点定义为尾端终端节点

单链表整表删除

单链表整表删除的算法思路如下：

声明一指针p和q；
将第一个结点赋值给p；
循环：
- 将下一结点赋值给q；
- 释放p；
- 将q赋值给p。

有人认为q变量没有存在的意义，将q替换为p->next即可，这会带来什么问题？

p指向一个结点，它除了有数据域，还有指针域。你在做free(p)时，其实是在对它整个结点进行删除和内存释放的工作,如果结点删除了，上哪还能继续使用p->next跳转到下一个节点呢

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

得到一些经验性的结论：
- 线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。若需要频繁插入和删除时，宜采用单链表结构。比如说游戏开发中，对于用户注册的个人信息，除了注册时插入数据外，绝大多数情况都是读取，所以应该考虑用顺序存储结构。而游戏中的玩家的武器或者装备列表，随着玩家的游戏过程中，可能会随时增加或删除，此时再用顺序存储就不太合适了，单链表结构就可以大展拳脚。当然，这只是简单的类比，现实中的软件开发，要考虑的问题会复杂得多。
- 线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构，这样可以不需要考虑存储空间的大小问题。而如果事先知道线性表的大致长度，比如一年12个月，一周就是星期一至星期日共七天，这种用顺序存储结构效率会高很多。

静态链表

静态链表的引入

C语言中的指针，使得它可以非常容易地操作内存中的地址和数据，这比其他高级语言更加灵活方便。后来的面向对象语言，如Java、C#等，虽不使用指针，但因为启用了对象引用机制，从某种角度也间接实现了指针的某些作用。
但对于一些语言，如Basic、Fortran等早期的编程高级语言，由于没有指针，链表结构按照前面我们的讲法，它就没法实现了。怎么办呢？
有人便想出用数组代替指针来描述单链表。

让数组的元素都是由两个数据域组成，data和cur。数据域data，用来存放数据元素，也就是通常我们要处理的数据；而cur相当于单链表中的next指针，存放该元素的后继在数组中的下标，我们把cur叫做游标。
我们把这种用数组描述的链表叫做静态链表，这种描述方法还有起名叫做游标实现法。

我们对数组第一个和最后一个元素作为特殊元素处理，不存数据。我们通常把未被使用的数组元素称为备用链表。而数组第一个元素，即下标为0的元素的cur就存放备用链表的第一个结点的下标；而数组的最后一个元素的cur则存放第一个有数值的元素的下标，相当于单链表中的头结点作用，当整个链表为空时，则为0。

静态链表的插入操作

静态链表中要解决的是：如何用静态模拟动态链表结构的存储空间的分配，需要时申请，无用时释放。
在静态链表中，操作的是数组，不存在像动态链表的结点申请和释放问题，所以我们需要自己实现这两个函数，才可以做插入和删除的操作。

静态链表的优缺点

总的来说静态链表其实是为了给没有指针的高级语言设计的一种实现单链表能力的方法。尽管不一定会用得上,但这样的思考方式是非常巧妙的。

循环链表

我们的单链表，如果想实现遍历功能，那么必须从头结点开始遍历，才能一次性把所有节点遍历完，一旦从中间节点开始遍历，那么就无法遍历到所有节点，需要执行第二次遍历，这个问题能解决吗？
将单链表中终端结点的指针端由空指针改为指向头结点,就使整个单链表形成一个环,通过这种操作，使得遍历完链表尾部后能继续遍历前面未遍历的部分，这种头尾相接的单链表称为单循环链表,简称循环链表

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

双向链表

我们在单链表中,有了 next 指针,这就使得我们要查找下一结点的时间复杂度为0(1)。可是如果我们要查找的是上一结点的话,那最坏的时间复杂度就是O(n)了,因为我们每次都要从头开始遍历查找。
为了克服单向性这一缺点,我们的老科学家们设计出了双向链表。双向链表(double linked list)是在单链表的每个结点中,再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域,一个指向直接后继,另一个指向直接前驱。

typedef struct DulNode
{
    ElemType data;
    struct DuLNode *prior;
    /*直接前驱指针*/
    struct DuLNode *next;
    /*直接后继指针*/
} DulNode, *DuLinkList;

双向链表是单链表中扩展出来的结构,所以它的很多操作是和单链表相同的,比如求长度的 ListLength,查找元素的 GetElem,获得元素位置的 LocateElem 等,这些操作都只要涉及一个方向的指针即可,另一指针多了也不能提供什么帮助。
双向链表既然是比单链表多了如可以反向遍历查找等数据结构,那么也就需要付出一些小的代价:在插入和删除时,需要更改两个指针变量。
插入操作时,其实并不复杂,不过顺序很重要,千万不能写反了。

s ->prior=p;        /*把p赋值给s的前驱，如图中①*/
s ->next=p ->next;  /*把p->next赋值给s的后继，如图中②*/
p->next->prior=s;   /*把s赋值给p->next的前驱，如图中③*/
p->next=s;          /*把S赋值给p的后继，如图中④*/

关键在于它们的顺序,由于第2步和第3步都用到了 p->next。如果第4步先执行,则会使得 p->next 提前变成了s,使得插入的工作完不成。所以我们不妨把上面这张图在理解的基础上记忆,顺序是先搞定s 的前驱和后继,再搞定后结点的前驱,最后解决前结点的后继。
删除操作同理，若要删除结点p,只需要下面两步骤

p->prior->next=p->next; /*把p->next 赋值给p->prior 的后继,如图中*/
p->next->prior=p->prior; /*把p->prior 赋值给p->next 的前驱,如图中2*/
free (p); /*释放结点*/

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

栈与队列

栈是一种特殊的线性表，栈限定仅在表尾进行插入和删除操作
我们把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的栈称为空栈。栈又称为后进先出(Last In First Out)的线性表,简称 LIFO 结构。
首先栈是一个特殊的线性表,也就是说,栈元素具有线性关系。定义中说是在线性表的表尾进行插入和删除操作,这里表尾是指栈顶,而不是栈底。
它的特殊之处就在于限制了这个线性表的插入和删除位置,它始终只在栈顶进行。这也就使得:栈底是固定的,最先进栈的只能在栈底。

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

栈的抽象数据类型

ADT 栈(stack)
Data
  线性表。元素具有相同的类型,相邻元素具有前驱和后继关系。
Operation
  InitStack (*S):初始化操作,建立一个空栈 S。
  DestroyStack (*S):若栈存在,则销毁它。
  ClearStack (*s):将栈清空。
  StackEmpty (s):若栈为空,返回true,否则返回 false.
  GetTop (S, *e):若栈存在且非空,用e返回S的栈顶元素。
  Push (*S,e):若栈S 存在,插入新元素e到栈S 中并成为栈顶元素。
  Pop (*S, *e):删除栈S 中栈顶元素,并用e返回其值。
  StackLength (S): 返回栈S 的元素个数。
endADT

由于栈本身就是一个线性表,所以线性表的顺序存储和链式存储,对于栈来说,也是同样适用的。

栈的顺序存储结构

栈是线性表的特例,所以栈的顺序存储是线性表顺序存储的简化
因为在栈中元素的插入和删除都在栈顶进行,所以我们存储在数组时，可以以下标为0的一段作为栈底，另一端为栈顶，因为栈底的裱花最小，不会频繁挪动元素。
通常定义top变量来指示栈顶元素的位置，以StackSize变量记录存储栈的长度e,则栈顶位置 top 必须小于 StackSize。当栈存在一个元素时,top 等于0,因此通常把空栈的判定条件定为top 等于-1。

typedef int SElemType; /* SElemType 类型根据实际情况而定,这里假设为int */
typedef struct
{
  SElemType data [MAXSIZE];
  int top; /* 用于栈顶指针 */
}SqStack;

栈普通情况、空栈和栈满的情况示意图如图

进栈和出栈

栈是特殊的线性表，且只能在栈顶进出元素，所以很好实现。

/* 插入元素e为新的栈顶元素 */
Status Push (SgStack *S, SElemType e)
{
  if (S->top == MAXSIZE -1) /* 栈满 */
    return ERROR;
  S->top++;           /* 栈顶指针增加一 */
  S->data[S->top]=e;  /* 将新插入元素赋值给栈顶空间 */
  return OK;
}

/* 删除栈顶元素,用e返回其值 */
Status Pop (SqStack *S, SElemType *e)
{
  if (S->top == -1) /* 栈空 */
    return ERROR;
  *e=S->data[S->top]; /* 将栈顶元素赋值给e */
  S->top--; /* 栈顶指针减一 */
  return OK;
}

两栈共享空间

栈的顺序存储非常方便,因为它只准栈顶进出元素,所以不存在线性表插入和删除时需要移动元素的问题。不过它有一个很大的缺陷,就是必须事先确定数组存储空间大小,万一不够用了,就需要编程手段来扩展数组的容量,非常麻烦。
对于一个栈,我们也只能尽量考虑周全,设计出合适大小的数组来处理,但对于两个相同类型的栈,我们可以做到最大限度地利用其事先开辟的存储空间来进行操作。
实现共享空间的方法：数组有两个端点，两个栈有两个栈底，让一个栈栈底为数组的始端，另一个栈为栈的末端，增加元素时，栈的栈顶部分向中间延伸

关键思路是:它们是在数组的两端,向中间靠拢。top1 和 top2是栈1和栈2的栈顶指针,只要它们俩不见面,两个栈就可以一直使用。从这里也就可以分析出来,栈1为空时,就是 top1 等于-1时;而当top2 等于n时,即是栈2为空时,那什么时候栈满呢?
想想极端的情况,若栈2是空栈,栈1 的 top1 等于n-1时,就是栈1满了。反之,当栈1 为空栈时,top2 等于 0时,为栈2 满。但更多的情况,其实就是两个栈见面之时,也就是两个指针之间相差1时,即top1 + 1 == top2 为栈满。
两栈共享空间的结构

/* 两栈共享空间结构 */
typedef struct
{
  SElemType data[MAXSIZE];
  int topl; /* 栈1栈顶指针 */
  int top2; /* 栈2栈顶指针 */
}SqDoubleStack;

对于栈的push方法，除了插入元素值参数外，还需要有一个判断是栈1还是栈2的栈号参数stackNumber

/* 插入元素e为新的栈顶元素 */
Status Push (SqDoubleStack *S, SElemType e, int stackNumber){
  if (S->top1+1==S->top2) /* 栈已满,不能再 push 新元素了 */
    return ERROR;
  if (stackNumber==1) /* 栈1 有元素进栈 */
    S->data [++S->top1] =e; /* 若栈1 则先 top1+1 后给数组元素赋值 */
  else if (stackNumber==2) /* 栈2 有元素进栈 */
    S->data [ -- S->top2]=e; /* 若栈2则先top2-1后给数组元素赋值 */
  return OK;
}

pop方法也同理，不再赘述

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

栈的链式存储

栈只是栈顶来做插入和删除操作,栈顶放在链表的头部还是尾部呢?由于单链表有头指针,而栈顶指针也是必须的,那干吗不让它俩合二为一呢,所以比较好的办法是把栈顶放在单链表的头部(如图 4-6-1 所示)。另外,都已经有了栈顶在头部了,单链表中比较常用的头结点也就失去了意义,通常对于链栈来说,是不需要头结点的。
对于链栈来说,基本不存在栈满的情况,除非内存已经没有可以使用的空间,如果真的发生,那此时的计算机操作系统已经面临死机崩溃的情况,而不是这个链栈是否溢出的问题。

链栈的结构代码：

typedef struct StackNode
{
  SElemType data;
  struct StackNode *next;
} StackNode, *LinkStackPtr;

typedef struct LinkStack
{
  LinkStackPtr top;
  int count;
}LinkStack;

进栈与出栈

对于链栈的进栈push操作，假设元素值为e的新结点是s, top 为栈顶指针

/* 插入元素e为新的栈顶元素 */
Status Push (LinkStack *S, SElemType e)
{
  LinkStackPtr s= (LinkStackPtr) malloc (sizeof (StackNode) );
  s->data=e;
  s->next=S->top; /* 把当前的栈顶元素赋值给新结点的直接后继*/
  S->top=s;       /* 将新的结点s 赋值给栈顶指针*/
  S->count++;
  return OK;
}

对于栈链的出栈pop操作，假设变量p用来存储要删除的栈顶结点,将栈顶指针下移一位,最后释放p即可

/* 若栈不空,则删除S的栈顶元素,用e返回其值,并返回 OK;否则返回 ERROR */
Status Pop (LinkStack *S, SElemType *e)
{
  LinkStackPtr pi
  if (StackEmpty (*s))
    return ERROR;
  *e=S->top->data;
  p=S->top;           /* 将栈顶结点赋值给p */
  S->top=S->top->next;/* 使得栈顶指针下移一位,指向后一结点,如图4*/
  free (p);           /* 释放结点p */
  S->count--;
  return OK;
}

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

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

栈的作用

栈有啥用啊，不就是一个被限制的线性表吗？为什么要单独引入为一个数据结构呢？
- 这和我们有两只脚可以走路,干吗还要乘汽车、火车、飞机一样。理论上,陆地上的任何地方,你都是可以靠双脚走到的,可那需要多少时间和精力呢?我们更关注的是到达而不是如何去的过程。
- 栈的引入简化了程序设计的问题,划分了不同关注层次,使得思考范围缩小,更加聚焦于我们要解决的问题核心。反之,像数组等,因为要分散精力去考虑数组的下标增减等细节问题,反而掩盖了问题的本质。

栈的应用 ———— 递归

栈有一个很重要的应用:在程序设计语言中实现了递归。
递归定义：把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数,称做递归函数。
实现斐波那契数列问题时，迭代和递归的区别是:
- 迭代使用的是循环结构,递归使用的是选择结构。
- 递归能使程序的结构更清晰、更简洁、更容易让人理解,从而减少读懂代码的时间。但是大量的递归调用会建立函数的副本,会耗费大量的时间和内存。
- 迭代不需要反复调用函数和占用额外的内存。
递归和栈有什么关系呢?这得从计算机系统的内部说起。
- 递归过程退回的顺序是它前行顺序的逆序。在退回过程中,可能要执行某些动作,包括恢复在前行过程中存储起来的某些数据。这种存储某些数据,并在后面又以存储的逆序恢复这些数据,以提供之后使用的需求,显然很符合栈这样的数据结构,因此,编译器使用栈实现递归就没什么好惊讶的了。
- 简单的说,就是在前行阶段,对于每一层递归,函数的局部变量、参数值以及返回地址都被压入栈中。在退回阶段,位于栈顶的局部变量、参数值和返回地址被弹出,用于返回调用层次中执行代码的其余部分,也就是恢复了调用的状态。

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

后缀(逆波兰)表示法定义

在计算机中，我们可以进行四则运算，但是计算机是如何实现先计算括号或者先乘除后加减的计算规则的呢
- 我们可以发现，如果一个计算式中有括号，那么括号一定是成对出现的对于多重括号，最后也一定是完全嵌套匹配的。这用栈结构正好合适，不管栈内有多少括号，只要碰到左括号则将括号进栈，碰到有括号则让最接近栈顶的左括号出栈，期间对数字进行运算。
- 但对于四则运算，括号也只是当中的一部分，先乘除后加减依旧不好实现，该如何有效处理呢？

20世纪50年代,波兰逻辑学家 Jan Łukasiewicz,当时也困惑于如何才可以搞定这个四则运算,最终他想到了一种不需要括号的后缀表达法,我们也把它称为逆波兰(Reverse Polish Notation, RPN)表示。

对于“9+ (3-1)×3+10÷2”,如果要用后缀表示法应该是什么样子:“931-3 * + 102/+”,这样的表达式称为后缀表达式,叫后缀的原因在于所有的符号都是在要运算数字的后面出现。显然,这里没有了括号。

后缀表达式计算结果

先来看看,计算机如何应用后缀表达式计算出最终的结果20的。
后缀表达式: 931-3*+102/+
规则:从左到右遍历表达式的每个数字和符号,遇到是数字就进栈,遇到是符号,就将处于栈顶两个数字出栈,进行运算,运算结果进栈,一直到最终获得结果。

初始化一个空栈。此栈用来对要运算的数字进出使用。
后缀表达式中前三个都是数字,所以9、3、1 进栈

接下来是“一”,所以将栈中的1 出栈作为减数,3出栈作为被减数,并运算3-1得到2,再将2进栈
接着是数字3进栈

后面是“*”,也就意味着栈中 3 和2 出栈,2与3 相乘,得到6,并将6进栈
下面是“+”,所以栈中6和9出栈,9与6相加,得到15,将15 进栈

接着是10与2两数字进栈
接下来是符号“/”,因此,栈顶的2与10出栈,10与2 相除,得到5,将5进栈

最后一个是符号“+”,所以15与5出栈并相加,得到20,将20 进栈
结果是20出栈,栈变为空,

能够看出后缀表达式真的可以很顺利的解决计算的问题，但这个后缀表达式931-3*+102/+是怎么出来的呢？

中缀表达式转后缀表达式

平时所用的标准四则运算表达式,即“9+(3-1)×3+10-2”叫做中缀表达式。

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

初始化一空栈,用来对符号进出栈使用
第一个字符是数字 9,输出 9,后面是符号“+”,进栈。
第三个字符是“(”,依然是符号,因其只是左括号,还未配对,故进栈。
第四个字符是数字3,输出,总表达式为93,接着是“-”,进栈。
接下来是数字1,输出,总表达式为931,后面是符号“)”,此时,我们需要去匹配此前的“(”,所以栈顶依次出栈,并输出,直到“(”出栈为止。此时左括号上方只有“-”,因此输出“-”。总的输出表达式为931-。
接着是数字3,输出,总的表达式为931-3。紧接着是符号“x”,因为此时的栈顶符号为“+”号,优先级低于“x”,因此不输出,“*”进栈。
之后是符号“+”,此时当前栈顶元素“*”比这个“+”的优先级高,因此栈中元素出栈并输出(没有比“+”号更低的优先级,所以全部出栈),总输出表达式为931-3 * +。然后将当前这个符号“+”进栈。也就是说,前6 张图的栈底的“+”是指中级表达式中开头的9 后面那个“+”,而图 4-9-9 左图中的栈底(也是栈顶)的“+”是指“9+(3-1)×3+”中的最后一个“+”。
最后一个数字2,输出,总的表达式为931-3* + 102
因已经到最后,所以将栈中符号全部出栈并输出。最终输出的后缀表达式结果为931-3 * + 102/+

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

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

队列的定义

队列如同一个倾斜的管道，队列是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。
队列是先进先出的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头

循环队列

线性表有顺序存储和链式存储,栈是线性表,所以有这两种存储方式。同样,队列作为一种特殊的线性表,也同样存在这两种存储方式。

队列顺序存储的不足

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

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

虽然现实中在排队时，前面的人离开之后，后面的人就全部向前一步补上空位，但有时想想，为什么非要全部移动呢，如果不去约束队列元素必须在数组前n个单元，那么出队的性能就会大大增加

为了避免当只有一个元素时,队头和队尾重合使处理变得麻烦,所以引入两个指针, front指针指向队头元素,rear指针指向队尾元素的下一个位置,这样当front 等于rear 时,此队列不是还剩一个元素,而是空队列。
假设长度为5 的数组,front 与rear 指针均指向下标为0 的位置。然后入队 a₁、a₂、a₃、a₄, front 指针依然指向下标为0位置,而rear 指针指向下标为4的位置

但是此时问题又出现了，这样前面的空位将不会再次放置元素，随着每次出队和入队，该队列的容量会不断减小，造成假溢出的现象

循环队列定义

循环队列可以用来解决假溢出的现象

当队列发生假溢出时，接着入队a₆,此时将他放置于下标为0处，rear 指针指向下标为1处，。若再入队 a⁷,则 rear 指针就与 front 指针重合,同时指向下标为2的位置

此时问题又出来了,我们刚才说,空队列时, front 等于 rear,现在当队列满时,也是 front 等于 rear,那么如何判断此时的队列究竟是空还是满呢?
办法一是设置一个标志变量 flag,当front == rear, 且flag = 0 时为队列空,当 front == rear, 且 flag = 1 时为队列满。
办法二是当队列空时,条件就是 front = rear,当队列满时,我们修改其条件,保留一个元素空间。也就是说,队列满时,数组中还有一个空闲单元。
重点讨论一下第二种方法,由于rear 可能比 front 大,也可能比front 小,所以尽管它们只相差一个位置时就是满的情况,也可能是相差整整一圈。所以若队列的最大尺寸为 QueueSize,那么队列满的条件是(rear+1)%QueueSize == front
- 取模“%”的目的就是为了整合 rear 与 front 大小为一个问题
- 当rear > front 时，此时队列的长度为rear-front。
- 当rear < front 时,队列长度分为两段,一段是QueueSize-front,另一段是 0 + rear,加在一起,队列长度为rearfront + QueueS

综上，通用的计算队列的长度公式为：

(rear-front + QueueSize) %QueueSize

循环队列解决了假溢出的问题，但一旦设置为循环队列，数组的大小也就没法再扩大了，此时又出现了数组可能溢出的问题，所以我们还需要再研究一下不担心队列长度的链式存储结构

链式结构队列

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

入队和出队

入队操作时,其实就是在链表尾部插入结点

/* 插入元素e为Q的新的队尾元素 */
Status EnQueue (LinkQueue *Q, QElemType e)
{
  QueuePtr s= (QueuePtr) malloc (sizeof (QNode) ) ;
  if (!s) /* 存储分配失败 */
    exit(OVERFLOW);
  s->data=e;
  s->next=NULL;
  Q->rear->next=s; /* 把拥有元素e新结点s赋值给原队尾结点的后继,*/
  Q->rear=s; /* 把当前的s设置为队尾结点,rear 指向s */
  return OK;
}

出队操作时,就是头结点的后继结点出队,将头结点的后继改为它后面的结点,若链表除头结点外只剩一个元素时,则需将rear 指向头结点

Status DeQueue (LinkQueue *Q, QElemType *e)
{
  QueuePtr p;
  if (Q->front==Q->rear)
    return ERROR;
  p=Q->front->next; /* 将欲删除的队头结点暂存给p,*/
  *e=p->data;     /* 将欲删除的队头结点的值赋值给e */
  Q->front->next=p->next; /*将原队头结点后继p->next 赋值给头结点后继,*/
  if (Q->rear==p) /*若队头是队尾,则删除后将 rear 指向头结点,见上图中③ */
    Q->rear=Q->front;
  free (p);
  return OK;
}

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

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

总结回顾

栈和队列都是特殊的线性表，只是对插入和删除操作做了限制。
栈(stack)是限定仅在表尾进行插入和删除操作的线性表。
队列(queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。
它们均可以用线性表的顺序存储结构来实现,但都存在着顺序存储的一些弊端。因此它们各自有各自的技巧来解决这个问题。
- 对于栈来说,如果是两个相同数据类型的栈,则可以用数组的两端作栈底的方法来让两个栈共享数据,这就可以最大化地利用数组的空间。
- 对于队列来说,为了避免数组插入和删除时需要移动数据,于是就引入了循环队列,使得队头和队尾可以在数组中循环变化。解决了移动数据的时间损耗,使得本来插入和删除是0(n)的时间复杂度变成了0(1)。
它们也都可以通过链式存储结构来实现,实现原则上与线性表基本相同

树

树的定义

线性表是一对一的线性结构，可现实中还有许多一对多的情况，树就是专门研究一对多的数据结构。
树(Tree)是n(n≥0)个结点的有限集。n=0 时称为空树。在任
意一棵非空树中:(1)有且仅有一个特定的称为根( Root )的结
点;(2)当n>1 时,其余结点可分为 m(m>0)个互不相交的
有限集 T1、T2、……、Tm,其中每一个集合本身又是一棵树,并
且称为根的子树(SubTree)

结点分类

树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度(Degree)。度为0 的结点称为叶结点(Leaf)或终端结点;度不为0 的结点称为非终端结点或分支结点。除根结点之外,分支结点也称为内部结点。树的度是树内各结点的度的最大值。

其他概念

结点的层次(Level)从根开始定义起,根为第一层,根的孩子为第二层。若某结点在第1层,则其子树的根就在第1+1 层。其双亲在同一层的结点互为堂兄弟。显然图中的D、E、F是堂兄弟,而G、H、I、J也是。树中结点的最大层次称为树的深度(Depth)或高度,当前树的深度为4。
森林(Forest) 是 m (m≥0) 棵互不相交的树的集合。对树中每个结点而言,其子树的集合即为森林。
对比线性表与树的结构,它们有很大的不同

树的存储结构

前面我们学过线性表有顺序存储和链式存储两种结构，树也是这两种结构吗？
先来看看顺序存储结构,用一段地址连续的存储单元依次存储线性表的数据元素。这对于线性表来说是很自然的,但是对于树来说，树的某个节点孩子有多个，无论按照哪种顺序将树的节点存储到数组，结点的存储位置都无法直接反映逻辑关系，所以简单的顺序存储结构是不能满足树的实现要求的。
不过充分利用顺序存储和链式存储结构的特点,完全可以实现对树的存储结构的表示。
这里介绍三种不同的表示法:
- 双亲表示法
- 孩子表示法
- 孩子兄弟表示法。

双亲表示法

每个人可能没有孩子，但是一定有双亲，树这种结构也是这样，除了根节点外,其余每个结点,它不一定有孩子,但是一定有且仅有一个双亲。
我们假设以一组连续空间存储树的结点,同时在每个结点中,附设一个指示器指示其双亲结点到链表中的位置。也就是说,每个结点除了知道自己是谁以外,还知道它的双亲在哪里。

/* 树的双亲表示法结点结构定义 */
#define MAX TREE SIZE 100
typedef int TElemType; /* 树结点的数据类型,目前暂定为整型 */

typedef struct PTNode /* 结点结构 */
{
  TElemType data; /* 结点数据 */
  int parent; /* 双亲位置 */
} PTNode;

typedef struct /* 树结构 */
{
  PTNode nodes [MAX TREE SIZE]; /* 结点数组 */
  int r, n; /* 根的位置和结点数 */
} PTree;

根结点是没有双亲的,所以我们约定根结点的位置域设置为-1,此时，所有的节点都存有它双亲的位置

下标	data	parent
0	A	-1
1	B	0
2	C	0
3	D	1
4	E	2
5	F	2
6	G	3
7	H	3
8	I	3
9	J	4

这样存储，我们可以根据结点快速的找到他的双亲结点，所用时间复杂度为O(1),直到 parent 为-1时,表示找到了树结点的根。可如果想知道结点的孩子是什么,不好意思,需要遍历整个结构才行。
如何改进？
- 增加一个结点最左边孩子的域,不妨叫它长子域,这样就可以很容易得到结点的孩子。如果没有孩子的结点,这个长子域就设置为-1

下标	data	parent	firstchild
0	A	-1	-1
1	B	0	3
2	C	0	4
3	D	1	6
4	E	2	9
5	F	2	-1
6	G	3	-1
7	H	3	-1
8	I	3	-1
9	J	4	-1

对于有0个或1个孩子结点来说,这样的结构是解决了要找结点孩子的问题了。但完全无法体现各兄弟之间的关系,所以我们需要再增加一个域,指向结点的右兄弟。也就是说,每一
个结点如果它存在右兄弟,则记录下右兄弟的下标。同样的,如果右兄弟不存在,赋值为-1

二叉树的定义

二叉树的特点

二叉树是一种特殊的树状结构,它的每个结点最多有两个孩子结点。
二叉树的特点
- 每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。注意不是只有两棵子树，而是最多有。没有子树或者有一棵子树都是可以的。
- 左子树和右子树是有顺序的，次序不能任意颠倒。
- 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树

二叉树的基本形态
- 空二叉树
- 只有一个根结点。
- 根结点只有左子树。
- 根结点只有右子树。
- 根结点既有左子树又有右子树。

特殊二叉树

斜树
- 所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。斜树有很明显的特点，就是每一层都只有一个结点，结点的个数与二叉树的深度相同。
- 有人会想，这也能叫树呀，与我们的线性表结构不是一样吗。对的，其实线性表结构就可以理解为是树的一种极其特殊的表现形式。
满二叉树
- 一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。
- 在满二叉树中，叶子只能出现在最下面一层，且这一层的叶子数必须达到最大。
- 非叶子节点的度一定是2

完全二叉树
- 对一棵具有n个结点的二叉树按层序编号，如果编号为i（1≤i≤n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树

区分满二叉树和完全二叉树
- 满二叉树一定是一棵完全二叉树，但完全二叉树不一定满
- 完全二叉树的所有结点与同样深度的满二叉树，它们按层序编号相同的结点，是一一对应的。
- 图中的树1，因为5结点没有左子树，却有右子树，那就使得按层序编号的第10个编号空档了。同样道理，图中的树2，由于3结点没有子树，所以使得6、7编号的位置空档了。图6中的树3又是因为5编号下没有子树造成第10和第11位置空档，所以这三棵树既不是满二叉树也不是完全二叉树

总结一下完全二叉树和满二叉树的特点：

满二叉树：
- 叶子只能出现在最下一层。
- 非叶子结点的度一定是2。
- 在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。
完全二叉树：
- 叶子结点只能出现在最下两层。
- 最下层的叶子一定集中在左部连续位置。
- 倒数二层，若有叶子结点，一定都在右部连续位置。
- 如果结点度为1，则该结点只有左孩子，即不存在只有右子树的情况。
- 同样结点数的二叉树，完全二叉树的深度最小。

二叉树的性质

性质1：在二叉树的第i层上至多有2^i-1 个结点（i≥1）

这个性质很好记忆
第一层是根结点，只有一个，所以2^1-1 =2⁰ =1。
第二层有两个，2^2-1 =2¹ =2。
第三层有四个，2^3-1 =2² =4。
第四层有八个，2^4-1 =2³ =8。
通过数据归纳法的论证，可以很容易得出在二叉树的第i层上至多有2^i-1 个结点（i≥1）的结论。

性质2：深度为k的二叉树至多有2^k-1个结点（k≥1）

这里看清楚是2^k-1个结点(K≥1)；
深度为k意思就是有k层的二叉树;
如果有一层，至多1=2¹ -1个结点。
如果有二层，至多1+2=3=2² -1个结点。
如果有三层，至多1+2+4=7=2³ -1个结点。
如果有四层，至多1+2+4+8=15=2⁴ -1个结点。
通过数据归纳法的论证，可以得出，如果有k层，此二叉树至多有2^k-1个结点。

性质3：对任何一棵二叉树T，如果其叶子结点数为n₀ ，度为2的结点数为n₂ ，则n₀ =n₂ +1。

一棵二叉树，除了叶子结点外，剩下的就是度为1或2的结点数了，我们设n₁ 为度是1的结点数。则树T结点总数n的计算方法为：n=n₀ +n ₁ +n ₂。
换一个角度，计算一下分支线的数量，我们可以发现，除了根节点外，每生成一个结点，他都对应着一条分支线，故分支线总数为n-1。
度为1的结点他会向外有两个分支线出去，度为2的结点会向外两个分支线出去，所以分支线总数=度为1的结点产生的分支线+度为2的结点产生的分支线，即为n-1=n₁ +n ₂,联立可推导出n₀ =n₂ +1。

性质4：具有n个结点的完全二叉树的深度为|log ₂ n+1|（|x|表示不大于x的最大整数）。

其实根据性质2就可以反推出该性质，因为该二叉树为满二叉树时结点数最多，故一个深度为k-1的满二叉树有2_k-1-1个结点。所以深度为k的完全二叉树至少有2_k-1个结点，最多有2_k-1个结点。逆运算即可根据结点数求出深度。

性质5：如果对一棵有n个结点的完全二叉树（其深度为|log ₂ n|+1）的结点按层序编号（从第1层到第|log ₂ n|+1层，每层从左到右），对任一结点i（1≤i≤n）有：
1．如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点[i/2]
2．如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。
3．如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1。

对于第一条来说是很显然的，i=1时就是根结点。i>1时，比如结点7，它的双亲就是[7/2]=3，结点9，它的双亲就是[9/2]=4。
第二条，比如结点6，因为2×6=12超过了结点总数10，所以结点6无左孩子，它是叶子结点。同样，而结点5，因为2×5=10正好是结点总数10，所以它的左孩子是结点10。
第三条，比如结点5，因为2×5+1=11，大于结点总数10，所以它无右孩子。而结点3，因为2×3+1=7小于10，所以它的右孩子是结点7。

二叉树存储结构

二叉树的顺序存储结构

前面提到，对于树这种一对多的关系，顺序存储结构较难实现。但二叉树是一种特殊的树，因为他的特殊性，所以顺序存储结构也能实现。
二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系，比如双亲与孩子的关系，左右兄弟的关系等。

完全二叉树用顺序存储的方法存储很简单，将树依按层级下排即可。

一棵完全二叉树：

将该二叉树存入数组，结果如下：

普通二叉树也可以按照其完全二叉树进行编号，只不过把不存在的节点设为”^””而已。

一棵普通二叉树：

将该二叉树存入数组，结果如下：

考虑一下极端情况，如果一棵二叉树为斜二叉树，它只有k个结点，却需要分配2^k-1个存储单元空间，这显然是对存储空间的浪费

一棵右斜二叉树:

* 将该二叉树存入数组，结果如下：

所以顺序二叉树结构一般只用于完全二叉树

链式存储结构

继续来考虑二叉树的链式存储结构。二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表。

typedef struct BiTNode{
  TElemType data;
  struct BiTNode *lchild, *rchild;
}BitNode, *BiTree;

如果有需要，还可以再增加一个指向其双亲的指针域，那样就称之为三叉链表。

遍历二叉树

遍历原理

遍历次序

如果手头有20张100元的和2000张1元的奖券同时洒向了空中，所有人比赛谁捡的最多，相信所有人都会先捡100元的，因为这样效率更高，所以可以得到这样的结论:同样是捡奖券，在有限时间内，要达到最高效率，次序非常重要。对于二叉树的遍历来讲，次序同样显得很重要。

二叉树的遍历（traversing binary tree）是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

二叉树的遍历次序不同于线性结构，最多也就是从头至尾、循环、双向等简单的遍历方式。树的结点之间不存在唯一的前驱和后继关系，在访问一个结点后，下一个被访问的结点面临着不同的选择。就像你人生的道路上，面临的不同的选择，由于选择方式的不同，遍历的次序就完全不同了。

遍历方法

二叉树的遍历方式可以很多，如果限制了从左到右的习惯方式，那么主要就分为四种：
* 前序遍历：根->左->右
- 规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。如图所示，遍历的顺序为：ABDGH-CEIF。

* 中序遍历：左->根->右

规则是若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。如图所示，遍历的顺序为：GDHBAE-ICF。

* 后序遍历：左->右->根

规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。如图所示，遍历的顺序为：GHDBIEFCA。

* 层序遍历：按层序遍历

规则是若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。如图所示，遍历的顺序为：ABCDEFGHI。

为什么要有这么多遍历方法呢？
- 使用图形的方法能够清晰的表现出树的结构，但对计算机来说，他只会处理线性序列，而这四种方法的目的便是将树变成某种意义的线性序列，我们可以在不同的遍历过程中对结点进行各种处理。

推导遍历结果

有一种题目为了考查对二叉树遍历的掌握程度，是这样出题的。已知一棵二叉树的前序遍历序列为ABCDEF，中序遍历序列为CBAEDF，请问这棵二叉树的后序遍历结果是多少？

三种遍历都是从根节点开始的，只是打印的顺序不同
- 如果给出了前序遍历结果，根据第一个字母能快速确定根节点
- 如果给出了后序遍历结果，根据最后一个字母能快速确定根节点
- 确定了根节点，便能根据根节点确定左右子树的边界

示例答案

根据前序遍历的结果，可以看出A是根节点，而根据中序遍历，可以知道C和B是A的左子树的结点，E、D、F是A的右子树的结点。

然后再看左右分支，前序遍历中的C和B是，先打印B后打印C，所以能够得出以B是A的左孩子，而C就只能是B的孩子，但不能确定是左孩子还是右孩子，在中序遍历中C在B的前面打印，这就说明C是B的左孩子，否则就是右孩子。

再来看右分支，根据谦虚遍历可以知道D是A的右孩子，而E是D的孩子，F可能是D的孩子也可能是E的孩子，根据中序遍历,由于E在D左侧，而F在右侧，则可以知道E是D的左孩子，而F是E的右孩子。
最终得到的二叉树：

二叉树遍历的性质：

已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
- 已知前序遍历和后序遍历是无法确定一棵二叉树的，因为前序遍历和后序遍历都无法确定左右子树的位置。
- 比如前序序列是ABC，后序序列是CBA。我们可以确定A一定是根结点，但接下来，我们无法知道，哪个结点是左子树，哪个是右子树。

树、森林与二叉树的转换

对于树来说，在满足树的条件下可以是任意形状，一个结点可以有任意多个孩子，显然对树的处理要复杂得多，去研究关于树的性质和算法，真的不容易。
前面所学习的二叉树尽管它也是树，但由于每个结点最多只能有左孩子和右孩子，面对的变化就少很多了。因此很多性质和算法都被研究了出来。
我们可以实现树和二叉树之间的转化来简化问题吗？
- 在学习树的存储结构时，用到的孩子兄弟法，可以实现将一棵树用二叉链表来存储，所以借助二叉链表，树和二叉树也可以相互进行转换。
- 从物理结构来看，它们的二叉链表也是相同的，只是解释不太一样而已。
- 因此，只要设定一定的规则，用二叉树来表示树，甚至表示森林都是可以的，森林与二叉树也可以互相进行转换。

树转化为二叉树

转化步骤：

加线。在所有兄弟结点之间加一条连线。
去线。对树中每个结点，只保留它与最左侧第一个孩子结点的连线，删除它与其他孩子结点之间的连线。
层次调整。以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。

层次调整时，第一个孩子(长子)是二叉树结点的左孩子，兄弟转换过来的孩子是结点的右孩子。
注意：当且仅当原树的根节点没有子节点时，二叉树根结点的度为0，其余情况转化后二叉树根节点的度均为1

森林转化为二叉树

森林是由若干棵树组成的，所以可以理解为:森林中的每一棵树都是兄弟，可以按照兄弟的处理办法来操作。

转化步骤：

把每个树转换为二叉树。
第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来。
当所有的二叉树连接起来后就得到了由森林转换来的二叉树。

二叉树转化为树

二叉树转换为树是树转换为二叉树的逆过程，也就是反过来做而已。

转化步骤：

加线。若某结点的左孩子结点存在，则将这个左孩子的右孩子结点、右孩子的右孩子结点、右孩子的右孩子的右孩子结点……哈，反正就是左孩子的n个右孩子结点都作为此结点的孩子。将该结点与这些右孩子结点用线连接起来。
去线。删除原二叉树中所有结点与其右孩子结点的连线。
层次调整。使之结构层次分明。

二叉树转化为森林

判断一棵二叉树能够转换成一棵树还是森林的标准很简单，那就是只要看这棵二叉树的根结点有没有右孩子，有就是森林，没有就是一棵树。

转化步骤：

从根结点开始，若右孩子存在，则把与右孩子结点的连线删除，再查看分离后的二叉树，若右孩子存在，则连线删除……，直到所有右孩子连线都删除为止，得到分离的二叉树。
再将每棵分离后的二叉树转换为树即可。

树和森林的遍历

树的遍历分为两种方式:

先根遍历。即先访问树的根结点，然后依次先根遍历根的每棵子树。
后根遍历。即先依次后根遍历每棵子树，然后再访问根结点。
下图的树的先根遍历序列为ABEFCDG，后根遍历序列为EFBCGDA。

森林的遍历也分为两种方式:

前序遍历：先访问森林中第一棵树的根结点，然后再依次先根遍历根的每棵子树，再依次用同样方式遍历除去第一棵树的剩余树构成的森林。
后序遍历：是先访问森林中第一棵树，后根遍历的方式遍历每棵子树，然后再访问根结点，再依次同样方式遍历除去第一棵树的剩余树构成的森林。
下图的森林的前序遍历序列的结果就是ABCDEFGHJI,后序遍历序列的结果就是BCDAFEJHIG。

对森林转化为的二叉树进行遍历分析即可发现，森林的前序遍历和二叉树的前序遍历结果相同，森林的后序遍历和二叉树的中序遍历结果相同。
这也就告诉我们，当以二叉链表作树的存储结构时，树的先根遍历和后根遍历完全可以借用二叉树的前序遍历和中序遍历的算法来实现。

哈夫曼树

哈夫曼树有什么用？

数据压缩引入

“喂，兄弟，最近无聊透顶了，有没有什么书可看？”“我这有《三
国演义》的电子书，你要不要？”“‘既生瑜，何生亮。’《三国演
义》好呀，你邮件发给我！”“OK！文件1M多大小，好像大了点。我
打个包，稍等……哈哈，少了一半，压缩效果不错呀。”“太棒了，
快点传给我吧。”

</div>
这是生活中常见的对白，在这个讲究效率的社会，什么都要求速度，在不能出错的情况下，速度越快越好。使用电脑的人几乎都会应用压缩和解压缩软件来处理文档。除了能减少文档在磁盘的空间外，更能让我们在网络上以压缩的形式传输大量数据，使保存和传递更加高效。

现在的压缩技术在编码上已经非常强大，这一切均来自曾经的技术积累。现在来学习最基本的压缩编码方法——哈夫曼编码
在介绍哈夫曼编码前，我们必须得介绍哈夫曼树，而介绍哈夫曼树，我们不得不提这样一个人，美国数学家哈夫曼（David Huffman）。他在1952年发明了赫夫曼编码，为了纪念他的成就，于是就把他在编码中用到的特殊的二叉树称之为哈夫曼树，他的编码方法称为哈夫曼编码。

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树（Huffman Tree）

乍一看好像没看懂，啥叫带权路径长度达到最小？就是树中所有的叶结点的权值乘上其到根结点根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）

这里分别将叶子结点ABCD都赋予一个权值，计算后左右两边的计算结果为：
- 左图：WPL=5×2+7×2+2×2+13×2=54
- 右图：WPL=5×3+2×3+7×2+13×1=48
通过计算结果可知，右图的带权路径长度最小，实际上右图是一棵哈夫曼树。

如何创建一棵哈夫曼树？

现在我们有这些带权的叶子结点，如何将这些叶子结点连接起来，生成一棵哈夫曼树呢？
- 首先将这些带权结点看成树，他们共同构成了一片森林
- 然后在这四个结点中，选择两个权值最小的树结合成一棵新的数，左右顺序不重要(因为哈夫曼编码不唯一)，得到的树的根节点是这两个结点的和

接着将这棵树放回到森林中，重复上面的步骤继续选择两个最小的组成新的树，直到森林中只有一棵树为止

这样就得到了一棵哈夫曼树，构造这棵树又有什么用呢？
- 实际上哈夫曼树比较重要的应用就是对数据进行压缩，他是现代压缩算法的基础。
对以下的字符串进行压缩：ABCABCD
- 这里可以直接采用刚才创建的哈夫曼树，对其进行标注
向左走是0，向右走是1，每个字符的哈夫曼编码即为根节点到这个字符整条路径上的值的拼接
- A:110
- B:0
- C:111
- D:10
经压缩后得到的编码为：ABCABCD = 110 0 111 110 0 111 10

图

图的定义

引入

旅游几乎是每个年轻人的爱好,但没有钱或没时间也是困惑年轻人不能圆梦的直接原因。假设你有了一笔不算很丰裕的闲钱,也有了约半年的时间。此时打算全国性的旅游,你将会如何安排这次行程呢?
假设旅游就是逐个省市进行,省市内的风景区不去细分,例如北京玩 7 天,天津玩 3 天,四川玩 20 天,你现在需要做的就是制订一个规划方案,如何才能用最少的成本将图中所有省市都玩遍,这里所谓最少的成本是指交通成本与时间成本。
如果你不善于规划,很有可能就会出现如玩好新疆后到海南,然后再冲向黑龙江这样的荒唐决策。但是即使是紧挨着省市游玩的方案也会存在很复杂的选择问题,比如游完湖北,周边有安徽、江西、湖南、重庆、陕西、河南等省市,你下一步怎么走最划算呢?
一时解答不了这些问题是很正常的,计算的工作本来就非人脑而应该是电脑去做的事情。在图的应用中,就有应的算法来解决这样的问题。学完这一章,即便不能马上获得最终的答案,也大概知道应该如何去做了。

在线性表中,数据元素之间仅有线性关系,每个数据元素只有一个直接前驱和一个直接后继。
在树形结构中,数据元素之间有着明显的层次关系,并且每一层上的数据元素可能和下一层中多个元素相关,但只能和上一层中一个元素相关。这和一对父母可以有多个孩子,但每个孩子却只能有一对父母是一个道理。
现实中,人与人之间关系就非常复杂,比如我认识的朋友,可能他们之间也互相认识,这就不是简单的一对一、一对多,而是更加复杂的多对多的情况。那就是我们今天要研究的主题——图。图是一种较线性表和树更加复杂的数据结构。在图形构中,结点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关。

图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G ( V,E ), 其中,G 表示一个图,V 是图 G 中顶点的集合,E是图G 中边的集合。

对于图的定义，需要明确的地方：

线性表中我们把数据元素叫元素,树中将数据元素叫结点,在图中数据元素,我们则称之为顶点(Vertex)。
线性表中可以没有数据元素,称为空表。树中可以没有结点,叫做空树。但是在图结构中，不允许没有顶点点。在定义中,若是顶点的集合,则强调了顶点集合 V 有穷非空。
线性表中,相邻的数据元素之间具有线性关系,树结构中,相邻两层的结点具有层次关系,而图中,任意两个顶点之间都可能有关系,顶点之间的逻辑关系用边来表示,边集可以是空的。

各种图的定义

无向边:若顶点到之间的边没有方向,则称这条边为无向边(Edge),用无序偶对(vi,vj)来表示。如果图中任意两个顶点之间的边都是无向边,则称该图为无向图(Undirected graphs)。
有向边:若从顶点到v的边有方向,则称这条边为有向边,也称为弧(Arc)。,有序偶来表示,vi称为弧尾(Tail),vj称为弧头(Head)。如果图中任意两个顶点之间的边都是有向边,则称该图为有向图(Directed graphs)。

对于图中的有向图 G₂来说,G₂= (V₂,{E₂}),其中顶点集合 V₂={A,B,C,D};弧集合 E₂= {,,,}

无向边用小括号“()”表示,而有向边则是用尖括号“<>”表示。

在图中,若不存在顶点到其自身的边,且同一条边不重复出现,则称这样的图为简单图。在数据结构中学习的基本都是简单图，在这里讨论的也都是简单图，显然下方图片的两张图就不属于讨论的范围

在无向图中，如果任意两个顶点之间都存在边,则称该图为无向完全图。含有n个顶点的无向完全图有nx(n-1)/2条边。比如

在有向图中,如果任意两个顶点之间都存在方向互为相反的两条弧,则称该图为有向完全图。

有很少条边或弧的图称为稀疏图,反之称为稠密图。这里稀疏和稠密是模糊的概念,都是相对而言的。
有些图的边或弧具有与它相关的数字,这种与图的边或弧相关的数叫做权(Weigh))。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网(Network)。

如果有两个图，其中图A’中所有点和线都能在A中找到，则称图A’是图A的子图。

图的顶点与边的关系

对于无向图 G=(V,{E}),如果边(v,v’)∈E,则称顶点 v 和v’互为邻接点(Adjacent),即v和v’相邻接。边(v,v’)依附(incident)于顶点 v 和 v’,或者说(v,v’)与顶点v和v’相关联。顶点v的度(Degree)是和v相关联的边的数目,记为TD(v)。例如图7-2-8 左侧上方的无向图,顶点A与B互为邻接点,边(A,B) 依附于顶点 A与B上,顶点 A 的度为3。而此图的边数是5,各个顶点度的和=3+2+3+2=10,推敲后发现,边数就是各顶点度数和的一半,多出的一半是因为重复两次记数。
对于有向图 G= (V,{E}),如果弧 ∈E,则称顶点v邻接到顶点v',顶点v'邻接自顶点v。弧和顶点 v,v’相关联。以顶点 v 为头的弧的数目称为v的入度(InDegree),记为ID (v); 以v 为尾的弧的数目称为v的出度(OutDegree),记为OD(v);顶点v的度为 TD (v) =ID (v) +OD (v)。例如下方的有向图,顶点A的入度是2(从B到A的弧,从C到A的弧),出度是1(从A到D的弧),所以顶点 A 的度为2+1=3。此有向图的弧有4条,而各顶点的出度和=1+2+1+0=4,各顶点的入度和=2+0+1+1=4。

路径的长度是路径上的边或弧的数目。例如上图有向图从B到C再到A的路径长度为2。
树中根结点到任意结点的路径是唯一的,但是图中顶点与顶点之间的路径却是不唯一的。
第一个顶点和最后一个顶点相同的路径称为回路或环(Cycle)。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路,称为简单回路或简单环。
两个图的粗线都构成环,左侧的环因第一个顶点和最后一个顶点都是B,且C、D、A 没有重复出现,因此是一个简单环。而右侧的环,由于顶点C的重复,它就不是简单环了。

连通图相关术语

在无向图 G中,如果从顶点v到顶点有路径,则称和是连通的。如果对于图中任意两个顶点v_i,v_j∈E，v_i和v_j都是连通的,则称 G 是连通图(ConnectedGraph)。
图1中它的顶点A到顶点B、C、D 都是连通的,但显然顶点A与顶点E或F就无路径,因此不能算是连通图。而图2,顶点A、B、C、D相互都是连通的,所以它本身是连通图。

无向图中的极大连通子图称为连通分量。注意连通分量的概念,它强调:
- 要是子图;
- 子图要是连通的;
- 连通子图含有极大顶点数;
- 具有极大顶点数的连通子图包含依附于这些顶点的所有边。
图1是一个无向非连通图。但是它有两个连通分量,即图2和图3.而图4,尽管是图1的子图,但是它却不满足连通子图的极大顶点数(图2满足)。因此它不是图1的无向图的连通分量。
在有向图 G 中,如果对于每一对v_i,v_j∈V、v_i≠v_j,从v_i到v_j和从v_j到v_i到都存在路径,则称 G 是强连通图。有向图中的极大强连通子图称做有向图的强连通分量。
图1并不是强连通图,因为顶点A到顶点D 存在路径,而D到A就在存在。图2就是强连通图,而且显然图2是图1的极大强连通子图,即是它的强连通分量。

连通图的生成树定义：
- 所谓的一个连通图的生成树是一个极小的连通子图,它含有图中全部的n 个顶点,但只有足以构成一棵树的 n-1 条边。
- 比如图1是一个普通图,但显然它不是生成树,当去掉两条构成环的边后,比如图 2 或图 3,就满足n 个顶点n-1条边且连通的定义了。它们都是一棵生成树。从这里也可知道,如果一个图有 n 个顶点和小于n-1条边,则是非连通图,如果它多于n-1 边条,必定构成一个环,因为这条边使得它依附的那两个顶点之间有了第二条路径。比如图 2 和图 3,随便加哪两顶点的边都将构成环。不过有n-1条边并不一定是生成树,比如图 4。

如果一个有向图有一个顶点的入度为0,其余顶点的入度均为1,则是一棵有向树。对有向树的理解比较容易,所谓入度为0其实就相当于树中的根结点,其余顶点入度为1 就是说树的非根结点的双亲只有一个。一个有向图的生成森林由若干棵有向树组成,含有图中全部顶点,但只有足以构成若干棵不相交的有向树的弧。如图1是一棵有向图。去掉一些弧后,它可以分解为两棵有向树,如图2和图3,这两棵就是图1有向图的生成森林。

图的定义与属于总结

图的术语是真的多，看完感觉脑袋晕晕的，现在整理一下：

图按照有无方向分为无向图和有向图。无向图由顶点和边构成,有向图由顶点和弧构成。弧有弧尾和弧头之分。
图按照边或弧的多少分稀疏图和稠密图。如果任意两个顶点之间都存在边叫完全图,有向的叫有向完全图。若无重复的边或顶点到自身的边则叫简单图。
图中顶点之间有邻接点、依附的概念。无向图顶点的边数叫做度,有向图顶点分为入度和出度。
图上的边或弧上带权则称为网。
图中顶点间存在路径,两顶点存在路径则说明是连通的,如果路径最终回到起始点则称为环,当中不重复叫简单路径。若任意两顶点都是连通的,则图就是连通图,有向则称强连通图。图中有子图,若子图极大连通则就是连通分量,有向的则称强连通分量。
无向图中连通且n 个顶点n-1 条边叫生成树。有向图中一顶点入度为0其余顶点入度为1的叫有向树。一个有向图由若干棵有向树构成生成森林。

图的存储结构

图的存储结构相较线性表与树来说就更加复杂了。我们口头上说的“顶点的位置”或“邻接点的位置”只是一个相对的概念。其实从图的逻辑结构定义来看,图上任何一个顶点都可被看成是第一个顶点,任一顶点的邻接点之间也不存在次序关系，因此无法靠数据元素在内存中的物理位置来表示元素之间的关系，即不可能靠简单的顺序存储结构来表示，靠多重链表的方式和树中一样会造成很多存储单元的浪费。
我们的前辈提供了五种存储结构：
- 邻接矩阵
- 邻接表
- 十字链表
- 邻接多重表
- 边集数组

图的遍历

我们经常会面临找东西的问题，不找的东西时常见,需要的东西寻不着。找东西的策略也因人而异。有些人因为找东西没有规划,当一样东西找不到时,往往会反复地找,甚至某些抽屉找个四五遍,另一些地方却一次也没找过。
图的遍历和找东西类似，我们希望从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次,这一过程就叫做图的遍历 (Traversing Graph)。
树的遍历共谈到了四种方案,应该说都还好,毕竟根结点只有一个,遍历都是从它发起,其余所有结点都只有一个双亲。可图的任一顶点都可能和其余的所有顶点相邻接,极有可能存在沿着某条路径搜索后,又回到原顶点,而有些顶点却还没有遍历到的情况。因此我们需要在遍历过程中把访问过的顶点打上标记,以避免访问多次而不自知。具体办法是设置一个访问数组 visited[n], n 是图中顶点的个数,初值为0,访问过后设置为 1。这其实在小说中常常见到,一行人在迷宫中迷了路,为了避免找寻出路时屡次重复,所以会在路口用小刀刻上标记。
对于图的遍历来说,如何避免因回路陷入死循环,就需要科学地设计遍历方案,通常有两种遍历次序方案:它们是深度优先遍历和广度优先遍历。
深度优先遍历
深度优先遍历(Depth_First_Search),也有称为深度优先搜索,简称为 DFS。
可以通俗的理解为不撞南墙不回头，一直搜索某一个方向，直到该方向所以顶点均搜索完毕，再退回来，继续搜索其他方向的顶点，直到所有顶点都搜索完毕。
搜索过程示例
比如现在我们要从A开始寻找下图中的I：
</div>
路线可以是这样的：
</div>
顶点B有三个方向，我们可以先随便选一个方向看看：
</div>
此时来到K，我们发现K已经是一个死胡同，没有其他路了，那么此时我们就需要回到上一个路口，继续去探索其他的路径：
</div>
接着往下一个相邻的顶点G走，发现G有其他的分叉，那么我们就继续向前：
</div>
此时走到F发现又是死路，那么退回到G，走其他的方向：
</div>
又到死胡同了，同样的，回到G继续走其他方向：
</div>
走到C之后，我们有其他的路，我们继续往后走：
</div>
此时走到顶点H，发现H只有一条路，并且H再向前是已经走过的顶点B，那么此时不能再向前了，所以说直接退回到C，走另一边：
</div>
此时来到E，又有两条路，那么继续随便选一条走：
</div>
此时来到顶点J，发现又是死胡同，退回到E，继续走另一边：
</div>
经过了这么多试错，终于是找到了I顶点，这种方式就是深度优先搜索。
广度优先遍历
广度优先遍历(Breadth_First_Search),又称为广度优先搜索,简称BFS。
以找钥匙为例，深度优先搜索是挨个房间查找，将这个房间的所有地方挨个查找后，若未找到则继续查找下一个房间，但我们一般不会把钥匙放到厨房的油烟机或者大衣柜的最顶上吧，而深度优先搜索则是，把这个房间的所有地方都查找一遍才查找下一个房间，这未必是最佳方案，所以我们可以先把家里所有房间简单看一遍，看看钥匙是不是放在显眼的位置，没有找到再找一找最常去的地方，这样一步步扩大查找的范围，直到找到为止，这就是广度优先遍历。
广度优先遍历和二叉树中的层序遍历类似，层序遍历实际上是优先将每一层进行遍历，图的搜索其实也可以采用这种方案，我们可以先探索顶点所有的分支，然后再依次去看这些分支的所有分支：
搜索过程示例
依旧还是从A来到B，此时B有三条分叉路，我们依次访问这三条路的各个顶点：
我们先记录一下这三个顶点，同样需要使用队列来完成：H、G、K
注意访问之后不要再继续向下了，接着我们从这三个里面的第一个顶点H开始，按照同样的方法继续：
此时因为只有一个分支，所以说找到C，继续记录，将C也添加进去：G、K、C注意此时需要回去，继续看之前三个顶点的第二个顶点G：
此时C已经看过了，接着就找到了F和D，也是记录一下：K、C、F、D然后，我们继续看之前三个结点的最后一个:
此时K已经是死胡同了，那么就结束，然后继续看下一个C：
此时继续将E给记录进去：F、D、E，接着看D和F，也没有后续了，那么最后就只有E了：

实际上广度优先遍历就是尽可能地扩展范围，多去探索广阔的土地，而不是死拽着一根不放

两种遍历的区别

对比图的深度优先遍历与广度优先遍历算法,你会发现,它们在时间复杂度上是一样的,不同之处仅仅在于对顶点访问的顺序不同。可见两者在全图遍历上是没有优劣之分的,只是视不同的情况选择不同的算法。
不过如果图顶点和边非常多,不能在短时间内遍历完成,遍历的目的是为了寻找合适的顶点,那么选择哪种遍历就要仔细斟酌了。
- 深度优先更适合目标比较明确,以找到目标为主要目的的情况
- 广度优先更适合在不断扩大遍历范围时找到相对最优解的情况。

最小生成树

引入

假设你是电信的实施工程师,需要为一个镇的九个村庄架设通信网络做设计,村庄位置大致如图,其中vo~ve是村庄,之间连线的数字表示村与村间的可通达的直线距离,比如 vo 至1就是10公里(个别如vo与V6,V6与V8,V5与V7未测算距离是因为有高山或湖泊,不予考虑)。你们领导要求你必须用最小的成本完成这次任务。你说怎么办?
显然这是一个带权值的图,即网结构。所谓的最小成本,就是n个顶点,用n-1条边把一个连通图连接起来,并且使得权值的和最小。在这个例子里,每多一公里就多一份成本,所以只要让线路连线的公里数最少,就是最少成本了。
如果你加班加点,没日没夜设计出的结果是方案一(粗线为要架设线路),我想你离被炒鱿鱼应该是不远了(同学微笑)。因为这个方案比后两个方案多出60%的成本会让老板气晕过去的。

</div>

方案三设计得非常巧妙,但也只以极其微弱的优势对方案二胜出,应该说很是侥幸。我们有没有办法可以精确计算出这种网图的最佳方案呢?答案当然是Yes。

在学习图的定义和术语时,曾经提到过,一个连通图的生成树是一个极小的连通子图,它含有图中全部的顶点,但只有足以构成一棵树n-1 条边，多一条会成环，少一条则无法连通。显然图中的三个方案都是网图的生成树。那么我们把构造连通网的最小代价生成树称为最小生成树(Minimum Cost Spanning Tree)，最小生成树主要针对于无向图。
找连通网的最小生成树,经典的有两种算法：普里姆算法和克鲁斯卡尔算法。
普利姆算法和克鲁斯卡尔算法都是典型的贪心算法，其核心逻辑完全遵循贪心算法 “每一步都选择当前最优解，最终期望得到全局最优解” 的设计思想
普里姆算法
普利姆算法(Prim Algorithm)，也可以通俗的理解为加点法
基本思路：从图中任意选择一个顶点作为起始点，然后每次选择一个与当前生成树连通的顶点中距离最小的顶点，将其加入到生成树中。重复这个过程，直到所有顶点都被加入到生成树中。

如图a，首先从图中任意取出一个顶点，这里取出顶点0，此时跟顶点0连接的三条边长分别为5,1,2，最小的边长为1
如图b，选择最小的边长，将两个顶点连接起来，接着寻找和顶点0以及顶点2连接的各条边，此时各边长分别为5,3,2,6,2,最小的边长为2
如图c，选择边长为2的边,因为有两条边长为2,所以可以任意选一个顶点，检查是否有顶点与该顶点连通，如果没有连通则连接该顶点，如果有连通，则换一个顶点。
如图d，重复上面的步骤，此时可选的边长共有5,3,2,3(没有6是因为2和3是连通的所以不作考虑)接着选择另一个边长为2的边，将其连接
如图e，重复上面的步骤，此时可选的边长共有5,3,3,4,最小的边长为3，此时所有顶点都已经并入生成树，求得最小生成树

普利姆算法是以找点为核心，边是根据距离顺带加入的，所以普利姆算法更适用于稠密图

克鲁斯卡尔算法

克鲁斯卡尔算法(Kruskal Algorithm)，可以通俗的理解为加边法
基本思路：每次找出候选边中权值最小的边，并将该边并入生成树中，重复此过程直到所有边都被检测完为止

如图a，搜索所有边，将所有边按照权值从小到大排序，得到1<2=2<3=3<4<5<6
如图b，选择权值最小的边，将其加入到生成树中，此时生成树只有一个顶点，所以不会成环
如图c，重复上面的步骤，选择权值为2的边，因为有两条边权值为2，随机选一条将其加入到生成树中，此时生成树有两个顶点，所以不会成环
如图d，重复上面的步骤，选择另一条权值为2的边，将其加入到生成树中，此时生成树有三个顶点，所以不会成环
如图e，重复上面的步骤，选择权值为3的边，有两条，但发现其中一条3和4是连通的所以跳过这条边，而另一条是不连通的，将其加入到生成树中
可以继续检测下面的边，但此时所有顶点都已经连通，故无论增加哪条边都会成环，故现在已经求得最小生成树

克鲁斯卡尔算法是以找边为核心，所以克鲁斯卡尔算法更适用于稀疏图

总结

对比两个算法，克鲁斯卡尔算法主要是针对边来展开，边数少时效率会非常高，所以对于稀疏图有很大的优势；而普里姆算法对于稠密
图，即边数非常多的情况会更好一些。
无论是普利姆算法还是克鲁斯卡尔算法，所求得的无向图最小生成树都不一定是唯一的，但他们的边权和一定是唯一的

最短路径

在网图和非网图中，最短路径的含义是不同的。
- 非网图它没有边上的权值，所谓的最短路径，其实就是指两顶点之间经过的边数最少的路径；
- 对于网图来说，最短路径，是指两顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点是源点，最后一个顶点是终点。
显然，研究网图的最短路径更有意义，有两种算法求最短路径的算法，分别是迪杰斯特拉算法和弗洛伊德算法

迪杰斯特拉算法

算法思想：
- 假设有两个顶点集合S和T，集合S中存放图中已找到最短路径的顶点，集合T存放图中剩余顶点。
- 初始状态集合S只包含源点a,然后不断从集合T中选取到顶点a路径最短的顶点a’并加入到集合S中
- 集合S每次并入一个新顶点a’，都要修改顶点a到集合T中顶点的最短路径的长度
- 不断重复该过程，直到集合T中的顶点全部并入到S为止

寻找a到各顶点的最短路径：

初始化先将a到b,c,d,e,f的路径全部设为∞，每当有路径先找寻距离a最近的顶点，a到b的权值为2，a到c的权值为5，故a到b此时为最短路径，将b添加到终点集

绪论

基础概念和术语

数据

数据元素

数据项

数据对象

数据结构

逻辑结构与物理结构

逻辑结构

物理结构

算法

数据结构与算法的关系

特性和要求

算法效率的度量方法

事后统计方法

事前分析估算法

衡量方式

总结回顾

线性表

定义

基础功能

顺序存储结构

存储方式

地址计算方式

顺序存储结构的插入和删除

顺序存储结构的实现

创建一个顺序存储结构的线性表

编写插入操作

判断数据合法性

扩容顺序表

链式存储结构

链表结构

单链表的读取

单链表的插入和删除

单链表整表创建

单链表整表删除

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

静态链表

静态链表的插入操作

静态链表的优缺点

循环链表

双向链表

栈与队列

栈的抽象数据类型

栈的顺序存储结构

进栈和出栈

两栈共享空间

栈的链式存储

进栈与出栈

栈的作用

栈的应用 ———— 递归

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

后缀(逆波兰)表示法定义

后缀表达式计算结果

中缀表达式转后缀表达式

队列的定义

循环队列

队列顺序存储的不足

循环队列定义

链式结构队列

入队和出队

总结回顾

树

树的定义

结点分类

其他概念

树的存储结构

双亲表示法

二叉树的定义

二叉树的特点

特殊二叉树

二叉树的性质

二叉树存储结构

二叉树的顺序存储结构

链式存储结构

遍历二叉树

遍历原理

遍历方法

推导遍历结果

树、森林与二叉树的转换