备考蓝桥杯：数据结构概念浅谈
备考蓝桥杯：数据结构概念浅谈
数据结构是计算机科学中的重要基础课程，它研究数据的组织方式以及数据之间的关系。本文将从数据结构的基本概念出发，介绍其三个主要组成要素：逻辑结构、存储结构和数据运算，并进一步探讨算法的时间复杂度和空间复杂度的度量方法，最后简要介绍C++标准模板库（STL）的相关知识。
1. 数据结构的概念
什么是数据结构
数据：指的所有能输入计算机并被程序处理的符号的介质总称
结构：组成整体的各部分的搭配和安排
大白话：数据结构就是把数据搭配在一起，也就是数据的组织形式，当一堆数据输入到计算机中时，要用哪种方式存储起来
为什么要有数据结构
在我们早期的计算机ENICA中，计算机主要是处理单纯的数值数据，来计算战争中弹道轨迹用的
随着技术不断发展，计算机要处理的数据类型也越来越多，数据量也越来越大，数据结构应运而生
2. 数据结构的三个组成要素
1. 逻辑结构
（为如何在计算机中存储做铺垫）
- 集合：所有数据只是放在一起，并没有什么联系
- 线性结构：数据之间是一对一的关系
- 树形结构：一对多的关系，比如我们的文件系统
- 图形结构：多对多的关系
2. 存储结构
- 顺序存储：把逻辑上相邻的元素同时也存储在物理内存上也相邻的空间中，比如说我们的数组就是这种形式
- 链式存储：用指针来存储前一个或者下一个元素的地址，我们竞赛中一般用不到指针
3. 数据运算
包括数据结构的创建，增删查改，输出排序等操作
举一个实际的例子 我们要做一个学生管理系统，我们面临的是一群学生的信息，学生之间按学号排序
逻辑结构：线性结构
存储结构：我们选择顺序存储
针对学生信息这个数据结构，
我们有下面的操作
- 创建学生管理系统
- 添加一个学生
- 删除一个学生
- 修改一个学生的信息
- 查询一个学生的信息
3. 算法好坏的度量（时间复杂度和空间复杂度）
算法有事前分析法（计算时间复杂度），事后分析法（计时器）
我们写的所有程序都是算法
算法可以没有输入但是必须要有输出，没有输出的算法是没有什么意义的
我们评判算法好坏的标准就是时间和空间的消耗量
时间复杂度计算
大O表达式，我们只保留时间开销最大的项，我们不要系数
如果没有常数项就写成1
- O（N）= N的三次方
- O（N）=1
- O（N）=N
- O（N）=logN
最优和平均和最差时间复杂度
这个find函数，最好的情况就是第一个元素就是待查找的元素，时间复杂度是O（1）
最差的情况就是全部遍历完才找到待查找的元素，时间复杂度是O（n）
平均情况就是O((1+n)/2)也就是O（n）
但是我们竞赛和工程中，我们的时间复杂度一般都指的是最差的时间复杂度
计算时间复杂度例子
这个时间复杂度的表达式就是F（n）= 2n+10
也就是O（n）
这个函数表达式f（m,n）=n+m
时间复杂度是O（n+m）
我们设执行次数为x，执行一次，cnt是2，执行二次，cnt是2的2次方，执行x次，cnt是2的x次方，2的x次方=n时，x=log2n
我们的时间复杂度也就是O（logn）
这里我们递归只用简单的方法做，因为如果想具体算要涉及到一些主定理的东西，我们只是为了应付竞赛，没必要追求那么深
公式：递归次数 乘 每次递归的时间复杂度
可以看到递归了N+1次，每次时间复杂度就是1，所以时间复杂度为O（N）
空间复杂度计算
比如我们创建一个长度为N的数组，我们就是O（N）的空间复杂度
一般我们不考虑太多空间复杂度，所以不过多陈述
4. STL
STL是C++标准的一部分,什么是C++标准的呢？就是我们写代码的一系列的行为规范，我们C++标准可以追溯到98年 C++98 之后又有了C++03，14，17，20等等，标准库只能向前兼容，不能向后兼容，比如我们的范围for就是C++11以后才有的，那我们在不支持C++11的编译器就不能用范围for
每个版本的C++标准都有一个标准库，比如我们的sort，swap，min，学好C++标准库就能避免我们费时间自己去造轮子，用人家已有的方法来解决问题
一般我们的竞赛都是支持STL库的使用的