数据结构

perror打印错误信息

线性表

结构体定义可放于.h，在对应程序引用

队列

当编译器输入不是想要的数据类型，该数据会变成脏数据，如果是循环中发生会导致持续读取到该脏数据

树

度：结点的子树个数

结点的度个数最多的就是整个树的度

深度：树的分支中元素最多的就是该树的深度

父节点：某个结点的上一级

兄弟结点：同一层级的几个结点之间互为兄弟结点

二叉树

数和二叉树的区别是结构类似的情况，树是相同的，二叉树是不同的

满二叉树每层结点个数为2的（n-1）次方，结点数为2的n次方减一个

度为0的结点总是比度为2的结点多一个

完全二叉树对比满二叉树的区别为最下面的结点少若干个（全无也可以），满二叉树也是特殊的完全二叉树

完全二叉树的深度为n时，结点数为log（

二叉树的顺序存储结构（浪费空间）

申请连续的存储空间；不是完全二叉树补成完全二叉树；按从左往右、从上到下编号；按编号存储到连续空间中，结点为虚节点（没有的）的用特殊符号标识

二叉树的链式存储结构（保存数据可用栈）

左子树地址/数据/右子树地址

遍历方式：上到下（较复杂，需要使用队列，存在左/右结点就放入队列），左到右（用的多，非递归方式为根结点和左结点先输出，右结点先放入栈中后续再取出执行，需要欧用循环），右到左

输入二叉树结构和顺序存储差不多，用前序序列，没有结点的用#代替

序列（前中后序列与根的位置有关）

前序序列：根左右

中序序列：左根右

后序序列：左右根

查找

顺序查找（比较浪费）

多次比较的基础上实现的

折半查找（适合顺序排列）

多次比较，但优于顺序查找

hash查找

容易产生冲突，重点是解决冲突

核心是在hash表中找空位放置元素

函数

直接定址法

元素加上一个常量存储

除留余数法（用的多）

对hash表长度取余存储

数字分析法（较麻烦，不太合适）

对所有元素进行分析，对取值不集中的两位做地址

平方取中法

对元素进行平方，选取中间几位做地址

折叠法

将元素分成几段，将这几段相加得地址

随机乘数法

将元素和随机的0-1之间的数相乘，获取小数部分和hash表长度相乘，得地址

基数转换法

将元素进制进行更换，选取其中部分作为地址

解决冲突的办法

开放地址法

存放函数为除留余数法

线性探测法

依次加一寻找空位

二次探测法

在冲突位左右寻空位，先加后减

链地址法

存放函数是除留余数法

该方法解决冲突的办法是对有冲突的元素放入一个链表

排序

稳定排序与非稳定排序的区别是数据相同的两个元素是否按原顺序排列

内排序与外排序的区别是数据是否在原位置排列（内排序常见）

直接插入排序

一个个比较

shell排序

基于直接插入排序

将数组变为n段排序，后续不断把n除2

快速排序

将其中一个元素拿去和最后面/最前面比较，需要交换就换，不需要交换就向后/向前移动再次比较，一次比较能获得一次基准，将数组分为两部分，再次用这个方法对两部分进行排序直到排好序