数据结构ppt(c语言版李春葆).ppt

《数据结构ppt(c语言版李春葆).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第八章查找主要内容：查找的定义和基本概念静态查找表哈希表1第2章至第7章中已经介绍了各种线性或非线性的数据结构，在这一章将讨论另一种在实际应用中大量使用的数据结构————查找表。查找表(SearchTable)是由同一类型的数据元素(或记录)构成的集合。由于“集合”中的数据元素之间存在着完全松散的关系，因此查找表是一种非常灵便的数据结构。对查找表经常进行的操作有：(1)查询某个“特定的”数据元素是否在查找表中；(2)检索某个“特定的”数据元素的各种属性；(3)在查找表中插入一个数据元素；(4)从查找表中删除某个数据元素。2

2、静态查找表(StaticSearchTable)：若对查找表仅作查询和检索操作，则称此类查找表为静态查找表。在查找过程中，查找表本身不发生变化。对静态查找表进行的查找操作称为静态查找。动态查找表(DynamicSearchTable)：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素,此类表为动态查找表。查找表的分类：3关键字(Key)：是数据元素(或记录)中某个数据项的值，用它可以标识(识别)一个数据元素(或记录)。若此关键字可以唯一地标识一个记录，则称此关键字为主关键字(Primar

3、yKey)(对不同的记录，其主关键字均不同)。反之，称用以识别若干记录的关键字为次关键字(SecondaryKey)。当数据元素只有一个数据项时，其关键字即为该数据元素的值。4查找(Searching)：根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。若查找表中存在这样的一个记录，则称“查找成功”，查找的结果为给出整个记录的信息，或指示该记录在查找表中的位置；否则称“查找不成功”，此时查找的结果可给出一个“空”记录或“空”指针。如何进行查找?取决于查找表的结构，即记录在查找表中所处的位置。然而，查找

4、表本身是一种很松散的结构，因此，为了提高查找的效率，需要在查找表中的元素之间人为地附加某种确定的关系，即用另外一种结构来表示查找表。5一些约定：典型的关键字类型说明：typedeffloatKeyType;//实型typedefintKeyType;//整型typedefchar*KeyType;//字符串型数据元素类型定义为：typedefstruct{KeyTypekey;//关键字域...//其它域}ElemType;6对两个关键字的比较约定为如下的宏定义：对数值型关键字：#defineEQ(a,b)((a)==(b

5、))#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)78.1静态查找表抽象数据类型静态查找表的定义为：ADTStaticSearchTable{数据对象D：D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同、可唯一标识数据元素的关键字。数据关系R：数据元素

6、同属一个集合。8基本操作P：Create(&ST，n)：操作结果：构造一个含n个数据元素的静态查找表ST。Destroy(&ST)：初始条件：静态查找表ST存在。操作结果：销毁表ST。Search(ST，key)：初始条件：静态查找表ST存在，key为和关键字类型相同的给定值。操作结果：若ST中存在其关键字等于key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。9Traverse(ST，visit())：初始条件：静态查找表ST存在，visit是对元素操作的应用函数。操作结果：按某种次序对ST的每个元素调用

7、函数visit()一次且仅一次，一旦visit()失败，则操作失败。}ADTStaticSearchTable静态查找表可以有不同的表示方法，在不同的表示方法中，实现查找操作的方法也不同。108.1.1顺序表的查找以顺序表或线性链表表示静态查找表，则Search函数可用顺序查找来实现。本节中只讨论它在顺序存储结构模块中的实现。//静态查找表的顺序存储结构typdefstruct{ElemType*elem;//数据元素存储空间基址//建表时按实际长度分配，0号单元留空intlength;//表长度}SSTable；11i0

8、1234567891011513192137566475808892找6464监视哨iiii比较次数=5比较次数：查找第n个元素：1查找第n-1个元素：2……….查找第1个元素：n查找第i个元素：n-i+1查找失败：n+1顺序查找(SequentialSearch)的查找过程：从表中最后一个记录开始，逐