软件工程与c语言chapter4.1-4.2.ppt

计算机软件基础第四章查找与排序计算机软件基础 查找与排序概述 线性表上的查找 二叉树上的查找 哈希查找 直接插入排序 交换排序 选择排序 多关键字排序本章内容 查找与排序概述 (1) 查找:又称检索,是指在大量数据中寻找关键字值等于给定值的记录。(2) 主关键字:指在组成记录的若干个数据项中,能够唯一标识一条记录的数据项。(3)次关键字:指在组成记录的若干个数据项中,不能唯一标识一条记录的数据项。计算机软件基础????(4) 平均查找长度(Average Search Length) 指查找过程中, 对于查找关键字进行比较的平均比较次数,记为 ASL 。其计算公式如下所示: 其中, pi为查找第 i个元素的概率, ci为查找第 i个元素所需进行的比较次数。通常认为查找每个元素的概率相等,即 p1 = p2 = … = pn =1/n 。??? ni iicp ASL 1计算机软件基础注意!!:本章所介绍的各种查找方法都是基于主关键字的查找。???? (1)排序:指将一组记录按照指定关键字大小递增(或递减)的次序排列起来。(2)稳定性:若待排序的一组记录中存在多个关键字值相同的记录,如果使用某种排序算法进行排序后,相同关键字值的多个记录的相对次序与排序前相比没有改变,则称此排序算法具有稳定性。计算机软件基础???? 线性表的查找?查找方法: : 都是在顺序存储的线性表上进行查找。假设后面算法涉及的线性表的类型定义如下(假设关键字类型为 int型): struct ElemType { int key; datatype other;} ;????注意:为了符合****惯,后面顺序线性表查找和排序算法中,元素在数组中的存储位置从 1开始。计算机软件基础一. 顺序查找 (从后往前),或者从线性表的表头到表尾(从前往后),依次将每个元素的关键字值和给定关键字值相比较,寻找关键字值与给定关键字值相等的元素。若找到满足条件的元素,则查找成功;若查找完整个线性表都找不到满足条件的元素,则查找失败。????计算机软件基础???? 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 )以防数组下标越界,因此设置了数组元素 r[0] 充当“监视哨”。 4. 算法分析当查找成功时,若所查元素为 r(n) ,只需一次比较;若所查元素为 r(1) ,需要 n次比较;若所查元素为 r(i) ,则需 n-i+1 次比较。因此在等概率条件下查找成功的平均查找长度为: ???????????????? ni ni i ni iininn inpcp ASL 11 12 1)1( 1)1( 计算机软件基础????计算机软件基础注意:! 二分查找算法在使用时必须满足两个前提条件: 1. 线性表中的元素必须按照查找关键字排列有序; 2. 线性表必须以顺序存储方式存储。????二. 二分查找