数据结构与算法
- 数据结构的三要素
- 逻辑结构
- 线性结构：线性表、栈、队列
- 非线性：树、图、集合
- 存储结构（物理结构）
- 数据的运算
- 逻辑结构
- 算法的特征
- 算法定义
- 五个特性：有穷性、确定性、可行性、输入、输出
- 效率的度量：时间复杂度、空间复杂度
数据结构的基本概念
数据：数据是信息的载体，是描述客观事物属性的数、字符以及所有计算机能识别符合的集合。是计算机程序加工的原料。
数据元素：是数据的基本单位，通常作为一个整体进行考虑和处理。
- 可由若干数据项组成，数据项是构成数据元素不可分割的最小单位。
- 例子：一个人可以抽象成一个数据元素，人的年龄、身高、性别等属性就是数据项。
数据对象：具有相同属性数据元素的集合，是数据的一个子集。例如：学生就是一个数据对象。
数据类型：值的集合和定义在值集上一组操作的总称。例如：整型变量，值集是某个区间的整数（区间大小依赖不同机器），定义的操作有加、减、乘、除和取模等算术运算。
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
- 在任何问题中，数据元素都不是孤立存在的，他们之间存在某种关系，这种数据元素之间的关系称为结构：逻辑结构、存储结构、数据运算。
- 逻辑结构和存储结构密不可分，算法的设计取决于逻辑结构，算法的实现依赖于存储结构。
数据结构三要素
逻辑结构：数据之间的逻辑关系
- 线性：数据元素只存在一对一关系
- 一般线性表
- 受限线性表：栈、队列
- 线性表推广：数组、广义表
- 非线性：没有对应、一对多、多对多
- 集合：同属集合，没有其他对应关系
- 树形结构：一对多关系
- 一般树
- 二叉树
- 图状结构：多对多
- 有向图
- 无向图
存储结构：数据结构在计算机中的表示，也称物理结构，依赖计算机语言
- 顺序存储：逻辑上相邻的元素存储在物理位置也相邻的存储单元中，元素间的关系由存储单元的邻接关系体现
- 优点：可实现随机存取，每个元素占最少的存储空间
- 缺点：只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片
- 链式存储：不要求逻辑上相邻的元素在物理位置上也相邻，借助指针表示元素之间的逻辑关系
- 优点：不会出现碎片，能充分利用所有存储单元
- 缺点：需要额外的存储空间存储指针，而且只能实现顺序存取
- 索引存储：在存储元素信息的同时，建立附加的索引表
- 优点：检索速度快
- 缺点：附加额外的空间存储索引，增删数据也要修改索引表，因而会花费较多时间
- 散列存储：根据元素的关键字计算出存储地址，又称哈希（Hash）存储
- 优点：检索、增删结点的操作都很快
- 缺点：若散列函数不好，则可能出现存储单元冲突，而解决冲突会增加时间和空间开销
数据的运算：数据的运算包括运算的定义和实现
- 运算的定义：针对逻辑结构，指出运算的功能
- 运算的实现：针对存储结构，指出运算的具体操作步骤
算法的基本概念
算法：对特定问题求解步骤的一种描述，是指令的有限序列，每条指令表示一个或多个操作。
算法的五个特性
- 有穷性：执行有穷步结束，有穷时间完成
- 确定性：每个输入对应唯一的输出
- 可行性：每个操作只能基于已实现的基本操作
- 输入：零个或多个输入
- 输出：一个或多个输出
算法效率的度量
时间复杂度：语句在算法中被执行的次数
O(1) < O(log(2)n) < O(n) < O(nlog(2)n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
空间复杂度：算法耗费的存储空间