数据结构复习大纲.doc

第1章 概述1概念和术语数据：是能输入到计算机中并能被计算机程序处理的符号的总称。数据元素：是数据的基本单位，它在计算机处理和程序设计中通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成。数据对象：是具有相同特征的数据元素的集合，是数据的一个子集。数据结构：是数据元素的组织形式，或数据元素相互之间存在一种或多种特定关系的集合。数据的逻辑结构：是指数据结构中数据元素之间的逻辑关系。数据的存储结构：是数据的逻辑结构在计算机内存中的存储方式，又称物理结构。数据类型：是一组具有相同性质的操作对象以及该组操作对象上的运算方法的集合。抽象数据类型：是指一个数学模型以及在该模型上定义的一套运算规则的集合。算法：建立在数据结构基础上的，为解决问题而采取的步骤和方法。2逻辑结构的四种基本形态根据数据元素之间关系的不同特征，通常有下列四类基本结构：（1）集合：结构中的数据元素间除了“同属于一个集合”的关系外，别无其它关系。（2）线性结构：结构中的数据元素之间存在一个对一个的关系。（3）树型结构：结构中的数据元素之间存在一个对多个的关系。（4）图型结构或网状结构：结构中的数据元素之间存在多个对多个的关系。3数据存储结构的基本组织方式数据存储结构有顺序和链式两种方式。（1）顺序存储结构的特点：要借助数据元素在存储器中的相应位置来体现数据元素相互间的逻辑关系，常用高级编程语言中的“一维数组”来描述或实现。（2）链式存储结构的特点：通过表示数据元素存储地址的指针来表示数据元素之间的逻辑关系，通常用链表来实现。在顺序存储结构的基础上，又可延伸变化出另外两种存储结构，即索引存储和散列存储。（1）索引存储就是在数据文件的基础上增加了一个索引表文件。通过索引表建立索引，可以把一个顺序表分成几个顺序子表，其目的是在查询时提高查找效率，避免盲目查找。（2）散列存储就是通过数据元素与存储地址之间建立起某种映射关系，使每个数据元素与每一个存储地址之间尽量达到一一对应的目的。这样，查找时同样可大大提高效率。4数据结构的研究内容数据结构的核心研究内容包括三个方面：数据的逻辑结构、存储结构以及相应的基本操作运算的定义和实现。5算法的五个重要特征（1）有穷性：一个算法必须保证在执行有限步骤之后结束，而不是无限的。（2）确定性：算法中每一条指令必须有明确的含义，而不能是模棱两可的。（3）可行性：每一个操作步骤都必须在有限的时间内完成。（4）输入：一个算法可以有一个或多个输入，也可以没有输入。（5）输出：一个算法可以有一个或多个输出。没有输出的算法是没有实际意义的。6算法的评价标准（1）正确性。（2）易读性。（3）高效性。（4）可维护性。7算法分析的目的算法分析主要是指分析算法的效率。算法效率的度量主要从两个方面：算法的运行时间和算法所需的存储空间。分析的目的是通过考察算法的时间和空间效率，以求改进算法或对不同的算法进行比较。一般情况下，鉴于运算空间（内存）较为充足，所以把算法的时间复杂度分析作为重点。8算法的时间复杂度分析（1）算法运算时间的度量的两种方法：事后统计的方法和事前分析估算的方法。（2）算法运行时间的分析规则通常把一个程序的运行时间定义为一个T（n），其中n是该程序输入数据的规模，而不是某一个具体的输入。T(n)的单位是不确定的，一般把它看成在一个特定计算机上执行的指令条数。通常记作：T(n)=O(f(n)，其中f(n)表示数据输入规模。常见的算法时间复杂度的形式按性能降序的排列如下：O(1)O()O(n)O(n*)O()O()O()9算法空间复杂度的含义空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。算法在计算机存储器内占用的存储空间主要分为三部分：算法源代码本身占用的存储空间；算法输入输出数据所占用的存储空间；算法运行过程中临时占用的存储空间。考虑一个算法的空间复杂度时，要综合分析这三个方面的因素。通常记作：S(n)=O(f(n)，其中n为问题的规模（或大小）。第2、3章 线性表、栈、队列1线性表的定义线性表是n个数据元素的有限序列，其中n（n0）为线性表的长度。线性表中各个元素的类型相同。对于线性表（a1，a2，ai，an）而言，数据元素a1没有直接前趋，an没有直接后继，表中的其它元素ai（2in-1）有且仅一个直接前趋ai-1和直接后继ai+1。 2顺序表顺序表是指线性表的顺序存储结构，即用一组连续的存储单元依次存放线性表的数据元素。在C语言中可用一维数组来表示。在顺序表中，以数据元素在计算机内“物理位置相邻”来表示表中数据元素间的逻辑关系。顺序表是一种随机存储结构，只要确定了存储顺序表的起始位置，则表中任一元素都可以随机存取。所以在顺序表中可以方便的进行数据元素的查找及存取。但是在进行插入和删除操作时，将会引起元素的大量移动，因而效率比较低，并且易产生空间浪费或“上溢”现象。顺序表的操作还应注意元素的存储位置，即数组下标（C语言中下标从0开始）。3链表 链表是线性表的链式存储结构。链表是用一组任意的存储单元（可以是连续的，也可以是不连续的）存放线性表的数据元素。在链表中，通过指针来表示元素之间的逻辑关系的，不再有逻辑顺序与物理存储顺序一致的特点，是非顺序存储结构。在单链表中，每个结点由数据域和指针域组成。数据域保存数据元素的信息，指针域存放其直接后继的存储位置。其类型可描述为：typedef struct Node elemtype data;struct Node *next;LinkList;单链表由头指针唯一确定。为了便于操作，可在链表的第一个结点之前添加一个表头结点。在链表中进行插入和删除操作只需要修改有关的指针内容，不需要移动元素。因此，链表较顺序表的插入和删除操作更加方便、高效。为了便于实现各种运算，若无特殊说明，均采用带头结点的链表。4栈栈（Stack）是限定仅在表的一端进行插入或删除操作的线性表。通常把允许插入和删除操作的一端称为栈顶（Top），而另一端称为栈底（Bottom）。表为空时称为空栈。在栈上的主要运算是入栈和出栈。栈中元素如果按a1，a2，an的顺序进栈，则出栈顺序为an，an-1，a1。因此，栈又称为“后进先出”（Last In First Out）的线性表，简称LIFO表。同线性表相似，栈也有顺序栈和链栈两种存储结构。顺序栈易产生“上溢”现象，而链栈不容易产生。另外，注意对栈的操作只能在栈顶进行。5队列队列（Queue）是限定只能在表的一端进行插入，在表的另一端进行删除的线性表。通常把允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）。队列中元素如果按a1，a2，an的顺序进队，则出队的顺序仍为a1，a2，an。因此，队列又称为“先进先出”（First In First Out）的线性表，简称FIFO表 。队列也有顺序队列和链队列两种存储结构。在顺序队列中，为避免“假满”现象，一般采用循环队列（即首尾相接）。链队列会因为队满而产生“上溢”现象。第4章 串1概念和术语串（String）（或字符串）：是由零个或多个字符组成的有限序列。一般记为s= “aa a” (n0)其中，s是串的名，用双引号括起来的字符序列是串的值。串的长度：串中字符的个数n。子串和主串：串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。空串：不包含任何字符的串，表示为“”。空格串：由一个或多个空格字符组成的串。例如：“ ”。2串的基本操作（1）用串变量赋值assign(s,t)和用串常量赋值create(s,ss)（2）判等函数equal(s, t）（3）求长函数length(s)（4）连接函数concat(s,t)（5）求子串函数substring(s, pos , len)（6）定位函数index(s,t) （7）置换函数replace(s,t,v) （8）插入子串insert(s,pos,t)（9）删除子串delete(s,pos,k)（10）串的复制copy(s,t)3串的顺序存储结构（顺序串）串的顺序存储方式类似于线性表的顺序存储方式，其存储结构用C语言描述为：typedef struct strnode char datamaxlen;int len;SeqString; /定义顺序串类型第5章 数组和广义表1多维数组的顺序存储结构对于多维数组，有两种存储方式：一是以行为主序（或先行后列）的顺序存放，如BASIC、PASCAL、C等程序设计语言中用的是以行为主的顺序分配，即一行分配完了接着分配下一行。另一种是以列为主序（先列后行）的顺序存放，如FORTRAN语言中，用的是以列为主序的分配顺序，即一列一列地分配。以行为主序的分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变，从右向左，最后是左下标。以列为主序分配的规律是：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变，从左向右，最后是右下标。不论按何种方式存储，只要确定了数组的首地址以及每个数组元素所占用的单元数，就可以将数组元素的存储地址表示为其下标的线性函数。设有mn二维数组Amn，以“以行为主序”的分配为例，按照元素的下标确定其地址的计算方法如下。设数组的基址为LOC(a11)，每个数组元素占据L个地址单元，计算aij 的物理地址的函数为：LOC(aij) = LOC(a11) + ( (i-1)*n + j-1 ) * L同理，对于三维数组Amnp，即mnp数组，对于数组元素aijk其物理地址为：LOC(aijk)=LOC(a111)+( ( i-1) *n*p+ (j-1)*p +k-1) )*L注意：在C语言中，数组中每一维的下界定 义为0，则：LOC(aij) = LOC(a00) + ( i*n + j ) * L2特殊矩阵压缩存储的意义在很多科学计算与工程应用中，经常要使用矩阵的概念。矩阵具有与数组相似的性质，如元素数目固定、元素按下标关系有序地排列，所以在编程时可以利用二维数组来存储矩阵，也可以利用程序设计语言中的各种矩阵运算。在某些情况下，特别是在数值分析中，经常会出现一些阶数很高的矩阵，其中含有许多值相同的元素或零元素，如三角矩阵、对称矩阵、稀疏矩阵等，从节约存储空间的角度考虑，此时若用二维数组存储会造成空间的极大浪费。为了节省存储空间，可以对这类矩阵进行压缩存储。即为对多个相同值的元素只分配一个存储空间，而对零元素可以不分配空间。3对称矩阵压缩存储的方法对称矩阵的特点是：在一个n阶方阵中，有aij=aji，其中1i , jn。对称矩阵关于主对角线对称，因此只需存储上三角或下三角部分即可。对于对称矩阵中的任意元素aij，若令I=max(i,j)，J=min(i,j)，则将上面两个式子综合起来得到：k=I*(I-1)/2+J-1。给出对称矩阵A中任意元素aij，依据它的下标i和j就可由上述对应关系式确定其在数组M中的位置K，因此aij的地址可由下式计算。Loc(aij)=Loc(MK)=Loc(M0)+K*L=Loc(M0)+I*(I+1)/2+J*L其中：L为每个数据元素所占的存储单元长度。 I=max(i,j)。 J=min(i,j)。 K=I*(I+1)/2+J。4三角矩阵压缩存储的方法形如图的矩阵称为三角矩阵，其中c为某个常数。其中下面图(a)为下三角矩阵：主对角线以上均为同一个常数；(b)为上三角矩阵，主对角线以下均为同一个常数；下面讨论它们的压缩存储方法。图4-1 三角矩阵3 c c c c6 2 c c c4 8 1 c c74 6 0 c82 9 5 7(a) 下三角矩阵3 4 8 1 0c 2 9 4 6c c 1 5 7c c c 08c c c c 7(b) 上三角矩阵三角矩阵中的重复元素c可以共享一个存储空间，其余的元素有n(n+1)/2个，因此可压缩存储到向量sa0.n(n+1)/2中，c存放在向量的最后一个分量中，排列时以行序为主。a和sak的对应关系是：k=i*(i-1)/2+j-1 当ijn*(n+1)/2-1 当ij上三角矩阵：5稀疏矩阵及其压缩存储的特点设m*n矩阵中有t个非零元素且t0）个互不相交的子集：T1，T2， ，Tn，其中每个子集本身又是一棵树（称之为子树），每一棵子树的根xi（1in）都是根结点root的后继，树T1，T2， ，Tn称为根的子树。2掌握树的基本概念结点的度（Degree）：是指结点拥有的子树的数目。叶子或终端结点：是指度为0的结点。非终端结点或分支结点：是指度不为0的结点。树的度：是指树内各结点的度的最大值。孩子（Child）和双亲（Parent）：某个结点的子树的根称为该结点的孩子，相应的，该结点称为其孩子的双亲。兄弟：同一个双亲的孩子结点互为兄弟。结点的层次：规定根所在的层次为第1层，根的孩子在第二层，依次类推。树的深度或高度：树中结点最大的层数。有序树：是指树中结点的各子树从左至右是有次序的，否则称为无序树。森林：是指n（n0）棵互不相交的树的集合。3理解二叉树的递归定义及其与树的区别二叉树（Binary Tree）是结点的有限集合，这个集合或者为空，或者是由一个根结点和两棵互不相交的分别称为左子树和右子树的二叉树组成。二叉树中的每个结点至多有两棵子树，且子树有左右之分，次序不能颠倒。二叉树是一种重要的树型结构，但二叉树不是树的特例。二叉树的 5 种形态分别为：空二叉树，只有根结点的二叉树，根结点和左子树，根结点和右子树，根结点和左右子树。二叉树与树的区别：二叉树中每个结点的孩子至多不超过两个，而树对结点的孩子数无限制；另外，二叉树中结点的子树有左右之分，而树的子树没有次序。4掌握满二叉树和完全二叉树的概念满二叉树（Full Binary Tree）和完全二叉树（Complete Binary Tree），是两种特殊形态的二叉树。一棵深度为k且有2k -1个结点的二叉树称为满二叉树。深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。完全二叉树的特点是：（1）只允许最后一层有空缺结点且空缺在右边，即叶子结点只能在层次最大的两层上出现；（2）对任一结点，如果其右子树的深度为j，则其左子树的深度必为j或j+1。5理解二叉树的性质已知二叉树的深度h可求出该二叉树拥有的最多结点数，已知结点数n可求出对应树或二叉树的最大和最小高度。性质1在二叉树的第i层上最多有2i-1个结点（i1）。性质2深度为k的二叉树最多有2k -1个结点（k1）。性质3对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0= n21。性质4具有n个结点的完全二叉树的深度为+1。性质5如果对一棵有n个结点的完全二叉树（其深度为+1，其中k为不大于的最大整数）的结点按层序编号（编号方法为从第1层到最后一层，每一层从左到右），则对任一结点i（1in），有（1）如果i=1，则结点i是二叉树的根，无双亲；如果i1，则其双亲是第个结点。（2）如果2in，则结点i无左孩子（即结点i为叶子结点）；否则其左孩子是第2i个结点。（3）如果2i+1n，则结点i无右孩子；否则其右孩子是第2i+1个结点。6二叉树中结点的编号规则和对应的顺序存储结构顺序存储二叉树的具体方法是：在一棵具有n个结点的完全二叉树中，从根结点开始编号为1，自上到下，每层自左至右地给所有结点编号，这样可以得到一个反映整个二叉树结构的线性序列；然后将完全二叉树上编号为i的结点依次存储在一维数组al . n中下标为i的元素中。7二叉树的链接存储结构及存储结点的类型定义链式存储是使用链表来存储二叉树中的数据元素，链表中的一个结点相应地存储二叉树中的一个结点。常见的二叉树的链式存储结构有两种：二叉链表和三叉链表。二叉链表是指链表中的每个结点包含两个指针域和一个数据域，分别用来存储指向二叉树中结点的左右孩子的指针及结点信息。三叉链表是指链表中的每个结点包含三个指针域和一个数据域，相比二叉链表多出的一个指针域则用来指向该结点的双亲结点。不论哪种链表，头指针都指向二叉树的根结点。在含有n个结点的二叉链表中，共有2n个指针域，但实际有效的指针数等于二叉树中的分支数（即n-1），所以共存在n+1个空的指针域。8掌握二叉树的先序、中序、后序遍历的递归算法和非递归算法。9能够根据先序+中序、后序+中序的遍历序列确定一棵二叉树，并理解为什么先序+后序不能唯一确定一棵二叉树。10掌握线索二叉树的定义及存储结构，会画出先序、中序和后序线索二叉树或相应的线索链表。12掌握遍历中序线索二叉树的规则及算法。13掌握树的三种存储结构：双亲表示法、孩子表示法、孩子/兄弟表示法，掌握这三种存储方法的特点，并且能够画出指定树的存储结构图。14理解二叉树与树或森林转换的目的，掌握树和二叉树之间的相互转换，掌握森林和二叉树之间的相互转换。15掌握树的先根、后根和按层遍历的过程。16掌握森林的先根、后根遍历。17掌握路径、路径长度、结点的权、结点的带权路径长度、树的带权路径长度的概念。路径：若在树中存在着一个结点序列k1，k2，kj，使得ki是ki+1的双亲（1ij），则此结点序列称为从k1到kj的路径。路径长度：从k1到kj所经过的分支数称为这两点之间的路径长度，它等于路径上的结点数减1。结点的权：在许多应用中，常常将树中的某个结点赋上一个具有某种意义的数值，这个和某个结点相关的数值称为该结点的权或权值。结点的带权路径长度：是指从树根到该结点之间的路径长度与结点的权值的乘积。树的带权路径长度：是指树中所有叶子结点的带权路径长度之和，通常记为WPL=。其中n表示叶子结点的个数，Wi表示叶子结点Ki的权值，Li表示根结点到Ki的路径长度。18掌握哈夫曼树的概念。哈夫曼树（Huffman Tree）：又称为最优二叉树，它是n个带权的叶子结点构成的所有二叉树中带权路径长度WPL最小的二叉树。19掌握哈夫曼树的构造方法，即根据一组给定的权值构造相应的哈夫曼树。20理解哈夫曼编码的含义，能够根据实际问题构造哈夫曼编码。第7章 图1基本概念及术语图G：由两个集合V(G)和E(G)所组成，记作G(V，E)，其中V(G)是图中顶点的非空有限集合，E(G)是图中边的有限集合。图6-1 图示例123G14321G27654321G3有向图(Digraph)：如果图中每条边都是有向的即每条边在图示时都用箭头表示方向，则称此图为有向图。有向图的边也称为弧，如图6-1中G1是有向图，它由V(G1)和E(G1)组成。V(G1)=V1,V2,V3，(G1)=,无向图(Undigraph)：如果图中每条边都是顶点无序对，则称为无向图。无向边用圆括号括起的两个相关顶点来表示。在无向图中，(V1,V2)和(V2,V1)是表示同一条边。如图6-1所示，G2和G3都是无向图。其中，V(G2)=V1,V2,V3,V4E(G2)=(V1,V2),(V1,V3),(V2,V3),(V2,V4),(V3,V4)V(G3)=V1,V2,V3,V4,V5,V6,V7E(G3)=(V1,V2),(V1,V3),(V2,V4),(V2,V5),(V3,V6),(V3,V7)无向完全图和有向完全图：若一个无向图有n个顶点，而每一个顶点与其他n-1个顶点之间都有边，这样的图称之为无向完全图。即共有n(n1)2条边。类似地，在有n个顶点的有向图中，若有n(n1)条弧，即任意两顶点之间都有双向相反的两条弧连接，则称此图为有向完全图。子图：设有两个图A和B且满足条件：V(B)(A)且E(B)E(A)则称B是A的子图。路径：在图中，从顶点p到q的一条路径是顶点序列(Vp, Vi1, Vi2, , Vin, Vq)且(Vp,Vi1),(Vi1,Vi2), , (Vin,Vq)是E(G)中的边，路径上边的数目称之为该路径长度。对于有向图，其路径也是有向的，路径由弧组成。简单路径：如果一条路径上所有顶点除其起始点和终止点外彼此都是不同的，则称该路径是简单路径。回路和简单回路：在一条路径中，如果其起始点和终止点是同顶点，则称其为回路。简单路径相应的回路称为简单回路。连通图和强连通图：在无向图G中，若从Vi到Vj有路径，则称Vi和Vj是连通的。若G中任意两顶点都是连通的，则称G是连通图。对于有向图而言，若G中每一对不同顶点Vi和Vj之间都有Vi到Vj和Vj到Vi的路径，则称G为强连通图。度、入度和出度：若(Vi, Vj)是E(G)中的一条边，则称顶点Vi和Vj是邻接的并称边(Vi, Vj)依附于顶点Vi和Vj。所谓顶点的度，就是依附于该顶点的边数。在有向图中，以某顶点为头，即终止于该顶点的弧的数目称为该顶点的入度；以某顶点为尾，即起始于该顶点的弧的数目称为该顶点的出度。该顶点的入度和出度之和称为该顶点的度。203010342021270201310图6-2 网G4 网G5 有向网若图G中每一条边都有一个对应的数，则称G为网。这些边上的数字称为权，它可以表示两顶点之间的距离或所花费的代价。类似地，边上带权的有向图称为有向网。如在图6-2中G4是一个网，而图G5则是一个有向网。2图的存储结构常用的存储结构有邻接矩阵和邻接表。（1）邻接矩阵表示法设G(V，E)是有n(n1)个顶点的图。则G的邻接矩阵是按如下定义的n阶方阵：0其它1当（i,Vj）E或E时costi,j= 0 1 1 01 0 1 11 1 0 10 1 1 0A2=A1=0 1 10 0 10 0 0 例如，图6-1中G1，2的邻接矩阵分别表示为A1、A2，矩阵的行列号对应于图6-1中结点的序号。由邻接矩阵的定义可知，无向图的邻接矩阵必定是对称阵；有向图的邻接矩阵不一定是对称的。 根据邻接矩阵，很容易判定任意两个顶点之间是否有边相连。求各顶点的度也是非常容易的。对于无向图，顶点Vi的度就是邻接矩阵中第i行(或第j列)上非零元的个数，即。对于有向图，第i行中非零元的个数为顶点Vi的出度，而第i列上的非零元个数为顶点Vi的入度。（2）邻接表表示法图的邻接链表存储结构是一种顺序分配和链式分配相结合的存储结构括两个部分：一部分是向量，另一部分是链表。邻接链表中的表头部分是向量，用来存储n个表头结点。向量的下标指示顶点的序号。例如，对于图6-1中G1和G2，其邻接链表如图6-3所示。在无向图的邻接表中顶点vi的度就是第i个链表中结点的个数。在有向图中，第i个链表的结点数仅是vi的出度，求vi的入度，必须查遍n个链表才能得出。(a) G1的邻接表123332(b) G2的邻接表图6-3 邻接表312341244332213图的遍历给定一个无向连通图G，G(V，E)，当从V(G)中的任一顶点v出发，去访问图中其余顶点，使每个顶点仅被访问一次。这个过程叫做图的遍历。通常有两种遍历图的方法，种是深度优先搜索法，另种为广度优先搜索法。（1）深度优先搜索设有无向连通图G(V，E)，从V(G)中任一顶点v出发深度优先搜索遍历图的步骤是：先访问指定顶点V1，然后访问与该顶点V1相邻的顶点V2，再从V2出发，访问与V2相邻且未被访问过的任意顶点V3，然后从顶点V3出发，重复上述过程，直到一个所有邻接点都被访问过的顶点为止，然后回溯到此顶点的直接前趋，从这里出发再继续访问。显然搜索是一个递归过程。（2）广度优先搜索设无向图G(V，E)是连通的，从V(G)中的任一顶点V1出发，广度优先搜索遍历图的步骤是：首先访问指定的起始顶点V1，从V1出发，依次访问与V1相邻的未被访问过的顶点W1，W2，W3，Wt，然后依次从W1，W2，W3，Wt出发，重复上述访问过程，直到所有顶点都被访问过为止。在广度优先搜索过程中，访问某个顶点之后，要将这个顶点保存起来，以备后面访问这个顶点的邻接点。由搜索这个过程可知，保存的信息应该组织成一个队列。4生成树和最小生成树无向图的连通分量：无向图的连通分量是图的一个极大连通子图。如图6-7 (a)有两个连通分量，分别为图6-7(b)和(c)。而图6-7(d)不是图6-7(a)的连通分量，因为它虽是图6-7(a)的连通子图，却不是极大连能子图，只有加上顶点3后，才构成极大连通子图。无向连通图只有一个连通分量，即是图本身。最小生成树：设图G是一个连通网，G上的一棵各边权值之和最小的带权生成树，称为G的最小生成树。构造最小生成树的算法有：普里姆算法和克鲁斯卡尔算法。(b)V5V4(a)(d)(c) (a)无向图; (b),(c)是图(a)的两个连通分量; (d)非连通分量图6-7 无向图的连通分量V3V2V1V0V2V1V0V3V2V1V0V5V45普里姆（Prim）算法假设N= ( V, E )是连通图，TE是N上最小生成树中边的集合。算法从U=u0( u0)，TE=开始，重复执行下述操作：在所有uU, vV-U的边(u, v)中找一条代价最小的边u0, v0并入集合TE，同时v0并入U，直到U=V为止。此时TE中必有n-1条边，则T= (V, TE)为N的最小生成树。6鲁斯卡尔（Kruskal）算法克鲁斯卡尔算法是从另一途径求网的最小生成树。假设连通网N= ( V, E )，则令最小生成树的初始状态为只有n个顶点而无边的非连通图T(V, )，图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依次类推，直至T中所有顶点都在同一连通分量上为止。7拓扑排序（1）AOV网：在有向图中以顶点表示“活动”，用有向边表示“活动”之间的优先关系，这样的有向图称为以顶点表示“活动”的网(Activity On Vertex Network)，简称AOV网。（2）拓扑排序的方法对于一个AOV网，构造其所有顶点的线性序列，使此序列不仅保持网中各顶点间原有的先后次序，而量使原来没有先后次序关系的顶点之间也建立起人为的先后关系。这样的序列称为拓扑有序序列。构造AOV网的拓扑有序序列的运算称为拓扑排序。某个AOV网，如果它的拓扑有序序列被构造成功，则该网中不存在有向回路，其各子工程可按拓扑有序序列的次序进行安排。一个AOV网的拓扑有序序列并不是唯一的。对AOV网进行拓扑排序的步骤是： 第一步：在网中选择一个没有前趋的顶点且输出之。第二步：在网中删去该顶点，并且删去从该顶点发出的全部有向边。第三步：重复上述两步，直到网中不存在没有前趋的顶点为止。这样操作结果有两种；一种是网中全部顶点均被输出，说明网中不存在有向回路；另一种是网中顶点未被全部输出，剩余的顶点均有前趋顶点，说明网中存在有向回路。8掌握关键路径的概念及确定关键路径的算法若在带权有向图G中，以顶点表示事件，边表示活动，权表示活动持续的时间，则此带权有向图称为用边表示活动的网(Activity On Edge net work)，简称AOE网。由于整个工程只有一个开始点和一个完成点，故在正常情况下，在这种工程图中只有一个入度为0的顶点(称为源点)和一个出度为0的顶点(称为汇点)。从源点到汇点之间的长度最长的路径称为关键路径。9掌握最短路径的概念及确定最短路径的算法所谓的最短路径是指对所经过的边的值之和为最小的路径。本章给出两个算法：一个是求从某个源点到其他顶点的最短路径，另一个是求每对顶点间的最短路径。确定单源最短路径可采用迪杰斯特拉（ijkstra）算法。确定所有顶点之间的最短路径有两种方法：一种是每次以一个顶点为源点，重复执行迪杰斯特拉算法n次，时间复杂度为O(n3)；另一种是弗洛伊德(Floyd)算法，时间复杂度也是O(n3)，但形式更简单。第9章 查找1查找的基本概念查找也称为检索。进行查找运算的数据元素通常是同一数据类型的数据元素或记录，由它们构成的集合又称为查找表。查找表分为静态查找表和动态查找表。静态查找表：仅对查找表进行查找操作，即查找关键字等于给定值的数据元素是否在查找表中或检索其属性，查找前后不能改变表。动态查找表：对查找表除进行查找操作外，可能还要向表中插入数据元素，或删除表中数据元素的表。关键字、主关键字和次关键字：查找表中区别不同记录的数据项的数据元素称为关键字。若此关键字可以惟一的标识一个记录，则称此关键字为主关键字（Primary Key）。反之，称用以识别若干记录的关键字为次关键字（Secondary Key）。查找（Searching）是根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。若表中存在一个这样的记录，则称查找成功，反之，查找不成功。注意：不同的查找方法，不同的查找表存储结构，具有不同的查找效率。平均查找长度，即在查找成功情况下的平均比较次数。平均查找长度的计算公式为：ASL=其中，n表示查找表的长度，即表中所包含的数据元素的个数，Pi是查找第i个元素的概率，一般认为查找每个元素的概率相等。Ci是查找第i个元素时，同给定值K的比较次数。在查找每个元素等概率的情况下，则平均查找长度的计算公式变为：ASL=其对应的时间复杂度为：O（n）。2线性表查找线性表查找是指进行查找运算的查找表所采用的存储结构是线性的。（1）顺序查找最简单的查找技术是顺序查找（Sequential Search），这种查找技术适用于基本线性表结构文件，如顺序存储或链式存储的基本线性表结构文件。顺序查找的算法思想是：从表的末端开始，依次将记录的关键字与给定值K进行比较，若出现相等情况，则查找成功；若直至第一个记录仍未发现相等，则查找失败。在顺序存储和链式存储两种方法中，由于每个元素在查找表中位置不同，查找成功时的比较次数也不同。在不等概率的条件下，为了减少整个算法查找的次数，可以把查找概率大的数据元素放在查找表的靠前的位置。（2）折半查找折半查找（Binary Search）也叫二分查找。算法思想为：在有序表中，取中间元素作为比较对象，若给定值与中间元素的关键字相等，则查找成功；若给定值小于中间元素的关键字，则在中间元素的左半区继续查找；若给定值大于中间元素的关键字，则在中间元素的右半区继续查找。不断重复上述查找过程，直到查找成功，或所查找的区域无数据元素，则查找失败。从折半查找过程看，可用二叉树来描述，称这个描述查找过程的二叉树为判定树。以树高为k的满二叉树（n=2k+1）为例。假设表中每个元素的查找是等概率的，即Pi=1/n，则树的第i层有2i-1个结点，因此，折半查找的平均查找长度为：3树表查找（1）二叉排序树二叉排序树（Binary Sort Tree）又称二叉查找树（Binary Search Tree），它或者是一棵空树，或者是一棵具有如下性质的非空二叉树：若它的左子树非空，则左子树上的所有结点的关键字的值均小于根结点的值。若它的右子树非空，则右子树上的所有结点的关键字的值均大于根结点的值。左右子树本身又各是一棵二叉排序树。二叉排序树的查找过程为：（i）若查找树为空，查找失败。（ii）查找树非空，将给定值k与查找树的根结点关键字比较。（iii）若相等，查找成功，结束查找过程，否则，继续查找。（iv）当给定值k小于根结点关键字，查找将在左子树上继续进行，转（i）。（v）当给定值k大于根结点关键字，查找将在右子树上继续进行，转（i）。算法实现以二叉链表作为二叉排序树的存储结构来实现。二叉排序树的运算（i）二叉排序树的创建（ii）二叉排序树的插入算法（iii）二叉排序树的删除运算算法分析在二叉排序树上查找关键字等于给定值k的过程，正好经过了一条从树根到该结点的路径。与关键字k比较的次数试该路径的长度加1。因此，查找的次数不会超过树的深度。由于二叉排序树的形状取决于输入的关键字序列，因此，对于同一组关键字，如果输入顺序不一样，所得到的二叉排序树也不一样。最好的情况是二叉排序树的形态和折半查找的判定树相同。（2）平衡二叉树平衡二叉树的定义平衡二叉树（Balanced Binary Tree 或 Height-Balanced Tree）又称AVL树。它或者是一棵空树，或者是具有下列性质的二叉排序树：它的左子树和右子树都是平衡二叉树，且左子树和右子树高度之差的绝对值不超过1。平衡二叉树的调整（i）左单旋转（又称RR型）（ii）右单旋转（又称LL型）（iii）左后右双向旋转（又称LR型）（iv）先右后左双向旋转（又称RL型）平衡二叉树的算法4哈希表查找（1）哈希表的定义把关键字与存储位置之间的对应关系，称之为哈希函数。每个关键字通过哈希函数得到一个存储位置，这个存储位置称为哈希地址。一组关键字通过哈希函数得到一段有限的连续地址，这段地址是所有关键字的一个映像，称为哈希表。哈希表又称为散列表或杂凑表。（2）哈希函数的构造常用的构造哈希函数的方法有：直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法。实际工作中需视不同的情况采用不同的哈希函数。通常，考虑的因素有：计算哈希函数所需时间（包括硬件指令的因素）；关键字的长度；哈希表的大小；关键字的分布情况；记录的查找频率。（3）冲突处理方法假设哈希表的地址集为0（n-1），冲突是指由关键字得到的哈希地址为j（0jn-1）的位置上已存有记录，则“处理冲突”就是为该关键字的记录找到另一个“空”的哈希地址。通常的处理冲突的方法有下列几种：开放定址法：线性探测法和二次探测法再哈希法拉链法建立一个公共溢出区（4）查找及分析在哈希表上进行查找的过程和哈希造表的过程基本一致。给定值k，根据造表时设定的哈希函数求得哈希地址，若表中此位置上没有记录，则查找不成功；否则比较关键字，若和给定值相等，则查找成功；否则根据造表时设定的处理冲突的方法找“下一个地址”，直至哈希表中某个位置为“空”或者表中所填记录的关键字等于给定值时为止。在一般情况下，处理冲突方法相同的哈希表，其平均查找长度依赖于哈希表的装填因子。哈希表的装填因子定义为： = 表中填入的记录数/哈希表的长度表示哈希表的装满程度。越小，发生冲突的可能性就越小，平均查找长度也小，但空间的浪费加大；反之，越大，表中已填入的记录越多，再填记录时，发生冲突的可能性就越大，则查找时，给定值需与之进行比较的关键字的个数也就越多。第10章 内部排序1基本概念排序：是计算机程序设计中一种重要操作，其功能是对一个数据元素集合或序列重新排列成一个按数据元素某个项值有序的序列。作为排序依据的数据项称为关键字。排序的确切定义如下：输入：n个记录R1，R2，Rn，其相应的关键字分别为K1，K2，Kn。输出：Ri1，Ri2，Rin，使得Ki1Ki2Kin（或Ki1Ki2Kin）。文件：文件是由一组记录组成的。记录则是由若干个数据项（或域）组成。其中有一项可用来标识一个记录，称为关键字项，该数据项的值称为关键字（Key）。稳定性：若对任意的数据元素序列使用某个排序方法，对它按关键字进行排序，若相同关键字元素间的位置关系排序前与排序后保持一致，称此排序方法是稳定的；而不能保持一致的排序方法则称为不稳定的。排序的分类：（1）按是否涉及数据的内、外存交换分类。在排序过程中，若整个文件都是放在内存中处理，排序时不涉及数据的内、外存交换，则称之为内部排序（简称内排序）。适合不太大的元素序列；反之，若排序过程中要进行数据的内、外存交换，则称之为外部排序。适合大元素序列。（2）按排序策略分类。可以分为五类：插入排序、选择排序、交换排序、归并排序和基数排序。2插入排序（1）直接插入排序直接插入排序方法的算法思想是：仅有一个记录的表总是有序的，因此，对n个记录的表，可从第二个记录开始直到第n个记录，逐个向有序表中进行插入操作，从而得到n个记录按关键字有序的表。算法的时间复杂度为O(n2)，需要一个辅助空间，是就地排序。直接插入排序是稳定排序。（2）折半插入排序折半插入排序的算法思想是：向有序表中插入一个记录，在有序表中确定插入位置，可以不断二分有序表来确定插入位置，即一次比较，通过待插入记录与有序表居中的记录按关键字比较，将有序表一分为二，下次比较在其中一个有序子表中进行，将子表又一分为二。这样继续下去，直到要比较子表中只有一个记录时，比较一次便确定了插入位置。确定插入位置所进行的折半查找，仅减少了关键字间的比较次数，而记录的移动次数不变，故时间复杂度仍为O(n2)。是一个稳定的排序方法。（3）希尔排序希尔排序的算法思想是：选择一个步长序列t1，t2，tk，其中titj，tk=1。按步长序列个数k，对序列进行k趟排序。每趟排序根据对应的步长ti，将待排序列分隔成若干长度为m的子序列，分别对各子表进行直接插入排序。仅步长因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。希尔排序算法分析很难， 关键字的比较次数与记录移动次数依赖于步长因子序列的选取，特定情况下可以准确估算出关键字的比较次数和记录的移动次数。希尔排序是不稳定排序，它需要一个辅助空间，即就地排序。希尔排序记录的比较次数和移动次数都比直接插入排序时要少，n越大时，效果越明显。3交