什么是数据结构
数据结构是存在一种或多种特定关系的数据元素的集合。
逻辑结构：是指数据对象中元素之间的相互关系。从逻辑上分有以下四种：
- 集合结构
- 线性结构
- 数形结构
- 图形结构
物理结构：是指数据结构在计算机中的存储形式：从物理上分有以下2种:
顺序存储结构
链式存储结构
什么是算法
定义：算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作
算法的特点：有穷性，确定性，可行行，输入，输出。
算法的设计要求: 正确性、可读性、输入、输出
线性表
定义：线性表是零个或多个具有相同元素的有限序列。线性表分为顺序存储结构和链式存储结构
线性表的顺序存储结构:
线性表的顺序存储结构，指的是连续的存储单元依次存储线性表的数据元素
优点:
- 无需为表中元素之间的逻辑关系而增加额外的存储空间。
- 可以快速的存取表中任一位置的元素
缺点:
- 插入和删除操作需要移动大量的元素
- 当线性表长度变化较大时，难以确定存储空间的容量
- 造成存储空间的碎片
线性表的链式存储结构:
结点:我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中的存储的信息称做指针或链。这两部分信息组成的数据元素ai的存储映像。称为结点
单链表
n个结点链接成一个链表，即为线性表的链式存储结构，因为此链表的每一个结点中只包含一个指针域，所以叫单链表。
静态链表
用数组描述的链表叫做静态链表
循环链表
将单链表中终端结点的指针由空指针指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。
双向链表
双向链表是在单链表的每一个结点中，再设置一个指向前驱结点的指针域
栈与队列
栈
栈是限定仅在表尾进行插入和删除的操作的线性表。我们把允许插入和删除的一端称为栈顶，另一端称为栈底。栈又是后进先出的线性表，简称LIFO（last in first out）
队列
队列是只允许在一端进行插入操作、而在另一端进行删除操作的线性表.队列是一种先进先出的线性表，简称FIFO（first in first out）。允许插入的一端称为队尾，允许删除的一端称为队头
他们均可用线性表的顺序存储结构来实现，但都存在着顺序存储的一些弊端。因此他们各自有各自的技巧来解决这个问题
对于栈来说，如果两个数据类型相同的栈，可以用数组的两端作栈底的方法让两个栈共享数据，这就可以最大地利用数组空间。
对于对列来说，为了避免数组插入和删除需要移动数据，于是引入了循环队列，使得队头和队尾可以在数组中循环变化。解决了移动数据的时间消化，使得本来插入和删除是O(n)的时间复杂度变成了O(1)。
他们也都可以通过链式存储结构来实现。实现原则上与线下表基本相同。
串
串（string）是由零个或多个字符组成的有限序列，又名字符串。
注：
串的顺序存储有一些变化，串值的存储空间可在程序执行过程中动态分配而得。比如在计算机中存在一个自由存储区。叫做”堆“。这个堆可由C语言动态分配函数malloc()和free()来管理
串的链式存储结构除了在连接串与串操作时有一定方便之外，总的来说不如顺序存储灵活，性能也不如顺序存储结构好。
树
树(Tree)是n(n>=0)个结点的有限集。当n=0时称为空数。在任意一棵非空树中:
有且仅有一个特定的结点称为根(root)结点；
当(n>1)时，其余的结点可分为m（m>0）个互不相交的有限集T1、T2、T3…Tm,其中每一个集合本身又是一棵树，并且称做根的子数（SubTree）
其他定义
结点拥有的子树称为结点的度。度为0时称为叶结点或终端结点。度不为0时称为非终端结点或分支结点。除根结点之外，分支结点也称为内部结点。
结点的层次从根开始定义起，根为第一层，根的孩子为第二层。双亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度或高度。 如果将树中结点的各个子树看成从左至右是有序的，不能互换的，则称该树为有序树，否则称为无序树。
森林是m（m>0）棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。
树的存储结构：
- 双亲表示法：在每一个结点中，附设一个指示器指示双亲结点在数组中的位置。
- 孩子表示法：把每个结点的孩子排列起来，以单链表作为存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中。
- 孩子兄弟表示法：任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设计两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。
二叉树
二叉树是n(n>=0)个结点的有限集合，该集合或为空集（称为空二叉树），或者由一个根节点和两颗互不相交的，分别称为根结点的左子树和右子树的二叉树组成。
二叉树的特点：
- 每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。注意不是只有两颗子树，而是最多有。没有子树或者有一颗子树都是可以的。
- 左子树和右子树是有顺序的，次序不能任意颠倒。
- 即使树中的某一个节点，也要区分是左子树还是右子树
二叉树具有5种基本形态
- 空二叉树
- 只有一个根结点
- 根结点只有左子树
- 根结点只有右子树
- 根结点既有左子树又有右子树
特殊二叉树
斜树:所有的结点都只有左子树的二叉树叫做左斜树。所有节点都只有右子树的二叉树叫做右斜树。左斜树和右斜树统称为斜树。
满二叉树：如果所有的分支节点都存在左子树和右子树，并且所有的叶子都在同一层上。这样的二叉树叫做满二叉树。
完全二叉树：对一颗具有n个结点的二叉树按层序标号，如果编号为i（1 <= i <=n ）的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵树称为完全二叉树。(不好理解)
