您当前的位置:首页 > 电脑百科 > 程序开发 > 语言 > C/C++/C#

C语言:数据结构-线性表的查找-顺序查找

时间:2019-07-03 13:50:11  来源:  作者:

存储结构

查找表为线性表,其存储结构为一维结构数组,也即是顺序表,数组的每一个元素对应查找表的一个记录。为简单起见,设记录中只有一个整数关键字,存放记录的结构体类型描述如下:

	typedef struct
	{
	int key; /*存放关键字的成员项*/
	…… /*其它成员项*/
	} NODE;

顺序查找

顺序查找(Sequential Search)是一种最简单的查找方法。现假设查找表中有n个记录,顺序存放在某个数组a中。顺序查找的方法为:从顺序表的一端开始,将给定值依次与数组中各个记录的关键字进行比较,若在表中找到某个记录的关键字与给定值相等,则查找成功,返回记录所在位置的下标i;若在找完表中所有记录后也未找到与给定值相等的关键字的记录,则查找失败,给出失败信息。该算法适合顺序表中记录的关键字无序的情况。

顺序查找的算法

int search(NODE a[],int n, int k)

/*在a[0]~a[n-1]中顺序查找关键字等于k的记录。查找成功时返回该记录的下标,失败时返回-1*/

{

int i=0;

while(i

i++;

if(a[i].key = =k) /*查找成功*/

return i;

else return -1; /*查找失败*/

}

在该算法中,while循环语句中包含两个判断条件,势必会影响查找的速度,因此要尽可能地减少判断条件以提高效率。这里介绍一个编程小技巧来达到这一目的。具体做法是:在顺序表的末尾设置一个监视哨a[n].key,开始查找之前,先将给定关键字的值k赋给a[n].key,这样循环中就不用判断整个表是否查找完毕。具体算法如下:

改进的顺序查找算法

	int search(NODE a[],int n, int k)
	/*在a[0]~a[n-1]中顺序查找关键字等于k的记录。查找成功时返回该记录的下标,失败时返回-1*/
	{
	int i=0;
	a[n].key=k;
	while(a[i].key!=k)
	i++;
	if(i>=n)
	return -1; /*查找成功*/
	else
	return i; /*查找失败*/
	}

顺序查找的基本操作是关键字的比较。查找成功的最好情况是第一个记录就符合查找要求,只需进行一次比较;最坏情况是第n个记录符合查找要求,要进行n次比较。若每个记录的查找概率相等,即pi=1/n,且每次都是成功查找,则顺序查找的平均查找长度为:

C语言:数据结构-线性表的查找-顺序查找

对于算法8-2,查找不成功时关键字的比较次数为n+1,顺序查找的算法时间复杂度为O(n)。



Tags:数据结构   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
1 概述数据结构和内部编码 无传统关系型数据库的 Table 模型schema 所对应的db仅以编号区分。同一 db 内,key 作为顶层模型,它的值是扁平化的。即 db 就是key的命名空间。 key...【详细内容】
2021-11-01  Tags: 数据结构  点击:(28)  评论:(0)  加入收藏
Redis常用的数据结构有 string list set zset hashstringstring 是 Redis 的基本的数据类型,一个 key 对应一个 value。string 类型是二进制安全的,Redis的string可以包含任...【详细内容】
2021-10-12  Tags: 数据结构  点击:(36)  评论:(0)  加入收藏
遵从所有教材以及各类数据结构相关的书书籍,我们先从线性表开始入门。今天这篇文章更偏概念,是关于有线性表的一个知识点的汇总。上文说过,物理结构是用于确定数据以何种方式存...【详细内容】
2021-07-19  Tags: 数据结构  点击:(94)  评论:(0)  加入收藏
1. 线性表线性表是一类最简单、最常用的数据结构。简单来说,一个线性表是n个元素的有限序列,其中n≥0,通常表示为(a1,a2,...,an)。其特点是,在非空的数据元素集合中:(1)存在唯一的一个...【详细内容】
2021-06-09  Tags: 数据结构  点击:(139)  评论:(0)  加入收藏
Mysql索引数据结构下面列举了常见的数据结构 二叉树 红黑树 Hash表 B-Tree(B树)Select * from t where t.col=5我们在执行一条查询的Sql语句时候,在数据量比较大又不加索引的情...【详细内容】
2021-06-07  Tags: 数据结构  点击:(90)  评论:(0)  加入收藏
Redis五种数据结构如下: 1.String 字符串类型是redis中最基本的数据类型,一个key对应一个value。String类型是二进制安全的,意思是 redis 的 string 可以包含任何数据。如数字,...【详细内容】
2021-04-14  Tags: 数据结构  点击:(208)  评论:(0)  加入收藏
一、栈栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈...【详细内容】
2021-04-06  Tags: 数据结构  点击:(266)  评论:(0)  加入收藏
序列是python中最基本的数据结构。所谓的序列,指的是可以连续存放多个值的内存空间,序列中的每个元素都会有一个数字,即它的位置或索引。通过这个索引就能找到序列中的元素 。...【详细内容】
2021-02-24  Tags: 数据结构  点击:(197)  评论:(0)  加入收藏
不要虚度每一天,你的经验就是这样积累出来,然后用在了你的事情上面。 一:摘要概述很多 redis 的使用者都可以清晰明白的道出Redis中常用的对象如string、list、hash、set、zset...【详细内容】
2021-01-18  Tags: 数据结构  点击:(167)  评论:(0)  加入收藏
速介绍8种常用数据结构数据结构是一种特殊的组织和存储数据的方式,可以使我们可以更高效地对存储的数据执行操作。数据结构在计算机科学和软件工程领域具有广泛而多样的用途...【详细内容】
2020-12-18  Tags: 数据结构  点击:(93)  评论:(0)  加入收藏
▌简易百科推荐
一、简介很多时候我们都需要用到一些验证的方法,有时候需要用正则表达式校验数据时,往往需要到网上找很久,结果找到的还不是很符合自己想要的。所以我把自己整理的校验帮助类分...【详细内容】
2021-12-27  中年农码工    Tags:C#   点击:(2)  评论:(0)  加入收藏
引言在学习C语言或者其他编程语言的时候,我们编写的一个程序代码,基本都是在屏幕上打印出 hello world ,开始步入编程世(深)界(坑)的。C 语言版本的 hello world 代码:#include <std...【详细内容】
2021-12-21  一起学嵌入式    Tags:C 语言   点击:(11)  评论:(0)  加入收藏
读取SQLite数据库,就是读取一个路径\\192.168.100.**\position\db.sqlite下的文件<startup useLegacyV2RuntimeActivationPolicy="true"> <supportedRuntime version="v4.0"/...【详细内容】
2021-12-16  今朝我的奋斗    Tags:c#   点击:(21)  评论:(0)  加入收藏
什么是shellshell是c语言编写的程序,它在用户和操作系统之间架起了一座桥梁,用户可以通过这个桥梁访问操作系统内核服务。 它既是一种命令语言,同时也是一种程序设计语言,你可以...【详细内容】
2021-12-16  梦回故里归来    Tags:shell脚本   点击:(18)  评论:(0)  加入收藏
一、编程语言1.根据熟悉的语言,谈谈两种语言的区别?主要浅谈下C/C++和PHP语言的区别:1)PHP弱类型语言,一种脚本语言,对数据的类型不要求过多,较多的应用于Web应用开发,现在好多互...【详细内容】
2021-12-15  linux上的码农    Tags:c/c++   点击:(17)  评论:(0)  加入收藏
1.字符串数组+初始化char s1[]="array"; //字符数组char s2[6]="array"; //数组长度=字符串长度+1,因为字符串末尾会自动添&lsquo;\0&lsquo;printf("%s,%c\n",s1,s2[2]);...【详细内容】
2021-12-08  灯-灯灯    Tags:C语言   点击:(47)  评论:(0)  加入收藏
函数调用约定(Calling Convention),是一个重要的基础概念,用来规定调用者和被调用者是如何传递参数的,既调用者如何将参数按照什么样的规范传递给被调用者。在参数传递中,有两个很...【详细内容】
2021-11-30  小智雅汇    Tags:函数   点击:(19)  评论:(0)  加入收藏
一、问题提出问题:把m个苹果放入n个盘子中,允许有的盘子为空,共有多少种方法?注:5,1,1和1 5 1属同一种方法m,n均小于10二、算法分析设f(m,n) 为m个苹果,n个盘子的放法数目,则先对...【详细内容】
2021-11-17  C语言编程    Tags:C语言   点击:(49)  评论:(0)  加入收藏
一、为什么需要使用内存池在C/C++中我们通常使用malloc,free或new,delete来动态分配内存。一方面,因为这些函数涉及到了系统调用,所以频繁的调用必然会导致程序性能的损耗;另一...【详细内容】
2021-11-17  深度Linux    Tags:C++   点击:(38)  评论:(0)  加入收藏
OpenCV(Open Source Computer Vision Library)是一个(开源免费)发行的跨平台计算机视觉库,可以运行在Linux、Windows、Android、ios等操作系统上,它轻量级而且高效---由一系列...【详细内容】
2021-11-11  zls315    Tags:C#   点击:(50)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条