数据结构

数据结构研究什么？

• 一组有特定关系的数据的存储与处理
• 抽象的方法

数据的逻辑结构

• 集合结构：数据元素放在一起，但是元素间没有关系
• 线性结构：数据元素的有序序列，每个元素有一个前趋和一个后继
• 树形结构：层次关系的数据，除了根元素，每个元素有且只有一个前趋，后继数目不限
• 图形结构：元素之间相互关联，每个元素可以有多个前趋和后继

数据结构的操作

• 创建：创建空的数据结构
• 清除：清空数据结构
• 插入：在指定位置插入新元素
• 删除：删除某个元素
• 搜索：搜索满足特定条件的元素
• 更新：修改某个元素的值
• 访问：访问数据结构中的某个元素
• 遍历：按照某种次序，访问每个元素有且只有一次

存储实现

• 需要储存的信息
  • 一组数据元素
  • 数据元素之间的关系
• 物理结构
  • 存储结点（存放数据元素，一个简单变量、结构体变量或对象）
  • 数据元素之间的关系的存储（逻辑结构的机内表示）
  • 附加信息（便于运算实现而设置的一些哑结点，如链表中的头节点）
• 关系的存储
  • 顺序存储（用存储的位置表示元素之间的关系，主要用数组实现）
  • 链接存储（用指针显式地指出元素之间的关系）
  • 哈希存储（用存储的位置表示元素之间的关系，主要用数组实现，主要用途是查找）
  • 索引存储（所有的存储节点存储在数据区，另外设置一个索引区域表示节点之间的关系）

运算实现

• 操作怎么实现
  • 每个运算对应一个算法
  • 每个算法用一个函数表示
  • 每个数据结构有一组函数

时间性能

• 时间性能的衡量
  • 与运行相关的因素
    • 机器性能
    • 处理的数据量
    • 数据分布
    • 编译器
• 标准操作
• 时间复杂度
  • 最好情况的时间复杂度
  • 最坏情况的时间复杂度
  • 平均情况的时间复杂度
• 大O表示法（上界）
• 两个定理
  • 求和定理
  • 求积定理

空间性能

• 空间复杂度
  • 算法处理过程中所需的额外工作量
  • 一般按最坏情况处理
  • 用大O表示法

算法优化问题提出

• 慢慢分析，逐步优化
• 最大连续子序列和问题

O(N^3)的算法

• 枚举法