《数据结构查找第九章》由会员分享，可在线阅读，更多相关《数据结构查找第九章（100页珍藏版）》请在金锄头文库上搜索。
1、第九章 查找,9.1基本概念 9.2静态查找表 9.3动态查找表 9.4哈希表,基本概念,查找表：是由同一类型的数据元素(或记录)构成的集合。 静态查找表：对查找表只作查询或检索操作 动态查找表：在对查找表进行查找过程中加入插入和删除操作 查找：在一个含有众多的数据元素(或记录)的查找表中找出某个“特定的”数据元素(或记录). 关键字：是数据元素(或记录)中某个数据项的值,用它可以标识一个数据元素(或记录). 主关键字：某关键字可以唯一标识一个记录。 次关键字：用以识别若干记录的关键字,影响查找效率的因素,1.数据结构(查找表的存储结构) 2.查找算法 3.记录的存放形式(有序,无序),典型的
2、关键字类型说明和数据元素类型说明：Typedef float KeyType; /实型Typedef int KeyType; /整型Typedef char *KeyType;/字符串型 数据元素类型定义为：typedef struct KeyType key; /关键字域 /其它域ElemType;,对两个关键字的比较约定为如下的宏定义 /对数据类型关键字 #define EQ(a ,b) (a)= =(b) #define LT(a ,b) (a) (b) #define LQ(a ,b) (a)= (b) /对字符串型关键字 #define EQ(a ,b) (!strcmp(a),(
3、b) #define LT(a ,b) (strcmp(a),(b)0) #define LQ(a ,b) (strcmp(a),(b)=0),9。2静态查找表,顺序表的查找 有序表的查找 索引顺序表的查找,抽象类型静态查找表定义为： ADT StaticSearchTable 数据对象D：D是具有相同特性的数据元素的集合。各数据元素均含有类型相同，可唯一数据元素的关键字 数据关系R：数据元素同属一个集合 基本操作 P： Create( 操作结果：构造一个含n各数据元素的静态查找表ST,Destroy ( 初始条件：静态查找表ST存在，key为和关键字类型相同的给定值。 操作结果：若ST中存在
4、其关键字等于key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”,Traverse(ST,Visit( ); 初始条件：静态查找表ST存在，Visit识对元素操作的应用函数 操作结果：按某种次序对ST的每个元素调用函数visit( )一次仅一次。一旦visit( )失败，则操作失败。 ADT StaticSearchTable,以顺序表或线性链表表示静态查找表。静态查找表的顺序存储结构： Typedef struct ElemType *elem; /数据元素存储空间基址，建表时按实际长度分/配，0号单元留空int length; /表长度 SSTable;,顺序表的查找,顺序查
5、找的查找过程从表中最后一个记录开始，逐个进行记录的关键字 和给定值的比较，若某个记录的关键字和给定值比较相 等，则查找成功，找到所查记录；反之，若直至第一个 记录，其关键字和给定值比较都不相等，则表明表中没 有所查记录，查找不成功。 顺序查找的缺点：平均查找长度较大优点：算法简单且适应面广,顺序查找,顺序查找算法实现,int Search_Seq(SSTable ST,KeyType key) /在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0ST.elem0.key=key; /”哨兵“for (i=ST.length; !EQ(ST.ele
6、mi.key,key);-i);/从后往前找return i; /找不到时，i为0 /Search_Seq,顺序查找操作的性能分析,平均查找长度(Average Search Length)为确定记录在查找表中的位置,需要和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度.对于n个记录的表,查找成功时的平均查找长度为ASL= i=1 n pi ci pi :为查找表中第i个记录的概率ci :为查找到表中其关键字与给定值相等的第i个记录时,和给定值已经进行过比较的关键字个数.,顺序查找平均查找长度,在顺序查找过程中, ci取决于所查记录 在表中的位置.一般情况下ci=n-
7、i+1 假设每个记录的查找概率相等 即pi=1/n 则在等概率下顺序查找平均查找长度为: ASL ss = i=1 n pi ci = 1/ni=1 n (n-i+1 )ASL ss =(n+1)/2,以有序表作为静态查找表时。折半查找的查找过程：先确定待查记录所在的范围(区间),然后逐步缩小范围直 到找到或找不到该记录为止，一般折半查找都是以处于区间 中间位置记录的关键字和给定值比较，若相等，则查找成功 若不等，则缩小范围，直至新的区间中间位置记录的关键字 等于给定值或者查找区间的大小小于0时（表明查找不成功 ）为止。,有序表的查找,折半查找算法,int Search_Bin(SSTable
8、 ST,KeyType key) /在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0 low=1; high=ST.length; /置区间初值 while (low45,6153,61data.key) return (T); /查找结束else if LT(key,T-data.key) return (SearchBST(T-lchild.key);/在左子树中继续查找else return (SearchBST(T-rchild,key);/在右子树中查找 /SearchBST,二叉排序树查找算法,插入过程：二叉排序树的结构通常不时一次
9、生成的， 而是在查找过程中，当树中不存在关键字等于 给定值的结点时再进行插入。新插入的结点一 定是一个新添加的叶子结点，并且是查找不成 功时查找路径上访问的最后一个结点的左孩子 或右孩子结点,二叉排序树的插入,例：查找的关键字序列为45,24,53,45,12,24,90则生成的二叉排序树如图：,空树,Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree /在右子树中查 /SearchBST,二叉排序树的插入算法,Status InsertBST(BiTree ,if (!p) T=s; /被插结点*s为新的根结点else if LT(e.key,p-data.key) p-lchild=s; /被插结点*s为左孩子else p-rchild=s; /被插 结点*s为右孩子return TRUE;else return FALSE; /树中已有关键字相同的结点，不再插入 /Insert BST,二叉排序树的删除,设在二叉排序树上被删结点为*p(指向结点的 指针p),其双亲结点为*f（结点指针为f)，且不失 一般性，可设*p是*f的左孩子 删除分三种情况： 若*p结点为叶子结点，既PL和PR均为空树。由于删去叶子结点不破坏整棵树的结构，则只需修改其双亲结点的指针即可,
