第四章 慧查找与排序
计算机软件基础 第四章 查找与排序
本章内容 今4.1查找与排序概述 计算机软件基 今42线性表上的查找 今4.3二又树上的查找 4.4哈希查找 ◆4.5直接插入排序 ◇4.6交换排序 今47选择排序 4.8多关键字排序
计算机软件基础 ❖ 4.1 查找与排序概述 ❖ 4.2 线性表上的查找 ❖ 4.3 二叉树上的查找 ❖ 4.4 哈希查找 ❖ 4.5 直接插入排序 ❖ 4.6 交换排序 ❖ 4.7 选择排序 ❖ 4.8 多关键字排序 本章内容
41查找与排序概述 计1与查找有关的概念 ()查找:又称检索,是指在大量数据中寻找 件关键字值等于给定值的记录。 基(2)主关键字:指在组成记录的若干个数据项 础中,能够唯一标识一条记录的数据项。 (3)次关键字:指在组成记录的若干个数据 项中,不能唯一标识一条记录的数据项
4.1 查找与排序概述 1.与查找有关的概念 (1) 查找：又称检索，是指在大量数据中寻找 关键字值等于给定值的记录。 (2) 主关键字：指在组成记录的若干个数据项 中，能够唯一标识一条记录的数据项。 (3）次关键字：指在组成记录的若干个数据 项中，不能唯一标识一条记录的数据项。 计 算 机 软 件 基 础
(4)平均查找长度( Average Search Length指 查找过程中,对于查找关键字进行比较的平均 计比较次数,记为4其计算公式如下所示 ASL=∑pc 件其中,P为查找第个元素的概率,c为查找 基第个元素所需进行的比较次数。通常认为查找 每个元素的概率相等,即p1=p2=…=pn=1n 注意!!:本章所介绍的各种查找方法都是 基于主关键字的查找
(4) 平均查找长度(Average Search Length)指 查找过程中，对于查找关键字进行比较的平均 比较次数，记为ASL。其计算公式如下所示： 其中，pi为查找第i个元素的概率， ci为查找 第i个元素所需进行的比较次数。通常认为查找 每个元素的概率相等，即p1 = p2 = … = pn =1/n。 = = n i ASL pici 1 计 算 机 软 件 基 础 注意！！：本章所介绍的各种查找方法都是 基于主关键字的查找。
2.与排序有关的概念 计算机软件基 (1)排序:指将一组记录按照指定关键字 大小递增(或递减)的次序排列起来。 (2)稳定性:若待排序的一组记录中存在 但多个关键字值相同的记录,如果使用某种 排序算法进行排序后,相同关键字值的多 个记录的相对次序与排序前相比没有改变, 则称此排序算法具有稳定性
2.与排序有关的概念 （1）排序：指将一组记录按照指定关键字 大小递增（或递减）的次序排列起来。 （2）稳定性：若待排序的一组记录中存在 多个关键字值相同的记录，如果使用某种 排序算法进行排序后，相同关键字值的多 个记录的相对次序与排序前相比没有改变， 则称此排序算法具有稳定性。 计 算 机 软 件 基 础
4.2线性表的查找 ◆查找方法: 共同点: 1.顺序查找 都是在顺序存储 的线性表上进行 2.二分查找 查找 3.分块查找 假设后面算法涉及的线性表的类型定义如 下(假设关键字类型为int型): struct ElemType 注意:为了符合习惯,后面顺序 线性表查找和排序算法中,元素 int key 在数组中的存储位置从1开始。 datatype other;
4.2 线性表的查找 ❖ 查找方法： 1. 顺序查找 2. 二分查找 3. 分块查找 共同点： 都是在顺序存储 的线性表上进行 查找。 假设后面算法涉及的线性表的类型定义如 下（假设关键字类型为int型）： struct ElemType { int key; datatype other;}； 注意：为了符合习惯，后面顺序 线性表查找和排序算法中，元素 在数组中的存储位置从1开始
顺序查找 计算机软件 1.基本思想 从线性表的表尾到表头(从后往前), 或者从线性表的表头到表尾(从前往后), 依次将每个元素的关键字值和给定关键字 基值相比较,寻找关键字值与给定关键字值 相等的元素。若找到满足条件的元素,则 查找成功;若查找完整个线性表都找不到 满足条件的元素,则查找失败
计 算 机 软 件 基 础 一. 顺序查找 1．基本思想 从线性表的表尾到表头（从后往前）， 或者从线性表的表头到表尾（从前往后）， 依次将每个元素的关键字值和给定关键字 值相比较，寻找关键字值与给定关键字值 相等的元素。若找到满足条件的元素，则 查找成功；若查找完整个线性表都找不到 满足条件的元素，则查找失败。
算法描述 int Seqsearch(seqlist L, int x) /在线性表上查找关键字为x的元素 计算机软件基 i int i; L->list0]key=x;/设置监视哨* L->leghth 件/从表尾开始向前扫描 while(l->list. key/=x)i--i return 1; 若查找成功,返回元素所在的位置;若查找失败, 则返回0值* 1 *seqsearch */
计 算 机 软 件 基 础 二．算法描述 int SeqSearch(SeqList *L,int x) /*在线性表上查找关键字为x的元素*/ { int i; L->list[0].key=x; /*设置监视哨*/ i=L->leghth; /*从表尾开始向前扫描*/ while(L->list[i].key!=x) i--; return i; /*若查找成功，返回元素所在的位置；若查找失败， 则返回0值*/ } /*seqsearch*/
3.算法说明 在算法中,线性表中的元素存放于数组r的下标为1 n的数组元素中,为了避免每次比较时都要判断条件 (i>0)以防数组下标越界,因此设置了数组元素ro 充当“监视哨”。 机4.算法分析 件若所查元素为1,需要n次比较:若所查元素为 基则需n+1次比较。因此在等概率条件下查找成功的 础平均查找长度为 ASL=∑pc=∑ n+1 ×(n-1+ 1)=∑(n-i+1)
3. 算法说明 在算法中，线性表中的元素存放于数组r的下标为1~ n的数组元素中，为了避免每次比较时都要判断条件 （i>0）以防数组下标越界，因此设置了数组元素r[0] 充当“监视哨” 。 4. 算法分析 当查找成功时，若所查元素为r(n)，只需一次比较； 若所查元素为r(1)，需要n次比较；若所查元素为r(i)， 则需n-i+1次比较。因此在等概率条件下查找成功的 平均查找长度为： = = = + = = − + = − + = n i n i i n i i i n n i n ASL p c p n i 1 1 1 2 1 ( 1) 1 ( 1) 计 算 机 软 件 基 础
二分查找 过注意 二分査找算法在使用时必须满足两个前 提条件: 1.线性表中的元素必须按照查找关键字排列 基有序 2.线性表必须以顺序存储方式存储
计 算 机 软 件 基 础 ❖ 注意：！ 二分查找算法在使用时必须满足两个前 提条件： 1. 线性表中的元素必须按照查找关键字排列 有序； 2. 线性表必须以顺序存储方式存储。 二. 二分查找