408数据结构知识点整理

绪论

数据结构的基本概念

基本概念和术语

数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。

数据对象是性质相同的数据元素的集合，是数据的一个子集。

数据类型主要有：

• 原子类型：其值不可分解的数据类型，如整型、实型、字符型等。
• 结构类型：其值可以分解为若干成分（分量）的数据类型，如数组、结构体等。
• 抽象数据类型（ADT）：一个数学模型以及定义在该模型上的一组操作。一个 ADT 就是一种数据结构

数据结构包括三方面：

• 逻辑结构：数据元素之间的逻辑关系，与存储无关。
• 存储结构：数据元素及其关系在计算机中的表示，包括数据元素的表示和关系的表示。
• 数据的运算：定义在抽象数据类型上的操作。

逻辑结构和存储结构密不可分

同样的数据元素可以组成不同的数据结构，不同的数据元素可以组成相同的数据结构。

数据结构的三要素

• 逻辑结构：数据元素之间的逻辑关系，与存储无关。分为线性结构和非线性结构。
  • 集合：除同属于一个集合外，别无其他关系。
  • 线性结构：一对一关系。
  • 树形结构：一对多关系。
  • 图状结构或网状结构：多对多关系。
• 存储结构：数据元素及其关系在计算机中的表示，包括数据元素的表示和关系的表示。
  • 顺序存储：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由存储单元的邻接关系来表示。缺点是插入和删除操作需要移动大量元素，只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片。
  • 链式存储：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系由存储单元中的指针来表示。优点是插入和删除操作不需要移动大量元素，缺点是每个元素因存储指针而占用额外的存储空间，且只能实现顺序存取。
  • 索引存储：在存储元素信息的同时，还建立附加的索引表，索引表中的每一项称为索引项，索引项的一般形式是（关键字，地址）。
  • 散列存储：根据元素的关键字直接计算出该元素的存储地址，又称哈希存储。
• 数据的运算：定义在抽象数据类型上的操作。

算法和算法评价

算法的基本概念

算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

算法的基本特征：有穷性、确定性、可行性、输入、输出

一个好的算法应该具有正确性、可读性、健壮性、高效率和低存储量的特征。

算法效率的度量

空间复杂度：算法在运行过程中临时占用的存储空间量，用 S(n) 表示，称 S(n) 为算法的空间复杂度。

算法原地工作：算法所需的辅助空间为常量，即 O(1)

时间复杂度：算法中基本操作重复执行的次数是问题规模 n 的某个函数，用 T(n) 表示，称 T(n) 为算法的时间复杂度。

顺序执行的代码只会影响常数项，因此可以忽略不计。

只需挑循环中的一个基本操作分析他的执行次数和 n 的关系。

多层嵌套循环，只需关注最深层循环中的基本操作执行次数。

最坏时间复杂度：最坏情况下算法的时间复杂度。

平均时间复杂度：所有可能输入实例在等概率出现的情况下，算法的期望运行时间。

最好时间复杂度：最好情况下算法的时间复杂度。

多项相加取最高次项，多项相乘都保留

算法的性能问题只有在 n 足够大时才会暴露出来

常见的渐进时间复杂度：

• O(1)：常数阶
• O(logn)：对数阶
• O(n)：线性阶
• O(nlogn)：线性对数阶
• O(n^2)：平方阶
• O(n^3)：立方阶
• O(2^n)：指数阶

常数阶 < 对数阶 < 幂阶 < 指数阶

常对幂指阶