数据结构-第7章-查找.pptxVIP

7.1查找的基本概念第7章查找查找又称为检索，其功能是从大量的数据元素中找出某个特定的满足给定条件的记录或数据元素。若找到满足给定条件的记录或数据元素，则称查找是成功的，此时查找的结果为给出整个记录的信息，或指示该记录在查找表中位置的指针；相反，若未找到满足给定条件的记录或数据元素，则称查找不成功，此时，查找的结果可给出一个“空”记录或“空”指针。查找的目的一般有如下四种：（1）查找某指定的数据元素在查找表中是否存在；（2）检索某个特定的数据元素的各种属性；（3）在查找表的合理位置上插入一个数据元素；（4）从查找表中删除某个数据元素。

7.1查找的基本概念第7章查找关键字标识数据元素（或记录）中某个数据项的值，用它可以标识一个数据元素（或记录）。若此关键字可以唯一标识一个记录，则称此关键字为主关键字（不同的记录，其主关键字均不同）。反之，把用以识别若干个记录的关键字称为次关键字。当数据元素只有一个数据项时，其关键字即为该数据元素的值。利用关键字的概念，查找运算的功能可确切地表述如下：根据给定的某个关键字值key，在某种数据结构中寻找一个其键值等于key的数据元素。若找到一个这样的数据元素，则称查找成功；否则，称查找不成功。

7.1查找的基本概念第7章查找静态查找（staticsearch）若对查找表只做前两种操作（即，肯定不会改变原查找表的内容），则称此查找为静态查找。动态查找（dynamicsearch）若在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素，则称此查找为动态查找。平均查找长度（averagesearchlength,ASL）为确定所查找的数据元素在查找表中的位置而需和给定关键字进行比较的次数的平均值。ASL是衡量一个查找算法性能好坏的依据,因为查找的过程实际上是“将查找表中各数据元素的关键字与给定的关键字进行比较的过程”，所以比较次数越少，则查找所需的时间就越短，效率就越高。

7.2静态查找表第7章查找7.2.1顺序查找顺序查找是一种最简单也是效率比较低下的查找算法。查找的基本思想是将每个结点的关键字与给定的待查的关键字值key依次进行比较，若当前扫描到的结点关键字值与key相等，则查找成功，返回该数据元素的存储位置；反之，若扫描结束后，仍未找到关键字等于key的结点，则查找失败，返回查找失败标志。顺序查找法既可以采用顺序存储结构，也可以采用链式存储结构。//静态查找表的顺序存储表示#definemaxsize100/*定义最大存储容量*/typedefstruct{datatypedata[maxsize];intlength;}seqtable;/*静态查找表的链式存储表示*/typedefstructnode{datatypedata;structnode*next;}linktable;

7.2静态查找表第7章查找7.2.2折半查找折半查找也称为“二分查找”,其查找效率较高，但要求待查找的数据元素采用顺序存储结构，而且查找表按关键字有序(已经按关键字排好序)。采用折半查找算法在有序表（假设为升序）中查找结点时，首先找到表的中间结点，将其关键字值与给定的要找的值key进行比较，若相等，则查找成功；若当前结点的关键字值大于要找的值key，则继续在表的前半部分进行折半查找，否则继续在表的后半部分进行折半查找。

7.2静态查找表第7章查找7.2.3分块查找分块查找是一种性能介于顺序查找和二分查找之间的查找方法，但它要求先对查找表建立一个索引表，再进行分块查找。索引表建立方法是先对查找表进行分块，要求“分块有序”，所谓“分块有序”是指块内关键字不一定有序，但块间有序，即后一块子表中所有数据元素的关键字值均大于前一块中最大的关键字值。然后，抽取各块中的最大关键字及其起始位置构成一个索引表，如图7-3所示。分块查找方法为分两步进行，先查找索引表，因其有序，故可采用二分查找，以确定待查记录在哪一块，然后，在已确定的块中再进行顺序查找。

7.3动态查找表第7章查找7.3.1二叉排序树1．二叉排序树定义二叉排序树（BinarySortTree）或者是一棵空树，或者是具有下列性质的二叉树：(1)若左子树不空，则左子树上所有结点的值均小于根结点的值；若右子树不空，则右子树上所有结点的值均大于根结点的值。(2)左右子树也都是二叉排序树。从二叉排序树的定义可得出二叉排序树的一个重要性质：按中序遍历该树所得到的中序序列是一个递增有序序列。

7.3动态查找表第7章查找2．二叉排序树的查找过程在二叉排序树中查找关键字值为key的数据元素的基本思想是用给定值key与根结点的关