C语言程序设计与数据结构 -刘信杰 C语言程序设计与数据结构 课件第15章.ppt

C语言程序设计与数据结构 第15章 查找与排序 总体要求： 掌握查找与排序的基本概念； 掌握顺序查找和二分查找的算法； 掌握直接插入排序、简单选择排序、冒泡排序的算法； 学习重点： 查找的有关算法：顺序查找、折半查找； 常用的排序方法：插入排序、交换排序。 主要内容 15.1 基本概念 15.2 查找算法介绍 15.3 排序算法介绍 15.4 典型习题分析解答 15.1基本概念 15.1.1 查找的基本概念 查找表(Search Table) 是由同一类型的数据元素(或记录)构成的集合。 若对查找表只作前两种统称为“查找”的操作，则称此类查找表为静态查找表(Static Search Table)。若在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素，则称此类表为动态查找表(Dynamic Search Table)。本章集中讨论静态查找表。????所谓“查找”即为在一个含有众多的数据元素(或记录)的查找表中找出某个“特定的”数据元素(或记录)。 ???? 关键字(Key) 是数据元素(或记录)中某个数据项的值，用它可以标识(识别)一个数据元素(或记录)。若此关键字可以唯一地标识一个记录，则称此关键字为主关键字(Primary Key)(对不同的记录，其主关键字均不同)。反之，称用以识别若干记录的关键字为次关键字(Secondary Key)。当数据元素只有一个数据项时，其关键字即为该数据元素的值。 查找(Searching) 根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。若表中存在这样的一个记录，则称查找是成功的，查找的结果为给出整个记录的信息，或指示该记录在查找表中的位置；若表中不存在关键字等于给定值的记录，则称查找不成功，此时查找的结果可给出一个“空”记录或“空”指针。 15.1.2 排序的基本概念 ?排序(Sorting)是计算机程序设计中的一种重要操作，它的功能是将一个数据元素(或记录)的任意序列，重新排列成一个按关键字有序的序列。 假设含n个记录的序列为 {R1，R2，…，Rn} ，若在排序后的序列中 Ri仍领先于Rj，则称所用的排序方法是稳定的；反之，若可能使排序后的序列中Rj领先于Ri，则称所用的排序方法是不稳定的。 由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，可将排序方法分为两大类：一类是内部排序，指的是待排序记录存放在计算机随机存储器中进行的排序过程；另一类是外部排序，指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。 15.2 查找算法介绍 15.2.1 顺序查找 顺序查找(Sequential Search)的查找过程为： 从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，若直至第一个记录，其关键字和给定值比较都不等，则表明表中没有所查记录，查找不成功。此查找过程可用下列算法描述。 【算法15.1】顺序查找的算法：????int Search_Seq(Sqlist ST，KeyType key) { ???//在顺序表ST中顺序查找其关键字等于key的数据元素。 //若找到，则函数值为该元素在表中的位置，否则为0。 ST.r[0].key = key; //0号单元作为监视哨???????? for( i=ST.length; !EQ (ST.r[i].key , key); --i ); //从后往前找???????????? return i； //找不到时，i为0????} // End of Search_Seq ?查找操作的性能分析: 15.2.2 折半查找 折半查找(BinarySearch)的查找过程是：先确定待查记录所在的范围(区间)，然后逐步缩小范围直到找到或找不到该记录为止。(具体查找过程见第7章) 算法如下： ???//在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0。 【算法15.2】折半查找的算法： ? int binsrch(Sqlist L, int key) { int mid,low,high,find; low=1; high=L.length;find=0; /*置区间初值*/ while ((low=high) (!find)) { mid=(low+high)/2; /*求中点*/ if (k= = L.r[mid].key) find=1; /*已查到*/ else i