文档介绍：计算机软件技术基础
数据结构与算法(5)
1
数据结构研究的内容
2
查找
基本概念
——若表中存在特定元素,称查找成功(应输出该记录)
——否则,称查找不成功(也应输出失败信息)
查找表
查找
查找成功
查找不成功
静态查找
动态查找
关键字
——由同一类型的数据元素(或记录)构成的集合。
——查询(Searching)特定元素是否在表中。
——只查找,不改变集合内的数据元素。
——既查找,又改变(增减)集合内的数据元素。
——记录中某个数据项的值,可用来识别一个记录
(预先确定的记录的某种标志)
例如“学号”
是一种数据结构
3
讨论2:对查找表常用的操作有哪些?
查询某个“特定的”数据元素是否在表中;
查询某个“特定的”数据元素的各种属性;
在查找表中插入一元素;
从查找表中删除一元素。
讨论3:有哪些查找方法?
查找方法取决于表中数据的排列方式;
讨论1:查找的过程是怎样的?
给定一个值K,在含有n个记录的文件中进行搜索,寻找一个关键字值等于K的记录,如找到则输出该记录,否则输出查找不成功的信息。
例如查字典
针对静态查找表和动态查找表的查找方法也有所不同。
“特定的”=关键字
4
讨论4:如何评估查找方法的优劣?
明确:查找的过程就是将给定的K值与文件中各记录的关键字项进行比较的过程。所以用比较次数的平均值来评估算法的优劣。称为平均查找长度ASL。
其中:
n是文件记录个数;
pi是查找第i个记录的查找概率(通常取等概率,即Pi =1/n);
ci是找到第i个记录时所经历的比较次数。
统计意义上的数学期望值
物理意义:假设每一元素被查找的概率相同,则查找每一元素所需的比较次数之总和再取平均,即为ASL。
显然,ASL值越小,时间效率越高。
Average Search Length
5
一、顺序查找( Linear search,又称线性查找)
顺序查找:用逐一比较的办法顺序查找关键字,这显然是最直接的办法。
假定记录按逻辑次序顺序存储在一个连续存储区中,n个记录用数组R[1..N] 表示,用C语言说明如下:
#define N 100 //数组长度常量
typedef int keytype; //关键字类型定义
typedef struct{
keytype key; //关键字数据项
othertype otherdata; //其他数据项
} Element; //数据元素类型定义
typedef Element Sqlist[N+1]; //数组定义
6
int Seq_Search (Sqlist R , KeyType k ){
int i;
R[0].key =k;
for( i=n; [i].key!=k; i - - );
return i;
} // Search_Seq
算法的实现:
技巧:把待查关键字key存入表头或表尾(俗称“监视哨”),这样可以加快执行速度。
例:
若将待查找的特定值key存入顺序表的首部(如0号单元),并从后向前逐个比较,就不必担心“查不到”。
//在顺序表R中,查找关键字与k相同的元素;若成功,返回其位置信息,否则返回0
//设立监视哨,可免去查找过程中每一步都要检测是否查找完毕。当n>1000时,查找时间将减少一半。
//找不到=不成功,返回值必为i=0;
//找得到=成功,返回值i正好代表所找元素的位置。
监视哨在顺序表的首部,所以扫描的方向必须是从后向前。
7
返回特殊标志,例如返回空记录或空指针。前例中设立了“监视哨”,[0].key使之结束,并返回 i=0。
讨论2:查找效率怎样计算?
用平均查找长度ASL衡量。
讨论1:查找失败怎么办?
讨论3:如何计算ASL?
分析:
查找第1个元素所需的比较次数为1;
查找第2个元素所需的比较次数为2;
……
查找第n个元素所需的比较次数为n;
总计全部比较次数为:1+2+…+n = (1+n)n/2
未考虑查找不成功的情况:查找监视哨所需的比较次数为n+1
这是查找成功的情况
若求某一个元素的平均查找次数,还应当除以n(等概率),
即:ASL=(1+n) / 2 ,时间效率为 O(n)
8
二、折半查找(又称二分查找或对分查找)
优点:算法简单,且对顺序结构或链表结构均适用。
缺点: ASL 太大,时间效率太低。
这是一种容易想到的查找方法。
先给数据排序(例如按升序排好),形成有序表,然后再将key与正中元素相比,若key小,则缩小至右半部内查找;再取其中值比较,每次缩小1/2的范围,直到查找成功或失败为止。