文档介绍：计算机软件技术基础
教师:曾晓东
电话:**********
E_mail: zengxiaodong@
查找
一、概念和术语
二、顺序表查找
三、散列查找
四、各种查找算法的比较
计算机软件技术基础
查找与排序
查找
访问与查找都是数据结构中的重要操作,访问数据结构中数据元素的访问算法都是与具体数据结构的特性紧密相关的。
如根据下标访问数组中的数据元素,沿指针指向访问线性链表中的结点、遍历一棵二叉树等。在这一节中,我们将讨论各种查找算法,并对查找算法进行分析。
计算机软件技术基础
查找与排序
一、概念和术语
记录(record):它是由若干个数据项(或称为域)组成的数据元素,它和结点、顶点的意义完全相同。
文件(file):它是由若干记录组成的集合,即含有若干记录的表称为文件。
关键字
1)主关键字:在数据处理中,被查找的元素通常是以记录形式出现的,即每一个数据元素(记录)由若干个数据项组成,其中能用来唯一标识该记录的数据项称为主关键字。
2)次关键字:用来标识若干记录的数据项称为次关键字。
计算机软件技术基础
查找与排序
一、概念和术语
查找
给定一个值K,在含有n个记录的文件中进行查找,寻找一个关键字值等于K的记录,如果找到则输出该记录,否则输出查找不成功的信息。
动态查找与静态查找
查找的同时对表作修改操作的表称为动态查找表,否则称之为静态查找表。
计算机软件技术基础
查找与排序
一、概念和术语
平均查找长度
由于待查记录在文件中的位置随意性很大,因此通常用比较次数的平均值,即统计意义上的数学期望值来评估查找算法,称为平均查找长度(ASL):
其中,n是文件中记录的个数,Pi是查找第i个记录的查找概率,通常我们认为每个记录的查找概率相等,即Pi=1/n;Ci是找到第i个记录时所经历的比较次数。
计算机软件技术基础
查找与排序
二、顺序表查找
1、顺序查找
顺序查找又称线性查找,是一种最简单的查找方法。
1)基本思想
从第一个记录开始,逐个比较记录的关键字,直到和给定的K值相等,则查找成功;若比较结果与文件中n个记录的关键字都不等,则查找失败。
2)算法描述
顺序表的类型定义
const int MAXSIZE=100;
typedef struct{
struct elemtype data[MAXSIZE];
int length;
} listtype
结点的类型定义
typedef struct{
keywordtype key;
datatype elemdata;
}elemtype;
计算机软件技术基础
查找与排序
二、顺序表查找
int sqlistsearch(listtype *a,keywordtype k){
//在顺序表a中查找关键字k,若成功则返回记录号,否则返回-1
int i;
a->data[a->length] = k; // 设置监视哨
for(i=0;a->data[i].key!=k;i++);
if(i == a->length) return(-1); // 查找不成功
else return(i); // 查找成功
}
3)性能分析
等概率情况下,Pi=1/n,Ci=i,所以:
计算机软件技术基础
查找与排序
二、顺序表查找
2、折半查找
又称对分查找,是对有序表进行的一种查找。
1)基本思想
先找到“中间记录”,比较其关键字,
如果关键字与给定值K相等,则查找成功;
如果关键字x小于给定值K,则说明被查找记录必在前半区间内;
反之则在后半区间内。这样把查找区间缩小了一半,继续进行查找。
计算机软件技术基础
查找与排序
二、顺序表查找
5 13 17 42 46 55 70 94
low mid hig
k=55
5 13 17 42 46 55 70 94
low mid hig
5 13 17 42 46 55 70 94
low mid hig
k=12
5 13 17 42 46 55 70 94
low mid hig
5 13 17 42 46 55 70 94
hig low
查找成功
查找失败
计算机软件技术基础
查找与排序