绪论

数据结构三要素

• 逻辑结构
• 数据的运算
• 物理结构（存储结构）

逻辑结构

• 集合结构：各个元素同属一个集合，没有其他关系
• 线性结构：一对一，顺序关系
• 树状结构：一对多
• 图状结构：多对多

数据运算

• 增
• 删
• 改
• 查

物理结构

• 顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的相邻关系来体现
• 链式存储：逻辑上相邻的元素，在物理位置上可以不相邻，借助指针来表示元素之间的关系
• 索引存储：在存储元素信息的同时，还建立附加索引表。索引表中的每项成为索引项，索引项一般是关键字，地址等
• 散列存储：根据元素关键字直接计算出该元素的存储地址，又称哈希存储

总结

• 顺序存储，物理上必须是连续的；非顺序存储，物理上可以是离散的
• 数据结构会影响存储空间分配方便程度
• 存储结构会影响对数据运算的速度
• 运算的定义是针对逻辑结构的（运算的功能），运算的实现是针对存储结构的（运算的具体步骤）

算法

什么是算法

• 程序 = 数据结构 + 算法
• 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作

算法的特征

• 有穷性：必须在有穷步之后结束，每一步都可在有穷时间内完成
• 确定性：每条指令必须有确切的含义，相同的输入只能得到相同的输出
• 可行性：描述的操作都可以通过已经实现的基本运算执行有限次来实现
• 输入：有零个或多个输入
• 输出：有一个或多个输出

好算法的特质

• 正确性：正确解决问题
• 可读性：良好的可读性
• 健壮性：非法数据输入时，不会产生莫名其妙的输出
• 高效率：时间复杂度低，空间复杂度低

时间复杂度

定义

事前预估算法时间开销T(n)与问题规模n的关系（T表示time）

规则

• 加法规则：多项相加，只保留最高阶的项，且系数为1
• 乘法规则：多项相乘，都保留
• 算法好坏：常对幂指阶
• 数量级：只考虑循环内最深层嵌套的部分

分类

• 最坏时间复杂度
• 平均时间复杂度
• 最好时间复杂度

一般只考虑最坏和平均复杂度

空间复杂度

定义

空间开销S(n)与问题规模n之间的关系

规则

• 只需关注存储空间大小与问题规模相关的变量
• 加法规则、乘法规则、算法好坏与时间复杂度一样
• 递归调用情况：空间复杂度=递归调用的深度