数据结构
(C
语言版
)
第一章：绪论
-
数据结构
是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的科学。 -
数据(data)
是对客观事物的符号表示，在计算机科学中是指所有以输入到计算机中并被计算机程序处理的符号的总称。 -
数据元素 (data element)
是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 -
数据对象 (data object)
是性质相同的数据元素的集合，是数据的一个子集。 -
数据结构 (data structure)
是相互之间存在一种或多种特定关系的数据元素的集合。 -
根据数据结构之间关系的不同特性，通常有下列4 类基本结构:
集合、线性结构、树形结构、图状结构或网状结构。
-
抽象数据类型 (ADT)
：是指一个数学模型以及定义在该模型上的一组操作，有“数据抽象”和“数据封装 ”两个重要特性。 -
算法(algorithm)
是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作，具有“有穷性 ”，“确定性 ”，“可行性 ”，“输入 ”，“输出 ” 五个特性。 - 算法设计的要求 ：正确性、可读性、健壮性、效率与低存储需求。
-
一般情况下，算法中基本操作重复执行的次数是问题规模 n 的某个函数 f(n) ，算法的时间量度记作 T(n)=O(f(n))，它表示随问题规模 n 的增大，算法执行时间的增长率和 f(n)的增长率相同，称作算法的
渐近时间复杂度
，简称
时间复杂度
。
第二章：线性表
-
线性表：
是 n 个数据元素的有限序列，有顺序存储和链式存储两种表示形式。 -
线性表的链式存储结构
的特点是用一组任意的存储单元存储线性表的数据元素，包括两个域， 其中存储数据元素信息的域称为数据域，存储直接后继存储位置的域称为指针域。 -
循环链表
是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。 -
双向链表
是指有两个指针域，其一指向直接后继，另一指向直接前趋。
第三章：栈和队列
-
栈是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义称为栈顶， 相应地， 表头端称为栈底。栈的修改是按后进先出的原则进行的，因此又称后进先出表。
-
队列是一种先进先出的线性表，它只允许在表的一端进行插入，而在另一端删除元素，在队列中，允许插入的一端称做队尾，允许删除的一端称做队头。
-
循环队列
是指将顺序队列臆造为一个环状的空间，即把存储队列元素的表从逻辑上视为一个环，称为循环队列。
队满条件:(Q.rear+1)%MaxSize==Q.front
队空条件：Q.front==Q.rear
队列中元素个数：（Q.rear-Q.front+MaxSize）%MaxSize
第四章：串
-
串(string)
是由零个或多个字符组成的有限序列。串中任意个连续的字符组成的子序列称该串的子串， 通常称字符在序列中的序号为该字符在序列中的序号为该字符的在串中的位置。
-
称两个串是相等的， 当且仅当这两个串的值相等。 也就是说，只有当两个串的长度相等，并且各个对应位置的字符都相等时才相等。
第六章：树与二叉树
-
树(tree)
是指 n(n>=0) 个结点的有限集，在任意一棵非空树中：
1）有且仅有一个特定的称为根。
2）当 n>1 时，其余结点可分为 m(m>0) 个互不相交的有限集，其中每一个集合本身又是一棵树。
-
树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树称为结点的
度
。度为 0 的结点称为
叶子或终端结点
。树的度是树内各结点的度的最大值。结点的子树的根称为该结点的
孩子
，相应的该结点称为孩子的
双亲
。同一个双亲的孩子之间互称兄弟。
结点的祖先
是从根到该结点所经分支上的所有结点。 反之，以某结点为根的子树中的任一结点都称为该结点的
子孙
。
-
结点的层次
从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第l 层，则其子树在第 l+1 层。其双亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度或高度。
-
如果将树中结点的各种子树看成是从左到右是有次序的，则称该树为有序树，否则称为无序树。
-
森林(forest)
是 m(m>0) 棵互不相交的树的集合。
-
二叉树（Binary Tree)
是另一种树型结构， 它的特点是每个结点至多只有两棵子树，并且二叉树的子树有左右之分，其次序不能任意颠倒。
-
一个深度为 k 且有 2K-1 个结点的二叉树称为满二叉树。深度为 k 的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应时，称之为完全二叉树。
-
遍历二叉树
：指按某条搜索路径巡访树上每个结点，使得每个结点均被访问一次，而且仅被访问一次。有先序遍历、中序遍历、后序遍历三种。
-
若结点有左子树，则其 lchild（rchild ）域指向指示其左 (右)孩子，否则令 lchild（rchild ）域指示其
前驱（后继）
，这种结点构成的二叉链表做为二叉树的存储结构称为线索链表。
-
从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径， 路径上的分支数目称做
路径长度
。树的路径长度是从树根到每一个结点的路径长度之和。树的带权路径长度 为树中所有叶子结点的带权路径长度之和。
-
假设有 n 个权值 {w1,w2, ⋯⋯，wn}，试构造一棵有 n 个叶子结点的二叉树，每个叶子结点带树为 wi,则其中带权路径长度 WPL 最小的二叉树称为
最优二叉树或赫夫曼树
。
第七章：图
-
在图中的数据元素通常称做 顶点，<v,w> 表示从 v 到 w 的一条
弧（arc）
，且称 v 为
弧尾（tail）
，称w 为
弧头（head）
,此时称图为
有向图（digraph）
，若 (v,w) 表示 v 和 w 之间的一条
边
，此时的图称为
无向图（undigraph）
。
-
有 n*(n-1)/2 条边的无向图称为
完全图（completed graph）
。具有 n(n-1) 条弧的有向图称为
有向完全图
，有很少条边或弧的图称为
稀疏图(sparse graph)
，反之称为
稠密图(dense graph)
。有时图的边或弧具有与它相关的数，这种与图的边或弧相关的数叫做
权
，这种带权的图称为
网(network)
。
-
顶点 v 的度是和 v 相关联的边的数目，记为TD(V) 。
-
无向图
G=(V,{E}) 中从点 v 到顶点 v’的路径是一个顶点序列，
路径的长度
是路径上边或弧的数目。第一个顶点和最后一个顶点相同的路径称为
回路或环
。序列中不重复出现的路径称为
简单路径
。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为
简单回路或简单环
。
-
在无向图 G 中，如果从顶点 v 到顶点 v’有路径，则称 v 和 v’是连通的。如果对于图中任意两个顶点 vi 、vj∈ V,vi 和 vj 都是连通的，则称 G 是连通图。所谓
连通分量
指的是无向图中的极大连通子图。
-
在有向图 G 中，如果对于每一对 vi、vj∈V, vi≠vj ,从 vi 到 vj 和从 vj 到 vi 都存在路径，则称 G 是强连通图。有向图中的极大强连通子图称做
有向图的强连通分量
。
-
一个
连通图的生成树
是一个极小连通子图， 它含有图中全部顶点，但只有足以构成一棵树的 n-1 条边。如果在一棵生成树上添加一条边， 必定构成一个环。 一棵有 n 个顶点的生成树有且仅有 n-1 条边。如果一个图有 n 个顶点和小于 n-1 条边，则是非连通图，如果它多于 n-1 条边，则一定有环。但是，有 n-1 条边的图不一定是生成树。
-
如果一个有向图恰有一个顶点的入度为 0，其余顶点的入度均为1，则是一棵
有向树
。一个有向图的生成森林 由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。
-
图的存储结构
有邻接矩阵、邻接表、逆邻接表以及十字链表等。
-
图的遍历
：指从图中某一顶点出发访遍图中其余顶点且使每一个顶点仅被访问一次。
-
通常有两条遍历图的路径：
-
深度优先搜索
：类似于树的先序遍历，假设从图中某顶点 v 出发，在访问了 v 之后依次从 v 的未被访问的邻接点出发深度优先遍历图，直到图中所有和 v 有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点做为起始点，重复上述过程，直至图中所有顶点都被访问到为止。
-
广度优先搜索
：类似于树的层序遍历，假设从图中某顶点 v 出发，在访问了 v 之后依次访问它们的邻接点， 并使先被访问的顶点的邻接点先于后访问的顶点的邻接点，直到图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直到图中所有顶点都被访问到为止。
-
假若在删去顶点 v 以及和 v 相关联的各边之后， 将图的一个连通分量分割成两个或两个以上的边通分量，则称顶点v 为该图的一个
关节点
。一个没有关节点的图称为
重连通图
。若在连通图上至少删去k 个顶点才能破坏图的连通性，则称此图的
连通度
为 k。
-
对于无向图来说， 若深度优先搜索过程中遇到回边，则必定存在环， 而对于有向图来说，这条回边有可能是指向深度优先生成森林中另一棵生成树上顶点的弧。
-
拓扑排序
(T
opological Sort)：指由某个集合上的一个偏序得到该集合上的一个全序。
-
AOV- 网：指用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网。
-
AOE- 网：指用边表示活动的网，是一个带权的有向无环图，其中，顶点表示事件弧表示活动，权表示活动持续的时间，通常一个AOE-网可用来估算工程的完成时间。
-
在正常的情况（无环）下，网中只有一个入度为零的点，称做
源点
和一个出度为零的点，称为
汇点
。
-
在 AOE-网点，路径长度最长的路径叫做
关键路径
，关键路径上的所有活动都是
关键活动
。
第九章：查找
-
查找表 （Search Table）
：是由同一类型的数据元素构成的集合。若对查找表只作查找操作，则称此类查找表为
静态查找表 (Static Search Table)
，若在查找过程中同时插入查找表中不存在的数据元素，则称此类表为
动态查找表
(Dynamic Search Table)
。
-
关键字（
Key
）
：是数据元素或记录中某个数据项的值，用它可能标识一个数据元素，若此关键字可以惟一地标识一个记录，则称此关键字为
主关键字
(Primary Key)
，反之，称用以识别若干记录的关键为
次关键字
(Secondary Key)
。
-
查找
：根据给定的某个值，在查找表中确定一个其关键字等给定值的记录或数据元素，若表中存在这样一个记录，则称查找是成功的，此时查找的结果为给出整个记录的信息，或指示该记录在查找表中的位置，若表中不存在关键字等于给定值的记录，则称查找不成功，此时查找的结果可给出一个“空”记录或“空”指针。
-
顺序查找
(Sequential Search)
的查找过程为：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功。反之，若直至第一个记录，其关键字和给定值比较都不相等，则表明表中没有所查记录，查找不成功。
-
平均查找长度 (Average Search Length)
：为确定记录在查找表中的位置，需和给定值进行比较的关键字的个数的期望值称为查找算法在查找成功时的平均查找长度。
-
折半查找
(Binary Search)
的查找过程：先确定待查记录在有序表中所在范围，然后逐步缩小范围直到找到或找不到该记录为止。
-
判定树
：树中每个结点表示表中一个记录，结点中的值为该记录在表中的位置，通常称这个查找过程的二叉树称为判定树。折半查找法在成功时进行比较的关键字个数最多不超过树的深度。
-
次优查找树
(Nearly Optimal Search Tree)
：构造一棵二叉树，使这棵二叉树的带权内路径长度 PH 值在所有具有同样权值的二叉树中近似为最小。
-
二叉排序树 (Binary Sort Tree)
：或者是一棵空树，或者是具有下列性质的二叉树:
a) 若它的左子树不空，则左子村上所有结点的值均小于它的根结点的值。
b) 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。
c) 它的左、右子树也分别为二叉排序树。
-
平衡二叉树 (Balanced Binary Tree)
：又称
AVL 树
，它或者是一棵空树，或者是具有下列性质的二叉树， 它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过 1。
-
平衡因子 BF (Balance Factor)
：为该结点的左子树深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只能是-1，0，1，只要二叉树上一个结点的平衡因子的绝对值大于 1，则该二叉树是不平衡的。
-
哈希表 (Hash Table)
：根据设定的哈希函数和处理冲突的方法将一组关键字映射到一个有限的连续的地址集上，并以关键字在越来越集中的像作为记录在表中的存储位置，这种表便称为哈希表， 这一映射过程称为哈希造表或散列，所得的存储位置称哈希地址或散列地址。
-
冲突
(Collision)
：对不同的关键字可能得到同一哈希地址，这种现象称为冲突，具有相同函数值的关键字对该哈希函数来说称作同义词。
-
常用的构造哈希函数的方法有：
-
直接定址法：取关键字或关键字的某个线性函数值为哈希地址。
-
数字分析法： 假设关键字是以 r 为基的数， 并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干位组成哈希地址。
-
平方取中法：取关键字平方的后的中间几位作为哈希地址。
-
折叠法：将关键字分割成位数相同的几部分，然后取这几部分的叠加和为哈希地址。
-
除留余数法： 取关键字被某个不大于哈希表表长 m 的数 p 除后的余数为哈希地址。
-
随机数法：选择一个随机函数，取关键字的随机函数值为它的哈希地址。
-
常用的处理冲突的方法：
- 开放定址法： 其中增量序列有线性探测再散列，二次探测再散列，随机探测再散列。
- 再哈希法： 即在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。
- 链地址法：将所有关键字为同义词的记录存储在同一线性链表中。
- 建立一个公共溢出区。
-
二次聚集
：指在处理冲突过程中发生的两个第一个哈希地址不同的记录争夺同一个后继哈希地址的现象。
-
装填因子
：是表中填入的记录数与哈希表的长度之商，哈希表的平均查找长度是装填因子的函数，不是规模n 的函数。
第十章：内部排序
-
排序
(Sorting)
：指将一个数据元素的任意序列重新排列成一个按关键字有序的序列。
-
假设 Ri=Rj,且在排序前的序列中Ri 领先于Rj ，若在排序后的序列中 Ri 仍领先于 Rj，则称所用的排序方法是稳定的，反之称所用的排序方法是不稳定的。
-
由于待排序的记录的数量不同， 使得排序过程中涉及的存储器不同， 可将排序方法分为两大类：
-
内部排序
：指的是待排序记录放在计算机随机存储器中进行的排序过程
-
外部排序
：指的是待排序记录的数量很大，以致内在一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。
-
-
直接插入排序 (Straight Insertion Sort)
：它的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的，记录数增 1 的有序表。
-
希尔排序 (Shell Sort)
：又称缩小增量排序，基本思想是先将整个记录序列分割成若干子序列分别进行直接插入排序，待整个序列中记录基本有序时，再对全体记录进行一次直接插入排序。
-
起泡排序 (Bubble Sort)
：首先将第一个记录的关键字同第二个记录的关键字进行比较，或为逆序，则交换， 依此类推，直至第 n-1 个记录和第 n 个记录的关键字进行比较为止。判别起泡排序结束的条件应该是在一趟排序过程中没有进行交换记录的操作。
-
快速排序 (Quick Sort)
：它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，分别对这丙部分继续进行快速排序，直至整个序列有序。
-
选择排序
：它的基本思想是每一趟在 n-i+1 个记录中选取关键字最小的记录作为有序序列中第 i 个记录。
-
堆排序 (Heap Sort)
：若在输出堆顶的最小值之后，使得剩余的 n-1 个元素的序列重新又构成一个堆，则得到 n 个元素中的次小值，如此反复，便能得到一个有序序列，称这个过程为堆排序。
-
归并排序 (Merging Sort)
是将两个或两个以上的有序表组合成一个新的有序表，其中 2-归并中的核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列。
-
基数排序（radix sort）
属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
|
|
|
|
|
|
||
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|