数据结构第一\二\三章——基础准备
#日拱一卒，功不唐捐；下定决心了要补一下这门核心课程，不学的话软件这条路实在走不远#
源自抖音博主“英雄哪里出来”，涉及侵权请私信告知。
1-3 数据结构学习大纲
刷题模式主要有两种，ACM模式与核心代码模式；ACM模式需要填入的代码是可以直接在编译器内运行的（需要包含主函数），核心代码模式则类似于力扣，提供代码解决方案。
2-1 数据结构概览
数据结构是指数据的组织和存储方式，它决定了数据的存储结构和逻辑结构。良好的数据结构设计可以提高数据的存储效率、查询效率和修改效率；降低程序的复杂度和错误率。
简单来说，数据结构是盛放数据的容器，对容器内的数据进行CRUD的过程，被我们称之为算法。
逻辑结构
逻辑结构，指的是数据在计算机中的逻辑关系，包括：
集合结构，数据元素之间没有固定的顺序；
线性结构，数据元素之间存在1对1的线性关系；
树状结构，数据元素之间存在1对多的层次关系；
图形结构，数据元素之间存在多对多的任意关系。
存储结构
存储结构，或曰物理结构，指的是数据再计算机中存储形式，包括：
顺序存储：数据元素按照一定的顺序存储在连续的内存空间之中；
链式存储：把数据元素存储在任意的内存之中不考虑连续与否，然后通过链接的关系把两个元素连接在一起。
2-2 时间复杂度
穷举法
单层循环
将所有情况进行遍历，举例：给定n（n<1000）个整数元素，求其中奇数有多少？
想要求取这个数组内奇数的个数，可以利用循环判断每个元素除上2的余数是0还是1，并且对其中符合条件的元素个数进行计数。又因为整数在内存中是以二进制形式存储的，即每个整数都可以表示为一系列0和1的组合。在二进制表示中，一个整数如果是奇数，那么它的最低位（也称为最右边的位，即第0位，从0开始计数）一定是1；如果是偶数，那么它的最低位一定是0。所以也可以通过和1按位与的方式判断一个数是否为奇数。
代码示例：
#include <iostream>
using namespace std;
static int arr[] = {1,17,89,2,6,7};
int OddCounter(int n, int a[])
{
int cnt = 0;
for (int i = 0; i <n;i++) {
if (a[i] & 1)
cnt++;
}
return cnt;
}
int main()
{
int counter=OddCounter(sizeof(arr) / sizeof(arr[0]),arr);
printf("Odd Number=%d\n",counter);
return 0;
}这个算法的时间复杂度为O(n)，时间复杂度与for循环中的n相关，n越大时间复杂度越高。
双层循环
给定n(n<=1000)个元素ai，求有多少个二元组(i,j)，满足ai+aj是奇数(i<j)。
代码示例：
int OddCounter(int n, int a[])
{
int cnt = 0;
for (int i = 0; i <n;i++) {
for (int j = i + 1; j < n; j++) {
if ((a[i]+a[j]) & 1)
cnt++;
}
}
return cnt;
}
这个算法的时间复杂度就与n^2相关，由此得出一般结论遍历次数随这n的增加，呈现立方式的增长，例如三层循环时，时间复杂度就与n^3相关。
概念介绍
时间复杂度的表示方法
在进行算法分析时，语句的总执行次数T(n)是关于问题规模n的函数，进而分析T(n)随着n的变化情况而确定T(n)的数量级。
算法的时间复杂度就是算法的时间度量，记作：T(n)=O(f(n))用大写的O来体现算法时间复杂度的记法，我们称之为大O记法。
时间函数
执行时间这个概念并不是用计时单位ms、s来衡量的时间，它仅代表一个执行次数的概念。我们用f(n)来表示这个时间函数。
举例如下：
单层循环的时间函数f(n)=n，线性时间函数；
双层循环的时间函数f(n)=n(n-1)/2,平方时间函数；
三层循环的时间函数f(n)=n(n-1)(n-2)，立方时间函数。
时间复杂度的O(n)的记法
由T(n)=O(f(n))可知：
当f(n)=n时，时间复杂度为O(n)；
当f(n)=n(n-1)/2时，时间复杂度为O(n^2)；
当f(n)=n(n-1)(n-2)时，时间复杂度为O(n^3)。
一般规律就是借鉴了数学上高阶无穷小的概念。
常见的时间复杂度由常数阶O(1)、对数阶O(logn)、根号阶O(根号n)、线性阶O(n)、线性对数阶、多项式阶、指数阶、阶乘阶。
2-3 空间复杂度
概念介绍
算法在执行过程中需要的额外存储空间叫做空间复杂度，这包括算法在运行时的变量、数组、链表等数据结构所占用的内存空间。算法设计的过程中我们通常希望尽可能降低空间复杂度，提高算法的效率。
常见数据结构的空间复杂度
数组（Array）：
空间复杂度：O(n)，其中n是数组中元素的数量。数组在内存中占用连续的空间，其大小在声明时确定，或动态分配时指定。
链表（Linked List）：
空间复杂度：O(n)，其中n是链表中节点的数量。链表中的每个节点都包含数据部分和指向下一个节点的指针（或引用）。尽管链表在物理上不是连续的，但从逻辑上看，它仍然需要为每个节点分配空间。
栈（Stack）：
空间复杂度：O(n)，其中n是栈中元素的数量。栈是一种后进先出（LIFO）的数据结构，其空间复杂度取决于栈中存储的元素数量。
队列（Queue）：
空间复杂度：O(n)，其中n是队列中元素的数量。队列是一种先进先出（FIFO）的数据结构，其空间复杂度同样取决于队列中存储的元素数量。
树（Tree）：
空间复杂度：O(n)，其中n是树中节点的数量。树是一种非线性数据结构，每个节点可以有多个子节点。树的空间复杂度取决于其包含的节点数。
对于特殊类型的树，如二叉树，其空间复杂度也是O(n)，但n特指二叉树中节点的数量。
图（Graph）：
空间复杂度：O(V + E)，其中V是图中顶点的数量，E是边的数量。图由顶点和连接这些顶点的边组成。存储图时，通常需要为每个顶点分配空间，并可能需要额外的空间来存储边（如邻接表或邻接矩阵）。
哈希表（Hash Table）：
空间复杂度：O(n)，其中n是哈希表中存储的元素数量。哈希表通过哈希函数将键映射到表中的位置，以支持快速的插入、删除和查找操作。哈希表的空间复杂度取决于其存储的元素数量以及哈希表的负载因子（即已填充的槽位与总槽位之比）。
扩展空间原因
一般原因是用空间换取时间上的效率。
原文地址：https://blog.csdn.net/qq_59757948/article/details/142381930
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！