PPT选择的文档

第9章9.1概述9.1.1查找表9.1.2相关术语9.1.1类型说明搜索9.2静态查找表9.2.1概述9.2.2搜索序列表9.2.3有序表搜索￡ 9.2.4索引顺序表搜索￡ 9.3动态查找表￡ 9.3.1概述￡ 9.3.2二进制排序树和平衡二进制树￡ 9.3.3 B树和B +树tree 9.4哈希表￡ 9.4.1定义￡ 9.4.2哈希函数的构造￡ 9.4.3处理冲突的方法￡ 9.4.4哈希表的搜索和分析￡ 9.3动态查找表￡ 9.3.1概述（1）动态查找表抽象数据类型的定义: ADT DynamicSearchTable {数据对象D: D是具有相同特征的数据元素的集合. 每个数据元素包含唯一标识数据元素的相同类型的关键字. 数据关系R: 数据元素属于同一集合. 基本操作P: InitDSTable（＆DT）;操作结果: 构造一个空的动态查找表DT. DestroyDSTable（＆DT）;初始条件: 存在动态查找表DT. 操作结果: 销毁动态查找表DT. SearchDSTable（DT二叉排序树 构造，键）;初始条件: 存在动态查找表DT，并且键是与关键字相同类型的给定值.

操作结果: 如果存在一个数据元素，其键等于DT中的键，则功能值为该元素的值或表中的位置二叉排序树 构造，否则为“空”. InsertDSTable（＆DT，e）;初始条件: 存在动态查找表DT，e是要插入的数据元素. 操作结果: 如果在DT中没有键等于e.key的数据元素，则在DT中插入e. DeleteDSTable（＆DT，键）;初始条件: 存在动态查找表DT，并且关键字是与关键字相同类型的给定值. 操作结果: 如果有一个数据元素的键等于DT中的键，则将其删除. TraverseDSTable（DT，Visit（））;初始条件: 存在动态查找表DT，Visit是元素操作的应用程序功能. 操作结果: 函数DT的每个元素以特定顺序仅调用一次函数visit（）一次. 一旦visit（）失败，该操作就会失败. } ADT DynamicSearchTable（2）动态搜索表的特征: 表结构本身是在搜索过程中动态生成的，也就是说，对于给定值的键，如果表中有一条记录的键等于键，搜索成功返回，否则插入键等于键的记录. ￡ 9.3.2二进制排序树和平衡二进制树（1）二进制排序树①定义二进制排序树: 它是空树或具有以下属性的二进制树: 1.如果其左子树不为空，则值左子树上所有节点的值均小于其根节点的值;如果其右子树不为空，则右子树上所有节点的值都大于其根节点的值; 3.它的左和右子树也是二进制排序树.

②图形表示45 12 3 24 37 61 90 53 100陈立杜望下夏草操（a）78（b）ͼ9.3二进制排序树示例例如: 30 20 10 25 355080 40 85 9023是二进制排序树. 88例如: 30 20 10 25 355080 40 66 85 9023不是二进制排序树. 88通常，将二进制列表作为二进制排序树的存储结构. typedef struct BiTNode {//节点结构TElemType数据； struct BiTNode * lchild，* rchild; //左右子指针} BiTNode，* BiTree; 2.二进制排序树搜索算法: 如果二进制排序树为空，则搜索失败；除此以外？ 1）如果给定值等于根节点的关键字，则搜索成功； 2）如果给定值小于根，则对于节点的关键字，继续在左侧子树上搜索； 3）如果给定值大于根节点的关键字，请继续在右侧子树上搜索. 例如: 二进制排序树503020 4080903532搜索关键字== 50，35，90，95，8588可以从上面的搜索过程中看到，在搜索过程中，生成搜索路径: 从根节点开始，沿着左边分支或右分支逐层下降，直到具有等于给定值的键的节点为止；或者-搜索从根节点开始，沿着左分支或右分支逐层向下进行，直到指针指向空树为止.

-不成功的搜索状态SearchBST（BiTree T，KeyType kval，BiTree f，BiTree和p）{//在根指针所指向的二进制排序树中递归搜索其//关键字等于kval的数据元素T，如果搜索成功，//返回指针p以指向数据元素的节点，并返回//函数值为TRUE；否则，表明搜索不成功，返回//指针p指向在搜索路径上访问的最后一个节点，//返回函数值为FALSE，指针f指向当前访问的节点的父节点//，并且其初始调用值为NULL. 该算法描述如下: ............ // SearchBSTif（！T）{p = f; return FALSE;} //如果（EQ（kval，T-> data.key））{p = T; return TRUE;} //如果（LT（kval，T-> data.key））返回SearchBST（T-> lchild，kval，T，p）;否则查找成功. 否则返回SearchBST（T-> rchild，kval，T，p）; //继续在右侧子树中搜索//继续在左侧子树中搜索3.二进制排序树的插入算法？根据动态查找表的定义，仅当搜索不成功时才执行“插入”操作. 如果二进制排序树为空树，则新插入的节点为新的根节点；否则，新插入的节点必须是通过搜索过程获得其插入位置的新叶节点.

状态插入BST（BiTree和T，ElemType e）{//当在二进制排序树中没有//等于e.key的数据元素时，插入值为e的节点并返回//返回TRUE；否则，不要插入并返回FALSEif（！SearchBST（T，e.key，NULL，p））{}……否则返回FALSE;} //插入BST = new BiTNode; //分配给新节点Space s-> data = e; s-> lchild = s-> rchild = NULL;如果（！P）T = s; p-> lchild = s; //插入s作为新的根节点，否则if（LT（e.key，p-> data.key））//插入* s为* p的左子节点//插入* s为* p的右子节点否则p-> rchild = s;返回TRUE; //成功插入4.二进制排序树的删除算法与插入相反. 删除是在搜索成功之后执行的，并且需要在删除二进制排序树上的节点之后维护二进制排序树的特性.

有三种情况需要讨论: ？ （1）删除的节点是叶子； （2）被删除的节点只有左子树或只有右子树； （3）删除的节点同时有左右子树. （1）删除的节点是叶节点. 例如: 88 Deleted keyword = 205030 20 35 40 85 80 903288其父节点中相应指针字段的值更改为“ empty”（2）删除的节点仅左侧子树或仅右侧子树80 Deleted = 405030 20 35 40 85 80 903288其父节点的相应指针字段的值更改为“指向已删除节点的左子树或右子树”. （3）删除的节点将左子树和右子树都替换为其前任，然后删除前任节点的算法如下: Status DeleteBST（BiTree＆T，KeyType kval）{//若宾查//在排序树T中//其键等于kval的数据元素，删除该数据元素节点并返回//函数值TRUE，否则返回函数值FALSEif（！T）返回FALSE; // //不存在关键字数据元素等于kval else {……}} // DeleteBSTif（EQ（kval，T-> data.key））{删除（T）; return TRUE;} //查找其键等于键的数据元素，否则if（LT（kval，T-> data.key））返回DeleteBST（T-> lchild，kval）;否则返回DeleteBST（T-> rchild，kval）; //继续在右边的子树中搜索//继续到左边的子树中进行删除操作的描述，如下所示: void Delete（BiTree＆p）{//从二进制排序树中删除节点p，//并重新连接其左或右子树，如果（！P-> rchild）{……}否则（（p-> lchild）{……} else {……}} //删除//如果右子树为空，只是重新加权连接其左子树q = p; p = p-> lchild;删除（q）; qppq //左子树为空. 只需重新连接其右子树q = p; p = p-> rchild;删除（q）; qq pp //左右子树不为空q = p; s = p-> lchild;而（s-> rchild）{q = s; s = s-> rchild;} // s删除节点的前体p-> data = s-> data;如果（q！= P）q-> rchild = s-> lchild; qp else q-> lchild = s-> lchild; s // heavy连接* q的左子树删除； 5.搜索性能分析对于每个特定的二进制排序树，可以根据平均搜索长度的定义获得ASL值. 显然，具有相同值的n个关键字用于构造两种不同形式的树. 交叉排序树的平均搜索长度值不同，甚至可能非常不同.

例如: 由关键字序列1、2、3、4和5构成的二进制排序树12 345ASL =（1 + 2 + 3 + 4 + 5）/ 5 = 3由关键字序列3，1 ，2,5,4构造的二进制排序树312 45ASL =（1 + 2 + 3 + 2 + 3）/ 5 = 2.2下面讨论了平均情况: 不失一般性，假定长度为n的序列有k个关键字小于第一个关键字，则必须有大于第一个关键字的nk-1个关键字，由它构成的二元排序树k nk-1的平均搜索长度为n和k函数P（n，k）（0 ？K？N-1）假设n个关键字可能具有相同的n !！可能的安排，带有n个关键字的二元排序树的平均搜索长度为n？ 1 1 ASL？ P（n）?? P（n，k）k？ 0 n在等概率搜索的情况下，1n P（n，k）？ P CC？ i？伊尼？ 1我？ 1nn 1 1 ?? P（n，k）？ C？ C？ C？ C？？？根？ i？在？一世？ 1 n LR？ 1 ？？？ 1？ K（P（k）？1）？ （N？k？1）（P（n？k？1）？1）n1 ??? 1？ k？ P（k）？ （n？k？1）？ P（n？k？1）n 1 1 1 ??? P（n）？ 1？ K？ P（k）？ （n？k？1）？ P（n？k？1）??? k？ 0 n？ n ?? 1 2n ??? 1？ 2？ k？ P（k）1 nk？方程，此递归方程有一个解: 1 P（n）？ 2 log n？ C nO（nlogn）

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-205394-1.html