简介
- 参考书籍：
- 数据结构 Java语言描述第二版
- 大话数据结构
- 参考资料
- www.cnblogs.com/skywang1234…
- www.geeksforgeeks.org/
- 算法可视化工具
- www.cs.usfca.edu/~galles/vis…
- algorithm-visualizer.org
- visualgo.net/en
- 学习的内容
- 时间复杂度
- 线性表的学习
- 栈与队列学习
- 串与数组
- 树与二叉树的学习
- 图的学习
- 排序
- 查找
- GitHub 仓库 :AlgorithmPractice
一、基本概念和术语
1. 数据(Data)
- 数据是信息的载体，是对客观事物的符号表示，能够被计算机程序识别，储存、加工和处理
- 数据还包括图像声音等非数值数据
2. 数据元素（Data Element）
- 数据元素是数据的基本单位。数据元素也称元素、结点、顶点、记录。
3. 数据项（Data Item）
- 一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成。
- 数据项是具有独立含义的最小标识单位。
4. 数据对象（Data Object）
- 是相同数据元素组成的集合
5. 数据结构（Data Structure）
一、含义：数据结构指的是数据之间的相互关系，即数据的组织形式。
二、数据结构包括内容
- 数据逻辑结构(Logical Structure)
- 定义：
- 数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，独立于计算机。
- 逻辑结构可以看作是从具体问题抽象出来的数学模型。
- 数据的逻辑结构是各个数据元素之间的逻辑关系
- 分类
- 线性结构
- 非线性结构
- 集合
- 树形结构
- 图形结构
- 数据的存储结构（Storage Structure）
- 定义：
- 数据元素及其关系在计算机存储器内的表示，称为数据的存储结构（Storage Structure）；
- 数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它依赖于计算机语言。
- 对机器语言而言，存储结构是具体的。一般，只在高级语言的层次上讨论存储结构。
- 储存方式：
- 顺序储存方式
- 链式储存方式
- 索引储存方式
- 散列储存（哈希储存）方式
- 数据的操作
- 定义：
- 数据操作就是对数据进行某种方法的处理，也称数据运算
- 数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。
- 最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。
二、算法与算法分析
1. 算法：
- 定义： 对特殊问题进行求解步骤的一种描述
- 性质：
- 有穷性
- 有限性
- 有效性
- 输入
- 输出
- 目标：
- 正确性
- 可读性
- 健壮性
- 高效性(时间和空间)
- 时间复杂度分析
- 算法执行时间： 指令序列(i)的执行次数和 * 指令序列(i)执行时间
- 空间复杂度分析
- 表示：S(n) = O(f(n))
- 固定空间需求(Fix space requiremnet): 程序代码、常量、变量所占空间，与处理问题规模无关
- 可变空间需求(Variable space requirement): 输入数据元素和程序运行所占的空间，与处理问题规模相关