一、绪论

（一）基本概念和术语

1.数据

数据是人们利用文字符号、数学符号以及其他规定的符号对现实世界的事务及活动所做的描述。

2.数据元素

是组成数据的基本单位。

3.字段

是构成数据的最小单位。

4.数据对象

是性质相同的数据元素的集合，是一个数据的子集。

5.数据结构

是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储表示（即所谓数据的逻辑结构和物理结构），并对这种结构定义相适应的运算，设计相应的算法，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。

6.数据的逻辑结构

是指数据结构中元素之间的逻辑关系，它是从具体问题抽象出来的数学模型，是独立于计算机存储的。

7.数据的逻辑结构的四种基本类型

集合结构、线性结构、树形结构、图形结构。

8.数据的存储结构

是数据的逻辑结构在计算机内存中的存储方式，又称为物理结构。

9.数据的存储结构的四种类型

顺序存储、链式存储、索引存储、散列存储。

10.数据处理

是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算的操作过程。

（二）算法的概念和特性

1.算法

是指在解决问题时，按照某种机械的步骤一定可以得到问题的结果（有解时给出问题的解，无解时给出无解的结论）的处理过程。

2.算法的三个组成元素

操作、控制结构、数据结构。

3.算法的五个重要特性

有穷性、确定性、可行性、输入性、输出性。

（三）算法的设计要求

算法的设计要求：正确性、可读性、稳健性、高效率和低存储量。

（四）算法常用的描述方法

算法常用的四种描述方法：自然语言描述算法、流程图描述算法、伪代码描述算法、计算机语言描述算法。

（五）算法分析和评价

1.算法分析的任务

利用数学工具讨论设计出每个具体算法的复杂度。

2.对算法分析和评价需要考虑的因素

正确性、可维护性、可读性、运算量、占用存储空间等。

3.算法的时间复杂度

算法时间复杂度：是指程序运行从开始到结束所需要的时间。

算法的时间复杂度的估算基于算法中基本操作的重复执行次数，或处于最内层循环的语句的频度。

算法时间的衡量方法：事后分析法、事前分析估算法。

常见的渐进时间复杂度有：O(1)<O(log₂ n)<O(n)<O(nlog₂ n)<O(n² )<O(n³ )<O(2ⁿ )

4.算法的空间复杂度

算法的空间复杂度：是指算法在执行过程中所占辅助空间的大小，用S(n)表示。

算法的空间复杂度作为算法所需存储量的一种度量，主要取决于算法的输入量和辅助变量所占空间。

二、线性表

（一）线性表的概念与基本操作

线性表是由同一类型数据元素组成的有序序列。

线性表的存储结构可以分为顺序存储结构和链式存储结构两种。

（二）顺序表

顺序表是按顺序存储结构存储的线性表，顺序表中的结点在内存中占用一段连续的储存单元。即线性表中逻辑相邻的元素在内存中也相邻。

1.插入操作

判断表是否已满，移动后面一整段数据，表长度加1。

2.删除操作

判断，移动后面一整段元素，表长度减1。

（三）单链表

链表是指按链式存储结构存储的线性表。链表是指线性表中的节点在内存中随机存放，即存储单元既可以连续也可以不连续。

1.插入操作（头插法/尾插法）

申请结点空间作为新结点，先获取待插入结点的后一个结点的地址，给新结点，在把新结点的地址给待插入结点。

2.删除操作

先找到待删除结点的前一个结点的指针域，再找到待删除结点的后一个结点的地址，把这个后结点地址给前结点指针域。

（四）循环链表

单链表的最后一个结点的指针域指向头结点，整个链表形成一个环，就构成了单链表。

（五）双链表

双向链表也称双链表，它的每个数据结点都有两个指针，分别指向前一个结点和后一个结点。

三、栈和队列

（一）栈

1.栈的概念及基本操作

栈又称为堆栈，是限制再表的一端进行插入和删除的线性表。

表中进行插入和删除的一端称为栈顶，常用top表示。

2.顺序栈

用顺序存储方式实现的栈称为顺序栈。top指向数组尾部。

（1）入栈，判断栈满，栈顶指针自增，加入元素。

（2）出栈，判断有元素，取出元素，栈顶指针自减。

3.链栈

用链式存储结构实现的栈称为链栈。top指向链表头部。

（1）新结点指针域指向原链表头部结点，top指向新结点。

（2）保存原头部结点，top指向后一个结点。

4.递归和栈

递归是指在定义自身的同时又出现了对自身的引用。若一个算法直接或间接的调用自己，则称这个算法为递归算法。

（二）队列

1.队列的概念及基本操作

队列简称队，仅允许在表的一端进行插入，在表的另一端进行删除。

插入数据的一端称为队尾，常用rear表示，删除数据的一端称为队首，常用front表示。

注：栈满时进栈为上溢，栈空时出栈为下溢。

2.顺序队列

用顺序存储方式实现的队列称为顺序队列。

（1）入队，判断队满，元素放入队尾，队尾指针自增。

（2）出队，判断队空，队首元素取出，队首指针自增。

队满的判断条件为rear==M，队空的判断条件为front==rear。

注：假设数组空间为M。front=0，rear=M，元素加入，为真溢出（队列已满）。front≠0，rear=M，元素加入，为假溢出（队列未满）。

3.循环队列

在顺序表的基础上，将数组最后一个元素的下一个元素从逻辑上认为是数组的第一个元素，形成逻辑上的环，这样的队列叫做循环队列。

（1）入队，判断队满，元素放入队尾，队尾指针自增。

（2）出队，判断队空，队首元素取出，队首指针自增。

队满的判断条件为（rear+1）%M==front，队空的判断条件为front==rear。

4.链式队列

用链式存储方式实现的队列称为链式队列。

（1）入队，原队尾元素的指针域指向新结点，rear指向后一个结点。

（2）出队，保存原队首元素，front指向后一个结点。

四、串

（一）串的概念和基本操作

串：由零个或多个字符组成的有限序列。

空串：长度为零的串称为空串，它不包含任何字符。

空白串：通常将仅由一个或多个空格组成的串称为空白串。

字串：串中任意个连续字符组成的子序列称为该串的子串。

串的分类：静态字符串（char s[]）和动态字符串（char *s）。

串与线性表操作的区别：线性表的操作通常是以单个数据元素为操作对象，串的操作通常以多个数据元素为操作对象。

（二）串的表示与实现

1.顺序串定长存储及实现

顺序串：用一组连续的存储单元依次存储串中的字符序列，构成串的顺序存储，简称顺序串。

2.串的堆存储及实现

堆存储结构的基本思想：每个串在存放时都会根据串的长度动态分配内存空间。

3.串的链式存储及实现

链串：按链式存储结构存储的串为链串，与链表结构类似，只是链串数据域为字符。

（三）串的模式匹配算法

模式匹配：字串在主串中的定位称为模式匹配或串匹配（字符串匹配）。

一个汉字占两个字节。

1.BF模式匹配算法

主串从首字符开始，与匹配子串从首字符开始逐个字符进行比较。

比较失败后，再从主串第二个字符开始，与匹配子串从首字符开始逐个字符比较，以此类推。

时间复杂度：最好情况为O(n)，最差情况为O(m*n)，一般情况为O(m+n)。

2.KMP模式匹配算法

主串从首字符开始，与匹配子串从首字符开始逐个字符进行比较。

在主串第n个字符比较失败后，从主串第n个字符开始，与匹配字串从首字符开始逐个字符比较，以此类推。

五、数组与广义表

（一）数组

1.数组的概念

数组是n（n>=1）个相同数据类型的数据元素a₀ ,a₁ ,a₂ ,...,a_n-1 构成的占用一块连续地址的内存单元的有限集合。数组通常以字节为内部计数单位。

2.数组的存储

（n维数组可以看成是一个n-i维数组，每个数据元素是i维数组。）

一维数组任一数组元素的存储单元地址：Loc(a_i)=Loc(a₀)+i*s。

以行序为主，二维数组的任一数组元素的存储单元地址：Loc(a_i·j)=Loc(a₀₀)+(i*n+j)*s。

以列序为主，二维数组的任一数组元素的存储单元地址：Loc(a_i·j)=Loc(a₀₀)+(j*m+i)*s。

注：m为行数，n为列数，i为行序号，j为列序号，s为单个元素所占空间。

3.矩阵的压缩

矩阵的压缩存储就是对矩阵的存储采取相同值元素只存储一次，对零值元素不分配存储空间的策略。

压缩矩阵通常是特殊矩阵和稀疏矩阵。

（1）特殊矩阵

特殊矩阵是指矩阵中有许多值相同的元素或由许多零元素，且值相同的元素或零元素的分布具有一定的规律，如三角矩阵、对角矩阵等。

对称矩阵：

所有数据元素都关于主对角线对称的矩阵（a_ij=a_ji），称为对角矩阵。

对称矩阵上三角任一数据元素的存储单元地址：Loc(a_ij)=Loc(a₀₀)+[j(j+1)/2+i]*s。

对称矩阵下三角任一数据元素的存储单元地址：Loc(a_ij)=Loc(a₀₀)+[i(i+1)/2+j]*s。

三角矩阵：

上/下三角（不包括主对角线）中的数据元素均为常数或零元素的矩阵。

三角矩阵上三角数据元素下标i、j与数组位置k的对应关系：（i<=j）时，k=i(2n-i+1)/2+j-i，（i>j）时，k=n(n+1)/2。

（2）稀疏矩阵

稀疏矩阵是矩阵的一种特殊情况，其零元素个数远大于非零元素个数。

稀疏矩阵压缩存储有两种方式：三元组表示法、十字链表表示法。

三元组顺序结构图与转置图：

（二）广义表

1.广义表的定义

广义表是由n个相互具有线性关系的数据元素构成的一个有限序列，是线性表的推广。

当广义表不空时，称第一个数据元素为该广义表的表头，称其余元素组成的表为该广义表的表尾。

广义表的深度是指表中所含括号的层数，原子的深度为0。规定小写字母表示原子，大写字母表示广义表的表名。

2.广义表的特性

线性表、多层次结构、可为其他广义表共享、可为递归表、任一非空广义表可分解为表头和表尾。

3.广义表的存储结构

（1）头尾表示法

需要表结点（标志域、指向表头的指针域、指向表尾的指针域）和原子结点（标志域、值域）两种结构。

（2）孩子兄弟表示法

需要表结点（标志域、指向第一个孩子的指针域、指向兄弟的指针域）和原子结点（标志域、值域、指向兄弟的指针域）两种结构。

六、树和二叉树

（一）树

1.树的概念和基本术语

（1）树的概念

树是零个或多个结点的有限集合。结点为0的树称为空树，结点大于0的树称为非空树。

（2）树的基本术语

结点的度：指结点拥有的子结点的数目。

叶子或终端结点：指度为0的结点。

树的度：指树的各结点的度的最大值。

树的深度或高度：树中结点最大的层数。

有序树：指树中各结点从左至右是有序的。

森林：指n（n>=0）棵互不相交的树的集合。

2.树的逻辑表示方法

有树形图法、嵌套集合法、凹入表示法、广义表表示法。

广义表表示法：((x，(a，b))，((x，(a，b))，y))。

3.树的逻辑存储结构

（1）双亲表示法

使用指针表示每个结点的双亲结点，即双亲表示法。

每个结点包含两个域：数据域和指针域。

（2）孩子表示法

使用指针表示每个结点的孩子结点，即孩子表示法。

每个结点包含一个数据域和多个指针域，指针域的个数为树的度。

（3）双亲孩子表示法

使用指针既表示出每个结点的双亲结点，又表示出每个节点的孩子结点，就是双亲孩子表示法。

指针域既包括指向孩子的指针，也包括指向双亲的指针。

（4）孩子兄弟表示法

使用指针既表示出每个结点的孩子结点，又表示出每个节点的兄弟结点，就是孩子兄弟表示法。

指针域包含两个指针，指向孩子结点的指针和指向最邻近兄弟结点的指针。

（二）二叉树

1.二叉树的概念

二叉树是节点的有限集合，这个集合或空、或由一个根结点和两棵互不相交的分别称为左子树和右子树的二叉树组成。

二叉树的五种形态：空二叉树、只有根结点的二叉树、根结点和左子树、根结点和右子树、根结点和左右子树。

二叉树和树的区别：二叉树结点的孩子最多两个，树无此限制，二叉树的子结点有左右之分，树的子结点无序。

满二叉树：深度为k且有2^k-1个结点的二叉树为满二叉树。

完全二叉树：除二叉树倒数第二层的结点的度小于等于2之外，其余层结点度都为2，且最底层的结点都是靠左集中的。

2.二叉树的性质

（1）二叉树第i层上的结点数目最多为2^i-1（i>=1）。

（2）深度为k的二叉树至多有2^k-1个结点（k>=1）。

（3）任意二叉树中，若叶节点的个数为n₀ ，度为2的结点数为n₂ ，则n₀=n₂+1。

（4）具有n个结点的完全二叉树的深度为log₂n的最大整数加1。

（5）对一个完全二叉树排序，设结点编号为i，则其左孩子结点编号为2i，右孩子结点编号为2i+1。

3.二叉树的存储结构

（1）二叉树的顺序存储结构

对完全二叉树按顺序存储，结点之间的逻辑关系通过数组下标体现。

对于非完全二叉树，通过补设“虚结点”，使二叉树结点编号与完全二叉树保持一致，再按顺序存储。

（2）二叉树的链式存储结构

二叉树最常用的链式存储结构是二叉链，每个结点包含三个域，分别是数据元素域，左孩子链域，右孩子链域。

4.二叉树的遍历

（1）前序遍历：先打印根，再打印左，最后打印右。

（2）中序遍历：先打印左，再打印根，最后打印右。

（3）后序遍历：先打印左，再打印右，最后打印根。

注：（前序和中序）或（中序和后序）可以唯一确定一棵二叉树，（前序和后序）不行。

（三）线索二叉树

1.线索二叉树的概念

在二叉树的链式存储结构中，增加指向前驱和后继结点的信息，称为线索，加上线索的二叉树称为线索二叉树。

对二叉树以某种次序遍历使其成为线索二叉树的过程称为线索化。

2.线索化二叉树

其结点由五个域：左孩子（标志0）或前驱结点（标志1）域、左前标志域、数据域、右后标志域、右孩子（标志0）或后继结点（标志1）域

3.遍历线索化二叉树

（四）哈夫曼树

1.哈夫曼树的概述

路径：若在树中存在一个结点序列，其中前一个结点是后一个结点的双亲结点，则称该序列为路径。

路径长度：为路径上的结点总数减1。

结点的权：为树的结点设置的具有某种意义的数值。

结点的带权路径长度：从根结点到该结点的路径长度与结点权值的乘积。

树的带权路径长度：树中所有叶子结点的带权路径长度之和，记为WPL。

哈夫曼树：又称最优二叉树，是由n个带权的叶子结点构成的所有二叉树中WPL最小的二叉树。

2.哈夫曼树的构造算法

选出所有根结点中权值最小的两个根结点进行合并，作为新树的左右结点，新树的根结点的权值为左右结点权值之和。

3.哈夫曼编码

在哈夫曼树中，规定左分支用0表示，右分支用1表示，根结点到叶子结点分支的0、1表示称为哈夫曼编码。

（五）树、森林和二叉树

1.二叉树与树、森林之间的转换

（1）将树转化为二叉树

先把所有兄弟结点之间加一条线，除第一个子结点外，把所有线全部去除。

（2）将森林转化为二叉树

先把森林中的每棵树转化为二叉树，再把所有二叉树的根结点连在一起。

（3）二叉树到树、到森林的转换

x为双亲的左结点，则把x的右节点、x的右节点的右节点、......全部和x的双亲结点相连，最后去掉原来所有双亲与右孩子的结点。

2.树、森林的遍历

（1）树的遍历

先根遍历：访问根结点，再按从左到右的顺序先根遍历每一个结点。

后根遍历：按从左到右的顺序后根遍历每一个子树，再访问根结点。

（2）森林的遍历

前序遍历：访问森林的第一棵树的根结点，再先根遍历第一棵树的根结点的子树，再前序遍历除第一棵树的子森林。

后序遍历：后根遍历森林的第一棵树的根结点的子树，再访问森林的第一棵树的根结点，再后序遍历除第一棵树的子森林。

七、图

（一）图的概念及基本术语

图：图G是由顶点有限非空集V和表示定点关系的边集合E所限定的一种数据结构，常记为G=（V（G），E（V））。

无向图：代表边的顶点偶对是无序的图。

有向图：代表边的顶点偶对是有序的图。

完全图：每个顶点之间都有边的图为完全图。完全有向图有ｎ（ｎ＋1）条边，完全无向图有ｎ（ｎ＋1）/2条边。

端点和临近点：无向图的边（v_i，v_ｊ），有向图的边＜v_i，v_ｊ＞。v_i，v_ｊ都为边的端点，它们互为临近点，在有向图里v_i为起点，v_ｊ为终点。

顶点的度：顶点所具有的边的数目称为该顶点的度。

入度和出度：在有向图中，以顶点为终点的边的数目称为入度，以顶点为起点的边的数目称为出度。

路径长度：是指一条路径上经过的边的数目。

简单路径：若一条路径上除开始和结束点可以相同外，其余顶点均不相同，则称此路径为简单路径。

回路或环：若一条路径起点和终点为同一顶点，则此路径被称为回路或环。起点和终点相同的简单路径被称为简单回路或简单环。

连通、连通图：若v_i到v_ｊ有路径，则称v_i和v_ｊ是连通的。若图G任意两个顶点连通，则称G为连通图。

连通分量：无向图中的极大连通子图称为连通分量，任何连通图的连通分量只有一个，即本身，而非连通图有多个连通分量。

稠密图、稀疏图：当一个图接近完全图时称为稠密图，反之则称为稀疏图。

极小连通子图：指包含所有顶点并保证连通的前提下包含原图最少的边。

生成树：指包含连通图全部顶点的一个极小连通子图。

权和网：图的每条边可以附有一个数，称为权。边带有权的图称为带权图，也称为网。

（二）图的存储结构

1.邻接矩阵表示法

邻接矩阵是顶点之间相邻的矩阵。

2.临接表表示法

是图的一种链式存储结构，在邻接表中，为图中每个顶点建立一个单链表。

（三）图的遍历

从给定图中任意指定的顶点出发，按照某种搜索方法沿着图的边访问图中所有的顶点，使每个顶点仅被访问一次。

1.深度优先遍历

先访问指定的顶点，再从指定的顶点出发，选择与该顶点相邻的未被访问的顶点访问（逐层深入），若临近顶点都被访问过，则回退上一步，重复该步骤。

2.广度优先遍历

先访问指定的顶点，再从指定的顶点出发，访问与该顶点临近的所有顶点，再依次访问被访问顶点的临近顶点（未被访问的），重复该步骤。

（四）图的应用

1.最小生成树

（1）生成树

无回路的图称为树或自由树或无根树。

若连通图G有ｎ个顶点，取ｎ个顶点和连接ｎ个顶点的ｎ－1条边，且无回路的子图称为G的生成树。

（2）最小生成树

树中边权之和定义为树的权，在所有生成树中树权最小的生成树，即为最小生成树。

2.最短路径

3.AOV网与拓扑排序

4.AOE网与关键路径

八、查找

（一）查找的概念及基本术语

若查找的同时对表中的记录做修改，相应表称为动态查找表，否则称为静态查找表。

查找的主要方法为：顺序查找、二分查找（折半查找）、二叉排序树法、哈希查找法等

最大查找长度：关键字的最多比较次数。

平均查找长度：关键字的平均比较次数。

（二）线性表查找

1.顺序查找

从表的一端开始，将关键字逐个与给定值比较。

优点：查找简单，无论数据是否有序。

缺点：平均查询过长，数据越大，效率越低。

2.二分查找

关键码必须有序，必须是顺序表，不适合链表。

主要比较码为表头（头序号：初始为0）、表尾（尾序号：初始为表长度减1）、中间项（中序号为：表头表尾序号和除2）。

通过查找值和中间项比较，让表头等于中间项的后一项或是表尾等于中间项的前一项，不断使查找区间减半。

二分查找的判定树或比较树：

3.分块查找

4.顺序查找三种查找方法的比较

（1）平均查找长度：二分查找最小，分块查找次之，顺序查找最大

（2）表结构：顺序查找有序表、无序表均可，二分查找仅适用有序表，分块查找要求至少分块有序。

（3）表的存储结构：顺序查找和分块查找无论顺序表、链表均适用，二分查找仅适用顺序表。

（三）树表的查找

二叉排序树：左子树上的记录的值均小于根记录的值，右子树上的记录的值均打于根记录的值，其左右子树均为二叉排序树。

二叉排序树的创建：（要先读入第一个结点为根结点）将下一待插入的结点与根结点比较，等于就排除，小于就放入左子树，大于就放入右子树，重复该步骤。

（四）哈希表的查找

1.哈希表的概念

在记录的存储位置和它的关键字之间建立一个确定的对应函数ｆ，使每个关键字和表中唯一的存储位置相对应，称这个对应关系ｆ为哈希（散列）函数，根据这个思想建立的表为哈希表。

2.构造哈希函数的方法

（1）直接地址法：用关键字或关键字的线性函数值为哈希地址。

（2）数字分析法

（3）平方取中法：取关键字平方过后的中间几位为哈希地址。

（4）除留余数法：取关键字被不大于哈希表长的数相除后的余数为哈希地址。

3.处理地址冲突的方法

（1）线性探测法：以冲突的哈希地址为自变量，向后加1，若仍冲突则继续加1。

（2）二次探测法：以冲突的哈希地址为自变量，按１^２，－１^２，２^２，－２^２．．．改变哈希地址。

（3）拉链法：把所有的同义词用单链表链接起来。

九、排序

（一）排序的概念及基本术语

稳定性：数据元素序列按关键字排序，若相同关键字元素排序前后保持一致则称该排序稳定，否则不稳定。

安排序策略分为五类：插入排序、选择排序、交换排序、归并排序、基数排序。

（二）插入排序

1.直接插入排序

将数据序列分为有序区和无序区，有序区初始元素个数为1，不断的将无序区的第一个元素放入有序区中，放入的元素从有序区的末尾元素开始，依次比较，到小于等于放入的元素时停止。

2.二分插入排序

将数据序列分为有序区和无序区，有序区初始元素个数为1，不断的将无序区的第一个元素放入有序区中，放入的元素通过二分查找，找到合适的位置插入。

3.希尔排序

选择一个不断减少的步长序列，按照步长对序列进行多趟排序，每趟排序根据对应的步长将待排序序列分隔成若干长度的子序列，分别进行直接插入排序。

（三）交换排序

1.冒泡排序

将数据序列分为有序区和无序区，有序区初始元素个数为0，从无序区第一个元素开始，两两交换，将较大的元素交换到后面，每一趟结束都将无序区的最大值交换到有序区的头部。

2.快速排序

在无序区中选第一个元素作为分区元素，首尾两个关键字向内不断靠近，将大于该元素的放入该元素的右区间，小于该元素的放入该元素的左区间，递归调用本函数，以不发生交换为结束本层函数的条件。

（四）选择排序

1.直接选择排序

将数据序列分为有序区和无序区，有序区初始元素个数为0，每一趟从无序区中找到最小的元素，放入有序区的尾部。

2.堆排序

小顶堆：根小于等于左右孩子结点。

大顶堆：根大于等于左右孩子结点。

（五）归并排序

归并排序是采用的分治法，将已有序的子序列合并，得到完全有序的序列，即先使每个子序列有序，再使子序列段间有序。

（六）基数排序

基数排序属于分配式排序，又称桶子法，基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。

（七）各种内排序方法的比较和选择