第一章 1.2 基本概念和术语

读书笔记-数据结构（C语言版）（第2）版 严蔚敏 数据结构基本概念和术语-数据、数据元素、数据项、数据对象 数据结构-逻辑结构和存储结构 数据类型和抽象数据类型

第一章 1.2 基本概念和术语

• 数据、数据元素、数据项和数据对象
  • 数据
    • 客观事物的符号表示，所有能输入到计算机中并被计算机程序处理的符号的总称
  • 数据元素
    • 数据的基本单位，在计算机中通常作为一个整体进行考虑和处理
  • 数据项
    • 组成数据元素，有独立含义，不可分割的最小单位
  • 数据对象
    • 性质相同的数据元素的结合，是数据的一个子集
• 数据结构
  • 相互之间存在一种或多种特定关系的数据元素集合
  • 层次
    • 逻辑结构
      • 概念
        • 数据的逻辑结构是从逻辑关系上描述数据，和存储无关，独立于计算机
      • 两个要素
        • 数据元素
        • 关系
          • 数据元素之间的逻辑关系
      • 四种基本结构
        • 集合结构
          • 数据元素之间除了属于“同一集合之外”，再无其他关系
        • 线性结构
          • 数据元素之间存在一对一的关系
        • 树结构
          • 数据元素之间存在一对多的关系
        • 图结构
          • 数据元素之间存在多对多的关系
    • 存储结构
      • 概念
        • 数据对象在计算机中的存储表示称为数据的存储结构，也称为物理结构
      • 两种基本结构
        • 顺序存储结构
          • 借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系
          • 通常借助程序设计语言中的数组类型来描述
          • 要求所有元素依次存放在一片连续的存储空间
        • 链式存储结构
          • 为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放后继元素的存储地址
          • 通常借助于程序设计语言中的指针类型来描述
          • 无需占用一整块存储空间
• 数据类型和抽象数据类型
  • 数据类型
    • 值的集合和定义在这个值集上的一组操作的总称
  • 抽象数据类型（ADT）
    • 概念
      • 一般由用户定义的、表示应用问题的数据模型，以及定义在这个模型上一组操作的总称
    • 三部分
      • 数据对象
      • 数据对象上关系的集合
      • 数据对象的基本操作的集合
    • 定义格式
      • ADT 抽象数据类型名{ 数据对象：<数据对象定义> 数据关系：<数据关系定义> 基本操作：<基本操作定义> }ADT抽象数据类型名
      • 数据对象和数据关系的定义采用数学符号和自然语言描述
      • 基本操作定义格式
        • 基本操作名（参数表） 初始条件：<初始条件描述> 操作结果：<操作结果描述>