西安交通大学：《计算机软件基础》第6单元 查找

第6单元 查找 计算机软件基础 The software bas ic of computer 下一页 主讲:刘志 西安交通大学 计算机教学实验中心

下一页 计算机软件基础 The software basic of computer 主讲：刘志强 西安交通大学 计算机教学实验中心 第6单元 查找

教学目标 了解有关查找的 基本概念 查找的主要算法 上一页 停止放映 页 第2页

下一页 上一页 停止放映 第 2 页 教学目标 ⚫了解有关查找的 –基本概念 –查找的主要算法

教学要求 通过本单元的学习,了解、掌握有关 查找的: ●基本概念 查找、平均查找长度 ●主要查找算法 顺序查找、折半查找、分块查找 上一页 树表查找、哈希查找 停止放映 页 第3页

下一页 上一页 停止放映 第 3 页 教学要求 通过本单元的学习，了解、掌握有关 查找的： ⚫ 基本概念 – 查找、平均查找长度 ⚫ 主要查找算法 – 顺序查找、折半查找、分块查找 – 树表查找、哈希查找

本单元涉及的内容 ●第3章 31什么是查找 32顺序表查找 33树表查找 34哈希查找 上一页 ●P9oP102 停止放映 页 第4页

下一页 上一页 停止放映 第 4 页 本单元涉及的内容 ⚫ 第3章 ⚫ 3.1 什么是查找 ⚫ 3.2 顺序表查找 ⚫ 3.3 树表查找 ⚫ 3.4 哈希查找 ⚫ P90~P102

基本概念 查找 ●查找表 ●静态查找 ●动态查找 ●平均查找长度 上一页 停止放映 页 第5页

下一页 上一页 停止放映 第 5 页 一、基本概念 ⚫ 查找 ⚫ 查找表 ⚫ 静态查找 ⚫ 动态查找 ⚫ 平均查找长度

查找 ●查找就是在给定的DS中找出满足某种条件 的结点;若存在这样的结点,查找成功; 否则,查找失败。 ●找表是一组待查数据元素的集合。 ●静亦找是仅仅进行查询和检索操作,不 改变查找表中数据元素间的逻辑关系的查 找。 上一页 ●动态查找是除了进行查询和检索操作外,还对查 找表进行插入、删除操作的查找,动态地改变查找 停止放映 表中数据元素之间的逻辑关系。 页 第6页

下一页 上一页 停止放映 第 6 页 查找 ⚫ 查找 就是在给定的DS中找出满足某种条件 的结点；若存在这样的结点，查找成功； 否则，查找失败。 ⚫ 查找表 是一组待查数据元素的集合。 ⚫ 静态查找 是仅仅进行查询和检索操作，不 改变查找表中数据元素间的逻辑关系的查 找。 ⚫ 动态查找 是除了进行查询和检索操作外，还对查 找表进行插入、删除操作的查找，动态地改变查找 表中数据元素之间的逻辑关系

平均查找长度 平均查找长度( ASL-Average Search Length) 在查找过程中,对每个结点记录中的关键字要进行反复 比较,以确定其位置。因此,与关键字进行比较的平 均次数,就成为平均查找长度。它是用来评价一个算 法好坏的一个依据。 ●对含有n个数据元素的查找表,查找成功时的平均查找 长度为: ASL=∑Pi米Ci 上一页 其中: 停止放映 Ci为查找第i个数据元素时需比较的次数=1 Pi为查找表中第i个数据元素的概率,且∑ 页 显然,C随查找过程及DS的不同而各异。 第7页

下一页 上一页 停止放映 第 7 页 平均查找长度 ⚫ 平均查找长度 （ASL-Average Search Length） 在查找过程中，对每个结点记录中的关键字要进行反复 比较，以确定其位置。因此，与关键字进行比较的平 均次数，就成为平均查找长度。它是用来评价一个算 法好坏的一个依据。 ⚫ 对含有n个数据元素的查找表，查找成功时的平均查找 长度为： ASL =  Pi * Ci 其中： Pi 为查找表中第i个数据元素的概率，且  Pi = 1 Ci为查找第i个数据元素时需比较的次数。 显然，Ci随查找过程及DS的不同而各异。 i=1 n i=1 n

、主要查找算法 顺序查找 折半查找 分块查找 树表查找 上一页 哈希查找 停止放映 页 第8页

下一页 上一页 停止放映 第 8 页 二、主要查找算法 •顺序查找 •折半查找 •分块查找 •树表查找 •哈希查找

1、顺序查找 ●顺序查找是最简单、最普通的查找方法。 ●查找步骤: stepl从第1个元素开始查找; step2用待查关键字值与各结点(记录)的 关键字值逐个迸行比较;若找到相等的结点, 则查找成功;否则,查找失败。 ●查找表的存储结构: 上一页 既适用于顺序存储结构 停止放映 也适用于链式存储结构 页 第9页

下一页 上一页 停止放映 第 9 页 1、顺序查找 ⚫ 顺序查找是最简单、最普通的查找方法。 ⚫ 查找步骤： –step1 从第1个元素开始查找； –step2 用待查关键字值与各结点（记录）的 关键字值逐个进行比较；若找到相等的结点， 则查找成功；否则，查找失败。 ⚫ 查找表的存储结构： –既适用于顺序存储结构 –也适用于链式存储结构

顺序查找算法3-1 seg search(item, n, key int *item, n, key int 1=0 while(i<n&& item[i]!=key 1+t if (item[i]== key printf(“查找成功!n”); return(i);} 上一页 e⊥se 停止放映 printf(“查找失败!ln”); return(-1);} 页 第10页

下一页 上一页 停止放映 第 10 页 顺序查找算法3-1 seq_search(item , n , key ) int *item ,n , key ; { int i=0 ; while ( i < n && item[i] != key ) i++; if (item[i]= = key ) { printf(“查找成功 !\n”); return (i); } else { printf(“查找失败 !\n”); return (-1);} }