文档介绍：《数据结构总结》
姓 名： 彭亚川
一、什么是数据结构
是研究数据的存储和操作的一门学问。
数据的存储分为两个部分：
个体的存储
个体关系的存储
从某种角度来讲，数据存储最核心的关系就是个体关系的存储，个体存储可以忽略不计
二、malloc
比如随意写一个动态分配
Int* arr=（int *）malloc（sizeof（int）*len）；
sizlen（int）*len表示该函数向操作系统请求一个空间字节数是4*len个，
malloc只返回第一个的字节地址
（int*）强制转换，表示把第一个字节的地址转换成int型
Free（arr）：代表把动态分配的
20个字节的内存释放
三、指针
A aa=new A(); //aa相当于一个指针可以指向A这个类里面的所有东西
A aa2=aa; //吧aa的指针赋给aa2
(); //调用f()
指针
指针就是地址，地址就是指针I
指针变量时存放内存单元的地址变量
指针的本质是一个操作受限的非负的整数
指针的分类
基本类型的指针
int *p: //p是个指针变量。Int * 表示该p变量只能存储int类型的地址
inti=I;
p=&I; //*p就代表i
四、栈
1、分配内存的方式
2、实现数据先进后出的存储方式
3、相当于一个箱子，先放后出
一分类
静态栈：与数组相似数组
动态栈：不连续，但是通过指针相连接，相当于一个箱子，相当于链表，只是把链表的一些功能砍去
栈的用处
函数调用，中断，表达式求值，内存分配，缓冲处理，迷宫
五、队列
实现先进先出的存储结构（相当于排队买票）本质也是链表
分类：
链式队列：对链表的操作
静态队列：数组实现（通常都必须是循环队列）
循环队列：
为什么静态队列必须是循环队列?防止数组越界
循环队列需要几个参数来确定的？两个参数
循环队列的各个参数的含义？
初始化
Font和Rear的值为空
2、队列非空
Font代表队列的第一个元素
Rear代表队列的最后有一个有效元素的下一个元素
4、队列空
Font和Rear的值相等但是不一定为0
伪算法的讲解
1、为了循环队列，
入队算法：Rear=(Rear+1)%数组长度
出队算法：Font=(Font+1)%数组长度
2、如何判断循环队列是空Font和Rear的值相等就为空
3、如何判断队列已经满（少用一个元素）
Font和Rear紧挨着队列已满否者没满
Rear=(Rear+1)%数组长度==Font=(Font+1)%数组长度
队列的应用
所有和时间有关的都有队列的影子
六、递归
严蔚敏
定义
一个函数自己直接或者间接调用自己（要写一个条件，什么时候不用调用自己）
求阶乘和累加的算法
二、递归必须要满足三个条件
1、必须有一个明确的终止
2、该函数的处理的数据规模必须在递减
3、这个转化必须是可解的
三、循环和递归的关系
所有的循环都可转换成递归，但是用递归的不一定用循环能解决
递归的优缺点
易于理解。2、速度慢。3、储存空间大
循环优缺点
1、不易理解。2、速度快。3、存储空间小
递归的作用
1、树和森林以递归方式定义
2、数和图很多算法都是以递归来实现的
3、很多数据公式都是以递归的方式定义的
七、树
树的定义
1、科学定义：尤其只有一个根节点，然后有又若干个不相交的子树，这些子树本身就是一颗树
2、通俗定义：树是由节点和边组成，每个节点只有一个父节点但是可以有多个子节点
但是有一个节点例外，该节点没有父节点，此节点称为根节点
3、专业术语：
节点：指的是一个个的圈，父节点：一般父节点只有一个，就是节点的爹（和它紧挨着的），子节点、子孙、堂兄弟
深度：从根节点到最低层节点的层次数称之为深度（根节点是第一层）
叶子节点：没有子节点的节点。
非终端节点：就是非叶子节点。
度：指的是子节点的个数
树的分类
一般树：任意一个节点的子节点的个数都不受限制
二叉树：任何一个节点的子节点的个数最多两个且子节点的位置不可更改（有序的）
二叉树分类：
1、一般二叉树：
2、满二叉树：每个节点都有两个子节点，不能再多一个（在不增加树的层数的节点的情况下，无法多添加一个节点的二叉树）
3、完全二叉树：如果只是删除了满二叉树最底层最右边的连续若干个子节点，这样形成的二叉树就是完全二叉树
完全二叉树包含满二叉树
森林：n个互不相交的树的集合
树的