数据结构-2

这份数据结构-2——查找思维导图模板，是数据结构学习者尤其是学生群体攻克查找相关知识难点的实用利器。在数据结构的学习中，查找是一个极为重要的板块，涉及到多种查找方法和复杂的概念、公式，学生往往在理解和记忆上存在较大挑战，而这份思维导图模板能够帮助学生系统地梳理知识，提升学习效率。模板围绕查找展开，首先对查找表进行分类，介绍了静态查找表和动态查找表，以及它们各自包含的查找方法。在顺序查找部分，阐述了其基本思想、适用场景，还提到了查找成功的平均查找长度公式。折半查找作为重点内容，详细说明了其适用条件、查找方法，以及如何根据中间值位置进行判断和下一步操作，同时给出了n个结点最多比较次数的公式和折半查找平均查找长度的公式。此外，模板还设置了考题板块，列举了关于查找运算及查找表的叙述考题，帮助学生巩固知识点。该模板以思维导图的形式呈现，层次分明、逻辑清晰，将查找的各个知识点有机整合。学生可以利用它进行课前预习，对查找知识有初步的整体认识；课堂上结合老师的讲解和模板内容，加深对重点难点的理解；课后复习时，通过模板快速回顾知识点，查漏补缺。

数据结构-2

• 查找
  • 分类： 1 静态查找表有：顺序查找，折半（二分）查找，分块找 2 动态查找表有：二叉排序树，平衡二叉树，B_树，哈希表
  • 顺序查找
    • 基本思想是：从表的一端开始，逐个将记录的关键字和给定值比较，若找到一个记录的关键字与给定值相等，则查找成功；若整个表中的记录均比较过，仍未找到关键字等于给定值的记录，则查找失败。
    • 顺序查找的方法对于顺序存储方式和链式存储方式的查找表都适用。不需要有序！
    • 查找成功的平均查找长度 ASL=（n+1）/2 (n代表有n个元素)； 成功查找的平均比较次数约为表长的一半。
  • 折半查找（重点）
    • 也叫二分查找，只适用于待查找序列中的元素是有序排列的！ 也只适用于顺序存储，不能是链式存储！
    • 设查找表的元素在储在一维数组r[1.⋯n]中，在表中的元素已经按关键字递增方式排序的情况下，进行折半查找的方法是： 1. 首先将待查元素的关键字（Key）值与表r中间位置上（下标为 mid）记录的关键字进行比较，若相等，则查找成功；若key>r[mid].key，则说明待查记录 只可能在后半个子表r[mid+1，⋯,n]中，下一步应在后半个子表中进行查找； 若key<r[mid].key，说明待查记录只可能在前半个子表r[1，…，mid-1］中，下一步应在r的前半个子表中进行查找， 这样逐步缩小范围，直到查找成功或子表为空时失败为止。
    • 注意：中间值位置算出来的若为小数，则应向下取整，如4.5=4， （从0开始的）
    • n个结点最多比较次数：」log2(n)」（下取整） + 1
    • 从折半查找判定树可以看出，查找成功时，折半查找的过程恰好走了一条从根结点到被查找结点的路径，与关键字进行比较的次数即为被查找结点在树中的层数。因此，折半查找在查找成功时进行比较的关键字个数最多不超过树的深度，而具有n个结点的判定树的深度为［log2(n)」(下取整)+1，所以折半查找在查找成功时和给定值进行比较的关键字个数最多为［1og2(n)」+1 (下取整)。
    • 折半查找的平均查找长度=log2(n+1)-1
  • 考题
    • 下面关于查找运算及查找表的叙述，错误的是（57）。（2009年上半年） （57）A.哈希表可以动态创建 B. 二叉排序树属于动态查找表 C. 二分查找要求查找表采用顺序存储结构或循环链表结构 D. 顺序查找方法既适用于顺序存储结构，也适用于链表结构