加文

在这个世界上取得成就的人,都努力去寻找他们想要的机会,如果找不到机会,他们便自己创造机会。 -- 萧伯纳
随笔 - 14, 文章 - 56, 评论 - 1, 引用 - 0
数据加载中……

查找

1. 查找的基本概念

衡量一个查找算法的时间效率的标准是:在查找过程中,关键字的平均次数,这个标准为平均查找长度ASL;

2. 顺序查找法

1) 在顺序表上的查找(非等概率查找):若等概率,则平均ASL为(n+1)/2;若非等概率,则求出期望

2) 在线性链表上的查找

3. 折半查找

1) 折半查找过程,关键序列有序,则二叉排序树一定,即判定树。

2) 若是关键码无序,仍可构造二叉排序树,进而计算每个关键码的平均ASL。

3) 若是关键码无序,仍可构造二叉排序树,建立过程中,可以调整为平衡二叉树。进而计算每个关键码的平均ASL。

4. B树

1) 线性索引:所有子表,分块有序,后一个子表的所有关键字大于前面一个子表中所有元素的关键字。另外,在建立一张索引表,索引项记录了各子表的最大关键值以及所在的位置,因此,各个索引项在索引表中的序号与各个子表的块号一一对应。对索引顺序结构进行查找时,分为两级查找。先通过索引项确定子表,然后在子表中查找。

2) 多级索引和m叉查找树:有多级索引构成一个m叉查找树,树中的每一个分支节点表示索引块,他最多存放m个索引块,每个索引块分别给出各子树节点的最大关键字和节点地址。

3) B树为二叉排序树

4) B-树的概念:根节点至少有2个子树;非根的非中终端接点有m/2个结点;含有k个结点的子树种有k-1个关键字。

5) B+树的概念:B+树是-B的一种变形,它与B树的区别在于有k个关键字的结点必然有K棵子树,非叶子结点仅仅具有索引作用,而跟记录有关的关键字都在叶子结点中。跟B树的查找类似,但是也有不同。由于跟记录有关的信息存放在叶结点中,查找时若在上层已找到待查的关键码,并不停止,而是继续沿指针向下一直查到叶结点层的关键码。此外,B+树的所有叶结点构成一个有序链表,可以按照关键码排序的次序遍历全部记录。上面两种方式结合起来,使得B+树非常适合范围检索。

5. 散列查找

1) 散列表的概念:表项的存储位置与表项关键字之间确立一个对应的关系函数。

2) 常见散列函数:除留余数法。

3) 解决冲突的方法:线性探测法,二次探测法,拉链法

4) 效率分析:查找成功的平均查找长度;查找失败的平均查找长度;

posted on 2011-12-09 21:34 chxzwj 阅读(139) 评论(0)  编辑 收藏 引用 所属分类: 数据结构


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理