本系列笔记来自于«大话数据结构»
本节纲要图示
基本概念和术语
数据
是描述客观事物的特号, 是计算机可以操作的对象, 是能被计算机识别, 并输入给计算机处理的符号集合.
Tip: 数据不仅仅包括整型, 实型等数值类型,还包括字符及声音, 图像, 视频等非数值类型.
数据元素
是组成数据的, 有一定意义的基本单位, 在计算机中通常作为整体处理, 也被称为记录.
Tip: 比如人类中, 人就是数据元素.
数据项
一个数据元素可以由若干数据项组成.
Tip: 比如人这样的数据元素, 可以由眼, 耳, 手, 脚等这些数据项组成.
数据项是数据不可分割的最小单位
数据对象
是性质相同的数据元素的集合, 是数据的子集.
Tip: 什么叫性质相同呢?在人这个数据元素中, 都有相同的数据项, 如姓名, 生日, 性别等.
数据结构
是相互之间存在一种或多种特定关系的数据元素的集合.
逻辑结构与物理结构
逻辑结构
是指数据对象中数据元素之间的相互关系.
集合结构
集合结构中的数据元素除了同属于一个集外, 它们之间没有其他关系.
各个数据元素是"平等"的.
线性结构
线性结构中的数据元素之间是一对一的关系
树形结构
树形结构中的数据元素之间存在一种一对多的层次关系
图形结构
图形结构的数据元素是多对多的关系
- 将每一个数据元素看做一个结点, 用圆圈表示.
- 元素之间的逻辑关系用结点之间的连线表示, 如果这个关系是有方向的, 那么用带箭头的连线表示.
物理结构
是指数据的逻辑结构在计算机的存储形式.
数据元素的存储结构形式有两种: 顺序存储和链式存储
顺序存储结构
是把数据元素存放在地址连续的存储单元里, 其数据间的逻辑关系和物理关系是一致的.
链式存储结构
链式存储非常灵活, 数据存在哪里不重要, 只要有一个指针存放相应的地址就能找到它了.
是把数据元素存放在任意的存储单元里, 这组存储单可以是连续的, 也可以是不连续的.
抽象数据类型
抽象是指抽取出事物具有的普遍的本质.
它是抽出问题的特征而忽略非本质的细节, 是对具体事物的一个概括.
抽象是一种思考问题的方式,它隐藏了繁杂的细节, 只保留实现目标所必需的信息
数据类型
是指一组性质相同的值的集合及定义在此集合上的一些操作的总称.
如GO语言中, 按照取值的不同, 数据类型可以分为两类:
- 原子类型: 是不可以再分解的基本类型. 如整型, 字符型,浮点型等
- 结构类型: 由若干个类型组合而成, 是可以再分解的, 如结构体, struct
抽象数据类型
Abstract Data Type, ADT
是指一个数学模型及定义在该模型上的一组操作.
Tip: 如游戏里, 一组基本操作, 走(前进, 后退, 上, 下), 跳, 使用技能等.
一个抽象数据类型定义了: 一个数据对象, 数据对象中各数据元素之间的关系及对数据元素的操作
