数据结构－概述

一、研究四方面内容

1. 研究数据结构的逻辑结构、物理结构以及它们的相应关系
2. 定义运算规则
3. 编制算法
4. 分析算法效率（主要考虑时间特性）

二、研究的三个结构

1. 线性结构
2. 树状结构
3. 网状结构

常见的数据结构：数组、栈、队列、表、串、树、图、文件等

• 数据结构：数据元素和其相互关系。DS=（D，R）
• 算法基本特性：有穷性、确定性、可行性
• 算法质量三要素：
  • 花费的运行时间
  • 占用的存储空间
  • 其他（可读性、易调性、健壮性、可移植性等）
• 算法定量分析：
  • 语句频度（Frequency Count）：语句可能重复执行的最大次数。
  • 时间复杂度（Time Complexity）

    设算法中所有语句的语句频度为t(n),f(n)是当n趋向无穷大时与t(n)为同阶无穷大，
    则算法的时间复杂度T(n)=O(f(n))
    其中：n为算法计算量或规模
    f(n)是运算时间随n增大时的增长率
    O(f(n))是算法时间特性的量度
    时间复杂度：常数阶->O(1)；线性阶->O(n)；平方阶->O(n[^2])。