数据结构.第九章ppt课件

1、查找和排序是数据处置系统中最重要的两个操作；查找和排序是数据处置系统中最重要的两个操作；其次是插入、删除操作；其次是插入、删除操作；讨论查找、排序，不可防止要涉及文件、记录、关键字等概念。讨论查找、排序，不可防止要涉及文件、记录、关键字等概念。文件文件查找表，是由同一类型的数据元素查找表，是由同一类型的数据元素(记录记录)构成的集合构成的集合记录记录构成文件的数据元素，是文件中可存取的数据的根本单位构成文件的数据元素，是文件中可存取的数据的根本单位字段字段数据项，数据的最小单位数据项，数据的最小单位关键字关键字某个可以用来标识记录的数据项某个可以用来标识记录的数据项主关键字主关键字某个可以用来

2、独一标识记录的数据项某个可以用来独一标识记录的数据项次关键字次关键字可以用来识别假设干记录的数据项可以用来识别假设干记录的数据项第九章第九章 查找查找D01曲守宁曲守宁数据库数据库004S01王永燕王永燕数据构造数据构造003L01潘玉奇潘玉奇程序设计程序设计002S01严蔚敏严蔚敏数据构造数据构造001课程号课程号课程名课程名教师教师课程类别课程类别课程安排表课程安排表文件文件记录记录数据数据项项主关键主关键字字次关键次关键字字对文件经常进展的操作有对文件经常进展的操作有:1) 查询某个查询某个“特定的数据元素能否存在特定的数据元素能否存在4) 对数据元素进展排序对数据元素进展排序2) 插入

3、某个数据元素插入某个数据元素3) 删除某个数据元素删除某个数据元素查找算法查找算法排序算法排序算法不论何种操作，都遵照一个重要的性质不论何种操作，都遵照一个重要的性质:都是对主关键字操作都是对主关键字操作9.1 静态查找静态查找9.1.1 顺序查找顺序查找从表最后一个记录开场，逐个向前进展记录关键字和给定值的比较，从表最后一个记录开场，逐个向前进展记录关键字和给定值的比较，相等，查找胜利；相等，查找胜利；不等，比较下一个记录；不等，比较下一个记录；思想思想:直至第一个记录，假设均不等，那么查找不胜利。直至第一个记录，假设均不等，那么查找不胜利。12. . .n-2n-1nTomAnnieJoh

4、nRoseJack查找查找 John 比较比较 2 次次查找查找 Jack 比较比较 n - 1 次次假设查找不存在假设查找不存在比较比较 n 次次9.1.2 有序表的查找有序表的查找表中数据元素按照主关键字顺序陈列。表中数据元素按照主关键字顺序陈列。 折半查找折半查找 斐波那契查找斐波那契查找 插值查找插值查找5 ，13 ，19 ，21 ，37 ，56 ，64 ，75 ，80 ，88 ，92折半查找折半查找5 ，13 ，19 ，21 ，37 ，56 ，64 ，75 ，80 ，88 ，92lowhighmid = ( low + high ) / 2查找查找 211 2 3 4 5 6 7 8 9 10 11midmid = 6high = mid 1 = 5highmid = 3midlow = mid + 1 = 4lowmid = 4mid找到找到查找查找 85lowhighmid = 6midlow = mid + 1 = 7lowmid = 9midlow = mid + 1 = 10lowmid = 10