目录

数据结构绪论

基本概念

三要素

算法

基本概念

  • 数据

  • 数据元素、数据结构

  • 数据类型、抽象数据类型（ADT）

 

三要素

1.逻辑结构

基本：

  1. 集合结构
  2. 线性结构
  3. 树形结构
  4. 图状结构（网状结构）

分类：

  1. 线性结构
  2. 非线性结构

2.数据的运算

定义：针对数据的逻辑结构

实现：针对数据的存储结构

3.物理结构（存储结构）

顺序存储

非顺序存储

 

算法

  • 基础

产生

程序=数据结构+算法

特性

  1. 有限性
  2. 确定性
  3. 可行性
  4. 输入
  5. 输出

“好”算法特质：

正确、可读、健壮、高效（时间复杂度低）低耗（空间复杂度低）

 

  • 性能

时间复杂度T(n)

如何计算？

  1. 忽略顺序执行的代码 ，因为其只影响常常数
  2. 只挑选一个循环中的基本操作
  3. 若存在多层嵌套，只关注最深层循环的次数

常用技巧：

从优至劣 常对幂指阶

三种复杂度：

最好、最坏、平均（所有输入的数据等概率）

空间复杂度S(n)

何如计算？

递归调用的次数