数据结构的划分

  • 逻辑结构：独立于计算机的数学模型，以不同方式划分为：
    • 线性结构与非线性结构，栈/树
    • 集合/线性/树/图
  • 物理结构：数据在计算机中存储的结构
    • 顺序结构/链式结构/索引结构/散列结构（哈希）

数据类型和抽象数据类型

数据类型

性质相同的值的集合，以及这些值的一组操作

抽象数据类型（ADP）

指一个数据模型以及该数据模型上的一些操作（抽象运算），它是抽象的，不考虑具体计算机实现。

定义格式：

  • 数据对象
  • 数据关系
  • 基本操作
    • 基本操作名（参数表）
    • 初始条件（描述初始条件）
    • 操作结果（描述操作结果）

举例

1
2
3
4
5
6
7
8
9
10
11
12
ADP 圆形{
   数据对象：D={r,x,y|r,x,y均为实数}
   数据关系：R={<r,x,y>|r是半径，<x,y>是圆心坐标}
   基本操作：
      Circle(&C,r,x,y)构造一个圆
      double Area(C)
         初始条件：圆形存在
         操作结果：计算面积
      double Circumference(C)
         初始条件：圆形存在
         操作结果：计算周长
}

小结