软件技术基础教学配套课件张选芳傅茂洺王欣计算机软件技术基础(邮电)1－8

《软件技术基础教学配套课件张选芳傅茂洺王欣计算机软件技术基础(邮电)1－8》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课件课件第一章第一章数据结构数据结构第二章第二章操作系统操作系统第三章第三章软件工程软件工程第四章第四章数据库数据库制作者：张选芳制作者：张选芳Email:zhangxuanfang@126.comEmail:zhangxuanfang@126.com计算机软件技术基础电话电话:5182508:5182508–数据结构11第一单元第一单元第二单元第二单元第三单元第三单元第四单元第四单元第五单元第五单元第六单元第六单元第七单元第七单元第八单元第八单元2计算机软件技术基础–数据结构2第八单元第八

2、单元查找和排序查找和排序3计算机软件技术基础–数据结构31.51.5查找和排序查找和排序1.5.11.5.1查找查找一一..查找的概念查找的概念查找又称检索，它是数据处理中使用查找又称检索，它是数据处理中使用频繁的一种重要操作。频繁的一种重要操作。查找表查找表((searchtable)searchtable)被查找的数据对象是由同一类型的数被查找的数据对象是由同一类型的数据元素据元素((或记录或记录))构成的集合，构成的集合，查找表是一种非常灵活的数据结构。查找表是一种非常灵活的

3、数据结构。给查找带来不便，影响查找的效率。给查找带来不便，影响查找的效率。4计算机软件技术基础–数据结构4关键字关键字((key)key)规定能够标识数据元素规定能够标识数据元素((或记录或记录))的一个的一个数据项或几个数据项为关键字数据项或几个数据项为关键字。。主关键字主关键字((primarykey)primarykey)若此关键字可以唯一地标识一个记若此关键字可以唯一地标识一个记录，则称此关键字为主关键字录，则称此关键字为主关键字；；次关键字次关键字((secondar

4、ykey)secondarykey)它可以标识若干个记录。称为次关键字它可以标识若干个记录。称为次关键字。。当记录只有一个数据项时，它就是该记当记录只有一个数据项时，它就是该记录的关键字。录的关键字。5计算机软件技术基础–数据结构5查找查找((searchingsearching))定义定义根据结定的值，在查找表中查找是否存在根据结定的值，在查找表中查找是否存在关键字等于给定值的记录，关键字等于给定值的记录，查找成功查找成功若存在一个或几个这样的记录，则称查找若存在一个或几个这样的

5、记录，则称查找成功，成功，查找的结果可以是对应记录在查找表查找的结果可以是对应记录在查找表中的位置或整个记录的值。中的位置或整个记录的值。查找不成功查找不成功若表中不存在关键字等于给定值的记若表中不存在关键字等于给定值的记录，则称查找不成功，录，则称查找不成功，查找的结果可以给出查找的结果可以给出一个特定的值或一个特定的值或““空空””指针。指针。6计算机软件技术基础–数据结构6查找应明确下述两个问题查找应明确下述两个问题(1)(1)查找的方法查找的方法在研究各种查找方法时，必须弄清各

6、种方在研究各种查找方法时，必须弄清各种方法所使用的组织方式。法所使用的组织方式。(2)(2)查找算法的评价查找算法的评价衡量一个算法的标准主要有两个衡量一个算法的标准主要有两个时间复杂度时间复杂度n空间复杂度。空间复杂度。ASLPCii平均查找长度平均查找长度i1其中其中:P:Pi为查找第为查找第ii个数据元素的概率个数据元素的概率;;CCi为查为查找到第找到第ii个数据元素时个数据元素时,,需进行的比较次数。需进行的比较次数。7计算机软件技术基础–数据结构7二．二．顺序表的

7、查找顺序表的查找1.1.顺序查找顺序查找基本思想基本思想从第一个元素开始，逐个把元素的关键从第一个元素开始，逐个把元素的关键字值和给定值比较，若某个元素的关键字值字值和给定值比较，若某个元素的关键字值和给定值相等，则查找成功；否则，若直至和给定值相等，则查找成功；否则，若直至第第nn个记录都不相等，说明不存在满足条件个记录都不相等，说明不存在满足条件的数据元素，查找失败。的数据元素，查找失败。顺序查找的适用范围顺序查找的适用范围顺序存储结构组织的查找表的查找顺序存储结构组织的查找表的

8、查找链式存储结构组织的查找表的查找链式存储结构组织的查找表的查找8计算机软件技术基础–数据结构8顺序查找算法顺序查找算法intintseqsearch(intseqsearch(intdata[],data[],intintx)x){{/*/*在表中查找关键字值等于在表中查找关键字值等于xx的元素，若的元素，若找到，则函数值为该元素在表中的位找到，则函数值为该元素在表中的位置，若没有找到，则函数值为置，若没有找到，则函数值为0*/0*/intinti=N;i=N;//N//N为表的长度