第6单元 查找 计算机软件基础 The software bas ic of computer 主讲:赵英良 西安交通大学计算机教学实近中心
下一页 计算机软件基础 The software basic of computer 主讲：赵英良 西安交通大学计算机教学实验中心 第6单元 查找
上节内容提要图 基本概念 有向图、无向图、边、弧、弧头、弧尾、顶点、邻 接点(有向、无向不同)、度、入度、出度、子图、生成 树、连通图、连通分量、强连通图、权、网、 存储结构及实现 邻接矩阵、邻接表(对有向、无向图不同) 遍历及其它操作 深度优先、广度优先遍历 应用 上页最小生成树(Pm算法, rusal算法)、拓扑排序 停止放映 二叉排序树的生成、查找和打印(有完整程序) Huffman树(带权路径最短的二叉树)与 Huffman编码 下一页 最短路径 第2页
下一页 上一页 停止放映 第 2 页 上节内容提要——图 –基本概念 • 有向图、无向图、边、弧、弧头、弧尾、顶点、邻 接点（有向、无向不同）、度、入度、出度、子图、生成 树、连通图、连通分量、强连通图、权、网、 –存储结构及实现 • 邻接矩阵、邻接表（对有向、无向图不同） –遍历及其它操作 • 深度优先、广度优先遍历 –应 用 –最小生成树（Prim算法、Kruskal算法）、拓扑排序 –二叉排序树的生成、查找和打印（有完整程序）， –Huffman树(带权路径最短的二叉树)与Huffman编码 –最短路径
第6单元 第3章查找和排序 3
下一页 第6单元 第3章 查找和排序 查找
查找的基本概念 ●L.箜找就是在给定的DS中找出滿足某种条件 的结点;若存在这样的结点,查找成功;否 则,查找失败。(找) ●2.查找表是一组待查数据元素的集合。待找 3静峦查找是仅仅进行查询和检索操作,不 改变查找表中数据元素间的逻辑关系的查找。 (不改变元素关系) ●4动态变找是除了进行查询和检索操作外,还对 上一页 查找表进行插入、删除操作的查找,动态地改变查 停止放峡找表中数据元素之间的逻辑关系。改变元素关系 下一页 第4页
下一页 上一页 停止放映 第 4 页 一、查找的基本概念 ⚫ 1.查找 就是在给定的DS中找出满足某种条件 的结点；若存在这样的结点，查找成功；否 则，查找失败。（找） ⚫ 2.查找表 是一组待查数据元素的集合。待找 ⚫ 3.静态查找 是仅仅进行查询和检索操作，不 改变查找表中数据元素间的逻辑关系的查找。 （不改变元素关系） ⚫ 4.动态查找 是除了进行查询和检索操作外，还对 查找表进行插入、删除操作的查找，动态地改变查 找表中数据元素之间的逻辑关系。改变元素关系
平均查找长度 ●5.平均查找长度(ASL- Average Search Length)(比较次数) 在查找过程中,要对每个结点记录中的关键字进行 反复比较,以确定其位置。因此,与关键字进行比 较的平均次数,就称为平均查找长度。是用来评价 算法好坏的一个依据。(算法的评价) 对含有n个数据元素的査找表,查找成功时的平均 查找长度为:ASL=∑Pi*Ci 其中:Pi为查找表中第i个数据元素的概率,且 上一页 停止放映 ∑Pi=1 i=1 下一页 Ci为查找第i个数据元素时需比较的次数。 Ci随查找过程及D的不同而各异。(Ci与方法和结构有 葉贞
下一页 上一页 停止放映 第 5 页 平均查找长度 ⚫ 5. 平均查找长度 （ ASL-Average Search Length）（比较次数） 在查找过程中，要对每个结点记录中的关键字进行 反复比较，以确定其位置。因此，与关键字进行比 较的平均次数，就称为平均查找长度。是用来评价 算法好坏的一个依据。(算法的评价) ⚫ 对含有n个数据元素的查找表，查找成功时的平均 查找长度为： ASL = Pi* Ci n i=1 Pi = 1 i=1 n 其中：Pi 为查找表中第i个数据元素的概率，且 Ci为查找第i个数据元素时需比较的次数。 Ci随查找过程及DS的不同而各异。（Ci与方法和结构有关）