前言：
本节我们将进入新的领域，那就是数据结构，数据结构在编程领域内有着举头轻重的作用。
作者将会以通俗易懂的方式给大家详细讲解数据结构。
所以咱们废话不多说，即将开始数据结构的学习。
1.数据结构前言
2.算法效率
3.复杂度
3.1时间复杂度
3.2空间复杂度
4.习题演练
1.数据结构前言：
1.1数据结构是什么
首先，在学习之前，我们得搞懂数据结构是什么？
数据结构是计算机存储，组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。
数据结构的形式有：线性表，树，图，哈希等。
1.2算法和算法与数据结构的重要性：
1.在我们刷题的过程我们会遇到各式各样的算法题，所以简单来说算法就是进行一系列的计算步骤，用来将输入步骤转换成输出结果。
2.数据结构其实和算法是不分家的，学好算法的前提下必须得掌握好数据结构。在今后我们参加竞赛或者实习面试时，我们都要去用到算法和数据结构去求解题目，所以学好二者对我们未来编程的道路上有很大的作用。
1.3怎么学习算法和数据结构：
主播总结的方法有两种：
第一种就是：死磕代码 ！当我们碰到一个完全没有思路的题目，我们先可以学着答案把代码的思路给写出来，然后再几小时后再独自写出代码，然后给自己规定日子按时练习代码，以达到随手就能写出代码，并理解代码的思路。（就像我们学习C语言时，对循环语句的书写，当时写什么都不顺畅，但后面联系多了，像那些循环语句和其他语句也是信手捏来的事情。）
第二种就是：进行画图。我们常常如果只用脑子去想的话，往往会忽略掉很多细节步骤，这样总是导致我们的结果与真正的答案存在偏差，所以我们要积极的进行画图。
2.算法效率：
在我们解决一到算法题时，我们往往可以有多种方法进行求解，但这些方法求解时也分好坏。
但怎么评价一个算法的好坏。
提供一道例题：旋转数组https://leetcode.cn/problems/rotate-array/description/
void rotate(int* nums, int numsSize, int k)
{
while(k--) 数组执行k次的结果
{
int end = nums[numsSize-1]; 数组所有元素向右执行一次的结果
for(int i = numsSize - 1;i > 0 ;i--)
{
nums[i] = nums[i-1]; 进行赋值，达到向右移动的效果。
}
nums[0] = end;
}
}
如上面代码块是解决本道题的常见思路，我们大致一看没有什么问题，但却在运行过程中运行不了，这是为什么。
说明这段代码写的不是很好。所以接下来给大家引用一个新概念， 那就是复杂度。
3.复杂度：
承接上面我们讲到的算法效率，我们评价一道算法题是否好坏时，我们可以从时间和空间两个维度来评价，也就是从时间复杂度和空间复杂度来评价。
时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。
复杂度在我们求解算法题时，也是很重要的，因为在我们参加竞赛或者面试过程中，面试官面对同一个题目时，如果都正确的话，他就会从复杂度的角度下来评价改题，当然面试官肯定会更青睐更优解的算法题。
通常，复杂度越高，代码运行的时长会越长，而复杂度越低时，代码运行的时长会越短。所以我们在求解算法题的过程中时，我们哟啊尽量写出复杂度越低的代码，提高我们的代码运行效率。
3.1时间复杂度：
我们其实可以把时间复杂度看成一个函数T（N），函数T（N）计算了程序的执行次数。
例题展示：
void Func1(int N)
{
int count = 0;
for (int i = 0; i < N ; ++ i)
{
for (int j = 0; j < N ; ++ j)
{
++count;
}
}
for (int k = 0; k < 2 * N ; ++ k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
由如图可得该方程式为：F（N）= N^2 + 2N +10 那它的复杂度是多少呢？接下来给他介绍大O的渐进表示法。
大O的渐进表示法：
1.在时间复杂度函数T(N)过程中，只保留最高阶项，去掉最低阶项，因为随着N的增大，只有最高阶的项影响最大，其他项可以忽略不计。
2.如果最高阶项存在且不是1，则可以去掉这个项目的常数系数，因为随着N的增大，系数对结果的影响越来越小，当N增大到无穷大的时候，前面的系数可以忽略不计，
3.T(N)中如果没有N相关的项目，只有常数项，用常数1取代所有加法常数。
如上行代码我们经过图解得出函数方程式为：T(N) = N^2 + 2N + 10 ;
由大O渐进表示法可得出：时间复杂度为： 0（N^2）;
下面给出几道例题，来帮助大家更好的理解时间复杂度：
例题1：
void Func3(int N, int M)
{
int count = 0;
for (int k = 0; k < M; ++ k)
{
++count;
}
for (int k = 0; k < N ; ++
k)
{
++count;
}
printf("%d\n", count);
}
由图解可得它的时间复杂度可以写为O(M+N)
但如果我们进一步推理的话：
如果M == N 我们可以写为O(N)或者O（M）
M >> N, O(M)
M<< N , O(N)
例2：
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++ k)
{
++count;
}
printf("%d\n", count);
}
由题易得 k执行了100次，我们可以将时间复杂度写成T(N) = 100;
由我们大O表示法的第三点可得，当式子中没有出现N项，只有常数项，那我们可以把它写成O(1)；
例题3：
const char * strchr ( const char * str, int character)
{
const char* p_begin = s; //我们要查找的字符串
while (*p_begin != character)
{
if (*p_begin == '\0')
return NULL;
p_begin++;
}
return p_begin;
}
如上图所示，我们随意的给出一些字符串，
假设我们要找的是第一个数字，这时我们执行次数为1，时间复杂度为O（1）；
如果要找的数字属于最后一个，这属于最坏的情况，这时执行次数为N，所以时间复杂度为O（N）;
所以综合下来时间复杂度的平均情况为：最好情况+最坏情况/2 得出的结果还是O（N）；
总结：
最坏情况：任意输入规模的最⼤运行次数(上界)
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数(下界)
⼤O的渐进表示法在实际中⼀般情况关注的是算法的上界，也就是最坏运行情况。
例题4：
冒泡排序计算时间复杂度
//
计算
BubbleSort
的时间复杂度？
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i-1] > a[i])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
由上行代码我们可以分成两层循环也就是外层循环和内存循环。
当我们第一次进入外层循环过程，则内存循环会进行n-1次机会，直到达到外层循环条件，进行第二层循环，所以由此方法可得，得出到n-1次时，T(N)函数呈现出了等差数列的函数形式。
有函数形式展开，在由大O方法得出时间复杂度为T(N)=O(N^2);
例题5：
对数形式
void func5(int n)
{
int cnt = 1;
while (cnt < n)
{
cnt *= 2;
}
}
由上行代码我们可以设几个数据找出规律：
因为cnt是偶数倍乘积，所以我们去n为2的偶数倍。
所以我们得出时间复杂度的结果为：O(logn)；
例题6；
递归形式：
long long Fac(size_t N)
{
if(0 == N)
return 1;
return Fac(N-1)*N;
}
如以上图解所示：
递归算法的时间复杂度 = 递归次数 * 单次递归的时间复杂度
单次递归的时间复杂度通常为1.
所以递归所使用的时间复杂度为：O（N）;
3,2空间复杂度：
由上文讲到空间复杂度主要表示算法运行所需要额外临时开辟的空间。
计算空间复杂度的方法：大O渐进表示法。
注意：函数运行时所需要的栈空间在编译期间已经确定好了（存储变量，局部变量等），所以空间复杂度主要通过函数在运行时候显示申请的额外空间来确定。
下面来举出两道实际例子，带大家什么了解求解空间复杂度。
例1：
//
计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i-1] > a[i])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
由上行代码可得，函数栈帧在编译期间创造好了，我们关注创造的额外变量就行。
上行代码中exchange等变量使用了额外的空间，根据我们大O渐进表示法可得
该函数的空间复杂度为：O(1);
例2：
long long Fac(size_t N)
{
if(N == 0)
return 1;
return Fac(N-1)*N;
}
我们这里又一次使用了递归，求法其实与求解时间复杂度大致相同。
递归的空间复杂度 = 递归次数 ＊单词递归的空间复杂度
在额外创建控件过程中，申请了N次空间，所以空间复杂度为O（N）。
4.习题演练：
旋转数组：https://leetcode.cn/problems/rotate-array/description/
我们在算法效率讲到了该习题，并写出了该题的常规思路，但我们在运行过程中出现了错误，这是为什么呢？
我们从代码的空间和时间复杂度来分析，因为下行代码使用了while循环和for循环执行了N的平方次，申请了额外的空间数为end 变量等，所以空间复杂度为O(1);
下行代码的时间复杂度：O(N^2),空间复杂度为：O(1)
void rotate(int* nums, int numsSize, int k)
{
while(k--) 数组执行k次的结果
{
int end = nums[numsSize-1]; 数组所有元素向右执行一次的结果
for(int i = numsSize - 1;i > 0 ;i--)
{
nums[i] = nums[i-1]; 进行赋值，达到向右移动的效果。
}
nums[0] = end;
}
}
接下来我们就从时间复杂度与空间复杂度的两点上对代码进行修改：
void rotate(int* nums, int numsSize, int k)
{
int newArr[numsSize]; //创建一个新数组
for (int i = 0; i < numsSize; ++i)
{
newArr[(i + k) % numsSize] = nums[i]; //取余数很关键，解决掉了很多问题。
}
for (int i = 0; i < numsSize; ++i)
{
nums[i] = newArr[i]; // 进行了赋值，
}
注意：1.我们分别使用了两个for循环，使得空间复杂度变为(F(N)=2N)–>O(N),
2.但是我们临时创建了一个新的数组，数组开辟了numsSize的空间，这使得我们的空间复杂度为O(N)，这里我们进行了空间换时间，在如今计算器的发展过程中，计算器的内存越来越大，所以人们对计算器占用的空间不需要担心太多。
那我们还有别的办法能让时间和空间同时得到最大利用，效率最高呢？
请看下行代码：
void reverse(int* nums,int left,int right)
{
while (left < right)
{
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
left ++ ;
right--;
}
}
void rotate(int* nums, int numsSize, int k)
{
k = k % numsSize; //转至k次次数对数组长度取余数，有利于
reverse(nums, 0, numsSize - 1 - k); // k位置的逆置
reverse(nums, numsSize - k, numsSize - 1); // n-k位置的逆置
reverse(nums, 0, numsSize - 1);
}
注意：1.这行代码的时间复杂度为O(N)，空间复杂度为O(1)，时间与空间复杂度相较于上面两段代码复杂度更低，有利于提高代码的运行效率。
2.本行代码使用了三次逆置的方法，并对次数进行了取余数操作，这样对既不会占用过多的内存，又能快速转换数组中的数。
如图所示：
总结：本节讲解了数据结构的一些基本概念，大家在平时也可以联系一些数据结构类型的题目，如果本节对大家有用的话，可以给作者点上赞和关注❤❤。