数据结构 第1章:绪论

文章目录

  • 1. 绪论
    • 1.1. 数据结构
  • 1.2. 算法
    • 1.2.1. 算法的基本概念
    • 1.2.2. 算法的时间复杂度
    • 1.2.3. 算法的空间复杂度

1. 绪论

程序 = 数据结构 + 算法

1.1. 数据结构

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

  2. 数据元素:数据的基本单位,一个数据元素可由若干数据项组成。

  3. 数据项:数据的不可分割的最小单位。

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

  5. 数据结构:指互相之间存在着一种或多种特定关系的数据元素的集合,包括逻辑结构,存储结构和对数据的运算。(数据元素都不是孤立存在的)。

  6. 抽象数据类型(ADT):指一个数学模型以及定义在该模型上的一组操作,只取决于它的一组逻辑特性,用一个三元组表示(D, S, P)。

  7. 数据类型:是程序设计语言中的一个概念,它是一个值的集合和操作的集合。

  8. 逻辑结构:是指数据之间关系的描述,与数据的存储结构无关。分为线性结构和非线性结构,通常分为四类结构:

  1. 集合:结构中的数据元素除了同属于一种类型外,别无其它关系。
  2. 线性结构:结构中的数据元素之间存在一对一的关系。
  3. 树型结构:结构中的数据元素之间存在一对多的关系。
  4. 图状结构(网状结构):结构中的数据元素之间存在多对多的关系。
  1. 存储结构:是指数据结构在计算机中的表示,又称为数据的物理结构。它包括数据元素的表示和关系的表示,通常由四种基本的存储方法实现:

数据的存储结构应正确反映数据元素之间的逻辑关系

  1. 顺序存储方式。数据元素顺序存放,每个存储结点只含一个元素,存储位置反映数据元素间的逻辑关系,存储密度大。有些操作(如插入、删除)效率较差。
  2. 链式存储方式。每个存储结点除包含数据元素信息外还包含一组(至少一个)指针,指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续,便于动态操作(如插入、删除等),但存储空间开销大(用于指针),且不能折半查找。
  3. 索引存储方式。除数据元素存储在一组地址连续的内存空间外,还需建立一个索引表,索引表中索引指示存储结点的存储位置(下标)或存储区间端点(下标)。
  4. 散列存储方式。通过散列函数和解决冲突的方法,将关键字散列在连续的有限的地址空间内,并将散列函数的值解释成关键字所在元素的存储地址。其特点是存取速度快,只能按关键字随机存取,不能顺序存取,也不能折半存取。
  1. 顺序存储与链式存储的区别
  1. 顺序储存结构
    是把数据元素存放在地址连续的存储单元里
    其数据间的逻辑关系和物理关系是一致的
  2. 链式存储结构
    是把数据元素存放在任意的存储单元里
    这组存储单元可以是连续的
    也可以是不连续的
    在这里插入图片描述

在这里插入图片描述

1.2. 算法

1.2.1. 算法的基本概念

  1. 算法:是对特定问题求解步骤的一种描述,是指令的有限序列。其中每一条指令表示一个或多个操作。
  2. 算法的特性:有穷性、确定性、可行性、输入、输出。
  3. 算法的设计目标:正确性,可读性,健壮性,高效率与低存储量需求。

算法和程序十分相似,但又有区别。程序不一定具有有穷性,程序中的指令必须是机器可执行的,而算法中的指令则无此限制。算法代表了对问题的解,而程序则是算法在计算机上的特定的实现。一个算法若用程序设计语言来描述,则它就是一个程序。

1.2.2. 算法的时间复杂度

  1. 如何计算
    找到一个基本操作(最深层循环)
    分析该基本操作的执行次数x与问题规模n的关系 x = f ( n )
    x的数量级O ( x ) O(x)O(x)就是算法时间复杂度T ( n ):O ( x ) = T ( n )

  2. 常用技巧
    在这里插入图片描述

  3. 三种复杂度
    最坏时间复杂度:考虑输入数据“最坏”的情况。
    平均时间复杂度:考虑所有输入数据都等概率出现的情况。
    最好时间复杂度:考虑输入数据“最好”的情况。

算法的性能问题只有在 n 很大时才会暴露出来

1.2.3. 算法的空间复杂度

  1. 普通程序:
  1. 找到所占空间大小与问题规模相关的变量
  2. 分析所占空间 x 与问题规模 n 的关系 x = f ( n )
  3. x 的数量级 O ( x ) 就是算法空间复杂度 S ( n )
  1. 递归程序:
  1. 找到递归调用的深度x与问题规模n的关系 x = f ( n )
  2. x的数量级 O ( x )就是算法空间复杂度 S ( n )

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Python: 如何绘制核密度散点图和箱线图?

01 数据样式 这是数据样式: 要求(我就懒得再复述一遍了,直接贴图): Note:数据中存在无效值NA(包括后续的DEM),需要注意 02 提取DEM 这里我就使用gdal去提取一下DEM列…

深度学习图像算法工程师--面试准备(2)

深度学习面试准备 深度学习图像算法工程师–面试准备(1) 深度学习图像算法工程师–面试准备(2) 文章目录 深度学习面试准备前言一、Batch Normalization(批归一化)1.1 具体步骤1.2 BN一般用在网络的哪个部分 二、Layer Normaliza…

CTP-API开发系列之八:报撤单代码实现

CTP-API开发系列之八:报撤单代码实现 CTP-API开发系列之八:报撤单代码实现前情回顾函数实现缓存FrontID 和 SessionID报单函数实现撤单函数实现 调用示例报单(形成挂单)对挂单进行撤单报单(立即成交)注意事…

XSS靶场-DOM型初级关卡

一、环境 XSS靶场 二、闯关 1、第一关 先看源码 使用DOM型&#xff0c;获取h2标签&#xff0c;使用innerHTML将内容插入到h2中 我们直接插入<script>标签试一下 明显插入到h2标签中了&#xff0c;为什么不显示呢&#xff1f;看一下官方文档 尽管插入进去了&#xff0…

系统运维网络知识汇总

一、系统运维中网络方面的规划与思考 系统运维建立在网络的基础之上&#xff0c;如果没有一个相对合理的网络架构&#xff0c;恐怕系统运维做起来也不是那么的顺手。一个公司基本上都会把网络和服务器独立开来&#xff0c;划分不同的区域摆放设备&#xff0c;很多时候都是物理…

基于Android的高校移动成绩查询系统的设计与实现

摘 要 在我国现今状态&#xff0c;互联网呈现出的高速发展状态以及高等教育的教学不断改革下&#xff0c;各高校的教务管理系统都已经从传统的纸质方式转向了基于Internet的绿色管理方式。而对于目前各高校所使用的都是浏览器/服务器&#xff08;B/S&#xff09;模式&#xff…

短视频解析接口分发系统,附带系统搭建教程

搭建教程 宝塔面板&#xff1a;Nginx系统 php7.2 Mysql 5.6-5.7 伪静态Thinkphp 上传文件直接访问域名安装即可 解析接口推荐&#xff1a;ce.qsy.mobi 源码免费下载地址抄笔记

JavaSE面试——类集框架List/Set/Queue

Collection 集成体系 Map 集成体系 List 和 Map、Set 的区别 1. 结构特点 1.存储数据类型&#xff1a; List 和 Set 是存储单列数据的集合&#xff0c;Map 是存储键和值这样双列数据的集合 2. 存储特点&#xff1a; List&#xff1a;存储数据有顺序&#xff0c;允许重复 …

kibana配置 dashbord,做可视化展示

一、环境介绍 这里我使用的kibana版本为7.17版本。 语言选择为中文。 需要已经有es&#xff0c;已经有kibana&#xff0c;并且都能正常访问。 二、背景介绍 kibana的可视化界面&#xff0c;可以配置很多监控统计界面。非常方便&#xff0c;做数据的可视化展示。 这篇文章&…

鸿蒙App基础

基础说明 .1、应用模型 .1.1、构成要素 应用组件 应用组件是应用的基本组成单位&#xff0c;是应用的运行入口。用户启动、使用和退出应用过程中&#xff0c;应用组件会在不同的状态间切换&#xff0c;这些状态称为应用组件的生命周期。应用组件提供生命周期的回调函数&…

Android 生成SO - 基础工程创建

最近需要给小伙伴扫盲一下如何使用Android Studio 生成一个SO文件&#xff0c;网上找了很多都没有合适的样例&#xff0c;那只能自己来写一个了。 原先生成SO是一个很麻烦的事情&#xff0c;现在Android Studio帮忙做了很多的事情&#xff0c;基本只要管好自己的C代码即可。 …

数据“隐领”未来!【隐私计算实训营】限时免费招募!

数智经济时代&#xff0c;为强化个人隐私信息保护&#xff0c;国家颁布了《国家安全法》、《网络安全法》、《数据安全法》等数据安全法律法规&#xff0c;并严厉处罚数据违规出海、侵权、滥用等问题。数据安全和隐私保护成为大家的共识。隐私计算技术在此背景下应运而生&#…

物联网云原生云边协同

文章目录 一、物联网平台设计1.物联网平台设计2.物联网平台实现 二、部署环境1.节点配置2.版本信息 三、物联网平台部署1.部署 Kubernetes 集群2.部署 KubeEdge3.部署 ThingsBoard 集群4.部署 ThingsBoard Edge4.1.创建 Edge 实例4.2.部署 PostgreSQL4.3.创建数据库4.4.部署 Th…

【C++】类与对象

文章目录 1. 面向过程与面向对象2. 类&#xff08;class&#xff09;类的作用域 3. 访问限定符封装 4. 类的实例化5. this指针6. 默认成员函数6.1 构造函数6.2 析构函数6.3 拷贝构造函数 1. 面向过程与面向对象 C语言是面向过程&#xff08;procedure-oriented&#xff09;的语…

“成像光谱遥感技术中的AI革命:ChatGPT应用指

遥感技术主要通过卫星和飞机从远处观察和测量我们的环境&#xff0c;是理解和监测地球物理、化学和生物系统的基石。ChatGPT是由OpenAI开发的最先进的语言模型&#xff0c;在理解和生成人类语言方面表现出了非凡的能力。本文重点介绍ChatGPT在遥感中的应用&#xff0c;人工智能…

数字脉搏:互联网的演进与社会脉络

✨✨ 欢迎大家来访Srlua的博文&#xff08;づ&#xffe3;3&#xffe3;&#xff09;づ╭❤&#xff5e;✨✨ &#x1f31f;&#x1f31f; 欢迎各位亲爱的读者&#xff0c;感谢你们抽出宝贵的时间来阅读我的文章。 我是Srlua小谢&#xff0c;在这里我会分享我的知识和经验。&am…

React-路由小知识

1.默认路由 说明&#xff1a;当访问的是一级路由时&#xff0c;默认的二级路由组件可以得到渲染&#xff0c;只需要在二级路由的位置去掉path,设置index.属性为true。 2.404路由 说明&#xff1a;当浏览器输入ul的路径在整个路由配置中都找不到对应的pth,为了用户体验&#x…

【蓝桥杯】路径之谜(DFS)

一.题目描述 小明冒充 X 星球的骑士&#xff0c;进入了一个奇怪的城堡。 城堡里边什么都没有&#xff0c;只有方形石头铺成的地面。 假设城堡地面是 nn 个方格。如下图所示。 按习俗&#xff0c;骑士要从西北角走到东南角。可以横向或纵向移动&#xff0c;但不能斜着走&#x…

如何在Linux使用Docker部署Firefox并实现无公网IP访问本地浏览器

文章目录 1. 部署Firefox2. 本地访问Firefox3. Linux安装Cpolar4. 配置Firefox公网地址5. 远程访问Firefox6. 固定Firefox公网地址7. 固定地址访问Firefox Firefox是一款免费开源的网页浏览器&#xff0c;由Mozilla基金会开发和维护。它是第一个成功挑战微软Internet Explorer浏…

基于React低代码平台开发:直击最新高效应用构建

&#x1f3e1;浩泽学编程&#xff1a;个人主页 &#x1f525; 推荐专栏&#xff1a;《深入浅出SpringBoot》《java对AI的调用开发》 《RabbitMQ》《Spring》《SpringMVC》《项目实战》 &#x1f6f8;学无止境&#xff0c;不骄不躁&#xff0c;知行合一 文章目录…