计算机备考资料：数据结构基本概念(九)

《计算机备考资料：数据结构基本概念(九)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构：基本概念(九)　　Ø最小生成树的定义　　设G=(V，E)是一个无向连通网，生成树上各边的权值之和称为该生成树的代价，在G的所有生成树中，代价最小的生成树称为最小生成树。　　Ø普里姆(Prim)算法的基本思想　　设G=(V，E)是一个无向连通网，令T=(U，TE)是G的最小生成树。T的初始状态为U={v0}(v0∈V)，TE={}，然后重复执行下述操作：在所有u∈U，v∈V-U的边中找一条代价最小的边(u，v)并入边集TE，同时v并入顶点集U，直至U=V为止。　　Ø克鲁斯卡尔(Kruskal)算法的基本思想　　设无向连通网为G=(V，E

2、)，令G的最小生成树为T=(U，TE)，其初态为U=V，TE={}，然后按照边的权值由小到大的顺序，依次考察边集E中的各条边。若被考察边的两个顶点属于T的两个不同的连通分量，则将此边加入到TE中，同时把两个连通分量连接为一个连通分量;若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路。如此下去，当T中的连通分量个数为1时，此连通分量便为G的一棵最小生成树。　　Ø迪杰斯特拉(Dijkstra)算法的基本思想　　设置集合S存放已经找到最短路径的顶点，S的初始状态只包含源点v，对vi∈V-S，假设从源点v到vi的有向边为最短路径。以后每

3、求得一条最短路径v,…,vk，就将vk加入集合S中，并将路径v,…,vk,vi与原来的假设相比较，取路径长度较小者为当前最短路径。重复上述过程，直到集合V中全部顶点加入到集合S中。　　ØFloyd算法的基本思想　　假设从vi到vj的弧(若从vi到vj的弧不存在，则将其弧的权值看成∞)是最短路径，然后进行n次试探。若vi,…,vk和vk,…,vj分别是从vi到vk和从vk到vj中间顶点的序号不大于k-1的最短路径，则将vi,…,vk,…,vj和已经得到的从vi到vj中间顶点的序号不大于k-1的最短路径相比较，取长度较短者为从vi到vj中间顶点的序

4、号不大于k的最短路径。　　ØAOV网的定义　　在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，称这样的有向图为顶点表示活动的网，简称AOV网。　　Ø拓扑序列的定义　　设G=(V，E)是一个具有n个顶点的有向图，V中的顶点序列v1,v2,…,vn称为一个拓扑序列，当且仅当满足下列条件：若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在顶点vj之前。　　Ø拓扑排序的基本思想　　对AOV网进行拓扑排序的基本思想是：　　⑴从AOV网中选择一个没有前驱的顶点并且输出它;　　⑵从AOV网中删去该顶点，并且删去所有以该顶点为尾的弧

5、;　　⑶重复上述两步，直到全部顶点都被输出，或AOV网中不存在没有前驱的顶点。　　Ø查找算法的时间性能　　查找算法用关键码的比较次数来度量查找算法的时间性能。对于查找成功的情况，将关键码比较次数的数学期望值定义为平均查找长度，即：　　ASL其中，n表示问题规模，即查找集合中的记录个数;pi表示查找第i个记录的概率;ci表示查找第i个记录所需的关键码的比较次数。　　Ø顺序查找算法的时间复杂度　　对于具有n个记录的顺序表，查找第i个记录时，需进行n-i+1次关键码的比较。设每个记录的查找概率相等，查找成功时，顺序查找的平均查找长度为：O(n);查找

6、不成功时，关键码的比较次数是n+1次，则查找失败的平均查找长度为O(n)。　　Ø顺序查找的适用情况　　顺序查找对表中记录的存储没有任何要求，顺序存储和链接存储均可应用;对表中记录的有序性也没有要求，无论记录是否按关键码有序均可应用。　　Ø折半查找的适用情况　　折半查找(也称对半查找、对分查找、二分查找)要求线性表中的记录必须按关键码有序，并且必须采用顺序存储。　　Ø折半查找的基本思想　　取有序表的中间记录作为比较对象，则　　(1)若给定值与中间记录的关键码相等，则查找成功;　　(2)若给定值小于中间记录的关键码，则在中间记录的左半区继续查找;　

7、　(3)若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。　　不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。　　Ø折半查找的时间复杂度　　具有n个结点的折半查找判定树的深度为。　　最好情况：比较1次，即查找的关键码是判定树的根结点;　　最坏情况：比较次数为，即查找的关键码是判定树的最下一层结点;　　平均情况：折半查找的平均时间复杂度为O(log2n)。　　查找不成功的比较次数最多不超过树的深度，最多为次。