数据结构基础学习之绪论

简介

1. 参考书籍：
   • 数据结构 Java语言描述第二版
   • 大话数据结构

• 参考资料
  • https://www.cnblogs.com/skywang12345/p/3603935.html
  • https://www.geeksforgeeks.org/
• 算法可视化工具
  • https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
  • http://algorithm-visualizer.org
  • https://visualgo.net/en
• 学习的内容

1. 时间复杂度
2. 线性表的学习
3. 栈与队列学习
4. 串与数组
5. 树与二叉树的学习
6. 图的学习
7. 排序
8. 查找

• GitHub 仓库 :AlgorithmPractice

一、基本概念和术语

1. 数据(Data)

• 数据是信息的载体，是对客观事物的符号表示，能够被计算机程序识别，储存、加工和处理
• 数据还包括图像声音等非数值数据

2. 数据元素（Data Element）

• 数据元素是数据的基本单位。数据元素也称元素、结点、顶点、记录。

3. 数据项（Data Item）

• 一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成。
• 数据项是具有独立含义的最小标识单位。

4. 数据对象（Data Object）

• 是相同数据元素组成的集合

5. 数据结构（Data Structure）

一、含义：数据结构指的是数据之间的相互关系，即数据的组织形式。

二、数据结构包括内容

1. 数据逻辑结构(Logical Structure)

• 定义：
  1. 数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，独立于计算机。
  2. 逻辑结构可以看作是从具体问题抽象出来的数学模型。
  3. 数据的逻辑结构是各个数据元素之间的逻辑关系
• 分类
  • 线性结构
  • 非线性结构
    1. 集合
    2. 树形结构
    3. 图形结构

2. 数据的存储结构（Storage Structure）

• 定义：
  • 数据元素及其关系在计算机存储器内的表示，称为数据的存储结构（Storage Structure）；
  • 数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它依赖于计算机语言。
  • 对机器语言而言，存储结构是具体的。一般，只在高级语言的层次上讨论存储结构。
• 储存方式：
  1. 顺序储存方式
  2. 链式储存方式
  3. 索引储存方式
  4. 散列储存（哈希储存）方式

3. 数据的操作

• 定义：
  • 数据操作就是对数据进行某种方法的处理，也称数据运算
  • 数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。
  • 最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。

二、算法与算法分析

1. 算法：

• 定义： 对特殊问题进行求解步骤的一种描述
• 性质：
  1. 有穷性
  2. 有限性
  3. 有效性
  4. 输入
  5. 输出
• 目标：
  1. 正确性
  2. 可读性
  3. 健壮性
  4. 高效性(时间和空间)
• 时间复杂度分析
  1. 算法执行时间： 指令序列(i)的执行次数和 * 指令序列(i)执行时间
• 空间复杂度分析
  1. 表示：S(n) = O(f(n))
  2. 固定空间需求(Fix space requiremnet): 程序代码、常量、变量所占空间，与处理问题规模无关
  3. 可变空间需求(Variable space requirement): 输入数据元素和程序运行所占的空间，与处理问题规模相关