关键词：

第七章小结

先列出一些基本的概念：

①关键字：数据元素（记录）中某个数据项的值，用它可以表示一个数据元素。

 

②动态查找表/静态查找表：若在查找的过程中进行修改操作（插入或删除），则相应的表为动态查找表，否则为静态查找表。

 

③平均查找长度：为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度。公式如下：ASL=∑PiCi (i=1,2,3,…,n),可以简单以数学上的期望来这么理解。其中：Pi 为查找表中第i个数据元素的概率，Ci为找到第i个数据元素时已经比较过的次数。

 

下图为本章的思维导图

1.　　顺序查找

　　　从表的一端开始，顺序扫描表，依次将扫描到的结点关键字和给定值（假定为a）相比较，若当前结点关键字与a相等，则查找成功；若扫描结束后，仍未找到关键字等于a的结点，则查找失败。

　　    顺序查找也是最普通的一种方法，我们刚开始学习的时候几乎都会用这种查找方法，也就是从头开始，一个一个地进行比较，所以这也是效率最低的一个方法。

　　    适用于线性表的顺序存储结构和链式存储结构。

　　　查找成功时的平均查找长度为： ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;

 2.　　折半查找

    　　搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如                 果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

　　　　

　　　　折半计算mid的公式

　　　　mid = (low+high)/2;
        if(a[mid]==value)
            return mid;
        if(a[mid]>value)
            high = mid-1;
        if(a[mid]<value)
            low = mid+1;

3.　　分块查找

　　　二分查找表使分块有序的线性表和索引表（抽取各块中的最大关键字及其起始位置构成索引表）组成，由于表是分块有序的，所以索引表是一个递增有序表，因此采用顺序或二分查找索引表，以               确定待查结点在哪                 一 块，由于块内无序，只能用顺序查找。　

4.　　树表查找　

　　　

　　　　二叉排序树(Binary Sort Tree)，又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树。
　　　　　　　 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值;
　　　 　　　　若它的右子树不空 ，则右子树上所有结点的值均大于它的根结点的值;
　 　　　　　　它的左、右子树也分别为二叉排序树。

 

 

　　　　平衡二叉树(AVL树)

　　    　　　　平衡二叉树，是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1。

　　   　　　　 从平衡二叉的英文名字(AVL树)，你也可以体会到，它是一种高度平衡的二叉排序树。

　　    　　　　高度平衡意思是说，要么它是一棵空树，要么它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。

　　

 

　

　　B-树

　　　　B树可以看作是对查找树的一种扩展，即他允许每个节点有M-1个子节点。

• • 　　根节点至少有两个子节点

  • 　　每个节点有M-1个key，并且以升序排列

  • 　　位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间

  • 其它节点至少有M/2个子节点

    B+树

  • B+树是对B树的一种变形树，它与B树的差异在于：

  • 有k个子结点的结点必然有k个关键码；
  • 非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。
  • 树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录。

 

5.　　散列表

第七章学习小结(代码片段)

第七章主要学习了很多种查找方式，从最简单的线性表查找到树表的查找到散列表查找，不同的查找方式有不同的优点，下面根据练习来实际应用这些知识。 这个问题的任务很简单：将一个不同的正整数序列插入哈希表，并... 查看详情

第七章学习小结(代码片段)

本章学习了关于查找的算法知识。查找算法的评价指标：关键字的平均查找长度ASL。查找成功的平均查找长度：若查找概率相同，则ASL=（从c1+c2+...+cn）/n若查找概率相同且进行顺序查找，则ASL=（1+2+...+n）/n=（n+1）/2不成功查找算... 查看详情

第七章学习小结(代码片段)

1、线性表的查找　　1.1、顺序查找　　　　（1）从表的一端开始，依次将记录的关键字和给定值进行比较，若某个记录的关键字和给定值相等，则查找成功；反之，若扫描整个表后，仍未找到关键字和给定值相等的记录，则查... 查看详情

数据结构：第七章学习小结(代码片段)

思维导图 算法小结1.顺序查找①基础方法1intSearch(SSTableST,KeyTypekey)23for(i=1;i<=ST.length;i++)45if(key==ST.R[i].key)returni;67return0;//若未查找到则返回08顺序查找②设置监视哨方法1//避免查找过程中每次检测整个表是否查找完毕的步骤2//... 查看详情

第七章学习小结(代码片段)

本章主要学习了查找的相关知识。关于查找，有以下几种基本概念：（1）查找表。按照数据类型可分为数组和链表；按照具体存储逻辑又可分为顺序表、哈希表等等。（2）关键字。作为待查找的元素，在查找表中进行检索。（3... 查看详情

第七章查找学习小结(代码片段)

一、查找及部分基本概念  部分概念： 1.查找表：要进行查找的数据结构，可以是线性表、树表、散列表等。 2.关键字：能够标识一个元素的数据项。 3.动态查找和静态查找：查找过程中可以对查找表进行操作... 查看详情

ds第七章学习记录(代码片段)

一.知识要点若在查找的同时对表做修改操作（如插入和删除），则相应的表称之为动态查找表。平均查找长度          设置监视哨的顺序查找ST.R[O].key=key;for(i=ST.length;ST.R[i].key!=key;--i);returni;//... 查看详情

第七章小结(代码片段)

一、章节概括本章学习了基于不同数据结构的查找，并讨论了不同方法的优缺点和时间复杂度，下面是我制作的思维导图   二、实践本章实践了QQ账号的申请与登陆这一题目，解决问题的过程中，学习了<bits/stdc++.h&g... 查看详情

第7章学习小结(代码片段)

第7章学习小结 上图为第七章的思维导图。在顺序查找中，设置监视哨的顺序查找比较重要。1intSearch_Seq(SSTableST,KeyTypekey)23ST.R[0].key=key;4for(i=ST.length;ST.R[i].key!=key;--i);5returni;6它的时间复杂度为O（n），空间复杂度为O（1）算法比... 查看详情

ds第4章学习小结(代码片段)

...明推荐理由及列出相关链接(或书目名称，具体页码)目前学习过程中存在的困难，待解决或待改进的问题上次博客确定的目标达到了吗？如果没达到，请分析原因接下来的目标一、你对本章内容的小结　　第4章主要学习了串、数... 查看详情

数据结构第七章学习总结(代码片段)

一、第七章内容小结 1.查找的基本概念    2.线性表的查找①顺序查找：从表的一端开始依次将记录的关键字和给定值进行比较，某记录的关键字和定值相等则查找成功；反之，扫描整个表未找到相等记录，则... 查看详情

第七章学习小结

一、本章的思维导图二、总结顺序查找本来以前以为自己打的代码就已经很漂亮了，根本没有再关注还可以再怎么优化它，本章学习到了一个监视哨的概念虽然这个算法的时间复杂度还是O(n)级别的，但是却减少了一半的时间开... 查看详情

第七章小结(代码片段)

概念梳理：1、查找表：是由同一类型的数据元素（或记录）构成的集合。2、关键字：是数据元素（或记录）中某个数据项的值，用它可以标识一个数据元素（或记录）。主关键字：若此关键字可以唯一地标识一个记录，则称此... 查看详情

第七章小结(代码片段)

第七章说实话，就像大梦初醒，一场梦结束之后，这一章就讲完了。可能我吸收的不是很好，所以在接下来的时间，好好的把知识点梳理一遍，做好总结。（1）理一理本章的概念关键字：关键字是数据元素中某个数据项的值。... 查看详情

数据结构第七章小结(代码片段)

1、typedefstruct和struct的区别structStuden1intID;charname;stu1;typedefstructStudent2intID;charname;stu2;Student1是结构体的名字，stu1是一个变量，相当于structStudent1stu1；而stu2是一个变量的类型，相当于structStudent2的别名。 2、召回率也叫查 查看详情

ds|数据结构||第五章小结(代码片段)

    本章主要学习了树和二叉树相关知识，包括二叉树的性质和存储结构（双亲表示法、孩子表示法、孩子兄弟法），二叉树的前、中、后序遍历算法等，还了解了哈夫曼树和哈夫曼编码的构造方法，以及森林与二... 查看详情

第七章学习小结

第七章学习小结一、基本概念（1）关键字：元素中某个数据项的值。关键字仅标识唯一记录时为主关键字，标识若干个记录的教此关键字。（2）查找：根据条件，在查找集合中匹配给定的目标值。（3）查找结果：找到匹配结果... 查看详情

数据结构第七章小结——查找(代码片段)

一、基本概念和专业术语：（1）查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。（2）查找算法分类：　　1）静态查找和动态查找；　　　 注：静态或者动态都是针对查找表而言... 查看详情