开始复习复习数据结构。

数据结构的基本概念

术语

  • 数据：是信息的载体，计算机程序加工的原料。
  • 数据元素：是数据的基本单位，一个数据元素可由若干个数据项组成，数据项是最小不可分割的单位。
  • 数据对象：具有相同性质的数据元素的集合。最简单的就是一个结构体的数组，就是一个数据对象。比如学生结构体，有名字，年龄等信息。
  • 数据类型：基本有以下几种类型：
    • 原子类型：用C语言来说的话，就是属于那种 int，char 这些的数据类型。
    • 结构类型：那就是C语言的结构体呗。
    • 抽象数据类型：抽象数据阻止及相关操作。因为 C 没有抽象的概念，所以硬要说应该就是定义了一系列规则的集合，或者说拿 C++ 的泛型来理解也可以吧。
  • 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合，数据结构包括三个方面的内容：逻辑结构，存储结构和数据运算。一个算法的设计取决于逻辑结构，一个算法的实现取决于存储结构。【也很简单，比如深搜。对于图这种抽象结构，大概算法的设计是取决于它是图这样的抽象逻辑结构（从一个点开始，找到与之相连的点，然后分别递归这些点）。但是具体实现就要看你是怎么存图，比如图可以用邻接矩阵或者是链式前向星存图，虽然它们最后实现出来都是深搜这个算法，但是具体的实现是不一样的，这就是我对这句话浅显的理解】。

数据结构三要素

数据结构的三个要素就是逻辑结构、存储结果和数据运算。

  • 逻辑结构：我感觉，只要没有涉及存储方式的，一律可以认为是一种逻辑结构。比如数组，栈，堆，图，等等，因为提到这个概念你并不能确定它的存储方式，这些结构也可以有多种的存储方式。比如线性结构，非线性结构那些的。一般就是四大类：线性、树形、集合、图。
  • 存储结构：只要提到这个概念，能确定怎么存，那就是存储结构，比如：
    • 顺序存储：逻辑相邻的元素物理位置也相邻
    • 链式存储：逻辑相邻的元素物理位置不一定相邻，但有额外的开销，且随机存取复杂度高。
    • 索引存储：附加索引表，存储（关键字，地址）的形式去查找，查找较快，插入删除很慢。
    • 散列存储：查找和插入删除都很快，但是散列函数不优秀会导致冲突，解决冲突可能会有较大的开销。
  • 数据的运算：可以理解为算法了，比如线性表的排序，图的深搜广搜等等。运算是相对逻辑结构而言的，运算的具体实现取决于存储结构。

算法和算法的评价

算法是对特定问题求解步骤的描述，是由有限条指令构成。有五个特性：有穷性，确定性，可行性（描述的操作可以通过使用多次已经实现的基本运算来实现），零个或多个输入，一个或多个输出。

除此之外，还应该达到以下的目标：正确性，可读性，健壮性，以及优秀的时间复杂度和空间复杂度。

算法效率度量

时间复杂度

略

空间复杂度

算法原地工作指的是常数的空间复杂度即O（1）。