数据结构第7章_查找.pptVIP

第7章 查找 7.1 基本概念 7.2 静态查找 7.3 动态查找表 7.4 哈希法查找 7.1 基本概念 列表：由同一类型的数据元素(或记录)构成的集合，可 利用任意数据结构实现。 关键字：数据元素某个数据项的值，用它可以标识列表中的一个或一组数据元素。 主关键字：唯一标识列表中的一个数据元素，否则为次关键字。 当数据元素仅有一个数据项时,数据元素值就是关键字。 查找：在一个给定的数据结构中，根据给定的条件查找满足条件的数据元素。 不同的数据结构采用不同的查找方法，查找的效率直接影响数据处理的效率。 查找的结果： 查找成功：找到满足条件的结点 查找失败：找不到满足条件的结点。 静态查找(static search) 在查找过程中，查找表本身的结构不发生变化，只确定是否存在数据元素的关键字值与给定的关键值相等或找出此数据元素的属性 。 动态查找(dynamic search) 在查找过程中，查找表本身的结构将发生变化，包括插入元素(查找不成功时，在查找表中插入关键字为给定值的记录)或删除元素(查找成功时，将查找表中关键字为给定值的记录删除。 （查找算法在查找成功时）平均查找长度：为确定数据元素在列表中的位置，需和给定值进行比较的关键字个数的期望值。 对于长度为n的列表，查找成功时的平均查找长度为： ASL=P1C1+P2C2+…+PnCn 其中Pi为查找列表中第i个数据元素的概率，Ci为找到列表中第i个数据元素时，已经进行过的关键字比较次数。 存储结构可为顺序结构，也可为链式结构。 顺序结构的数据类型定义： #define LIST_SIZE 20 typedef struct { KeyType key; OtherType other_data; }RecordType; typedef struct { RecordType r[LIST_SIZE+1]; /*r[0]为工作单元*/ int length; }RecordList; 【不设置监视哨的顺序查找法】 int SeqSearch(RecordList l，KeyType k) /*不用监视哨法，在顺序表中查找关键字等于k的元素*/ { i=l.length; while(i=1l.r[i].key!=k) i--; if(i=1) return i; else return 0; } 循环条件i=1判断查找是否越界。利用监视哨可省去这个条件，从而提高查找效率。 假设列表长度为n，那么查找第i个数据元素时需进行n-i+1次比较，即Ci=n-i+1。又假设查找每个数据元素的概率相等，即Pi=1/n，则顺序查找算法的平均查找长度为： ASL= = 用折半查找法查找4、70的具体过程，其中mid=(low+high)/2，当highlow时，表示不存在这样的子表空间，查找失败。 假设查找表中各记录的关键字为{4，8，12，15，21，32，38，41，55，67，78，90} 折半查找法的查找过程的折半查找判定树表示：树中结点对应记录，结点值不是记录值，是记录在表中的位置序号 根结点对应表中的中间记录，左子树为前子表，右子树为后子表 折半查找法的查找过程可用的折半查找判定树来表示。树中结点对应记录，结点值不是记录值，是记录在表中的位置序号 查找关键字为70的记录所经过的路线用虚线所示。考虑到存在查找不成功的可能性，折半查找判定树中增加了一系列的外部结点（矩形结点），如果在查找过程中到达外部结点，则意味着查找失败。 折半查找判定树通常不是完全二叉树，但出最底层外为一棵满二叉树 长度为n的有序表，查找成功时最多的比较次数与n个结点的完全二叉树的深度相同，为int(log2n)+1,查找失败时比较次数为int(log2n)+2 折半查找算法 的时间复杂度为O(log2n) 折半查找算法的效率远高于顺序查找算法 折半查找的算法如下： int BinSrch(SqList l，KeyType k) /*在有序表l中折半查找其关键字等于k的元素，若找到，则函数值为该元素在表中的位置*/ { low=0