《数据结构课件第九章.ppt》由会员分享，可在线阅读，更多相关《数据结构课件第九章.ppt（43页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、查找查找和和排序排序是数据处理系统中最重要的两个操作；是数据处理系统中最重要的两个操作；其次是其次是插入插入、删除删除操作；操作；讨论查找、排序，不可避免要涉及讨论查找、排序，不可避免要涉及文件文件、记录记录、关键字关键字等概念。等概念。文件文件查找表查找表，是由同一类型的数据元素，是由同一类型的数据元素(记录记录)构成的集合构成的集合记录记录构成文件的数据元素，是文件中可存取的数据的基本单位构成文件的数据元素，是文件中可存取的数据的基本单位字段字段数据项，数据的最小单位数据项，数据的最小单位关键字关键字某个可以用来标识记录的数据项某个可以用来标识记录的数据项主关键字主关键字某个可以用来某个可
2、以用来唯一唯一标识记录的数据项标识记录的数据项次关键字次关键字可以用来识别若干记录的数据项可以用来识别若干记录的数据项第九章第九章 查找查找D01曲守宁曲守宁数据库数据库004S01王永燕王永燕数据结构数据结构003L01潘玉奇潘玉奇程序设计程序设计002S01严蔚敏严蔚敏数据结构数据结构001课程号课程号课程名课程名教师教师课程类别课程类别课程安排表课程安排表文件文件记录记录数据数据项项主关键主关键字字次关键次关键字字对对文件经常进行的操作有文件经常进行的操作有:1)查询某个查询某个“特定特定”的数据元素是否存在的数据元素是否存在4)对数据元素进行排序对数据元素进行排序2)插入某个数据元素插
3、入某个数据元素3)删除某个数据元素删除某个数据元素查找算法查找算法排序算法排序算法不管何种操作，都遵循一个重要的性质不管何种操作，都遵循一个重要的性质:都是对主关键字操作都是对主关键字操作9.1 静态查找静态查找9.1.1 顺序查找顺序查找从表最后一个记录开始，逐个向前进行记录关键字和给定值的比较，从表最后一个记录开始，逐个向前进行记录关键字和给定值的比较，相等，查找成功；相等，查找成功；不等，比较下一个记录；不等，比较下一个记录；思想思想:直至第一个记录，若均不等，则查找不成功。直至第一个记录，若均不等，则查找不成功。12.n-2n-1nTomAnnieJohnRoseJack查找查找 Jo
4、hn 比较比较 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=10midhigh=mid 1=9highhigh a2a3,可组成六种不同的输入序列。问其中哪几种输入序列所构造的二叉排序树的高度为3？