数据结构相关概念

数据

数据对象

数据元素

数据项1 数据项2

数据结构

数据结构分类

• 逻辑结构
• 物理结构（存储结构）

逻辑结构：反映数据对象中数据元素之间的相互关系

• 集合结构
• 线性结构
• 树形结构
• 图形结构

物理结构：数据的逻辑结构在计算机中的存储形式

• 顺序结构
• 链式结构

关键：数据的存储结构应正确反映数据元素之间的逻辑关系，如何存储数据元素之间的逻辑关系，是实现物理结构的重点和难点

抽象数据类型

• 一个数据对象

• 数据对象中各个数据元素之间的关系

• 对数据元素的操作

算法

算法的特性

• 有穷性
• 确定性
• 可行性
• 输入
• 输出

算法的设计与要求

• 正确性
• 可读性
• 健壮性
• 高效率
• 低存储量

算法的度量方法

• 事后统计方法
• 事前分析估算方法
  • 函数的渐近增长
  • O()推导

常见的时间复杂度所耗时间大小的排列

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)< O(n!) < O(n^n)

• 空间复杂度
• 最坏情况
• 平均情况