1. 什么是数据结构

数据结构是一门关注（非数值计算的）程 序设计问题中所出现的计算机操作对象以及 它们之间的关系和操作的学科。

2. 基本概念和术语

数据结构 ： 数据对象 + 对象中所有数据成员之间的关系 数据对象 ： 同类数据元素的集合 数据元素：数据中的一 个“个体”，是数据的基本单位 数据项：组成数据元素的有 特定意义的不可分割的最小单位

数据结构关注的三个方面

1. 逻辑结构

1. 线性结构：数据元素的有序序列。除了第一个和最后一个元素外，其余元素都有一个前趋和一个后继，1对1。

   • 线性表
   • 栈和队列
   • 字符串

2. 非线性结构

   • 层次结构——树：除了根元素外，每个节点有且仅有一个前趋，后继数目不限，1对多。
   • 网状结构——图：每个元素的前趋和后继数目都 不限，多对多。
   • 其他——集合：元素间的次序是任意的。元素 之间除了“属于同一集合”的联系外没有其他的关系。

2. 存储结构

• 顺序存储结构：数组
• 链接存储结构：链表
• 索引存储方式（间接寻址）：一个存地址的数组
• 哈希（散列）存储方式：通过构造散列函数来映射元素地址

3. 运算

• 创建
• 清除
• 插入
• 删除
• 搜索
• 更新
• 访问
• 遍历

算法的设计取决于选定的逻辑结构。

算法的最终实现依赖于采用的存储结构。

3. 抽象数据类型（自学）

4. 算法和算法分析

时间复杂性与空间复杂性

算法必须满足的五个重要特性

1. 输入：有0个或多个输入
2. 输出：有一个或多个输出
3. 确定性：每步定义都是确切的、无歧义的
4. 有穷性：算法应在执行有穷步后结束
5. 有效性：每一条运算应足够基本

时间复杂性度量： 用程序步来衡量一个程序的执行时间。 赋值语句/表达式计算：程序步为1 循环程序步 = 循环次数 * 循环内部程序步

算法的（渐近）时间复杂度：$T(n) = O(f(n))$

for(int i = 0; i < n; i++){         // n+1
    for(int j = 0; j < n; j++){     // n(n+1)
        c[i][j] = 0;                  // n^2
        for(int k = 0; k < n; k++){     // n^2(n+1)
            c[i][j] += a[i][k] * b[k][j];   // n^2(n+1)
        }
    }
}

GraphToy

$O(1) < O(\log_2{n}) < O(n) < O(n \log_2{n}) < O(n^2) < O(n^3)$

最坏、最好和平均情况

1. 大$O$表示法

给出时间复杂度的上界，即最坏情况

2. 大$\Omega$表示法

给出时间复杂度的下界，即最好情况

3. 大$\theta$表示法

给出了时间复杂度的上界和下界