数据结构

  1. 背景及目标
  2. 定义
    1. 逻辑结构
    2. 存储结构
    3. 抽象数据类型
  3. 线性结构
    1. 线性表
      1. 一元多项式及其运算
    2. 栈
    3. 队列
  4. 树
    1. 二叉树
    2. 堆
  5. 图
    1. 高级数据结构

背景及目标

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

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

定义

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

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

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

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

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

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

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

逻辑结构表示

二元组 -- `B = (D, R)`  

D为集合，R为集合中元素的二元关系

逻辑结构

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

存储结构

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

抽象数据类型

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

  • 有定义数据结构就是ADT的物理实现

      ```s
      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):
          ...
  ```

线性结构

线性表

  1. 简称表，是零个或多个元素的有穷序列，通常可以表示为k0, k1, ... kn-1(n>=1)
  2. 线性表中的元素叫表目或者记录
  3. i 称为表目 ki 的 索引 或 下标
  4. n是表的长度

  5. 长度为零的线性表叫空表

  6. 特点

    1. 灵活，长度可增长、缩短
    2. 二元组 B = (K, R) K = {a0, a1,...an-1} R = {r} r表示前驱/后继关系，具有反对称性和传递性

一元多项式及其运算

栈

  1. LIFO last in first out
  2. 插入和删除操作都限制在表的同一端进行
  3. 应用：深搜

  4. 可以用数组来实现堆栈，也可以用链表（单向链尾不能找到前一个）来实现堆栈

     ```js
     // 抽象数据结构
     // 通常由一个一维数组和一个记录栈顶元素位置的变量组成

    ```

  • 中缀表达式转换为后缀表达式

    1. 从头到尾读取中缀表达式的每个对象
    2. 假如是运算符：直接输出
    3. 假如是左括号：压入堆栈
    4. 假如是右括号，将栈顶的运算符弹出并输出，直到遇到左括号（出栈，不输出）
    5. 运算符：
      1. 若优先级大于栈顶运算符时，则把它压栈；
      2. 若优先级小于等于栈顶运算符时，将栈顶运算符弹出并输出；
      3. 再比较新的栈顶运算符，直到该运算符大于栈顶运算符优先级为止，然后将该运算符压栈
    6. 若各对象处理完毕，则把堆栈中存留的运算符一并输出

队列

  1. FIFP first in first out
  2. 插入操作在表的一端，删除操作在另一端
  3. 应用：宽搜
  4. 也是一种受限制的线性表

树

二叉树

堆

图

高级数据结构

一个函数不仅要做好，而且要做得漂亮

results matching ""

    No results matching ""