自考02142数据结构导论密训高频考点重点汇总.pdf

1、1 1/1515第一章 概论第一章 概论知识点名称知识点名称内容内容引言引言1.数据结构指一组相互之间存在一种或多种特定关系的数据的组织方式和它们在计算机内的存储方式，以及定义在该组数据上的一组操作。2.算法+数据结构=程序数据、数据元素和数据项数据、数据元素和数据项1.数据：所有被计算机存储、处理的对象。2.数据元素：数据的基本单位，是运算的基本单位。常常又简称为元素。3.数据项是数据的不可分割的最小标识单位。在数据库中数据项又称为字段或域。4.从宏观上看，数据、数据元素和数据项实际上反映了数据组织的三个层次，数据可由若干个数据元素组成，而数据元素又可由若干个数据项组成。5.数据结构是相互之

2、间存在一种或多种特定关系的数据元素的集合。它包括数据的逻辑结构、数据的存储结构和数据的基本运算。数据的逻辑结构数据的逻辑结构1.数据的逻辑结构：与数据元素本身的形式、内容、相对位置、个数无关。2.集合：任意两个结点之间都没有邻接关系，组织形式松散。3.线性结构：结点按逻辑关系依次排列形成一条“链”，结点之间一个一个依次相邻接。4.树形结构：具有分支、层次特性，其形态像自然界中的树，上层的结点可以和下层多个结点相邻接，但下层结点只能和上层的一个结点相邻接。5.图结构：最复杂，其中任何两个结点都可以相邻接。数据的存储结构数据的存储结构1.数据的逻辑结构在计算机中的实现称为数据的存储结构。2.顺序存

3、储方式：指所有存储结点存放在一个连续的存储区里。利用结点在存储器中的相对位置来表示数据元素之间的逻辑关系。3.链式存储方式：指每个存储结点除了含有一个数据元素外，还包含指针，每个指针指向一个与本结点有逻辑关系的结点，用指针表示数据元素之间的逻辑关系。4.除了上述两种存储方式之外，还有索引存储方式和散列存储方式。但主要的存储方式是：顺序存储方式和链式存储方式。运算运算1.运算是指在某种逻辑结构上施加的操作，即对逻辑结构的加工。2.运算包括：建立、查找、读取、插入和删除等。3.线性表、栈和队列中的元素具有相同的逻辑结构（即线性结构），但有不同的运算集，它们是不同的数据结构。算法分析算法分析1.正确

4、性：能正确地实现预定的功能，满足具体问题的需要。2.易读性：易于阅读、理解和交流，便于调试、修改和扩充。3.健壮性：即使输入非法数据，算法也能适当地做出反应或进行处理，不会产生预料不到的运行结果。4.时空性：指该算法的时间性能（或时间效率）和空间性能（或空间效率），前者是算法包含的计算量，后者是算法需要的存储量。时间复杂度时间复杂度1.常见的时间复杂度的比较：O（1）O（log2n）O（n）O（n2）O（n3）O（n4）next。某带有头结点的单链表的头指针为head，判断该单链表为非空的条件是 head-next!=NULL。线性表的基线性表的基本运算在单本运算在单链表上的实链表上的实现现1

5、.初始化（1）假设单链表的类型定义如下：typedefstruct node DataType data;3 3/1515struct node *next;node ，*LinkList;算法 InitiateLinkList（）实现单链表的初始化：LinkListInitiateLinkList（ ） /建立一个空的单链表LinkList head; /头指针head=malloc（sizeof（node）; /动态构建一个结点，并定义为头结点head-next=NULL;return head;/空表由一个头指针 head 和一个头结点组成。head 指向新创建的结点，即头结点。一个空单

6、链表仅有一个头结点，它的指针域为 NULL。（2）在带头结点的单链表 L 中，第一个数据元素结点的指针为 L-next。（3）设有一个单链表，若结点的指针域为 next，则指针 p 所指的结点为最后一个结点的条件是p-next=NULL。工作指针 p-next 为 NULL 时，说明已经走到了表的尾部，这时已完成对所有结点的访问。2.插入 p 指向的新结点的操作（1）设 r 指向单链表的最后一个结点，要在最一个结点之后插入 s 所指的结点，需执行的语句序列是r-next=s;r=s;r-next=NULL。（2）将一个由指针 q 指向的结点插在单链表中由指针 p 所指向的结点之后的操作是：q-

7、next=p-next;p-next=q;。3.删除*p 结点的操作在一个单链表中，已知指针 q 指向指针 p 所指结点的前驱结点，则删除*p 结点的操作语句是q-next=p-next。循环链表循环链表1.在单链表中，如果让最后一个结点的指针域指向第一个结点可以构成循环链表。（1）只有头指针 head1）判断 P 所指结点为尾结点的条件：p-next=head2）判断指针 P 所指结点为首结点的条件：p=rear-next-next3）判断链表是否为空的条件：head-next=head4 4/1515（2）有头指针 head 和尾指针 rear说明：rear-next 指向头结点 head

8、。在 带有 头结 点 的循 环 链表 中， 尾 指针 为 rear ， 判断 指针 P 所 指结 点为 首 结点 的 条件是p=rear-next-next。（3）只有尾指针 rear1）删除表首结点的操作可表示为：p=rear-next-next;rear-next-next=p-next;free（p）;2） 已知尾指针的单向循环链表中， 在第一个结点后面插入一个新结点， 该算法的时间复杂度为 O （1） 。双向循环链双向循环链表表1.每个结点有两个指针，next 指针指向直接后继结点；prior 指针指向直接前驱结点。2.带头结点的双向循环链表 L 为空的条件：（L-next=L）&（L

9、-prior=L）。3.删除（1）设 p 指向待删结点，删除*p 的操作：p-prior-next=p-next;/语句p-next-prior=p-prior;/语句free（p）;（2）这两个语句的执行顺序可以颠倒。4.插入在 p 所指结点的后面插入一个新结点*t 的操作:t-prior=p;t-next=p-next;5 5/1515p-next-prior=t;p-next=t;顺序实现与顺序实现与链接实现的链接实现的比较比较顺序表时间复杂度单链表时间复杂度按位置查找运算O（1）O（n）定位运算O（n）O（n）插入、删除运算O（n）O（n）第三章第三章 栈、队列和数组栈、队列和数组知识

10、点名称知识点名称内容内容栈、队列和栈、队列和数组数组1.栈和队列可看作是特殊的线性表。它们是运算受限的线性表。栈和队列也同样有两种存储结构（顺序存储结构和链式存储结构）。2.栈和队列可看作是特殊的线性表。（1）函数的嵌套调用和程序递归的处理都是用栈来实现的。（2）操作系统中进程调度、网络管理中的打印服务等都是用队列来实现的。栈的基本概栈的基本概念念1.栈：这种线性表上的插入和删除运算限定在表的某一端进行。允许进行插入和删除的一端称为栈顶，另一端称为栈底。不含任何数据元素的栈称为空栈。2.栈的修改原则：后进先出，栈又称为后进先出线性表，简称后进先出表。3.栈的基本运算：（1）初始化 InitSt

11、ack（S）：构造一个空栈 S；（2）判栈空 EmptyStack（S）：若栈 S 为空栈，则结果为 1，否则结果为 0；（3）进栈 Push（S，x）：将元素 x 插入栈 S 中，使 x 成为栈 S 的栈顶元素；（4）出栈 Pop（S）：删除栈顶元素；（5）取栈顶 GetTop（S）：返回栈顶元素。栈的顺序实栈的顺序实现现1.当空栈，栈顶下标值 top=0，如果此时做出栈运算，则产生“下溢”。当栈中的数据元素已经填满了，如果再进行进桟操作，会发生“上溢”。2.初始化IntInitStack（SeqStk *stk）stk-top=0;return1;3.判栈空IntEmptyStack（Se

12、qStk *stk）/若栈为空，则返回值 1，否则返回值 0if（stk-top=0）return 1;else return 0;6 6/15154.进栈Int Push（SeqStk *stk，DataType x）/若栈未满，元素 x 进栈 stk 中，否则提示出错信息if（stk-top=maxsize-1）/判断找是否满error（“栈已满”）;return 0;elsestk-top+;/栈未满，top 值加 1stk-datastk-top=x;/元素 x 进桟return 1;5.出栈Int PopSeqStk *stk）if（EmptyStack（stk）/判断是否下溢（栈空

13、）error（“下溢”）;return 0;else/未下溢，栈顶元素出栈stk-top-;/top 值减 1return 1;也可以理解为：原栈顶的下一个结点成为新的栈顶，即 top=top-next;6.取栈顶元素DataType GetTop（SeqStk*stk）/取栈顶数据元素，栈顶数据元素逋过参数返回if（EmptyStack（stk）return NULLData;/栈空，返回 NULLDataelsereturn stk-datastk-top;/返回栈顶数据元素栈的链接实栈的链接实现现1.栈的链接实现称为链栈，链栈可以用带头结点的单链表来实现。LS 指向链表的头结点，首结点是

14、栈顶结点，LS-next 指向栈顶结点，尾结点为栈底结点。2.出栈操作始终是栈顶结点出栈，即删除头结点之后的结点，如下图：7 7/1515原栈顶的下一个结点成为新的栈顶，即 top=top-next;3.链栈由于采用了链表的方式作为存储方式，各结点通过链域的连接组成栈，由于每个结点空间都是动态分配产生，链栈不用预先考虑容量的大小。4.入栈时，使用 malloc 申请空间后，用指针相连接，所以节点个数没有限制；但是出栈时，如果栈中的元素个数为 0，则不能继续出栈，所以需要判断当前栈是否为空。综上，链表不需要判满，只需要判定是否为空即可。5.链栈 LS 中，Ls 一next 指向栈顶结点，则新结点

15、 * P 入栈的操作为：P 一next=LS 一next；和 LS-next=p；。递归与栈递归与栈1.将递归形式描述的算法改写为功能等价的非递归形式描述的算法，通常应设置的输助结构是栈。队列的基本队列的基本概念概念1.队列是一种先进先出的线性表，新加入的数据元素插在队列尾端，出队列的数据元素在队列首部被删除。队列的顺序队列的顺序实现实现1.循环队列：为了避免元素的移动，将存储队列元素的一维数组首尾相接，形成一个环状。2.入队列操作语句：SQ.rear=（SQ.rear+1）%maxsize;SQ.dataSQ.rear=x;3.出队列赋值语句：SQ.fronts（SQ.front+1）%ma

16、xsize;4.循环队列满：（CQ.rear+1）%maxsize=CQ.front）成立。5.队列空条件：（CQ.rear=CQ.front）成立。6.数组 Qn表示一个循环队列，设 f 为队列中第一个元素的位置，r 为队列中实际队尾的位置加 1，则队列中元素个数的公式：（r-f+n）%n队列的链接队列的链接实现实现1.由于链接实现需要动态申请空间，故链队列在一定范围内不会出现队列满的情况。2.当（LQ.front=LQ.rear）成立时，队列中无数据元素，此时队列为空。带头结点的链队列中，队列头和队列尾指针分别为 front 和 rear，则判断队列空的条件为 front=rear。3.在

17、实现队列的链表结构中，仅设置尾指针的单循环链表的时间复杂度最优。数组的存储数组的存储结构结构1.数组元素的存储位置是下标的线性函数：对于二维数组 amn，如果每个元素占 k 个存储单元，以行为主序为例，讨论数组元素 aij位置与下标的关系。2.由于下标从 0 开始，元素 aij之前已经有 i 行元素，每行有 n 个元素，在第 i 行，有 j+1 个元素，总共有 n*i+j+1 个元素， 第一个元素与 aij相差 n*i+j+11 个位置， 故 aij的位置为： loci， j=loc0，0+（n*i+j）*k。矩阵的压缩矩阵的压缩存储存储1.为了节省存储空间，对这类矩阵采用多个值相同的元素只分

18、配一个存储空间，零元素不存储的策略，这一方法称为矩阵的压缩存储。2.特殊矩阵8 8/1515（1）对称矩阵。一个 n 阶方阵 A 中的元素满足下述条件：aij=aji0i，jn-1。假设以一维数组 Mn（n+1）/2作为 n 阶对称矩阵 A 的存储结构。（2）三角矩阵。以主对角线为界的上（下）半部分是一个固定的值 c 或零。1）为存储 n 阶的三角矩阵，采用数组 Mn（n+1）/2，把矩阵中上（下）三角部分的 n（n+1）/2 个元素存储在数组 M0Mn（n+1）/2-1的 n（n+1）/2 个单元中，其中 c 若非 0，则存放到数组的Mn（n+1）/2中。2）上三角矩阵中元素 aij在数组

19、M 中的位置对应关系：3.稀疏矩阵：非零元素个数很少的矩阵。矩阵压缩存储主要是为了节省存储空间。三元组表示法：用三个项来表示稀疏矩阵中的非零元素 aij，即（i，j，aij），其中 i 表示行序号，j 表示列序号，aij是非零元素的值，通常称为三元组。第四章第四章 树和二叉树树和二叉树知识点名称知识点名称内容内容树的概念树的概念1.树是 n（n 多 0）个结点的有限集合，一棵树满足以下两个条件：（1）当 n=0 时，称为空树；（2）当 n0 时，有且仅有一个称为根的结点，除根结点外，真余结点分 m（m0）个互不相交的非空集合 T1，T2，Tm，这些集合中的每一个都是一棵树，称为根的子树。树的相

20、关术树的相关术语语1.结点的度：树上任一结点所拥有的子树的数目称为该结点的度。2.叶子：度为 0 的结点称为叶子或终端结点。3.树的度：一棵树中所有结点的度的最大值称为该树的度。一个结点的子树的根称为该结点的孩子（或称子结点）。相应地该结点称为孩子的双亲（也称父结点） 。父结点相同的结点互称为兄弟。4.结点的层次：从根开始算起，根的层次为 1，其余结点的层次为其双亲的层次加 1。5.树的高度：一棵树中所有结点层次数的最大值称为该树的高度或深度。6.对于任一个树都有：结点数=分支数+1。二叉树的基二叉树的基本概念本概念1.二叉树是 n（n0）个元素的有限集合，该集合或者为空，或者由一个根及两棵互

21、不相交的左子树和右子树组成，其中左子树和右子树也均为二叉树。2.左右子树次序不可换，都可为空。二叉树的性二叉树的性1.满二叉树：深度为 k（k1）且有 2k-1 个结点的二叉树称为满二叉树。由性质 2 知，满二叉树上的9 9/1515质质结点数已达到了二叉树可以容纳的最大值。2.完全二叉树：如果对满二叉树按从上到下，从左到右的顺序编号，并在最下一层删去部分结点（删后最后一层仍有结点），如果删除的这些结点的编号是连续的且删除的结点中含有最大编号的结点，那么这棵二叉树就是完全二叉树。3.具体性质：（1）性质 1：二叉树的第 i（i1）层上至多有 2i-1个结点。（2）性质 2：深度为 h（h1）的

22、二叉树中至多含有 2h-1 个结点。（3）性质 3：若在任意一棵二叉树中，若度数为 0 的结点（叶结点）个数为 n0，度数为 2 的结点个数为 n0=n2+1。（4）性质 4：具有 n 个结点的完全二叉树完全二叉树深为 log2n +1。（5）性质 5：如果将一棵有 n 个结点的完全二叉树完全二叉树按层编号，按层编号是指：将一棵二叉树中的所有 n 个结点按从第一层到最大层，每层从左到右的顺序依次标记为 1，2，n。则对任一编号为 i（1in）的结点 A 有：1）当 i=1 时，该结点 A 为根，它无双亲结点。当 i1 时，该结点 A 的双亲结点的编号为 i/2 。2）若 2in，则结点 A 既

23、无左孩子，也无右孩子；否则 A 的左孩子的编号为 2i；3）若 2i+1n，则结点 A 无右孩子；否则，A 的右孩子的编号为 2i+1。二叉树的顺二叉树的顺序存储结构序存储结构1.二叉树的顺序存储结构可以用一维数组来实现。2.如果需要顺序存储的非完全二叉树，首先必须用某种方法将其转化为完全二叉树，为此可增设若干个虚拟结点。会造成了空间的浪费。二叉树的链二叉树的链式存储结构式存储结构1.二叉树有不同的链式存储结构，其中最常用的是二叉链表与三叉链表。2.二叉链表：具有 n 个结点的二叉树中，共有 2n 个指针域，其中只有 n-1 个用来指向结点的左、右孩子（因为没有指向根结点的指针域），其余的 n

24、+1 个指针域为 NULL。二叉树遍历二叉树遍历的递归实现的递归实现1.先序遍历2.中序遍历3.后序遍历（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。应用举例应用举例1.由一个二叉树的后序序列和中序序列，可以唯一确定一棵二叉树。2.由一个二叉树的先序序列和中序序列，也可以唯一确定一棵二叉树。3.必须要有中序序列。树的存储结树的存储结1.孩子链表表示法：1010/1515构构（1）树上的一个结点 X 以及该结点的所有孩子结点组成一个带头结点的单链表。（2）头

25、结点含有两个域：数据域和指针域。其中，数据域用于存储结点 X 中的数据元素，指针域用于存储指向 X 第一个孩子结点的指针。（3）表结点也含两个域：孩子域（child）和指针域（next），孩子域存储其中一个孩子的序号，指针域指向其下一个孩子的结点。2.孩子兄弟链表表示法（1）存储时每个结点除了数据域外，还有指向该结点的第一个孩子和下一个兄弟结点的指针。（2） 孩子兄弟链表的结构形式与二叉链表完全相同， 但结点中指针的含义不同。 二叉链表中结点的左、右指针分别指向左、右孩子；而孩子兄弟链表中结点的两个指针分别指向孩子和兄弟。3.双亲表示法由一个一维数组构成。数组的每个分量包含两个域：数据域和双亲

26、域。数据域用于存储树上一个结点中数据元素，双亲域用于存储本结点的双亲结点在数组中的序号（下标值）。树、森林与树、森林与二叉树的关二叉树的关系系1.树转换成二叉树（1）将所有兄弟结点连接起来；（2）保留第一个兄弟结点与父结点的连接，断开其他兄弟结点与父结点的连接，然后以根结点为轴心按顺时针的方向旋转 45角。2.森林转换成二叉树（1）将每棵树转换成相应的二叉树；（2）将（1）中得到的各棵二叉树的根结点看作是兄弟连接起来.3.二叉树转换成森林在待转换的二叉树中，断开根结点与右孩子的连线，得到两棵二叉树，其中一棵是以二叉树 B 的根结点为根的二叉树，另一棵是以根结点的右孩子 E 为根结点的二叉树。森

27、林的遍历森林的遍历1.先序遍历森林2.中序遍历森林（1）访问森林中第棵树的根结点；（2）先序遍历森林第一棵树的根结点的子树组成的森林；（3）先序遍历除去第一棵树之外其余的树组成的森林。（1）中序遍历森林中第一棵树的根结点的子树组成的森林；（2）访问第裸树的根结点；（3）中序遍历除去第一棵树之外其余的树组成的森林。分类与判定分类与判定树树1.分类：一种常用运算，其作用是将输入数据按预定的标准划分成不同的种类。2.判定树：用于描述分类过程的二叉树。哈夫曼哈夫曼（HuffmaHuffman n）树与哈）树与哈夫曼算法夫曼算法1.给定一组值 p1，pk，如何构造一棵有 k 个叶子且分别以这些值为权的判

28、定树，使得其平均比较次数 WPL 最小。满足上述条件的判定树称为哈夫曼树。2.平均比较次数：3.哈夫曼算法：（1）由给定的值p1，pk构造森林 F=T1，Tk，其中每个 Ti 为一棵只有根结点且其权为pi 的二叉树。1111/1515（2）从 F 中选取根结点的权最小的两棵二叉树 Ti 和 Tj，构造一棵分别以 Ti 和 Tj 为左、右子树的新的二叉树 Th，置 Th 根结点的权为 Ti 和 Tj 根结点的权值之和。（3）从 F 中删去 Ti、Tj，并将 Th 加入 F。若 F 中仍多于一棵二叉树，则返回，直到 F 中只含一棵二叉树为止，这棵二叉树就是哈夫曼树。4.结论：最终求得的哈夫曼树中共

29、有结点总数：2n-1 个。其中，n 个叶结点是初始森林中的 n 个结点，合并 n-1 次共产生 n-1 个新结点，且哈夫曼树中没有度数为 1 的分支结点。哈夫曼编码哈夫曼编码1.将哈夫曼树中每个结点的左分支标志“0”，每个结点的右分支标志为“1”，这样，从根到每个叶结点形成序列，将该序列作为叶结点对应字符的编码，由此得到的二进制编码称为哈夫曼编码。第五章第五章 图图知识点名称知识点名称内容内容图的定义和图的定义和术语术语1.在图结构中，任意两个结点之间都可能相关，即结点之间的邻接关系可以是任意的。没有顶点的不叫图，故图最少有一个顶点。2.图的分类（1）无向完全图：任何两点之间都有边的无向图称为

30、无向完全图。一个具有 n 个顶点的无向完全图的边数为 n（n-1）/2。（2）有向完全图：任何两点之间都有弧的有向图称为有向完全图。一个具有 n 个顶点的有向完全图的弧数为 n（n-1）。3.度无向图中顶点 v 的度是与该顶点相关联的边的数目，记为 D（v）。D（v）=ID（v）+OD（v）。（1）入度：如果 G 是一个有向图，则把以顶点 v 为终点的弧的数目称为 v 的入度，记为 ID（v）；（2）出度：把以顶点 v 为始点的弧的数目称为 v 的出度，记为 OD（v）。4.连通在无向图中，如果从顶点 v 到顶点 v有路径，则称 v 和 v是连通的。5.连通图如果图中的任意两个顶点 vi 和

31、vj 都是连通的，则称 G 为连通图。6.连通分量是无向图中的极大连通子图。7.强连通图对于有向图来说，如果图中任意一对顶点 vi 和 vj（其中 ij）都有顶点 vi 到顶点 vj 的路径，也有从 vj到 vi 的路径，即两个顶点间双向连通。8.强连通分量有向图的极大强连通子图9.生成树一个连通图的生成树， 是含有该连通图的全部顶点的一个极小连通子图。 若连通图 G 的顶点个数为 n，则 G 的生成树的边数为 n-1。如果边数大于 n-1，则一定有环。如果边数小于 n-1，则不一定连通。10.树形结构中，结点间有层次关系，每一层结点只能和上一层中的至多一个结点相关，但可能和下一层的多个结点相

32、关。图结构中，任意两个结点之间都可能相关，即结点之间的邻接关系可以是任意的。邻接矩阵邻接矩阵1.用矩阵来描述图中顶点之间的关联关系，其中1212/15152.无向图的邻接矩阵是一个对称矩阵。3.有向图：（1）顶点 Vi 的出度 OD（vi）是邻接矩阵中第 i 行元素之和。（2）顶点 Vi 的入度 ID（vi）是邻接矩阵中第 i 列元素之和。邻接表邻接表1.邻接表是顺序存储与链式存储相结合的存储方法。图的遍历图的遍历1.深度优先搜索（1）类似于树的先序遍历。（2）基本思想：假定以图中某个顶点 vi 为出发点，首先访问出发点 vi，然后任选一个 vi 的未访问过的邻接点 vj，以 vj 为新的出发

33、点继续进行深度优先搜索，依此类推，直至图中所有顶点都被访问过。深度优先搜索遍历类似于树的先序遍历。（3）结论采用邻接矩阵作为存储结构的图的时间复杂度：O（n2），n 为图的顶点数。采用邻接表作为存储结构的图的时间复杂度：O（n+e），n 为图的顶点数，e 为图的边数。2.广度优先搜索（1）类似于树的按层次遍历的过程。（2）基本思想：从图中某个顶点 vi 出发，在访问了 vi 之后依次访问 vi 的所有邻接点，然后依次从这些邻接点出发按广度优先搜索方法遍历图的其他顶点，重复这一过程，直至所有顶点都被访问到。最小生成树最小生成树1.一个图的最小生成树是图所有生成树中权总和最小的生成树。2.最小生成

34、树算法分析：（1）Prim 算法1）初始化：U=u0。其中 U 为一个新设置的顶点的集合，初始 U 中只含有顶点 u0，这里假设在构造最小生成树时，从顶点 u0 出发；2）对所有 uU，vV-U（其中 u，v 表示顶点）的边（u，v）中，找一条权最小的边（u，v） ，将这条边加入到集合 T 中，将顶点 v加入到集合 U 中；3）如果 U=V，则算法结束；否则重复第 2）3）步。（2）克鲁斯卡尔（Kruskal）算法1）设 G=(V，E)，令最小生成树初始状态为只有 n 个顶点而无边的非连通图 T= （V，），每个顶点自成一个连通分量；2）在 E 中选取代价最小的边，若该边依附的顶点落在 T 中

35、不同的连通分量上，则将此边加入到 T 中，否则，舍去此边，选取下条代价最小的边；3）依此类推，重复 2），直至 T 中所有顶点都在同连通分量上为止。3.Dijkstm 算法求单源最短路径问题，即从一个点到所有其他顶点的最短路径。Dijkstra 算法的思想是按照最短路径长度递增的方法产生从一点到其他顶点的最短路径。拓扑排序拓扑排序1.如果以图中的顶点来表示活动，有向边表示活动之间的优先关系，这种用顶点表示活动的有向图称为 AOV 网。AOV 网中的弧表示了活动之间存在着的制约关系。1313/15152.拓扑排序算法的时间复杂度为 O（n+e），n 是图的顶点个数，e 是图的弧的数目。3.完成拓

36、扑排序的前提条件是 AOV 网中不允许出现回路。第六章第六章 查找查找知识点名称知识点名称内容内容基本概念基本概念1.查找表（SearchTable）是由同一类型的数据元素构成的集合，它是一种以查找为“核心”，同时包括其他运算的非常灵活的数据结构。2.其分类有：（1）静态查找表：建表、查找、读表中元素；（2）动态查找表：初始化、查找、读表中元素、插入、删除。顺序表上的顺序表上的查找查找1.静态查找表最简单的实现方法是以顺序表作为存储结构，即链式存储结构。2.“查找成功时的平均查找长度”（记为 ASL）：iniCP1iASL，其中，Pi为查找第 i 个元素（即给定值 key 与顺序表中第 i 个

37、元素的键值相等）的概率，且11iniP，Ci表示在找到第 i 个元素时，与给定值已进行比较的键值个数。有序表上的有序表上的查找查找1.有序表：如果顺序表中数据元素是按照键值大小的顺序排列的，则称为有序表。适用于二分查找。2.二分查找：用给定值 key 与处在中间位置的数据元素 T.elemmid的键值 T.elemmid.key 进行比较，可根据三种比较结果区分三种情况：（1）key=T.elemmid.key，查找成功，T.elemEmid即为待查元素；（2）keyT.elemmid.key，说明若待查元素若在表中，则一定排在 T.elemmid之后。3.平均查找长度二分查找的平均查找长度为

38、11log1ASL2bnnn故二分查找算法的平均时间复杂度为：O（log2n）。索引顺序表索引顺序表上的查找上的查找1.索引顺序表由两部分组成：一个是顺序表，另一个是索引表。二叉排序树二叉排序树1.定义：一棵二叉排序树（又称二叉查找树）或者是一棵空二叉树，或者是具有下列性质的二叉树：（1）若它的左子树不空，则左子树上所有结点的键值均小于它的根结点键值；（2）若它的右子树不空，则右子树上所有结点的键值均大于它的根结点键值；（3）根的左、右子树也分别为二叉排序树。2.二叉排序树上的平均查找长度是介于 O（n）和 O（log2n）之间的。散列表散列表1.数据元素的键值和存储位置之间建立的对应关系 H

39、 称为散列函数，用键值通过散列函数获取存储位置的这种存储方式构造的存储结构称为散列表。2.设有散列函数 H 和键值 k1、k2（k1k2），若 H（k1）=H（k2），则这种现象称为“冲突”，且称键值 k1 和 k2 互为同义词。常用散列法常用散列法1.数字分析法又称数字选择法，其方法是收集所有可能出现的键值，排列在一起，对键值的每一位进行分析，选择1414/1515分布较均匀的若干位组成散列地址。所取的位数取决于散列表的表长，见表长为 100，则取 2 位即可。2.除留余数法是一种简单有效且最常用的构造方法， 其方法是选择一个不大于散列表长 n 的正整数 p， 以键值除以 p所得的余数作为散

40、列地址，即 H（key）=keymodp（pn）注意：通常选 p 为小于散列表长度 n 的素数。3.平方取中法以键值平方的中间几位作为散列地址。通常在选定散列函数时不一定能知道键值的分布情况。所得散列地址比较均匀。4.基数转换法将键值看成另一种进制的数再转换成原来进制的数，然后选其中几位作为散列地址。散列表的实散列表的实现现1.线性探测法对任何键值 key，设 H（key）=d，设散列表的容量为 m，则线性探测法生成的后继散列地址序列为d+1，d+2，m-1，0，1，d-12.二次探测法生成的后继散列地址不是连续的，而是跳跃式的，以便为后续数据元素留下空间从而减少堆积。按照二次探测法，键值 k

41、ey 的散列地址序列为 d0=H（key）；di=（d0+i）mod m。其中，m 为散列表的表长，i=12，-12，22，-22，土 k2（km/2）。第七章第七章 排序排序知识点名称知识点名称内容内容概述概述1.n 个记录的序列为R1，R2，Rn，其相应的键值序列为k1，k2，kn，假设 ki=kj，若在排序前的序列中民在均之前，即 ij，经过排序后，Ri仍在 Rj之前，则称所用的排序方法是稳定的；反之，则称所用的排序方法是不稳定的。2.稳定性是排序方法本身的特性，与数据无关。3.在排序过程中主要有比较两个键值大小和将记录从一个位置移动到另一个位置这两种基本操作。因此，从键值的比较次数和记

42、录的移动次数两个方面来分析时间复杂度。4 4 种排序方种排序方法法1.在待排记录有序的前提下，直接插入排序时间效率最高。2.堆排序：对于 n 个元素的关键字序列k1，k2，kn，当且仅当满足关系 kik2i 且 kik2i+1（2in，2i+1n）称其为最小堆，反之则为最大堆。3.设记录数为 n，冒泡排序算法在最好情况下所作的比较次数为 n-1。4.对比分析（1）插入排序：直接插入排序，是稳定的，时间复杂度为 O（n2），空间复杂度为 O（1），即只需要个记录的辅助空间。（2）交换排序：1）冒泡排序：是稳定的，时间复杂度为 O（n2）。2）快速排序：是不稳定的，平均时间性能最佳，其时间复杂度为 O（nlog2n）。但在最坏情况下，近似于 O（n2）。对较大的 n 值效果较好。（3）选择排序1）直接选择排序：是不稳定的，时间复杂度为 O（n2），但不适宜于 n 较大的情况。2）堆排序：是不稳定的，平均时间、最坏情况下时间复杂度都为 O（nlog2n），最大优点是只需要1515/1515一个记录大小的辅助空间。（4）归并排序1）有序序列的合并：此算法的执行时间为 O（n-h+1）.2）二路归并排序：是稳定的，时间复杂度为 O（nlog2n）。在 n 较大时，归并排序的时间性能优于堆排序，但它所需的辅助存储量较多。