什么是队列
具有一定操作约束的线性表 只能在一端插入，从另一端删除
先入先出FIFO
队列的顺序存储实现
环形数组可以使数组的空间得到最大空间利用
队列的顺序存储结构通常由一个一维数组和一个记录队列头元 素位置的变量front以及一个记录队列尾元素位置的变量rear组成。
arr1.png
注意：
顺环队列会出现空、满无法区分，解决方法空一个空间不放元素或者添加一个tag或者size标记
队列的链式存储实现
队列的链式存储结构也可以用一个单链表实现。插入和删除操作 分别在链表的两头进行.
list1.png
list2.png
树和树的表示
查找(Searching)
查找:根据某个给定关键字K ，从集合R中找出关键字与K相同的记录
-
静态查找:集合中记录是固定的
没有插入和删除操作，只有查找
-
动态查找:集合中记录是动态变化的
除查找，还可能发生插入和删除
静态查找
-
方法1:顺序查找
serach1.png
哨兵的作用可以少一步判断(i>0)
- 方法2：二分查找算法 具有对数的时间复杂度O(logN)
二分查找的启示我们可以存在一种新的结构叫做树
树的定义
树(Tree): n(n≥0)个结点构成的有限集合。
当n=0时，称为空树;
对于任一棵非空树(n> 0)，它具备以下性质
树中有一个称为“根(Root)”的特殊结点，用 r 表示;
其余结点可分为m(m>0)个互不相交的有限集T1，T2，... ，Tm，其 中每个集合本身又是一棵树，称为原来树的“子树(SubTree)”
子树是不相交的
除了根结点外，每个结点有且仅有一个父结点;
一棵N个结点的树有N-1条边。
树的一些基本术语
- 结点的度(Degree):结点的子树个数
- 树的度:树的所有结点中最大的度数
- 叶结点(Leaf):度为0的结点
- 父结点(Parent):有子树的结点是其子树
的根结点的父结点 - 子结点(Child):若A结点是B结点的父结 L
点，则称B结点是A结点的子结点;子结点也
称孩子结点。 - 兄弟结点(Sibling):具有同一父结点的各
结点彼此是兄弟结点。 - 路径和路径长度:从结点n1到nk的路径为一 个结点序列n1 , n2 ,... , nk , ni是 ni+1的父结 点。路径所包含边的个数为路径的长度。
- 祖先结点(Ancestor):沿树根到某一结点路 径上的所有结点都是这个结点的祖先结点。
- 子孙结点(Descendant):某一结点的子树 中的所有结点是这个结点的子孙。
- 结点的层次(Level):规定根结点在1层， 其它任一结点的层数是其父结点的层数加1。
- 树的深度(Depth):树中所有结点中的最 大层次是这棵树的深度。
树的表示
Tree1.png
这种数据结构称为二叉树 左边指向子节点 右边指向兄弟节点
