数据结构

定义

• 基本的数据组织和数据处理方法

  1. 各种数据的逻辑结构表示
  2. 各种数据的存储结构表示
  3. 各种数据结构的运算定义
  4. 设计实现运算的算法(以数据结构为中心的算法设计--也就是基本算法设计方法，再高一层就是通用算法设计)
  5. 分析算法的效率(时间复杂度、空间复杂度分析，设计出求解问题的高效算法)

如何组织数据跟数据的规模以及存储的地方是有关系，就像图书与书架的关系！！

新书如何插入？如何找到某一本书？

解决问题方法的效率，跟数据的组织方式是直接相关的，跟空间的利用效率有关, 跟算法的巧妙程度有关系

定义(差不多的)：数据对象在计算机中的组织方式 ， 必定与一系列加在其上的操作相关联， 完成这些操作的方法就是算法，算法与数据结构始终是一起的。

根据数据结构的逻辑特性 -> 映射到计算机中的存储结构 -> 运算实现算法设计（数据运算高效实现）

数组结构中讨论的元素关系主要是指相邻关系或邻接关系

• 同一逻辑结构可以对应多种存储结构
• 同样的运算，在不同的存储结构中，其实现过程也是不同的

逻辑结构

1. 集合
2. 线性结构
   1. 简单： 线性表、栈、队列、散列表
   2. 复杂： 广义表、多维数组、文件...
3. 树形结构
4. 图形结构

存储结构

1. 顺序存储结构
2. 链式存储结构
3. 索引存储结构
4. 哈希(散列)存储结构

抽象数据类型

• （ADT）是描述数据结构的方法， 这个是重点，面向对象时，就是将一类对象抽象成一种数据类型的过程，抽象好了可大大提高开发效率
• 指的是从求解问题的数学模型中抽象出来的数据逻辑结构和运算，不考虑计算机的具体实现
• = 逻辑结构 + 抽象运算
• 实质上就是对一个求解问题的形式化描述，程序员可以在理解基础上实现它
• 通常把基于存储结构的运算实现的步骤或过程称为算法
• 数据类型： 是一个值的集合和定义在此集合上的一组操作的总称，是已经实现了的数据结构，包括数据对象集，数据集合相关联的操作集，只描述数据对象集、相关操作集是什么，不涉及其他
• 抽象： 指描述数据结构的方法不依赖于具体实现，与存放数据的机器无关；与数据存储的物理结构无关；与实现操作的算法和编程语言都无关
• 有定义数据结构就是ADT的物理实现

            eg:
            类型名称： 矩阵（Matrix）
            数据对象集：
            操作集：
                Matrix create(int M, int N):
                int getMaxRow(Matrix A):
                int getMaxCol(Matrix A):
                // 这里的ElementType 根据矩阵元素的值的类型而定，并不明确指定其类型
                ElementType getEntry(Matrix A, int i; int j):
                Matrix add(Matrix A, Matrix B):
                ...