North China Electric Power University I 第八章查找表 ★基本概念 ★静态查找表 ★动态查找表 ★Hash法
第八章 查找表 ★ 基本概念 ★ 静态查找表 ★ 动态查找表 ★ Hash法 North China Electric Power University
North China Electric Power University I ★基本念 查找表:是一种以集合为逻辑结构,以查找为核 心运算,同时包括其他运算的数据结构 关鍵字:用来标识数据元素的数据项,简称键。 主关键字:可以唯一标识一个数据元素的关键字。 次关键字:可以标识若干数据元素的关键字。 查找:根据某个给定的K值,在查找表中寻找一 个键值等于K的元素,若找到这样的元素, 则称查找成功,此时的运算结果为该数据 元素在查找表中的位置,否则称查找不成 功,运算结果为一特殊标志
查找表：是一种以集合为逻辑结构，以查找为核 心运算，同时包括其他运算的数据结构。 关键字：用来标识数据元素的数据项，简称键。 ★ 基本概念 主关键字：可以唯一标识一个数据元素的关键字。 次关键字：可以标识若干数据元素的关键字。 查找：根据某个给定的K值，在查找表中寻找一 个键值等于K的元素，若找到这样的元素， 则称查找成功，此时的运算结果为该数据 元素在查找表中的位置，否则称查找不成 功，运算结果为一特殊标志。 North China Electric Power University
North China Electric Power University I 1建表: Create(st) 静态查找表2查找: Search(s,1) 3读表元:Ge(st;pos 查找表 1初始化: Initiate(t 2查找: Search(st,k) 动态查找表3读表元: Get(st, pos) 4插入: Insert(st,k) 5删除: Delete(st,k)
North China Electric Power University 查找表 静态查找表 动态查找表 1.建表：Create(st) 2.查找：Search(st,k) 3.读表元：Get(st,pos) 2.查找：Search(st,k) 3.读表元：Get(st,pos) 1.初始化：Initiate(st) 4.插入：Insert(st,k) 5.删除：Delete(st,k)
North China Electric Power University I ★静态查找表 1)顺序表上的查找:以顺序表作为存储结构,然后在这 个存储结构上实现静态査找表的基本运算 顺序表类型定义如下: Const maxsize=静态査找表的表长; Type rec=record key: Keytype End: sqTable-arraylo. maxsize of rec; n: Integer; 顶序查找过程:假定该查找表有n个记录,首先将要查找 的那个关键字赋给实际上并不存在的第n1个记录的关键 字域,然后从头开始一个一个的向下查找,用计数查 到就送出来看是第几个,若<=n,则查找成功,若=n+1 则查找失败
North China Electric Power University ★ 静态查找表 1)顺序表上的查找：以顺序表作为存储结构，然后在这 个存储结构上实现静态查找表的基本运算。 顺序表类型定义如下： Const maxsize=静态查找表的表长; Type Rec=Record key:KeyType; … End; sqTable=Array[0..maxsize] of Rec; n:Integer; 顺序查找过程：假定该查找表有n个记录，首先将要查找 的那个关键字赋给实际上并不存在的第n+1个记录的关键 字域，然后从头开始一个一个的向下查找，用i来计数,查 到就送出来看i是第几个，若i<=n，则查找成功，若i=n+1 则查找失败
North China Electric Power University I Procedure Sqsearch(r:sq Table; ke KeyType); begin rn+1. key: =k; l; while(rli. key< >k) do i:=i+1 if i<=n then Write(Succ i=,i) else write( Unsucc’); End: 平均查找长度:为确定某元素在表中某位置所进行的比 较次数的期望值 在长度为n的表中找某一元素,查找成功的平均查找长度 ASL=∑PC1
North China Electric Power University Procedure SqSearch(r:sqTable;k:KeyType); Begin r[n+1].key:=k; i:=1; while (r[i].key< >k) Do i:=i+1; if i<=n then Write(‘Succ i=’,i) else Write(‘Unsucc’); End; 平均查找长度：为确定某元素在表中某位置所进行的比 较次数的期望值。 在长度为n的表中找某一元素，查找成功的平均查找长度: ASL=∑PiCi