第一章绪论

数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。

数据元素是数据的基本单位

一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

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

数据类型 ：一个值的集合和定义在集合上的一组操作的总称

逻辑结构：数据元素之间的逻辑关系, 与存储无关, 独立于计算机（一个算法的设计）

存储结构：数据结构在计算机中的表示，又称映像 / 物理结构（一个算法的实现）

顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现

优点：随机存取, 元素占用最少存储空间

缺点：只能使用相邻的一整块存储单元, 产生较多的外部碎片
链式存储：逻辑上相邻的元素在物理位置上可以不相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系

优点: 不会出现碎片现象

缺点: 存储指针占用额外的存储空间; 只能顺序存取
索引存储：建立附加的索引表。索引表中的每项称为索引项，索引项的一般形式是（关键字，地址）

优点: 检索速度快

缺点: 占用较多存储空间; 增加和删除数据要修改索引表, 花费较多时间
散列存储：根据元素的关键字直接计算出该元素的存储地址，又称哈希（Hash）存储

优点: 检索, 增加和删除结点都很快

缺点: 若散列函数不好, 出现元素存储单元冲突, 会增加时间和空间的开销

数据的运算

运算的定义是针对逻辑结构的，指出运算的功能

运算的实现是针对存储结构的，指出运算的具体操作步骤。

易错点

算法：对特定问题求解步骤的描述，是指令的有限序列，其中每条指令表示一个或多个操作

算法的特性

好的算法

1. 正确性
2. 可读性
3. 健壮性：输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果
4. 高效率与低存储量需求 （时间复杂度低、空间复杂度低）

算法的时间复杂度

定义：事前预估算法时间开销 T (n) 与问题规模 n 的关系

衡量算法随着问题规模增大, 算法执行时间增长的快慢

同一个算法, 实现的语言的级别越高级, 执行效率越低

O(1) < O(log2n) < O(n) < O(nlog2n) < O(n2 ) < O(n3 ) < O(2n) < O(n!) < O(nn)  常对幂指阶

算法的空间复杂度

衡量算法随着问题规模增大, 算法所需空间增长的快慢

HL🌱数字花园