备考蓝桥杯：数据结构概念浅谈

目录

1数据结构的概念

什么是数据结构:

为什么要有数据结构

2.数据结构的三个组成要素

1.逻辑结构

2.存储结构

3.数据运算

3。算法好坏的度量（时间复杂度和空间复杂度）

时间复杂度计算

最优和平均和最差时间复杂度

计算时间复杂度例子

空间复杂度计算

4.STL

---

1数据结构的概念

什么是数据结构:

数据：指的所有能输入计算机并被程序处理的符号的介质总称

结构：组成整体的各部分的搭配和安排

.大白话：数据结构就是把数据搭配在一起，也就是数据的组织形式，当一堆数据输入到计算机中时，要用哪种方式存储起来

为什么要有数据结构

在我们早期的计算机ENICA中，计算机主要是处理单纯的数值数据，来计算战争中弹道轨迹用的

随着技术不断发展，计算机要处理的数据类型也越来越多，数据量也越来越大，数据结构应运而生

2.数据结构的三个组成要素

1.逻辑结构

（为如何在计算机中存储做铺垫）

集合 所有数据只是放在一起，并没有什么联系

线性结构，数据之间是一对一的关系

树形结构 一对多的关系，比如我们的文件系统

图形结构，多对多的关系

2.存储结构

顺序存储：把逻辑上相邻的元素同时也存储在物理内存上也相邻的空间中，比如说我们的数组就是这种形式

链式存储：用指针来存储前一个或者下一个元素的地址，我们竞赛中一般用不到指针

3.数据运算

包括数据结构的创建，增删查改，输出排序等操作

举一个实际的例子 我们要做一个学生管理系统，我们面临的是一群学生的信息，学生之间按学号排序

逻辑结构：线性结构

存储结构：我们选择顺序存储

针对学生信息这个数据结构，

我们有下面的操作

1.创建学生管理系统

2.添加一个学生

3.删除一个学生

4.修改一个学生的信息

5.查询一个学生的信息

3。算法好坏的度量（时间复杂度和空间复杂度）

算法有事前分析法（计算时间复杂度），事后分析法（计时器）

我们写的所有程序都是算法

算法可以没有输入但是必须要有输出，没有输出的算法是没有什么意义的

我们评判算法好坏的标准就是时间和空间的消耗量

时间复杂度计算

大O表达式，我们只保留时间开销最大的项，我们不要系数

如果没有常数项就写成1

1.O（N）= N的三次方 2.O（N）=1

3.O（N）=N                4.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库的使用的