数据结构-查找DS-chap.ppt

南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 1 1第第8 8章章 查找查找南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 2 2第第8 8章章 查找查找主要内容主要内容n第第2 2章至第章至第7 7章章线性或非线性的数据结构线性或非线性的数据结构n本章本章查找表查找表（实际应用中大量使用（实际应用中大量使用 ）n静态查找表及查找算法静态查找表及查找算法n顺序表顺序表n有序表有序表n静态树表静态树表n索引顺序表索引顺序表n动态查找表及查找算法动态查找表及查找算法n二叉排序树二叉排序树n平衡的二叉排序树平衡的二叉排序树nB B树树n哈希表及查找算法哈希表及查找算法n哈希表哈希表南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 3 3第第8 8章章 查找查找重点与难点重点与难点n本章的重点本章的重点n静态查找表及查找算法静态查找表及查找算法n顺序表顺序表顺序查找顺序查找n有序表有序表折半查找折半查找n动态查找表及查找算法动态查找表及查找算法n二叉排序树二叉排序树查找、建立与删除查找、建立与删除n哈希表及查找算法哈希表及查找算法n哈希表哈希表建立、查找建立、查找南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 4 4第第8 8章章 查找查找重点与难点重点与难点n本章的难点本章的难点n静态查找表及查找算法静态查找表及查找算法n静态树表静态树表n动态查找表及查找算法动态查找表及查找算法n二叉排序树二叉排序树查找、建立与删除查找、建立与删除n平衡的二叉排序树平衡的二叉排序树nB B树树n哈希表及查找算法哈希表及查找算法n哈希表哈希表建立、查找建立、查找南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 5 5第第8 8章章 查找查找基本概念基本概念1.1.关键字关键字(Key)是数据元素是数据元素(或记录或记录)中某个数据项的值，用中某个数据项的值，用它可以标识它可以标识(识别识别)一个数据元素一个数据元素(或记录或记录)。若此关键字可。若此关键字可以唯一地标识一个记录，则称此关键字以唯一地标识一个记录，则称此关键字为主关键字为主关键字(Primary Key)(Primary Key)(对不同的记录，其主关键字均不同对不同的记录，其主关键字均不同)。反之，。反之，称用以识别若干记录的关键字为称用以识别若干记录的关键字为次关键字次关键字(Secondary Key)(Secondary Key)。当数据元素只有一个数据项时，其关键字即为该数据元素当数据元素只有一个数据项时，其关键字即为该数据元素的值。的值。2.2.查找查找(Searching)根据给定的某个值，在查找表中确定根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。若表中存在一个其关键字等于给定值的记录或数据元素。若表中存在这样的一个记录，则称查找是成功的，查找的结果为给出这样的一个记录，则称查找是成功的，查找的结果为给出整个记录的信息，或指示该记录在查找表中的位置；若表整个记录的信息，或指示该记录在查找表中的位置；若表中不存在关键字等于给定值的记录，则称查找不成功，此中不存在关键字等于给定值的记录，则称查找不成功，此时查找的结果可给出一个时查找的结果可给出一个“空空”记录或记录或“空空”指针。指针。南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 6 6第第8 8章章 查找查找基本概念基本概念n查找表查找表(SearchTable)：由同一类型的数据元素：由同一类型的数据元素(或或记录记录)构成的集合。构成的集合。n由于由于“集合集合”中的数据元素之间存在着完全松散的关系，因中的数据元素之间存在着完全松散的关系，因此查找表是一种非常灵便的数据结构。此查找表是一种非常灵便的数据结构。n对查找表经常进行的操作：对查找表经常进行的操作：n查询某个查询某个“特定的特定的”数据元素是否在查找表中；数据元素是否在查找表中；n检索某个检索某个“特定的特定的”数据元素的各种属性；数据元素的各种属性；n在查找表中插入一个数据元素；在查找表中插入一个数据元素；n从查找表中删去某个数据元素。从查找表中删去某个数据元素。n查找表的分类：查找表的分类：n静态查找表静态查找表(StaticSearchTable)：对查找表只作前两种统：对查找表只作前两种统称为称为“查找查找”的操作。的操作。n动态查找表动态查找表(DynamicSearchTable)：在查找过程中同时：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素。在的某个数据元素。南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 7 7第第8 8章章 查找查找8.1 8.1 静态查找表静态查找表n抽象数据类型抽象数据类型静态查找表静态查找表的定义的定义ADT StaticSearchTableADT StaticSearchTablen数据对象数据对象D D：具有相同特性的数据元素的集合。各个数据具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字。元素均含有类型相同，可唯一标识数据元素的关键字。n数据关系数据关系R R：数据元素同属一个集合。数据元素同属一个集合。n基本操作基本操作P P：Create(&STCreate(&ST，n)n)；操作结果：构造一个含操作结果：构造一个含n n个数据元素的静态查找表个数据元素的静态查找表STST。Destroy(&ST)Destroy(&ST)；初始条件：静态查找表初始条件：静态查找表STST存在。存在。操作结果：销毁表操作结果：销毁表STST。南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 8 8第第8 8章章 查找查找8.1 8.1 静态查找表静态查找表n抽象数据类型抽象数据类型静态查找表静态查找表的定义的定义Search(STSearch(ST，key)key)；初始条件：静态查找表初始条件：静态查找表STST存在，存在，keykey为和关键字类型相为和关键字类型相同的给定值。同的给定值。操作结果：若操作结果：若STST中存在其关键字等于中存在其关键字等于keykey的数据元素，的数据元素，则函数值为该元素的值或在表中位置，否则为则函数值为该元素的值或在表中位置，否则为“空空”。Traverse(STTraverse(ST，visit()visit()；初始条件：静态查找表初始条件：静态查找表STST存在，存在，visitvisit是对元素操作的是对元素操作的应用函数。应用函数。操作结果：按某种次序对操作结果：按某种次序对STST的每个元素调用函数的每个元素调用函数visitvisit()()一次且仅一次，一旦一次且仅一次，一旦visit()visit()失败，则操作失败。失败，则操作失败。ADT StaticSearchTable ADT StaticSearchTable南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 9 9第第8 8章章 查找查找8.1 8.1 静态查找表静态查找表n小结小结n顺序表的（简单）查找顺序表的（简单）查找n设置监视哨设置监视哨n适用的存储结构：顺序、链式适用的存储结构：顺序、链式n有序表的折半查找有序表的折半查找n有序表的等概率查找有序表的等概率查找n适用的存储结构：顺序、链式适用的存储结构：顺序、链式n其他有序表查找方法：斐波那契查找、插值查找其他有序表查找方法：斐波那契查找、插值查找n静态树表的查找静态树表的查找n有序表的不等概率查找有序表的不等概率查找n适用的存储结构：二叉链表适用的存储结构：二叉链表n索引顺序表的查找索引顺序表的查找n顺序表的查找的改进顺序表的查找的改进n适用的存储结构：顺序、顺序与链式结合适用的存储结构：顺序、顺序与链式结合南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 10 10第第8 8章章 查找查找8.2 8.2 动态查找表动态查找表n动态查找表的特点动态查找表的特点n表结构本身是在查找过程中表结构本身是在查找过程中动态生成动态生成的，即对于给定的，即对于给定值值key，若表中存在其关键字等于，若表中存在其关键字等于key的记录，则查的记录，则查找成功并返回位置信息；否则，插入关键字等于找成功并返回位置信息；否则，插入关键字等于key的记录。的记录。n一种基于树的查找法（树表查找法）一种基于树的查找法（树表查找法）n将待查表组织成特定树的形式并在树结构上实现查找将待查表组织成特定树的形式并在树结构上实现查找的方法的方法。南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 11 11第第8 8章章 查找查找8.2 8.2 动态查找表动态查找表n抽象数据类型抽象数据类型动态查找表动态查找表的定义的定义ADT DynamicSearchTableADT DynamicSearchTablen数据对象数据对象D D：具有相同特性的数据元素的集合。各个数具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字。据元素均含有类型相同，可唯一标识数据元素的关键字。n数据关系数据关系R R：数据元素同属一个集合。数据元素同属一个集合。n基本操作基本操作P P：InitDSTable(&DT)InitDSTable(&DT)；操作结果：构造操作结果：构造个空的动态查找表个空的动态查找表DTDT。DestroyDSTable(&DT)DestroyDSTable(&DT)；初始条件：动态查找表初始条件：动态查找表DT DT 存在。存在。操作结果：销毁动态查找表操作结果：销毁动态查找表DTDT。SearchDSTable(DT SearchDSTable(DT，key)key)；初始条件：动态查找表初始条件：动态查找表DTDT存在，存在，keykey为和关键字类型相同的给定为和关键字类型相同的给定值。值。操作结果：若操作结果：若DTDT中存在关键字等于中存在关键字等于keykey的数据元素，则函数值为的数据元素，则函数值为该元素值或在表中位置，否则为该元素值或在表中位置，否则为“空空”。南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 12 12第第8 8章章 查找查找8.2 8.2 动态查找表动态查找表n抽象数据类型抽象数据类型动态查找表动态查找表的定义的定义InsertDSTable(&DTInsertDSTable(&DT，e)e)；初始条件：动态查找表初始条件：动态查找表DTDT存在，存在，e e为待插入数据元素。为待插入数据元素。操作结果：若操作结果：若DTDT中不存在其关键字等于中不存在其关键字等于e.keye.key的数据元素，则插入的数据元素，则插入e e到到DTDT。DeleteDSTable(&DTDeleteDSTable(&DT，key)key)；初始条件：动态查找表初始条件：动态查找表DTDT存在，存在，keykey为和关键字类型相同的给定值。为和关键字类型相同的给定值。操作结果：若操作结果：若DTDT中存在其关键字等于中存在其关键字等于keykey的数据元素，则删除。的数据元素，则删除。TraverseDSTable(DTTraverseDSTable(DT，Visit()Visit()；初始条件：动态查找表初始条件：动态查找表DTDT存在，存在，VisitVisit是对结点操作的应用函数。是对结点操作的应用函数。操作结果：按某种次序对操作结果：按某种次序对DTDT的每个结点调用函数的每个结点调用函数Visit()Visit()一次且至一次且至多一次。一旦多一次。一旦visit()visit()败，则操作失败。败，则操作失败。ADT DynamicSearchTable ADT DynamicSearchTable南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 13 13第第8 8章章 查找查找8.2 8.2 动态查找表动态查找表n存储结构存储结构n二叉链表二叉链表n主要内容主要内容n二叉排序树二叉排序树n二叉排序树的定义二叉排序树的定义n二叉排序树的查找过程二叉排序树的查找过程n二叉排序树的插入二叉排序树的插入n二叉排序树的建立二叉排序树的建立n二叉排序树的删除二叉排序树的删除n二叉排序树的查找分析二叉排序树的查找分析n平衡的二叉排序树的定义平衡的二叉排序树的定义 lchild data rchildkey南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 14 14第第8 8章章 查找查找8.2 8.2 动态查找表动态查找表二叉排序树二叉排序树n二叉排序树的定义：一种二叉排序树的定义：一种特殊结构的二叉树，或者特殊结构的二叉树，或者是一棵空树，或者是具有是一棵空树，或者是具有如下性质的二叉树：如下性质的二叉树：n若它的左子树非空，则左子若它的左子树非空，则左子树上所有结点的值均小于根树上所有结点的值均小于根结点的值；结点的值；n若它的右子树非空，则右子若它的右子树非空，则右子树上所有结点的值均大于根树上所有结点的值均大于根结点的值；结点的值；n它的左右子树也分别为二叉它的左右子树也分别为二叉排序树。排序树。n中序遍历二叉排序树中序遍历二叉排序树n递增有序序列递增有序序列353515154545505040402525101020203030南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 15 15第第8 8章章 查找查找8.2 8.2 动态查找表动态查找表二叉排序树二叉排序树n二叉排序树的查找二叉排序树的查找与次优二叉树类似与次优二叉树类似n当二叉排序树不空时，首先将给定值和根结点的关键字当二叉排序树不空时，首先将给定值和根结点的关键字比较，若相等，则查找成功，否则将依据给定值和根结比较，若相等，则查找成功，否则将依据给定值和根结点的关键字之间的大小关系，分别在左子树或右子树上点的关键字之间的大小关系，分别在左子树或右子树上继续进行查找。继续进行查找。353515154545505040402525101020203030搜索搜索4545 搜索成功搜索成功 搜索搜索2828搜索失败搜索失败南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 16 16第第8 8章章 查找查找8.2 8.2 动态查找表动态查找表二叉排序树二叉排序树n二叉排序树查找的递归算法二叉排序树查找的递归算法nBiTreeSearchBST(BiTreeT，KeyTypekey)/在根指针在根指针T T所指二叉排序树中递归地查找某关键字等于所指二叉排序树中递归地查找某关键字等于keykey的数据元素的数据元素/若查找成功，则返回指向该数据元素结点的指针，否则返回空指针若查找成功，则返回指向该数据元素结点的指针，否则返回空指针if(!T)|EQ(key，T-data.key)return(T)；/查找结束查找结束elseifLT(key，T-data.key)return(SearchBST(T-lchild，key)；/在左子树中继续查找在左子树中继续查找elsereturn(SearchBST(T-rchild，key)；/在右子树中继续查找在右子树中继续查找/SearchBST南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 17 17第第8 8章章 查找查找8.2 8.2 动态查找表动态查找表二叉排序树二叉排序树n二叉排序树查找的二叉排序树查找的非非递归算法递归算法nBiTreeNSearchBST(BiTreeT，KeyTypekey)/在根指针在根指针T T所指二叉排序树中非递归地查找某关键字等于所指二叉排序树中非递归地查找某关键字等于keykey的数据元素的数据元素/若查找成功，则返回指向该数据元素结点的指针，否则返回空指针若查找成功，则返回指向该数据元素结点的指针，否则返回空指针p=T;/指针指针p指向根结点，搜索从根结点开始指向根结点，搜索从根结点开始while(p!=NULL&p-data.key!=key)if(keykey)p=p-lchild;elsep=p-rchild;return(p);/NSearchBST南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 18 18第第8 8章章 查找查找8.2 8.2 动态查找表动态查找表二叉排序树二叉排序树n二叉排序树的插入二叉排序树的插入n二叉排序树的查找的特点二叉排序树的查找的特点n动态树表查找动态树表查找n树的结构通常不是一次生成的，而是在查找过程中，当树中不树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。存在关键字等于给定值的结点时再进行插入。n新插入的结点一定是一个新添加的叶子结点，并且是查新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。右孩子结点。n插入前必须要查找，以确定要插入的位置，因此必须修插入前必须要查找，以确定要插入的位置，因此必须修改二叉排序树的查找算法改二叉排序树的查找算法n查找不成功时必须查找不成功时必须返回插入的位置返回插入的位置南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 19 19第第8 8章章 查找查找8.2 8.2 动态查找表动态查找表二叉排序树二叉排序树n二叉排序树查找的递归算法二叉排序树查找的递归算法（查找不成功时返回插入的位置查找不成功时返回插入的位置）nStatus SearchBST(BiTree TStatus SearchBST(BiTree T，KeyType keyKeyType key，BiTree fBiTree f，BiTree&p)BiTree&p)/在根指针在根指针T T所指二叉排序树中递归地查找其关键字等于所指二叉排序树中递归地查找其关键字等于keykey的数据元素，的数据元素，/若查找成功，则指针若查找成功，则指针p p指向该数据元素结点，并返回指向该数据元素结点，并返回TRUETRUE，/否则指针否则指针p p指向查找路径上访问的最后一个结点并返回指向查找路径上访问的最后一个结点并返回FALSEFALSE，/指针指针f f指向指向T T的双亲，其初始调用值为的双亲，其初始调用值为NULLNULLif(!T)p=fif(!T)p=f；return FALSEreturn FALSE；/查找不成功查找不成功else else if EQ(key,T-data.key)if EQ(key,T-data.key)p=T p=T；return TRUEreturn TRUE；/查找成功查找成功else if LT(key,T-data.key)else if LT(key,T-data.key)SearchBST(T-lchild,key,T,p)SearchBST(T-lchild,key,T,p)；/在左子树中继续查找在左子树中继续查找else SearchBST(T-rchild,key,T,p)else SearchBST(T-rchild,key,T,p)；/在右子树中继续查找在右子树中继续查找/SearchBST/SearchBST南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 2020第第8 8章章 查找查找8.2 8.2 动态查找表动态查找表二叉排序树二叉排序树n二叉排序树的插入算法二叉排序树的插入算法nStatus Status InsertBSTInsertBST(BiTree&T(BiTree&T，ElemType e)ElemType e)/当二叉排序树当二叉排序树T T中不存在关键字等于中不存在关键字等于e.keye.key的数据元素时的数据元素时,插入插入e e并返回并返回TRUETRUE，否则，否则返回返回FALSEFALSEif(!SearchBST(Tif(!SearchBST(T，e.keye.key，NULLNULL，p)p)/查找不成功查找不成功s=(BiTree)malloc(sizeof(BiTNode)s=(BiTree)malloc(sizeof(BiTNode)；s-data=es-data=e；s-lchild=s-rchild=NULLs-lchild=s-rchild=NULL；if(!p)T=sif(!p)T=s；/被插结点被插结点*s s为新的根结点，原树为空为新的根结点，原树为空else if LT(e.keyelse if LT(e.key，p-data.key)p-data.key)p-lchild=s p-lchild=s；/被插结点被插结点*s s为左孩子为左孩子else p-rchild=s else p-rchild=s /被插结点被插结点*s s为右孩子为右孩子return TRUEreturn TRUE；else return FALSE;else return FALSE;/树中已有关键字相同的结点，不再插入树中已有关键字相同的结点，不再插入/InsertBST/InsertBST南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 21 21第第8 8章章 查找查找8.2 8.2 动态查找表动态查找表二叉排序树二叉排序树n二叉排序树的建立二叉排序树的建立n依次输入数据依次输入数据 53,78,65,17,87,09,81,15 53,78,65,17,87,09,81,15，建立二叉排序树建立二叉排序树535378537865537865175378658717537865091787537865811787095378651517870981南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 2222第第8 8章章 查找查找8.2 8.2 动态查找表动态查找表二叉排序树二叉排序树n二叉排序树的建立二叉排序树的建立n重复插入重复插入n中序遍历二叉排序树，得到升序序列中序遍历二叉排序树，得到升序序列n建立的过程即为对无序序列进行排序的过程建立的过程即为对无序序列进行排序的过程n二叉排序树既拥有类似于折半查找的特性，又采用了链二叉排序树既拥有类似于折半查找的特性，又采用了链表作存储结构，因此是动态查找表的一种适宜表示表作存储结构，因此是动态查找表的一种适宜表示n同样同样n3 n3 个数据，如果输入顺序不同，建立起来的二叉个数据，如果输入顺序不同，建立起来的二叉排序树的形态也不同，这直接影响到二叉排序树的查找排序树的形态也不同，这直接影响到二叉排序树的查找性能。性能。南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 2323第第8 8章章 查找查找8.2 8.2 动态查找表动态查找表二叉排序树二叉排序树n二叉排序树的建立算法二叉排序树的建立算法nvoid CreateBST(BSTree bst)void CreateBST(BSTree bst)/*/*从键盘输入元素的值，创建相应的二叉排序树从键盘输入元素的值，创建相应的二叉排序树*/KeyType key;KeyType key;bst=NULL;bst=NULL;scanf(%d,&key);scanf(%d,&key);while(key!=ENDKEY)while(key!=ENDKEY)/*ENDKEY/*ENDKEY为自定义常数为自定义常数*/InsertBST(bst,key);InsertBST(bst,key);scanf(%d,&key);scanf(%d,&key);南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 2424第第8 8章章 查找查找8.2 8.2 动态查找表动态查找表二叉排序树二叉排序树n二叉排序树的删除二叉排序树的删除n在二叉搜索树中删除一个结点时，必须将因删除结点而在二叉搜索树中删除一个结点时，必须将因删除结点而断开的二叉链表重新链接起来，同时确保二叉搜索树的断开的二叉链表重新链接起来，同时确保二叉搜索树的性质不会失去。性质不会失去。n为保证在删除后树的搜索性能不至于降低，还需要防止为保证在删除后树的搜索性能不至于降低，还需要防止重新链接后树的高度增加。重新链接后树的高度增加。n分四种情况进行讨论分四种情况进行讨论n删除删除叶结点叶结点n被删结点缺右子树被删结点缺右子树n被删结点缺左子树被删结点缺左子树n被删结点左、右子树都存在被删结点左、右子树都存在单分支结点单分支结点双分支结点双分支结点南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 2525第第8 8章章 查找查找8.2 8.2 动态查找表动态查找表二叉排序树二叉排序树n二叉排序树的删除二叉排序树的删除n删除叶结点，只需将其双亲结点指向它的指针清零，删除叶结点，只需将其双亲结点指向它的指针清零，再释放它即可。再释放它即可。5378651787092345删除删除6565双亲结点双亲结点指针清零指针清零53781787092345南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 2626第第8 8章章 查找查找8.2 8.2 动态查找表动态查找表二叉排序树二叉排序树n二叉排序树的删除二叉排序树的删除n被删结点缺右子树，可以拿它的左子女结点顶替它的位被删结点缺右子树，可以拿它的左子女结点顶替它的位置，再释放它。置，再释放它。5378651787092345删除删除4545缺右子树缺右子树,用用左子女顶替左子女顶替53786517870923南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 2727第第8 8章章 查找查找8.2 8.2 动态查找表动态查找表二叉排序树二叉排序树n二叉排序树的删除二叉排序树的删除n被删结点缺左子树，可以拿它的右子女结点顶替它的位被删结点缺左子树，可以拿它的右子女结点顶替它的位置，再释放它。置，再释放它。53788817940923删除删除7878缺左子树缺左子树,用用右子女顶替右子女顶替539488170923南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 2828第第8 8章章 查找查找8.2 8.2 动态查找表动态查找表二叉排序树二叉排序树n二叉排序树的删除二叉排序树的删除n被删结点左、右子树都存在，可以在它的右子树中寻找被删结点左、右子树都存在，可以在它的右子树中寻找中序下的第一个结点中序下的第一个结点(关键码最小关键码最小),用它的值填补到被删用它的值填补到被删结点中，再来处理这个结点的删除问题。结点中，再来处理这个结点的删除问题。8853788117940945删除删除7878在右子树上找在右子树上找中序下第一个中序下第一个结点填补结点填补2365538188179409452365南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 2929第第8 8章章 查找查找8.2 8.2 动态查找表动态查找表二叉排序树二叉排序树n二叉排序树的删除算法二叉排序树的删除算法nStatus Status DeleteBSTDeleteBST(BiTree&p,KeyType key)(BiTree&p,KeyType key)if(!T)if(!T)return FALSE;return FALSE;else if(EQ(key,T-data.key)else if(EQ(key,T-data.key)return return Delete(T);else if(LT(key,T-data.key)else if(LT(key,T-data.key)return return DeleteBSTDeleteBST(T-lchild,key);(T-lchild,key);else else return return DeleteBSTDeleteBST(T-rchild,key);(T-rchild,key);/DeleteBST /DeleteBST 南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 3030第第8 8章章 查找查找8.2 8.2 动态查找表动态查找表二叉排序树二叉排序树n二叉排序树的删除算法二叉排序树的删除算法nStatusStatusDelete(BiTree&p)(BiTree&p)if(!p-rchild)if(!p-rchild)q=p;p=p-lchild;free(q);q=p;p=p-lchild;free(q);else else if(!p-lchild)q=p;p=p-rchild;free(q);if(!p-lchild)q=p;p=p-rchild;free(q);else else q=p;s=p-lchild;q=p;s=p-lchild;while(s-rchild)q=s;s=s-rchild;while(s-rchild)q=s;s=s-rchild;p-data=s-data;p-data=s-data;if(q!=p)if(q!=p)q-rchild=s-lchild;q-rchild=s-lchild;else q-lchild=s-lchild;else q-lchild=s-lchild;delete s;delete s;return TRUE;return TRUE;/Delete /Delete南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 31 31第第8 8章章 查找查找8.3 8.3 哈希表哈希表n什么是哈希表什么是哈希表n哈希表的构造方法哈希表的构造方法n哈希表的冲突处理方法哈希表的冲突处理方法n哈希表的查找哈希表的查找南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 3232第第8 8章章 查找查找8.3.1 8.3.1 什么是哈希表什么是哈希表n例例1:1:招招10001000个新生个新生,将其学号从将其学号从000000编到编到999999，则可以，则可以用一个顺序表来存放学生的住处，每个学生的学号用一个顺序表来存放学生的住处，每个学生的学号正好是他的信息在顺序表的序号正好是他的信息在顺序表的序号n 学学 号号哈希函数哈希函数学生信息在表中的序号学生信息在表中的序号（关键字）（位置）南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 3333第第8 8章章 查找查找8.3.1 什么是哈希（hash）表n静态查找表和动态查找表元素的位置和它的静态查找表和动态查找表元素的位置和它的关键字之间不存在一个关键字之间不存在一个确定关系确定关系,查找只能通查找只能通过关键字的比较操作过关键字的比较操作,查找效率只能取决于和查找效率只能取决于和给定值比较的关键字个数。给定值比较的关键字个数。n如能在关键字和位置之间建立一种确定的关如能在关键字和位置之间建立一种确定的关系系f f，使每个关键字和唯一的位置对应，则在使每个关键字和唯一的位置对应，则在查找时可以通过这种查找时可以通过这种f f快速找到给定值的位置，快速找到给定值的位置，而不需要进行关键字比较。而不需要进行关键字比较。f f称为称为哈希函数哈希函数，按这个思想建立的表称为按这个思想建立的表称为哈希表哈希表。南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 3434第第8 8章章 查找查找8.3.8.3.2 2 哈希表的构造哈希表的构造n构造哈希表的就是在关键字和元素存放位置之间构造哈希表的就是在关键字和元素存放位置之间建立映射关系建立映射关系 f(key)=locate(i)f(key)=locate(i)姓氏姓氏赵赵钱钱孙孙李李吴吴陈陈黄黄叶叶代代存放存放位置位置13138 89 96 611111 14 412122 2 f(key f(key）是什么？）是什么？(姓氏的首字母的姓氏的首字母的ASCIIASCII码值码值-AA的的ASCIIASCII码值码值)/2)/2如果要加入如果要加入“张张”姓怎么办？姓怎么办？南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 3535第第8 8章章 查找查找8.3.8.3.2 2 哈希表的构造哈希表的构造n哈希表的构造哈希表的构造n冲突是指不同的关键字通过哈希函数的映射后得到了冲突是指不同的关键字通过哈希函数的映射后得到了相同的位置相同的位置n冲突不可避免，但应尽量减少冲突冲突不可避免，但应尽量减少冲突n构造哈希表的关键是找到合适的哈希函数，既可以从构造哈希表的关键是找到合适的哈希函数，既可以从关键字到存储位置的进行映射关键字到存储位置的进行映射,又能减少冲突。又能减少冲突。n经典的构造函数都是经典的构造函数都是对数字型关键字而言对数字型关键字而言的，对非数的，对非数字的关键字要先将其转化为数字型关键字字的关键字要先将其转化为数字型关键字n常见的哈希构造函数有直接定址法、数字分析法、平常见的哈希构造函数有直接定址法、数字分析法、平方取中法、折叠法等，每种方法均有其适用条件方取中法、折叠法等，每种方法均有其适用条件南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 3636第第8 8章章 查找查找8.3.8.3.2 2 哈希表的构造哈希表的构造n直接定址法直接定址法 H(key)=key H(key)=key 或或 H(key)=a*key+bH(key)=a*key+bn仅限于地址集合的大小等于关键字集合的大小仅限于地址集合的大小等于关键字集合的大小,如前例中学生学号和学生信息位置的映射如前例中学生学号和学生信息位置的映射南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 3737第第8 8章章 查找查找8.3.8.3.2 2 哈希表的构造哈希表的构造n数字分析法数字分析法n关键字由多位数字构成，分析关键字集中的全体，关键字由多位数字构成，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为并从中提取分布均匀的若干位或它们的组合作为地址地址n例：南航学生的学号构成如下例：南航学生的学号构成如下 年份年份+专业号专业号+班号班号+流水号流水号n限制条件：能够预估全体关键字每一位上各数字限制条件：能够预估全体关键字每一位上各数字出现的频度出现的频度南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 3838第第8 8章章 查找查找8.3.8.3.2 2 哈希表的构造哈希表的构造n平方取中法平方取中法n关键字中每一位都有某些数字重复出现频度很高关键字中每一位都有某些数字重复出现频度很高的现象，则先求关键字的平方，通过的现象，则先求关键字的平方，通过“平方平方”扩扩大差别，同时平方值中的中间几位受到整个关键大差别，同时平方值中的中间几位受到整个关键字各位的影响字各位的影响南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 3939第第8 8章章 查找查找8.3.8.3.2 2 哈希表的构造哈希表的构造南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 4040第第8 8章章 查找查找8.3.8.3.2 2 哈希表的构造哈希表的构造n折叠法折叠法n关键字位数特别多，而且关键字中每一位上数字关键字位数特别多，而且关键字中每一位上数字分布大致均匀，可将其分割为几个部分，取其叠分布大致均匀，可将其分割为几个部分，取其叠和为哈希地址，有和为哈希地址，有“移伴叠加移伴叠加”和和“间界叠加间界叠加”，如，如ISBNISBN号号0-442-20586-40-442-20586-4南昌航空大学计算机学院南昌航空大学计算机学院/软件学院软件学院 41 41第第8 8章章 查找查找8.3.8.3.2 2 哈希表的构造哈希表的构造n除留余数法（取模法）除留余数法（取模法）H(key)=key mod p;p=m(m H(key)=key mod p;p=m(m为表长为表长)n关键问题是如何取关键问题是如何取P P，一般是取不大于，一般是取不大于m m