---清风予你
清风拂过之处，万物复苏之初。
真理在被证实以前都只是暗室里的装饰，只有眼前亮起来以后，才有机会彰显它的价值。
攀登高山固然危险，但为一睹山顶的美景，值得冒险一试。
希望你在无人问津的日子里，暗自努力，记得按时吃饭！
......
目录
第一章 数据结构与算法
1.1 算法
算法的基本概念
▶定义
计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法；简单来说，算法就是解决问题的基本步骤。
▶算法的基本特征
（1）可行性
算法在特定的执行环境中执行应当能够得出满意的结果，即必须有一个或多个输出。
（2）确定性
算法的确定性表现在对算法中每一步的描述都是明确的，没有多义性。
（3）有穷性
算法中的操作步骤为有限个，且每个步骤都能在有限的时间内完成（算法的运行时间有限）
（4）拥有足够的情报
一般来说，算法在拥有足够的输入信息和初始化信息时，才是有效的；当提供的情报不够时，算法可能无效；
特殊情况，算法可以没有输入，故一个算法有0个或多个输入。
总之，算法是一个动态的概念，是指一组严谨地定义运算顺序或操作步骤的规则，并且每一个步骤都是有效的、明确的，此顺序将在有限的次数内终止。
▶算法的基本要素
（1）对数据对象的运算和操作
在一般的计算机系统中，基本的运算和操作有以下4类：算术运算、逻辑运算、关系运算和数据传输。
（2）算法的控制结构，即算法中各个操作之间的执行顺序。
描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。
一个算法一般都可以用顺序、选择（又称分支）、循环（又称重复）3种基本控制结构组合而成。
▶算法的基本设计方法
常用的算法基本设计方法有 列举法、归纳法、递推法、递归法、减半递推技术和回溯法6种。
算法复杂度
算法复杂度包括算法的 时间复杂度 和算法的 空间复杂度（即存储器）。
▶算法的时间复杂度
算法的时间复杂度是指（执行算法所需要的计算工作量）
算法的计算工作量是用算法所执行的基本运算次数来度量的，而算法的基本运算次数是 问题规模（通常用整数n表示）的函数，即算法的工作量=f(n)。
▶算法的空间复杂度
算法的空间复杂度是指执行这个算法所需要的（内存空间）。
一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。
如果额外空间量相对于问题规模（即输入数据所占的存储空间）来说是常数，即 额外空间量不随问题规模的变化而变化，则称该算法是原地（in place）工作的。
为了降低算法的空间复杂度，主要应 减少输入数据所占的存储空间以及额外空间，通常采用存储压缩技术。
注：算法的时间复杂度与空间复杂度没有直接关系。
★例题★
(1）下列叙述正确的是（ ）
A、算法就是程序
B、设计算法时只需要考虑数据结构的设计
C、设计算法时只需要考虑结果的可靠性
D、以上3种说法都不对
（2）下列叙述错误的是（ ）
A、算法的时间复杂度与算法所处理数据的存储结构有直接关系
B、算法的空间复杂度与算法所处理数据的存储结构有直接关系
C、算法的时间复杂度与空间复杂度有直接关系
D、算法的时间复杂度与算法程序执行的具体时间是不一致的
★Answer★
（1）D 解析：算法不等于程序，也不等于计算方法；设计算法时不仅要考虑对数据对象的运算和操作，还要考虑算法的控制结构。
（2）C 解析：算法的时间复杂度是指执行算法所需要的计算工作量，数据的存储结构直接决定数据的输入，而这会影响算法所执行的基本运算次数；算法的空间复杂度是指执行算法所需要的内存空间，其中包括输入数据所占的存储空间；算法的时间复杂度和空间复杂度没有直接关系；算法程序执行的具体时间受到所使用的计算机、程序设计语言以及算法实现过程中的许多细节的影响，而算法的时间复杂度与这些因素无关，所以是不一致的。
1.2 数据结构的基本概念
数据结构
▶定义
数据结构研究内容包括以下3个方面：
（1）数据集合中个数据元素之间所固有的逻辑关系，即数据的逻辑结构；
（2）在对数据元素进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；
（3）对各种数据结构进行的运算。
数据：是需要处理的数据元素的集合，一般来说，这些数据元素，具有某个共同的特征。
数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
数据对象：是性质相同的数据元素的集合，是数据的一个子集。
结构：就是关系，是集合中各个数据元素之间存在的某种关系（或联系）
数据的逻辑结构：指反映数据元素之间的逻辑关系（即前后件关系）的数据结构。
数据的存储结构：又称为数据的物理结构，是数据的逻辑结构在计算机存储空间的存放方式。
数据结构的图形表示
数据元素之间最基本的关系是 前后件关系。
前后件关系：即每一个二元组，都可以用图形来表示。用中间标有元素值的方框表示 数据元素，一般称之为数据节点，简称为节点。
★节点的基本概念
基本概念 |
含义 |
根节点 |
数据结构中，没有前件的节点 |
终端节点（或叶子节点） |
数据结构中，没有后件的节点 |
内部节点 |
数据结构中，除了根节点和终端节点以外的节点，统称内部节点 |
★线性结构与非线性结构
基本概念 |
含义 |
| 线性结构 |
一个非空的数据结构，其满足以下两个条件： （1）有且只有一个根节点； （2）每一个节点最多有一个前件，也最多有一个后件 |
非线性结构 |
不满足以上两个条件的数据结构就称为 非线性结构； 非线性结构主要指 树形结构 和 网状结构 |
注意：
（1）在线性结构插入或删除任何一个节点后还应是 线性结构；
（2）线性结构和非线性结构在删除结构所有节点后，都会产生 空 的数据结构
疑难解答：空的数据结构是线性结构还是非线性结构？？
答：一个空的数据结构究竟是属于线性结构还是属于非线性结构，这要根据具体情况来确定。如果对该数据结构的算法是按线性结构的规则来处理的，则属于线性结构；否则属于非线性结构。
★例题★
（1）下列叙述正确的是（ ）
A、有一个以上根节点的数据结构不一定是非线性结构
B、只有一个根节点的数据结构不一定是线性结构
C、循环链表是非线性结构
D、双向链表是非线性结构
（2）设数据集合为D={1,3,5,7,9}，D上的关系为R，下列关系使数据结构B=（D，R）为非线性结构的是（ ）
A、R={（5,1），（7,9），（1,7），（9,3）}
B、R={（9,7），（1,3），（7,1），（3,5）}
C、R={（1,9），（9,7），（7,5），（5,3）}
D、R={（1,3,），（3,5），（5,9），（7,3）}
★Answer★
（1）B 解析：线性结构应满足有且只有一个根节点，每个节点最多有一个前件，也最多有一个后件；有一个根节点以上的数据结构一定是非线性结构；循环链表和双向链表都是线性结构。
（2）D 解析：线性结构应满足有且只有一个根节点，每个节点最多有一个前件，也最多有一个后件；故A选项中，根节点为5，线性表为51793,；B选项中，根节点为9，线性表为97135；C选项中，根节点为1，线性表为19753,；D选项中，根节点为1,7，属于非线性结构。
1.3 线性表及其顺序存储结构
线性表
▶定义：
线性表是n（n>=0）个数据元素构成的有限序列，表中除第一个元素外的每一个元素，有且只有一个前件，除最后一个元素外，有且只有一个后件。
▶非空线性表的特征
- 只有一个根节点，即节点a1，它无前件。
- 有且只有一个终端节点，即节点an，它无后件。
- 除根节点与终端节点外，其他所有节点有且只有一个前件，也有且只有一个后件。
节点个数n称为线性表的长度，当n=0时，称为空表。
▶线性表的顺序存储结构
线性表可以采用（顺序存储）和（链式存储）两种存储结构。
▶定义：
将线性表一个接一个地存储在一片相邻的存储区域中，这就是采用了顺序存储结构，这种顺序表示的线性表也称为 顺序表。
顺序表的两个基本特征：
-
- 线性表中所有元素所占的存储空间是连续的；
- 线性表中各数据元素在存储空间中是按照逻辑顺序一次存放的。
注意：
（1）在顺序表中，每个元素占有相同的存储空间，元素的存储顺序与逻辑顺序一致。
（2）经过线性表的多次插入运算，可能出现存储空间已满，这时仍继续插入的错误运算，这类错误称之为“上溢”。
★例题★
（1）下列关于线性表的插入运算描述正确的是（ ）
A、线性表存储空间已满的情况下，继续插入的错误运算称为“上溢”
B、在线性表的末尾插入新元素，需要移动线性表中的所有元素
C、在线性表的第一个位置处插入新元素不需要移动线性表中的所有元素
D、线性表的插入运算的时间主要花费在元素的插入上
（2）下列关于线性表的删除运算描述错误的是（ ）
A、若删除线性表的末尾元素，不需要移动线性表中的元素
B、若删除线性表的第一个元素，则需要移动线性表上的所有元素
C、线性表每删除一个元素，线性表的长度减少1
D、线性表的顺序存储结构适合常变动的长度较大的线性表
★Answer★
（1）A 解析：在线性表的末尾插入新元素，不需要移动线性表中的所有元素；线性表的插入运算其时间主要花费在节点的移动上，所需移动节点的次数不仅与表的长度有关，而且与插入的位置有关。
（2）D 解析：设线性表中有x个元素，删除表中第n个元素，则需要第n个元素之后的（x-n）个元素向前移一个位置，且表的长度减少1，当删除线性表的末尾元素时，则n=x，故不需要移动线性表中的元素；当n=1时，则除第一个元素以外的元素都需要移动；线性表的顺序存储结构适用于小线性表，或者建立之后不常变动的线性表。
1.4 栈和队列
栈和队列都是一种特殊的线性表，它们都有各自的特点；
栈是（先进后出）的线性表，队列是（先进先出）的线性表
栈及其基本定义
▶定义：
栈是一种特殊的线性表，它所有的插入与删除都是限定在同一端进行。在栈中，一端是封闭的，即不允许插入元素，也不允许删除元素；另一端是开口的，允许插入和删除元素。
▶特点：
1.（先进后出）或（后进先出）
例如（枪械的子弹匣）子弹匣的一端是完全封闭的，最先被压入的子弹是最后被弹出，最后压入的子弹是最先被弹出。
注：
（1）在栈中，允许插入与删除的一端称为（栈顶），不允许插入与删除的一端称为（栈底）。当栈中没有元素时，称为 空栈。例如（没有子弹的子弹匣称为空栈）
（2）通常用指针top来指示栈顶的位置，用指针bottom来指示栈底。
2.栈具有记忆作用
3.在顺序存储结构下，栈的插入与删除运算都不需要移动表中其他数据元素
4.栈顶指针top动态反映了栈中元素的变化情况
▶栈的基本运算
栈的基本运算有三种：入栈运算、退栈运算、读栈顶元素
入栈运算即栈的插入，在栈顶位置插入一个新元素；退栈运算即栈的删除，就是取出栈顶元素赋予的指定变量；读栈顶元素就是将栈顶元素（即栈顶指针top指向的元素）的值赋予给一个指定的变量。
队列及其基本运算
▶定义：
队列是指允许在一端进行插入，而在另外一端进行删除的线性表。在队列中，允许进行删除运算的一端称为队头（或排头），允许进行插入运算的一端称为对尾。
▶特点：
（先进先出）
例如：（火车进出隧道）最先进入隧道（出隧道）的是车头，最后进入（出隧道）的是车尾。
注：
（1）在队列中，队头指针front，队尾指针rear。
（2）往队列的队尾插入一个元素称为 入队 运算，从队列的排头删除一个元素称为 退队 运算。
▶队列的基本运算
队列的基本运算有两种：入队运算，退队运算
入队运算是指在队列的队尾加入一个新元素；退队运算则是指在队列的队头（排头）退出一个元素，并赋给指定的变量。例：（循环队列）
★例题★
（1）一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素的出栈顺序是（ ）
A、12345ABCDE
B、EDCBA54321
C、ABCDE12345
D、54321EDCBA
（2）对于循环队列，下列叙述正确的是（ ）
A、队头指针是固定不变的
B、队头指针一定大于队尾指针
C、队头指针一定小于队尾指针
D、队头指针可以大于队尾指针，也可以小于队尾指针
★Answer★
（1）B 解析：栈是一种特殊的线性表，它的插入运算和删除运算都是在同一端进行的，先入栈的元素最后出栈（先进后出），故元素的出栈顺序是EDCBA54321。
（2）D 解析：循环队列是一种顺序的存储元素，循环队列的队头和队尾都不是固定的，随着元素入队与出队操作要进行变化；循环队列的队头指针可能大于队尾指针，也可能小于队尾指针。
1.5 线性链表
线性表主要有两种存储方式：顺序存储，链式存储
▶比较：
线性表的顺序存储结构（顺序表） 具有简单、运算方便等优点，特别是对于小线性表或长度固定的线性表，其特点是用物理存储位置上的邻接关系来表示节点间的逻辑关系。
优点：（1）可以随机存取表中任意节点；
（2）无须为表示节点间的逻辑关系额外增加存储空间
缺点：（1）顺序表的插入和删除运算效率很低；
（2）顺序表的存储空间不便于扩充；
（3）顺序表不便于存储空间的动态分配
线性表的链式存储结构 （线性链表，简称链表），其特点是每个存储节点都包括数据域和指针域，用指针表示节点间的逻辑关系。
优点：（1）在进行插入和删除运算时，只需改变指针即可，不需要移动元素；
（2）链表的存储空间易于扩充并且方便空间的动态分配
缺点：（1）需要额外的空间（指针域）来表示数据元素之间的逻辑关系，存储密度比顺序表低
线性链表的基本概念
▶线性链表
线性链表的基本单位称为（存储节点），每个存储节点包括两部分：（数据域）和（指针域）
数据域：存放数据元素本身的信息
指针域：存放一个指向后件节点的指针，即存放下一个数据元素的存储地址
▶单链表/双向链表
由于线性链表中，每个节点只有一个指针域，故又称为 单链表。
在实际应用中，有时还会用到每个存储节点有两个指针域的链表，一个指针域存放前件的地址，称为左指针（Llink）;另一个指针域存放后件的地址，称为右指针（Rlink）,这样的线性链表称为双向链表。
对比：
在单链表中，只能顺指针方向进行扫描，即（由某一个节点出发，只能找到它的后件，若要找出它的后件，必须从头指针开始重新寻找）
而在双向链表中，由于每个节点设置了两个指针，从某一个节点出发，可以很方便地找到其他任意一个节点。
注意：
在线性链表中，各数据元素节点的存储空间可以是不连续的，且各数据元素的存储顺序与逻辑顺序可以不一致。
★例题★
（1）下列关于线性链表的叙述中，正确的是（ ）
A、各数据节点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致
B、各数据节点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续
C、进入插入与删除时，不需要移动表中的元素
D、以上说法均不正确
（2）线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有（ ）
A、节省存储空间
B、插入与删除运算效率高
C、便于查找
D、排序时减少元素的比较次数
★Answer★
（1）C 解析：在线性链表中，各数据节点的存储空间可以不连续，而且它们的存储顺序与逻辑顺序可以不一致；当对元素进行插入与删除运算时，只需改动有关节点的指针域即可，不需要移动表中元素，运算效率大大提高。
（2）B 解析：在线性链表中，对元素进行插入与删除运算时，只需改动有关节点的指针域即可，不需要移动表中元素，运算效率大大提高。