数据结构与算法基础(王卓)(25)线性表的查找(1):顺序查找(线性查找)
基本基础概念:
看这就不用去翻PPT了
查找:
关键字:
用来表示一个数据元素(或记录)的某个数据项的值
主关键字:
可以唯一地表示一个记录的关键字【例(如):准考证号】
次关键字:
用以识别若干记录的关键字【例(如):姓名为xx,成绩为xx分...】
查找表:(动态静态)
由同一类型的数据元素(或记录)构成的集合。由于集合中的数据元素之间存在着松散的关系,因此查找表是一种应用灵便的结构
静态查找表:
做查询、检索操作的查找表
动态查找表:
做插入、删除操作的查找表
对查找表常进行的几个操作:
- 1.查询某个特定的数据元素是否在查找表中
- 2.检索某个特定的数据元素的各种属性
- 3.如果查询结果为不存在,则在查找表中插入一个数据元素
- 4.如果查询结果为存在,则删除查找表中的某个数据元素
查找算法的评价标准:
关键字的平均比较次数,也叫平均查找长度(ASL)
回归程序:
一、顺序查找(线性查找)
前置条件:
#include<iostream>
using namespace std;typedef int KeyType;
//数据元素类型定义
struct ElemType
{KeyType key; //关键字域//... //其他域
};struct SSTable//Sequential Search Table
{ElemType* R; //表基址int length; //表长
};
SSTable ST; //定义顺序表ST
第一种形式:(常规)
- 从前往后逐个比较元素
- 只要指向的数组元素和我们要的目标元素一样就返回
int Search_Seq(SSTable ST, KeyType key)
//Seq:顺序
//此查找表为从1开始,0号位置为空,可按需更改
{//正序for (int i = 1; i <= ST.length; i++)if (ST.R[i].key == key)return i;return 0;//倒序/*for (int i = ST.length; i >= 1 ; i--)if (ST.R[i].key == key)return i;return 0;*/
}
第二种形式:
- 从头开始
- 只要指向的数组元素和我们要的目标元素不一样
- 就(一直)继续往后比
倒序则遍历顺序相反
int Search_Seq(SSTable ST, KeyType key)
{//正序int i;for (i = 1; ST.R[i].key != key; i++){if (i >= ST.length)break;}if (i > 0)return i;elsereturn 0;//倒序/*int i;for (i = ST.length; ST.R[i].key != key; i--){if (i <= 0)break;}if (i > 0)return i;elsereturn 0;*/
}
第三种形式:
int Search_Seq(SSTable ST, KeyType key)
{//正序int i;for (i = 1 ; ST.R[i].key != key && i <= ST.length; i++);return i;//倒序/*int i;for (i = ST.length; ST.R[i].key != key && i > 0; i--);return i;*/
}
类似:
- 从头开始
- 只要指向的数组元素和我们要的目标元素不一样 且比较的指针没有超出队伍外
- 就(一直)继续往后比
第二、三种形式的思想从根本上和第一种没有什么区别
只是第二、三种形式把不相等就进入下一轮循环放到循环的判断语句当中
的 for循环没有执行语句
顺序查找最终最简算法:
以上算法的问题(不足):
每次循环都需要进行两次比较
那么我们如何将它改进为:每次循环只需要进行一次比较,不需要进行两次比较 呢?
改进操作:
把待查关键字key存入表头(哨兵/监视哨),从后往前逐个比较
办法原理:
免去查找过程中每一步都要检查是否查找完毕的步骤
且保证无论如何函数都会有最终的返回结果
程序实现:
int Search_Seq(SSTable ST, KeyType key)
{//正序ST.R[0].key = key;int i;for (i = 1; ST.R[i].key != key; i++);return i;//倒序/*ST.R[0].key = key;int i;for (i = ST.length; ST.R[i].key != key; i--);return i;*/
}
当ST.lenath较大时,此改进能使进行一次查找所需的平均时间几乎减少一半
时间空间复杂度:(不算哨兵)
时间复杂度O(n)、空间复杂度O(1),ASL=(n+1)/2
另外, 还有一个
关于使用【ST.R[ ]】的纠纷问题,详见:
数据结构与算法基础(王卓)(26)线性表的查找(2):顺序查找(二分查找、分块查找)
中的问题(1):【ST.R[mid].key】