网络与信息安全-数据结构作业1-数据结构基本概念

数据结构(逻辑结构 / 存储结构 / 数据的运算)

逻辑结构

  • 数据的逻辑结构指的是数据元素之间的逻辑关系,就是从逻辑关系上描述数据,与数据的存储无关,独立于计算机的,数据的逻辑结构分为线性结构 和 非线性结构,线性表是典型的线性结构,集合/树/图是典型的非线性结构

    • 集合结构中的数据元素之间仅有 属于同一集合的关系
    • 线性结构中的数据元素之间仅存在 一对一 的关系
    • 树形结构元素之间存在一对多关系,线性结构元素之间存在一对一关系,图形 / 网状结构元素之间存在多对多关系


    数据的逻辑结构分类图

    • 与数据元素本身的形式、内容、相对位置、个数无关的是数据的 (逻辑结构)

      • 存储结构是对内容和个数的体现
      • 存储实现是对内容的体现
      • 运算实现是对形式的体现
      • 逻辑实现是理论上虚拟的东西,与数据元素本身无关
    • 常见的线性的数据结构: 线性表,栈,队列,双队列,数组,串
    • 常见的非线性数据结构: 二维数组,多维数组,广义表,树(二叉树等),图,堆

存储结构

存储结构是指数据结构在计算机中的表示,也叫做物理结构。它包括数据元素的表示和关系的表示,是逻辑结构用计算机语言的实现。主要包括:顺序储存 / 链式储存 / 索引储存 / 散列储存。

  • 顺序储存: 把逻辑上相邻的元素储存在物理位置上也相邻的地方,每一次都占用一整块内存单元
  • 链式储存: 逻辑上相邻的元素在物理上不一定相邻,由指示元素储存地址的指针来表示元素之间的逻辑关系,可以不占用一整块的内存空间,但是由于使用了指示元素的指针,所以需要额外申请空间
  • 索引储存: 在储存元素的同时,建立附加的索引表,一般形式是{关键字,元素}, 类似于CPP 的 map , 检索速度提高,但是空间增大,在增删元素时,耗时增加
  • 散列储存: 根据元素的某一种性质直接计算出该元素出现的地址,类似于 Hash, 增删改元素快速,但是有可能出现碰撞的可能

数据的计算

标签: PTA, 数据结构, 笔记

仅有一条评论

  1. smx smx

    饭饭棒棒哒~

添加新评论