数据结构、算法和STL简介 【复习笔记】
1. 数据结构
1.1 数据结构的定义和背景
定义： 数据结构是一种数据组织、管理和存储的格式。它是相互间存在一种或多种特定关系的数据元素的集合
背景： 随着计算机的发展，需要处理的数据越来越大、越来越复杂，这需要我们研究数据的特性，提高计算机处理数据的效率
数据结构即研究如何组织数据、如何管理数据和如何将数据存储在计算机里
1.2 数据结构三要素
1.2.1 逻辑结构
数据中各种元素间逻辑关系
常见逻辑结构：
1.集合：所以数据在一个集合中，无其他的联系（随机，无规律）
2.线性结构：一对一的关系（像一条线一样）
3.树形结构：一对多关系（如大树的主干和分支）
4.图结构：多对多关系
1.2.2 存储结构（物理结构）
数据在计算机中的存储方式
主要的存储结构：
1. 顺序存储：逻辑上相邻的元素在物理上也存储在相邻单元（数组）
2. 链式结构：通过指针存储上一个或下一个元素的地址，像一条链子一样（链表）
1.2.3 数据运算
数据结构的实现和基于数据结构的各种操作
分别对应：创建+增删查改+其他
2. 算法
2.1 算法的定义
算法是为解决一个特定问题而设计的一系列精确的、可执行的步骤和规则的集合，它可以用某种程序设计语言来描述和实现，并且在有限的时间和空间内完成任务（算法可以没有输入，但一定有输出）
可以简单看作：初始数据 -> 算法 -> 目标数据
2.2 算法好坏的衡量
这取决于算法中语句的执行次数和需求资源个数
如果根据算法执行中对需求资源个数（即对空间的消耗）判断，这就是空间复杂度
如果根据算法执行中对执行次数（即需要的时间）判断，这就是时间复杂度
2.2.1 时间复杂度
时间复杂度是一个函数式T（N）
void fun1(int N)
{
int count1 = 0;
int count2 = 1000;
int count3 = 0;
for (int a = 0; a < N; a++)
{
count1++; //执行 n 次
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
count1++; //执行n^2次
}
}
while (count2--)
{
count3++; //执行1000次
}
}
//T(N)=N^2+n+1000注：关于log N \ log2 N \ lg N，当 N 接近无穷大时，底数大小对结果无影响，可以将底数2省略不写
2.2.2 大O表示法
上面案例，随着N增大，对结果影响最大的是N^2,其余项可以忽略不计
大O表示法中，一般把T(N)中对结果影响不大的项忽略，即上面案例看作O(N^2)
大O表示法规定：1. 时间复杂度T(N),只保留最高项，去掉最低项
2. 如果最高项不是1，去除这个项目的常数系数
3. T(N)中只有常数项，用1取代所以常数
2.2.3 递归算法的时间复杂度
单次递归时间 * 总的递归次数（这只是简单的估算方式）
严谨的计算方式要利用主定理求得
2.2.4 空间复杂度
const int N = 15;
int arr[N]; //需要大小和问题规模一样大的数组，空间复杂度为O(N)
int main()
{
int n = 0;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
}递归算法的空间复杂度同理：单次递归空间复杂度*总的递归次数
2.2.5 常见的时间复杂度
O(1) < O(log N) < O (N) < O(Nlog N) < O (N^2) <O (N^3) < O(2^N) < O( N!)
2.2.6 时间限制和空间限制
1. c++设定1到2秒的时间限制，控制执行次数在 10^7 到 10^8 之间
2. 空间限制在128MB 或 256MB，可以开一个3*10^7大小的 int 类型数组，或 5000*5000大小的二维数组
3. STL
3.1 STL的定义
STL即标准模板库，是c++标准库的一部分，含有一些模板化的数据结构和算法