数据结构基础知识

程序（Program）=数据结构（Data Structure）+算法（Algorithm）

数学基础

1. 指数

image.png
2. 对数
image.png
3. 级数
级数是指将数列的项依次用加号连接起来的函数。我们使用∑（希腊语：Sigma，汉语：西格玛）符号进行表示，如 5.png
级数理论是分析学的一个分支；它与另一个分支微积分学一起作为基础知识和工具出现在其余各分支中。二者共同以极限为基本工具，分别从离散与连续两个方面，结合起来研究分析学的对象，即变量之间的依赖关系──函数。
image.png
4. Π运算
Π（希腊语：pi，汉语：派）运算与∑符号的运算法则类似，由∑的加法变成了乘法，其代表“求乘积”，如 7.png

四大逻辑结构（Logic Structure）

1) 集合结构
集合结构（Set Structure）中所有数据元素除了同属于一个集合外，并无其他关系。

51.png
2) 线性结构
线性结构（Linear Structure）指的是数据元素之间存在“一对一的关系”
52.png
3) 树形结构
树形结构（Tree Structure）指的是数据元素之间存在“一对多”的层次关系。
53.png
4) 图形结构
图形结构（Graphic Structure，也称：网状结构）指的是数据元素之间存在“多对多的关系”（注：此时的“多对多”中的多表示，至少有一个）
54.png

复杂度

1.时间复杂度

• 定义
  时间复杂度表示一个程序运行所需要的时间
• 度量方法
  1.事先统计法：采取在计算机编译程序前对该算法进行预估的方式估算
  2.事后统计法：指在程序运行结束之后直接查看运行时间的方式进行时间复杂度的统计
  3.以下为一些常用的基本公式：
  a)O(a）=O(1) 其中a为常数
  b)O(an)=O(n) 其中a为常数
  c)O(an2++bn+c)=O(n2) 其中a,b,c均为常数，结果只与最大项n有关
  d)O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)
  在设计程序的时候一定要注意，高计算需求的地方一定不要使用太高的时间复杂度的计算方式！

2.空间复杂度
一个程序的空间复杂度是指运行完一个程序所需内存的大小，其包括两个部分。
a)固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间。
b)可变空间，这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。

内存

image.png

(地址的常用表示为十六进制表示法，即Ox+十六进制数)
由这个图可以清晰的发现对于每一段的内存中的数据，都有一个地址与之相对应，也真是因为有地址的存在，我们计算机中才可以轻易的去访问到其中数据。

• 内存的申请
  1. Malloc函数
  malloc（）函数在堆中申请分配一个大小为size个字节的连续内存空间，若成功分配，则返回一个指向所分配空间起始地址的指针，否则返回空指针（NULL）

• 内存的释放
  2.Free函数
  free（）函数用来释放已分配的内存空间，参数p是待释放的内存空间的首指针
  总结来说malloc就是用来申请内存空间，而free是为了释放内存空间，这两个函数在C/C++语言的数据结构中十分重要，也十分常用，请务必牢记，这里总结几个新手易犯的错误：
  a)忽略判断是否内存申请失败，如果内存申请失败并没有执行一些中断之类的操作，程序会继续向下运行，直到各种错误把整个程序弄崩溃
  b)使用malloc不适用free，这在做题中似乎无关紧要，但是一旦在工作中养成这样的习惯，则会制造出很多无用的内存垃圾，造成程序效率的低下，当然了，后面出现了内存回收机制可以自动帮我们free掉内存垃圾，但是依旧要养成即时释放内存的好习惯。
  c)使用指针后胡乱进行移动，产生不知名的指针位移，这样的效果往往是不知道自己的程序究竟出了什么错误，也极其难修改。

• 数据结构程序的过程
  先定义所需要的变量与指针变量---->进行内存分配---->判断是否分配成功(分配不成功就报错或者退出程序)---->对指针空间中的数据进行操作(如赋值，修改，查询，删除) ---->完成操作后释放指针

• 在C++中引入的对象思维，有一个极其类似于malloc函数的方法，就是new方法，但他们还是有一些区别的：
  1.new操作符从自由存储区（free store）上为对象动态分配内存空间，而malloc函数从堆上动态分配内存。
  2.自由存储区是C++基于new操作符的一个抽象概念，凡是通过new操作符进行内存申请，该内存即为自由存储区。而堆是操作系统中的术语，是操作系统所维护的一块特殊内存，用于程序的内存动态分配，C语言使用malloc从堆上分配内存，使用free释放已分配的对应内存。

以上知识均来自于https://www.dotcpp.com/course/ds/的整理