资源描述：
《算法13--静态查找表.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第8章查找本章主要内容8.1静态查找表8.2动态查找表8.3哈希表2基本概念1．什么是查找表是由同一类型的数据元素(或记录)组成的数据集合。2.对查找表经常进行的操作1）查询某个“特定的”数据元素是否在查找表中；2）检索某个“特定的”数据元素的各种属性；3）在查找表中插入一个数据元素；4）从查找表中删去某个数据元素。33.查找表分类动态查找表静态查找表4.关键字是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。若此关键字可以识别唯一的一个记录，则称之谓“主关键字”。若此关键字能识别若干记录，则称之谓“次关键字”。45.查找根据给定的某个值
2、，在查找表中确定一个其关键字等于给定值的数据元素或(记录)。若查找表中存在这样一个记录，则称“查找成功”，查找结果：给出整个记录的信息，或指示该记录在查找表中的位置；否则称“查找不成功”，查找结果：给出“空记录”或“空指针”。5例：高考成绩表示准考证号姓名各科成绩总分政治语文外语数学物理化学生物...179325179326179327......陈红陆华张平.......847685......768488......746573......938779......876962......765763......877178......635455..typede
3、ffloatKeyType;//实型typedefintKeyType;//整型typedefchar*KeyType;//字符串型数据元素类型定义为：typedefstruct{KeyTypekey;//关键字域//其它域}ElemType;。典型的关键字类型说明：对两个关键字的比较约定为如下的宏定义：//对数值型关键字#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineLQ(a,b)((a)<=(b))//对字符串型关键字#defineEQ(a,b)(!Strcmp((a),(b)))#defineLT(a
4、,b)(Strcmp((a),(b))<0)#defineLQ(a,b)(Strcmp((a),(b))<=0)典型的关键字类型说明：对两个关键字的比较约定为如下的宏定义：//对数值型关键字#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)典型的关键字类型说明：
5、静态查找数据类型定义：ADTStaticSearchTable{数据对象D：D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字。数据关系R：数据元素同属一个集合。8.1静态查找表基本操作P初始条件操作结果Create(&ST,n)构造一个含n个数据元素的静态查找表ST。Destroy(&ST)静态查找表ST存在。销毁表ST。Search(ST,key)静态查找表ST存在，key为和关键字类型相同的给定值。若ST中存在其关键字等于key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。Traverse(ST,Visit
6、())静态查找表ST存在，Visti是对元素操作的应用函数。按某种次序对ST的每个元素调用函数visit()一次且仅一次。一旦visit()失败，则操作失败。8.1.1顺序表的查找//静态查找表的顺序存储结构：typedefstruct{ElemType*elem;//数据元素存储空间基址，建表时按实长度分配，0号单元留空intlength;//表长度}SSTable;8.1.1顺序表的查找intSearch_Seq(SSTableST,KeyTypekey){ST.elem[0].key=key;//“哨兵”for(i=ST.length;!EQ(ST.elem[
7、I].key,key);――i);//从后往前找Returni;//找不到时，i为0}//Search_Seq“顺序”的含义：从表尾（或表头）开始以顺序方式搜索查找表，将关键字与给定值进行比较。查找的顺序与数据元素的存储位置有关系，与数据元素的值没有关系。ST.elem回顾顺序表的查找过程：假设给定值e=64,要求ST.elem[i]=e,i=?iii207ST.elemiST.elemi60ikval=64kval=60i64ii哨兵改进查找成功时平均查找长度(ASL)为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值其中:n为表长,Pi为查找
