数据结构讲义第9章查找

《数据结构讲义第9章查找》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第9章查找9.1基本概念和术语9.2静态查找表9.2.1顺序查找9.2.2折半查找9.2.3分块查找9.3动态查找表9.3.1二叉排序树9.3.2平衡二叉树9.3.3B-树和B+树9.4哈希表9.4.1什么是哈希表9.4.2哈希函数的构造方法9.4.3处理冲突的方法9.4.5哈希表的查找和分析9.5小结9.1基本概念和术语1数据项(也称项或字段):是具有独立含义的标识单位，是数据不可分割的最小单位。2组合项由若干项、组合项构成。3数据元素（记录）是由若干项、组合项构成的数据单位，是在某一问题中作为整体进行考虑和处理的基本单位。9.1基本概念和术语4关键码（key）

2、关键码是数据元素（记录）中某个项或组合项的值，用它可以标识一个数据元素（记录）。能唯一确定一个数据元素（记录）的关键码，称为主关键码(PrimaryKey)；不能唯一确定一个数据元素（记录）的关键码，称为次关键码(SecondaryKey)。9.1基本概念和术语5查找表(SearchTable)是由具有同一类型（属性）的数据元素组成的集合（又称为字典）。分为静态查找表和动态查找表两类:静态查找表(StaticSearchTable)：仅对查找表进行查找操作，而不能改变的表；动态查找表(DynamicSearchTable)：对查找表除进行查找操作外，允许向表中插入

3、或删除表中数据元素的表。9.1基本概念和术语6.查找(searching)按给定的某个值kx，在查找表中确定一个其关键码等于kx的数据元素（记录）。9.1基本概念和术语7数据元素类型说明typedefstruct{/*出生日期类型定义*/charyear[5]；/*年：用字符型表示，宽度为4个字符*/charmonth[3]；/*月：字符型，宽度为2*/chardate[3]；/*日：字符型，宽度为2*/}BirthDate；typedefstruct{/*数据元素类型定义*/charnumber[7]；/*学号：字符型，宽度为6*/charname[9]；/*姓

4、名：字符型，宽度为8*/charsex[3]；/*性别：字符型，宽度为2*/BirthDatebirthdate；/*出生日期:构造类型*/charcomefrom[21]；/*来源：字符型，宽度为20*/intresults；/*成绩：整型，宽度由“C语言”决定*/}ElemType；9.1基本概念和术语8查找表的类型定义例：用线性表表示查找表：（1）用顺序表来表示查找表：typedefMAXSIZE1000typedefstruct{//顺序存储结构ElemTypeelem[MAXSIZE+1]；intlength;}SStable;（2）用单链表表示查找表t

5、ypedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;用其它形式表示的线性表的类型定义在以后的章节中解释。9.1基本概念和术语说明：本章以后讨论中，涉及的关键码类型和数据元素类型统一说明如下：typedefstruct{KeyTypekey；/*关键码字段，可以是整型、字符型、构造型等*/……/*其它字段*/}ElemType；9.2静态查找表9.2.1顺序查找9.2.2折半查找9.2.3分块查找9.2静态查找表（基于线性表的查找）静态查找表结构静态查找表是数据元素的线性表，可以是基于数组

6、的顺序存储或以线性链表存储。typedefMAXSIZE1000typedefstruct{//顺序存储结构ElemTypeelem[MAXSIZE+1]；intlength;}SStable;typedefstructLNode{//链式存储结构ElemTypedata;structLNode*next;}LNode,*LinkList;9.2静态查找表（基于线性表的查找）9.2.2顺序查找(SequentialSearch)查找方法：从表的一端开始，向另一端逐个按给定值kx与关键码进行比较，若找到，查找成功，并给出数据元素在表中的位置；若整个表检测完，仍未找到

7、与kx相同的关键码，则查找失败，给出失败信息。例：给定kx=56,90，在下表中进行顺序查找。1913372105567592648088012345678910119.2静态查找表（基于线性表的查找）9.2.1顺序查找//不设置监视哨的顺序查找算法intsearch_Seq(SSTableST，KeyTypekx){i=l.length;while(i>=1&&ST.elem[i].key!=kx)i--;returni;}9.2静态查找表（基于线性表的查找）9.2.1顺序查找【算法9.1】以顺序存储为例，数据元素从下标为1的数组单元开始存放，0号单元留空。in

8、tsear