6. 数据结构 笔记

数据结构的概念

数据结构是计算机科学的基础，涵盖了数据的特性、数据之间关系的研究以及在计算机中高效存储和处理数据的方法。理解数据的逻辑结构和存储结构对于设计高效的程序和算法至关重要。

• 基本概念
  • 定义: 数据结构是研究数据的特性和数据之间存在的关系，以及如何在计算机中有效存储和处理数据。
  • 重要性:
    • 早期计算机主要用于科学计算，数据对象简单，对数据结构重视不够。
    • 随着计算机应用的扩展，非数值计算问题变得重要，需要更复杂的数据结构来处理。
  • 应用案例:
    • 学生信息检索自动化问题，构建线性数据结构。
    • 皇后问题，利用树的结构进行探索和求解。
    • 教学计划编排问题，使用图的数据结构表示课程间的先后关系。。
• 数据结构的组成
  • 数据项与数据元素
    • 数据项: 构成数据元素的最小单位，如姓名、专业等。
    • 数据元素: 数据的基本单位，由若干个数据项组成，如学生信息。
  • 数据对象: 性质相同的数据元素的集合，如全体学生或教师。
  • 数据结构: 数据元素的集合及元素之间的关系，分为逻辑结构和存储结构。
• 数据的逻辑结构
  • 线性结构: 元素间存在一一对应的关系，有严格的顺序。
  • 非线性结构
    • 集合: 所有数据元素都属于同一个集合，无联系。
    • 树状结构: 元素间存在一对多的关系，有层次关系。
    • 图状结构: 元素间存在多对多的关系，网状结构。
• 数据的存储结构
  • 顺序存储: 逻辑相邻的节点在物理位置上相邻，由存储单元的邻接关系体现。
  • 链式存储: 逻辑上相邻的节点在物理位置上不相邻，由附加指针字段表示。
  • 索引存储: 重复节点信息的同时建立附加表。
  • 散列存储: 根据节点的关键字直接计算存储地址。
• 运算集合
  • 算法实现: 大多数运算都是通过算法实现的，算法的实现与数据的存储结构密切相关。

简单数据结构

• 线性表
  • 定义: 由N个类型相同的数据元素组成的有限序列
  • 表示: L = {I1, I2, …, IN}
  • 特点
    • 数据元素类型相同
    • 元素间线性关系，一个接一个排列
    • 支持访问、插入和删除操作
  • 存储结构
    • 顺序存储: 地址连续的一块空间存放，称为正式表
    • 链式存储: 逻辑相邻元素物理上不相邻，通过指针链接
• 栈和队列
  • 栈: 特殊的线性表，只允许在栈顶进行插入和删除
  • 队列: 特殊的线性表，只允许在队尾插入，在队头删除
• 树
  • 定义: 由N个结点的有限集T，T为非空时，满足特定条件的非线性结构
  • 基本术语
    • 节点: 包含数据元素及指向子树的分支
    • 节点度: 节点拥有的子树数目
    • 叶子节点: 度为零的节点
    • 双亲与孩子: 双亲是孩子的直接前驱，孩子是双亲的直接后继
    • 兄弟节点: 同一个双亲的孩子节点互为兄弟
  • 树的度: 树中所有节点度的最大值
  • 树的深度: 树中所有节点层次的最大值
• 二叉树
  • 定义: 特殊的树形结构，每个节点最多有两棵子树
  • 特点
    • 每个节点最多两个子树
    • 左右子树有顺序区分
  • 基本形态
    • 空二叉树
    • 只有根节点的二叉树
    • 左子树为空的二叉树
    • 右子树为空的二叉树
    • 左右子树均非空的二叉树

算法基础

• 算法概念
  • 定义: 解决问题的方法和步骤
  • 特点:
    • 有限步骤
    • 可执行性
    • 正确性
    • 有穷性
  • 表示方式:
    • 自然语言
    • 伪代码
    • 流程图
• 算法的性质
  • 名称: 便于描述和交流，经典算法有特定名称（如辗转相除法）
  • 输入: 需要一些初始数据或条件
  • 输出: 有明确的结果作为输出
  • 有效性: 每一步都是可执行的
  • 正确性: 输出结果必须正确
  • 有穷性: 必须在有限步骤后终止
• 算法表示
  • 自然语言: 使用日常语言描述算法
  • 伪代码: 接近计算机语言，便于转换为程序
  • 流程图: 使用图形符号表示算法流程
• 算法评价
  • 时间复杂度: 关注算法最耗时指令的执行次数，反映随问题规模增长的效率变化
  • 空间复杂度: 执行算法所需的存储开销，随问题规模增长的存储需求
  • 优劣比较: 时间复杂度和空间复杂度较低的算法更优
• 算法例子
  • 辗转相除法（欧几里得算法）: 求两个正整数的最大公约数
    • 步骤:
    • 输入: 两个正整数A和B
    • 输出: A和B的最大公约数