数据结构 ch09.pptVIP

算法分析 从顺序查找过程可见（不考虑越界比较），顺序查找不论给定值k为何，若第1个记录符合给定值，只要比较1次。若第n个记录符合给定值，要比较n次，即ci=i。若每个记录的查找概率相等，且每次查找都是成功的。则在等概率的情况下，顺序查找的平均查找长度为： 查找成功时的平均比较次数约为表长的一半。若k值不在表中，则须进行n+1次比较之后才能确定查找失败。顺序查找算法的时间复杂性为O(n)。 算法分析 二分查找算法的计算复杂性可以用二叉树来进行分析。我们把当前查找区间的中间位置上的记录作为根。左子表和右子表中的记录分别作为根的左子树和右子树。由此得到的二叉树，称为描述二分查找的判定树或比较树。 在查找概率相同的情况下，Pi=1/n。查找成功的平均查找长度为： 二分查找算法比顺序查找算法平均查找长度为 n/2的比较次数少，查找速度快。虽然二分查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算，即使采用高效率的排序方法也要花费O(nlog2n)的时间。另外，二分查找只适用顺序存储结构，不适于线性链表结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的记录。 二分查找特别适用于那种一经建立就很少改动，而又经常需要查找的线性表。 算法分析 由于分块查找实际上是两次查找过程，所以分块查找的平均查找长度是：查找索引表确定给定值所在块内的平均查找长度ASLb与在块的查找关键值的平均查找长度ASLk之和。即ASL=ASLb+ASLk。 若用顺序查找确定所在块，则分块查找成功时的平均查找长度为： 若用二分查找确定所在块，则分块查找成功时的平均查找长度为： 二叉排序树查找算法分析 在二叉排序树上查找其关键字等于给定值的结点的过程，恰是走了一条从根结点到该结点的路径的过程。和给定值比较的关键字次数等于路径长度加1（或结点所在层次数）。含有n个结点的二叉排序树并不唯一，其平均查找长度和树的形态有关。 例如，（a)图和(b)图是结点数为6的两棵二叉排序树。(a)图中树的深度为3，而(b)图树的深度为6。 从平均查找长度分析，假设6个记录的查找概率相等，即为1／6。则图 (a)树的平均查找长度为： 而图 (b)树的平均查找长度为： 当表中记录按关键字有序时，构成的二叉排序树蜕变为歪斜树。树的深度为n，其平均查找长度为(n+1)/2（和顺序查找相同），这是最差的情况。显然，最好情况下平均查找长度和log2n成正比。为了避免出现歪斜树，在构造二叉排序树的过程中需要不断进行平衡处理，使其成为平衡二叉树。 平衡二叉树上进行查找算法分析 在平衡二叉树上进行查找的过程与二叉排序树的查找算法相同。因此，在查找过程中和关键字进行比较的次数不超过树的深度。含有n个结点的平衡树的最大深度为： 因此，在平衡树上进行查找的时间复杂性为O(logn)。 1．B-树的查找 在B-树中查找给定关键字的方法类似于二叉排序树上的查找。不同的是在每个记录上确定向下查找的路径不一定是二路（即二叉）的，而是n+l路的。 在B-树上进行查找的过程是一个顺指针查找结点和在结点的关键字中进行查找交叉进行的过程。 B-树存储结构C语言描述： #define m 3 //B-树的阶，应根据实际情况确定 typedef int KeyType; //关键字类型 typedef struct node{ //结点数据类型 int n; //结点中关键字的个数 KeyType key[m+1]; //关键字数组为key[1..n]，key[0]不用 struct node *parent; //指向双亲结点 struct node *son[m+1]; //孩子指针数组 son[0..n] }BTREE; 例如，要将关键字值序列（3，15，22，24），存储到编号为0到4的表长为5的哈希表中。 计算存储地址的哈希函数可取除5的取余数算法H(k)=k % 5。则构造好的哈希表如图所示。 理想情况下，哈希函数在关键字和地址之间建立了一个一一对应关系，从而使得查找只需一次计算即可完成。由于关键字值的某种随机性，使得这种一一对应关系难以发现或构造。因而可能会出现不同的关键字对应一个存储地址。即k1≠k2，但H(k1)=H(k2)，这种现象称为冲突。 把这种具有不同关键字值而具有相同哈