高斯混合模型是一种混合模型，混合的基本分布是高斯分布
参考《统计学习方法》
高斯混合模型（Gaussian Mixture Model，GMM）是一种用于对数据进行建模的概率模型。它假设数据是由多个高斯分布（正态分布）组成的混合体，每个分布代表一个潜在的子群。GMM 在聚类、密度估计和异常检测等领域具有广泛的应用。
以下是一个使用 Python 的 scikit-learn 库实现 GMM 的示例代码：
首先，确保已安装 scikit-learn 库，可以通过以下命令安装：
1 | pip install scikit-learn |
接下来，使用下面的代码示例：
1 | import numpy as np |
在上述代码中，我们首先使用 make_blobs 函数生成一个示例数据集，用于演示 GMM 的聚类效果。然后，我们创建了一个 GMM 模型，指定了期望的分布数量（n_components），并使用 fit 方法训练模型。最后，我们根据 GMM 模型的预测结果绘制了原始数据和聚类效果。
Gradient Boosting Decision Tree 迭代决策树，泛化能力较强
梯度提升决策树（Gradient Boosting Decision Tree，GBDT）是一种集成学习算法，通过迭代地训练弱学习器（通常是决策树），每一轮都试图修正前一轮的错误。这些弱学习器的预测结果被组合起来，形成最终的集成模型。 几乎可用于所有回归问题（线性/非线性），相对logistic regression仅能用于线性回归，GBDT的适用面非常广。亦可用于二分类问题（设定阈值，大于阈值为正例，反之为负例）。
可用于搜索排序
C4.5分类树:在每次分枝时，是穷举每一个feature的每一个阈值，找到使得按照feature<=阈值，和feature>阈值分成的两个分枝的熵最大的feature和阈值（熵最大的概念可理解成尽可能每个分枝的男女比例都远离1:1），按照该标准分枝得到两个新节点，用同样方法继续分枝直到所有人都被分入性别唯一的叶子节点，或达到预设的终止条件，若最终叶子节点中的性别不唯一，则以多数人的性别作为该叶子节点的性别。
在每个节点（不一定是叶子节点）都会得一个预测值，以年龄为例，该预测值等于属于这个节点的所有人年龄的平均值。分枝时穷举每一个feature的每个阈值找最好的分割点，但衡量最好的标准不再是最大熵，而是最小化均方差–即（每个人的年龄-预测年龄）^2 的总和 / N，或者说是每个人的预测误差平方和 除以 N。这很好理解，被预测出错的人数越多，错的越离谱，均方差就越大，通过最小化均方差能够找到最靠谱的分枝依据。分枝直到每个叶子节点上人的年龄都唯一（这太难了）或者达到预设的终止条件（如叶子个数上限），若最终叶子节点上人的年龄不唯一，则以该节点上所有人的平均年龄做为该叶子节点的预测年龄。
参考：http://www.schonlau.net/publication/05stata_boosting.pdf
多棵树来共同决策。GBDT的核心就在于，每一棵树学的是之前所有树结论和的残差，这个残差就是一个加预测值后能得真实值的累加量。比如A的真实年龄是18岁，但第一棵树的预测年龄是12岁，差了6岁，即残差为6岁。那么在第二棵树里我们把A的年龄设为6岁去学习，如果第二棵树真的能把A分到6岁的叶子节点，那累加两棵树的结论就是A的真实年龄；如果第二棵树的结论是5岁，则A仍然存在1岁的残差，第三棵树里A的年龄就变成1岁，继续学。这就是Gradient Boosting在GBDT中的意义，简单吧。
残差： A的预测值 + A的残差 = A的实际值 ，残差为0，极为真实值，（过拟合问题）
优点：Boosting的最大好处在于，每一步的残差计算其实变相地增大了分错instance的权重，而已经分对的instance则都趋向于0。这样后面的树就能越来越专注那些前面被分错的instance。
Adaboost是另一种boost方法，它按分类对错，分配不同的weight，计算cost function时使用这些weight，从而让“错分的样本权重越来越大，使它们更被重视”。Bootstrap也有类似思想，它在每一步迭代时不改变模型本身，也不计算残差，而是从N个instance训练集中按一定概率重新抽取N个instance出来（单个instance可以被重复sample），对着这N个新的instance再训练一轮。由于数据集变了迭代模型训练结果也不一样，而一个instance被前面分错的越厉害，它的概率就被设的越高，这样就能同样达到逐步关注被分错的instance，逐步完善的效果。Adaboost的方法被实践证明是一种很好的防止过拟合的方法，但至于为什么则至今没从理论上被证明。GBDT也可以在使用残差的同时引入Bootstrap re-sampling，GBDT多数实现版本中也增加的这个选项，但是否一定使用则有不同看法。re-sampling一个缺点是它的随机性，即同样的数据集合训练两遍结果是不一样的，也就是模型不可稳定复现，这对评估是很大挑战，比如很难说一个模型变好是因为你选用了更好的feature，还是由于这次sample的随机因素。
参考：http://en.wikipedia.org/wiki/Gradient_boosted_trees#Gradient_tree_boosting
每次走一小步逐渐逼近结果的效果，要比每次迈一大步很快逼近结果的方式更容易避免过拟合。即它不完全信任每一个棵残差树，它认为每棵树只学到了真理的一小部分，累加的时候只累加一小部分，通过多学几棵树弥补不足。
没用Shrinkage时：（yi表示第i棵树上y的预测值， y(1~i)表示前i棵树y的综合预测值）
y(i+1) = 残差(y1yi)， 其中： 残差(y1yi) = y真实值 - y(1 ~ i)
y(1 ~ i) = SUM(y1, …, yi)
Shrinkage不改变第一个方程，只把第二个方程改为：
y(1 ~ i) = y(1 ~ i-1) + step * yi
即Shrinkage仍然以残差作为学习目标，但对于残差学习出来的结果，只累加一小部分（step*残差）逐步逼近目标，step一般都比较小，如0.01~0.001（注意该step非gradient的step），导致各个树的残差是渐变的而不是陡变的。直觉上这也很好理解，不像直接用残差一步修复误差，而是只修复一点点，其实就是把大步切成了很多小步。本质上，Shrinkage为每棵树设置了一个weight，累加时要乘以这个weight，但和Gradient并没有关系。这个weight就是step。就像Adaboost一样，Shrinkage能减少过拟合发生也是经验证明的，目前还没有看到从理论的证明。
实际的搜索排序使用的是LambdaMART算法，必须指出的是由于这里要使用排序需要的cost function，LambdaMART迭代用的并不是残差。Lambda在这里充当替代残差的计算方法，它使用了一种类似Gradient*步长模拟残差的方法。这里的MART在求解方法上和之前说的残差略有不同，其区别描述见这里。
就像所有的机器学习一样，搜索排序的学习也需要训练集，这里一般是用人工标注实现，即对每一个(query,doc) pair给定一个分值（如1,2,3,4）,分值越高表示越相关，越应该排到前面。然而这些绝对的分值本身意义不大，例如你很难说1分和2分文档的相关程度差异是1分和3分文档差距的一半。相关度本身就是一个很主观的评判，标注人员无法做到这种定量标注，这种标准也无法制定。但标注人员很容易做到的是”AB都不错，但文档A比文档B更相关，所以A是4分，B是3分“。RankNet就是基于此制定了一个学习误差衡量方法，即cost function。具体而言，RankNet对任意两个文档A,B，通过它们的人工标注分差，用sigmoid函数估计两者顺序和逆序的概率P1。然后同理用机器学习到的分差计算概率P2（sigmoid的好处在于它允许机器学习得到的分值是任意实数值，只要它们的分差和标准分的分差一致，P2就趋近于P1）。这时利用P1和P2求的两者的交叉熵，该交叉熵就是cost function。它越低说明机器学得的当前排序越趋近于标注排序。为了体现NDCG的作用（NDCG是搜索排序业界最常用的评判标准），RankNet还在cost function中乘以了NDCG。
好，现在我们有了cost function，而且它是和各个文档的当前分值yi相关的，那么虽然我们不知道它的全局最优方向，但可以求导求Gradient，Gradient即每个文档得分的一个下降方向组成的N维向量，N为文档个数（应该说是query-doc pair个数）。这里仅仅是把”求残差“的逻辑替换为”求梯度“，可以这样想：梯度方向为每一步最优方向，累加的步数多了，总能走到局部最优点，若该点恰好为全局最优点，那和用残差的效果是一样的。这时套到之前讲的逻辑，GDBT就已经可以上了。那么最终排序怎么产生呢？很简单，每个样本通过Shrinkage累加都会得到一个最终得分，直接按分数从大到小排序就可以了（因为机器学习产生的是实数域的预测分，极少会出现在人工标注中常见的两文档分数相等的情况，几乎不同考虑同分文档的排序方式）
另外，如果feature个数太多，每一棵回归树都要耗费大量时间，这时每个分支时可以随机抽一部分feature来遍历求最优（ELF源码实现方式）。
在 Python 中，可以使用 scikit-learn 库来实现 GBDT。
首先，确保已安装 scikit-learn 库，可以通过以下命令安装：
1 | pip install scikit-learn |
接下来，使用下面的代码示例：
1 | from sklearn.datasets import load_iris |
在上述代码中，我们使用了 load_iris 函数加载鸢尾花数据集，并将数据集划分为训练集和测试集。然后，我们创建了一个 GBDT 分类器，并使用 fit 方法训练模型。最后，我们在测试集上进行预测，并计算了预测的准确率。
Generative Adversarial Network，就是大家耳熟能详的 GAN，由 Ian Goodfellow 首先提出，在这两年更是深度学习中最热门的东西，仿佛什么东西都能由 GAN 做出来。我最近刚入门 GAN，看了些资料，做一些笔记。
1.Generation
什么是生成（generation）？就是模型通过学习一些数据，然后生成类似的数据。让机器看一些动物图片，然后自己来产生动物的图片，这就是生成。
以前就有很多可以用来生成的技术了，比如 auto-encoder（自编码器）
你训练一个 encoder，把 input 转换成 code，然后训练一个 decoder，把 code 转换成一个 image，然后计算得到的 image 和 input 之间的 MSE（mean square error），训练完这个 model 之后，取出后半部分 NN Decoder，输入一个随机的 code，就能 generate 一个 image。
但是 auto-encoder 生成 image 的效果，当然看着很别扭啦，一眼就能看出真假。所以后来还提出了比如VAE这样的生成模型，我对此也不是很了解，在这就不细说。
上述的这些生成模型，其实有一个非常严重的弊端。比如 VAE，它生成的 image 是希望和 input 越相似越好，但是 model 是如何来衡量这个相似呢？model 会计算一个 loss，采用的大多是 MSE，即每一个像素上的均方差。loss 小真的表示相似嘛？
生成对抗网络（Generative Adversarial Network，GAN）是一种深度学习模型，用于生成与训练数据相似的新数据。GAN 包括两个主要组件：生成器（Generator）和判别器（Discriminator）。生成器试图生成类似于真实数据的样本，而判别器试图区分生成的样本和真实样本。这两个组件通过对抗性训练相互竞争，最终生成具有高质量的新数据。
以下是一个使用 Python 的 TensorFlow 库实现简单 GAN 的示例代码：
首先，确保已安装 tensorflow 库，可以通过以下命令安装：
1 | pip install tensorflow |
接下来，使用下面的代码示例：
1 | import tensorflow as tf |
这个示例展示了如何使用 TensorFlow 实现简单的 GAN，生成手写数字图片。代码中首先定义了生成器和判别器模型，然后构建 GAN 模型。通过循环训练生成器和判别器，使它们相互竞争和优化，最终生成具有相似特征的新图片。
Bagging（Bootstrap Aggregating）是一种集成学习方法，旨在提高模型的稳定性和泛化能力。它通过随机从训练集中有放回地抽取样本，然后训练多个独立的基本模型，最终通过投票或取平均来融合这些模型的预测结果。随机样本抽取和多模型组合有助于减小模型的方差，提高整体性能。
以下是使用 Python 的 scikit-learn 库实现 Bagging 的示例代码。我们将使用决策树作为基本模型：
首先，确保已安装 scikit-learn 库，可以通过以下命令安装：
1 | pip install scikit-learn |
接下来，使用下面的代码示例：
1 | from sklearn.datasets import load_iris |
在上述代码中，我们使用了 load_iris 函数加载鸢尾花数据集，并将数据集划分为训练集和测试集。然后，我们创建了一个 Bagging 分类器，基本模型选用了决策树。通过训练 Bagging 模型，然后在测试集上进行预测，并计算了预测的准确率。
通过调整参数（如基本模型、基本模型数量等），您可以进一步优化 Bagging 模型的性能。请注意，Bagging 算法也适用于其他基本模型，例如随机森林中的决策树、KNN 等。
开始节点--> 数据元素 ... --> 终端节点
clear、isEmpty、length、get、insert、remove、indexOf
public interface IList {
// 线性表置空操作
public void clear();
// 判断线性表是否为空操作
public boolean isEmpty();
// 获取线性表中元素的长度操作
public int length();
// 获取指定位置上面的元素操作
public Object get(int i);
// 在指定位置上面插入元素的操作
public void insert(int i, Object x);
// 删除指定位置上面的元素的操作
public void remove(int i);
// 查找指定元素的位置首次出现的位置操作
public int indexOf(Object x);
// 显示线性表中的内容操作
public void display();
}
顺序存储， 逻辑上相邻的数据元素，在物理存储上也是相邻的。 不便于插入和删除
public class SqList implements IList {
// 线性表存储空间
private Object[] listElem;
// 线性表的当前长度
private int curLen;
// 顺序表类的构造函数，构造一个存储空间容量为maxSize的线性表
public SqList(int maxSize) {
// TODO Auto-generated constructor stub
curLen = 0;
listElem = new Object[maxSize];
}
// 将一个已经存在的线性表置成空表
public void clear() {
// TODO Auto-generated method stub
// 置顺序表的当前长度为0
curLen = 0;
}
// 判断线性表中的数据元素的个数是否为0，若为0则返回true，否则返回false
public boolean isEmpty() {
// TODO Auto-generated method stub
return curLen == 0;
}
// 求线性表中的数据元素的个数并返回其值
public int length() {
// TODO Auto-generated method stub
// 返回顺序表的当前长度
return curLen;
}
// 读取到线性表中的第i个数据元素并由函数返回其值，其中i的取值范围为0≤i≤length()-1，若i不在此范围则抛出异常
public Object get(int i) {
// TODO Auto-generated method stub
if (i < 0 || i >= curLen) {
throw new RuntimeException("第" + i + "个元素不存在");
}
return listElem[i];
}
// 在线性表的第i个数据元素之前插入一个值位x的数据元素
public void insert(int i, Object x) {
// TODO Auto-generated method stub
// 判断表是否满了
if (curLen == listElem.length) {
throw new RuntimeException("存储空间已经满了，无法插入新的元素");
}
// 插入的位置不合法
if (i < 0 || i > curLen) {
throw new RuntimeException("插入的位置不合法");
}
// 必须要从最后一个元素开始依次逐个后移动，直到第i个数据元素移动完毕为止。
for (int j = curLen; j > i; j--) {
listElem[j] = listElem[j - 1];
}
listElem[i] = x;
curLen++;
}
public void remove(int i) {
// TODO Auto-generated method stub
if (i < 0 || i > curLen - 1) {
throw new RuntimeException("删除的位置不合法");
}
for (int j = i; j < curLen; j++) {
listElem[j] = listElem[j+1];
}
curLen--;
}
// 返回线性表中首次出现指定的数据元素的位序号，若线性表中不包含此数据元素，则返回-1
public int indexOf(Object x) {
// TODO Auto-generated method stub
for (int i = 0; i < curLen; i++) {
if (listElem[i].equals(x)) {
return i;
}
}
return -1;
}
// 输出线性表中的数据元素
public void display() {
// TODO Auto-generated method stub
for (int i = 0; i < curLen; i++) {
System.out.print(listElem[i] + " ");
}
System.out.println();
}
// 测试
public static void main(String[] args) {
SqList sqList = new SqList(10);
sqList.insert(0, "a");
sqList.insert(1, "z");
sqList.insert(2, "d");
sqList.insert(3, "m");
sqList.insert(4, "z");
int order = sqList.indexOf("z");
if (order!=-1) {
System.out.println("顺序表中第一次出现的值为z的数据元素的位置为："+order);
}else {
System.out.println("顺序表中不包括z元素");
}
}
}
链式存储，单向链表，节点保存下一个节点的引用，便于插入和删除
public class Node {
// 存放结点的值
private Object data;
// 后继结点的引用
private Node next;
// 无参数时的构造函数
public Node() {
// TODO Auto-generated constructor stub
this(null, null);
}
// 带有一个参数时的构造函数
public Node(Object data) {
this(data, null);
}
// 带有两个参数时的构造函数
public Node(Object data, Node next) {
this.data = data;
this.next = next;
}
public Object getData() {
return data;
}
public void setData(Object data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
红黑树是特殊的二叉查找树
注：确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。
public class RBTree<T extends Comparable<T>> {
private RBTNode<T> mRoot; // 根结点
private static final boolean RED = false;
private static final boolean BLACK = true;
public class RBTNode<T extends Comparable<T>> {
boolean color; // 颜色
T key; // 关键字(键值)
RBTNode<T> left; // 左孩子
RBTNode<T> right; // 右孩子
RBTNode<T> parent; // 父结点
public RBTNode(T key, boolean color, RBTNode<T> parent, RBTNode<T> left, RBTNode<T> right) {
this.key = key;
this.color = color;
this.parent = parent;
this.left = left;
this.right = right;
}
}
...
}
public class RBTree<T extends Comparable<T>> {
private RBTNode<T> mRoot; // 根结点
private static final boolean RED = false;
private static final boolean BLACK = true;
public class RBTNode<T extends Comparable<T>> {
boolean color; // 颜色
T key; // 关键字(键值)
RBTNode<T> left; // 左孩子
RBTNode<T> right; // 右孩子
RBTNode<T> parent; // 父结点
public RBTNode(T key, boolean color, RBTNode&lt;T&gt; parent, RBTNode&lt;T&gt; left, RBTNode&lt;T&gt; right) {
this.key = key;
this.color = color;
this.parent = parent;
this.left = left;
this.right = right;
}
}
…
}
/*
- 对红黑树的节点(x)进行左旋转
- 左旋示意图(对节点x进行左旋)：
px px
/ /
- x y
- / \ –(左旋)-. / \ #
- lx y x ry
/ \ / \
- ly ry lx ly
*/
private void leftRotate(RBTNode<T> x) {
// 设置x的右孩子为y
RBTNode<T> y = x.right;
// 将 “y的左孩子” 设为 “x的右孩子”；
// 如果y的左孩子非空，将 “x” 设为 “y的左孩子的父亲”
x.right = y.left;
if (y.left != null)
y.left.parent = x;
// 将 “x的父亲” 设为 “y的父亲”
y.parent = x.parent;
if (x.parent == null) {
this.mRoot = y; // 如果 “x的父亲” 是空节点，则将y设为根节点
} else {
if (x.parent.left == x)
x.parent.left = y; // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
else
x.parent.right = y; // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
}
// 将 “x” 设为 “y的左孩子”
y.left = x;
// 将 “x的父节点” 设为 “y”
x.parent = y;
}
/*
- 对红黑树的节点(y)进行右旋转
- 右旋示意图(对节点y进行左旋)：
py py
/ /
y x
/ \ --(右旋)-. / \ #
x ry lx y
/ \ / \ #
lx rx rx ry
*/
private void rightRotate(RBTNode<T> y) {
// 设置x是当前节点的左孩子。
RBTNode<T> x = y.left;
// 将 “x的右孩子” 设为 “y的左孩子”；
// 如果"x的右孩子"不为空的话，将 “y” 设为 “x的右孩子的父亲”
y.left = x.right;
if (x.right != null)
x.right.parent = y;
// 将 “y的父亲” 设为 “x的父亲”
x.parent = y.parent;
if (y.parent == null) {
this.mRoot = x; // 如果 “y的父亲” 是空节点，则将x设为根节点
} else {
if (y == y.parent.right)
y.parent.right = x; // 如果 y是它父节点的右孩子，则将x设为“y的父节点的右孩子”
else
y.parent.left = x; // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子”
}
// 将 “y” 设为 “x的右孩子”
x.right = y;
// 将 “y的父节点” 设为 “x”
y.parent = x;
}
/*
- 将结点插入到红黑树中
- 参数说明：
node 插入的结点 // 对应《算法导论》中的node
*/
private void insert(RBTNode<T> node) {
int cmp;
RBTNode<T> y = null;
RBTNode<T> x = this.mRoot;
// 1. 将红黑树当作一颗二叉查找树，将节点添加到二叉查找树中。
while (x != null) {
y = x;
cmp = node.key.compareTo(x.key);
if (cmp < 0)
x = x.left;
else
x = x.right;
}
node.parent = y;
if (y!=null) {
cmp = node.key.compareTo(y.key);
if (cmp < 0)
y.left = node;
else
y.right = node;
} else {
this.mRoot = node;
}
// 2. 设置节点的颜色为红色
node.color = RED;
// 3. 将它重新修正为一颗二叉查找树
insertFixUp(node);
}
/*
- 新建结点(key)，并将其插入到红黑树中
- 参数说明：
key 插入结点的键值
*/
public void insert(T key) {
RBTNode<T> node=new RBTNode<T>(key,BLACK,null,null,null);
// 如果新建结点失败，则返回。
if (node != null)
insert(node);
}
/*
- 红黑树插入修正函数
- 在向红黑树中插入节点之后(失去平衡)，再调用该函数；
- 目的是将它重新塑造成一颗红黑树。
- 参数说明：
node 插入的结点 // 对应《算法导论》中的z
*/
private void insertFixUp(RBTNode<T> node) {
RBTNode<T> parent, gparent;
// 若“父节点存在，并且父节点的颜色是红色”
while (((parent = parentOf(node))!=null) && isRed(parent)) {
gparent = parentOf(parent);
//若“父节点”是“祖父节点的左孩子”
if (parent == gparent.left) {
// Case 1条件：叔叔节点是红色
RBTNode&lt;T&gt; uncle = gparent.right;
if ((uncle!=null) &amp;&amp; isRed(uncle)) {
setBlack(uncle);
setBlack(parent);
setRed(gparent);
node = gparent;
continue;
}
// Case 2条件：叔叔是黑色，且当前节点是右孩子
if (parent.right == node) {
RBTNode&lt;T&gt; tmp;
leftRotate(parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3条件：叔叔是黑色，且当前节点是左孩子。
setBlack(parent);
setRed(gparent);
rightRotate(gparent);
} else { //若“z的父节点”是“z的祖父节点的右孩子”
// Case 1条件：叔叔节点是红色
RBTNode&lt;T&gt; uncle = gparent.left;
if ((uncle!=null) &amp;&amp; isRed(uncle)) {
setBlack(uncle);
setBlack(parent);
setRed(gparent);
node = gparent;
continue;
}
// Case 2条件：叔叔是黑色，且当前节点是左孩子
if (parent.left == node) {
RBTNode&lt;T&gt; tmp;
rightRotate(parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3条件：叔叔是黑色，且当前节点是右孩子。
setBlack(parent);
setRed(gparent);
leftRotate(gparent);
}
}
// 将根节点设为黑色
setBlack(this.mRoot);
}
/*
- 删除结点(node)，并返回被删除的结点
- 参数说明：
node 删除的结点
*/
private void remove(RBTNode<T> node) {
RBTNode<T> child, parent;
boolean color;
// 被删除节点的"左右孩子都不为空"的情况。
if ( (node.left!=null) && (node.right!=null) ) {
// 被删节点的后继节点。(称为"取代节点")
// 用它来取代"被删节点"的位置，然后再将"被删节点"去掉。
RBTNode<T> replace = node;
// 获取后继节点
replace = replace.right;
while (replace.left != null)
replace = replace.left;
// "node节点"不是根节点(只有根节点不存在父节点)
if (parentOf(node)!=null) {
if (parentOf(node).left == node)
parentOf(node).left = replace;
else
parentOf(node).right = replace;
} else {
// "node节点"是根节点，更新根节点。
this.mRoot = replace;
}
// child是"取代节点"的右孩子，也是需要"调整的节点"。
// "取代节点"肯定不存在左孩子！因为它是一个后继节点。
child = replace.right;
parent = parentOf(replace);
// 保存"取代节点"的颜色
color = colorOf(replace);
// "被删除节点"是"它的后继节点的父节点"
if (parent == node) {
parent = replace;
} else {
// child不为空
if (child!=null)
setParent(child, parent);
parent.left = child;
replace.right = node.right;
setParent(node.right, replace);
}
replace.parent = node.parent;
replace.color = node.color;
replace.left = node.left;
node.left.parent = replace;
if (color == BLACK)
removeFixUp(child, parent);
node = null;
return ;
}
if (node.left !=null) {
child = node.left;
} else {
child = node.right;
}
parent = node.parent;
// 保存”取代节点”的颜色
color = node.color;
if (child!=null)
child.parent = parent;
// “node节点”不是根节点
if (parent!=null) {
if (parent.left == node)
parent.left = child;
else
parent.right = child;
} else {
this.mRoot = child;
}
if (color == BLACK)
removeFixUp(child, parent);
node = null;
}
/*
- 删除结点(z)，并返回被删除的结点
- 参数说明：
tree 红黑树的根结点
z 删除的结点
*/
public void remove(T key) {
RBTNode<T> node;
if ((node = search(mRoot, key)) != null)
remove(node);
}
/*
- 红黑树删除修正函数
- 在从红黑树中删除插入节点之后(红黑树失去平衡)，再调用该函数；
- 目的是将它重新塑造成一颗红黑树。
- 参数说明：
node 待修正的节点
*/
private void removeFixUp(RBTNode<T> node, RBTNode<T> parent) {
RBTNode<T> other;
while ((node==null || isBlack(node)) && (node != this.mRoot)) {
if (parent.left == node) {
other = parent.right;
if (isRed(other)) {
// Case 1: x的兄弟w是红色的
setBlack(other);
setRed(parent);
leftRotate(parent);
other = parent.right;
}
if ((other.left==null || isBlack(other.left)) &amp;&amp;
(other.right==null || isBlack(other.right))) {
// Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的
setRed(other);
node = parent;
parent = parentOf(node);
} else {
if (other.right==null || isBlack(other.right)) {
// Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。
setBlack(other.left);
setRed(other);
rightRotate(other);
other = parent.right;
}
// Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
setColor(other, colorOf(parent));
setBlack(parent);
setBlack(other.right);
leftRotate(parent);
node = this.mRoot;
break;
}
} else {
other = parent.left;
if (isRed(other)) {
// Case 1: x的兄弟w是红色的
setBlack(other);
setRed(parent);
rightRotate(parent);
other = parent.left;
}
if ((other.left==null || isBlack(other.left)) &amp;&amp;
(other.right==null || isBlack(other.right))) {
// Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的
setRed(other);
node = parent;
parent = parentOf(node);
} else {
if (other.left==null || isBlack(other.left)) {
// Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。
setBlack(other.right);
setRed(other);
leftRotate(other);
other = parent.left;
}
// Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
setColor(other, colorOf(parent));
setBlack(parent);
setBlack(other.left);
rightRotate(parent);
node = this.mRoot;
break;
}
}
}
if (node!=null)
setBlack(node);
}
/**
* Java 语言: 红黑树
*
* @author skywang
* @date 2013/11/07
*/
public class RBTree<T extends Comparable<T>> {
private RBTNode<T> mRoot; // 根结点
private static final boolean RED = false;
private static final boolean BLACK = true;
public class RBTNode<T extends Comparable<T>> {
boolean color; // 颜色
T key; // 关键字(键值)
RBTNode<T> left; // 左孩子
RBTNode<T> right; // 右孩子
RBTNode<T> parent; // 父结点
public RBTNode(T key, boolean color, RBTNode&lt;T&gt; parent, RBTNode&lt;T&gt; left, RBTNode&lt;T&gt; right) {
this.key = key;
this.color = color;
this.parent = parent;
this.left = left;
this.right = right;
}
public T getKey() {
return key;
}
public String toString() {
return ""+key+(this.color==RED?"(R)":"B");
}
}
public RBTree() {
mRoot=null;
}
private RBTNode<T> parentOf(RBTNode<T> node) {
return node!=null ? node.parent : null;
}
private boolean colorOf(RBTNode<T> node) {
return node!=null ? node.color : BLACK;
}
private boolean isRed(RBTNode<T> node) {
return ((node!=null)&&(node.color==RED)) ? true : false;
}
private boolean isBlack(RBTNode<T> node) {
return !isRed(node);
}
private void setBlack(RBTNode<T> node) {
if (node!=null)
node.color = BLACK;
}
private void setRed(RBTNode<T> node) {
if (node!=null)
node.color = RED;
}
private void setParent(RBTNode<T> node, RBTNode<T> parent) {
if (node!=null)
node.parent = parent;
}
private void setColor(RBTNode<T> node, boolean color) {
if (node!=null)
node.color = color;
}
/*
- 前序遍历”红黑树”
*/
private void preOrder(RBTNode<T> tree) {
if(tree != null) {
System.out.print(tree.key+” “);
preOrder(tree.left);
preOrder(tree.right);
}
}
public void preOrder() {
preOrder(mRoot);
}
/*
- 中序遍历”红黑树”
*/
private void inOrder(RBTNode<T> tree) {
if(tree != null) {
inOrder(tree.left);
System.out.print(tree.key+” “);
inOrder(tree.right);
}
}
public void inOrder() {
inOrder(mRoot);
}
/*
- 后序遍历”红黑树”
*/
private void postOrder(RBTNode<T> tree) {
if(tree != null)
{
postOrder(tree.left);
postOrder(tree.right);
System.out.print(tree.key+” “);
}
}
public void postOrder() {
postOrder(mRoot);
}
/*
- (递归实现)查找”红黑树x”中键值为key的节点
*/
private RBTNode<T> search(RBTNode<T> x, T key) {
if (x==null)
return x;
int cmp = key.compareTo(x.key);
if (cmp < 0)
return search(x.left, key);
else if (cmp > 0)
return search(x.right, key);
else
return x;
}
public RBTNode<T> search(T key) {
return search(mRoot, key);
}
/*
(非递归实现)查找”红黑树x”中键值为key的节点
*/
private RBTNode<T> iterativeSearch(RBTNode<T> x, T key) {
while (x!=null) {
int cmp = key.compareTo(x.key);
if (cmp < 0)
x = x.left;
else if (cmp > 0)
x = x.right;
else
return x;
}
return x;
}
public RBTNode<T> iterativeSearch(T key) {
return iterativeSearch(mRoot, key);
}
/*
- 查找最小结点：返回tree为根结点的红黑树的最小结点。
*/
private RBTNode<T> minimum(RBTNode<T> tree) {
if (tree == null)
return null;
while(tree.left != null)
tree = tree.left;
return tree;
}
public T minimum() {
RBTNode<T> p = minimum(mRoot);
if (p != null)
return p.key;
return null;
}
/*
- 查找最大结点：返回tree为根结点的红黑树的最大结点。
*/
private RBTNode<T> maximum(RBTNode<T> tree) {
if (tree == null)
return null;
while(tree.right != null)
tree = tree.right;
return tree;
}
public T maximum() {
RBTNode<T> p = maximum(mRoot);
if (p != null)
return p.key;
return null;
}
/*
找结点(x)的后继结点。即，查找”红黑树中数据值大于该结点”的”最小结点”。
*/
public RBTNode<T> successor(RBTNode<T> x) {
// 如果x存在右孩子，则”x的后继结点”为 “以其右孩子为根的子树的最小结点”。
if (x.right != null)
return minimum(x.right);
// 如果x没有右孩子。则x有以下两种可能：
// (01) x是”一个左孩子”，则”x的后继结点”为 “它的父结点”。
// (02) x是”一个右孩子”，则查找”x的最低的父结点，并且该父结点要具有左孩子”，找到的这个”最低的父结点”就是”x的后继结点”。
RBTNode<T> y = x.parent;
while ((y!=null) && (x==y.right)) {
x = y;
y = y.parent;
}
return y;
}
/*
找结点(x)的前驱结点。即，查找”红黑树中数据值小于该结点”的”最大结点”。
*/
public RBTNode<T> predecessor(RBTNode<T> x) {
// 如果x存在左孩子，则”x的前驱结点”为 “以其左孩子为根的子树的最大结点”。
if (x.left != null)
return maximum(x.left);
// 如果x没有左孩子。则x有以下两种可能：
// (01) x是”一个右孩子”，则”x的前驱结点”为 “它的父结点”。
// (01) x是”一个左孩子”，则查找”x的最低的父结点，并且该父结点要具有右孩子”，找到的这个”最低的父结点”就是”x的前驱结点”。
RBTNode<T> y = x.parent;
while ((y!=null) && (x==y.left)) {
x = y;
y = y.parent;
}
return y;
}
/*
- 对红黑树的节点(x)进行左旋转
- 左旋示意图(对节点x进行左旋)：
px px
/ /
- x y
- / \ –(左旋)-. / \ #
- lx y x ry
/ \ / \
- ly ry lx ly
*/
private void leftRotate(RBTNode<T> x) {
// 设置x的右孩子为y
RBTNode<T> y = x.right;
// 将 “y的左孩子” 设为 “x的右孩子”；
// 如果y的左孩子非空，将 “x” 设为 “y的左孩子的父亲”
x.right = y.left;
if (y.left != null)
y.left.parent = x;
// 将 “x的父亲” 设为 “y的父亲”
y.parent = x.parent;
if (x.parent == null) {
this.mRoot = y; // 如果 “x的父亲” 是空节点，则将y设为根节点
} else {
if (x.parent.left == x)
x.parent.left = y; // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
else
x.parent.right = y; // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
}
// 将 “x” 设为 “y的左孩子”
y.left = x;
// 将 “x的父节点” 设为 “y”
x.parent = y;
}
/*
- 对红黑树的节点(y)进行右旋转
- 右旋示意图(对节点y进行左旋)：
py py
/ /
y x
/ \ --(右旋)-. / \ #
x ry lx y
/ \ / \ #
lx rx rx ry
*/
private void rightRotate(RBTNode<T> y) {
// 设置x是当前节点的左孩子。
RBTNode<T> x = y.left;
// 将 “x的右孩子” 设为 “y的左孩子”；
// 如果"x的右孩子"不为空的话，将 “y” 设为 “x的右孩子的父亲”
y.left = x.right;
if (x.right != null)
x.right.parent = y;
// 将 “y的父亲” 设为 “x的父亲”
x.parent = y.parent;
if (y.parent == null) {
this.mRoot = x; // 如果 “y的父亲” 是空节点，则将x设为根节点
} else {
if (y == y.parent.right)
y.parent.right = x; // 如果 y是它父节点的右孩子，则将x设为“y的父节点的右孩子”
else
y.parent.left = x; // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子”
}
// 将 “y” 设为 “x的右孩子”
x.right = y;
// 将 “y的父节点” 设为 “x”
y.parent = x;
}
/*
- 红黑树插入修正函数
- 在向红黑树中插入节点之后(失去平衡)，再调用该函数；
- 目的是将它重新塑造成一颗红黑树。
- 参数说明：
node 插入的结点 // 对应《算法导论》中的z
*/
private void insertFixUp(RBTNode<T> node) {
RBTNode<T> parent, gparent;
// 若“父节点存在，并且父节点的颜色是红色”
while (((parent = parentOf(node))!=null) &amp;&amp; isRed(parent)) {
gparent = parentOf(parent);
//若“父节点”是“祖父节点的左孩子”
if (parent == gparent.left) {
// Case 1条件：叔叔节点是红色
RBTNode&lt;T&gt; uncle = gparent.right;
if ((uncle!=null) &amp;&amp; isRed(uncle)) {
setBlack(uncle);
setBlack(parent);
setRed(gparent);
node = gparent;
continue;
}
// Case 2条件：叔叔是黑色，且当前节点是右孩子
if (parent.right == node) {
RBTNode&lt;T&gt; tmp;
leftRotate(parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3条件：叔叔是黑色，且当前节点是左孩子。
setBlack(parent);
setRed(gparent);
rightRotate(gparent);
} else { //若“z的父节点”是“z的祖父节点的右孩子”
// Case 1条件：叔叔节点是红色
RBTNode&lt;T&gt; uncle = gparent.left;
if ((uncle!=null) &amp;&amp; isRed(uncle)) {
setBlack(uncle);
setBlack(parent);
setRed(gparent);
node = gparent;
continue;
}
// Case 2条件：叔叔是黑色，且当前节点是左孩子
if (parent.left == node) {
RBTNode&lt;T&gt; tmp;
rightRotate(parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3条件：叔叔是黑色，且当前节点是右孩子。
setBlack(parent);
setRed(gparent);
leftRotate(gparent);
}
}
// 将根节点设为黑色
setBlack(this.mRoot);
}
/*
- 将结点插入到红黑树中
- 参数说明：
node 插入的结点 // 对应《算法导论》中的node
*/
private void insert(RBTNode<T> node) {
int cmp;
RBTNode<T> y = null;
RBTNode<T> x = this.mRoot;
// 1. 将红黑树当作一颗二叉查找树，将节点添加到二叉查找树中。
while (x != null) {
y = x;
cmp = node.key.compareTo(x.key);
if (cmp &lt; 0)
x = x.left;
else
x = x.right;
}
node.parent = y;
if (y!=null) {
cmp = node.key.compareTo(y.key);
if (cmp &lt; 0)
y.left = node;
else
y.right = node;
} else {
this.mRoot = node;
}
// 2. 设置节点的颜色为红色
node.color = RED;
// 3. 将它重新修正为一颗二叉查找树
insertFixUp(node);
}
/*
- 新建结点(key)，并将其插入到红黑树中
- 参数说明：
key 插入结点的键值
*/
public void insert(T key) {
RBTNode<T> node=new RBTNode<T>(key,BLACK,null,null,null);
// 如果新建结点失败，则返回。
if (node != null)
insert(node);
}
/*
- 红黑树删除修正函数
- 在从红黑树中删除插入节点之后(红黑树失去平衡)，再调用该函数；
- 目的是将它重新塑造成一颗红黑树。
- 参数说明：
node 待修正的节点
*/
private void removeFixUp(RBTNode<T> node, RBTNode<T> parent) {
RBTNode<T> other;
while ((node==null || isBlack(node)) &amp;&amp; (node != this.mRoot)) {
if (parent.left == node) {
other = parent.right;
if (isRed(other)) {
// Case 1: x的兄弟w是红色的
setBlack(other);
setRed(parent);
leftRotate(parent);
other = parent.right;
}
if ((other.left==null || isBlack(other.left)) &amp;&amp;
(other.right==null || isBlack(other.right))) {
// Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的
setRed(other);
node = parent;
parent = parentOf(node);
} else {
if (other.right==null || isBlack(other.right)) {
// Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。
setBlack(other.left);
setRed(other);
rightRotate(other);
other = parent.right;
}
// Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
setColor(other, colorOf(parent));
setBlack(parent);
setBlack(other.right);
leftRotate(parent);
node = this.mRoot;
break;
}
} else {
other = parent.left;
if (isRed(other)) {
// Case 1: x的兄弟w是红色的
setBlack(other);
setRed(parent);
rightRotate(parent);
other = parent.left;
}
if ((other.left==null || isBlack(other.left)) &amp;&amp;
(other.right==null || isBlack(other.right))) {
// Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的
setRed(other);
node = parent;
parent = parentOf(node);
} else {
if (other.left==null || isBlack(other.left)) {
// Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。
setBlack(other.right);
setRed(other);
leftRotate(other);
other = parent.left;
}
// Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
setColor(other, colorOf(parent));
setBlack(parent);
setBlack(other.left);
rightRotate(parent);
node = this.mRoot;
break;
}
}
}
if (node!=null)
setBlack(node);
}
/*
- 删除结点(node)，并返回被删除的结点
- 参数说明：
node 删除的结点
*/
private void remove(RBTNode<T> node) {
RBTNode<T> child, parent;
boolean color;
// 被删除节点的"左右孩子都不为空"的情况。
if ( (node.left!=null) &amp;&amp; (node.right!=null) ) {
// 被删节点的后继节点。(称为"取代节点")
// 用它来取代"被删节点"的位置，然后再将"被删节点"去掉。
RBTNode&lt;T&gt; replace = node;
// 获取后继节点
replace = replace.right;
while (replace.left != null)
replace = replace.left;
// "node节点"不是根节点(只有根节点不存在父节点)
if (parentOf(node)!=null) {
if (parentOf(node).left == node)
parentOf(node).left = replace;
else
parentOf(node).right = replace;
} else {
// "node节点"是根节点，更新根节点。
this.mRoot = replace;
}
// child是"取代节点"的右孩子，也是需要"调整的节点"。
// "取代节点"肯定不存在左孩子！因为它是一个后继节点。
child = replace.right;
parent = parentOf(replace);
// 保存"取代节点"的颜色
color = colorOf(replace);
// "被删除节点"是"它的后继节点的父节点"
if (parent == node) {
parent = replace;
} else {
// child不为空
if (child!=null)
setParent(child, parent);
parent.left = child;
replace.right = node.right;
setParent(node.right, replace);
}
replace.parent = node.parent;
replace.color = node.color;
replace.left = node.left;
node.left.parent = replace;
if (color == BLACK)
removeFixUp(child, parent);
node = null;
return ;
}
if (node.left !=null) {
child = node.left;
} else {
child = node.right;
}
parent = node.parent;
// 保存"取代节点"的颜色
color = node.color;
if (child!=null)
child.parent = parent;
// "node节点"不是根节点
if (parent!=null) {
if (parent.left == node)
parent.left = child;
else
parent.right = child;
} else {
this.mRoot = child;
}
if (color == BLACK)
removeFixUp(child, parent);
node = null;
}
/*
- 删除结点(z)，并返回被删除的结点
- 参数说明：
tree 红黑树的根结点
z 删除的结点
*/
public void remove(T key) {
RBTNode<T> node;
if ((node = search(mRoot, key)) != null)
remove(node);
}
/*
- 销毁红黑树
*/
private void destroy(RBTNode<T> tree) {
if (tree==null)
return ;
if (tree.left != null)
destroy(tree.left);
if (tree.right != null)
destroy(tree.right);
tree=null;
}
public void clear() {
destroy(mRoot);
mRoot = null;
}
/*
- 打印”红黑树”
- key – 节点的键值
- direction – 0，表示该节点是根节点;
-1，表示该节点是它的父结点的左孩子;
1，表示该节点是它的父结点的右孩子。
*/
private void print(RBTNode<T> tree, T key, int direction) {
if(tree != null) {
if(direction==0) // tree是根节点
System.out.printf("%2d(B) is root\n", tree.key);
else // tree是分支节点
System.out.printf("%2d(%s) is %2d's %6s child\n", tree.key, isRed(tree)?"R":"B", key, direction==1?"right" : "left");
print(tree.left, tree.key, -1);
print(tree.right,tree.key, 1);
}
}
public void print() {
if (mRoot != null)
print(mRoot, mRoot.key, 0);
}
}
/**
Java 语言: 二叉查找树
@author skywang
@date 2013/11/07
*/
public class RBTreeTest {
private static final int a[] = {10, 40, 30, 60, 90, 70, 20, 50, 80};
private static final boolean mDebugInsert = false; // “插入”动作的检测开关(false，关闭；true，打开)
private static final boolean mDebugDelete = false; // “删除”动作的检测开关(false，关闭；true，打开)
public static void main(String[] args) {
int i, ilen = a.length;
RBTree<Integer> tree=new RBTree<Integer>();
System.out.printf(“== 原始数据: “);
for(i=0; i<ilen; i++)
System.out.printf(“%d “, a[i]);
System.out.printf(“\n”);
for(i=0; i<ilen; i++) {
tree.insert(a[i]);
// 设置mDebugInsert=true,测试”添加函数”
if (mDebugInsert) {
System.out.printf(“== 添加节点: %d\n”, a[i]);
System.out.printf(“== 树的详细信息: \n”);
tree.print();
System.out.printf(“\n”);
}
}
System.out.printf(“== 前序遍历: “);
tree.preOrder();
System.out.printf(“\n== 中序遍历: “);
tree.inOrder();
System.out.printf(“\n== 后序遍历: “);
tree.postOrder();
System.out.printf(“\n”);
System.out.printf(“== 最小值: %s\n”, tree.minimum());
System.out.printf(“== 最大值: %s\n”, tree.maximum());
System.out.printf(“== 树的详细信息: \n”);
tree.print();
System.out.printf(“\n”);
// 设置mDebugDelete=true,测试”删除函数”
if (mDebugDelete) {
for(i=0; i<ilen; i++)
{
tree.remove(a[i]);
System.out.printf(“== 删除节点: %d\n”, a[i]);
System.out.printf(“== 树的详细信息: \n”);
tree.print();
System.out.printf(“\n”);
}
}
// 销毁二叉树
tree.clear();
}
}
n阶对称矩阵：只存储上三角或者下三角矩阵中的元素，把原来需要存储n*n个元素压缩至n*(n-1)/2个元素
//对称矩阵的压缩算法
public class SymeMatric {
double[] a;// 矩阵元素
int n; // 矩阵的阶数
int m;// 一维数组的元素的个数--长度
public SymeMatric(int n) {
// 对称矩阵中不重复元素，保存到一维数组中所需要的一维数组的长度
// 2阶对称矩阵对应(1+2=3)维数组，3阶对称矩阵对应1+2+3=6维数组，
// 4阶对称矩阵对应1+2+3+4维数组，n阶对称矩阵对应前n项和，
// 所以一维数组的长度m的值为1,2,3...n的前n项和
m = n * (n + 1) / 2;
a = new double[m];
this.n = n;
}
// 通过一个二维数组来初始化
public void evalute(double[][] b) {
int k = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// i >= j表示只保存下三角元素
if (i >= j) {
a[k++] = b[i][j];
}
}
}
}
// 通过一个一维数组来初始化,那么这个一维数组就是对称矩阵元素的一个副本
public void evalute(double[] b) {
for (int k = 0; k < m; k++) {
a[k] = b[k];
}
}
// 对称矩阵相加
public SymeMatric add(SymeMatric b) {
SymeMatric t = new SymeMatric(n);
int k;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i >= j) {
k = i * (i - 1) / 2 + j - 1;
} else {
k = j * (j - 1) / 2 + i - 1;
}
// 求和
t.a[k] = a[k] + b.a[k];
}
}
return t;
}
// 打印对称矩阵，这个才是关键！！
public void print() {
int k;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i >= j) {
k = i * (i - 1) / 2 + j - 1;
} else {
k = j * (j - 1) / 2 + i - 1;
}
System.out.print(" " + a[k]);
}
System.out.println();
}
}
}
m对角矩阵：非零元素在每行中有m个，一维数组s[k]和A[i][j]的对应关系为：k = m*i+j
矩阵m*n如果有t个非零元素，那么s = t/m*n称为矩阵的稀疏因子，如果s<=0.05那么矩阵为稀疏矩阵
注：三元组顺序表表示，其中三元组格式为(i,j,e)记录了非零元素的行号、列号以及非零元素
inal int _ROWS=5; //定义行数
final int _COLS=5; //定义列数
final int _NOTZERO=6; //定义稀疏矩阵中不为零的个数
int i,j,tmpRW,tmpCL,tmpNZ;
int temp=1;
int Sparse[][]=new int[_ROWS][_COLS]; //声明稀疏矩阵
int Compress[][]=new int[_NOTZERO+1][3];//声明压缩矩阵
for(i=0;i<_ROWS;i++) //将矩阵初始值都设为0
for(j=0;j<_COLS;j++)
Sparse[i][j]=0;
tmpNZ=_NOTZERO; //产生随机稀疏矩阵
for(i=1;i<tmpNZ+1;i++) {
tmpRW=(int)(Math.random()*100);
tmpRW=(tmpRW%_ROWS);
tmpCL=(int)(Math.random()*100);
tmpCL=(tmpCL%_COLS);
if(Sparse[tmpRW][tmpCL]!=0)
tmpNZ++;
Sparse[tmpRW][tmpCL]=i;
}
/开始压缩稀疏矩阵/
Compress[0][0]=_ROWS;
Compress[0][1]=_COLS;
Compress[0][2]=_NOTZERO;
for(i=0;i<_ROWS;i++) {
for(j=0;j<_COLS;j++) {
if(Sparse[i][j]!=0){
Compress[temp][0]=i;
Compress[temp][1]=j;
Compress[temp][2]=Sparse[i][j];
temp++;
}
}
}
先进后出(LIFO, Last In First Out)
数组 栈大小固定
链表 栈大小不固定
public class Node {
//数据域
public int data;
//指针域，指向下一个节点
public Node next;
public Node() {
}
public Node(int data) {
this.data = data;
}
public Node(int data, Node next) {
this.data = data;
this.next = next;
}
}
public class Stack {
public Node stackTop;//栈顶
public Node stackBottom;//栈底
public Stack(Node stackTop, Node stackBottom) {
this.stackTop = stackTop;
this.stackBottom = stackBottom;
}
public Stack() {
}
}
/**
进栈
@param stack 栈
@param value 要进栈的元素
*/
public static void pushStack(Stack stack, int value) {
// 封装数据成节点
Node newNode = new Node(value);
// 栈顶本来指向的节点交由新节点来指向
newNode.next = stack.stackTop;
// 栈顶指针指向新节点
stack.stackTop = newNode;
}
/**
遍历栈(只要栈顶指针不指向栈底指针，就一直输出)
@param stack
*/
public static void traverse(Stack stack) {
Node stackTop = stack.stackTop;
while (stackTop != stack.stackBottom) {
System.out.println("关注公众号：Java3y：" + stackTop.data);
stackTop = stackTop.next;
}
}
/**
判断该栈是否为空
@param stack
*/
public static void isEmpty(Stack stack) {
if (stack.stackTop == stack.stackBottom) {
System.out.println("关注公众号：Java3y---->该栈为空");
} else {
System.out.println("关注公众号：Java3y---->该栈不为空");
}
}
/**
出栈(将栈顶的指针指向下一个节点)
@param stack
*/
public static void popStack(Stack stack) {
// 栈不为空才能出栈
if (!isEmpty(stack)) {
//栈顶元素
Node top = stack.stackTop;
// 栈顶指针指向下一个节点
stack.stackTop = top.next;
System.out.println(“关注公众号：Java3y—->出栈的元素是：” + top.data);
}
}
/**
清空栈
@param stack
*/
public static void clearStack(Stack stack) {
stack.stackTop = null;
stack.stackBottom = stack.stackTop;
}
先进先出(LILO, Last In Last Out)
数组实现循环队列，节省内存资源
public class Queue {
//数组
public int [] arrays;
//指向第一个有效的元素
public int front = 0;
//指向有效数据的下一个元素(即指向无效的数据)
public int rear = 0;
}
/**
入队
@param queue
*/
public static void enQueue(Queue queue,int value) {
// 不是满的队列才能入队
if (!isFull(queue)) {
// 将新的元素插入到队尾中
queue.arrays[queue.rear] = value;
// rear节点移动到新的无效元素位置上
queue.rear = (queue.rear + 1) % queue.arrays.length;
}
}
/**
出队
@param queue
*/
public static void outQueue(Queue queue) {
//判断该队列是否为null
if (!isEmpty(queue)) {
//不为空才出队
int value = queue.arrays[queue.front];
System.out.println("关注公众号：Java3y--->出队的元素是：" + value);
// front指针往后面移
queue.front = (queue.front + 1) % queue.arrays.length;
}
}
/**
- 判断队列是否空，front和rear指针相等，就是空了
- @param queue
- @return
*/
public static boolean isEmpty(Queue queue) {
if (queue.rear == queue.front) {
System.out.println(“关注公众号：Java3y—>此时队列空的！”);
return true;
} else {
System.out.println(“关注公众号：Java3y—>此时队列非空！”);
return false;
}
}
/**
判断队列是否满了，front和rear指针紧挨着，就是满了
@param queue
@return
*/
public static boolean isFull(Queue queue) {
if ((queue.rear + 1) % queue.arrays.length == queue.front) {
System.out.println("关注公众号：Java3y--->此时队列满了！");
return true;
} else {
System.out.println(“关注公众号：Java3y—>此时队列没满了！”);
return false;
}
}
/**
- 遍历队列
- @param queue
*/
public static void traverseQueue(Queue queue) {
// front的位置
int i = queue.front;
while (i != queue.rear) {
System.out.println("关注公众号：Java3y---&gt;" + queue.arrays[i]);
//移动front
i = (i + 1) % queue.arrays.length;
}
}
链表实现