`
housen1987
  • 浏览: 339517 次
  • 性别: Icon_minigender_1
  • 来自: 长沙
社区版块
存档分类
最新评论

顺序查找表和索引查找表

阅读更多

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

对查找表进行的操作有:

(1)查询某个“特定的”数据元素是否存在查找表中。

(2)检索某个“特定的”数据元素的各种属性。

(3)在查找表中插入一个数据元素。

(4)从查找表中删除某个数据元素。


只做查询的操作的查找表称为静态查找表(Static Search Table)

若在查找过程中同时插入查找表中不存在的数据元素,或者从查找表中删除已存在的某个数据元素,则称此查找表为动态查找表(Dynamic Search Table)


关键字(Key)是数据元素(或记录)中某个数据项的值,用它可以标识一个数据元素(或记录),若此关键字可以唯一的标识一条记录,则称此关键字为主关键字(Primary Key),其他的用于识别若干记录的关键字称为次关键字(Secondary Key)。当数据元素只有一个数据项时,其关键字即为该数据元素的值。


查找(Searching)根据给定的某个值,在查找表中确定一个其关键字等于给定值的记录或数据元素。若表中存在这样的记录,则查找是成功的,若不存在,则查找不成功,给出“空”记录或空指针。


典型的关键字类型说明可以是:

typedef float KeyType; //实型
typedef int KeyType; //整型
typedef char *KeyType; //字符型

 数据元素类型定义为:

typedef struct{
    KeyType key; //关键字域
    ... //其他
}

 对两个关键字的比较的宏定义如下:

//--对数值型关键字
#define EQ(a,b) ((a) == (b))
#define LT(a,b) ((a) < (b))
#define LQ(a,b) ((a) <= (b))

...

//--对字符型关键字
#define EQ(a,b) (!strcmp((a),(b)))
#define LT(a,b) (strcmp((a),(b)) < 0)
#define LQ(a,b) (strcmp((a),(b)) <= 0)

1 静态查找表

抽象数据类型静态查找表定义如下:

ADT StaticSearchTable{
  数据对象D:D是具有相同特性的数据元素的集合,各个数据元素均含有类型相同的,可唯一标识数据元素的关键字。
  数据关系R:数据元素同属一个集合。
  基本操作P:
    Create(&ST,n);
      操作结构:构造一个含n个数据元素的静态查找表ST。
    Destroy(&ST);
      初始条件:静态查找表ST存在。
      操作结果:销毁表ST。
    Search(ST,key);
      初始条件:静态茶渣表ST存在,key为和关键字类型相同的给定值。
      操作结果:若ST中存在其关键字等于key的数据元素,则函数值为该元素的值或在表中的位置,否则为“空”。
    Traverse(ST,visit());
      初始条件:静态查找表ST存在,visit是对元素操作的应用函数。
      操作结果:按某种次序对ST的每隔元素调用函数visit()一次。
}ADT StaticSearchTable;

1.1 顺序表的查找

 

//----------- 静态查找表的顺序存储结构------------
typedef struct{
    Element *elem;//数据元素存储空间基址
    int length;
}SSTable;

顺序查找表的实现(Sequential Search)

    从表中最后一个记录开始,逐个进行记录的关键字和给定值的比较,若某个记录的关键字和给定值比较成功,则查找成功,反之,直到第一个记录,仍不能成功比较,则查找不成功。

 

int search_seq(SSTable ST,KeyType key){
    int i;
    //在顺序表ST中顺序查找其关键字=key的数据元素,
    //若找到,则函数值为该元素在表中的位置,否则为0.
    ST.elem[0].key = key;//哨兵
    for(i=ST.length;!ST.item[i].key == key;--i) //从后往前找
    return i; //找不到时,i =0
}//search_seq

查找操作的性能分析:

衡量一个算法好坏的量度有3条:

时间复杂度

空间复杂度(衡量算法的数据结构所占存储以及大量的附加存储)

算法的其他性能

通常以”其关键字和给定值进行过比较的记录个数的平均值“作为衡量查找算法好坏的依据。


平均查找长度(Average Search Length):为确定记录在查找表中的位置,需和给定值进行比较的关键字个数的期望。

(1) 等概率的情况下顺序查找成功的平均查找长度为:

(n+1)/2

 

(2) 查找不成功的平均查找长度为

n+1

(3) 当查找不成功的概率不可以忽略时,假设查找成功和查找不成功的概率相同,则顺序查找的平均查找长度为:

3(n+1)/4

 

顺序查找的缺点:当n较大时,查找效率很低。

 

1.2 有序表的查找

折半查找(Binary Search):先确定待查记录所在的范围,然后逐步缩小范围直到找到或找不到记录为止。

顺序查找的查找过程如下:

(1) 确定待查记录所在的范围,设区间范围为[low,high];

(2) 求出处于该区间中间位置的值mid,mid = [low+high]/2;

(3) 将给定的key值与有序表中第mid个记录的关键字ST.item[mid].key相比较

(3.1) 若key == ST.item[mid].key,则查找成功

(3.2) 若key < ST.item[mid].key,则high=mid-1,并判断high是否小于low,若high<low,则查找不成功,否则,待查记录还是可能在新的区间[low,high]中,继续执行步骤(2)

(3.3) 若key > ST.item[mid].key,则low = mid + 1,判断high是否小于low,若high<low,则查找不成功,否则,待查记录还是可能在新的区间[low,high]中,继续执行步骤(2)。

算法实现如下:

 

int binarySearch(STable ST,KeyType key){
	int mid,low=0,high=ST.length;
	while(low <=high){
		mid = (low+high)/2;
		if(ST.item[mid].key == key) return mid;
		elseif(ST.item[mid].key < key) low = mid + 1;
		else high = mid - 1;
	}
	return 0;
}

 

折半查找的过程可以用二叉树表示,

判定树即描述查找过程的二叉树

折半查找时与给定值进行比较的次数最多为[log(2)n]+1次

(1) 查找成功时的平均查找长度:

ASL = (n+1)/n * log(2)(n+1) - 1

当n>50时,简化为

ASL = log(2)(n+1)-1

(2) 查找不成功时的平均查找长度

uASL = log(2)(n+1)


折半查找的优点:查找效率比顺序查找的高

缺点:只能适用于有序表,且顺序存储结构,不能用于线性链表

 

1.3 索引顺序表的查找

 

索引顺序表包括存储数据的顺序表(称为主表)和索引表两部分。顺序表被分为若干子表(又称块),整个顺序表有序或分块有序。将每个子表中的最大关键字取出,再加上指向该关键字记录所在子表第一个元素的指针,就构成一个索引项,将这些索引项按关键字增序排列,就构成了索引表。


对于索引顺序表可按分块进行查找,过程分为两个阶段:

(1) 确定待查记录所在的子表(块),由于索引表是按关键字有序排列的,对于索引表可按折半查找,若待查记录关键字的key值,<=第i个子表最大关键字,且大于第i-1个子表的最大关键字,即K(i-1) < key < K(i),则待查关键字位于第i个子表中。

(2) 在已确定的子表中确定待查记录的位置,由于子表中的记录不一定按关键字有序排列,只能按顺序查找法查找。


索引表类型定义如下:

 

#define MAXLEN <索引表最大长度>
typedef int keytype;
typedef struct{
    keytype key;
    int link;
}IndexType;//索引项数据类型
typedef IndexType IDX[MAXLEN+1];//索引表类型,下标从1开始

 

 索引表查找算法:

 

IndxSearch(IDX idx,int b,STable,keytype key){
    int s = ST.length / b; //b为索引表中元素个数,s为每个子表中元素个数
    int i,j;
    for(i=1;i<b+1;i++)
        if(key <= idx[i]) break;
    if(i == b+1) return 0;//从索引表中查找失败

    //注意,此处是从idx[i].link开始,不能设置0哨兵,只能用if判断j == idx[i].link-1
    for(j = idx[i].link+s-1;key!=ST.item[j].key;j--);
    if(j == idx[i].link-1) return 0;    
    else return j;
}
   

一般情况下,为进行分块查找,可以将长度为n的表均匀分成b块,每块还有s个元素,即b = [n/s],如果索引表采用顺序查找的方式,则查找成功时的平均查找长度为:

(s+b+2)/2

如果索引表采用折半查找,则成功时的平均查找长度为:

log(2)(n/s+1)+s/2

 

 

分享到:
评论

相关推荐

    索引顺序表查找

    索引顺序表查找,通过c++实现。

    数据结构--索引顺序表查找

    C语言数据结构中实现索引顺序表查找,可以参考。

    数据结构课程设计 索引顺序查找

    数据结构课程设计,索引顺序查找,用c++做的~有源代码,任务书,报告,超全~~~

    课程设计-索引顺序表查找

    太好了简单方便实用的软件,支持 课程设计-索引顺序表查找

    数据结构中索引顺序表查找

    数据结构中索引顺序表查找,将一些数据分别存放在不同的链表里,每一个链表都有一个头指针作为索引,储存一段数据的最大值或者最小值。查找时先查找到对应的索引,即可较快的找到目标数据。

    二分查找索引表,在索引表中定块采用顺序方法进行查找

    二分查找索引表,在索引表中定块采用顺序方法进行查找

    索引顺序查找的设计与实现数据结构课程设计

    索引顺序查找(分块查找)的设计与实现 (1) 要求能自动建立索引表; (2) 对任意待查找的关键字,若查找成功,给出其关键字比较次数。

    查找算法.doc

    简单顺序查找、有序表的二分查找、索引表的顺序查找。这里主要介绍前两种。 一、简单顺序查找 简单顺序查找对数据表的特性没有要求,即是否具有递增递减特性基本不影响查找的性能。基本就是从表的一段开始逐个比较...

    顺序表的查找

    很实用的一个课设文档,希望大家阅览和下载哦!

    3种查找算法——数据结构实验

    3种查找算法,顺序查找 折半查找 索引查找,c语言编写,可直接运行

    数据结构 分块查找算法

    分块查找又称索引顺序查找,它是顺序查找的一种改进方法。 方法描述:将n个数据元素"按块有序"划分为m块(m ≤ n)。每一块中的结点不必有序,但块与块之间必须"按块有序";即第1块中任一元素的关键字都必须小于第2...

    mysql多条件索引

    如果查询语句使用索引(通常是where条件匹配索引)就会利用树的结构加快查找,索引会按值查找到要查找的行在表中位置,不需回表查询数据的就是聚簇索引(索引和数据存放在一起)。通常是需要回表再查数据,需要消耗...

    高级语言查找和排序代码.pdf

    静态查找表:顺序查找 有序表查找 索引顺序表查找 动态查找表:二叉排序树 平衡二叉树 B-树、 B+树 哈希表:哈希函数构造方法 处理冲突的方法 哈希表的查找过程 排序算法 插入排序 交换排序 选择排序 归并排序 ...

    数据结构-查找算法-C语言

    (1)掌握顺序查找,二分法查找和索引查找的算法思想及程序实现方法。 (2)掌握二叉排序树、AVL树的查找、插入、删除、建立算法的思想及程序实现方法。 (3)掌握散列存储结构的思想,能选择合适散列函数,实现...

    分块查找算法实现

    分块查找,是对顺序查找的一种改进。 将查找表分成若干子表(块),并对子表建立索引表。 索引表包括:关键字段、起始位置和块表长度。

    关于SQL Server中索引使用及维护简介

    聚簇索引的索引页面指针指向数据页面,所以使用聚簇索引查找数据几乎总是比使用非聚簇索引快。每张表只能建一个聚簇索引,并且建聚簇索引需要至少相当该表 120%的附加空间,以存放该表的副本和索引中间页。 SQL ...

    mysql数据库设计为表连接设计索引

    只用于访问一张表的谓词称为本地谓词,定义了表和表之间的连接关系的谓词称为连接谓词。连接谓词大部分是基于主键=外键这一条件,这是是最快的连接方式了。有三种扫描方式: 循环嵌套:首先在外层表中找到一行满足...

    查找算法的比较

    顺序查找只是从头到尾进行遍历。二分查找则是先对数据进行排序,然后利用三个标志,分别指向最大,中间和最小数据,接下来根据待查找数据和中间数据的比较不断移动标志,直至找到。二叉排序树则是先构造,构造部分...

    C++数据结构实验五:查找排序

    3. 掌握查找的概念、静态查找与动态查找、顺序查找、二分查找、索引查找等算法思想。 4. 掌握二叉排序树的概念、平衡二叉树等算法思想。 5. 掌握哈希查找、直接插入排序、快速排序、冒泡排序、简单选择排序等算法...

Global site tag (gtag.js) - Google Analytics