前言：
本专栏属于数据结构相关内容，附带一些代码加深对一些内容的理解，为方便读者观看，本专栏内的所有文章会同时附带C语言和Python对应的代码，辅助不同主修语言的读者去更好的理解对应的内容，若是代码0基础的读者，可先去博主其他专栏学习一下基础的语法及知识点：
魔法天才的跳转链接：
C语言：C基础_Gu_shiwww的博客-CSDN博客
Python语言：python1_Gu_shiwww的博客-CSDN博客
数据结构是计算机中组织和存储数据的方式，它定义了数据的逻辑结构、存储结构以及操作（算法）。简单来说，数据结构就是“数据 + 数据之间的关系 + 操作方法”。
1 数据结构相关概念：
1.1 基本概念
数据不仅仅包括整型、实型等数值类型，还包括字符及声音、图像、视频等非数值类型。
（2）数据元素：数据元素是组成数据且有一定意义的基本单位，在计算机中通常作为整体处理。又被称为节点。
节点这个词一定要熟悉，在链表中会大量出现。
（3） 数据项：一个数据元素可以由若干个数据项组成。数据项是数据不可分割的最小单位。
前提：众所周知，Python语言虽然简便，但是Python语言的底层逻辑代码实际使用C语言进行编写，在引入中博主优先使用C语言，后续会修改为两个版本的代码
给定以下代码块（不可直接运行）：
struct student
{
float weight;
float height;
int age;
};
int main()
{
struct student t1; //stu1 // 数据元素/节点
t1.weight = 123.6; // 数据项
struct student stu_arr_23061[21]; // 数据对象
return 0;
}
1.*思考：
以下表格的数据元素、数据项以及数据对象都是什么呢？
编号 |
书名 |
作者 |
出版社 |
001 |
数据结构 |
张三 |
a |
002 |
网络编程 |
李四 |
b |
003 |
驱动开发 |
王五 |
c |
（建议先自己思考再看答案，答案不唯一）
数据元素（节点）：从第二行开始每一行就是一个元素。（节点）
数据项：对于某数据元素来说，它的编号、书名、作者以及出版社等为数据项
数据对象：该表格除去第一行结构体定义外，剩下的整体就相当于一个结构体数组
1.2 逻辑结构
数据对象中 数据元素/节点 之间的相互关系
逻辑结构通常分为以下几种：
1.2.1 集合结构
数据元素/节点： 除了同属于一个集合之外，他们之间没有其他关系
eg：同班同学
1.2.2 线性结构
数据元素/节点： 一对一的关系
eg：排队
1.2.3 树形结构（层次结构）
数据元素/节点： 之间存在一种一对多的关系
eg：族谱（单传除外）
1.2.4 图形关系（网状结构）
eg：人际关系网
1.3 物理结构
1.3.1 顺序存储结构
把数据元素（节点）存放在地址连续的存储单元里，这样的存储成为顺序存储结构。（数组、列表）
特点：
1、内存连续
2、相对于链式存储结构每个元素占用的空间少
1.3.2 链式存储结构
特点：1、内存不连续
2、通过指针连接
//传统的数据类型：int char short float ->数据项
//自己构造的数据类型：struct linklist
//问题：环境-》温度、湿度、PM2.5、雾霾等
typedef char datatype
struct linklist
{
datatype data;
struct linklist *next;
}
struct linklist A = {996,NULL};
struct linklist B;
B.next = NULL;
B.data = 520;
A.next = &B;
1.3.3 索引存储结构
查找一个人的电话就可以先查索引表，再查相应的数据文件，加快了查询速度。
特点：
1、检索速度快。
2、多了一张索引表，故占用内存多。
3、删除数据文件时要及时更改索引表。
1.3.4 散列存储结构
通过构造相应散列函数，由散列函数的值来确定 数据元素/节点 存放的地址。
特点：
1、存的时候按照对应关系存。
2、取的时候按照对应关系取。
逻辑结构是面向问题的，物理结构是面向计算机的。其基本目标就是将数据及其逻辑关系存储到计算机的内存中。
2 算法
2.1 概念
软件 = 程序 + 文档
程序 = 数据结构 + 算法
软件 = 数据结构 + 算法 + 文档
算法 = 对结点集合的运算和操作 + 控制结构
算法用来描述对特定问题的求解步骤，它是指令的有限序列，其中每一条指令代表一个或多个操作。
2.2 特征
算法五大特征：
1.有穷性：一个算法必须总是(对任何合法的输入值)在执行有穷步以后结束，且每一步都可以在有穷的时间内完成。
2.确切性：算法中每一个指令都必须有确切的含义，读者和计算机在理解时不会产生二义性。真 、假
3.可行性：一个算法是能行的，即算法中描述的操作都是可以通过执行有效次基本运算来实现。
4.输入性：一个算法有零个输入或多个输入，以刻画运算对象的初始情况。
所谓零个输入就是指算法本身给出了初始条件，例如在函数内部定义int a = 5;
5.输出性：一个算法必须有一个输出或多个输出，以反映出对输入数据加工后的结果，没有输出的算法是毫无意义的。
2.3 描述
最简单的描述算法的方法是使用自然语言，用自然语言来描述算法的优点是简单且 便于人们对算法的理解和阅读，缺点是不够严谨，易产生歧义。当算法比较复杂且 包含很多转移分支时，用自然语言描述就不是那么直观清晰了。
2.算法框图法
使用程序流程图、盒图等算法描述工具来描述算法。其特点是简洁明了、便于理解 和交流。
3.伪代码语言描述法
用上述两种方法描述的算法并不能够直接在计算机上执行。为了解决理解与执行之 间的矛盾，人们常常使用一种称为伪代码语言的描述方法来对算法进行描述。伪代 码语言介于高级程序设计语言和自然语言之间，它忽略高级程序设计语言中一些严 格的语法规则与描述细节，因此它比程序设计语言更容易描述和被人理解，而比自 然语言或算法框图更接近程序设计语言。
4.高级程序设计语言描述法
使用特定的可以直接在计算机上执行的程序描述算法。优点是不用转换直接可以编 译执行，缺点是需要对特定的程序设计语言比较理解。大部分的算法最终是需要通 过能够向计算机发送一系列命令的程序来实现的。
程序与算法不同。
程序可以不满足算法的有穷性，例如，操作系统，它是在无限循环中执行的程序， 因而不是算法。然而可以把操作系统的各种任务看作一些单独的问题，每一个问题 由操作系统中的一个子程序通过特定的算法实现，该子程序得到输出结果后便终止。
2.4 标准
衡量一个算法的好坏的四个标准：正确性、可读性、健壮性、高效率和低存储量的特征。
1. 正确性
算法至少应该具有输出、输出和加工处理无歧义性、能正确反映问题的需求、能够 得到问题的正确答案。
2.可读性
便于阅读、理解和交流。
3.健壮性
当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果。
4.时间效率高与低存储量需求
时间效率指算法的执行时间，存储量主要指算法程序运行时所占用的内存或外部硬 盘空间。设计算法应该尽量班组时间效率高和存储量低的要求。
2.5 时间复杂度
前言
对于一个算法的复杂性分析主要是对算法效率的分析，包括衡量其运行速度的时间效率，以及其运行时所需要占用的空间大小。对于算法的时间效率的计算，通常是抛开与计算机硬件、软件有关的因素，仅考虑实现该算法的高级语言程序。算法的时间复杂度是一个函数，它定性描述该算法的运行时间，时间复杂度常用 O 表述，它衡量着一个程序的好坏，时间复杂度的估算是算法题的重中之重。
2.5.1 概念
通常时间复杂度用一个问题规模函数来表达： T(n) = O(f(n)T(n) 问题规模的时间函数
n 代表的是问题的规模 输入数据量的大小
O 时间数量级
f(n) 算法中可执行语句重复执行的次数
2.5.2 计算
1. 给定N个元素的数组a[N]，求其中奇数多少个。
# 判断一个数是偶数还是奇数，只需要判断它除上2的余数是0还是1，
# 把所有数都判断一遍，并且对符合条件的情况进行计数，
# 最后返回这个计数就是答案，需要遍历所有的数，因此代码为：
for (i = 0; i < N ; i++)
if (a[i] % 2)
num++;
for i in range(N): # 使用range函数生成从0到N-1的序列进行迭代
if a[i] % 2: # 判断a[i]是否为奇数（奇数除以2的余数为1）
num += 1 # 奇数计数加一由代码段知，该函数中只有一层
for循环，而该循环执行了n次，因此时间复杂度为T(n) =O(n)。
2. 求下面函数的时间复杂度。
void func()
{
int num = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
num++; // 两层循环，每次循环n次，因此为n*n
for (int k = 0; k < N; k++)
++num; // 一层循环，循环n次
for (int l = 0; l < 10; l++)
++num; // 一层循环，循环10次
}
def func(N):
num = 0
# 两层嵌套循环，每次外层循环N次，内层循环也N次，因此总共执行N*N次
for i in range(N):
for j in range(N):
num += 1
# 一层循环，循环N次
for k in range(N):
num += 1
# 一层循环，循环10次
for l in range(10):
num += 1由注释，可列出计算时间的复杂度的表达式：N*N+N+10但是我们能写成O(N*N+N+10)吗？
我们知道，对于时间复杂度我们不需算出精确的数字，只需要算出这个算法属于什么量级即可，我们又如何知道它属于哪个量级呢？即我们将字母取无穷大，例如本题中字母为N，N取无穷大，而10对于N取无穷大后没有影响，因此10可以舍去，原表达式化为N*N+N+10但是我们能写成O(N*N+N+10)吗？
我们知道，对于时间复杂度我们不需算出精确的，再转化为N×(N+1)，由于N为无穷大，因此+1也是没有影响的，原式就变成了O(N*N)即O(N2)。这就是大 O 渐近表示法，只是一种量级的估算，而不是准确的值。
由此可得计算时间复杂度的一般规律(大O表示法)N*N+N+10
- 如果有常数项将其置为
1。N*N+N+1 - 去除表达式中所有加法常数。
N*N+N - 修改的表达式中 只保留最高阶项，因为只有它才会对最终结果产生影响。
N*N - 如果最高阶项系数存在且不是
1，则将其系数变为1，得到最后的表达式。N*N
3. 计算冒泡排序的时间复杂度
for (i = 0; i < N-1; i++)
for (j = 0; j < N-1-i; j++)
if(a[j] > a[j+1])
{
a[j] ^= a[j+1];
a[j+1] ^= a[j];
a[j] ^= a[j+1];
}
for i in range(N - 1):
for j in range(N - 1 - i):
if a[j] > a[j + 1]:
# 使用异或运算符交换 a[j] 和 a[j+1]
a[j] ^= a[j + 1]
a[j + 1] ^= a[j]
a[j] ^= a[j + 1]例如在这个冒泡排序中,我们需要将无序数组转化为有序数组的一种算法，它并不像上题一样是简单的双层嵌套循环，很容易想到它的循环次数是一个等差数列,第一次循环
N-1次,第二次N-2次.....一直到1。因此为
N-1 + N-2 + N-3 + ... + 1 = (N-1)*N/2由上面所说的规律时间复杂度为O(N²)。
通过上面的例子我们看出，大 O 渐近表示法去掉了对结果影响不大的项，简洁明了地表示出了时间复杂度。在实际情况中一般只关注算法的最坏运行情况。
例如在上述冒泡排序中如果给定的数组就已经是有序的了，那么就是它的最好情况，时间复杂度为O(N)。
但是如果有非常多的数据很显然我们看不出它到底是否为最好情况，所以我们必须用最坏的期望来计算所以它是O(N*N)。
4. 函数内循环为常数次
int fun(int n)
{
int i = 0, num = 0;
for(; i<100; i++)
num++;
return num;
}
def fun(n):
num = 0
for i in range(100):
num += 1
return num此时时间复杂度为
O(1)，这里的1不是指一次,而是常数次，该循环执行了100次，不管n多大，他都执行100次，所以是O(1)。
