第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与方法和结构有关）
、主要查找算法 顺序查找 折半查找 分块查找 树表查找 上一页 哈希查找 停止放映 下一页 第6页
下一页 上一页 停止放映 第 6 页 二、主要查找算法 •顺序查找 •折半查找 •分块查找 •树表查找 •哈希查找
1、顺序查找 ●(1)算法思想: 从第1个元素到最后1个元素,逐个进行比 较。 ●(2)特点 ●最简单、最普通的查找方法。 ●(3)适用范围(查找表的存储结构) 上一页 既适用于顺序存储结构 停止放映 也适用于链式存储结构 下一页 第7页
下一页 上一页 停止放映 第 7 页 1、顺序查找 ⚫ (1)算法思想： 从第1个元素到最后1个元素，逐个进行比 较。 ⚫ (2)特点： ⚫ 最简单、最普通的查找方法。 ⚫ (3)适用范围（查找表的存储结构）： –既适用于顺序存储结构 –也适用于链式存储结构
顺序查找的算法描述 ●(4)操作步骤 stepl从第1个元素开始查找; step2用待查关键字值与各结点 (记录)的关键字值逐个进行比较; 若找到相等的结点,则查找成功;否 则,查找失败。 上★-逐个比较 停止放映 下一页 第8页
下一页 上一页 停止放映 第 8 页 顺序查找的算法描述 ⚫ (4)操作步骤： –step1 从第1个元素开始查找； –step2 用 待 查 关 键 字 值 与 各 结 点 （记录）的关键字值逐个进行比较； 若找到相等的结点，则查找成功；否 则，查找失败。 –逐个比较
顺序查找算法框图 开始 seg search(A, n, key) A待查表 i=0 n元素个数 key要找的值 查找key的循环 I++ isn&&Ali:=key? I<n,且还没找到, 循环 Y Ai=ke 上一页 显示“查找失败” 显示“查找成功” 停止放映 下一页 返回 第9页
下一页 上一页 停止放映 第 9 页 顺序查找算法框图 i=0 seq_search(A，n，key) A 待查表 n 元素个数 key 要找的值 i<n&&A[i]!=key? Y N 查找key的循环 显示“查找失败” 返回 开始 i++ A[i]==key? N Y 显示“查找成功” I<n，且还没找到， 循环
(5)顺序查找算法3-1 tem待查表 seg search(item key n元素个数 int *item, n, key key要找的值 i int i=0 while (i<n&& item[i]! key i++ /*查找key的循环* if (item[i]== key printf(“查找成功!\n”); return(i);} 上一页 e⊥se 停止放映 printf(“查找失败!n”); return(-1);} 下一页 WHile I中,有两个判断条件,改进一下,可以减少一半 第10页
下一页 上一页 停止放映 第 10 页 (5)顺序查找算法3-1 seq_search(item , n , key ) int *item ,n , key ; { int i=0 ; while ( i < n && item[i] != key ) i++; /* 查找key的循环 */ if (item[i]= = key ) { printf(“查找成功 !\n”); return (i); } else { printf(“查找失败 !\n”); return (-1);} } item 待查表 n 元素个数 key 要找的值 While中，有两个判断条件，改进一下，可以减少一半