1、1基本概念 数据 数据是信息的载体，在计算机科学中是指所有能输入到计算机中并能被计算机程序识别和处理的符号集合。 数据元素数据元素也称为结点，是表示数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据项数据项是构成数据元素的不可分割的最小单位。 数据对象数据对象是具有相同性质的数据元素的集合，是数据的子集。注意：在不产生混淆的情况下，将数据对象简称为数据。 数据结构数据结构是指相互之间存在一定关系的数据元素的集合，即数据结构是一个二元组 DataStructure = (D, R)，其中 D 是数据元素的集合， R 是 D 上关系的集合。按照视点的不同，数据结构分为逻辑结构和存
2、储结构。 数据的逻辑结构数据的逻辑结构是指数据元素之间逻辑关系的整体。根据数据元素之间逻辑关系的不同，数据结构分为四类： 集合：数据元素之间就是“属于同一个集合”，除此之外，没有任何关系； 线性结构：数据元素之间存在着一对一的线性关系； 树结构：数据元素之间存在着一对多的层次关系； 图结构：数据元素之间存在着多对多的任意关系。注意：数据结构分为两类：线性结构和非线性结构。 数据的存储结构数据的存储结构又称为物理结构，是数据及其逻辑结构在计算机中的表示。通常有两种存储结构：顺序存储结构和链接存储结构。顺序存储结构的基本思想是：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系是由元素的
3、存储位置来表示的。链接存储结构的基本思想是：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系是用指针来表示的。注意：存储结构除了存储数据元素之外，必须存储数据元素之间的逻辑关系。 抽象数据类型抽象数据类型是一个数据结构以及定义在该结构上的一组操作的总称。抽象数据类型提供了使用和实现两个不同的视图，实现了封装和信息隐藏。 算法的定义通俗地讲，算法是解决问题的方法，严格地说，算法是对特定问题求解步骤的一种描述，是指令的有限序列。 算法的特性 输入：一个算法有零个或多个输入（即算法可以没有输入），这些输入通常取自于某个特定的对象集合。 输出：一个算法有一个或多个输出（即算法必须要有输出），通
4、常输出与输入之间有着某种特定的关系。2 有穷性：一个算法必须总是（对任何合法的输入）在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中的每一条指令必须有确切的含义，不存在二义性。并且，在任何条件下，对于相同的输入只能得到相同的输出。 可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。 线性表的定义线性表简称表，是零个或多个具有相同类型的数据元素的有限序列。数据元素的个数称为线性表的长度，长度等于零时称为空表。 线性表的逻辑关系在一个非空表 L(a 1，a 2，a n)中，任意一对相邻的数据元素 ai-1 和 ai 之间（1in）存在序偶关系（a i-1，a i）
5、，且 ai-1 称为 ai 的前驱，a i 称为 ai-1 的后继。在这个序列中， a1 无前驱，a n 无后继，其它每个元素有且仅有一个前驱和一个后继。 顺序表的存储结构定义用 MaxSize 表示数组的长度，顺序表的存储结构定义如下：#define MaxSize 100typedef structElemType dataMaxSize; / ElemType 表示不确定的数据类型int length; /length 表示线性表的长度 SeqList; 顺序表是随机存取结构设顺序表的每个元素占用 c 个存储单元，则第 i 个元素的存储地址为：LOC(ai)= LOC(a1)(i1)c
6、顺序表的优缺点顺序表利用了数组元素在物理位置上的邻接关系来表示线性表中数据元素之间的逻辑关系，这使得顺序表具有下列优点： 无需为表示表中元素之间的逻辑关系而增加额外的存储空间； 可以快速地存取表中任一位置的元素（即随机存取）。同时，顺序表也具有下列缺点： 插入和删除操作需移动大量元素。在顺序表上做插入和删除操作，等概率情况下，平均要移动表中一半的元素。 表的容量难以确定。由于数组的长度必须事先确定，因此，当线性表的长度变化较大时，难以确定合适的存储规模。 造成存储空间的“碎片”。数组要求占用连续的存储空间，即使存储单元数超过所需的数目，如果不连续也不能使用，造成存储空间的“碎片”现象。 单链表
7、的存储结构定义单链表的存储结构定义如下：Struct Node ElemType data; / ElemType 表示不确定的数据类型struct Node *next; *first; /first 为单链表的头指针 双链表的存储结构定义双链表存储结构定义如下：3struct DulNodeElemType data; / ElemType 表示不确定的数据类型struct DulNode *prior, *next; / prior 为前驱指针域，next 为后继指针域 *first; /first 表示双链表的头指针 栈的定义 栈是限定仅在表尾进行插入和删除操作的线性表。允许插入和删除
8、的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈。 栈的操作特性 栈的操作具有后进先出的特性。 队列的定义队列是只允许在一端进行插入操作，而另一端进行删除操作的线性表。允许插入的一端称为队尾，允许删除的一端称为队头。 队列的操作特性队列的操作具有先进先出的特性。 循环队列中解决队空队满的判断条件方法一：附设一个存储队列中元素个数的变量 num，当 num=0 时队空，当 num=QueueSize 时为队满；方法二：修改队满条件，浪费一个元素空间，队满时数组中只有一个空闲单元；即队空的条件是front=rear，队满的条件是 (rear+1) % QueueSize=front，队
9、列长度为 (rear-front+QueueSize) % QueueSize。方法三：设置标志 flag，当 front=rear 且 flag=0 时为队空，当 front=rear 且 flag=1 时为队满。 串的定义串是零个或多个字符组成的有限序列。 空格串和空串的定义只包含空格的串称为空格串。串中所包含的字符个数称为串的长度，长度为 0 的串称空串，记作 “ “。 串的比较串的比较是通过组成串的字符之间的比较来进行的。给定两个串：X=“x1x2xn“Y=“y1y2ym“则当 n=m 且 x1=y1，x n=ym 时，称 X=Y；当下列条件之一成立时，称 XY： nm，且 xi=yi
10、（i =1，2，n）； 存在某个 kmin(m，n)，使得 xi=yi（i=1，2，k -1），x ky k。 改进的模式匹配算法中 nextj的求法用 nextj表示 tj 对应的 k 值（ 1jm ），其定义如下： 数组的基本操作数组是一个具有固定格式和数量的数据集合，在数组上一般不能做插入、删除元素的操作。因此，在数组中通常只有两种操作： 读取：给定一组下标，读取相应的数组元素；0 j=1max k | 1kj 且t 1t2 tk -1 =t j-k+1tj-k+2 tj-11 其它情况nextj=4 修改：给定一组下标，存储或修改相应的数组元素。 二维数组的寻址按行优先，设二维数组的行
11、下标与列下标的范围分别为l 1，h 1与l 2，h 2，则任一元素 aij 的存储地址可由下式确定：LOC(aij)LOC(a l1l2)(i l1)(h2l 21)(j l 2)c 特殊矩阵的定义特殊矩阵是指矩阵中有很多值相同的元素并且它们的分布有一定的规律。 矩阵压缩存储的基本思想压缩存储的基本思想是： 为多个值相同的元素只分配一个存储空间； 对零元素不分配存储空间。 对称矩阵的压缩存储中：下三角元素 aij（ij ）在一个数组 SA 中的下标为：k = i(i-1)/2 + j-1。上三角中的元素 aij（ij），则访问和它对应的下三角中的元素 aji 即可，即：k = j(j-1)/2
12、 + i-1。 三角矩阵的压缩存储中：下三角矩阵中任一元素 aij 在一个数组 SA 中的下标 k 与 i、j 的对应关系为：上三角矩阵元素 aij 在 SA 中的下标为：k =(i-1)(2n-i +2)/2+(j-i)。 稀疏矩阵的压缩存储方式三元组顺序表和十字链表 三元组的定义struct elementint row, col;ElemType item ; 广义表的定义广义表是 n（n0）个数据元素的有限序列。 表头当广义表 LS 非空时，称第一个元素为 LS 的表头； 表尾称广义表 LS 中除去表头后其余元素组成的广义表为 LS 的。 长度广义表 LS 中的直接元素的个数称为 LS
13、 的长度； 深度广义表 LS 中括号的最大嵌套层数称为 LS 的深度。 树的定义 树是 n（n0）个结点的有限集合。当 n0 时，称为空树；任意一棵非空树满足以下条件： 有且仅有一个特定的称为根的结点； 当 n1 时，除根结点之外的其余结点被分成 m（m0）个互不相交的有限集合 T1，T 2，T m，其中每个集合又是一棵树，并称为这个根结点的子树。k= i(i-1)/2 + j-1 当 ijn(n1)/2 当 ij5 结点的度、树的度某结点所拥有的子树的个数称为该结点的度；树中各结点度的最大值称为该树的度。 叶子结点、分支结点度为 0 的结点称为叶子结点，也称为终端结点；度不为 0 的结点称为
14、分支结点，也称为非终端结点。 孩子结点、双亲结点、兄弟结点某结点的子树的根结点称为该结点的孩子结点；反之，该结点称为其孩子结点的双亲 路径、路径长度如果树的结点序列 n1, n2, , nk 满足如下关系：结点 ni 是结点 ni+1 的双亲（1ik），则把 n1, n2, , nk 称为一条由 n1 至 nk 的路径；路径上经过的边的个数称为路径长度。 祖先、子孙如果从结点 x 到结点 y 有一条路径，那么 x 就称为 y 的祖先，而 y 称为 x 的子孙。注意：某结点子树中的任一结点都是该结点的子孙。 结点的层数、树的深度（高度）规定根结点的层数为 1，对其余任何结点，若某结点在第 k 层
15、，则其孩子结点在第 k+1 层；树中所有结点的最大层数称为树的深度，也称为树的高度。 二叉树的定义 二叉树是 n（n0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。 二叉树的特点二叉树的特点是： 每个结点最多有两棵子树，所以二叉树中不存在度大于 2 的结点； 子树的次序不能任意颠倒，某结点即使只有一棵子树也要区分是左子树还是右子树。注意：二叉树和树是两种树结构。 二叉树的基本形态二叉树具有五种基本形态： 空二叉树； 只有一个根结点； 根结点只有左子树； 根结点只有右子树； 根结点既有左子树又有右子树。 斜树所
16、有结点都只有左子树的二叉树称为左斜树；所有结点都只有右子树的二叉树称为右斜树；左斜树和右斜树统称为斜树。斜树的特点：每一层只有一个结点，即只有度为 1 和度为 0 的结点并且只有一个叶子结点； 斜树的结点个数与其深度相同。 满二叉树在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。满二叉树的特点： 叶子结点都在最下一层； 只有度为 0 和度为 2 的结点。 完全二叉树对一棵具有 n 个结点的二叉树按层序编号，如果编号为 i（1i n）的结点与同样深度的满二叉树中编号为 i 的结点在二叉树中的位置完全相同，则这棵二叉树称为完全二叉树。完全二
17、叉树的特点是： 叶子结点只能出现在最下两层，且最下层的叶子结点都集中在左面连续的位置； 如果有度为 1 的结点，只可能有一个，且该结点只有左孩子。 二叉树的基本性质性质 1 二叉树的第 i 层上最多有 2i-1 个结点（i1）。6性质 2 在一棵深度为 k 的二叉树中，最多有 2k-1 个结点，最少有 k 个结点。性质 3 在一棵二叉树中，如果叶子结点的个数为 n0，度为 2 的结点个数为 n2，则n0n 21。性质 4 具有 n 个结点的完全二叉树的深度为 。1log2性质 5 对一棵具有 n 个结点的完全二叉树中的结点从 1 开始按层序编号，则对于任意的编号为i（1in）的结点（简称为结点
18、 i），有： 如果 i1，则结点 i 的双亲的编号为 ；否则结点 i 是根结点，无双亲；2/i 如果 2in，则结点 i 的左孩子的编号为 2i；否则结点 i 无左孩子； 如果 2i1n，则结点 i 的右孩子的编号为 2i1；否则结点 i 无右孩子。 二叉树的存储包括：二叉树的顺序存储和二叉树的链式存储。二叉链表的存储结构定义如下： struct BiNodeElemType data; BiNode *lchild, *rchild; *root; /root 表示二叉链表的头指针struct TriNodeElemType data; TriNode *lchild, *rchild, *
19、parent; / parent 指向该结点的双亲 *root; /三叉链表的头指针 遍历的含义所谓遍历就是无重复无遗漏地访问。二叉树的遍历是指从根结点出发，按照某种次序访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。 二叉树的遍历次序定义前序遍历（或称前根遍历、先序遍历）若二叉树为空，则空操作返回；否则 访问根结点； 前序遍历根结点的左子树； 前序遍历根结点的右子树。中序遍历（或称中根遍历）若二叉树为空，则空操作返回；否则 中序遍历根结点的左子树； 访问根结点； 中序遍历根结点的右子树。后序遍历（或称后根遍历）若二叉树为空，则空操作返回；否则 后序遍历根结点的左子树； 后序遍历
20、根结点的右子树；7 访问根结点。层序遍历二叉树的层序遍历是从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。 线索二叉树的定义在一个具有 n 个结点的二叉链表中，利用 n+1 个空指针域存放指向该结点在某种遍历序列中的前驱和后继结点的指针，这些指向前驱和后继结点的指针称为线索，加上线索的二叉树称为线索二叉树，相应地，加上线索的二叉链表称为线索链表。 线索二叉树的存储结构定义线索链表中的结点定义如下：enum flag Child, Thread; /枚举类型，枚举常量 Child=0，Thread=1struct ThrNodeElemType d
21、ata; / ElemType 表示不确定的数据类型ThrNode *lchild, *rchild;flag ltag, rtag;*root; /root 表示线索链表的头指针 树的存储结构包括：双亲表示法、孩子表示法、孩子兄弟表示法。双亲表示法的存储结构定义如下：#define MaxSize 100; /树中最大结点个数struct PNode /数组元素的类型ElemType data; /树中结点的数据信息，int parent; /该结点的双亲在数组中的下标;PNode TreeMaxSize; 孩子表示法的存储结构定义如下：struct CTNode /孩子结点int chil
22、d;CTNode *next;struct CBNode /表头结点ElemType data;CTNode *firstchild; /指向孩子链表的头指针;孩子兄弟表示法又称为二叉链表表示法，存储结构定义如下：struct TNodeElemType data; / ElemType 表示不确定的数据类型TNode *firstchild; /firstchild 指向该结点的第一个孩子TNode *rightsib; /rightsib 指向该结点的右兄弟; 树转换为二叉树8树转换为二叉树的方法是： 加线树中所有相邻兄弟结点之间加一条连线； 去线对树中的每个结点，只保留它与第一个孩子结点
23、之间的连线，删去它与其它孩子结点之间的连线； 层次调整以根结点为轴心，将树顺时针转动一定的角度，使之层次分明。 森林转换为二叉树森林转换为二叉树的方法如下： 将森林中的每棵树转换成二叉树； 从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连起来后，所得到的二叉树就是由森林转换的二叉树。 二叉树转换为树或森林树和森林转换为二叉树的过程是可逆的，将一棵二叉树还原为树或森林的方法如下： 加线 若某结点 x 是其双亲 y 的左孩子，则把结点 x 的右孩子、右孩子的右孩子、，都与结点 y 用线连起来； 去线删去原二叉树中所有的双亲结点与右孩子结点的连线； 层次调
24、整整理由、两步所得到的树或森林，使之层次分明。树的遍历序列与二叉树的遍历序列之间的对应关系根据树与二叉树的转换关系以及树和二叉树遍历的操作定义可知，树的遍历序列与由树转化成的二叉树的遍历序列之间具有如下对应关系：树的前序遍历序列等于二叉树的前序遍历序列，树的后序遍历序列等于二叉树的中序遍历序列。 哈夫曼树中叶子结点的权值叶子结点的权值是指对叶子结点赋予的一个有意义的数值量。 二叉树的带权路径长度设二叉树具有 n 个带权值的叶子结点，从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和称做二叉树的带权路径长度，记为：WPL= klw1其中，w k 为第 k 个叶子结点的权值； lk 为从
25、根结点到第 k 个叶子结点的路径长度。 哈夫曼树定义给定一组具有确定权值的叶子结点，可以构造出不同的二叉树，将其中带权路径长度最小的二叉树称为哈夫曼树，也称为最优二叉树。 哈夫曼算法的基本思想哈夫曼算法的基本思想是： 初始化：由给定的 n 个权值w 1，w 2，w n构造 n 棵只有一个根结点的二叉树，从而得到一个二叉树集合 FT 1，T 2，T n； 选取与合并：在 F 中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一棵新的二叉树，这棵新二叉树的根结点的权值为其左、右子树根结点的权值之和； 删除与加入：在 F 中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到 F 中； 重
26、复、两步，当集合 F 中只剩下一棵二叉树时，这棵二叉树便是哈夫曼树。 图的定义 图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G=(V，E)9其中，G 表示一个图，V 是图 G 中顶点的集合，E 是图 G 中顶点之间边的集合。 无向图与有向图若顶点 vi 和 vj 之间的边没有方向，则称这条边为无向边，用无序偶对(v i，v j)来表示；若从顶点 vi 到vj 的边有方向，则称这条边为有向边（也称为弧），用有序偶对来表示，v i 称为弧尾，v j 称为弧头。如果图的任意两个顶点之间的边都是无向边，则称该图为无向图，否则称该图为有向图。 简单图若不存在顶点到其自身的边，且同一条边不
27、重复出现，则称这样的图为简单图。 邻接、依附在无向图中，对于任意两个顶点 vi 和 vj，若存在边(v i，v j)，则称顶点 vi 和 vj 互为邻接点，同时称边(vi，v j)依附于顶点 vi 和 vj。在有向图中，对于任意两个顶点 vi 和 vj，若存在弧，则称顶点 vj 是 vi 的邻接点，同时称弧依附于顶点 vi 和 vj。 无向完全图、有向完全图在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。含有 n 个顶点的无向完全图有 n(n-1)/2 条边。在有向图中，如果任意两顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。含有 n 个顶点的有向完全图有 n(n-
28、1)条边。 稠密图、稀疏图称边数很少的图为稀疏图，反之，称为稠密图。 顶点的度、入度、出度在无向图中，顶点 v 的度是指依附于该顶点的边的个数，记为 TD(v)。在具有 n 个顶点 e 条边的无向图中，有下式成立：eTDnii2)(1在有向图中，顶点 v 的入度是指以该顶点为弧头的弧的个数，记为 ID(v)；顶点 v 的出度是指以该顶点为弧尾的弧的个数，记为 OD(v)。在具有 n 个顶点 e 条边的有向图中，有下式成立：niiniOI11)( 连通图、连通分量在无向图中，若任意顶点 vi 和 vj(ij)之间有路径，则称该图是连通图。非连通图的极大连通子图称为连通分量。 强连通图、强连通分量
29、在有向图中，对任意顶点 vi 和 vj (ij )，若从顶点 vi 到 vj 和从顶点 vj 到 vi 均有路径，则称该有向图是强连通图。非强连通图的极大强连通子图称为强连通分量。 邻接矩阵的存储结构定义假设图 G(V，E)有 n 个顶点，则邻接矩阵是一个 nn 的方阵，定义为：邻接矩阵的存储结构定义如下：#define MaxSize 10typedef struct1 若(v i，v j)E 或E0 否则arcij10ElemType vertexMaxSize; /存放图中顶点的信息，ElemType 表示不确定的数据类型int arcMaxSizeMaxSize; /存放图中边的信息i
30、nt vertexNum, arcNum; /图的顶点数和边数 MGraph; 邻接表的存储结构定义邻接表是一种顺序存储与链接存储相结合的存储方法，具体方法为：将顶点 vi 的所有邻接点链成一个单链表，称为顶点 vi 的边表（对于有向图则称为出边表），边表的头指针和顶点的数据信息采用顺序存储（称为顶点表）。所以，在邻接表中存在两种结点：顶点表结点和边表结点。其中，vertex：数据域，存放顶点信息；firstedge：指针域，边表的头指针；adjvex：邻接点域，存放边该顶点的邻接点在顶点表中的下标；next：指针域，指向边表中的下一个结点。邻接表的存储结构定义如下：struct ArcNod
31、e /定义边表结点int adjvex; /邻接点域ArcNode *next;struct VertexNode /定义顶点表结点ElemType vertex; / ElemType 表示不确定的数据类型ArcNode *firstedge;#define MaxSize 10typedef structVertexNode adjlistMaxSize; /顶点表int vertexNum, arcNum; /图的顶点数和边数 ALGraph; 图的遍历次序定义 深度优先遍历从图中某顶点 v 出发进行深度优先遍历的基本思想是： 访问顶点 v； 从 v 的未被访问的邻接点中选取一个顶点 w，从 w 出发进行深度优先遍历； 重复上述两步，直至图中所有和 v 有路径相通的顶点都被访问到。广度优先遍历从图中某顶点 v 出发进行广度优先遍历的基本思想是： 访问顶点 v； 依次访问 v 的各个未被访问的邻接点 v1，v 2，v k； 分别从 v1，v 2，v k 出发依次访问它们未被访问的邻接点，直至图中所有与顶点 v 有路径相通的顶点都被访问到。vertex firstedge adjvex next顶点表结点 边表结点邻接表表示的结点结构
