数据结构讲义第9章

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

1、数据结构吴润秀南昌工程学院9.1静态查找表9.2动态查找表9.3哈希表目录第九章查找查找的基本概念查找表(SearchTable)：是由同一类型的数据元素（或记录）构成的集合。由于“集合”中的数据元素之间存在着完全松散的关系,因此查找表是一种非常灵便的数据结构。查找表的操作：1、查询某个“特定的”数据元素是否在查找表中。2、检索某个“特定的”数据元素的各种属性。3、在查找表中插入一个数据元素；4、从查找表中刪去某个数据元素。静态查找表：对查找表只作前两种操作，这两种操作统称为“查找”的操作，则称此类查找表为静态查找表。动态查找表：在查找过程

2、中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个元素（也即元素集合可以根据情况动态改变），则称此类表为动态查找表。在日常生活中，人们几乎每天都要进行“查找”工作。例如，在电话号码簿中查阅“某单位”或“某人”的电话号码；在字典中查阅“某个词”的读单和含义等等。其中“电话号码簿”和“字典”都可视作是一张查找表。查找：根据给定的某个值，在查找表中确定一个其关键字等于给定的记录或数据元素。若表中存在这样的一个记录，则称查找是成功的，此时查找的结果为给出整个记录的信息，或指示该记录在查找表中的位置；若表中不存在关键字等于给定值的记录，则称查

3、找不成功。关键字（关键码）、主关键字、次关键字。举例：P214页书，（查找学生的高考成绩）如何进行查找呢？其实，在一个结构中查找某个数据元素的过程依赖于这个数据元素在结构中所处的地位。因此，对表进行查找的方法取决于表中数据元素依何种关系（这个关系是人为地加上的）组织在一起的。举例：查电话号码时，由于电话号码簿是按用户（集体或个人）的名称（或姓名）分类且依笔划顺序编排，则查找的方法就是先顺序查找待查用户的所属类别，然后在此类中顺序查找，直到找到该用户的电话号码为止。又如，查阅英文单词时，由于字典是按单词的字母在字母表中的次序编排的，因此查找时不需要从

4、字典中第一个单词比较起，而只要根据待查单词中每个字母在字母表中的位置查到该单词。同样，在计算机中进行查找的方法也随数据结构不同而不同。但前面我们又说到查找表中的数据元素之间存在着完全松散的关系，这给我们查找带来不便。为此，需在数据元素之间人为地加上一些关系，以例按某种规则进行查找，即以另一种数据结构来表示查找表。一些约定：典型的关键字类型说明：typedeffloatKeyType;//实型typedefintKeyType;//整型typedefchar*KeyType;//字符串型数据元素类型定义为：typedefstruct{KeyTypek

5、ey;//关键字域...}ElemType;对两个关键字的比较约定为如下的宏定义：对数值型关键字#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineLQ(a,b)((a)<=(b))对字符串型关键字#defineEQ(a,b)(!strcmp((a),(b)))#defineLT(a,b)(strcmp((a),(b))<0)#defineLQ(a,b)(strcmp((a),(b))<=0)静态查找表静态查找表的抽象数据类型定义：ADTStaticSearchTable{数据对象D：D是具有

6、相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字。数据关系R：数据元素同属一个集合。基本操作P：Create(&ST,n);操作结果：构造一个含n个数据元素的静态查找表ST。Destroy(&ST);初始条件：静态查找表ST存在。操作结果：销毁表ST。9.1静态查找法Search(ST,key);初始条件：静态查找表ST存在，key为和关键字类型相同的给定值。操作结果：若ST中在在其关键字等于key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。Traverse(ST,Visit());初始条件：静态查

7、找表ST存在，Visit是对元素操作的应用函数。操作结果：按某种次序对ST的每个元素调用函数visit()一次且仅一次。一旦visit()失败，则操作失败。}ADTStaticSearchTable顺序表的查找以顺序表或线性链表表示静态查找表，则Search函数可用顺序查找来实现。静态查找表的顺序存储结构typedefstruct{ElemType*elem;//ElemTypeelem[100];intlength;}SSTable;顺序查找：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成

8、功，找到所查记录；反之，查找不成功。intSearch_Seq(SSTableST,KeyTypekey){ST.elme