数据结构基本概念

数据结构

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。它包括数据的逻辑结构、数据的存储结构和数据的基本运算。

数据的逻辑结构

数据的逻辑结构是指数据元素之间的逻辑关系。所谓逻辑关系是指数据元素之间的关联方式或“邻接关系”。 逻辑结构与数据元素本身的形式、内容、相对位置、个数无关。逻辑结构有集合、线性结构、树形结构、图结构。

需要注意的：逻辑结构与数据元素本身形式，内容无关。 逻辑结构与数据元素的相对位置无关。 逻辑结构与所含结点个数无关。

集合、线性结构、树形结构、图结构逻辑结构示意图

集合

任意两个结点之间都没有邻接关系，组织形式松散。类似于操场上上广播体操的学生，相互之间没有关联。

线性结构

结点按逻辑关系依次排列形成一条“链”，结点之间一个一 个依次相邻接。类似于拔河比赛的一方，一根线串起来，彼此相邻。

树形结构

具有分支、层次特性，上层的结点可以和下层多个结点相邻接，但下层结点只能和上层的一个结点相邻接。类似于家族图谱有上下级关系。

图结构

最复杂，其中任何两个结点都可以相邻接。

数据的存储结构

顺序存储结构

借助数据元素的相对存储位置来表示数据元素之间的逻辑结构；

线性表的顺序存储方法：将表中的结点一次存放在计算机内存中一组连续的存储单元中。

• 预先分配好长度，需要预估存储数据需要的存储量。
• 插入和删除需要移动其他元素。
• 存取快捷，是随机存取结构。

链式存储结构

每个存储结点除了含有一个数据元素外，还包含指针，每个指针指向一个与本结点有逻辑关系的结点，用数据元素地址的指针表示数据元素之间的逻辑关系。

• 动态分配，不需要预先确定内存分配。
• 插入和删除不需要移动其他元素。
• 非随机存取结构。

索引存储方式

借助索引表中的索引指示各存储节点的存储位置。

散列存储方式

用散列函数指示各节点的存储位置。

数据的基本运算

运算是指在某种逻辑结构上施加的操作，即对逻辑结构的加工。这种加工以数据的逻辑结构为对象。一般来说，在每个逻辑结构上，都定义了一组基本运算，这些运算包括：建立、查找、读取、插入和删除等。

数据、数据元素和数据项

数据：所有被计算机存储、处理的对象。

数据元素：数据的基本单位，是运算的基本单位，又简称为元素。在程序中作为一个整体而加以考虑和处理。数据元素通常具有完整确定的实际意义。

数据项：数据元素由数据项组成。在数据库中数据项又称为字段或域。它是数据的不可分割的最小标识单位。

线性表、栈、队列

线性表、栈（后进先出，例如行李箱行李）、和队列（头部删除，尾部插入，例如银行排队）中的元素具有相同的逻辑结构（即线性结构），但有不同的运算集，它们是不同的数据结构。

时间复杂度

算法运行时需要的总步数，通常是算法输入规模的函数。

如何确定算法的计算量：合理地选择一种或几种操作作为“标准操作”，无特殊说明，默认以赋值语句作为标准操作。确定每个算法共执行多少次标准操作，并将此次数规定为该算法的计算量。

• 以算法在所有输入下的计算量的最大值作为算法的计算量，称为算法的最坏情况时间复杂度。
• 以算法在所有输入下的计算量的加权平均值作为算法的计算量，称为算法的平均情况时间复杂度。
• 最坏情况时间复杂度和平均情况时间复杂度通称为时间复杂度。

常见的时间复杂度阶数：按数量级递增排序

• 常数阶 O(1）：即算法的时间复杂度与输入规模 n无关。
• 对数阶 O (log2n)
• 线性阶 O (n)
• 多项式阶 O (nC)：常见的多项式阶有 O（n2)和 O（n3)。
• 指数阶 O (Cn)，C为大于 1 的正整数。常见的指数阶有 O(2n)。通常认为，时间复杂度具有指数阶的算法是实际不可计算的，而阶数低于平方阶的算法是高效率的。 ?

空间复杂度

算法执行时所临时占用的存储空间大小的亮度，通常是问题规模 n 的函数。 包含以下部分

• 程序代码所占用的空间
• 输入数据所占用的空间
• 辅助变量所占用的空间，估算算法空间复杂度时一般只分析辅助变量所占用的空间。