首页 > 代码库 > 算法学习之查找算法：静态查找表（1）顺序表查找
算法学习之查找算法：静态查找表（1）顺序表查找
引言：
对查找表一般的操作有：1、查询某个“特定的”数据元素是否在查找表中；2、检索某个“特定的”数据元素的各种属性；3、在查找表中插入一个数据元素；4、从查找表中删去某个数据元素。
静态查找表的操作只包括两种：1、查找某个“特定的”数据元素是否在查找表中；2、检索某个“特定的”数据元素的各种属性；
静态查找表又有四种表现形式：顺序表的查找、有序表的查找、静态树的查找、索引顺序表的查找。
静态查找涉及的关键字类型和数据元素类型统一说明：
/*典型关键字类型*/
typedef float KeyType; //实型
typedef int KeyType; //整型
typedef char *KeyType; //字符串型
/*数据元素类型*/
typedef struct{
KeyType key; //关键字域
..... //其他域
}SElemType;
/*对两个关键字的比较约定如下*/
//-----对数值型关键字
#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)顺序表结构定义如下：
typedef struct{
ElemType *elem; //数据元素存储空间基址，建表时按实际长度分配，0号单元留空
int length; //表长度
}SSTable；
顺序查找过程：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，若直至第一个记录，其关键字和给定值比较都不相等，则表明表中没有所查记录，查找不成功。
假设顺序表长度为10，即length=11，elem所指各个数据为：10 25 36 49 52 15 68 45 90 80 .图示顺序查找如下：
elem---> [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]
‘\0‘ 10 25 36 49 52 15 68 45 90 80
elem的0号单元为空，假设查找元素在顺序表中，比如查找36，则首先将36放入elem的0号单元中，然后依次从80开始往前比较，直到遇到3号单元中的36，查找成功。示例如下：
elem---> [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]
36 10 25 36 49 52 15 68 45 90 80 //将36放入0号单元，作为哨兵
elem---> [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]
36 10 25 36 49 52 15 68 45 90 80 //将36与80比较，不等则继续向前
elem---> [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]
36 10 25 36 49 52 15 68 45 90 80 //将36与90比较，不等则继续向前
。。。。。。。。。
依次往前移动比较元素，当比较到3号单元时，相等，则比较结束
elem---> [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]
36 10 25 36 49 52 15 68 45 90 80 //将36与36比较，相等，比较结束，返回i
如果比较的值不在顺序表中，比如给定的值为5，首先将5放入0号单元，
elem---> [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]
5 10 25 36 49 52 15 68 45 90 80 //将5放入0号单元，作为哨兵
当比较到5时，返回i的值为0。表示查找失败。以静态查找表的顺序存储结构实现：
示例代码（C语言描述）：
/*********************************************************************
Author：李冰 date：2014-9-20
Email：libing1209@126.com
*********************************************************************/
#define EQ(a, b) ((a) == (b))
#define ElemType int
typedef struct{
ElemType *elem; //数据元素存储空间基址，建表时按实际长度分配，0号单元留空
int length; //表长度
}SSTable;
//在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置,否则为0
int Search_Seq(SSTable ST, ElemType key)
{
int i;
ST.elem[0] = key; //“哨兵”
for(i = ST.length; !EQ(ST.elem[i], key); --i); //从后往前找
return i; //找不到时，i为0
}
性能分析：我们知道当讨论一个程序的性能时一般从3个角度：时间复杂度、空间复杂度、和算法的其他性能。由于在查找过程中，通常只是需要一个固定大小的辅助空间来做比较，所以空间复杂度是一定的。而时间复杂度却是可变的：其关键字和给定值进行过比较的记录个数的平均值。
适用范围：顺序查找一般适用于查找数据比较少的情况下。
优点：
1、算法实现简单且适应面广
2、对表的结构无任何要求，无论记录是否按关键字有序排列。
3、即适用于顺序表又适用于单链表。
缺点：
1、平均查找长度较大，特别是当n很大时，查找效率较低。
2、速度慢，平均查找长度为 (n + 1) / 2，时间复杂度为 O(n)
算法学习之查找算法：静态查找表（1）顺序表查找