中南大学算法设计与分析.ppt

数据结构简要回顾：栈，队列 —— 栈(Stack) （ LIFO, Last – In – First – Out ） 特点：后进先出的线性结构。 操作：数据加入和取出在栈顶进行。 向栈中添加一个元素称 进栈 ( push ) 从栈顶取出一个元素称 出栈 ( pop ) 应用：递归算法中很常见。（后述） 函数调用时参数传递 —— 队列(Queue)（ FIFO, First – In – First – Out ） 特点：先进先出的线性结构。 操作： 数据加入在队尾，入队 ( enqueue ) 数据取出在队头，出队 ( dequeue ) c d v top push(v) E B D F B D F X D F X Z 头 尾 * 数据结构简要回顾：图 图形结构 非正式定义：图是由一些 顶点 和 边 连接而成。（前述） 正式定义： 图 G = ( V, E ) 是一个二元组，由两个集合定义： 有限集合V，元素称为顶点；有限集合E，元素是一对顶点，称为边。 a c b d e f 集合的列举法表示 * 数据结构简要回顾：图 （1）无向图与有向图 无向图：边无方向，(u, v) 与 (v, u) 相同。 有向图：边有方向，(u, v) 与 (v, u) 不同。 （2）完全图 任意两个顶点之间都有边相连的图。 顶点数：无向完全图 n(n-1)/2，有向完全图 n(n-1) （3）稠密图 相对完全图而言，所缺边数较少的图。 （4）稀疏图 相对完全图而言，所缺边数较多的图。 a c b d e f * 数据结构简要回顾：图的表示 图的存储结构：邻接矩阵、邻接链表、十字链表、邻接多重链表 1. 邻接矩阵表示 用 n ×n 的布尔矩阵表示具有 n 个顶点的图。若第 i 个和第 j 个顶点 有边相连，则矩阵第 i 行、第 j 列元素值为 1，否则则该元素值为 0. 2. 邻接链表表示 每个顶点用一个邻接链表表示，包括 与该顶点邻接的所有顶点。 a c b d e f * 数据结构简要回顾：加权图 加权图（或称带权图） 给边赋值的图，边上的值称为边的权(重) 应用举例： 交通网模型。每个城市为一个顶点，连接 两个城市的边的权重表示它们的距离。 图的表示：邻接矩阵、邻接链表均可。 a b c d 1 5 7 2 4 邻接矩阵表示 邻接链表表示 * 数据结构简要回顾：路径和环 路径、连通性、无环性 —— 图的常用特性 路径： 起始顶点→终止顶点 的一个顶点序列 简单路径：路径中的顶点仅通过一次（无重复顶点） 路径长度：路径中顶点数减 1，等于边数 连通图： 任一对顶点都有一条路径连接。否则，非连通图 a c b d e f a→c →b → f a c b d e f a →c → e → c → b → f a c b d e h g f i 左图为非连通图，包括 两个连通的子图，连通 分量 = 2 * 数据结构简要回顾：树 回路： 起点和终点都是同一个顶点的简单路径 无环图：不包括回路的图。（有闭合路径的图） 树形结构 概念：连通无回路的图。准确术语：自由树 森林：若干棵树的集合，树与树之间不连通 树的特点： 边数 = 顶点数 - 1，检验连通图是否包含回路的简便方法 有根树 （简称 树） 自由树可转换为有根树，如下图所示 h g f i * 基本数据结构回顾：自由树转换为有根树 自由树转换为有根树 —— 层次结构 任选自由树的一个顶点作为树根（顶层，0层），根的邻接顶点作为下面 一层（1层），以此类推。形成一种层次结构，描述具有层次关系的对象 集合。选哪个顶点作为根，取决于应用中各个顶点所具有的层次关系， 如企业组织架构图所固有的上下级关系（领导关系，平级协作关系）。 概念：祖孙、父子、兄弟、叶节点。入度，出度 顶点 c 的深度：从根到 c 的路径长度。（2） 树的高度：从根到叶的最长路径长度。 （3） i c h b g a d e f a b c h d e g f i * 基本数据结构回顾：有序树 有序树 任意节点的所有子节点的位置有序。 二叉查找树（ 或称二叉检索树, BST ） 设任一节点值K，该节点左子树的任意 节点值 ＜ K，右子树 任意节点值 ≥ K 9 5 null 10 null 1 null 7 null null 12 null null 4 null 9 5 10 1 4 7 12 BST * 基本数据结构回顾：有序树表示 树的存储结构