顺序表、链表、队列、栈、树、图
线性结构：任意一个节点至多有一个前驱节点，一个后继节点
顺序表、链表、队列、栈
非线性结构：任意一个节点可以有多个前驱或多个后继节点
树、图
存储结构：
顺序结构存储
链式结构存储
顺序表：在连续的地址中储存数据
优点：
地址连续，顺序访问快速简单
缺点：
定义时无法确定内存的大小
插入或删除数据时，会有大段的数据在进行移动
顺序表常见操作： 1.完成查找、删除、修改 2.完成顺序表是否为空 3.完成获取顺序表中元素个数的函数 4.完成顺序表清空的函数 5.完成顺序表的排序，可以选择升序或降序
链表：在内存中将每个数据分区保存在不同节点中，每个节点中利用指针来记录下一个节点所在的位置
链表类型： 有头无头 循环不循环 单链双链 有头无头：第一个节点是否存数据，头节点不存放数据 循环不循环：最后一个节点指向NULL则不循环，指向第一个节点则循环 单链双链：若节点只有一个指针记录后继节点的位置，则是单链 若节点有两个指针，分别记录前驱和后继节点的位置，则是双链
栈：先进后出
顺序结构栈：使用数组的方式完成
链式结构栈：使用链表的方式完成
队列：先进先出
树：有n个不相交节点组成的有限集合，其中每个节点最多只有一个前驱节点
可以有多个后继节点(n>=0)
术语： 父节点：节点前驱节点，没有父节点称为树的根节点 子节点：节点的后继节点，没有子节点的称为叶子节点 兄弟节点：与节点所在同一层，且拥有同一个父节点 节点的度：节点拥有的子树个数 树的度：所有节点中拥有度的最大值 树的深度：树的层数 森林：由n棵树形成的有限集(n>=0) 二叉树：每个节点最多只能拥有两个子节点 研究意义：树的结构过于复杂，而二叉树相对简单，所在实际研究过程中 会将树转为二叉树进行研究 二叉树的子节点，要分左右孩子 树转二叉树： 1.让树的根节点作为二叉树的根 2.让节点的第一个子节点作为节点的左孩子 3.让节点的第一个兄弟节点作为节点的右孩子 4.为每个节点重复2、3步骤 二叉树特征： 若二叉树有i层，则第i层最多可以有2的i-1次方个节点 深度为k的二叉树，最多可以有2的k次方-1个节点 特殊二叉树： 满二叉树：深度为k的二叉树，正好有2的k次方-1个节点 完全二叉树： 对节点进行编号，二叉树的节点正好顺序与编号对应则是完全二叉树 若二叉树为完全二叉树，深度为k的二叉树，最少有2的k-1次方个节点 最多有2的k次方-1个节点 二叉排序树： 节点若有左孩子，则左孩子中的数据一定小于该节点中的数据 节点若有右孩子，则右孩子中的数据一定大于等于该节点中的数据 树的存储： 顺序存储结构： 对二叉树中的每个节点进行编号，将对应数组下标节点存放到数组的指定位置上 二叉树的深度越大，空间的浪费也就越多 链式存储结构： 使用结构体，形成一个节点，每个节点中存储数据、左孩子指针、右孩子指针 通过指针记录其左右孩子节点的位置 二叉树的遍历： 先序遍历：根左右 中序遍历：左根右 后序遍历：左右根 二叉树节点的删除： 1.如果节点是叶子节点，则直接删除 2.如果节点有左孩子，没有右孩子，则左孩子顶替该节点位置 3.如果节点有右孩子，没有左孩子，则右孩子顶替该节点位置 4.如果节点有左和右孩子，则将左孩子放到第一个右孩子的最左边的叶子节点 哈夫曼树：最优二叉树 带权节点：权是一个数字，用来构建哈夫曼树的依据 构建哈夫曼树： 1.建造森林全是根 2.选用两小造棵树 3.删除两小填新人 4.重复2、3剩单根
图：由n个顶点和n条边形成的有限集合
分类： 有向图：边带有方向 无向图：边不带有方向 图的存储： 顺序存储（邻接矩阵）： 使用一维数组保存图中所有的顶点 使用二维数组保存图中所有的边 链式存储（邻接表）： 使用一维数组保存图中所有的顶点 每个顶点节点作为单链的头节点，使用链表将图中的边记录保存 图的遍历： 广度优先：从一个节点开始，遍历该节点及其能够直接到达的所有节点 然后再将已经遍历过得节点，作为起始节点，遍历其能够到达的所有节点 深度优先：从一个节点出发，一直走到底，再递归回来
