Perfree

简简单单的生活,安安静静的写博客

8.2 线性表的查找
通过本知识点的学习,能够对一个给定的顺序表,按照顺序查找、折半查找和分块查找算法查找某个数据元素,能计算出实际比较操作的次数。 1.存储结构 查找表为线性表,其存储结构为一维结构数组,也即是顺序表,数组的每一个元素对应查找表的一个记录。为简单起见,设记录中只有一个整数关键字,存放记录的结构体类型描述
8.1 查找表的基本概念
查找算法在实际开发中有重要的应用。要求能准确叙述查找的定义,理解查找的基本思想。 简单说来,查找就是在数据元素(或记录)的集合中找出“满足查找要求”的数据元素(记录)。以下叙述中,统一采用“记录”这一名词。 1.相关名词 查找表(Search Table):是同一类型的记录构成的集合。 关键字(Ke
7小结
1.图结构中的每个结点可以有任意多个前驱和任意多个后继。对于无向图,每个顶点的邻接点既是它的前驱结点,又是它的后继结点;对于有向图,每个顶点的入边邻接点是它的前驱结点,出边邻接点是它的后继结点。 2.无向图中每个顶点的度、入度和出度均等于它的邻接点数;有向图中每个顶点的度、入度和出度分别等于它的邻接
7.6 拓扑排序
能够理解AOV网、拓扑序列及拓扑排序等概念,能够利用拓扑排序算法写出AOV网的任一种拓扑序列。 一个较大的工程往往被划分成许多子工程,我们把这些子工程称作活动(Activity)。在整个工程中,有些子工程(活动)必须在其他有关子工程完成之后才能开始,也就是说,一个子工程的开始是以它的所有前序子工程的
7.5 最短路径
能够理解最短路径和最短路径长度的概念,能够利用狄克斯特拉算法求出图中一顶点到其余各顶点的最短路径和最短路径长度。 1.最短路径的概念 由图的概念可知,在一个图中,若从一顶点到另一顶点存在着一条路径(这里只讨论无回路的简单路径),则称其路径长度等于该路径上所经过的边的数目,它也等于该路径上的顶点数减1
7.4 图的生成树和最小生成树
能够理解生成树和最小生成树的概念,掌握克鲁斯卡尔算法的思想并能构造最小生成树。 1.图的生成树和最小生成树的概念 在一个连通图G中,如果取它的全部顶点和一部分边构成一个子图G′,即: V(G’)=V(G)和E(G’)ÍE(G) 若边集E(G’)中的边既能够把图中的所有顶点连通而又不形成回路
7.3 图的遍历
能够理解图的遍历概念,掌握图的深度优先搜索和广度优先搜索遍历的方法和算法。 1.图的遍历的概念 图的遍历就是从称为初始点的一个指定的顶点出发,按照一定的搜索方法对图中的所有顶点访问一次且仅一次的过程。 图的遍历比树的遍历要复杂,因为从树根到达树中的每个结点只有一条路径,而从图的初始点到达图中的每个顶
7.2 图的存储结构
能够掌握图的邻接矩阵、邻接表和边集数组表示的方法和相应的生成算法。 图的存储结构又称作图的存储表示或图的表示。它有多种表示方法,这里主要介绍邻接矩阵、邻接表和边集数组这三种方法。 邻接矩阵(adjacency matrix)是表示图形中顶点之间相邻关系的矩阵。设G=(V,E)是具有n个顶点的图,顶点
7.1 图的概念
生活中有许多现象可以表示为图,请结合实例理解图的定义及相关概念。 1.图的定义 (1)无向图的定义 无向图是一个有序的二元组< V, E>,记为G,如图7-1(a)所示。 V为顶点集,E为连结点的边集(无向边) G 1= < V(G1) , E(G1) > V(G1) = {
6.5 哈夫曼树
理解哈夫曼树的定义及算法的基本思想,给定一些带权叶子结点,能手工建立哈夫曼树,并求出叶子结点的哈夫曼编码。 1.基本概念 (1)路径和路径长度 若在一棵树中存在着一个结点序列k1、k2、…、kj,使得ki是ki+1的双亲(1≤i1到kj的路径(Path)。因树中每个结点只有一个双亲结点,所以它也是这

标签