文档介绍：:一般,假定被查找的对象是由一组结点组成的表(Table)或文件,而每个结点则由若干个数据项组成。并假设每个结点都有一个能惟一标识该结点的关键字。查找(Searching):给定一个值K,在含有n个结点的表中找出关键字等于给定值K的结点。查找表的数据结构表示:(1)动态查找表和静态查找表(2)。它是把顺序查找和二分查找相结合的一种查找方法,即把线性表分成若干块,块和块之间有序,但每一块内的结点可以无序。分块查找的基本思想是:先确定被查找的结点所在的块(采用二分查找法)后,对该块中的结点采用顺序查找。分块查找介于顺序和二分查找之间,其优点是:在表中插入或删除一个记录时,只要找到该记录所属的块,就在该块内进行插入和删除运算。分块查找的主要代价是增加一个辅助数组的存储空间和将初始表分块排序的运算。(BinarySortTree)又称二叉查找(搜索)树或二叉分类树,它是一种特殊的二叉树;或者为空或者满足下面条件的二叉树:每个结点的左子树上的所有结点的关键字,值均小于该结点的关键字值;每个结点的右子树上的所有结点的关键字,值均大于或等于该结点的关键字值。左、右子树本身又各是一棵二叉排序树。、二叉排序树的特点由BST性质可得:(1)二叉排序树中任一结点x,其左(右)子树中任一结点y(若存在)的关键字必小(大)于x的关键字。(2)二叉排序树中,各结点关键字是惟一的。(3)按中序遍历该树所得到的中序序列是一个递增有序序列。。其过程可以简单描述为:在查找某一个值K时,首先令K与二叉树的根结点的值Ra进行比较;如果K<Ra:则在二叉树的左子树上查找K;如果K≥Ra:则在二叉树的右子树上查找K;如果二叉排序树中没有值为K的结点,则将值为K的结点按照二叉排序树构造的规则插入到该二叉树中;其对应算法主要分为两步,(1)二叉排序树查找成功的平均查找长度(2)在二叉排序树上进行查找时的平均查找长度和二叉树的形态有关(3)二叉排序树和二分查找的比较(4)(1)散列(HASH)表的定义:若一个结点在表中的位置和该结点的关键字之间不存在确定的关系,则在表中查找某结点时必然要进行关键字的比较,否则不然。(2)散列表的冲突现象①冲突②安全避免冲突的条件③冲突不可能完全避免④影响冲突的因素券酸偿砷囤带断求甸洱默沂汕蓝牛憾埋尹茎斤亡教醉履星伯浙晃环编善巩数据结构与算法分析8数据结构与算法分析8