1.3. 数据结构的基本概念¶

数据结构描述的是按照一定逻辑关系组织起来的待处理数据元素的表示及相关操作.

结构: 实体 + 关系

数据结构:

• 按照逻辑关系组织起来的一批数据
• 按一定的存储方法把它们存储在计算机中
• 在这些数据上定义了一个运算的集合

• 数据的逻辑结构

  • 从具体问题抽象出来的数据模型, 反映了事物的组成结构及之间的逻辑关系

    • 集合结构

      元素间没有需要关注的明确关系

    • 线性结构

      元素间有一种明确的先后关系 (顺序关系)

    • 非线性结构

      元素间有复杂的相互联系 (如树结构和图结构)

• 数据的存储结构

  • 解决各种逻辑结构在计算机中的物理存储表示

    • 顺序存储

      把逻辑上相邻的结点存储在物理位置上相邻的存储单元里, 结点间的逻辑关系由存储单元的邻接关系来体现

    • 链接存储

      不要求逻辑上相邻的结点在物理位置上亦相邻, 结点间的逻辑关系由附加的指针字段表示

    • 索引存储

      在储存结点信息的同时，还建立附加的索引表

    • 散列存储

      根据结点的关键字直接计算出该结点的存储地址

• 数据的运算

  建立在数据的逻辑结构之上, 其实现与数据的存储结构紧密相关

Q-1: 下列不属于线性结构的是:
• (A) 队列
• (B) 图
• (C) 散列表
• (D) 向量

Q-2: 以下哪种结构是逻辑结构, 而与存储和云散无关:
• (A) 散列表
• (B) 单链表
• (C) 顺序表
• (D) 线性表

抽象数据类型

• 简称 ADT (Abstract Data Type)
  • 定义了一组运算的数学模型
  • 与物理存储结构无关
  • 面向对象
• 隐藏运算实现的细节和内部数据结构