数据结构——绪论

一、绪论

(一)基本概念

数据:数据是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素:数据元素是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成,数据项是构成数据元素的不可分割的最小单位。

数据对象:数据对象是性质相同的数据元素的集合,是数据的一个子集。

数据结构:数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

数据元素都不是孤立存在的,而是在它们之间存在着某种关系,这种数据元素相互之间的关系称为结构

数据结构三要素:

1、逻辑结构

结构定义中的“关系”描述的是数据元素之间的逻辑关系,因此又称为数据的逻辑结构

根据数据元素之间关系的不同特性,通常有下列4类基本结构:

  • 集合:结构中的数据元素之间除了“同属于一个集合”的关系外,别无其他关系。

  • 线性结构:结构中的数据元素之间存在一个对一个的关系。除了第一个元素,所有元素都有唯一的前驱;除了最后一个元素,所有元素都有唯一后继。

  • 树形结构:结构中的数据元素之间存在一个对多个的关系

  • 图状结构或网状结构:结构中的数据元素之间存在多个对多个的关系

2、数据的运算

针对于某种逻辑结构,结合实际需求,定义基本运算。

3、物理结构(存储结构)

数据结构在计算机中的表示称为数据的物理结构,又称为存储结构

数据元素之间的关系在计算机中有两种不同的表达式:顺序映射非顺序映射,并由此得到两种不同的存储结构:顺序存储结构链式存储结构

顺序映射:特点是接触元素在存储器中的相对位置来表示数据元素之间的逻辑关系。

非顺序映射:特点是借助指示元素存储地址的指针表示数据元素之间的逻辑关系。

(1)顺序存储

把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中,元素之间的关系由存储单元的邻接关系来体现。

(2)链式存储

逻辑上相邻的元素在物理位置上可以不相邻,借助指示元素存储地址的指针来表示元素之间的逻辑关系。

(3)索引存储

在存储元素信息的同时,还建立附加的索引表。索引表中的每项称为索引项,索引项的一般形式是(关键字,地址)

(4)散列存储

根据元素的关键字直接计算出该元素的存储地址,又称哈希(Hash)存储。

4、总结

(1)若采用顺序存储,则各个数据元素在物理上必须是连续的;若采用非顺序存储,则各个数据元素在物理上可以是离散的。

(2)数据的存储结构会影响存储空间分配的方便程度

(3)数据的存储结构会影响对数据运算的速度

运算的定义是针对逻辑结构的,指出运算的功能;

运算的实现是针对存储结构的,指出运算的具体操作步骤。

数据类型和抽象数据类型

数据类型

数据类型是一个值的集合和定义在此集合上的一组操作的总称。

  • 原子类型。其值不可再分的数据类型。

  • 结构类型。其值是由若干个成分按某种结构组成的,因此是可以再分解的,并且它的成分可以是非结构的也可以是结构的。

抽象数据类型(Abstract Data Type,ADT)

抽象数据组织及与之相关的操作。

抽象数据类型的定义由一个值域和定义在该值域上的一组操作组成。若按照其值的不同特性可以分为3种:

  • 原子类型:原子类型的变量的值是不可分解的。这类抽象数据类型较少,因为一般情况下,已有的固有数据类型足以满足需求。

  • 固定聚合类型:该类型的变量,其值由确定数目的成分按某种结构组成。

  • 可变聚合类型:和固定聚合类型相比较,构成可变聚合类型“值”的成分的数目不确定。

显然,后两种类型可统称为结构类型。

(二)算法和算法分析

1、算法

算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作。一个算法还具有下列5个重要特性:

(1)有穷性:一个算法必须总是(对任何合法的输入值)在执行有穷步之后结束,且每一步都可在又穷时间内完成。

(2)确定性:算法中每一条指令必须有确切的含义,读者理解时不会产生二义性。并且在任何条件下,算法只有唯一的一条执行路径,即对于相同的输入只能得出相同的输出。

(3)可行性:一个算法是能行的,即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。

(4)输入:一个算法有零个或多个的输入,这些输入取自于某个特定的对象的集合。

(5)输出:一个算法有一个或多个的输出,这些输出是同输入有着某些特定关系的量。

2、算法设计要求

通常设计一个“好”的算法应考虑达到以下目标:

(1)正确性:算法应当满足具体问题的需求。

(2)可读性:算法应具有良好的可读性,以帮助人们理解。

(3)健壮性:输入非法数据时,算法能适当地做出反应或进行处理,而不会产生莫名其妙的输出结果。

(4)效率与低存储量需求:效率指的是算法执行的时间。存储量需求值算法执行过程中所需要的最大存储空间。

3、算法效率的度量

算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。而度量一个程序的执行时间通常有两种方法:

(1)事后统计的方法

(2)事前分析估算的方法

一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间度量记作:

                ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​T(n) = O( f(n) )

它表示随问题规模n的增大,算法执行时间的增长率和f(n) 的增长率相同,称做算法的渐近时间复杂度,简称时间复杂度

结论一:顺序执行的代码只会影响常数项,可以忽略。

结论二:只需挑循环中的一个基本操作分析它的执行次数与n的关系即可。

结论三:如果有多层嵌套循环,只需关注最深层循环了几次。

4、算法的存储空间需求

空间复杂度:空间开销(内存开销)与问题规模n之间的关系。

空间复杂度作为算法所需存储空间的亮度,记作:

        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        S(n) = O( f(n) )

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/55448.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

消息队列总结(4)- RabbitMQ Kafka RocketMQ高性能方案

1.RabbitMQ的高性能解决方案 1.1 发布确认机制 RabbitMQ提供了3种生产者发布确认的模式: 简单模式(Simple Mode):生产者发送消息后,等待服务器确认消息已经被接收。这种模式下,生产者发送消息后会阻塞&am…

学习系统编程No.34【线程同步之信号量】

引言: 北京时间:2023/7/29/16:34,一切尽在不言中,前几天追了几部电视剧,看了几部电影,刷了n个视屏,在前天我们才终于从这快乐的日子里恢复过来,然后看了两节课,也就是上…

真机搭建中小网络

这是b站上的一个视频,演示了如何搭建一个典型的中小网络,供企业使用 一、上行端口:上行端口就是连接汇聚或者核心层的口,或者是出广域网互联网的口。也可理解成上传数据的端口。 二、下行端口:连接数据线进行下载的端…

Scratch Blocks自定义组件之「旋律播放」

一、背景 看到microbit edit有旋律编辑器,就在scratch块中也写了一个,如下图所示 这是我写的 这是Micro:bit的 二、功能配置说明 支持8个音符8拍旋律控制 三、使用说明 (1)引入添加field_tone.js到core文件夹中,代码在…

信息系统网络安全整改方案

第1章 项目概述 1.1 项目目标 本方案将通过对公司网络信息系统的安全现状进行分析工作,参照国家信息系统等级保护要求,找出信息系统与安全等级保护要求之间的差距,给出相应的整改意见,推动 XX 企业公司网络信息系统安全整改工作的…

计算机毕设 深度学习手势识别 - yolo python opencv cnn 机器视觉

文章目录 0 前言1 课题背景2 卷积神经网络2.1卷积层2.2 池化层2.3 激活函数2.4 全连接层2.5 使用tensorflow中keras模块实现卷积神经网络 3 YOLOV53.1 网络架构图3.2 输入端3.3 基准网络3.4 Neck网络3.5 Head输出层 4 数据集准备4.1 数据标注简介4.2 数据保存 5 模型训练5.1 修…

与“云”共舞,联想凌拓的新科技与新突破

伴随着数字经济的高速发展,IT信息技术在数字中国建设中起到的驱动和支撑作用也愈发凸显。特别是2023年人工智能和ChatGPT在全球的持续火爆,更是为整个IT产业注入了澎湃动力。那么面对日新月异的IT信息技术,再结合疫情之后截然不同的经济环境和…

【抖音小游戏】 Unity制作抖音小游戏方案 最新完整详细教程来袭【持续更新】

前言 【抖音小游戏】 Unity制作抖音小游戏方案 最新完整详细教程来袭【持续更新】一、相关准备工作1.1 用到的相关网址1.2 注册字节开发者后台账号 二、相关集成工作2.1 下载需要的集成资源2.2 安装StarkSDK和starksdk-unity-tools工具包2.3 搭建测试场景 三、构建发布3.1 发布…

【深度学习】MAT: Mask-Aware Transformer for Large Hole Image Inpainting

论文:https://arxiv.org/abs/2203.15270 代码:https://github.com/fenglinglwb/MAT 文章目录 AbstractIntroductionRelated WorkMethod总体架构卷积头Transformer主体Adjusted Transformer Block Multi-Head Contextual Attention Style Manipulation Mo…

探索Vue组件通信的秘密:打破隔阂,实现数据共享

一、Vue组件通信 每个组件都有自己的数据, 提供在data中, 每个组件的数据是独立的, 组件数据无法互相直接访问 (合理的)但是如果需要跨组件访问数据, 就需要用到组件通信 要是有一万个商品????就要写一万个吗?函数调用…

KubeSphere 3.4.0 发布:支持 K8s v1.26

2023 年 07 月 26 日,KubeSphere 开源社区激动地向大家宣布,KubeSphere 3.4.0 正式发布! 让我们先简单回顾下之前三个大版本的主要变化: KubeSphere 3.1.0 新增了“边缘计算”、“计量计费” 等功能,将 Kubernetes 从…

myeclipse的Debug模式

1.表示当前实现继续运行直到下一个断点,快捷键为F8。 2.表示打断整个进程 3.表示进入当前方法,快捷键为F5。 4.表示运行下一行代码,快捷键为F6。 5.表示退出当前方法,返回到调用层,快捷键为F7。 6.表示当前线程的…

kotlin 编写一个简单的天气预报app(五)增加forcast接口并显示

参考资料 OpenWeatherMap提供了一个/forecast接口,用于获取未来几天的天气预报。你可以使用HTTP GET请求访问该接口,并根据你所在的城市或地理坐标获取相应的天气数据。 以下是一个示例请求的URL和一些常用的参数: URL: http://api.openwe…

我的创作纪念日——256天

机缘 最开始我写博客没有什么特别的原因,主要是因为以下几点: 练习自己的语言组织能力 记录自己学习生活中学到的知识 为和我同一个学习阶段的朋友提供帮助 事实上最开始我根本不指望我的博客有多少人看,主要是想找一个好的保存 Markdown 笔…

花费7元训练自己的GPT 2模型

在上一篇博客中,我介绍了用Tensorflow来重现GPT 1的模型和训练的过程。这次我打算用Pytorch来重现GPT 2的模型并从头进行训练。 GPT 2的模型相比GPT 1的改进并不多,主要在以下方面: 1. GPT 2把layer normalization放在每个decoder block的前…

PHP最简单自定义自己的框架(一)

为啥要定义自己的框架: 定制化需求:每个项目都有不同的需求和特点,使用通用的框架可能无法满足所有的要求。自定义框架可以根据具体需求进行定制,提供更加灵活和符合项目需求的解决方案。学习和成长:自定义框架是一个很…

STM32存储左右互搏 I2C总线读写EEPROM ZD24C1MA

STM32存储左右互搏 I2C总线读写EEPROM ZD24C1MA 在较低容量存储领域,EEPROM是常用的存储介质,不同容量的EEPROM的地址对应位数不同,在发送字节的格式上有所区别。EEPROM是非快速访问存储,因为EEPROM按页进行组织,在连…

一文搞懂Redis架构演化之路

目录 从最简单的开始:单机版 Redis 数据持久化:有备无患 主从复制:多副本 哨兵:故障自动切换 分片集群:横向扩展 总结 这篇文章我想和你聊一聊 Redis 的架构演化之路。 现如今 Redis 变得越来越流行,…

图为科技加入深圳市智能交通行业协会 ,打 …

图为科技加入深圳市智能交通行业协会,打造智能交通新生态! 交通是国民经济发展的“大动脉”,交通拥堵、事故频发等问题不仅影响了人们的出行体验,也对经济的发展产生了负面影响。安全、高效、便捷的出行,一直是人们的…

【Unity实用插件篇】| 学会使用 可编程瓦片Tile Map,快速搭建2D地图

前言【Unity 实用插件篇】| 学会使用 可编程瓦片Tile Map,快速搭建2D地图一、导入 Tile Map Editor二、创建调色板 Tile Palette三、快速绘制地图四、TilePalette 调色板功能介绍五、TileMap 相关组件属性介绍GirdTilemapTilemap Renderer 瓦片地图渲染器Tile Assets 瓦片资源…