注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

SINOBANJO

IN GOD WE TRUST ! ~ ClueeZhuo

 
 
 
 
 

日志

 
 

SINOBANJO - 数据结构之静态查找表  

2014-12-01 19:16:13|  分类: 班卓数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

静态查找表

         我们继续了解数据结构中有关查找的学习。下文将简单描述查找中的静态查找表。

基本概念

查找:就是在数据集合中寻找满足某种条件的数据对象。

查找表:是由同一类型的数据元素(或记录)组成的数据集合。

衡量一个查找算法的时间效率的标准是

在查找过程中关键字的平均比较次数或平均读写磁盘次数(只适合于外部查找),这个标准也称为平均查找长度ASL(Average Search Length),通常它是查找结构中对象总数 n 或文件结构中物理块总数 n 的函数。

算法所需要的存储量和算法的复杂性等问题。

静态查找表的顺序存储结构

#define maxsize 静态查找表的表长

typedef  struct {

     ElemType  item[maxsize+1];

   // 存储数据元素的数组空间,0号单元留空

   int        n;    // 表的长度

} sqtable;

 

数据元素类型ElemType的定义为:

typedef struct {

    keyType key;    // 关键字域

             // 其它属性域

} ElemType ;

 

查找过程

从表中最后一个元素开始,顺序用各元素的关键字与给定值K进行比较,若找到与其值相等的元素,则查找成功,给出该元素在表中的位置;否则,若直到第一个记录仍未找到关键字与x相等的对象,则查找失败。

        int Search_sqtable(sqtable R, KeyType k)

        {

            //顺序查找的算法,0号元素为监视

            int i;

            R.item[0].key = k;

            for (i = R.n; R.item[i].key != k; --i) ;

            return i;

        }

顺序查找的时间性能

SINOBANJO - 数据结构之静态查找表 - 班卓 - SINOBANJO

 

 

有序表的查找

上述顺序查找表的查找算法简单,但平均查找长度较大,特别不适用于表长较大的查找表。若以有序表表示静态查找表,则查找过程可以基于“折半”进行。

折半查找(二分查找,Binary Search)

SINOBANJO - 数据结构之静态查找表 - 班卓 - SINOBANJO

 

 

SINOBANJO - 数据结构之静态查找表 - 班卓 - SINOBANJO

 

折半查找的效率比顺序查找高,但折半查找只适用于有序表,且限于顺序存储结构

索引顺序表的查找—分块查找

SINOBANJO - 数据结构之静态查找表 - 班卓 - SINOBANJO

 

 

1)先查索引表——折半查找

2)再查顺序表——顺序查找

 

索引顺序查找的平均查找长度 =查找“索引”的平均查找长度 + 在块中查找“顺序表”的平均查找长度

 

对比顺序表和有序表的查找性能

SINOBANJO - 数据结构之静态查找表 - 班卓 - SINOBANJO

 

 

几种查找表的特性

SINOBANJO - 数据结构之静态查找表 - 班卓 - SINOBANJO

 

 

可得如下结论

从查找性能看,最好情况能达O(logn),此时要求表有序

从插入和删除的性能看,最好情况能达O(1),此时要求存储结构是链表

 

本小结中简答介绍了数据结构中关于静态查找的知识点,包含基本概念、查找过程、折半查找、索引顺序表、以及几种查找表的特性。本小结多从数据结构之文献中学习。

  评论这张
 
阅读(54)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017