数据结构

头指针：链表中第一个结点存储的位置称为头指针， 如果单链表有头结点，则头指针指向头结点 ，如果单链表没有头结点，则头指针指向第一个首元结点

头节点：在单链表的一个结点前附设一个结点称为头结点，数据域可以不存任何信息，指针域指向单链表第一个元素的结点

首元结点：单链表中第一个有数据元素的结点，如果单链表有头结点，则首元结点为头结点的下一个结点，如果单链表没有头结点，则首元结点就是单链表的第一个结点

栈应用

单调栈

循环队列：

单调队列

分支结点(非终端结点)：度不为0的节点称为分支结点(非终端结点)，除根结点外，分支节点也称内部结点

二叉树是n(n>=0)个结点的有限集合，该集合或者为空集，或者由一个根结点和两个互不相交的，分别称为根结点的左子树和右子树的二叉树组成

斜树:所有结点都只有左子树或只有右子树的二叉树

满二叉树：在一棵二叉树中，所有的分支结点都有左子树和右子树，并且所有的叶子结点都在同一层上，这样的二叉树称为满二叉树

完全二叉树：对一棵具有n个结点的二叉树按层级编号，如果编号为i的结点与和它相同深度的满二叉树的编号为i的结点在树中位置一致，则这棵二叉树称为完全二叉树

二叉查找树(BST)：对于树中每个结点X，它的左子树中所有项的值都小于X项的值，它的右子树中所有项的值都大于X项的值

线索二叉树:指向前驱和后继的指针称为线索，在二叉树的结点上加上线索的二叉树称为线索二叉树
                   对二叉树以某种次序遍历，使其变为线索二叉树的过程称做线索化

平衡二叉树

1: 在二叉树的第i层上，最多有2^i - 1个结点

2：深度为k的二叉树，最多有2^k - 1个结点

3： 对于任意一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1

4: 具有n个结点完全二叉树的深度为[log2 n]+1([x]表示不大于x的最大整数)

5： 如果对一棵有n个结点的完全二叉树的结点按层级编号，对任意结点i有：
             1. 如果i=1，则结点i是树的根。如果i>1，则其双亲结点是[i/2]
             2. 如果2i > n，则结点i无左孩子(为叶子结点)，否则其左孩子为2i
             3. 如果2i+1 > n，则结点i无右孩子，否则其右孩子为结点2i+1

二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置也就是数组的下标，要能体现结点之间的逻辑关系
比较适合存储完全二叉树
对于一般的二叉树，也可以按照完全二叉树存储，将不存在的结点用“^”占位

由一个数据域和两个指针域组成

定义：二叉树的遍历是指从根结点出发，按照某种次序，依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次

前序遍历：先访问根结点，再前序遍历左子树，再前序遍历右子树

中序遍历：先中序遍历左子树，再访问根结点，再中序遍历右子树

后序遍历： 先后续遍历左子树，再后续遍历右子树，再访问根结点

路径：从树中一个结点到另一个结点的分支构成两个结点之间的路径

路径长度：路径上的分支数称为路径长度

结点路径长度：从该结点到根结点的分支数称为结点的路径长度

树的路径长度:从树根到每一个结点的路径之和称为树的路径长度

结点的WPL(带权路径长度)：从该结点到树根的路径长度与该结点上权的乘积

树的带权路径长度：树中所有叶子结点的WPL(带权路径长度)之和

以w1,w2,...,wn作为相应叶子结点的权值来构造一棵赫夫曼树，规定赫夫曼树的左分支代表0，右分支代表1。则从根结点到叶子结点所经过的路径分支组成的0和1的序列便为该叶子结点对应字符的编码，这就是赫夫曼编码

相关概念

性质：

定义：B树是一种平衡的多路查找树，结点最大的孩子数目称为B树的阶

性质

2-3树

2-3-4树

一颗m阶B+树和B树的差异

小顶堆：任意结点的值均小于等于其左右孩子值，并且最小值位于堆顶，即根节点处

大顶堆：任意结点的值均大于等于它的左右孩子，并且最大的值位于堆顶，即根节点处

无向边：若顶点Vi到Vj之间的边没有方向，则称这条边为无向边，用无序偶对(Vi,Vj)表示

无向图：图中任意两顶点的边都是无向边，则称该图为无向图

无向完全图：在无向图中，若任意两个顶点之间都存在边，则称该图为无向完全图

顶点的度：顶点v的度是和顶点v相关的边的数目(记为TD(v))。边数等于各顶点度之和的一半

连通图：如果从顶点v到v'有路径，则称v和v'是连通的，如果图中任意两个顶点都是连通的，则称图是连通图

连通分量

生成树：无向图中连通且n个顶点和n-1条边的叫生成树

有向边：若顶点Vi到Vj之间的边有方向，则称这条边为有向边，也称为弧，用有序偶对<Vi,Vj>,Vi称为弧尾，Vj称为弧头

有向图：图中任意两顶点的边都是有向边，则称该图为有向图

有向完全图：在有向图中，若任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图

入度：以顶点V为头的弧的数量称为，顶点V的入度(记为ID(v))

出度：以顶点V为尾的弧的数量称为，顶点V的出度(记为ID(v))

强连通图：是指在有向图G中，如果对于每一对vi、vj，vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。

强连通分量：有向图中的极大强连通子图称做有向图的强连通分量

有向树：有向图中一个顶点入度为0的，其余顶点入度为1的称为有向树

生成森林：一个有向图的生成森林由若干个有向树组成，含有图中所有顶点，但只有足以构成若干棵不相交的有向树的弧

图的邻接矩阵就是用两个数组来表示图，一个一维数组存储图中顶点集合，一个二维数组(邻接矩阵)存储图中边或弧的关系

邻接表是将数组和链表结合起来的存储方法

1.顶点数组中每个元素包含，data，firstin，fristout

2.单链表中每个结点包含：tailvex，headvex，headlink，taillink

重新定义邻接表的边表结点结构为(ivex,ilink,jvex,jlink),其中ivex和jvex表示依附某条边的两个顶点在顶点数组中的下标，ilink指向依附顶点ivex的下一条边，jlink指向依附顶点jvex的下一条边

由两个一维数组组成，一个一维数组存储图中顶点集合，另一个数组存储边的信息，这个边数组的每个元素由一条边的起始下标，终点下标和权重组成

在查找表的尽头放置哨兵，免去每次比较值后还要判断下标是否越界

前提线性表中记录是有序的，每次比较时取线性表的中间值比较，若相等则查找成功，若小于，则在线性表左半区查找，若大于则在线性表右半区查找，不断重复上述过程，直到成功，或所有查找区域无记录，查找失败

插值查找算法类似于二分查找，不同的是插值查找每次从自适应 mid 处开始查找

斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1，即n=F(k)-1;
开始将k值与第F(k-1）位置的记录进行比较(及mid=low+F(k-1)-1),比较结果也分为三种
1）相等，mid位置的元素即为所求
2）> ,low=mid+1,k-=2;说明:low=mid+1说明待查找的元素在[mid+1,hign]范围内，k-=2 说明范围[mid+1,high]内的元素个数为n-（F(k-1))= Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1个，所以可以递归的应用斐波那契查找
3)< ,high=mid-1,k-=1;说明:low=mid+1说明待查找的元素在[low,mid-1]范围内，k-=1 说明范围[low,mid-1]内的元素个数为F(k-1)-1个，所以可以递归的应用斐波那契查找

直接定址法

数字分析法

平方取中法

折叠法

除留余数法

随机数法

开放定址法

再散列函数法

链地址法

公共溢出区法