查看: 122|回复: 0

数据结构与算法概念

[复制链接]
发表于 2020-2-16 00:53:21 | 显示全部楼层 |阅读模式
数据布局小白入门

数据布局指一组相互之间存在一种或多种特定关系的数据元素的集合,
当我们需要在计算机中存储这些数据时,还涉及到数据的,组织方式,在计算机中的存储方式,以及定义在该数据上的一组操作;

  • 一组数据相互之间有某种关系
  • 组织方式
  • 存储方式
  • 以及可对其进行的一组操作
理解:

我们学习的最终目的是要在计算机中存储一组数据,但是不得不先考虑数据的组织方式,在计算机中的存储方式,以及可以对这些数据进行的一组操作,当然了既然是一组数据一定表明了这写数据之间是存在想换的关联关系的;关系大概还会有多种;
例如:

一组数据:12345
组织方式:从小到大
存储方式:可利用线性存储布局
操作:要取出最大的一个
数据布局研究方向

问题:

  • 机外处理
  • 处理要求
建模:

  • 逻辑布局
  • 基本运算
实现:

  • 存储布局
  • 算法
基本术语

数据(Data):

所有能被计算机处理的符号的集合
数据元素(DataElement):

是数据集合中的一个 个体,即数据的基本单位
数据项(DataItem):

数据元素常常可分为多少个数据项,数据项是数据具有意义的最小单位
组织数据的三个层次:

数据(表)->数据元素(行)->数据项(字段)
实际问题中的数据成为原始数据
逻辑布局(LogicalStructure)

数据元素之间的布局关系,如从小到大/一对一/一对多
物理布局(PhysicalStructure)

也会叫做存储布局,指数据在计算机内的表示,逻辑布局在计算机中的具体实现
逻辑布局

常见的逻辑布局如下:

集合:

数据元素属于同一个集合,表示为R{}; 数据之间不存在特定关系
组织布局疏松,任意两节点之间都没有邻接关系
线性:

除了起始节点d1和终端阶段dn外,每个节点都有一个前驱和一个后继,表示为R={d1,d2...dn},数据之间存在前后顺序关系
各节点按逻辑关系排列,形成一条'链'
树状:

每个元素最多有一个前驱,可以有多个后继,表示为(D,{R}),就像一个树干长了多个树枝
具备分支,层次特性,上层节点可以和下层多个节点相邻接,但是下层节点只能和一个上层节点邻接
图状:

任何两个元素之间都可以相邻接,表示为(D,{R})
注意:

逻辑布局

  • 与元素本身的形式,内容,无关
  • 元素的相对位置,无关
  • 与包含的节点个数,无关
存储布局

存储布局由 存储节点(每个存储节点存放一个数据元素) 和 节点之间的逻辑关系共同构成
反过来说,一个完整的存储布局必须可以存储数据元素,以及元素之间的逻辑关系
存储布局分类分为四种:(缺图)
顺序存储

利用索引(相对起始位置)来表示数据的逻辑布局,数据被存储在一组连续的存储单元中
特点:

  • 需预先分配长度,
  • 插入和删除慢,需要移动其他元素
  • 存取数据快捷,属于随机存储布局(可通过索引直接访问任意位置数据)
链式存储

借助元素地点指针表示数据的逻辑布局,每个元素都会包含指向下一个元素的指针
这种布局需要在节点上附加一个指针项,指出后继节点的位置,即每个节点存储单元包含两个部门:[数据项,指针项]
特点:

  • 动态分配内容,不需要预先分配内存
  • 插入删除快捷,不需要移动其他元素
  • 非随机存取布局(获取数据必须遍历前面的所有节点)
索引存储(Map是否属于索引布局 很疑惑?)

借助索引表来指示数据元素的存储位置
索引表中包含了所有数据元素的地点,查询索引表能够快速的定位到需要的数据
特点:

  • 索引是一份独立于实际存放数据,的数据布局(就像书的目录都在正文前面)
  • 索引需要占用额外的存储空间
  • 当实际数据发生改变时需要重建索引
  • 查询数据快
  • 插入修改,删除慢
散列存储(哈希表)

通过散列函数计算得出元素的位置
特点:

  • 在散列函数不变时,相同数据会得出相同的位置
  • 存入顺序和取出顺序通常不一致
  • 无法完成随机存取(指定获取某个元素)
顺序和链式是最基本的也是最常用的存储布局,需要重点掌握,包括各自的优缺点,利用场景等
链式存储布局可实现树布局(逻辑布局)
运算

运算指的是某种逻辑布局上可以进行的操作;
运算分为两类:


  • 加工型运算
    会改变原逻辑布局的内容,顺序,个数等的操作
  • 引用型运行
    与加工型运算相反
常见运算:

建立,查找,读取,插入,删除
此中:
加工型:建立,插入,删除 引用型:读取,查找

天涯海角也要找到Ni:数据结构与算法概念

相关技术服务需求,请联系管理员和客服QQ:2753533861或QQ:619920289
您需要登录后才可以回帖 登录 | 用户注册

本版积分规则

帖子推荐:
客服咨询

QQ:2753533861

服务时间 9:00-22:00

快速回复 返回顶部 返回列表