查找表(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) 对任意待查找的关键字,若查找成功,给出其关键字比较次数。
简单顺序查找、有序表的二分查找、索引表的顺序查找。这里主要介绍前两种。 一、简单顺序查找 简单顺序查找对数据表的特性没有要求,即是否具有递增递减特性基本不影响查找的性能。基本就是从表的一段开始逐个比较...
很实用的一个课设文档,希望大家阅览和下载哦!
3种查找算法,顺序查找 折半查找 索引查找,c语言编写,可直接运行
分块查找又称索引顺序查找,它是顺序查找的一种改进方法。 方法描述:将n个数据元素"按块有序"划分为m块(m ≤ n)。每一块中的结点不必有序,但块与块之间必须"按块有序";即第1块中任一元素的关键字都必须小于第2...
如果查询语句使用索引(通常是where条件匹配索引)就会利用树的结构加快查找,索引会按值查找到要查找的行在表中位置,不需回表查询数据的就是聚簇索引(索引和数据存放在一起)。通常是需要回表再查数据,需要消耗...
静态查找表:顺序查找 有序表查找 索引顺序表查找 动态查找表:二叉排序树 平衡二叉树 B-树、 B+树 哈希表:哈希函数构造方法 处理冲突的方法 哈希表的查找过程 排序算法 插入排序 交换排序 选择排序 归并排序 ...
(1)掌握顺序查找,二分法查找和索引查找的算法思想及程序实现方法。 (2)掌握二叉排序树、AVL树的查找、插入、删除、建立算法的思想及程序实现方法。 (3)掌握散列存储结构的思想,能选择合适散列函数,实现...
分块查找,是对顺序查找的一种改进。 将查找表分成若干子表(块),并对子表建立索引表。 索引表包括:关键字段、起始位置和块表长度。
聚簇索引的索引页面指针指向数据页面,所以使用聚簇索引查找数据几乎总是比使用非聚簇索引快。每张表只能建一个聚簇索引,并且建聚簇索引需要至少相当该表 120%的附加空间,以存放该表的副本和索引中间页。 SQL ...
只用于访问一张表的谓词称为本地谓词,定义了表和表之间的连接关系的谓词称为连接谓词。连接谓词大部分是基于主键=外键这一条件,这是是最快的连接方式了。有三种扫描方式: 循环嵌套:首先在外层表中找到一行满足...
顺序查找只是从头到尾进行遍历。二分查找则是先对数据进行排序,然后利用三个标志,分别指向最大,中间和最小数据,接下来根据待查找数据和中间数据的比较不断移动标志,直至找到。二叉排序树则是先构造,构造部分...
3. 掌握查找的概念、静态查找与动态查找、顺序查找、二分查找、索引查找等算法思想。 4. 掌握二叉排序树的概念、平衡二叉树等算法思想。 5. 掌握哈希查找、直接插入排序、快速排序、冒泡排序、简单选择排序等算法...