Data Structure——Introduction

1. 数据结构

• 数据：分为数值型和非数值型
• 数据元素：数据处理的最小单位
  e.g student 是一个数据，student.age 是一个数据元素
• 数据结构：逻辑结构+存储结构+基本操作

1.1 逻辑结构

指元素间关系：

• 集合关系：没什么关系
• 线性关系：一对一
• 树形关系：一对多
• 图关系：多对多

相应的基本操作：

• 创建、删除数据结构
• 元素的增删改查
• 遍历每一个元素

1.2 存储结构

• 数组：元素间关系以存储空间连续性表示
• 链表：元素间关系以指针表示

常见的存储方式：

• 顺序存储：用连续的空间存储。
  优点：可以直接通过序号访问。
  缺点：预先声明数组占用空间的大小，需要连续内存空间，对插入和删除效率低
• 链式存储：元素间关系显示存储，占用内存空间不连续
  优点：动态增加或缩短链表长度，插入删除高效，存储利用率高
  缺点：无法通过序号直接访问而要从头遍历，消耗一个指针域空间
• 除此之外还有索引存储和散列存储

2. 算法

5个特性：确定性，有穷性，可行性，有输入，有输出

基本要求：正确性，可读性，健壮性（注意边界条件和特殊值），时间效率，空间效率

2.1 时间复杂度

• 用基本语句执行次数度量运行时间
• 执行次数称为时间频度，与处理的数据规模n有关。如有分支语句，按照执行语句多的分支计算
• 时间复杂度：由频度函数的最高次项决定，不带系数
• 计算方法：找与n有关的循环语句
• 时间复杂度到达立方阶：顽性算法；常量级到平方阶：易性算法
• 求和定理：T1(n)＋T2(n)＝O(MAX(f(n)，g(n))
• 求积定理：T1(n)×T2(n)=O(f(n)×g(n))
• 不存在时间复杂度低于o(n)的数组排序算法
• 时间复杂度分为最好、最坏和平均时间复杂度。通常以最坏情况作为算法的时间复杂度

![[1-常见时间复杂度数量级.png]]
![[1-各数据结构基本操作时间复杂度.png]]

2.2 空间复杂度

• 算法程序和待处理数据在内存中的存储是无法避免的，通常更关注处理数据的过程中一些额外的辅助空间