数据结构（C语言版）（第2版）
第2版前言
- 读者可从人邮教育社区（www.ryjiaoyu.com）上免费下载。
第1章 绪论
- 如何合理地组织数据、高效地处理数据，这就是“数据结构”主要研究的问题。
1.1 数据结构的研究内容
- 首先从具体问题抽象出数学模型，然后设计一个解此数学模型的算法，最后编写程序，进行测试、调试，直到解决问题。
- 数据结构主要研究非数值计算问题，非数值计算问题无法用数学方程建立数学模型
- 这类数学模型称为“线性”的数据结构。
- 在这类问题中，计算机处理的对象是树结构，元素之间是一对多的层次关系，施加于对象上的操作有查找、插入和删除等。这类数学模型称为“树”的数据结构。
- 这类数学模型称为“图”的数据结构。
- 数据结构是一门研究非数值计算程序设计中的操作对象，以及这些对象之间的关系和操作的学科。
- 数据结构是介于数学、计算机硬件和软件三者之间的一门核心课程
1.2 基本概念和术语
- 数据（Data）是客观事物的符号表示，是所有能输入到计算机中并被计算机程序处理的符号的总称
- 数据元素（Data Element）是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。
- 数据项（Data Item）是组成数据元素的、有独立含义的、不可分割的最小单位。
- 数据对象（Data Object）是性质相同的数据元素的集合，是数据的一个子集。
- 只要集合内元素的性质均相同，都可称之为一个数据对象。
- 数据结构（Data Structure）是相互之间存在一种或多种特定关系的数据元素的集合
- 数据的逻辑结构有两个要素：一是数据元素；二是关系。
- 图1.3 四类基本逻辑结构关系图
- 数据元素之间存在一对多的关系
- 集合结构、树结构和图结构都属于非线性结构
- 线性结构包括线性表（典型的线性结构，如例1.1中的学生基本信息表）、栈和队列（具有特殊限制的线性表，数据操作只能在表的一端或两端进行）、字符串（也是特殊的线性表，其特殊性表现在它的数据元素仅由一个字符组成）、数组（是线性表的推广，它的数据元素是一个线性表）、广义表（也是线性表的推广，它的数据元素是一个线性表，但不同构，即或者是单元素，或者是线性表）。
- 数据元素在计算机中有两种基本的存储结构，分别是顺序存储结构和链式存储结构。
- 每个结点占用两个连续的存储单元，一个存放结点的信息，另一个存放后继结点的首地址。
- 数据类型（Data Type）
- 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。
- 比如取模运算是不能用于实型变量的。
- 抽象就是抽取出实际问题的本质。
- 抽象数据类型（Abstract Data Type，ADT）一般指由用户定义的、表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称，具体包括三部分：数据对象、数据对象上关系的集合以及对数据对象的基本操作的集合。
1.3 抽象数据类型的表示与实现
- 抽象数据类型的概念与面向对象方法的思想是一致的
- 抽象数据类型相当于在概念层（或称为抽象层）上描述问题，而类相当于在实现层上描述问题。
- 最终表示和实现抽象数据类型，最好用面向对象的方法
- 数据结构的表示（存储结构）用类型定义（typedef）描述；数据元素类型约定为ElemType，由用户在使用该数据类型时自行定义。
- 使用new和delete动态分配和释放内存空间：
1.4 算法和算法分析
- 算法（Algorithm）是为了解决某类问题而规定的一个有限长的操作序列。
- （3）健壮性。
- 衡量算法效率的方法主要有两类：事后统计法和事前分析估算法。
- 问题规模是算法求解问题输入量的多少，是问题大小的本质表示，一般用整数n表示。
- 一条语句的重复执行次数称作语句频度（Frequency Count）。
- 所谓“基本语句”指的是算法中重复执行次数和算法的执行时间成正比的语句，它对算法运行时间的贡献最大。
- 一般情况下，算法中基本语句重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作T(n)=O(f(n))它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称做算法的渐近时间复杂度，简称时间复杂度（Time Complexity）。
- 找出所有语句中语句频度最大的那条语句作为基本语句，计算基本语句的频度得到问题规模n的某个函数f(n)，取其数量级用符号“O”表示即可
- 如果算法的执行时间不随问题规模n的增加而增长，算法中语句频度就是某个常数。即使这个常数再大，算法的时间复杂度都是O(1)
- 多数情况下，当有若干个循环语句时，算法的时间复杂度是由最深层循环内的基本语句的频度f(n)决定的。
- 常见的时间复杂度按数量级递增排列依次为：常量阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n2)、立方阶O(n3)、……、k次方阶O(nk)、指数阶O(2n)等。
- 一般情况下，随着n的增大，T(n)的增长较慢的算法为较优的算法
- 称算法在最好情况下的时间复杂度为最好时间复杂度，指的是算法计算量可能达到的最小值；称算法在最坏情况下的时间复杂度为最坏时间复杂度，指的是算法计算量可能达到的最大值；算法的平均时间复杂度是指算法在所有可能情况下，按照输入实例以等概率出现时，算法计算量的加权平均值。
- 若算法执行时所需要的辅助空间相对于输入数据量而言是个常数，则称这个算法为原地工作，辅助空间为O(1)
- 算法1仅需要另外借助一个变量t，与问题规模n大小无关，所以其空间复杂度为O(1)。算法2需要另外借助一个大小为n的辅助数组b，所以其空间复杂度为O(n)。
- 不过，通常情况下，鉴于运算空间较为充足，人们都以算法的时间复杂度作为算法优劣的衡量指标。
1.5 小结
- 存储结构是逻辑结构在计算机中的存储表示，有两类存储结构：顺序存储结构和链式存储结构。
第2章 线性表
- 线性结构的基本特点是除第一个元素无直接前驱，最后一个元素无直接后继之外，其他每个数据元素都有一个前驱和后继。
2.1 线性表的定义和特点
- 同一线性表中的元素必定具有相同的特性，即属于同一数据对象，相邻数据元素之间存在着序偶关系。
- 诸如此类由n（n≥0）个数据特性相同的元素构成的有限序列称为线性表。
2.2 案例引入
- 改进方案是利用链式存储结构表示多项式的有序序列，这样灵活性更大些。
- 解决这类问题的最好方法就是从具体应用中抽象出共性的逻辑结构和基本操作（即抽象数据类型），然后采用程序设计语言实现相应的存储结构和基本操作。
2.4 线性表的顺序表示和实现
- 线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，这种表示也称作线性表的顺序存储结构或顺序映像。
- LOC(ai)=LOC(a1)+(i−1) × l
- 线性表的顺序存储结构是一种随机存取的存储结构。
- 通常都用数组来描述数据结构中的顺序存储结构
- 将L定义为SqList类型的变量，便可以利用L.elem[i-1]访问表中位置序号为i的的图书记录。
- 显然，顺序表取值算法的时间复杂度为O(1)。
- 在查找时，为确定元素在顺序表中的位置，需和给定值进行比较的数据元素个数的期望值称为查找算法在查找成功时的平均查找长度（Average Search Length，ASL）。
- 顺序表按值查找算法的平均时间复杂度为O(n)。
- 顺序表插入算法的平均时间复杂度为O(n)。
- 顺序表删除算法的平均时间复杂度为O(n)。
2.5 线性表的链式表示和实现
- 整个链表的存取必须从头指针开始进行，头指针指示链表中第一个结点（即第一个数据元素的存储映像，也称首元结点）的存储位置。
- 指针为数据元素之间的逻辑关系的映像，则逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻，由此，这种存储结构为非顺序映像或链式映像。
- 单链表可由头指针唯一确定
- 通常习惯上用LinkList定义单链表，强调定义的是某个单链表的头指针；用LNode *定义指向单链表中任意结点的指针变量。
- 若定义LinkList p或LNode *p，则p为指向某结点的指针变量，表示该结点的地址；而*p为对应的结点变量，表示该结点的名称。
- 首元结点、头结点、头指针
- 首元结点是指链表中存储第一个数据元素a1的结点
- 头结点是在首元结点之前附设的一个结点，其指针域指向首元结点
- 头指针是指向链表中第一个结点的指针
- （1）便于首元结点的处理
- 单链表是非随机存取的存储结构，要取得第i个数据元素必须从头指针出发顺链进行寻找，也称为顺序存取的存取结构。
- 单链表取值算法的平均时间复杂度为O(n)。
- 在单链表中，判别条件为p!=NULL或p->next!=NULL，而循环单链表的判别条件为p!=L或p->next!=L。
- 在双向链表的结点中有两个指针域，一个指向直接后继，另一个指向直接前驱
2.6 顺序表和链表的比较
- 当线性表的长度变化较大，难以预估存储规模时，宜采用链表作为存储结构。
- 所谓存储密度是指数据元素本身所占用的存储量和整个结点结构所占用的存储量之比
- 基于此，当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构。
- 若线性表的主要操作是和元素位置紧密相关的这类取值操作，很少做插入或删除时，宜采用顺序表作为存储结构。
- 对于频繁进行插入或删除操作的线性表，宜采用链表作为存储结构。
习题
- B. 需不断对L进行删除、插入
3.1 栈和队列的定义和特点
- 栈（stack）是限定仅在表尾进行插入或删除操作的线性表。
- 栈又称为后进先出（Last In First Out，LIFO）的线性表
- 在程序设计中，如果需要按照保存数据时相反的顺序来使用数据，则可以利用栈来实现。
- 队列（queue）是一种先进先出（First In First Out，FIFO）的线性表
3.2 案例引入
- 和线性表一样，栈和队列的存储结构也包括顺序和链式两种。
3.3 栈的表示和操作的实现
- 栈也有两种存储表示方法，分别称为顺序栈和链栈
- 顺序栈是指利用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。
- 栈空时，top和base的值相等，都指向栈底；栈非空时，top始终指向栈顶元素的上一个位置。
3.4 栈与递归
- 栈有一个重要应用是在程序设计语言中实现递归
- 所谓递归是指，若在一个函数、过程或者数据结构定义的内部又直接（或间接）出现定义本身的应用，则称它们是递归的，或者是递归定义的。
- 采取“分治法”进行递归求解的问题需要满足以下三个条件。（1）能将一个问题转变成一个新问题，而新问题与原问题的解法相同或类同，不同的仅是处理的对象，并且这些处理对象更小且变化有规律。（2）可以通过上述转化而使问题简化。（3）必须有一个明确的递归出口，或称递归的边界。
- 调用函数和被调用函数之间的链接及信息交换需通过栈来进行。
- 采用这种方法计算Fibonacci数列和Hanoi塔问题递归算法的时间复杂度均为O(2n)。
3.5 队列的表示和操作的实现
- 队列也有两种存储表示，顺序表示和链式表示。
- 在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置
- 对于非循环队列，尾指针和头指针的差值便是队列长度，而对于循环队列，差值可能为负数，所以需要将差值加上MAXQSIZE，然后与MAXQSIZE求余。
第4章 串、数组和广义表
- 串是一种特殊的线性表，其特殊性体现在数据元素是一个字符，也就是说，串是一种内容受限的线性表。
4.1 串的定义
- 串（string）（或字符串）是由零个或多个字符组成的有限序列，一般记为s=“a1a2 … an”(n≥0)
4.3 串的类型定义、存储结构及其运算
- 但考虑到存储效率和算法的方便性，串多采用顺序存储结构。
- 本章后面算法描述当中所用到的顺序存储的字符串都是从下标为1的数组分量开始存储的，下标为0的分量闲置不用。
- 子串的定位运算通常称为串的模式匹配或串匹配。
- 其改进在于：每当一趟匹配过程中出现字符比较不等时，不需回溯i指针，而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较
4.5 广义表
- 广义表是线性表的推广，也称为列表
- 广义表可为其他广义表所共享
- （3）广义表可以是一个递归的表，即广义表也可以是其本身的一个子表
- 值得提醒的是，广义表( )和(( ))不同。前者为空表，长度n=0；后者长度n=1，可分解得到其表头、表尾均为空表( )。
5.1 树和二叉树的定义
- 树的结构定义是一个递归的定义
- 结点：树中的一个独立单元
- 结点的度：结点拥有的子树数称为结点的度。
- 树的度：树的度是树内各结点度的最大值。
- 叶子：度为0的结点称为叶子或终端结点。
- 非终端结点：度不为0的结点称为非终端结点或分支结点。除根结点之外，非终端结点也称为内部结点。
- 双亲和孩子：结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。
- 祖先：从根到该结点所经分支上的所有结点。
- 子孙：以某结点为根的子树中的任一结点都称为该结点的子孙
- 层次：结点的层次从根开始定义起，根为第一层，根的孩子为第二层。树中任一结点的层次等于其双亲结点的层次加1。
- 树的深度：树中结点的最大层次称为树的深度或高度。
- 森林：是m（m≥0）棵互不相交的树的集合
- （1）有且仅有一个称之为根的结点；（2）除根结点以外的其余结点分为两个互不相交的子集T1和T2，分别称为T的左子树和右子树，且T1和T2本身又都是二叉树。
- （1）二叉树每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点）； （2）二叉树的子树有左右之分，其次序不能任意颠倒。
5.2 案例引入
- 如果在编码时考虑字符出现的频率，使频率高的字符采用尽可能短的编码，频率低的字符采用稍长的编码，来构造一种不等长编码，则会获得更好的空间效率，这也是文件压缩技术的核心思想
- 任何一个字符的编码都不是另一个字符的编码的前缀
5.4 二叉树的性质和存储结构
- 性质1 在二叉树的第i层上至多有2i−1个结点（i≥1）。
- 性质3 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
- 满二叉树：深度为k且含有2k−1个结点的二叉树。
- 满二叉树的特点是：每一层上的结点数都是最大结点数，即每一层i的结点数都具有最大值2i−1。
- 完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。
- 叶子结点只可能在层次最大的两层上出现
- 性质4 具有n个结点的完全二叉树的深度为注1。
- 在含有n个结点的二叉链表中有n+1个空链域
5.5 遍历二叉树和线索二叉树
- 线索二叉树是在第一次遍历时将结点的前驱、后继信息存储下来，便于再次遍历二叉树。
- 遍历二叉树（traversing binary tree）是指按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。
- 由二叉树的先序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树。
- 这种信息只有在遍历的动态过程中才能得到，为此引入线索二叉树来保存这些在动态过程中得到的有关前驱和后继的信息。
5.7 哈夫曼树及其应用
- 哈夫曼（Huffman）树又称最优树
- 路径长度：路径上的分支数目称作路径长度。
- 树的带权路径长度：树中所有叶子结点的带权路径长度之和，通常记作[插图]。
- 哈夫曼树：假设有m个权值{w1, w2,…, wm}，可以构造一棵含n个叶子结点的二叉树，每个叶子结点的权为wi，则其中带权路径长度WPL最小的二叉树称做最优二叉树或哈夫曼树。
- 在构造哈夫曼树时，首先选择权小的，这样保证权大的离根较近，这样一来，在计算树的带权路径长度时，自然会得到最小带权路径长度，这种生成算法是一种典型的贪心法。
- 为出现次数较多的字符编以较短的编码。
6.1 图的定义和基本术语
- 图（Graph）G由两个集合V和E组成，记为G=(V, E)，其中V是顶点的有穷非空集合，E是V中顶点偶对的有穷集合，这些顶点偶对称为边。
- 对于图G，若边集E(G)为有向边的集合，则称该图为有向图；若边集E(G)为无向边的集合，则称该图为无向图。
- 无向完全图和有向完全图：对于无向图，若具有n(n−1)/2条边，则称为无向完全图。对于有向图，若具有n(n−1)条弧，则称为有向完全图。
- 顶点v的度是指和v相关联的边的数目，记为TD(v)
- 路径长度是一条路径上经过的边或弧的数目。
- 回路或环：第一个顶点和最后一个顶点相同的路径称为回路或环。
- 强连通图和强连通分量：在有向图G中，如果对于每一对vi,vj∈V, vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。有向图中的极大强连通子图称作有向图的强连通分量。
- 连通图的生成树：一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n−1条边，这样的连通子图称为连通图的生成树。
6.5 图的遍历
- 广度优先搜索（Breadth First Search，BFS）遍历类似于树的按层次遍历的过程。
6.6 图的应用
- 在一个连通网的所有生成树中，各边的代价之和最小的那棵生成树称为该连通网的最小代价生成树（Minimum Cost Spanning Tree），简称为最小生成树。
- 一个无环的有向图称作有向无环图（Directed Acycline Graph），简称DAG图。
7.1 查找的基本概念
- 关键字是数据元素（或记录）中某个数据项的值，用它可以标识一个数据元素（或记录）
- 若在查找的同时对表做修改操作（如插入和删除），则相应的表称之为动态查找表，否则称之为静态查找表。
7.2 线性表的查找
- 折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
7.3 树表的查找
- 中序遍历一棵二叉树时可以得到一个结点值递增的有序序列。
- 磁盘管理系统中的目录管理，以及数据库系统中的索引组织多数都采用B-树这种数据结构。
8.1 基本概念和排序方法概述
- 排序（Sorting）是按关键字的非递减或非递增顺序对一组记录重新进行排列的操作
- 假设Ki=Kj（1≤i≤n，1≤j≤n，i≠j），且在排序前的序列中Ri领先于Rj（即i