《数据结构查找更新》由会员分享，可在线阅读，更多相关《数据结构查找更新（79页珍藏版）》请在金锄头文库上搜索。
1、数据结构 与 算法第七讲：查找开场白*2内容提要v查找概论v静态查找表v动态查找表v哈希表*3查找概论*4v查找表(Search Table)：同一类型的数据元素（或记录）构成的集合。v关键字(Key)：数据元素中某个数据项的值，又称键值 。若某关键字可以唯 一地标记一个记录，则称主关键字(Primary Key)。对于可以识别多个数据 元素的关键字，称为次关键字(Secondary Key)。v查找(Searching)就是根据给定的某个值，在查找表中确定一个其关键字等 于给定值的数据元素（或记录）。主关键码主关键字数据元素(记录）次关键字数据项（字段）查找表的种类*5v静态查找表(Stat
2、ic Search Table): 只作查找操作的查找表。v主要操作：v（1）查询某个“特定的”数据元素是否在查找表中v（2）检索某个“特定的”数据元素和各种属性。v应用：查字典/查个人信息等v动态查找表(Dynamic Search Table):在查找过程中同时插入查找表中不 存在的数据元素，或者从查找表中删除已经存在的某个数据元素。v主要操作：v（1）查找时插入数据元素v（2）查找时删除数据元素v应用：清理网站的注册用户等v查找结构：为提高查找效率而专门为查找操作设置的数据结构v如：线性表/树/散列表 等。内容提要v查找概论v静态查找表v动态查找表v哈希表*6顺序表查找v顺序查找(Seq
3、uential Search)又叫线性查找，是最基本的查找技 术。从表中第一个（或最后一个）记录开始，逐个进行记录的关键字 和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找 到所查的记录；如果直到最后一个（或第一个）记录，其关键字和给 定值比较都不等，则表中没有所查记录，查找不成功。*7顺序表查找算法*8/* 顺序查找, a为数组, n为要查找的数组个数, key为要查找的关键字，朴素版 */1.int Sequential_Search(int *a, int n, int key)2. int i;3. for (i=1; iamid)12. low = mid+1;13. e
4、lse14. return mid;15. 16. return 0;17./* 调用参数*/ a =0,1,16,24,35,47,59,62,73,88,99 n = 10 key = 62v折半查找技术，又称二分查找。它的前提是线性表中的记录必须是关键码有序 且采用顺序存储。基本思想是：在有序表中，取中间记录作为比较对象，若给 定值与中间记录的关键字相等，则查找成功；若小于，则在中间记录的左半区 继续查找，否则在右半区继续查找。不断重复，直到查找成功（或失败）。99887362594735241610a下标987654321010lowhighmidlowmidhighmidlowmid
5、时间复杂度：O(logn)折半查找的性能分析*1247大了小了73大了小了24大了小了1大了小了35大了小了164759大了小了88大了小了6299/* 调用参数*/ a =0,1,16,24,35,47,59,62,73,88,99 n = 10 key = 62平均搜索长度注意：对于需要频繁执行插入删除的数据集，不建议使用。插值查找及算法实现*131.int Interpolation_Search(int *a, int n, int key)2.3. int low, high, mid;4. low = 1;5. high = n;6. while (lowamid)12. low
6、= mid+1;13. else14. return mid;15. 16. return 0;17./* 调用参数*/ a =0,1,16,24,35,47,59,62,73,88,99 n = 10 key = 16折半查找需要查找几次？插值查找呢？v为什么一定要折半，而不是折四分之一或者其他呢？插值查找：根据要查找的 关键字key与查找表中最大最小记录的关键字比较后使用插值公式计算下一步 查找范围的查找方法。时间复杂度：O(logn)注意：适合数据分布均匀情况，若极度不均则不是合适选择。斐波那契查找v基本思想：q当key=amid时，查找成功；q当keyamid时，新范围是第mid+1个
7、到第high个，此 时范围个数为Fk-2-1个。*14lowmidhig hFk-1Fk-1-1Fk-2-134921813786553423121100.F下标0 7斐波那契查找的代码实现*151.int Fibonacci_Search(int *a, int n, int key)2.3. int low, high, mid, i, k;4. low = 1; high = n; k = 0;5. while (nFk-1) k+;6. for (i=n; i amid)14. low = mid+1; k = k-2;15. 16. else 17. if (mid 6.#inclu
8、de7.typedef int datatype;8.typedef struct node /* 二叉排序树结点定义 */9. 10. datatype key; /* 结点值 */11. struct node *lchild,*rchild; /* 左、右孩子指针 */12.bsnode;13.typedef bsnode* bstree;二叉排序树的查找运算*241.#include “bstree.h”2./*-二叉排序树的递归查找-*/3./* 在根指针t所指二叉排序树中递归地查找某关键字4. 等于key的数据元素，若查找成功，则返回指向5. 该数据元素结点的指针，否则返回空指针
9、*/6.bstree SearchBST(bsnode* t, datatype x)7. 8. if (t=NULL | x=t-key)9. 10. return t;11. 12. if (xkey) /*递归地在左子树中检索*/13. 14. return SearchBST(t-lchild, x); 15. 16. else /*递归地在右子树中检索*/17. 18. return SearchBST(t-rchild, x); 19. 20.对于一棵给定的二叉排序树， 树中的查找运算很容易实现，其算 法可描述如下：（1）当二叉树为空树时，检索失败；（2）如果二叉排序树根结点的关键
10、字 等于待检索的关键字，则检索成功；（3）如果待检索的关键字小于二叉排 序树根结点的关键字，则用相同的方 法继续在根结点的左子树中检索；（4）如果待检索的关键字大于二叉排 序树根结点的关键字，则用相同的方 法继续在根结点的右子树中检索。二叉排序树的查找算法性能分析v在二叉排序树上进行检索的方法与二分检索相似，和关 键字的比较次数不会超过树的深度。因此，在二叉排序 树上进行检索的效率与树的形状有密切的联系。 v在最坏的情况下，含有n个结点的二叉排序树退化成一 棵深度为n的单支树（类似于单链表），它的平均查找 长度与单链表上的顺序检索相同，即ASL=（n+1）/2。v在最好的情况下，二叉排序树形态
11、比较匀称，对于含有 n个结点的二叉排序树，其深度不超过log2n，此时的平 均查找长度为O（log2n）。 *25304046505560657075 80例如，对于右图中的两棵二叉排序树，其深度分别 是4和10，在检索失败的情况下，在这两棵树上的最大 比较次数分别是4和10；在检索成功的情况下，若检索 每个结点的概率相等，则对于图（a）所示的二叉排序 树其平均查找长度为：ASLa= =对于图（b）所示的二叉排序树其平均查找长度为： ASLb=（1+2+3+4+5+6+7+8+9+10）/10=5.5（b）（a）6040703050 65804655 75二叉排序树的插入运算*261.void
12、 InsertBST(bstree 5. p = t;6. while (p) /* 查找插入位置 */7. if (x = p-key) 8. return;9. f = p; 10. p = (xkey)?p-lchild:p-rchild;11. 12. /* 生成待插入的新结点 */13. p = (bstree)malloc(sizeof(bsnode); 14. p-key = x;15. p-lchild = p-rchild = NULL;16. if (t=NULL) 17. t = p; /* 原树为空 */18. 19. else 20. if (xkey) f-lchi
13、ld = p;21. else f-rchild = p;22. 23.假设待插入的数据元素为x，则二叉 排序树的插入算法可以描述为：1.若二叉排序树为空，则生成一个关键 字为x的新结点，并令其为二叉排序 树的根结点；2.否则，将待插入的关键字x与根结点 的关键字进行比较，若二者相等，则 说明树中已有关键字x，无须插入；3.若x小于根结点的关键字，则将x插入 到该树的左子树中，否则将x插入到 该树的右子树中去。4.将x插入子树的方法与在整个树中的 插入方法是相同的，如此进行下去， 直到x作为一个新的叶结点的关键字 插入到二叉排序树中，或者直到发现 树中已有此关键字为止。 二叉排序树的建立*27
14、1.bstree CreatBST() /*根据输入的结点序列，建立一棵二叉排序树，并返回根结点的地址*/ 2. 3. bstree t=NULL;4. datatype key;5. printf(“n请输入一个以-1为结束标记的结点序列：n“);6. scanf(“%d“, /*输入一个关键字*/7. while (key!=-1) InsertBST( scanf(“%d“, 8. return t; /*返回建立的二叉排序树的根指针*/9.对于输入实例（30，20，40，10，25，45）， 创建二叉排序树的过程如下 ：（a）空树30 （b）插入303020（c）插入20302040（
15、d）插入40302040103020401025302040102545 （e）插入10（f）插入25（g）插入45思考： 1.对于输入实例（30，20，10，25，40，45）或（30，40，45，20，10，25） ，生成的二叉排序树一样吗？ 2.如果是（10，20，25，30，40，45）或（45，40，30，25，20，10）呢？二叉排序树的删除（一）v原则：从二叉排序树中删除一个结点，不能把以该结点为 根的子树都删去，并且还要保证删除后所得的二叉树仍然 满足BST性质v删除操作的一般步骤：(1) 进行查找：查找时，令p指向当前访问到的结点，parent指向其 双亲(其初值为NULL)。开始查找，若树中找不到被删结点则返回，否 则p指向被删结点。 (2) 删去*p：删*p时，应将*p的子树(若有)仍连接在树上且保持BST 性质
