DataStructure

程序=算法+数据结构 ## DataStructure 遇到问题 -> 抽象信息 -> 定义相关联的数据结构

• data
• data element (alias node)
• data item
• data object (set of the data item sharing the same feature)
• data structure

两个层次：

1. 逻辑结构（数据之间抽象化的相互关系）
2. 储存结构（物理结构）数据元素及其关系 在计算机中储存方式

   逻辑结构

• 划分方法一
  1. 线性结构：一个开始一个终点，所有节点最多一个前驱和后继
  2. 非线性结构：可能多个～
• 划分方法二
  图，树， etc.

存储结构

• 顺序存储结构 借助相对位置
• 链式存储结构 借助指针

###数据类型
变量所具有的数据种类， 定义在这类上的一组运算

• 抽象数据类型
  实现信息的隐藏和封装

  ADT name{
    数据对象:
    数据关系:
    基本操作:
  }

  与该结构相关的操作都封装在类型内

线性表

• 一个首、尾节点
• 除首位节点，一个前驱一个后驱

线性表的顺序表示

顺序存储结构：把 逻辑上相邻的数据元素存储在 物理上相邻的存储单元。[数组]
空间复杂度: O(1)(没有占据辅助空间)
优点

• 存储密度大
• 可以随机存储任意数据
• 缺点*
• 在插删增改时需要移动大量元素
• 浪费空间

线性表的链式表示

链式存储结构：节点的物理位置是任意的

数组

是下标和数组值的偶对的集合