开始复习复习数据结构。

数据结构的基本概念

术语

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

数据结构三要素

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

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

算法和算法的评价

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

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

算法效率度量

时间复杂度

空间复杂度

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