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

计算机软件基础,第四章 查找与排序,计算机软件基础,4.1 查找与排序概述 4.2 线性表上的查找 4.3 二叉树上的查找 4.4 哈希查找 4.5 直接插入排序 4.6 交换排序 4.7 选择排序 4.8 多关键字排序,本章内容,4.1 查找与排序概述,1.与查找有关的概念,(1) 查找：又称检索，是指在大量数据中寻找关键字值等于给定值的记录。 (2) 主关键字：指在组成记录的若干个数据项中，能够唯一标识一条记录的数据项。 (3）次关键字：指在组成记录的若干个数据项中，不能唯一标识一条记录的数据项。,计算机软件基础,(4) 平均查找长度(Average Search Length)指查找过程中，对于查找关键字进行比较的平均比较次数，记为ASL。其计算公式如下所示： 其中，pi为查找第i个元素的概率， ci为查找第i个元素所需进行的比较次数。通常认为查找每个元素的概率相等，即p1 = p2 = = pn =1/n。,计算机软件基础,注意！：本章所介绍的各种查找方法都是基于主关键字的查找。,2.与排序有关的概念,（1）排序：指将一组记录按照指定关键字大小递增（或递减）的次序排列起来。 （2）稳定性：若待排序的一组记录中存在多个关键字值相同的记录，如果使用某种排序算法进行排序后，相同关键字值的多个记录的相对次序与排序前相比没有改变，则称此排序算法具有稳定性。,计算机软件基础,4.2 线性表的查找,假设后面算法涉及的线性表的类型定义如下（假设关键字类型为int型）： struct ElemType int key; datatype other;；,注意：为了符合习惯，后面顺序线性表查找和排序算法中，元素在数组中的存储位置从1开始。,计算机软件基础,一. 顺序查找,1基本思想 从线性表的表尾到表头（从后往前），或者从线性表的表头到表尾（从前往后），依次将每个元素的关键字值和给定关键字值相比较，寻找关键字值与给定关键字值相等的元素。若找到满足条件的元素，则查找成功；若查找完整个线性表都找不到满足条件的元素，则查找失败。,计算机软件基础,二算法描述 int SeqSearch(SeqList *L,int x) /*在线性表上查找关键字为x的元素*/ int i; L-list0.key=x; /*设置监视哨*/ i=L-leghth; /*从表尾开始向前扫描*/ while(L-listi.key!=x) i-; return i; /*若查找成功，返回元素所在的位置；若查找失败，则返回0值*/ /*seqsearch*/,3. 算法说明 在算法中，线性表中的元素存放于数组r的下标为1 n的数组元素中，为了避免每次比较时都要判断条件（i0）以防数组下标越界，因此设置了数组元素r0充当“监视哨”。 4. 算法分析 当查找成功时，若所查元素为r(n)，只需一次比较；若所查元素为r(1)，需要n次比较；若所查元素为r(i)，则需n-i+1次比较。因此在等概率条件下查找成功的平均查找长度为：,计算机软件基础,计算机软件基础,注意：！ 二分查找算法在使用时必须满足两个前提条件： 1. 线性表中的元素必须按照查找关键字排列有序； 2. 线性表必须以顺序存储方式存储。,二. 二分查找,计算机软件基础,二. 二分查找,1基本思想 找到查找区间的中间位置，用此位置上元素的关键字值与待查关键字值相比较。若相等，则查找成功；否则，将查找范围缩小到半个区间，只在可能存在待查元素的前半区间或后半区间进行查找。重复上述过程，直到查找成功或查找范围缩小到空。,计算机软件基础,二分查找过程示例,下面是在一个升序线性表18，26，32，45，52，66，80，91上查找关键字为80的元素的二分查找过程。,18 26 32 45 52 66 80 91 low=1 mid=4 high=8,8045 到右区间查找 改变low,计算机软件基础,二分查找过程示例,下面是在一个升序线性表18，26，32，45，52，66，80，91上查找关键字为80的元素的二分查找过程。,18 26 32 45 52 66 80 91 low=5 mid=6 high=8,8066 到右区间查找 改变low,计算机软件基础,二分查找过程示例,下面是在一个升序线性表18，26，32，45，52，66，80，91上查找关键字为80的元素的二分查找过程。,18 26 32 45 52 66 80 91 low=7 mid=7 high=8,80=80 查找成功,计算机软件基础,二算法描述 int binsearch(SeqList *L,int x) /*在长度为n的升序线性表上查找关键字为x的元素*/ int low,high,mid; low=1; high=L-length; /*设置查找区间左、右端点的初值*/ while(lowlistmid.key) return(mid); /*查找成功时返回元素所在的位置*/ else if(xlistmid.key) high=mid-1; /*缩小查找区间*/ else low=mid+1; return(0); /*查找失败时返回0值*/ /*binsearch*/,计算机软件基础,3.算法说明 算法中的整型变量low、high、mid分别用于标识查找区间的左端点、右端点及中间位置。 在升序排列的线性表中，若待查元素关键字值小于中间位置元素的关键字值，则缩小查找区间到原区间的上半部（区间左端点不变，区间右端点变为mid 1）；若待查元素关键字值大于中间位置元素的关键字值，则缩小查找区间到原区间的下半部（区间右端点不变，区间左端点变为mid +1）；若待查元素关键字值等于中间位置元素的关键字值，则查找成功，返回该元素的位置值mid。,计算机软件基础,在等概率条件下，查找成功时的平均查找长度为：,结论：当n很大时，二分查找的平均查找长度可近似为log2(n+1) 1。,4算法分析,计算机软件基础,三. 分块查找,分块查找是性能介于顺序查找和二分查找之间的一种查找方法，又称索引顺序查找。,分块查找的使用前提： 1.将线性表分块:将线性表均匀地分成若干块，块内元素不要求有序，但必须保证块间有序，即后一块中元素的关键字值均大于前一块元素的关键字值； 2.建立索引表:建立由各块中最大关键字值和起始位置两个数据项构成的索引表ID。,计算机软件基础,例：若需对如下线性表进行分块查找，如何对其分块及建立索引表。,索引表ID,起始地址addr,1,6,11,最大关键字值key,23,48,86,数据表R,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15,计算机软件基础,1. 基本思想 首先在索引表中查找，确定待查元