数据结构

一、数据结构简介

数据结构是以某种特定的布局方式存储数据的容器,所存储的数据结构是指相互之间存在一种或多种特定关系的数据元素的集合，数据结构的布局方式决定了数据结构对于数据的操作的效率

二、数据结构的类型

集合结构 线性结构 树形结构 图形结构

集合结构： 一种数据类型的集合，单个数据之间没有关联性

顺序结构：是一个有序数据元素的集合

顺序结构必须满足的：
1.必须有个一个开头元素
2.一个结尾元素
3.除了第一个元素其他元素必有一个前驱元素
4.除了最后一个元素其他的必有一个后继元素

常用顺序结构 :队列、栈、顺序表、
队列：先进先出，类似排队，只能在队列的末尾添加元素，在队列的头部删除元素
栈：先进后出，类似网盒子里放东西，先放进的元素，最后再能取出。
线性表：线性表除了一个和最后一个数据元素之外，其它数据元素都是首尾相接的

树形结构：树形结构是嵌套结构。 一个树形结构的外层和内层有相似的结构， 所以这种结构多可以递归的表示。一颗树可以简单的表示为根， 左子树， 右子树。 左子树和右子树又有自己的子树。

二叉树.jpg

三、数据结构的存储

顺序存储结构 和 链式存储结构

顺序存储结构

可以理解成一个固定的连续位置的容器，把数据依次放入容器中。

链式存储结构

单链表 双链表 循环链表

单链表 每个节点存储的是本身的数据信息，和下一个数据的地址信息 单链表.jpg

双链表 每个节点存储了上一个节点的地址和下一个节点的地址

双链表.jpg

四、二叉树

二叉树是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：

1582471556890.jpg

二叉树中，第 i 层最多有 2i-1 个结点。
如果二叉树的深度为 K，那么此二叉树最多有 2K-1 个结点。
二叉树中，终端结点数（叶子结点数）为 n0，度为 2 的结点数为 n2，则 n0=n2+1。

二叉树的顺序存储，指的是使用顺序表（数组）存储二叉树。需要注意的是，顺序存储只适用于完全二叉树。换句话说，只有完全二叉树才可以使用顺序表存储。因此，如果我们想顺序存储普通二叉树，需要提前将普通二叉树转化为完全二叉树。

五、二叉树遍历

二叉树遍历.jpg

先序遍历，中序遍历，后续遍历

1．先序遍历
⑴ 访问根结点；⑵ 遍历左子树；⑶ 遍历右子树。A B D E G C F

2．中序遍历
⑴遍历左子树；⑵访问根结点；⑶遍历右子树。D B G E A C F

3．后序遍历
⑴遍历左子树；⑵遍历右子树；⑶访问根结点。D G E B F C A