数据结构与算法基础——第02周-线性表的顺序表示和实现-查找算法(2.4.4)

发表于 分类于 ， ， 阅读时长 ≈ 1 分钟

一 概述

  • 顺序表上的查找操作
  • 顺序表基本操作的实现——顺序表的查找
  • 顺序表基本操作的实现——顺序表的查找算法分析

二 顺序表上的查找操作

2.1 图书

ISBN 书名 定价
1 程序设计基础 25
2 单片机技术及应用 32
3 编译原理 46
4 汇编语言程序设计教程 21
5 计算机操作系统 17
6 计算机导论实验指导 18
7 使用数据结构 29
8 数据结构(C语言版) 38
9 C#面向对象程序设计 42
10 C语言程序设计 35

2.2 按值查找

  • 例如：在图书表中，按照给定书号进行查找，确定是否存在该图书
  • 如果存在：输出是第几个元素；
  • 如果不存在：输出0

三 顺序表基本操作的实现——顺序表的查找

3.1 过程

  • 在线性表L中查找与指定值e相同的数据元素的位置
  • 从表的一端开始，逐个进行记录的关键字和给定值的比较。找到则返回该元素的未知序号；未找到返回0

3.2 代码

1
2
3
4
5
6
7
8
9
int LocateElem(SqList L, ElemType e)
{
	//在线性表L中查找值为e的数据元素，返回其序号(是第几个元素)
	for(i=0;i<L.length;i++)
	{
		if(L.elem[i]==e) return i+1;//查找成功，返回序号
	}
	return 0;//查找失败，返回0
}

四 顺序表基本操作的实现——顺序表的查找算法分析

4.1 进行比较

因为查找算法的基本操作为：将记录的关键字同给定值进行比较，基本操作：L.elem[i]==e

比较次数：e=a,1次；e=b,2次；e=c,3次；...，e=g,7次

4.2 平均查找长度ASL(Average Search Length)

为确定记录在表中的位置，需要与给定值进行比较的关键字的个数的期望值叫做查找算法的平均查找长度

对含有n个记录的表，查找成功时：

1
2
3
	  n
ASL=  ∑ PiCi
     i=1

注：

  • Pi：第i个记录被查找的概率
  • Ci：找到第i个记录需比较的次数

顺序查找的平均查找长度：

ASL=P1+2P2+...+(n-1)Pn-1+nPn

假设每个记录的查找概率相等：pi=1/n，则ASLss=∑ni=1PiCi=1/n∑ni=1i=(n+1)/2