数据结构第九章

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

1、第九章查找※教学内容：静态查找表(顺序表,有序表,索引顺序表)；动态查找表(二叉排序树,平衡二叉树,B-树)的建立和查找；哈希表的建立，查找及分析※教学重点：顺序查找，折半查找和索引查找的方法；二叉排序树的构造方法；二叉平衡树的旋转平衡方法；B-树的建立过程；哈希表的构造方法；计算各种查找方法在等概率情况下查找成功时和失败时的平均查找长度※教学难点：二叉平衡树的旋转平衡方法何谓查找表？查找表是由同一类型的数据元素(或记录)构成的集合。由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。对查找表经常进行的操作:1)查询某个“特定的”数据元素是否在查找表中

2、；2)检索某个“特定的”数据元素的各种属性；3)在查找表中插入一个数据元素；4)从查找表中删去某个数据元素。查找表可分为两类:静态查找表仅作查询和检索操作的查找表为静态查找表。动态查找表有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中；或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素,此类表为动态查找表。几个概念:关键字用来标识一个数据元素（或记录）的某个数据项的值，称为关键字。主关键字若此关键字可唯一地标识一个记录，则称此关键字是主关键字；次关键字反之，用以识别若干记录的关键字是次关键字。查找根据给定的某个值，在查找表中确定一个其关键

3、字等于给定值的数据元素或(记录)。若查找表中存在这样一个记录，则称“查找成功”。查找结果给出整个记录的信息，或指示该记录在查找表中的位臵；否则称“查找不成功”。查找结果给出“空记录”或“空指针”。如何进行查找？查找的方法取决于查找表的结构,即表中数据元素是依何种关系组织在一起的。由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。为了提高查找的效率，需要在查找表中的元素之间人为地附加某种确定的关系，换句话说，用另外一种结构来表示查找表。9.1静态查找表9.2动态查找树表9.3哈希表9.1静态查找表抽象数据类型静态查找表的定义：ADTStaticSearchTable

4、{数据对象D：D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素。数据关系R：数据元素同属一个集合。基本操作P：Create(&ST,n);Destroy(&ST);Search(ST,key);Traverse(ST,Visit());}ADTStaticSearchTableCreate(&ST,n);操作结果：构造一个含n个数据元素的静态查找表ST。Destroy(&ST);初始条件：静态查找表ST存在；操作结果：销毁表ST。Search(ST,key);初始条件：静态查找表ST存在，key为和查找表中元素的关键字类型相同的给定值；操作

5、结果：若ST中存在其关键字等于key的数据元素，则函数值为该元素的值或在表中的位臵，否则为“空”。Traverse(ST,Visit());初始条件：静态查找表ST存在，Visit是对元素操作的应用函数；操作结果：按某种次序对ST的每个元素调用函数Visit()一次且仅一次，一旦Visit()失败，则操作失败。假设静态查找表的顺序存储结构为typedefstruct{//数据元素存储空间基址，ElemType*elem;//建表时按实际长度分配，0号单元留空intlength;//表的长度}SSTable;数据元素类型的定义为:typedefstruct{keyTypekey;

6、//关键字域……//其它属性域}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)n一、顺序查找表1n1ASLss(ni1)ni12二、有序查找表nh11j1n1ASLbsCi

7、j2log2(n1)1ni1nj1n三、静态查找树表四、索引顺序表一、顺序查找表以顺序表或线性链表表示静态查找表（1）回顾顺序表的查找过程：kkkST.elem213788199205645680751301234567891011ST.Length假设给定值e=64,要求ST.elem[k]=e,问:k=?（2）从前往后查的算法intlocation(SqListL,ElemType&e,Status(*compare)(ElemType,ElemType)){k=1;