当前位置: 首页 > news >正文

【第1章 数据结构概述】

目录

一. 基本概念

1. 数据、数据元素、数据对象

2. 数据结构

二. 数据结构的分类

1. 数据的逻辑结构可分为两大类:a. 线性结构;b. 非线性结构

2. 数据的存储结构取决于四种基本的存储方法:顺序存储、链接存储、索引存储、散列存储

3. 数据的运算

三. 数据类型

1. 基本类型、组合类型

2. 抽象数据类型

四. 算法和算法分析

1. 算法概念

2. 算法分析


一. 基本概念

1. 数据、数据元素、数据对象

数据:客观事物的符号表示,对现实世界的事物采用计算机能够识别、存储和处理的形式进行描述的符号的集合。

数据元素:数据的基本单位,可以由若干数据项组成。其中数据项包括:初等项(数据不可分割的最小单位;组合项:由若干数据项组成)

数据对象:性质相同的数据元素的集合

例如:

 每一行是一个学生的相关信息,即学生个体,则是一个数据元素;

学号、姓名、性别等信息,为数据项,其中成绩为组合项,学号为初等项;

学生情况表则是一个数据对象。

2. 数据结构

一般认为包括以下三个方面:

(1)逻辑结构:数据元素与数据元素之间的逻辑关系;

(2)存储结构(物理结构):数据元素与数据元素之间的关系在计算机中的存储表示;

(3)数据的运算:对数据的操作。

二. 数据结构的分类

1. 数据的逻辑结构可分为两大类:a. 线性结构;b. 非线性结构

(1)线性结构

有且仅有一个开始节点和终端节点,并且所有节点最多只有一个前驱和一个后继。

例如:线性表就是典型的线性结构。

(2)非线性结构

一个节点可能有多个前驱和后继。

树:一个节点最多只有一个前驱,而可以有多个后继

图:对节点的前驱和后继的个数不作限制-------------最一般的非线性结构

2. 数据的存储结构取决于四种基本的存储方法:顺序存储、链接存储、索引存储、散列存储

(1)顺序存储:把逻辑上相邻的节点存储在物理位置相邻的存储单元里,节点之间的逻辑关系用存储单元的邻接关系来体现。

注意:

  • 顺序存储主要用于线性结构,但是非线性结构也可以通过线性化的方法实现顺序存储
  • 通常顺序存储用程序语言的数组描述

(2)链接存储:对逻辑上相邻的节点不要求在存储的物理位置上也相邻,节点之间的逻辑关系由附加的指针表示。

注意:

  • 链接存储常用于非线性结构,但线性结构也可以链接存储
  • 通常链接存储用程序语言的指针描述

(3)索引存储:在存储节点数据的同时,还建立附加的索引表。索引表的每一项称为索引项。一般索引项由关键字(唯一标识该节点的数据项)和地址(节点的存储地址)组成。

(4)散列存储:根据节点的关键字计算出该节点的存储地址,然后按存储地址存放该关键字对应的数据元素。

 注意:

  • 同一种逻辑结构采用不同的存储方法,可得到不同的存储结构
  • 通常将同一逻辑结构的不同存储结构用不同的名称标识,如:
  1. 线性表的顺序存储称为顺序表;
  2. 线性表的链接存储称为链表;
  3. 线性表的散列存储称为散列表。

3. 数据的运算

同一种逻辑结构,采用同一种存储方式,如果定义的运算不同,也用不同的名称标识。如:

  • 栈:线性表插入、删除操作限制在表的一端;
  1. 若该线性表为顺序存储,则称为顺序栈;
  2. 若该线性表链式存储,则称为链式栈。
  • 队列:线性表的插入限制在表的一端,删除限制在表的另一端
  1. 若该线性表为顺序存储,则称为顺序队列;
  2. 若该线性表为链式存储,则称为链式队列。

综述:数据的逻辑结构 + 数据的存储结构 + 数据的运算 = 数据结构

三. 数据类型

1. 基本类型、组合类型

高级程序语言中,数据类型分为两种:

(1)基本数据类型:其取值范围,允许的操作,由系统预先规定;

(2)组合类型:由基本类型组合构造.

2. 抽象数据类型

Abstract Data Type,ADT,指抽象数据的组织和与之相关的操作,即将数据和操作封装在一起,使得用于程序只能通过在ATD里定义的某些操作来访问其中的数据,从而实现信息隐蔽。

四. 算法和算法分析

1. 算法概念

定义:一个有穷的指令集,这些指令为解决某一特定任务规定了一个运算系列。

算法的五大特性:

(1)输入:一个算法必须有一个或多个输入(通过输入,使得任务开始,从而算法启动有了意义),这里不同于程序的特性;

(2)输出:一个算法应该有一个或多个输出;

(3)确定性:无歧义,每一种情况,需执行的动作要严格、清晰规定;

(4)有穷性:有限个步骤结束;

(5)可行性:可通过基本操作执行完成。

2. 算法分析

一个好的算法应满足下述要求:

(1)正确性;

(2)可读性;

(3)健壮性:输入非法数据,能做出反应或处理,输出错误信息并终止执行;

(4)时间效率和存储占用量:时间开销往往和空间开销相互制约,需折中处理。

撇开与计算机软硬件相关的因素,可以认为一个特定算法“运行工作量”的大小只依赖于问题的规模,或者问题规模的函数。一般将求解问题的输入量作为问题的规模,用n表示。

时间复杂度T(n) = f(n),其中f(n)是算法所求解问题规模n的函数,当n趋于无穷大时,时间复杂度T(n)的数量级(阶)称为算法的渐进时间复杂度。即T(n) = O(f(n)).

有时,算法的时间复杂度不仅仅依赖于问题的规模,还与输入实例的初始化状态有关。

常见的时间复杂度,按数量级递增排列,有O(1) <<O(log2n)<<O(n)<<O(nlog2n)<<O(n^2)<<O(n^3)...<<O(n^k)<<O(2^n)

空间复杂度指所需存储空间的耗费,记为S(n) = O(f(n)),其中n为问题规模,f(n)为算法所处理的数据所需的存储空间与算法操作所需辅助空间之和。

相关文章:

【第1章 数据结构概述】

目录 一. 基本概念 1. 数据、数据元素、数据对象 2. 数据结构 二. 数据结构的分类 1. 数据的逻辑结构可分为两大类&#xff1a;a. 线性结构&#xff1b;b. 非线性结构 2. 数据的存储结构取决于四种基本的存储方法&#xff1a;顺序存储、链接存储、索引存储、散列存储 3. …...

【附安装包】MyEclipse2019安装教程

软件下载 软件&#xff1a;MyEclipse版本&#xff1a;2019语言&#xff1a;简体中文大小&#xff1a;1.86G安装环境&#xff1a;Win11/Win10/Win8/Win7硬件要求&#xff1a;CPU2.5GHz 内存4G(或更高&#xff09;下载通道①百度网盘丨下载链接&#xff1a;https://pan.baidu.co…...

poi-tl设置图片(通过word模板替换关键字,然后转pdf文件并下载)

选中图片右击 选择设置图片格式 例如word模板 maven依赖 <!-- java 读取word文件里面的加颜色的字体 转pdf 使用 --><dependency><groupId> e-iceblue </groupId><artifactId>spire.doc.free</artifactId><version>3.9.0</ver…...

[element-ui] el-tree 懒加载load

懒加载&#xff1a;点击节点时才进行该层数据的获取。 注意&#xff1a;使用了懒加载之后&#xff0c;一般情况下就可以不用绑定:data。 <el-tree :props"props" :load"loadNode" lazy></el-tree>懒加载—由于在点击节点时才进行该层数据的获取…...

【C++】使用 nlohmann 解析 json 文件

引言 nlohman json GitHub - nlohmann/json: JSON for Modern C 是一个为现代C&#xff08;C11&#xff09;设计的JSON解析库&#xff0c;主要特点是 易于集成&#xff0c;仅需一个头文件&#xff0c;无需安装依赖 易于使用&#xff0c;可以和STL无缝对接&#xff0c;使用体验…...

Nginx到底是什么,他能干什么?

目录 Ngnix是什么&#xff0c;它是用来做什么的呢&#xff1f; 一。Nginx简介 二&#xff0c;为什么要用Nginx呢&#xff1f; 二。Nginx应用 1.HTTP代理和反向代理 2.负载均衡 Ngnix是什么&#xff0c;它是用来做什么的呢&#xff1f; 一。Nginx简介 Nginx是enginex的简写&…...

如何判断一个java对象还活着

引用计数算法 引用计数器的算法是这样的&#xff1a;在对象中添加一个引用计数器&#xff0c;每当有一个地方引用它时&#xff0c;计数器值就加一&#xff1b;当引用失效时&#xff0c;计数器值就减一&#xff1b;任何时刻计数器为零的对象就是不可能再被使用的。 缺点&#x…...

Go语言基础之结构体

Go语言中没有“类”的概念&#xff0c;也不支持“类”的继承等面向对象的概念。Go语言中通过结构体的内嵌再配合接口比面向对象具有更高的扩展性和灵活性。 类型别名和自定义类型 自定义类型 在Go语言中有一些基本的数据类型&#xff0c;如string、整型、浮点型、布尔等数据…...

前端食堂技术周刊第 96 期:2023 CSS 状态、Nuxt 3.7、TypeScript 5.2、eBay 性能优化、贝塞尔曲线

美味值&#xff1a;&#x1f31f;&#x1f31f;&#x1f31f;&#x1f31f;&#x1f31f; 口味&#xff1a;冰镇黑乌龙 食堂技术周刊仓库地址&#xff1a;https://github.com/Geekhyt/weekly 大家好&#xff0c;我是童欧巴。欢迎来到前端食堂技术周刊&#xff0c;我们先来看…...

一文总结Redis知识点

目录 为什么基于MySQL又出现Redis&#xff1f;Redis的优点&#xff1f;Redis支持的基本命令Redis支持的数据结构1 String2 List3 Set4 Sorted Set5 Hash6 Stream 消息队列7 Geospatial 地理空间8 Bitmap 位图9 Bitfield 位域10 HyperLogLog Redis是单线程还是多线程&#xff1f…...

ARM寄存器组

CM3 拥有通用寄存器 R0‐R15 以及一些特殊功能寄存器。 R0-R7&#xff0c;通用目的寄存器 R0-R7也被称为低组寄存器&#xff0c;所有指令可以访问它们&#xff0c;它们的字长为32位&#xff0c;复位后的初始值是不可预料的。 R8-R12&#xff0c;通用目的寄存器 R8-R12也被称…...

Windows查看当前文件夹下的所有.c文件的个数

在Windows的命令提示符&#xff08;CMD&#xff09;中&#xff0c;你可以使用for循环和dir命令结合起来&#xff0c;以计算当前文件夹下所有 .c 文件的个数。 下面是一个简单的示例&#xff0c;这个批处理脚本会计算当前目录下所有 .c 文件的个数&#xff1a; echo off setlo…...

ubuntu Qt 地图离线调用

ubuntu环境下在Qt上调用百度地图_ubuntu 百度地图_拿到金像奖上课那家店的博客-CSDN博客 【Qt初入江湖】Qt QtWebEngineWidgets 底层架构、原理详细描述_鱼弦的博客-CSDN博客 Ubuntu20.04 QT无法用Qwebengine控件的解决方案&#xff08;临时&#xff09;_cmsyq的博客-CSDN博客…...

Android Studio升级到Android API 33版本后,XML布局输入没有提示

低版本的Android Studio升级到Android API 33版本后&#xff0c;XML布局输入没有提示。查一下我目前使用的Android Studio 是2021年发布&#xff0c;而Android API 33是2022年发布的&#xff0c;这是由低版本升级到高版本造成不兼容的问题。解决方法有两种&#xff1a; 第一种…...

操作XML(带命名空间)

之前文章讲述了使用c# xpath如何操作xml文件&#xff0c;在实际开发项目中&#xff0c;遇到的很多xml文件都是带有命名空间的&#xff0c;如果还是用之前的代码获取&#xff0c;那将获取到null。 本文讲解操作代码有命名空间的Xml文件&#xff0c;以及多个命名空间的xml。 <…...

二叉搜索树(C++)

二叉搜索树 概念二叉搜索树的应用二叉搜索树的实现K模型基本结构和函数声明接口实现①find——查找关键码②Insert——插入关键码③Erase——删除关键码&#xff08;重点&#xff09;时间复杂度 源码&#xff08;整体&#xff09;非递归递归 KV模型 在使用C语言写数据结构阶段时…...

软件架构知识点

常用软件架构模型分类&#xff08;5种&#xff09; 软件架构建模方法&#xff08;模型4种&#xff09; 架构师分类&#xff08;微软4种&#xff09; 系统架构设计师的角色特质&#xff08;6种&#xff09; 计算机系统组成图谱 嵌入式操作系统的特点&#xff08;5个&#x…...

C语言日常刷题6

文章目录 题目答案与解析1234567 题目 1、以下对C语言函数的有关描述中&#xff0c;正确的有【多选】&#xff08; &#xff09; A: 在C语言中&#xff0c;一个函数一般由两个部分组成&#xff0c;它们是函数首部和函数体 B: 函数的实参和形参可以是相同的名字 C: 在main()中定…...

微信小程序使用stomp.js实现STOMP传输协议的实时聊天

简介&#xff1a; uniapp开发的小程序中使用 本来使用websocket&#xff0c;后端同事使用了stomp协议&#xff0c;导致前端也需要对应修改。 如何使用 在static/js中新建stomp.js和websocket.js&#xff0c;然后在需要使用的页面引入监听代码发送代码即可 代码如下&#x…...

基于饥饿游戏算法优化的BP神经网络(预测应用) - 附代码

基于饥饿游戏算法优化的BP神经网络&#xff08;预测应用&#xff09; - 附代码 文章目录 基于饥饿游戏算法优化的BP神经网络&#xff08;预测应用&#xff09; - 附代码1.数据介绍2.饥饿游戏优化BP神经网络2.1 BP神经网络参数设置2.2 饥饿游戏算法应用 4.测试结果&#xff1a;5…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

Oracle查询表空间大小

1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)

船舶制造装配管理现状&#xff1a;装配工作依赖人工经验&#xff0c;装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书&#xff0c;但在实际执行中&#xff0c;工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...