组合计数

加乘原理

乘法原理：完成一个工程需要分 $n$ 个步骤，$a_i(1 \le i \le n)$ 代表第 $i$ 个步骤的不同方法数目。那么完成这件事共有 $S = a_1 \times a_2 \times \cdots \times a_n$ 种不同的方法。

加法原理：完成一个工程可以有 $n$ 类办法，$a_i(1 \le i \le n)$ 代表第 $i$ 类方法的数目。那么完成这件事共有 $S=a_1+a_2+\cdots +a_n$​ 种不同的方法。

例题(快速幂)：计算$x^ymod\ p$

1
2
3
4
5
6

int pow(int x,int y){ 
	int res=1;
	x%=p;
	for(;y;y>>=1,x=x*x%p) if(y&1) res=res*x%p;
    return res;
}

排列数

从 $n$ 个不同元素中，任取 $m$（$m\leq n$）个元素按照一定的顺序排成一列，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个排列；

从 $n$ 个不同元素中取出 $m$($m\leq n$) 个元素的所有排列的个数，叫做从 $n$ 个不同元素中取出 $m$ 个元素的排列数，用符号 $\mathrm A_n^m$表示。
$$
\mathrm A_n^m = n(n-1)(n-2) \cdots (n-m+1) = \frac{n!}{(n - m)!}
$$

组合数

从 $n$ 个不同元素中，任取 $m \leq n$ 个元素组成一个集合，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个组合；

从 $n$ 个不同元素中取出 $m \leq n$ 个元素的所有组合的个数，叫做从 $n$ 个不同元素中取出 $m$ 个元素的组合数，用符号 $\dbinom{n}{m}$ 来表示；
$$
\dbinom{n}{m} = \frac{\mathrm A_n^m}{m!} = \frac{n!}{m!(n - m)!}
$$

例题：计算$\dbinom{n}{m} mod\ p$

1
2
3
4
5
6

int inv(int x,int p){ //求逆元
	return pow(x,p-2);
}
fac[0]=1;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i; //预处理出阶乘
return ((fac[n]*inv(fac[m],p))%p*inv(fac[n-m],p))%p;

圆排列

$n$ 个人全部来围成一圈，所有的排列数记为 $\mathrm Q_n^n$。考虑其中已经排好的一圈，从不同位置断开，又变成不同的队列。
所以有
$$
\mathrm Q_n^n \times n = \mathrm A_n^n \Longrightarrow \mathrm Q_n = \frac{\mathrm A_n^n}{n} = (n-1)!
$$

由此可知部分圆排列的公式：

$$
\mathrm Q_n^r = \frac{\mathrm A_n^r}{r} = \frac{n!}{r \times (n-r)!}
$$

抽屉原理

将 $n$ 个物体，划分为 $k$ 组，那么至少存在一个分组，含有大于或等于 $\left \lceil \dfrac{n}{k} \right \rceil$ 个物品。

推广的形式也可以使用反证法证明：若每个分组含有小于 $\left \lceil \dfrac{n}{k} \right \rceil$ 个物体，则其总和 $S\leq (\left \lceil \dfrac{n}{k} \right \rceil -1 ) \times k=k\left\lceil \dfrac{n}{k} \right\rceil-k < k(\dfrac{n}{k}+1)-k=n$ 矛盾。

此外，划分还可以弱化为覆盖结论不变。
给定集合 $S$, 一个 $S$ 的非空子集构成的簇 ${A_1,A_2\ldots A_k}$

• 若满足 $\bigcup_{i=1}^k A_i$ 则称为 $S$ 的一个覆盖（cover）；
• 若一个覆盖还满足 $i\neq j\to A_i\cap A_j=\varnothing$ 则称为 $S$ 的一个划分。

鸽巢原理可以有如下叙述：对于 $S$ 的一个覆盖 ${A_1,A_2\ldots A_k}$ 有至少一个集合 $A_i$ 满足 $\left\vert A_i \right\vert \geq \left\lceil \dfrac{\left\vert S \right\vert}{k} \right\rceil$。

容斥原理

设 U 中元素有 n 种不同的属性，而第 i 种属性称为 $P_i$，拥有属性 $P_i$ 的元素构成集合 $S_i$，那么

$$
\begin{aligned}
\left|\bigcup_{i=1}^{n}S_i\right|=&\sum_{i}|S_i|-\sum_{i<j}|S_i\cap S_j|+\sum_{i<j<k}|S_i\cap S_j\cap S_k|-\cdots\
&+(-1)^{m-1}\sum_{a_i<a_{i+1} }\left|\bigcap_{i=1}^{m}S_{a_i}\right|+\cdots+(-1)^{n-1}|S_1\cap\cdots\cap S_n|
\end{aligned}
$$

即

$$
\left|\bigcup_{i=1}^{n}S_i\right|=\sum_{m=1}^n(-1)^{m-1}\sum_{a_i<a_{i+1} }\left|\bigcap_{i=1}^mS_{a_i}\right|
$$
证明：

对于每个元素使用二项式定理计算其出现的次数。对于元素$ x$，假设它出现在 $T_1,T_2,\cdots,T_m$ 的集合中，那么它的出现次数为

$$
\begin{aligned}
Cnt=&|{T_i}|-|{T_i\cap T_j|i<j}|+\cdots+(-1)^{k-1}\left|\left{\bigcap_{i=1}^{k}T_{a_i}|a_i<a_{i+1}\right}\right|\
&+\cdots+(-1)^{m-1}|{T_1\cap\cdots\cap T_m}|\
=&\dbinom{m}{1}-\dbinom{m}{2}+\cdots+(-1)^{m-1}\dbinom{m}{m}\
=&\dbinom{m}{0}-\sum_{i=0}^m(-1)^i\dbinom{m}{i}\
=&1-(1-1)^m=1
\end{aligned}
$$

于是每个元素出现的次数为 1，那么合并起来就是并集;

数理逻辑

命题

命题是指具有确切真值的判断语义；

• 原子命题：无法分解为更简单命题的命题；
• 复合命题：可以继续被分解的命题；

命题应该用大写的字母表示；

联结词

进一步，复合命题可以表示为原子命题和联结词的组成；

命题公式

对于一个常值命题而言，它的真值不是真就是假；

对于一个任意的，没有赋予内容的原子命题，称其为命题变量，如果它没有确切的真值，真值取决于命题的内容；

命题公式可由如下规则生成：

• 命题变元本身是一个公式；
• 若$G$是一个公式，则$\neg G$也是公式；
• 若$G,H$是一个公式，则$(G\wedge H),(G\vee H),(G\to H),(G\lrarr H)$也是公式；
• 联结词的使用有限次；

对于$G$是含有命题变元$P_1,P_2,…,P_n$的公式，记为$G(P_1,P_2,…,P_n)$

指定$P_1,P_2,…,P_n$的一组真值，称这组真值是$G$的一个解释$I$;

分类

对于命题公式$G$;

• 重言式：若$G$的所有解释下真值为真；
• 矛盾式：若$G$的所有解释下真值为假；
• 可满足式：至少存在一种解释$I$,使得$G$在$I$下为真；

若对于两个命题公式$G,H$,它们出现的命题变元为$P_1,…,P_n$,对于$2^n$个每一种解释，$G,H$的真值相同，称$G,H$是等价的，记作$G=H$;

• 显然$=$不是联结词，而是一种等价关系；
• 满足自反性，对称性，传递性；
• 当$G\lrarr H$为重言式时，$G=H$

对于等价关系可以暴力的使用真值表加以验证；

代入定理：

对于命题公式$G(P_1,…,P_n)$,对于任意的命题公式$G_i(P_1,…,P_n),1\le i\le n$;

如果$G$是重言式或者矛盾式，

对于$G(G_1,…,G_n)=G’(P_1,…,P_n)$也是重言式或者矛盾式；

替换定理

设$Ｇ_1$是$Ｇ$的子公式，$Ｈ_1$是任意的命题公式，在$Ｇ$中凡出现$Ｇ$_1，处都
以$H_1$替换，由此得到新的命题公式$Ｈ$，若$G_1=H_1$,则$G=H$

范式

文字：命题变元，或者命题变元的否定；

子句：有限个文字的析取式

短语：有限个文字的合取式

析取范式：有限个短语的析取式；

合取范式：有限个短语的合取式；

主析取范式：每一个短语都是最小项；

定理：对于任意的命题公式，都存在与其等价的析取范式和合取范式；

proof:可分为如下三步逐步转化：

1. 消去等价关系和蕴含关系
   $$
   (G\to H)=(\neg G \vee H)\
   (G\lrarr H)=(\neg G\vee H)\wedge (G\vee \neg H)
   $$

2. 将否定移动到命题变元前面
   $$
   \neg \neg G=G\
   \neg(G\wedge H)=\neg G\vee \neg H\
   \neg(G\vee H)=\neg G\wedge \neg H
   $$

3. 重复利用分配律
   $$
   G\wedge(H\vee S)=(G\vee H)\wedge(G\vee S)\
   G\vee(H\wedge S)=(G\wedge H)\vee(G\wedge S)
   $$

推理理论

形式证明：

• 前提：已知的命题公式；
• 结论：从前提出发利用推理规则推出的命题公式

通过形式证明可以的出有效结论，我们不关心前提时都为真，只关注推理的真实性；

对于公式$G_1,G_2,…,G_n,H$，称$H$为$G_1,G_2,…,G_n$的逻辑结果，当且仅当对于任意的解释$I$，若$I$同时满足$G_1,G_2,…,G_n$,则$I$满足$H$，记作$G_1,G_2,…,G_n\Rarr H$

• 此时称这个$G_1,G_2,…,G_n\Rarr H$是有效的，
• 称$G_1,G_2,…,G_n$为一组前提；
• 称$H$为结论，或者逻辑结果；

关系理论

集合定义

序偶(ordered pair)：两个元素$x,y$按照一定的次序组成的二元组$<x,y>$；

• $<a,b>=<c,d>\iff a=c,b=d$

$n$重有序组：$n$个元素$a_1,a_2,…,a_n$按照一定的次序组成的$n$元组

笛卡尔积(Cartesian product):对于集合$A,B$，笛卡尔积为如下集合
$$
A\times B={<x,y>|x\in A\wedge y\in B}
$$

• 不满足交换律：$A\times B \neq B\times A$，但是$\mid A\times B\mid = \mid B\times A\mid = |A|\times|B|$
• $A\times(B\cup C)=(A\times B)\cup(A\times C)$;
• $A\times(B\cap C)=(A\times B)\cap(A\times C)$;
• $A\times B\subseteq C\times D\iff A\sube C,B\sube D$

关系(relation):对于非空集合$A,B$, 称$R$是从$A$到$B$的二元关系$R:A\to B$，如果$R$是$A\times B$的一个子集；

• 空关系：$R=\varnothing$;
• 恒等关系：$R=I_A={<x,x>|x\in A}$
• 全关系：$R=A\times B$
• $x$对$y$有关系$R$：$<x,y>\in R\iff xRy$
• 所有可能的关系有$2^{|A||B|}$个

$n$元关系：$A_1\times…\times A_n$的任意子集；

对于$A,B$间的二元关系$R\subseteq C\times D\sube A\times B$;

若$C \sube A,D\sube B$且
$$
C={x\mid x\in A,\exist y\in B,<x,y>\in R}\
D={y\mid y\in B, \exist x\in A, <x,y> \in R}
$$
定义如下概念：

• 前域$A$
• 后域$B$
• 定义域${\rm dom} R=C$
• 值域${\rm ran} R=D$
• 域${\rm fid}R =C\cup D$

关系图和关系矩阵

关系可以用关系图表示

• 若关系定义在不同的集合：用带箭头的二部图表示，由前域指向后域；
• 若关系定义在某一个集合：用可能有向图表示，可能有自环和重边；；

称$\mathbf M_R =(m_{ij}){m\times n}$为关系$R$的关系矩阵(邻接矩阵)，如果
$$
m{ij}=\begin{cases}1&<a_i,b_j>\in R\0&<a_i,b_j>\notin R \end{cases}
$$
显然这是一个Bool矩阵，对于$\mathbf A,\mathbf B$是$m\times n$的Bool矩阵：

• 并
  $$
  \mathbf C=\mathbf A\vee \mathbf B=(c_{ij}),c_{ij}=\begin{cases}1&a_{ij}=1\vee b_{ij}=1\0& a_{ij}=0\wedge b_{ij}=0 \end{cases}
  $$

• 交
  $$
  \mathbf C=\mathbf A\wedge \mathbf B=(c_{ij}),c_{ij}=\begin{cases}1&a_{ij}=1\wedge b_{ij}=1\0& a_{ij}=0\vee b_{ij}=0 \end{cases}
  $$

• 布尔积
  $$
  \mathbf C=\mathbf A\odot \mathbf B=(c_{ij}),c_{ij}=\begin{cases}1&\exist k,a_{ik}=b_{kj}=1\0&\rm otherwise \end{cases}
  $$

关系表

在关系代数理论中，关系可以用二维表表示；

对于关系$R\sube A_1\times A_2\times \cdots\times A_n$,第$i$个属性代表$A_i$,每一个行/表项为$R$中的元素；

复合运算

对于非空集合$A,B,C$，$R：A\to B,S:B\to C$,称一个从$A$到$C$的关系是复合关系，如果
$$
R \circ S = {<x,z>|x\in A \wedge z\in C\wedge (\exist y)(y\in B\wedge xRy\wedge yRz)}
$$

• $\varnothing \circ R=R\circ \varnothing=\varnothing$
• $(R\circ S)\circ T=R\circ(S\circ T)$
• $I_A \circ R=R\circ I_B$
• $R\circ (S_1\cup S_2)=(R\circ S_1)\cup (R\circ S_2)$
• $R\circ (S_1\cap S_2)\sube(R\circ S_1)\cap (R\circ S_2)$
• $(S_1\cup S_2)\circ R=(S_1\circ R)\cup( S_2\circ R)$
• $(S_1\cap S_2)\circ R\sube(S_1\circ R)\cap( S_2\circ R)$

逆运算

对于非空集合$A,B$，$R:A\to B$,$R$的逆关系是指
$$
R^{-1}:B\to A={<b,a>|<a,b>\in R}
$$

• $(R\circ S)^{-1}=S^{-1}\circ R^{-1}$
• $(R\cup S)^{-1}=R^{-1}\cup S^{-1}$
• $(R\cap S)^{-1}=R^{-1}\cap S^{-1}$
• $(R- S)^{-1}=R^{-1}- S^{-1}$
• $\overline R^{-1}=\overline {R^{-1}}$
• $S\sube R\iff S^{-1}\sube R^{-1}$

逆关系的关系矩阵等于原关系的关系矩阵转置；

幂运算

对非空集合$A$,定义关系$R\sube A\times A$的$n$次幂如下：

• $R_0=I_A$；
• $R^1=R$;
• $R^{n+1}=R^n\circ R=R\circ R^n$

注意到，幂集$R^n$随着$n$增加呈现递减趋势，得出如下定理：
$$
\bigcup_{i=1}^n R^i=\bigcup_{i=1}^{|A|}R^i
$$
proof:只需证明$R^k\sube \bigcup_{i=1}^{|A|}R^i$,注意到定义缩减没必要的复合运算即可；

性质

对于定义在一个集合上的关系，我们考察其自反性，反自反性，对称性，反对称性和传递性；

如果对$\forall x\in A$，都有$<x,x>\in R$,那么称$R$在 $A$上是自反的，关系图上表现为每个结点有自环，关系矩阵上表现为主对角线上全部为1；

• $R$是自反的$\iff I_A\sube R$

如果对$\forall x\in A$，都有$<x,x>\notin R$，那么称称$R$在 $A$上是反自反的；关系图上表现为每个结点都没有自环，关系矩阵上表现为主对角线上全部为0；

• $R$是反自反的$\iff R\cap I_A=\varnothing$

如果对$\forall x,y\in A$，都有$<x,y>\in R \iff<y,x>\in R$,那么称$R$在 $A$上是对称的;关系图上表现为任意两个结点要么没有边，要么有两条反向边，关系矩阵上表现为对称矩阵；

• $R$是对称的$\iff R=R^{-1}$

如果对$\forall x,y\in A$，都有$<x,y>\in R\wedge<y,x>\in R \iff x=y$,那么称$R$在 $A$上是反对称的;关系图上表现为任意两个结点至多一条边，关系矩阵上表现为矩阵自交为0；

• $R$是反对称的$\iff R\cap R^{-1}\sube I_A$

设$R$是非空集合$R$上的关系．对$\forall x,y,z\in A$，如果$＜x,y＞\in R,＜y,z＞\in R$，那么$＜x,z＞∈R$，则称关系$R$是传递的;关系图上表现为每个结点有自环，关系矩阵上表现为$r_{ij}=r_{jk}=1$必有$r_{ik}=1$；

• $R$是传递的$\iff R\circ R\sube R$

对于定义在集合$A$上的二元关系$R,S$,考察其保守性：逆运算和交运算保守性好，并，差和复合运算的保守性差；

• 若$R,S$具有自反性，则$R^{-1},R\cup S,R\cap S,R\circ S$具有自反性；
• 若$R,S$具有反自反性，则$R^{-1},R\cup S,R\cap S,R- S$具有自反性；
• 若$R,S$具有对称性，则$R^{-1},R\cup S,R\cap S,R- S$具有自反性；
• 若$R,S$具有反对称性，则$R^{-1},R\cap S,R- S$具有自反性；
• 若$R,S$具有传递性，则$R^{-1},,R\cap S$具有传递性；

关系闭包

在给定关系添加尽可能少的元素，使关系满足特殊性质，这个过程称为关系闭包；

形式化说，对于定义在非空集合$A$上的关系$R$，若存在定义在$A$上的另一个关系$R’$,使得$R\sube R’$,且满足

• $R’$是自反的/对称的/传递的
• 对于任何自反的/对称的/传递的关系$S$,若$R\sube S$,必有$R’\sube S$;

称$R’$为$R$的自反闭包(reflexive closure)/对称闭包(symmetric closure)/传递闭包(transitive closure),记作$r(R)/s(R)/t(R)$;

闭包运算算法：
$$
r(R)=R\cup I_A\
s(R)=R\cup R^{-1}\
t(R)=\bigcup_{i=1}^{|A|} R^i
$$

等价关系

称定义在非空集合$A$上的关系$R$为等价关系，若$R$具有自反性，对称性和传递性；

给定非空集合$A$,称集合$S={S_1,S_2,\cdots,S_n}$构成集合$A$的一个划分(partition),$S_i(1\le i\le n)$称作划分的类(class),若

• $S_i\sube A,S_i\neq \varnothing,1\le i\le n;$
• $S_i\cap S_j = \varnothing, i\neq j, 1\le i,j\le n;$
• $\bigcup_{i=1}^n S_i=A;$

利用等价关系可以将集合划分成互不相交的子集,也即等价类；

对于定义在集合$A$上的等价关系$R$,对$\forall x\in A$,称集合
$$
[x]_R={y\mid y \in A \ \wedge <x,y>\in R}
$$
是$x$生成的关于$R$的等价类(equivalence)，$x$为该类的代表元(generator);

简单来说，在等价关系中，所有与$x$有关系的元素处于同一个等价类中，不难观察以下结论成立

• 对$\forall x\in A,[x]_R\neq \varnothing;$
• 对$\forall x,y\in A$, 若$y\in [x]_R$，则$[x]_R=[y]_R$;若$y\notin [x]_R$,则$[x]_R\cap [y]_R=\varnothing$;
• $\bigcup_{x\in A}[x]_R = A$;

进一步定义集合$A$关于等价关系$R$的商集$A/R$
$$
A/R = {[x]_R\mid x\in A}
$$
商集算法如下：

1. 若$A$非空，选取$a\in A$,计算$[a]_R$并加入到$A/R$中；
2. 若$[a]_R\neq A$，更新$A\leftarrow A-[a]_R$,回到1；

显然商集是对$A$的等价划分，由划分也可以生成一种等价关系，如下：

定集合$A$的一个划分$π={S_1，S_2,\cdots, S_n}$，则由该划分确定的关系
$$
R=\bigcup_{i=1}^n (S_i\times S_i)
$$
是$A$上的等价关系,称该关系$ R$为由划分$π$所导出的等价关系;

序关系

称定义在集合$A$上的关系$R$为拟序关系，如果$R$是反自反的，反对称的和传递的，记作小于$<$;

序偶$<A,< >$称为拟序集，改记$<a,b>\in <$为$a< b$,其逆关系大于为$> $也是拟序关系；

称定义在集合$A$上的关系$R$为偏序关系，如果$R$是自反的，反对称的和传递的，记作小于等于$\le$;

序偶$<A,\le>$称为偏序集，改记$<a,b>\in \le$为$a\le b$,其逆关系大于等于为$\ge $也是偏序关系；

规定偏序关系对应的哈斯图(Hasse diagram)如下：

• 用小圆圈或点表示$ A$中的元素，省掉关系图中所有的自环;
• 对于$\forall x，y∈A$，若$x≤y$且$x≠y$，则将$x$画在$y$的下方，可省掉关系图中所有边的箭头;
• 对于$\forall x，y∈A$，若$x≤y$且$x≠y$，且$x$与$y$之间不存在$z\in A$，使得$x≤z，z≤y$，则$x$与$y$之 间用一条线相连，否则无线相连;

$<A,\le>$是偏序集，$B$是$ A$的任何一个子集，若存在元素$b∈B$，使得

• 对$\forall x\in B$，都有$x≤b$，则称$b$为$B$的最大元;
• 对$\forall x\in B$，都有$x≥b$，则称$b$为$B$的最小元;
• 对$\forall x\in B$，满足 $x≥b\Rightarrow x=b$，则称$b$为$B$的极大元;
• 对$\forall x\in B$，满足$x≤b\Rightarrow x=b$，则称$b$为$B$的极小元.

若存在元素$a\in A$，使得

• 对$\forall x\in B$，都有$x≤a$，则称$a$为$B$的上界（upper bound）;
• 对$\forall x\in B$，都有$x≥a$，则称$a$为$B$的下界（lower bound）;
• 设元素$a’\in A$是$B$的一个上界，对$B$的任何一个上界$a\in A$，若均有$a≥a’$，则称$a’$为$B$的上确界.记为 $a’=\sup B$;
• 设元素$a’\in A$是$B$的一个下界，对$B$的任何一个下界$a\in A$，若均有$a\ge a’$，则称$a’$为$B$的下确界.记为 $a’=\inf B$;

进一步有以下结论：

$<A,\le>$是偏序集，$B$是$ A$的任何一个子集

• 若最大元$b$存在，则同时是极大元，上界，上确界；若$A$中的一个上界$a\in B$，则$a$是$B$的最大元；
• 若最小元$b$存在，则同时是极小元，下界，下确界；若$A$中的一个下界$a\in B$，则$a$是$B$的最小元；

对于有限子集$B$,最大元/最小元若存在，则一定唯一，且是唯一极大元/极小元；若上确界/下确界存在，则上确界/下确界唯一；

对偏序关系$<A,\le>$来说，若$\forall x,y\in A$，总有$x\le y$或$y\le x$其一成立，则$\le $为全序关系/线序(linear order)；

$<A,\le>$为全序集，其哈斯图表现为一条线；

对偏序关系$<A,\le>$来说，若$A$中任意非空子集均有最小元，则$\le$为良序关系(well order)；

$<A,\le>$为良序集，良序关系一定是偏序关系，反之则不然，良序关系一定是全序关系，反之则不然；

函数

称关系$f$为集合$A$到集合$B$的函数/映射(function/mapping)，记作$f:A\to B$,若对于每个$x\in A$,存在唯一的$y\in B$, 使得$<x,y>\in f$;

• 定义域${\rm dom}f=A$;
• 值域${\rm ran}f = B$;
• $<x,y>\in f$改记为$y=f(x)$,自变量为$x$，函数值为$y$;

即任意可能的输入集合$A$对应输出集合$B$；

称$f$是从$A$到$B$的单射(injection),若对于$\forall x_1,x_2\in A$,均有$f(x_1)\neq f(x_2)$;

称$f$是从$A$到$B$的满射(surjection)，若${\rm ran}f=B$,即对$\forall y\in B$,$\exist x\in A,s.t.y = f(x)$；

称$f$是从$A$到$B$的双射(bijection)，若$f$既是单射又是满射；

当双射$f$定义在$A\to A$上时，称$f$是集合$A$上的变换(transform)；

若函数$f:A\to A\ s.t. \forall x\in A,f(x)=x$,称$f$是$A$上的恒等函数$\boldsymbol I_A$;

若函数$f:A\to B\ s.t.\exist b\in B,\forall x\in A,f(x)=b$,称$f$是$A$上的常值函数；

若定义$A$为全集$U={u_1,u_2,\cdots, u_n}$的一个子集，则子集$A$的特征函数定义为
$$
f_A(u_i)=\begin{cases}
1&,u_i\in A;\
0&,u_i\notin A.
\end{cases}
$$
若变换$\sigma:A\to A$定义在有限集合上，则称$\sigma$为$A$上的置换/排列(permutation),$n$称作置换的阶(order),通常如下表示：
$$
\sigma=\left(\begin{array}{c}
a_1&a_2&\cdots&a_n\
\sigma(a_1)&\sigma(a_2)&\cdots&\sigma(a_n)
\end{array}\right)
$$
不同置换个数为$n!$个；

基础数据结构与算法

第一章：线性结构

顺序表

• 对于一个顺序表，我们可以不需要因为结点逻辑关系额外增加开销，逻辑结构和存储结构一致；
• 做到$O(1)$随机存取访问与修改，但是只能在$O(n)$实现删除与插入，平均移动约一半的元素，并且预先分配空间过小容易溢出，过大容易浪费；

顺序表模板类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163

#pragma once
template<typename T> class SeqList{//动态顺序表,希望能实现类似vector容器
private:
    #define _OVERFLOW 3
    #define _ERROR -1
    #define _OUT_OF_RANGE -1
    #define _MAXSIZE 1024
    #define _FAIL -1
    T *elem;
    int _size=0;
    int _capacity=0;

public:
    SeqList(){//无参数构造
        elem=new T[_MAXSIZE];
        if(!elem){
            std::cout<<"OVERFLOW"<<std::endl;
            exit(_OVERFLOW);
        }
        _size=0;
        _capacity=_MAXSIZE;
    }

    ~SeqList(){//销毁
        delete[] elem;
        elem=nullptr;//避免悬垂指针
    }

    const void clear(){//清空，保持头部指针和容量不变
        _size=0;
        _capacity=_MAXSIZE;
    }

    int size()const{//返回容器的大小
        return _size;
    }

    bool empty()const{
        return _size==0;
    }

    const T& at(int index)const{
        if(index<0||index>_size){
            std::cout<<"ERROR:ArrayIndexOutOfBoundsException"<<std::endl;
            exit(_OUT_OF_RANGE);
        }
        return *(elem+index);
    }
    const T* begin()const{//第一个元素的指针，并没有整个iterator
        return elem;
    }
    const T* end()const{//末尾元素的下一个位置
        return elem+_size;
    }
    const T& front()const{//头部元素的引用
        return *elem;
    }
    const T& back()const{//末尾元素的引用
        return *(elem+_size-1);
    }
    T& operator[] (int index){//重载[]访问与修改元素，不给出越界提示
        return *(elem+index);
    }
    const T& operator[](int index)const{//允许对const对象的访问
        return *(elem+index);
    }
    const T* find(const T* beg,const T* end,const T& value)const{
        for(const T* tmp=beg;tmp!=end;tmp++){
            if(*tmp==value) return tmp;
        }
        return this->end();//找不到返回表尾，默认分支
    }
    int capacity()const{return _capacity;}

    SeqList(const SeqList& x) {//拷贝构造
        _size = x.size();
        _capacity = x.capacity();
        elem = new T[_capacity];
        if(!elem){
            std::cout<<"OVERFLOW"<<std::endl;
            exit(_OVERFLOW);
        }
        for (int i = 0; i < x.size(); i++) {
            elem[i] = x[i];
        }
    }

    bool operator==(const SeqList&r)const{
        if(this->_size!=r._size) return false;//容量不同其他相同应该视为相同的顺序表
        for(int i=0;i<this->_size;i++) {
            if(this->elem[i]!=r.elem[i]) return false;
        }
        return true;
    }
    bool operator!=(const SeqList&r)const{
        return !((*this)==r);
    }
    SeqList<T>& operator=(const SeqList<T>& x){
        if(this!=&x){
            delete[] elem;
            _size=x.size();
            _capacity=x.capacity();
            elem=new T[_capacity];
            if(!elem){
                std::cout<<"OVERFLOW"<<std::endl;
                (_OVERFLOW);
            }
            for(int i=0;i<x.size();i++){
                elem[i]=x[i];
            }
            return *this;
        }
    }

    //在顺序表L中第i个位置数据元素之前插入数据元素e，可以实现头尾插入 
    void insert(int pos,T value){
        if(_size==_capacity) {//size变化可能会触发扩容机制
            _capacity*=2;
            T* upd_elem=new T[_capacity];
            if(!elem){
                std::cout<<"OVERFLOW"<<std::endl;
                exit(_OVERFLOW);
            }
            for(int i=0;i<_size;i++){
                upd_elem[i]=elem[i];
            }
            delete elem;
            elem=upd_elem;
        }
        if(pos>=_MAXSIZE) {
            std::cout<<"OVERFLOW"<<std::endl;
            exit(_OVERFLOW);
        }
        else if(pos<0||pos>_size) {
            std::cout<<"ERROR:ArrayIndexOutOfBoundsException"<<std::endl;
            exit(_OUT_OF_RANGE);
        }
        for(int i=_size;i>pos;i--){
            elem[i]=elem[i-1];
        }//增加数据应该从后面开始移动
        elem[pos]=value;
        _size++;
    }
    void push_back(T& value){
        insert(this->_size,value);
    }
 
    //删除指定位置pos的数据
    void erase(int pos){
        if(pos>=_MAXSIZE) {
            std::cout<<"OVERFLOW"<<std::endl;
            exit(_OVERFLOW);
        }
        else if(pos<0||pos>=_size) {
            std::cout<<"ERROR:ArrayIndexOutOfBoundsException"<<std::endl;
            exit(_OUT_OF_RANGE);
        }
        for(int i=pos;i<_size;i++){
            elem[i]=elem[i+1];
        }
        _size--;
    }
};

单链表

• 对于一个头部带哑结点的单链表，指针必须遍历整个单链表，最坏时间复杂度为$O(N)$，在查找效率上比顺序表更慢；

• 尽管对于单链表的插入与删除操作的复杂度为$O(N)$，但是省去了对元素的移动操作，并且在已知附近结点的情况下只需要修改几个指针就可以完成插入操作，在频繁插入与删除首尾位置，单链表表现出比顺序表更加优越的性能；

• 对于单链表的各个变形都稍微分析优缺点：

  • 不带头部的单链表：在实际实现中，对于结点是否是第一个需要反复判断，特殊处理；并且由于有头部节点的存在，使得空表和只有头结点的表处理起来一样；

  • 循环单链表:

    在最后一个结点指针域存放第一个结点的地址，形成一个环；

    判断遍历是否终止条件改为 p->next==head;

  • 带尾指针的循环单链表

    在合并两个循环单链表的场景可以将复杂度将为$O(1)$;

  • 双向链表：是STL中 std::list容器的底层实现，支持高效寻找前驱的操作，是以时间换空间的策略；

  • 静态链表：喜闻乐见的比赛专用，码量小，静态空间；

  下面给出单链表和双向链表的模板类实现：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176

  #pragma once template<typename T>class ListNode{ private: ListNode<T>* _next; T _data; public: friend class List;//声明友元 ListNode(const T& item,const ListNode<T>& ptr=nullptr){ this->_data=item; this->_next=ptr; } ListNode(const T& item=0) {this->_data=item;this->_next=nullptr;} ~ListNode(){//无需检查next为空 _data=0; delete _next; _next=nullptr; } T& data(){return this->_data;} void data(const T item){this->_data=item;} ListNode<T>* next(){return this->_next;} void next(const ListNode<T>* ptr){this->_next=ptr;} }; //头节点是哑结点(数据域不包含有效信息)、记录长度的单链表实现 template<typename T>class List{ private: ListNode<T>* _head; int _size; #define _INVALID_INDEX -1 #define _FAIL -1 #define _OVERFLOW 3 public: friend class ListNode; List(){ this->_head=new ListNode<T>; _head->data=0; _head->next=nullptr; _size=0; }//无参数构造 ListNode<T>* head()const{return this->_head;} const int size()const{return this->_size;} bool empty()const{return (this->_head)->_next==nullptr;} const T& at(int pos){//查找位置在pos的结点,返回引用 ListNode<T>* tmp=this->_head; int cnt=0; while(tmp){ if(cnt==pos) return tmp->_data; cnt++; tmp=tmp->_next; } std::cout<<"INVALID_INDEX"<<std::endl; exit(_INVALID_INDEX); } T& operator[](int pos){ ListNode<T>* tmp=this->_head; int cnt=0; while(tmp){ if(cnt==pos) return tmp->_data; cnt++; tmp=tmp->_next; } exit(_INVALID_INDEX); } const T& operator[](int pos)const{//查找位置在pos的结点 ListNode<T>* tmp=this->_head; int cnt=0; while(tmp){ if(cnt==pos) return tmp->_data; cnt++; tmp=tmp->_next; } exit(_INVALID_INDEX); } ListNode<T>* at_pos_ptr(int pos){ ListNode<T>* tmp=this->_head; int cnt=0; while(tmp){ if(cnt==pos) return tmp; cnt++; tmp=tmp->_next; } std::cout<<"INVALID_INDEX"<<std::endl; exit(_INVALID_INDEX); } ListNode<T>* find(int value){ ListNode<T>* tmp=_head->_next; while(tmp){ if(tmp->_data==value) return tmp; else tmp=tmp->_next; } if(!tmp) { std::cout<<"FAIL"<<std::endl; exit(_FAIL); } } void insert(int pos,T value){ ListNode<T>* pre=this->at(pos-1);//若pos不合法将退出 ListNode<T>* tmp =new ListNode<T>(value); //参数构造结点实例 tmp->_next=pre->_next; pre->_next=tmp; this->_size++;//头节点记录长度发生变化 }//尽管复杂度为O(n)，但是速度仍然比插入顺序表整体移动元素更快 void erase(int pos){ ListNode<T>* pre=this->at(pos-1); ListNode<T>* now=pre->_next; ListNode<T>* nxt=now->_next; pre->next=nxt; delete now; } List(const List<T>& x){ this->_head=new ListNode<T>; ListNode<T>* tmp=_head->_next; ListNode<T>*tmpx=x._head->_next; while(tmp){ tmp->_data=tmpx._data; tmp->_next=tmpx._next; tmp=tmp->_next; tmpx=tmpx._next; } return *this; };//拷贝构造,不应该连头结点一起拷贝 bool operator==(const List<T>&r)const{ if(this->_size!=r._size) return false; ListNode<T>* local=this->_head; ListNode<T>* out=r._head; while(out!=nullptr){ if(out->data!=local->data)return false; out=out->_next; local=local->_next; } return true; } bool operator!=(const List<T>&r)const{ return !((*this)==r); } const List<T>& operator=(const List<T>& x){ if(this!=&x){ delete _head; _head=new ListNode<T>; ListNode<T>* tmp=_head->_next; ListNode<T>*tmpx=x._head->_next; while(tmp){ tmp->_data=tmpx._data; tmp->_next=tmpx._next; tmp=tmp->_next; tmpx=tmpx._next; } return *this; } } List(T& elem[],int n){ for(int i=n-1;i>=0;i--){ this->insert(1,elem[i]); } } void clear(){ while(_head->_next) erase(1); } ~List(){ this->clear(); delete this->_head; this->_head=nullptr; this->_size=0; } };

​

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

template<typename T>
class Node {
public:
    T data;
    Node<T>* next;
    Node<T>* prev;

    Node(T data = T(0), Node<T>* next = nullptr, Node<T>* prev = nullptr)
        : data(data), next(next), prev(prev) {}
};

template<typename T>
class List {
private:
    Node<T>* head;
    Node<T>* tail;
    int size;

public:
    //default constructor
    List(): head(nullptr), tail(nullptr), size(0){}
    
    //add data to the front of the list
    void push_front(T data) {
        Node<T>* node = new Node<T>(data, head);
        if (head != nullptr)
            head->prev = node;
        head = node;
        if (tail == nullptr)
            tail = head;
        size++;
    }
    
    //add data to the back of the list
    void push_back(T data) {
        Node<T>* node = new Node<T>(data, nullptr, tail);
        if (tail != nullptr)
            tail->next = node;
        tail = node;
        if (head == nullptr)
            head = tail;
        size++;
    }

    //remove data from the front of the list
    void pop_front() {
        if (head == nullptr)
            return;
        Node<T>* node = head;
        head = node->next;
        if (head != nullptr)
            head->prev = nullptr;
        delete node;
        size--;
    }

    //remove data from the back of the list
    void pop_back() {
        if (tail == nullptr)
            return;
        Node<T>* node = tail;
        tail = node->prev;
        if (tail != nullptr)
            tail->next = nullptr;
        delete node;
        size--;
    }

    //return number of the elements in the list
    int length() {
        return this->size;
    }

    //return true if the list is empty, false otherwise
    bool empty() {
        return size == 0;
    }

    //destructor
    ~List() {
        while (head != nullptr) {
            Node<T>* node = head;
            head = node->next;
            delete node;
        }
        tail = nullptr;
        size = 0;
    }
};

顺序栈

实现从略（留坑，期末要复习不完力）；

链式栈

实现从略（留坑，期末要复习不完力）；

队列

实现从略（留坑，期末要复习不完力）；

查找

顺序查找

依次检查顺序表的每一个关键字，空间复杂度为$O(1)$,时间复杂度为$O(N)$；

等概率查找成功的$ASL=\frac{\sum_{i=1}^{n}(n-i+1)}{n}=\frac{n+1}{2}$;

考虑查找失败情况，$ASL=\frac{n+\frac{n+1}{2}}{2}=\frac{3n+1}{4}$;

索引查找

将数据分成两个关键字，对总体分块，对每一个块使用顺序查找；

不考虑查找失败的情况下，假设数据分成$b$块，每块数据有$s$个元素,近似看成$N=sb$；

$ASL=\frac{b+1}{2}+\frac{s+1}{2}=\frac{1}{2}(s+\frac{n}{s})+1=O(\sqrt{n})$;

明显在分$\sqrt{n}$块时算法最优；

哈希查找

为降低查找的时间复杂度，可以考虑建立储存数据与储存地址的哈希函数（映射关系）：假设要将$m$个关键字$K_i$存储到长度为$n$的表中，建立的哈希函数为$H$，$1\le H(K_i)\le n$,一个计算简单的哈希函数很难保证是单射，想要避免哈希冲突很难保证简单好算，下提供几种建立哈希函数的思路：

• 线性哈希：$H(K)=aK+b$;

• 数字分析哈希：

  • 对关键字按照某种规则分解成一组数字（比如按位数），对组内每一个数字哈希，再重新组合得到新的值作为哈希值；
  • 需要关键字有某种规律才好；

• 平方取中：

  • 将关键字平方得到的，取中间几位作为哈希值；
  • 处理比较连续的数据效果比较好，冲突可能性低；

• 折叠哈希：

  • 将关键字拆分成等长的部分，按照某种规则（预处理）加起来得到哈希值；当然可以多次折叠形成多哈；
  • 处理大数据映射到小数据效果较好，对相似数据处理较差；

• 模数哈希：

  • $H(K)=K \ mod\ p$，$p$可以取小于$m$的质数（如果有因子$d$,关键字模$p$的余数都是$d$的倍数，增加了冲突的可能性；
  • 目前用的比较多，可以多重哈希；
  • 可能需要解决自然溢出等哈希冲突的问题；

  1 2 3 4 5

  int myHash(const char* x){ int hashval=0; while(*x!='\0') hashval+=(hashval<<5)+*x-'a'; return hashval; }

哈希冲突处理

开放地址

对于$H(K_0)=K_0 %p=A$,现发生第$i$次冲突$H(K_1)=A$,引入再散列$d_i$，$H(K_1)=(A+d_i)%p$;

• 线性探测再散列：$d_i=1,2,…,p-1$;
• 二次探测再散列：$d_i=1^2,-1^2,2^2,-2^2,…,(p/2)^2,-(p/2)^2$;
• 伪随机探测再散列：$d_i=i\cdot H_i(Key)$;

多哈希

• 设置$n$级哈希函数，由第$i$级哈希函数处理第$i$次哈希函数的地址；

链地址法

• 将冲突记录到同一个线性链表中；

公共溢出法

• 设置HashTable和OverTable；
• OverTable顺序记录每一个溢出的值；

哈希表查找、性能分析

排序

接下来的排序默认为不减序；

直接插入排序

保持左边序列有序，插入当前的数到左边序列合适的位置；

具体来说，假设$a[0]…a[i-1]$有序,依次比较当前数$now=a[i]$与$a[i-1],a[i-2],…a[0]$.假设$a[k]>now$，将$a[k]$后移一位，更新$a[k] \gets now$,否则停止循环；

空间复杂度为$O(1)$，时间复杂度为$O(N^2)$;

适用于数据量较小的、或者几乎已经排好序的数组，此时几乎只需要遍历一遍，时间复杂度接近$O(N)$;

1
2
3
4
5
6
7
8
9
10
11
12

void insert_sort(int *s,int n){//插入排序
    for(int i=1;i<n;i++){
        if(s[i]>=s[i-1]) continue;
        int tmp=s[i];
        for(int j=i-1;s[j]>tmp&&j>=0;j--){
            s[j+1]=s[j];
            s[j]=tmp;
        }
        
    }
}

Shell排序

Shell排序是一种不稳定的排序，平均复杂度为$O(N^{1.25})$,但可以适当地选取序列，使得复杂度升到$O(N^2)$,根据不同间距序列的选取，使得Shell排序有着不同的复杂度表现；

Shell排序可以分成三步：

• 选取一个间距$L$，将原来序列划分为间距为$L$的所有子序列；
• 对每个子序列进行插入排序；
• 减小要选取的间距；

1
2
3
4
5
6
7
8
9
10
11
12
13

void ShellSort(int *s,int n){
    int l=1;
    while(l<n) l=3*l+1;
    while(l>=1){
        for(int i=l;i<n;i++){
            for(int j=i;j>=l&&s[j-l]>s[j];j-=l){
                std::swap(s[j],s[j-l]);
            }
        }
        l/=3;
    }
    return ;
}

冒泡排序

在每一趟冒泡中，比较相邻两个元素，若逆序则交换，（优化）记录每一趟冒泡最后一次交换发生的位置；

冒泡排序是稳定的，但是时间复杂度为$O(N^2)$,不优化之前的总比较次数和交换次数为$\frac{1}{2}N(N-1)$;

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void bubble_sort(int *s,int n){
    int idx=n-1;
    while(idx>0){
        int expos=0;
        for(int i=0;i<idx;i++){
            if(s[i]>s[i+1]){
                std::swap(s[i],s[i+1]);
                expos=i;
            }
        }
        idx=expos;
    }
    retrun ;
}

选择排序

每一趟找到前面无序部分中最大的数，将它交换到后面有序部分的头部；

选择排序是不稳定的，最坏复杂度为$O(N^2)$

1
2
3
4
5
6
7
8
9
10

void selection_sort(int *s,int n){
    for(int i=n;i>1;i--){
        int Maxpos=0;
        for(int j=0;j<i;j++){
            if(s[j]>s[Maxpos]) Maxpos=j;
        }
        std::swap(s[Maxpos],s[i-1]);
    }
    return ;
}

基数排序

第二章：递归与分治

主方法

对$T(N)=aT(N/b)+f(N),N>b$,那么分三类讨论；
$$
T(N) = \begin{cases}\Theta(N^{\log_b a}) & f(N) = O(N^{\log_b a-\epsilon}),\epsilon > 0 \ \Theta(f(N)) & f(N) = \Omega(N^{\log_b a+\epsilon}),\epsilon\ge 0\ \Theta(N^{\log_b a}\log^{k+1} N) & f(N)=\Theta(N^{\log_b a}\log^k N),k\ge 0 \end{cases}
$$
第一种情况表明合并子问题复杂度很低，解决问题主要复杂度来源是解决若干个子问题；

第二种情况表明合并子问题复杂度很高，解决问题主要复杂度来源是合并子问题；

第三种情况是合并和解决子问题比较均衡，递归深度为$logN$;

二分查找

• 表有序，不经常变动且查找频繁，记录按关键字排序

• 维护查找范围的左端点和右端点，每次检查中间的数是否在表中；

• 如果在表中，则查找成功；如果不在，那么按大小缩小到具体要查找左边区间还是右边区间；

使用二分查找关键字如下（找不到返回-1）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

typedef bool(*fun)(int*,int,int) ;
bool judg(int*a,int m,int key){
    return a[m]==key;
}
int Find(int*a,int n,fun judg,int key){
    int l=0;
    int r=n-1;
    while(r>=l){
        int m=l+((r-l)>>1);
        if(judg(a,m,key)) return m;
        if(key<a[m]) r=m-1 ;
        else l=m+1;
    }
    return -1;
}
int main(){
    int n=11;
    int a[11]={2,7,10,12,16,20,26,32,44,56,62};
    int idx=Find(a,n,judg,32);
    std::cout<<idx<<" ";
    return 0;
}

二分查找的性能分析：

假设有序表长度为$n=2^k-1$,二叉判定树高$k=log_2(n+1)$，每个记录查找概率相等，第$i$层有$2^{i-1}$个结点；

平均查找长度为$\frac{1}{n}(\sum_{i=1}^{k}i\cdot2^{i-1})=\frac{n+1}{n}log_2(n+1)-1$;

即复杂度为$O(logN)$

归并排序

• divide：将数组分成均匀两半

• sort：递归解决每个半部分

• merge：把两部分合并起来组成一个新的排序

一个简单的对整数数组归并排序如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

void MergeSort(int*a,int l,int r){
    if(r-l<1) return ;
    if(r-l==1) {
        if(a[l]>a[r]) std::swap(a[l],a[r]);
        return ;
    }

    int m=l+((r-l)>>1);
    MergeSort(a,l,m);
    MergeSort(a,m+1,r);

    int tmp[r-l+1]={0};
    int p=0,pa=l,pb=m+1;
    while(pa<=m&&pb<=r){
        if(a[pa]<a[pb]){
            tmp[p]=a[pa];
            pa++;
            p++;
        }
        else{
            tmp[p]=a[pb];
            pb++;
            p++;
        }
    }
    while(pa<=m) {
         tmp[p]=a[pa];
         p++;
         pa++;
    }
    while(pb<=r) {
         tmp[p]=a[pb];
         p++;
         pb++;
    }
    for(int i=0;i<r-l+1;i++){
        a[l+i]=tmp[i];
    }
    return ;
}

归并排序时一种稳定的算法，可以看到使用$T(n)$来表示排列$n$个数所需要用的比较次数，得到$T(n)=O(nlog\ n)$,因为有地递推关系：

​
$$
T(n)= \begin{cases}
0 & n=1 \
T(n/2)+n & n>1
\end{cases}
$$

快速排序

• 选取基准元素pivot；
• 找到基准元素排序后的位置（实现操作后左边元素均小于它，右边元素均大于它）；
  • 维护左端指针low和右端指针high；
  • high向左扫描，遇到小于pivot元素时停止，交换pivot和该元素；
  • low向右扫描，遇到大于pivot元素停止，交换pivot和该元素；
  • high向右扫描..
  • low向左扫描…
  • …
  • 直到low==high，基准元素到达这个位置，结束；
• 划分成子序列，递归地解决问题；

以下是一个对整数数组进行的快速排序代码；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

 void QuickSort(int *a,int low,int high){
    if(low<high){
        int pivot=a[low];
        int l=low;
        int r=high;
        while(l<r){
            while(l<r&&a[r]>=pivot) r--;
            a[l]=a[r];
            while(l<r&&a[l]<=pivot) l++;
            a[r]=a[l];
        }
        int idx=l;
        a[idx]=pivot;

        QuickSort(a,low,idx-1);
        QuickSort(a,idx+1,high);
    }
}

由于快速排序时一种不稳定的算法，空间平均复杂度为$O(logN)$，最坏复杂度$O(N^2)$;

大数乘法

对于$X=A\cdot2^{n/2}+B,Y=C\cdot2^{n/2}+D,X\cdot Y=AC\cdot2^n-((A-B)(C-D)-AC-BD)\cdot2^{n/2}+BD$;

将大数乘法分解成更小的数，由于移位复杂度是线性的，分治得到复杂度递推式为$T(N)=3T(N/2)+O(N)$;

得到$T(N)=O(3^{log_2N})=O(N^{1.58})$;

由于涉及存储结构和常数优化等问题可能实现还不如常规算法，并且将整数看作多项式利用FFT可以实现$O(NlogN)$解决,这里就不贴代码了；

Straseen矩阵乘法

分形

• Koch曲线
• Mandelbrot集合

Hanota问题

在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。

题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
void move(std::vector<int>&A,std::vector<int>&B){
        if(A.empty())return;
        B.push_back(A.back());
        A.pop_back();
        return ;
}
void Hanota(int n,std::vector<int>&A,std::vector<int>&B,std::vector<int>&C){
    if(n==1) {
        move(A,C);
        return ;
    }
    Hanota(n-1,A,C,B);
    move(A,C);
    Hanota(n-1,B,A,C);
}
void hanota(std::vector<int>& A, std::vector<int>& B, std::vector<int>& C) {
    Hanota(A.size(),A,B,C);
}
};

第三章：树与图

二叉树

• 第$i$层上至多有$2^{i-1}$个结点,至少一个结点;
• 深度为$k$的二叉树至多有$2^k-1$个结点，至少$k$个结点;
• 二叉树边数为$B$,顶点数为$N$,二度顶点数为$n_2$,一度顶点数为$n_1$,叶子数为$n_0$,有如下关系式
  • $B=N-1$
  • $N=n_2+n_1+n_0$
  • $B=2n_2+n_1$
  • $n_2=n_0-1$

满二叉树、完全二叉树

满二叉树：一棵深度为$k$且有$2^k -1$个结点的二叉树;

完全二叉树：深度为$k$的，有$n$个结点的二叉树，当且仅当其每一个结点都与深度为$k$的满二叉树中编号从$1$至$n$的结点一一对应;

• 满二叉树是叶子一个也不少的树，完全二叉树只有最后一层叶子不满，且全部集中在左边，换言之，满二叉树最后一层全是叶子，完全二叉树只有倒数第一层和倒数第二层有叶子；
• 具有$n$个结点的完全二叉树的深度必为$⌊log_2n⌋+1 $;
• 对完全二叉树，若从上至下、从左至右编号，则编号为$i$ 的结点，其左孩子编号必为$2i$，其右孩子编号必为$2i+1$；其双亲的编号必为$⌊i/2⌋$;

二叉树的存储

顺序存储

结点间关系蕴含在其存储位置中，浪费空间，适于存满二叉树和完全二叉树；

链式存储

• 由数据域、左指针域、右指针域构成；

遍历

三种方式：先序遍历，中序遍历，后序遍历；

时间复杂度为$O(N)$,空间复杂度为$O(N)$;

访问路径是相同的，只是访问结点的时机不同：

第1次经过时访问＝先序遍历

第2次经过时访问＝中序遍历

第3次经过时访问＝后序遍历

重要结论：

由二叉树的前序序列+中序序列，或由其后序序列+中序序列均能唯一地确定一棵二叉树，

但由前序序列+后序序列却不一定能唯一地确定一棵二叉树。

树、二叉树、森林相互转换

• 树$\to$二叉树

​ 加线：将兄弟结点用线相连

​ 抹线：保留双亲与最左边孩子的连线，去掉双亲和其他孩子的连线

​ 旋转：将经过加线和去线以后的结果，进行旋转处理得到转换后的二叉树

​ 树转换成的二叉树，根结点的右子树一定为空

​ 注意，就算是二叉树，通过这种方式转化，结构也可能发生变化；

​

• 二叉树$\to$树

​ 加线：将结点和其左孩子结点的右孩子以及右孩子的右孩子加线相连

​ 抹线：去掉结点和右孩子的连线

​ 旋转：将加线、去线后的结果，进行旋转处理，就得到转换后的树

​

• 森林$\to$二叉树

​ 将每棵树分别转换成二叉树,将每棵树的根结点用线相连

​ 以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结 构;

​

• 二叉树$\to$森林

​ 抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全 部抹掉，使之变成孤立的二叉树

​ 还原：将孤立的二叉树还原成树;

​

二叉树模板类

以下是一个简单的二叉树模板类（未测试）；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

#include <iostream>
#include <queue>
#include <map>
#include <functional>
template<typename T>class BTNode{
private:
    T data;
    BTNode<T>* l;
    BTNode<T>* r;
    friend class BT;
public:
    BTNode(int val=0,BTNode<T>* a=nullptr,BTNode<T>* b=nullptr)
    :data(val),l(a),r(b){};

    ~BTNode(){
        delete l;
        delete r;
    }

    T data() {return this->data;}
    T leftson(){return this->l;}
    T rightson(){return this->r;}

};
template<typename T>class BT{
private:
    BTNode<T>* root;
public:
    BT(BTNode<T>* x=nullptr):root(x){};

    DLR(T*out){
        if(!this->root) return ;
        *out++=root.data();
        root->l.DLR(out);
        root->r.DLR(out);
    }
    LDR(T*out){
        if(!this->root) return ;
        root->l.LDR(out);
        *out++=root.data();
        root->r.LDR(out);
    }
    LRD(T*out){
        if(!this->root)return ;
        root->l.LRD(out);
        root->r.LRD(out);
        *out++=root.data();
    }

    LevalTraval(T*out){
        std::queue<BTNode<T>* > q;
        BTNode<T>* now=this->root;
        q.push_back(now);
        while(!now) {
            *out++=now->data();
            q.pop_front();
            if(now->l) q.push_back(now->l);
            if(now->r) q.push_back(now->r);
        }
    } 
    build(int n,T* pre,T* in){
        std::map<int,T> f;
        for(int i=0;i<n;i++) f[in[i]]=i;

        std::function<void(std::map<int,T>,T*,T*,int,int,int,int)>
        build_tmp=[](std::map<int,T>f,T *pre,T* in,int l,int r,int x,int y){
            BTNode* now=new BTNode<T>(pre[l]);
            this=BT(now);
            int m=f[pre[l]];
            if(m!=x) now->l.build_tmp(f,pre,in,l+1,l+m-x,x,m-1);
            if(m!=y) now->r.build_tmp(f,pre,in,r-y+m+1,r,m+1,y);
        };
        build_tmp(f,pre,in,0,n-1,0,n-1);
    }

    int leavesNumber(){
        if(!this) return 0;
        if(!root->l&&!root->r) return 1;
        return root->l->leavesNumber()+root->r->leavesNumber();
    }

    int depth(){
        if(!this)return 0;
        if(!root->l&&!root->r) return 1;
        return 1+std::max(root->l->depth(),root->r->depth());
    }

    
};

树、森林的遍历

二叉排序树BST

• 若其左子树非空，则左子树上所有结点的值均小于根结点的值；

• 若其右子树非空，则右子树上所有结点的值均大于等于根结点的值；

• 其左右子树本身又各是一棵二叉排序树；

• 中序遍历二叉排序树后，得到一个关键字的递增有序序列

查找

若二叉排序树为空，则查找失败，返回空指针；

若查找的关键字等于根结点，成功，返回根结点地址；否则

• 若小于根结点，查其左子树

• 若大于根结点，查其右子树

平均查找性能：最好$O(logN)$,最坏$O(N)$;

插入

（插入的元素一定在叶结点上）

若二叉排序树为空，则插入结点应为根结点；

否则，继续在其左、右子树上查找

• 树中已有，不再插入

• 否则，查找直至某个结点的左子树或右子树为空为止，则插入结点应为该结点的左孩子或右孩子

建树

从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树；

删除

• 删除叶结点：只需将其双亲结点指向它的指针清零，再释放它即可。

• 被删结点缺右子树：可以拿它的左孩子结点顶替它的位置，再释放它。

• 被删结点缺左子树：可以拿它的右孩子结点顶替它的位置，再释放它。

• 被删结点左、右子树都存在：

  • 可以在它的右子树中寻找中序下的第一个结点(后继填充法),
  • 或是在它的左子树中寻找中序下的最后一个结点(前驱填充法)，
  • 用它的值填补到被删结点中，再来处理这个结点的删除问题。

平衡二叉树AVL

对所有结点，$|\text{左、右子树深度之差(平衡因子)}|≤ 1$

对于一个二叉平衡排序树，无论是删除结点还是插入结点，先当作一棵普通的二叉排序树处理，再进行关键的平衡性调整（下面四张图至关重要）；

• 找到最小不平衡子树$T$；
• 确定$T$根节点到最远叶结点这条路径上前三个结点$R>D>L$(排序是指关键字大小)；
• 按照下图旋转（四种可能情况）

​

实现从略（留坑，期末要复习不完力）；

红黑树RBT

特点：利用对树中的结点 “红黑着色”的要求，降低了平衡性的条件，达到局部平衡，有着良好的最坏情况运行时间，它可以在$O(logN)$时间内做查找，插入和删除，这里的N是树中元素的数目;

实现从略（留坑，期末要复习不完力）；

最优二叉树HuffmanTre

• 根据给定的n个权值{w1,w2,……wn}，构造n棵只有根结点的二叉树。

• 在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和。

• 在森林中删除这两棵树，同时将新得到的二叉树加入森林中。

• 重复上述两步，直到只含一棵树为止，这棵树即霍夫曼树。

实现从略（留坑，期末要复习不完力）；

性质：一棵有$N$个叶子结点的Huffman树有 $2N-1$个结点

图的存储

• 邻接矩阵

  邻接矩阵AdjMartrix[n][n],其中AdjMartrix[u][v]表示边$u \to v$的信息（头，尾，权重），空间复杂度为$O(N^2)$，适合对稠密图存储

  1 2 3 4 5 6 7 8 9

  int vertex[_MAXSIZE];//顶点，一维数组 class edge{//边 public: int head; int to; int weight; char *info; }; edge AdjMartrix[_MAXSIZE][_MAXSIZE];//邻接矩阵

• 邻接表

  由顶点表、边表和基本信息组成（点数，边数）组成，其中边表记录头结点、边权和头结点指向的下一条边；

  顶点表记录想要访问的头结点以及顶点信息；

  优点：空间效率高，容易寻找顶点的邻接点；

  缺点：判断两顶点间是否有边，需搜索两结点对应的单链表，没有邻接矩阵方便

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

  class AdjNode{ public: int adjvex; AdjNode *next; int weight; }; class AdjHead{ public: int adjvex; AdjNode * next; int len; }; class AdjList{//邻接表 public: AdjHead head[_MAXSIZE]; int vernum; int edgenum; };

• 十字链表

  将邻接表和逆邻接表拼在一起，查询更加方便；

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

  class edge_{ public: int head; int to; int weight; edge* hlink;//下一条入边 edge* tlink;//下一条出边 }; class vertex_{ public: int vertex; edge* firstin; edge* firstout; }; vertex_ crossLink[_MAXSIZE];//十字链表 class _edge_{ public: bool vis; int head; int to; _edge_* hlink; _edge_* tlink; }; class _vertex_{ public: int first; _edge_* next; }; _vertex_ node_[_MAXSIZE];//临界多重表

深度优先搜索DFS

一种用于遍历或搜索树或图的算法。所谓深度优先，就是说每次都尝试向更深的节点走；

时间复杂度为$O(|V|+|E|)$;

1
2
3
4
5
6
7
8
9
10
11
12

bool vis[_MAXSIZE];
void DFS(AdjList gra,int now){//基于邻接表的深搜
    vis[now]=true;
    AdjHead Now= gra.head[now];
    for(AdjNode* Nxt=Now.next;Nxt;Nxt=Nxt->next){
        int nxt=Nxt->adjvex;
        if(!vis[nxt]){
            DFS(gra,nxt);
        }
    }
    return ;
}

广度优先搜索BFS

所谓宽度优先。就是每次都尝试访问同一层的节点。 如果同一层都访问完了，再访问下一层。

这样做的结果是，BFS 算法找到的路径是从起点开始的最短 合法路径。换言之，这条路径所包含的边数最小。

在 BFS 结束时，每个节点都是通过从起点到该点的最短路径访问的。

时间复杂度为$O(|V|+|E|)$;

1
2
3
4
5
6
7
8
9
10

void BFS(AdjList gra,int now){
    std::queue<int> q;
    q.push(now);
    AdjHead Now= gra.head[now];
    while(!q.empty()){
        vis[q.front()]=true;
        q.pop();
        for(AdjNode* Nxt=Now.next;Nxt;Nxt=Nxt->next) q.push(Nxt->adjvex);
    }
}

有向无环图DAG，拓扑排序

经典的Kahn算法

• 所有入度为0的顶点进队列

• 栈非空时，输出栈顶元素并退栈；在邻接表中查找它的直接后继$x$，把$x$的入度减1；若$x$的入度为0则进栈

• 重复上述操作直至栈空为止；

• 若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕

时间复杂度：$O(|V|+|E|)$空间复杂度：$O(|V|)$

求字典序最大/最小的拓扑排序:将 Kahn 算法中的队列替换成最大堆/最小堆实现的优先队列即可，此时总的时间复杂度为$O(E+V \log{V})$;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

bool TopoSort(int*out,int* indegree,std::vector<int> Adj[],int n){
    //out为输出序列,indegree记录每个结点的入度,Adj记录每个结点的出邻点,1~n为结点
    //由于直接传图可能会改变图的结构,所以传这些可能更改的信息即可
    std::queue<int> q;
    for(int i=1;i<n;i++) if(!indegree[i]) q.push(i);
    int cnt=0;
    while(!q.empty()){
        int now=q.front();
        *out++=now;
        cnt++;
        q.pop();
        for(int j=0;j<Adj[now].size();j++) 
            if(!--indegree[Adj[now][j]]) 
                q.push(Adj[now][j]);
    }
    return cnt==n;//判断是否是DAG,拓扑序列是out
}

最小生成树

Prim算法

• 将顶点u0看作G的极小连通子图T；

• 选择一个端点u在T上，另一个端点v不在T上的权重最小的边(u,v)；将边(u,v)和顶点v添加到T上；

• 重复步骤2，直到T包含n个顶点；

Kruskal算法

• 删除图G=(V,E)的所有边，得到只有n个顶点、没有边的非连通图T=(V,Æ)，每个顶点自成一个连通分量

• 将E中所有的边按照权重从小到大排序；

• 按照权重从小到大的顺序考察E中每一条边，如果它的两个端点落在不同的连通分量上，则将其加入T中；

• 重复步骤2，直到所有顶点都在同一连通分量上

最短路径

Dijkstra算法

• 对于每个点v均维护一个「当前最短距离数组」dis[v]以及「访问数组」vis[v]，首先将

  dis[u]初始化为0，将其他点的距离初始化为无穷，并将所有点初始化为未访问的。记

  e[i]:u-v的边权e[i].w。然后进行以下步骤：

  1. 从所有未访问的点中，找出当前距离最小的,并将其标记为已访问的;
  2. 调整所有出边连接但尚未访问的点，转移状态；
  3. 重复1和2步骤，直到所有点都已访问，因为所有边权权值均为正的，所以用之后访问的结点是不能更新已经访问过的结点的（因为贪婪算法下若可以更新的话必定在还在之前就已经更新过了）；
  4. 可以用pre[y]=i维护最短的路径（点边关系）；

Floyd算法

考虑对每个$k$值，「$i$到$j$ 的路径只允许经过标号不大于$k$的点」中最短路径长度$dis[i][j]$，明显$k=n$是我们所求问题的答案；

• 初始$k=0$，所欲值都是正无穷；

• 递归的说，对于已有的$k-1 $允许的最短路径，新的最短路径要么经过$k$,要么维持不变；

• 状态转移方程为
  $$
  dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]),for\ all\ (i,j)s
  $$

• 时间复杂度为$O(|V|^3)$;

第四章：线性规划

字典树(Trie)

字典树用边来代表字母，而从根结点到树上某一结点的路径就代表了一个字符串。

字典树可以高效处理一类字符串、异或最大值以及数集维护问题；

以下是一个Trie树模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

# include <iostream>
# include <string>
# include <vector>

class Trie {
public:
    # define ALPHABET_SIZE 26
    # define MAX_CAPACITY 100000

    int cnt; // 维护当前结点标号，头结点标号为0
    int next[MAX_CAPACITY][ALPHABET_SIZE];
    bool isEndOfWord[MAX_CAPACITY];  // 标记某结点结尾的字符串是否存在

    void insert(std::string&s) {
        // TODO: 插入字符串s到Trie树中
        int n = s.length();
        int p = 0;
        for(int i = 0; i < n; i++) {
            int index = s[i] - 'a';
            if(next[p][index] == 0) next[p][index] = ++cnt;
            p = next[p][index];
        }
        isEndOfWord[p] = true;  // 每次插入完成时在这个字符串所代表的节点处打上标记
    }

    Trie(std::vector<std::string>&words) {
        // TODO: 构建Trie树
        for(auto &word : words) insert(word);
    }
    bool find(std::string&s) {
        // TODO: 查询字符串s是否在Trie树中
        int n = s.length();
        int p = 0;
        for(int i = 0; i < n; i++) {
            int index = s[i] - 'a';
            if(next[p][index] == 0) return false;
            p = next[p][index];
        }
        return isEndOfWord[p];
    }
};

注意字符串最好还是传递引用，在字符串I/O开销很大时往往会造成大量的不必要的复制，可能有内存超限的隐患；

B Tree

B树的应用场景：读写磁盘

我们知道，磁盘由于有机械运动部分，导致其读写速度比主存慢许多，而读写磁盘的主要开销来自于磁盘机械臂的寻道；

为了摊还寻道时间，需要设计一种高效的数据结构，满足如下要求，以减少磁盘的读取次数：

• 批量读写：磁盘一次IO操作存取大量的数据项
• 有限载入：磁盘比内存大得多，不能将磁盘的所有数据载入内存；
• 缓存：根据局部性原理，最近访问过的数据应该留在内存一段时间，并且用高效的方式组织起来；
• 任务：将所需页面从磁盘复制到内存，将修改的页面写回磁盘；
• 数据结构的指针应该保存在内存中；

因此以下是个人理解：

• B树往往作为索引结构而存在，通过索引找到在磁盘中存储在磁盘中的数据项(关键字)；
• B树的每个结点被设计地可能很大，当读写磁盘时按照结点为单位，批量地将大量关键字读写，进行内存和磁盘地交换，即IO操作；
• B树的根节点存在于内存，而不是磁盘的存储结构；
• 换句话说，B树是一个维护内存和磁盘交换数据信息的数据结构，其设计作用为降低IO次数
• 在操作系统实现一次IO操作中中，B树算法应该先于IO调度算法：OS启动相关的管理进程，在B树中找到需要和磁盘交换的数据项，读写磁盘之前，IO调度算法再适当优化顺序，进一步减少寻道时间；

定义

一个结点关键字数目在$[d,m-1]$的B树是具有以下性质的有根树(对于某些$d$阶B树和$m$阶B树说法对应关系，$m=2d+1$)：

• 每个结点至多有$m$个子结点，即$m$个子树,$m-1$个关键字；
• 每个非根结点至少有$d+1$个子节点，即$d+1$个子树，$d$个关键字;
• 根节点至少有$1$个关键字；
• 关键字在结点内部升序排列；

其中B树的最小度数为$d$;特别的$d=2$时每个结点有$2,3,4$个关键字，也称$2-3-4$树，是最简单的B树，可以转化成RB树；

满结点：有$m$个子树的结点；

B树的高度
$$
h\le \log_d \frac{N+1}{2}
$$
而且可以注意到，B树的叶子结点均在最高一层；

下图是一个合法的B树，以下均按照该树举例；

操作

新建

B树初始化指创建一个空的根结点，并为新节点分配一个磁盘页；

对于一个$d$阶B树而言，其结点应该维护如下字段

• 当前关键字个数n;
• 关键字数组keys;
• 子节点数组child;
• 是否是叶子isLeaf;

类似于普通的树，也应该有初始化根，搜索，插入，分裂，删除，合并的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

template<typename T>
class BTree {
private:
    int d;
    struct Node {
        std::vector<T> keys;  
        std::vector<Node*> child;
        bool isLeaf;         
        int n;     

        Node(bool leaf = true) : isLeaf(leaf), n(0) {}
    };
    Node* root; 
    
    void insertNonFull(Node* x, const T& k) ;
    void splitChild(Node* x, int i);
    Node* search(Node* x, const T& k);
    void remove(Node* x, const T& k);
    void merge(Node* x, int i);
    void fill(Node* x, int i) ;
    void borrowFromPrev(Node* x, int i);
    void borrowFromNext(Node* x, int i);
public:
    BTree(int _d);
    bool search(const T& k);
    void insert(const T& k);
    void remove(const T& k);
};

BTree::BTree(int _d):d(_d){
    this->root = new BTree::Node();
}

插入+分裂

插入关键字，先查找关键字是否存在，若不存在，在叶子结点插入；

• 插入非满结点：直接找到关键字对应的位置，在该非满结点添加关键字，插入后仍是一个合法的B树结点；
• 插入满结点：必须需要按中间关键字分裂成两个结点，一个满结点上有$m-1$个关键字，插入一个关键字后，需要将中间关键字上提到父节点，左右两边各分出两个含有$d$个关键字的结点

按照顺序3，14，7，1，8，5，11，17，13，6，23，12，20，26，4，16，18，24，25，19插入，建立一个2阶B树；

过程如下：

搜索

搜索B树是二叉搜索的直接推广，从根节点开始，搜索关键字$k$:

在一个结点中的key（关键字）查找可用顺序查找或者二分查找；

删除+合并

1. 如果是叶子结点，直接删除key；

   非叶子结点，删除之后，将右子树最左的叶结点的key上移，取代已删除的key；

2. 叶结点key数量>=d，则结束；

   若叶结点中的key小于d个，则观察兄弟结点中是否有>d个key的结点

3. 是，则向兄弟结点借key，并保持两个结点的keys平均分配至两个节点中

   否，则该结点与一个兄弟结点合并

上述B树按顺序删除8,20,18,5

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246

template<typename T>
class BTree {
private:
    // B树的最小度数d
    int d;
    
    struct Node {
        std::vector<T> keys;        // 关键字数组
        std::vector<Node*> child;   // 子节点指针数组 
        bool isLeaf;                // 是否为叶节点
        int n;                      // 当前关键字个数

        Node(bool leaf = true) : isLeaf(leaf), n(0) {}
    };

    Node* root;  // 根节点指针

    // 在非满节点x中插入关键字k
    void insertNonFull(Node* x, const T& k) {
        int i = x->n - 1;
        
        if(x->isLeaf) {
            // 在叶节点中插入
            while(i >= 0 && x->keys[i] > k) {
                x->keys[i + 1] = x->keys[i];
                i--;
            }
            x->keys[i + 1] = k;
            x->n++;
        } else {
            // 在内部节点中找到合适的子节点
            while(i >= 0 && x->keys[i] > k) i--;
            i++;
            
            if(x->child[i]->n == 2 * d - 1) {
                splitChild(x, i);
                if(k > x->keys[i]) i++;
            }
            insertNonFull(x->child[i], k);
        }
    }

    // 分裂节点
    void splitChild(Node* x, int i) {
        Node* y = x->child[i];
        Node* z = new Node(y->isLeaf);
        
        z->n = d - 1;
        
        // 将y的后半部分关键字复制到z
        for(int j = 0; j < d - 1; j++) {
            z->keys.push_back(y->keys[j + d]);
        }
        
        // 如果y不是叶节点，复制相应的子节点
        if(!y->isLeaf) {
            for(int j = 0; j < d; j++) {
                z->child.push_back(y->child[j + d]);
            }
        }
        
        y->n = d - 1;
        
        // 将新节点插入到x的子节点中
        x->child.insert(x->child.begin() + i + 1, z);
        x->keys.insert(x->keys.begin() + i, y->keys[d - 1]);
        x->n++;
    }

    // 在节点中查找关键字
    Node* search(Node* x, const T& k) {
        int i = 0;
        while(i < x->n && k > x->keys[i]) i++;
        
        if(i < x->n && k == x->keys[i]) return x;
        
        if(x->isLeaf) return nullptr;
        
        return search(x->child[i], k);
    }

    // 删除关键字
    void remove(Node* x, const T& k) {
        int i = 0;
        while(i < x->n && k > x->keys[i]) i++;

        if(i < x->n && k == x->keys[i]) {
            if(x->isLeaf) {
                // 从叶节点直接删除
                x->keys.erase(x->keys.begin() + i);
                x->n--;
            } else {
                // 从内部节点删除
                Node* pred = x->child[i];
                if(pred->n >= d) {
                    // 用前驱替换
                    T pred_key = pred->keys[pred->n - 1];
                    x->keys[i] = pred_key;
                    remove(pred, pred_key);
                } else {
                    Node* succ = x->child[i + 1];
                    if(succ->n >= d) {
                        // 用后继替换
                        T succ_key = succ->keys[0];
                        x->keys[i] = succ_key;
                        remove(succ, succ_key);
                    } else {
                        // 合并节点
                        merge(x, i);
                        remove(pred, k);
                    }
                }
            }
        } else {
            if(x->isLeaf) return;
            
            bool flag = (i == x->n);
            if(x->child[i]->n < d) {
                fill(x, i);
            }
            
            if(flag && i > x->n)
                remove(x->child[i - 1], k);
            else
                remove(x->child[i], k);
        }
    }

    // 合并节点
    void merge(Node* x, int i) {
        Node* child = x->child[i];
        Node* sibling = x->child[i + 1];
        
        child->keys.push_back(x->keys[i]);
        
        for(int j = 0; j < sibling->n; j++) {
            child->keys.push_back(sibling->keys[j]);
        }
        
        if(!child->isLeaf) {
            for(int j = 0; j <= sibling->n; j++) {
                child->child.push_back(sibling->child[j]);
            }
        }
        
        x->keys.erase(x->keys.begin() + i);
        x->child.erase(x->child.begin() + i + 1);
        x->n--;
        
        child->n = child->keys.size();
        delete sibling;
    }

    // 填充节点
    void fill(Node* x, int i) {
        if(i != 0 && x->child[i - 1]->n >= d) {
            borrowFromPrev(x, i);
        } else if(i != x->n && x->child[i + 1]->n >= d) {
            borrowFromNext(x, i);
        } else {
            if(i != x->n)
                merge(x, i);
            else
                merge(x, i - 1);
        }
    }

    // 从前一个兄弟节点借关键字
    void borrowFromPrev(Node* x, int i) {
        Node* child = x->child[i];
        Node* sibling = x->child[i - 1];
        
        child->keys.insert(child->keys.begin(), x->keys[i - 1]);
        
        if(!child->isLeaf) {
            child->child.insert(child->child.begin(), sibling->child[sibling->n]);
        }
        
        x->keys[i - 1] = sibling->keys[sibling->n - 1];
        
        child->n++;
        sibling->n--;
    }

    // 从后一个兄弟节点借关键字
    void borrowFromNext(Node* x, int i) {
        Node* child = x->child[i];
        Node* sibling = x->child[i + 1];
        
        child->keys.push_back(x->keys[i]);
        
        if(!child->isLeaf) {
            child->child.push_back(sibling->child[0]);
        }
        
        x->keys[i] = sibling->keys[0];
        
        sibling->keys.erase(sibling->keys.begin());
        
        if(!sibling->isLeaf) {
            sibling->child.erase(sibling->child.begin());
        }
        
        child->n++;
        sibling->n--;
    }

public:
    BTree(int _d) : d(_d) {
        root = new Node();
    }

    // 查找关键字
    bool search(const T& k) {
        return search(root, k) != nullptr;
    }

    // 插入关键字
    void insert(const T& k) {
        if(root->n == 2 * d - 1) {
            Node* s = new Node(false);
            s->child.push_back(root);
            root = s;
            splitChild(s, 0);
            insertNonFull(s, k);
        } else {
            insertNonFull(root, k);
        }
    }

    // 删除关键字
    void remove(const T& k) {
        if(!root) return;
        
        remove(root, k);
        
        if(root->n == 0) {
            Node* tmp = root;
            if(root->isLeaf)
                root = nullptr;
            else
                root = root->child[0];
            delete tmp;
        }
    }
};

评价

• B树的查找性能逼近二分查找；
• 改变B树结构（插入与删除操作）不需要移动大段的内存数据

基本概念

常见的数据库产品有：关系型数据库MySQL，非关系型mongoDB，时序型InfluxDB,图型Neo4j；

这些数据库需要解决的共性问题如下：

1. 数据模型、规范化理论：组织数据
2. 数据定义和操作语言：存取数据
3. 安全性控制：用户的操作数据的权限
4. 并发性控制：多人操作同一数据
5. 数据恢复：故障的补救
6. 数据仓库、 数据挖掘 ：分析和发现有价值的数据

数据

数据是一种符号序列，它的内容是事物特性的反映。

数据是对现实世界的事物采用计算机能够识别、存储和处理的方式进行描述，或者说是计算机化的信息。

• 不仅包括数字、字母、文字和其他特殊字符；
• 而且还包括图形、图像、声音等多媒体数据。

数据库

数据库(Database,简称DB)是长期储存在计算机内、有组织的、可共享的大量数据集合。

• 数据按一定的数据模型组织、描述和储存
• 可为各种用户共享
• 冗余度较小
• 数据独立性较高
• 易扩展

数据库系统

数据库系统（Database System，简称DBS）是指在计算机系统中引入数据库后的系统构成。
在不引起混淆的情况下常常把数据库系统简称为数据库。组成如下：

• 硬件系统
• 数据库集合
• 数据库管理系统及相关软件
• 数据库管理员（DBA）
• 用户

表

表是二维结构，它包括行和列。一个表包括一组相关的实体——实体集。有时，术语实体集和表经常互换使用。

数据库系统使用关系来组织数据元素的，因此称关系就是表也不过分；每一个表对应于一个应用实体集，而每行则代表实体的一个事例。

数据库管理系统

DBMS：一个能够让用户定义、创建和维护数据库以及控制对数据库访问的软件系统。

• 查询处理器主要有四部分：
  • DDL编译器：
  • DML 编译器；
  • 嵌入式DML的预编译器；
  • 查询运行核心程序；
• 存储管理器主要有四个部分：
  • 授权和完整性管理器；
  • 事务管理器；
  • 文件管理器；
  • 缓冲区管理器；

根据这些组件的功能，可以总结出DBMS的功能：

1. 数据库定义功能：提供数据定义语言（DDL，Data Define Language）对各级数据模式精确定义。
2. 数据操纵功能：提供对数据库中的数据进行追加、插入、修改、删除、检索等操作。
3. 数据库运行控制功能：提供数据控制语言（DCL，Data Control Language）。数据库的恢复、并发控制、完整性控制、安全性控制；
4. 数据库的维护功能：包括数据库的初始数据的载入、转换功能、数据库的转储功能、数据库的重组织功能和性质监视、分析功能等。
5. 数据字典：数据字典(Data Dictionary，记为DD)。DD中存放着数据库三级结构的描述。对于数据库的操作都要通过查阅DD进行。

数据管理技术体系

根据计算机系统的结构不同，数据库系统结构可分为：

• 集中式
• 客户机/服务器式
• 并行式
• 分布式
• 基于互联网

三级结构模式

型，值

型（Type）：对某一类数据的结构和属性的说明，类似于表头
值（Value）：是型的一个具体赋值，是表里的某项数据；
例如：学生记录
记录型：（学号，姓名，性别，系别，年龄，籍贯）
该记录型的一个记录值：（900201，李明，男，计算机，22，江苏）

模式，实例

模式（Schema）

• 是型的描述
• 反映的是数据的结构及其联系
• 模式是相对稳定的

实例（Instance）

• 模式的一个具体值
• 反映数据库某一时刻的状态
• 同一个模式可以有很多实例
• 实例随数据库中的数据的更新而更新

数据库中的三级模式结构包括以下三个层次：外模式、概念模式和内模式。这个结构旨在将数据库系统中的物理存储和逻辑设计分离开来，以提高数据的独立性和安全性

内模式

• 定义：内模式是数据库的物理存储结构，描述了数据在存储设备上的具体存储方式。
• 作用：内模式处理数据的物理存储和访问方法，优化数据库性能。
• 特点：
  • 包括数据存储格式、索引、访问路径、数据压缩等物理细节。
  • 提供数据的物理独立性，逻辑设计的改变不会影响物理存储。
  • 关注性能优化、数据安全性和数据完整性。

概念模式

• 定义：概念模式是数据库的全局逻辑结构，描述了所有数据及其关系。它是数据库设计者和管理员所用的模式。
• 作用：概念模式独立于物理存储，提供一个全局的数据模型，确保数据的一致性和完整性。
• 特点：
  • 包含所有数据实体、属性、数据类型、关系、约束等的定义。
  • 独立于应用程序和物理存储。
  • 逻辑上组织了整个数据库，提供了数据视图的一致性。

外模式

• 定义：外模式是数据库的用户视图，它定义了用户如何看待数据库中的数据。每个用户或应用程序可以有一个或多个外模式。
• 作用：外模式屏蔽了数据库的复杂性，提供了定制化的数据视图，确保用户只访问他们需要的数据。这提高了数据的安全性和使用的便捷性。
• 特点：
  • 可以包括部分的数据库数据。
  • 可以对数据进行重新组织和格式化以适应特定的应用需求。
  • 不影响数据库的物理存储结构。

三层模式体系结构如下：

用户访问数据库的过程

概念

关系模式的五元组表示： R(U, D, DOM, F)

• R：关系名
• U：组成该关系的属性名集合
• D：属性组U中属性所来自的域
• DOM：属性向域的映象集合
• F：属性间数据的依赖关系集合

关系模式的简化三元组表示： R（U, F）

不好的数据库模式设计可鞥会导致如下问题：

1. 数据冗余：浪费存储空间，引起异常。
2. 操作异常：更新，删除，插入异常。

通常用模式分解的办法消除冗余和异常现象。但是注意，范式可能不是数据库的最佳实践；

函数依赖与数据依赖

什么是数据依赖？

• 是现实世界属性间相互联系的抽象
• 是数据内在的性质
• 是语义的体现

数据依赖的类型

• 函数依赖（Functional Dependency，简记为FD）
• 多值依赖（Multivalued Dependency，简记为MVD）

函数依赖：

• 属性（列）之间的联系
• 属性之间在语义上的关联特性
• 两个属性或属性集之间的约束

数据库设计者根据对关系R中的属性的语义理解确定函数依赖，确定约束R的所有元组r的函数依赖集，并获知属性间的语义关联。

平凡函数依赖：如果Y⊆X,显然X→Y成立；

• 例如：{Dname,Pname}→{Pname}
• 不反映新的语义；

完全函数依赖：

• X、Y是某关系不同属性集；
• 不存在X’⊂X,使得 X’→Y成立；

部分函数依赖：

• X、Y是某关系不同属性集；
• 存在X’⊂X,使得 x’→Y成立；

传递函数依赖

• X、Y、Z是某关系不同属性集
• 如果X→Y， Y→Z， X→Z且不存在Y → X；
• 条件Y → X说明，X和Y不是一一对应；

候选码与主码：设$K$为$R(U,F)$ 中的属性或属性组合，若$K \xrightarrow{f} U$,则$K$为$R$​的候选码(Candidate Key)。若候选码多于一个，则选定其中的一个为主码(Primary Key)。

在一个学生表（Student）中，可能有以下列：学号（StudentID）、身份证号（IDNumber）、电子邮件（Email）。每一个列都可以单独作为候选码，因为它们都能够唯一地标识一个学生记录。如果选择学号（StudentID）作为主码，那么学号列将被用作唯一标识每一行学生记录的主键。

包含在任何候选码中的属性称为主属性（Prime Attribute）。不包含在任何候选码中的属性称为非主属性（Non-Key Attribute）。
最简单的情况，单个属性是码。最极端的情况，整个属性组是码，称为全码（All-key）

关系模式$R_l$中属性或属性组合$X$并非 $R_l$的码,但$X$是另一个关系模式 $R_2$的码,则称$X$是$R_l$的外码(Foreign Key)。

模式分解和规范化

函数依赖可能引起的更新异常问题
解决方法：“一事一地” ，对关系模式进行分解，使之表达的语义概念单纯化。
关系模式R的分解就是用两个或两个以上关系来替换R，分解后的关系模式的属性集都是R中属性的子集，其并集与R的属性集相同。
模式分解帮助消除不良设计中的一些问题，如冗余、不一致或异常。
模式分解的定义

设有关系模式 $R(U)$,属性集为$U$,若用一关系模式的集合${R_1(U_1),R_2(U_2),\cdots,R_k(U_k)}$来取代,其中$U=\bigcup_{i=1}^{k}U_{i}$则称此关系模式的集合为$R$的一个分解,以$\rho={R_{1},\cdots,R_{k}}$表示。

无损连接分解：通过连接被分解后的小表可以获得原始表的内容

范式（Normal Forma，NF）是一种关系的状态，是衡量关系模式的标准。
范式的种类（ 1NF，2NF，3NF，BCNF ）与数据依赖有着直接的联系
数据冗余浪费存储空间，导致数据库难以保持一致性。
范式确保数据库模式的一致性。
为确定特定关系是否符合范式，需要检查关系中属性间的函数依赖，而不是检查关系中的当前实例。
规范化主要作为验证和改进逻辑数据库设计的工具，使得逻辑设计能够：
满足特定约束
避免不必要的数据重复。
例如：就诊关系模式R（Dname，Dlevel，Dsal，Pname，Fsum）存在冗余信息（重复存储的职称和工资），不是一个好的设计

1NF

在关系模式R的每个关系r中，如果每个属性值都是不可再分的原子值，那么称R是第一范式（1NF）的模式。
满足1NF的关系称为规范化的关系；否则称为非规范化的关系。
关系数据库研究的关系都是规范化的关系。
1NF中不允许出现“表中有表”的现象。

2NF

如果关系模式R∈1NF，且每个非主属性（不是组成候选码的属性）完全函数依赖于候选码，那么称R属于2NF的模式。
只有在主键是复合属性下才可能不符合2NF
2NF举例

• 设有关系模式R（Dname，Pname，Dlevel，Dsal，Fsum)的属性分别表示医生编号、患者编号、医生职称级别、医生工资和诊疗费用。（Dname，Pname）是R的候选码。
• 如果R上有两个FD：（ Dname ， Pname ）→（Dlevel，Dsal）和Dname →（Dlevel，Dsal），因此前面一个FD是局部依赖，所以R不是2NF。此时R会出现冗余和异常。例如，某个医生为N个病人看病，则在关系中会出现N个元组，而医生的职称级别和工资就会重复N次。
• 如果将R分解为R1（ Dname ，Dlevel，Dsal）和R2（ Dname ， Pname ，Fsum）后，局部依赖（ Dname ， Pname ）→（Dlevel，Dsal）就消失了，R1和R2都是2NF了。

2NF分解算法：将关系模式R分解成2NF模式子集
设有关系模式R(U)，主键是W，R上还存在函数依赖X→Z，其中Z是非主属性和X ⊂ W，则W→Z就是一个局部依赖。此时应该把R分解成两个模式：
① R1（XZ），主键是X；
② R2（U-Z），主键仍为W，外键是X（参考R1）。
利用外键和主键的连接可以从R1和R2重新得到R。
如果R1和R2还不是2NF，则重复上述过程，一直到数据库模式中每一个关系模式都是2NF为止。

3NF

如果关系模式R∈1NF，且每个非主属性都不传递依赖于R的候选码，那么称R属于3NF的模式。
两个条件:
（1）R中的非主属性相互独立；
（2）R中的非主属性函数依赖于主键。
举例：

• R2（ Dname ，Pname，Fsum）是2NF模式，而且也是3NF模式。
• 但是R1（ Dname ，Dlevel，Dsal）是2NF模式，但不一定是3NF。因为如果R1中存在函数依赖Dname →Dlevel和Dlevel→Dsal，那么Dname→Dsal就是一个传递依赖，即R1不是3NF模式。
• 此时R1的关系也会出现冗余和异常。例如，R2中存在M个职称同为主任级别的医生，则R1中需要重复存储M个相同的工资数目。
• 如果将R1分解为R11（ Dname ，Dlevel）和R12（Dlevel，Dsal）后，Dname→Dsal就不会出现在R11和R12中，因此R11和R12都是3NF的模式。

BCNF

定义：如果关系模式R∈1NF，且每个属性都不传递依赖于R的候选码，那么称R是BCNF的模式。
原因： 3NF模式中，并未排除主属性对候选键的传递依赖
满足BCNF的关系模式有：

• 所有非主属性对每一个码都是完全函数依赖。
• 所有的主属性对每一个不包含它的码，也是完全函数依赖。
• 没有任何属性完全函数依赖于非码的任何一组属性。

以下是一个例子：

关系模式R（Bno，Bname，Author）的属性分别表示书号、书名和作者名。假如每个书号只有一个书名，但不同的书号可以有相同的书名；每本书可以有多个作者合写，但每个作者参与编著的书名应该互不相同。

• R上的FD如下：Bno→Bname和（Bname，Author）→Bno
• 因此R的关键码是（Bno，Author）或（Bname，Author），因而模式R的属性都是主属性，R是3NF模式。
• 但根据两个FD可知，属性Bname传递依赖于关键码（Bname，Author），因此R不是BCNF。
• 例如，一本书由多个作者编写时，其书名与书号之间的联系在关系中将多次出现，会导致数据冗余和操作异常。
• 如果将R分解为R1（Bno，Bname）和R2（Bno，Author），则能够解决上述问题，且R1和R2都是BCNF。
• 但这样分解可能会导致新的问题，例如，这个分解把（Bname，Author）→Bno丢失了，数据语义将会引起新的矛盾。

BCNF分解算法：将R无损分解且保持依赖地分解成3NF模式集。
① 对于关系模式R和R上成立的FD集F，先求出F的最小依赖集，然后再把最小依赖集中那些左部相同的FD用合并性合并起来。
② 对最小依赖集中每个FD X→Y去构成一个模式(XY)。
③ 在构成的模式集中，如果每个模式都不包含R的候选码，那么把候选码作为一个模式放入模式集中。
举例：

• 设关系模式R（ABCDE），R的最小依赖集为{A→B，C→D}。从依赖集可知R的候选码为ACE。
• 先根据最小依赖集，可知ρ={AB,CD}。然后再加入由候选码组成的模式ACE。因此最后结果ρ={AB,CD,ACE}是一个3NF模式集，R相对于该依赖集是无损分解且保持函数依赖。

模式设计原则

满足范式要求的数据库设计是结构清晰的，同时可避免数据冗余和操作异常。这并意味着不符合范式要求的设计一定是错误的。
关系模式分解一般应具有3个特性：

• 达到BCNF，或3NF；
• 无损分解；
• 保持函数依赖。

一个好的模式设计方法应符合3条原则：表达性、分离性和最小冗余性。

• 表达性：数据等价和语义等价；即无损分解和保持依赖集
• 分离性：关系中只存储有直接联系的属性值；清除冗余和异常现象
• 最小冗余性：模式个数和模式中属性总数应最少；

数据库有如下的设计方法：

• 直观设计方法（手工试凑法）

  依赖于设计者的经验和技巧，设计质量难以保证。

• 新奥尔良（New Orleans）设计方法

  运行软件工程的思想和方法，提出了数据库设计的规范 .新奥尔良法将数据库设计分成：需求分析、概念设计、逻辑设计和物理设计。

• 基于实体-关系（E-R）模型的数据库设计方法

  在需求分析的基础上，用E-R图构造一个反映现实世界实体之间联系的企业模式转换成基于某一特定的DBMS的概念模式；

• 3NF设计方法
  在需求分析的基础上，确定数据库模式中的全部属性和属性间的依赖关系，将它们组织在一个单一的关系模式中，然后再分析模式中不符合3NF的约束条件，将其进行投影分解，规范成若干个3NF关系模式的集合。
• 面向对象的数据库设计方法 （ODL）
  使用面向对象的概念和术语来描述和完成数据库的结构设计，并可方便地转换为面向对象的数据库。
• 用于数据库设计的计算机辅助软件工具(CASE)
  SYSBASE公司的PowerDesigner、Oracle公司的Design er2000、CA公司的ERWin、Rational公司的Rational Rose、Microsoft公司的Visio。

SQL语言

对于SQL语言来说，

1. 以同一种语法结构提供两种使用方法：既是自含式语言，又是嵌入式语言
2. 语言简洁，易学易用，核心功能只需9个动词
   DDL（数据定义语言）：CREATE、DROP、ALTER
   DML（数据操纵语言）： SELECT、INSERT、UPDATE、DELETE
   DCL（数据控制语言）：GRANT、REVOKE

以下式SQL Server的包含的数据类型：

数据库创建

为了创建数据库，用户必须是系统管理员或者被授权使用CREATE DATABASE语句，语法形式如下：

1
2
3
4
5
6
7
8
9
10
11
12
13

CREATE DATABASE <数据库名>
[<On  Primary>     
% 一个数据库可建多个档案文件，主档案文件是会有一个，默认在主档案文件
    ([Name = 系统使用的逻辑名],
    [Filename = 完全限定的NT Server文件名], 
    [Size = 文件的初始大小],
    [MaxSize = 最大的文件尺寸],
    [FileGrowth = 系统的扩展文件量])…]
    [<Log On>
    ([Name = 系统使用的逻辑名],
    [Filename = 完全限定的NT Server文件名],
    [Size = 文件的初始大小],
    [FileGrowth = 系统的扩展文件量])]

创建表操作如下：

1
2
3
4
5
6
7
8

CREATE TABLE  基表名（
    <列名1> <列类型> <列约束>,
    <列名2> <列类型> <列约束>,
    …
    <列名n> <列类型> <列约束>,
    < 表约束> | [ { PRIMARY KEY | UNIQUE } [ ,…] ]
）
表名形式为：[数据库名[.拥有者.]]表名  

例如：

1
2
3
4
5
6
7

CREATE TABLE Medicine (
    Mno VARCHAR(10) PRIMARY KEY,
    Mname VARCHAR(50) NOT NULL,
    Mprice DECIMAL(18,2) NOT NULL,
    Munit VARCHAR(10) DEFAULT '克',
    Mtype VARCHAR(10)
)

常用完整性约束

1. 主码约束： PRIMARY KEY

2. 唯一性约束：UNIQUE

3. 非空值约束：NOT NULL

4. 参照完整性约束：Foreign Key？

   • 含有主键或者唯一性约束列的表为主表（或父表），含有外键的表为从表（或子表）。
   • 参照完整性：外键约束指定外键的列与主表中主键或者唯一性约束列相关联，也就是说，外键的每一个值至少能在主表的主键或唯一性约束列中找到一个相同的列值。
   • 外键是在从表上定义，当修改或删除主表的记录，或者在从表上修改或插入数据时，由数据库管理系统自动进行检查。
   • 在需要命名约束、多列约束或定义外键约束时，必须使用 CONSTRAINT 关键字。在简单约束（如单列主键、唯一约束、检查约束和默认值）中，可以省略 CONSTRAINT 关键字。

   • 以下是外键的一个示例：

     1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

     CREATE TABLE RecipeMaster ( Rno VARCHAR(10) PRIMARY KEY, Pno VARCHAR(10) NOT NULL, Dno VARCHAR(10) NOT NULL, DGno VARCHAR(10), Rdatetime DATETIME, ) CREATE TABLE RecipeDetail ( Rno varchar (10) , Mno varchar (10) , Mamount decimal(18, 0), CONSTRAINT Rnofk FOREIGN KEY(Rno) REFERENCES RecipeMaster(Rno), CONSTRAINT mnofk FOREIGN KEY(Dno) REFERENCES medicine(Mno) );