数据结构之绪论

一个著名公式：
程序=数据结构+算法

非数值计算：无法用数学的公式或方程来描述
描述非数值计算问题的数据模型不是数学方程，而是诸如表，树和图之类的具有逻辑关系的数据
数据结构：是一门研究非数值计算的程序设计中计算机的操作对象以及他们之间的关系和操作的学科

数据结构：

1. 逻辑结构：数据元素之间的逻辑关系
2. 物理结构｜存储结构：数据元素及其关系在计算机内存中的表示
3. 运算和实现：对数据元素可以施加的操作以及这些操作在相应的存储结构上的实现

数据结构的两个层次：

1. 逻辑结构
   描述数据元素之间的逻辑关系
   与数据的存储无关，独立于计算机
   是从具体问题抽象出来的数学模型
2. 物理结构(存储结构)
   数据元素及其关系在计算机存储器中的结构(存储方式)
   是数据结构在计算机中的表示

逻辑结构与存储结构的关系：

1. 存储结构是逻辑关系的映像与元素本身的映像
2. 逻辑结构是数据结构的抽象，存储结构是数据结构的实现
3. 两者综合起来建立了数据元素之间的结构关系

逻辑结构的种类

划分方式一

• 线性结构
  有且仅有一个开始和终端结点，并且所有节点都最多只有一个直接前趋和一个直接后继
  eg: 线性表，栈，队列，串

• 非线性结构
  一个结点可能有多个直接前趋和直接后继
  eg: 树，图

划分方式二

• 集合结构
  结构中的数据元素之间除了同属于一个集合的关系外，无任何其他关系
• 线性结构
  结构中的数据元素之间存在着一对一的线性关系
• 树形结构
  结构中的数据元素之间存在着一对多的层次关系
• 图状结构
  结构中的数据元素之间存在着多对多的任意关系

存储结构的种类

四种基本的存储结构：

• 顺序存储结构
• 链式存储结构
• 索引存储结构
• 散列存储结构