6. 数据结构 笔记
数据结构的概念
数据结构是计算机科学的基础,涵盖了数据的特性、数据之间关系的研究以及在计算机中高效存储和处理数据的方法。理解数据的逻辑结构和存储结构对于设计高效的程序和算法至关重要。
- 基本概念
- 定义: 数据结构是研究数据的特性和数据之间存在的关系,以及如何在计算机中有效存储和处理数据
- 重要性
- 早期计算机主要用于科学计算,数据对象简单,对数据结构重视不够
- 随着计算机应用的扩展,非数值计算问题变得重要,需要更复杂的数据结构来处理
- 应用案例
- 学生信息检索自动化问题,构建线性数据结构。
- 四皇后问题,利用树的结构进行探索和求解。
- 教学计划编排问题,使用图的数据结构表示课程间的先后关系。。
- 数据结构的组成
- 数据: 信息的载体,是客观事物的符号表示
- 数据项与数据元素
- 数据项: 构成数据元素的最小单位,如姓名、专业等
- 数据元素: 数据的基本单位,由若干个数据项组成,如学生信息
- 数据对象: 性质相同的数据元素的集合,如全体学生或教师
- 数据结构: 数据元素的集合及元素之间的关系,分为逻辑结构和存储结构
- 数据的逻辑结构
- 线性结构: 元素间存在一一对应的关系,有严格的先后顺序
- 非线性结构
- 集合: 所有数据元素都属于同一个集合,无联系
- 树型结构: 元素间存在一对多的关系,有层次关系
- 图状结构: 元素间存在多对多的关系,网状结构
- 数据的存储(物理)结构
- 定义
- 数据在计算机的存储表示
- 四类结构
- 顺序存储: 逻辑相邻的节点在物理位置上相邻,由存储单元的邻接关系体现
- 链式存储: 逻辑上相邻的节点在物理位置上不相邻,由附加指针字段表示
- 索引存储: 重复节点信息的同时建立附加表
- 散列存储: 根据节点的关键字直接计算存储地址
- 定义
- 运算集合
- 算法实现: 大多数运算都是通过算法实现的,算法的实现与数据的存储结构密切相关。
简单数据结构
- 线性表
- 定义: 由 N 个同一类型的数据元素组成的有限序列
- 表示: L = {a1, a2, …, aN},L 为线性表名称
- 特点
- 数据元素类型相同
- 元素间线性关系,一个接一个排列
- 支持访问、插入和删除操作
- 存储结构
- 顺序存储
- 定义
- 地址连续的一块空间存放,称为线性表
- 特点
- 第一个元素的存储地址通常称作线性表的起始位置或基地址
- 线性表的顺序存储结构是一种随机存取的存储结构,这种存储结构的线性表为顺序表
- 以数据元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系
- 定义
- 链式存储: 逻辑相邻元素物理不要求上下必须相邻,通过指针链接
- 顺序存储
- 栈和队列
- 栈: 受限的线性表,只允许在栈顶进行插入和删除
- 队列: 受限的线性表,只允许在队尾插入,在队头删除
- 树
- 定义: 由 N 个结点的有限集 T,T 为非空时,满足特定条件的非线性结构
- 术语
- 结点: 包含数据元素及指向子树的分支
- 结点的度: 节点拥有的子树数目
- 叶子(终端)节点: 度为 0 的节点
- 非终端节点:度不为 0 的节点
- 双亲与孩子: 双亲是孩子的直接前驱,孩子是双亲的直接后继
- 祖先: 从根节点到该节点路径上的所有节点
- 子孙:以某节点为根的子树中所有节点都被称为是该节点的子孙
- 兄弟节点: 同一个双亲的孩子节点互为兄弟
- 堂兄弟:双亲在同一层的节点互为堂兄弟
- 树的度: 树中所有节点度的最大值
- 结点的层次: 根节点层次为 1,其子树为 2,以此类推
- 树的深度: 树中所有节点层次的最大值
- 有序树和无序树:依据树中每棵子树从左到右的排列顺序是否可以互换
- 森林:由 M 棵互不相交的树组成的有限集
- 二叉树
- 定义
- 特殊的树形结构,每个节点最多有两棵子树
- 特点
- 每个节点最多只有两棵子树
- 左右子树有顺序不能颠倒
- 基本形态
- 空二叉树
- 只有根节点的二叉树
- 左子树为空的二叉树
- 右子树为空的二叉树
- 左右子树均非空的二叉树
- 定义
算法基础
- 算法概念
- 定义
- 解决问题的方法和步骤
- 特点
- 有限步骤
- 可执行性
- 正确性
- 有穷性
- 表示方式
- 自然语言
- 伪代码
- 流程图
- 定义
- 算法的性质
- 算法名称: 便于描述和交流,算法有特定名称(如辗转相除法)
- 输入: 需要一些初始数据或条件
- 输出: 有明确的结果作为输出
- 有效性: 每一步都是可执行的
- 正确性: 输出结果必须正确
- 有穷性: 必须在有限步骤后终止
- 算法的表示
- 自然语言: 使用日常语言描述算法
- 伪代码: 接近计算机语言,便于转换为程序
- 流程图: 使用图形符号表示算法流程
- 算法评价
- 时间复杂度
- 关注算法最耗时指令的执行次数,反映随问题规模增长的效率变化
- 空间复杂度
- 执行算法所需的存储开销,随问题规模增长的存储需求
- 优劣比较
- 时间复杂度和空间复杂度较低的算法更优
- 时间复杂度
- 算法例子
- 辗转相除法(欧几里得算法): 求两个正整数的最大公约数