华师本科生数据结构课件第8章查找表简.PPT
《华师本科生数据结构课件第8章查找表简.PPT》由会员分享,可在线阅读,更多相关《华师本科生数据结构课件第8章查找表简.PPT(128页珍藏版)》请在启牛文库网上搜索。
1、第第8 8章章 查找表查找表8.1 静态查找表8.2 动态查找树表8.3 哈希表学习提要 熟熟练掌握掌握顺序表和有序表的序表和有序表的查找方法。找方法。熟熟练掌握二叉排序掌握二叉排序树的构造和的构造和查找方法。找方法。掌握二叉平衡掌握二叉平衡树的的维护平衡方法。平衡方法。理解理解B-B-树的特点以及它的特点以及它们的建的建树过程。程。熟熟练掌握哈希表的构造方法,深刻理解哈希表掌握哈希表的构造方法,深刻理解哈希表与其它与其它结构的表的构的表的实质性的差性的差别。掌握描述掌握描述查找找过程的判定程的判定树的构造方法,以及的构造方法,以及按定按定义计算各种算各种查找方法在等概率情况下找方法在等概率情
2、况下查找找成功成功时的平均的平均查找找长度。度。何谓查找表?查找表是由同一类型的数据元素查找表是由同一类型的数据元素(或记录或记录)构成的构成的集合。集合。由于由于由于由于“集合集合集合集合”中的数据元素之间存在着松散的关系,因中的数据元素之间存在着松散的关系,因中的数据元素之间存在着松散的关系,因中的数据元素之间存在着松散的关系,因此查找表是一种应用灵便的结构。此查找表是一种应用灵便的结构。此查找表是一种应用灵便的结构。此查找表是一种应用灵便的结构。对查找表经常进行的对查找表经常进行的操作操作:1)1)1)1)查询查询某个某个某个某个“特定的特定的特定的特定的”数据元素是否在查找表中;数据元
3、素是否在查找表中;数据元素是否在查找表中;数据元素是否在查找表中;2)2)2)2)检索检索某个某个某个某个“特定的特定的特定的特定的”数据元素的各种属性;数据元素的各种属性;数据元素的各种属性;数据元素的各种属性;3)3)3)3)在查找表中在查找表中在查找表中在查找表中插入插入一个数据元素;一个数据元素;一个数据元素;一个数据元素;4)4)4)4)从查找表中从查找表中从查找表中从查找表中删去删去某个数据元素。某个数据元素。某个数据元素。某个数据元素。仅作仅作仅作仅作查询查询查询查询和和和和检索检索检索检索操作的查找表。操作的查找表。操作的查找表。操作的查找表。静态查找表静态查找表在查询之后,还
4、需要将在查询之后,还需要将在查询之后,还需要将在查询之后,还需要将“查询查询查询查询”结果为结果为结果为结果为“不在查找表中不在查找表中不在查找表中不在查找表中”的数据元素的数据元素的数据元素的数据元素插入到插入到插入到插入到查找表查找表查找表查找表中;或者,从查找表中中;或者,从查找表中中;或者,从查找表中中;或者,从查找表中删除删除删除删除其其其其“查询查询查询查询”结结结结果为果为果为果为“在查找表中在查找表中在查找表中在查找表中”的数据元素。的数据元素。的数据元素。的数据元素。动态查找表动态查找表查找表分类查找表分类是数据元素是数据元素(或记录或记录)中某个中某个数据项数据项的值,的值
5、,用以用以标识标识(识别识别)一个数据元素一个数据元素(或记录或记录)。关键字关键字若此关键字识别若此关键字识别唯一的唯一的唯一的唯一的一个记录一个记录,则称之谓则称之谓“主关键字主关键字主关键字主关键字”.若此关键字能识别若此关键字能识别若干若干若干若干记录,则称之谓记录,则称之谓“次关键字次关键字次关键字次关键字”。根据给定的某个值,在查找表中根据给定的某个值,在查找表中根据给定的某个值,在查找表中根据给定的某个值,在查找表中确定一个其关键确定一个其关键确定一个其关键确定一个其关键字等于给定值的数据元素或(记录)字等于给定值的数据元素或(记录)字等于给定值的数据元素或(记录)字等于给定值的
6、数据元素或(记录)查找查找若查找表中存在这样一个记录若查找表中存在这样一个记录若查找表中存在这样一个记录若查找表中存在这样一个记录,则称则称则称则称查找成功查找成功查找成功查找成功,查找结果查找结果查找结果查找结果:给出整个记录的信息给出整个记录的信息给出整个记录的信息给出整个记录的信息,或指示该记录在查找表中的位置或指示该记录在查找表中的位置或指示该记录在查找表中的位置或指示该记录在查找表中的位置;否则称否则称否则称否则称查找不成功查找不成功查找不成功查找不成功,查找结果查找结果查找结果查找结果:给出给出给出给出空记录空记录空记录空记录或或或或空指针空指针空指针空指针。由于查找表中的数据元素
7、之间不存在明显的组织规律,由于查找表中的数据元素之间不存在明显的组织规律,由于查找表中的数据元素之间不存在明显的组织规律,由于查找表中的数据元素之间不存在明显的组织规律,因此因此因此因此不便于查找不便于查找不便于查找不便于查找。为了提高查找的效率,。为了提高查找的效率,。为了提高查找的效率,。为了提高查找的效率,需要在查找表需要在查找表需要在查找表需要在查找表中的元素之间人为地中的元素之间人为地中的元素之间人为地中的元素之间人为地 附加某种确定的关系,换句话说,附加某种确定的关系,换句话说,附加某种确定的关系,换句话说,附加某种确定的关系,换句话说,用另外一种结构来表示查找表。用另外一种结构来
8、表示查找表。用另外一种结构来表示查找表。用另外一种结构来表示查找表。如何进行查找?如何进行查找?查找的方法取决于查找表的结构。查找的方法取决于查找表的结构。查查找找表表(Search Table):是是一一种种以以集集合合为为逻逻辑辑结结构构、以查找为核心运算以查找为核心运算的数据结构。的数据结构。静静态态查查找找表表:只只对对查查找找表表进进行行查查询询某某个个特特定定的的数数据据元元素素或或某某个个特特定定数数据据元元素素的的各各种种属属性性的的操操作作。如如:查查询询成成绩绩表表中中是是否否有有某某学学生生或或该该学学生生某某门门课课程的成绩。程的成绩。动动态态查查找找表表:对对查查找找
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 本科生 数据结构 课件 查找