本系列笔记来自于«大话数据结构»

本节纲要图示

数据结构基本概念

基本概念和术语

数据

是描述客观事物的特号, 是计算机可以操作的对象, 是能被计算机识别, 并输入给计算机处理的符号集合.

Tip: 数据不仅仅包括整型, 实型等数值类型,还包括字符及声音, 图像, 视频等非数值类型.

数据元素

是组成数据的, 有一定意义的基本单位, 在计算机中通常作为整体处理, 也被称为记录.

Tip: 比如人类中, 人就是数据元素.

数据项

一个数据元素可以由若干数据项组成.

Tip: 比如人这样的数据元素, 可以由眼, 耳, 手, 脚等这些数据项组成.

数据项是数据不可分割的最小单位

数据对象

是性质相同的数据元素的集合, 是数据的子集.

Tip: 什么叫性质相同呢?在人这个数据元素中, 都有相同的数据项, 如姓名, 生日, 性别等.

数据结构

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

逻辑结构与物理结构

逻辑结构

是指数据对象中数据元素之间的相互关系.

集合结构

集合结构中的数据元素除了同属于一个集外, 它们之间没有其他关系.

各个数据元素是"平等"的.

image-20210126203852796

线性结构

线性结构中的数据元素之间是一对一的关系

image-20210126204101002

树形结构

树形结构中的数据元素之间存在一种一对多的层次关系

image-20210126204136991

图形结构

图形结构的数据元素是多对多的关系

  1. 将每一个数据元素看做一个结点, 用圆圈表示.
  2. 元素之间的逻辑关系用结点之间的连线表示, 如果这个关系是有方向的, 那么用带箭头的连线表示.

image-20210126204217410

物理结构

是指数据的逻辑结构在计算机的存储形式.

数据元素的存储结构形式有两种: 顺序存储和链式存储

顺序存储结构

是把数据元素存放在地址连续的存储单元里, 其数据间的逻辑关系和物理关系是一致的.

什么是数据结构- 知乎

链式存储结构

链式存储非常灵活, 数据存在哪里不重要, 只要有一个指针存放相应的地址就能找到它了.

是把数据元素存放在任意的存储单元里, 这组存储单可以是连续的, 也可以是不连续的.

image-20210126205155383

抽象数据类型

抽象是指抽取出事物具有的普遍的本质.

它是抽出问题的特征而忽略非本质的细节, 是对具体事物的一个概括.

抽象是一种思考问题的方式,它隐藏了繁杂的细节, 只保留实现目标所必需的信息

数据类型

是指一组性质相同的值的集合及定义在此集合上的一些操作的总称.

如GO语言中, 按照取值的不同, 数据类型可以分为两类:

  1. 原子类型: 是不可以再分解的基本类型. 如整型, 字符型,浮点型等
  2. 结构类型: 由若干个类型组合而成, 是可以再分解的, 如结构体, struct

抽象数据类型

Abstract Data Type, ADT

是指一个数学模型及定义在该模型上的一组操作.

Tip: 如游戏里, 一组基本操作, 走(前进, 后退, 上, 下), 跳, 使用技能等.

一个抽象数据类型定义了: 一个数据对象, 数据对象中各数据元素之间的关系及对数据元素的操作

big-white