数据的逻辑结构：
- 集合
- 线性
- 树形
- 图形
数据元素的存储结构：
- 顺序存储
- 链式存储
算法三要素：
- 有穷性
- 确定性
- 可行性
渐进增长：
函数的渐进增长：给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有n>N，f(n)总是比g(n)大，我们说f(n)的增长渐进快于g(n)。
时间复杂度：
T(n) = O(f(n)) O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n) 基本不考虑O(n^3)以上的算法 时间复杂度一般都是值最坏复杂度
算法的空间复杂图：
S(n) = O(f(n))
- 零个或多个数据元素的优先序列。
- 若将线性表记为(a1, ..., ai-1, ai, ai+1, ..., an),则表中ai-1领先于ai,ai领先于ai+1,称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。
- 线性表元素的个数为n(n为自然数)定义为线性表的长度，当n=0时，称为空表。
Operation:
- InitList(*L)
- ListEmpty(L)
- ClearList(*L)
- GetElem(L, i, *e)
- LocateElem(L, e)
- ListInsert(*L, i, e)
- ListDelete(*L, i, *e)
- ListLength(L)
我们通常把具有存取时间性能为O(1)的存储结构称为随机存储结构
线性表顺序存储结构
优点：
- 无需为存储逻辑有新的存储开销
- 可以快速地存取表中任意位置
缺点：
- 插入和删除时，开销较大
- 容量变大时，不易确定存储容量
- 造成存储空间碎片
若线性表需要频繁查找，很少插入和删除，宜采用顺序存储结构。反之采用单链表结构 用数组描述的链表叫做静态链表
- 是限定仅在表尾进行插入和删除操作的线性表
- 我们把允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom),不含任何数据元素的栈称为空栈。栈又称为后进先出(Last In First Out)的线性表，简称LIFO结构
- 栈的插入操作，叫做进栈，也称压栈、入栈
- 栈的删除操作，叫做出栈，也有的叫做弹栈
如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些。
- 一种不需要括号的后缀表达法，我们也把它称为逆波兰(Reverse Polish Notation, RPN)
- 标准四则运算表达式叫做中缀表达式
- 是只允许在一端进行插入操作，而在另一端进行删除操作的线性表
- 队列是一种先进先出(First In First Out)的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。
- 我们把队列的这种头尾相接的顺序存储结构称为循环队列
- 队列的链式存储结构，即线性表的单链表并只能尾进头出。简称为链队列
- 串(string)是由零个或多个字符组成的有限序列，有名叫字符串。
- 零个字符的串称为空串(null string),可以使用""表示。
- 串中任意个数的连续字符组成的子序列称为该串的子串。
KPM算法
$$
next(j)=\begin{cases}
0&\text{当j=1时}\
\max{k | 1<k<j,且p_{1}..._{k-1} = p_{j-k+1} ... P_{j-1}}当此集合不空时\
1&\text{其它情况}
\end{cases}
$$
定义：
树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。在任意一棵非空树中:
- 有且仅有一个特定的称为根(Root)的结点。
- 当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、...、Tm，其中每一个集合本身又是一个树，并且称为根的子树(subTree)
结点分类：
- 结点拥有的子树数称为结点的度(Degree)。度为0的结点称为叶结点(Leaf)或终端结点；度不为0的结点称为非终端结点或分支结点。除根结点之外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。
- 结点的子树的根称为该结点的孩子(Child)，相应地，该结点称为孩子的双亲(Parent)
- 同一个双亲的孩子之间互称兄弟(sibling)。
- 结点的祖先是从根到该结点所经分支上的所有结点。
- 以某结点为根的子树中的任一结点都称为该结点的子孙。
树的其它相关概念：
- 结点的层次(Level)从根开始定义起，根为第一层，根的孩子为第二层。树中结点的最大层次称为树的深度(Depth)或高度。
- 如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序数，否则为无序数。
- 森林(Forset)是m(m>=0)课互不相交的树的集合。
定义：
二叉树是n(n>=0)个结点的有限集合，该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
特点：
- 每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。
- 左子树和右子树是有顺序的，次序不能任意颠倒。
- 即使树种某结点只有一棵子树，也要区分它的左子树还是右子树。
特殊二叉树：
- 斜树: 所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜数。
- 满二叉树: 在一棵二叉树中，如果所有分支结点都存在左子树和右子树。并且所有叶子都在同一层上，这样的二叉树称为满二叉树。
- 完全二叉树: 对一棵具有n个结点的二叉树按层序编号，如果编号为i（1<=i<=n）的结点与同样深度的满二叉树中标号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。特点：
- 叶子结点只能出现在最下两层。
- 最下层的叶子一定集中在左部连续位置。
- 倒数两层，若有叶子结点，一定都在右部连续位置。
- 如果结点度为1，则该结点只有左孩子，即不存在只有右子树的情况
- 同样结点数的二叉树，完全二叉树的深度最小
二叉树性质：
- 在二叉树的第i层上之多有$2^{i-1}$个结点。
- 深度为k的二叉树至多有$2^k-1$个结点。
证明: 满二叉树结点数为$$1+2+\cdots+2^{k-1} = 2^k-1$$
- 对任何一棵二叉树T,如果其终端结点数为$n_0$,度为2的结点数为$n_2$,则$n_0=n_2+1$。
证明:
$\because n-1 = 2n_2 + n_1(边的数量为n-1)\ \because n = n_1 + n_2 + n_0\ \therefore n_0 = n_2 + 1$
- 具有n个结点的完全二叉树的深度为[$log_2n$]＋1([x]表示不大于x的最大整数)
证明:
$\because$ 因为深度为k的满二叉树结点为$2^k-1$ $\therefore$n个结点的满二叉树则深度为$log_2(n+1)$ 如果完全二叉树和满二叉树度数相同，那么它的结点数一定少于等于同样度数的满二叉树，且一定多于$2^{k-1}-1$。即$2^{k-1}-1<n\leq2^k-1$。由于n是整数，所以$2^{k-1}{\leq}n<2^K$。$\because$k也是整数。$\because$ 深度为[$log_2n$]＋1
- 如果对一棵有n个结点的完全二叉树（其深度为$[log_2n]+1$的结点按层次编号，对任一结点i(
$1{\leq}i{\leq}n$ )有） - 如果i=1,则结点i是root，如果i>1,则其双亲是结点[i/2]
- 如果2i>n,则结点i为leaves；否则其做孩子是结点2i。
- 如果2i+1>n,则结点i无右孩子；否则其右孩子是结点2i+1。
二叉树的遍历（traversing binary tree）是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅访问一次。
- 前序遍历
首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。(root, left, right)
- 中序遍历
先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树。(left, root, right)
- 后序遍历
首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。(left, right, root)
- 层序遍历
从树的第一层开始访问，从上向下逐层遍历，在同一层中，按从左到有的顺序对结点逐个访问。
有n个结点的二叉链表，一共有2n个指针域。而二叉树一共有n-1条分支。所以存在n+1个空指针域。我们给这些空指针域加上前驱和后继，称为线索。加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树。
树与森林的遍历：
- 先根遍历
先访问树的根结点，然后依次对每棵子树进行先根访问。（树的前序，二叉树的前序）
- 后根遍历
依次对每棵树进行后根访问，在访问树的根结点。（树的后续，二叉树的中序）
哈夫曼树（Huffman tree） 从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称作路径长度。树的路径长度就是从树根到每一结点的路径长度之和。树的带权路径长度为树中所有叶子结点的带权路径（WPL）之和，其中WPL最小的二叉树称为哈夫曼树（最优二叉树）
定义：
图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为G(V,E),G表示一个图，V是图G中**顶点(Vertex)的集合，E是图G中边(Edge)**的集合。
无向图：
若顶点$v_i$到$v_j$之间的边没有方向，则称这条边为无向边(Edge),用无序偶对**(
$v_i,v_j$ )来表示。如果图中任意两个顶点之间的边都是无向边，则称该图为无向图(Undirected graphs)**。
有向图：
若从顶点$v_i$到$v_j$的边有方向，则称这条边为有向边，也称为弧(Arc)。使用有序偶**<$v_i,v_j$>来表示，$v_i$称为弧尾(Tail)，$v_j$称为弧头(Head)。如果图中任意两个顶点之前的边都是有向边，则称该图为有向图(Directed graphs)**。
简单图和无安全图：
在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。每对顶点之间都恰连一条边的简单图称为完全图。
无向完全图和有向完全图：
每一条边都为无向边的完全图称为无向完全图。含有n个顶点的无向完全图有$\frac{n\times(n-1)}{2}$条边。在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称为图为有向完全图。含有n个顶点的有向完全图有$n\times(n-1)$条边。
网：
有很少条边或弧的图称为稀疏图，反之称为稠密图。边或弧带权(Weight)的图通常称为网(Network)。
子图：
假设有两个图$G=(V,{E})$和$G'=(V',{E'})$,如果$V' \subseteq V$且$E' \subseteq E$，则称G'为G的子图(Subgraph)
####图的顶点与边之间的关系： 无向图：
对于无向图$G=(V,{E})$，如果边$(v,v') \in E$，则称顶点$v$和$v'$互为邻接点(Adjacent)，即$v$和$v'$相邻接。边$(v,v')$依附(incident)于顶点$v$和$v'$,或称为与顶点相关联。顶点$v$的度(Degree)是和v相关联的边的数目，记为TD(v)。易证$e=\frac{1}{2}\sum_{i=1}^{n}TD(v_i)$。
有向图：
对于有向图$G=(V,{E})$，如果弧$<v,v'> \in E$,则称顶点$v$邻接到顶点$v'$，顶点$v'$邻接自顶点$v$。弧$<v,v'>$和顶点$v$,
$v'$ 相关联。以顶点v为头的弧的数目称为$v$的入度(InDegree)，记为ID(v);以$v$为尾的弧的数目称为$v$的出度(OutDegree)，记为OD(v)；顶点$v$的度$TD(v) = ID(v) + OD(v)$。易证$e = \sum_{i=1}^{n}ID(v_i) = \sum_{i=1}^{n}OD(v_i)$。
（缺省部分......）
图的存储结构：
- 图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组表示图。一个一维数组存储图中的顶点信息，一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。
- 图的邻接表(Adjacency List)
- 十字链表(Orthogonal List)(有向图的邻接表优化)
- 邻接多重表 (无向图的邻接表优化)
- 边集数组
图的遍历(Traversing Graph)
- 深度优化遍历(Depth_First_Search),也称为深度优化搜索，简称DFS。
- 广度优先遍历(Breadth_First_Search),也称为广度优先搜索，简称BFS。
构造连通网的最小代价生成树称为最小生成树(Minimum Cost Spanning Tree)
- Prim算法
- Kruskal算法
最短路径算法
- Dijkstra算法
- Floyd算法 D^{0}[v][w] = min{D^{-1}[v][w], D^{-1}[v][0] + D^{-1}[0][w]}
AOV网 AOE网
拓扑排序，其实就是对一个有向图构造拓扑序列的过程。 关键排序，路径上各个活动所持续的时间之和称为路径长度，从源点到汇点具有最大长度的路径叫关键路径，在关键路径上的活动叫关键活动。
几个参数:
- 事件的最早发生时间etv(earliest time of vertex):即顶点vk的最早发生时间。
- 事件的最晚发生时间ltv(latest time of vertex):即顶点vk的最晚发生时间。
- 活动的最早开工时间ete(earliest time of edge): 即弧ak的最早发生时间。
- 活动的最晚开工时间lte(latest time of edge):即弧ak的最晚发生时间。
查找表（Search Table）是由同一类型的数据元素（或记录）构成的集合。关键字（key）是数据元素中某个数据项的值，又称为键值。若此关键字可以唯一地标识一个记录，则称此关键字为主关键字（Primary Key），可以识别多个数据元素（或记录）的关键字，我们称为次关键字（Secondary Key）。
查找(Searching)就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素(或记录)。
静态查找表(Static Search Table):
只作查找操作的查找表
动态查找表(Dynamic Search Table):
在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。
数序查找(Sequential Search)
索引就是把一个关键字与它对应的记录相关联的过程。 线性索引就是将索引项集合组织为线性结构，也称为线性表。
稠密索引是指在线性索引中，将数据集中的每个记录对应一个索引项 对于稠密索引，索引项一定是按照关键码有序的排列。 分块有序：块内无序，块间有序。
倒排索引(inverted index)
二叉排序树(Binary Sort Tree)又称为二叉查找树。它或者是一颗空树，或者是具有下列性质的二叉树:
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结构的值
- 若它的右子树不空，则左子树上所有结点的值均大于它的根结构的值
- 它的左右子树也分别为二叉排序树
平衡二叉树(Self-Balancing Binary Search Tree 或 Height-Balanced Binary Search Tree)，是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1.
二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF(Balance Factor),平衡二叉树的平衡因子只可能是0，1，-1。
距离插入结点最近的，且平衡因子的绝对值大于1的结点为根的子树，我们称为最小不平衡子树。
多路查找树(muitl-way search tree)，其每一个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素。
2-3 树是这样的一棵多路查找树：其中的每一个结点都具有两个孩子（称为2结点）或三个孩子（称为3结点）
一个2结点包含一个元素和两个孩子（或没有孩子）。左子树小于该元素，右子树大于该元素。 一个3结点包含一小一大两个元素和三个孩子（或没有孩子）。左子树包含小于较小元素的元素，右子树包含大于较大元素的元素，中间子树包含介于两元素之间的元素。
**B数(B-tree)是一种平衡的多路查找树。结点最大的孩子数目称为B数的阶(order) 一个m阶的B数具有如下属性：
- 如果根结点不是叶结点，则其至少有两棵子树。
- 每一个非根的分支结点都有k-1个元素和k个孩子，其中[m/2]<=k<=m。每一个叶子结点n都有k-1个元素，其中[m/2]<=k<=m。
- 所有叶子结点都位于同一层次。 （需要补充）
两个关键字$key_1 \neq key_2$，但却有$f(key_1) = f(key_e)$,这种现象我们称为冲突(collision),并把$key_1$和$key_2$称为这个散列函数的同义词(synonym)
堆是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆，反之称为小顶堆。