Qi

title:机器学习-GAN

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
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

import tensorflow as tf
from tensorflow.keras.layers import Dense, Flatten, Reshape
from tensorflow.keras.models import Sequential
import matplotlib.pyplot as plt
import numpy as np

# 生成器模型
def build_generator(latent_dim, output_shape):
    model = Sequential([
        Dense(128, input_dim=latent_dim, activation='relu'),
        Dense(256, activation='relu'),
        Dense(np.prod(output_shape), activation='sigmoid'),
        Reshape(output_shape)
    ])
    return model

# 判别器模型
def build_discriminator(input_shape):
    model = Sequential([
        Flatten(input_shape=input_shape),
        Dense(256, activation='relu'),
        Dense(128, activation='relu'),
        Dense(1, activation='sigmoid')
    ])
    return model

# 生成器和判别器的参数
latent_dim = 100
input_shape = (28, 28, 1)

# 构建生成器和判别器
generator = build_generator(latent_dim, input_shape)
discriminator = build_discriminator(input_shape)
discriminator.compile(loss='binary_crossentropy', optimizer='adam', metrics=['accuracy'])
discriminator.trainable = False

# 构建 GAN 模型
gan_input = tf.keras.Input(shape=(latent_dim,))
gan_output = discriminator(generator(gan_input))
gan = tf.keras.Model(gan_input, gan_output)
gan.compile(loss='binary_crossentropy', optimizer='adam')

# 加载 MNIST 数据集
(x_train, _), (_, _) = tf.keras.datasets.mnist.load_data()
x_train = x_train / 255.0
x_train = np.expand_dims(x_train, axis=-1)

# 训练 GAN
epochs = 10000
batch_size = 32

for epoch in range(epochs):
    # 生成随机噪声作为输入
    noise = np.random.normal(0, 1, (batch_size, latent_dim))
    # 生成假图片
    generated_images = generator.predict(noise)
    # 随机选择真实图片
    real_images = x_train[np.random.randint(0, x_train.shape[0], batch_size)]
    
    # 训练判别器
    d_loss_real = discriminator.train_on_batch(real_images, np.ones((batch_size, 1)))
    d_loss_fake = discriminator.train_on_batch(generated_images, np.zeros((batch_size, 1)))
    d_loss = 0.5 * np.add(d_loss_real, d_loss_fake)
    
    # 训练生成器
    noise = np.random.normal(0, 1, (batch_size, latent_dim))
    g_loss = gan.train_on_batch(noise, np.ones((batch_size, 1)))
    
    # 打印损失
    if epoch % 100 == 0:
        print(f"Epoch {epoch}, D Loss: {d_loss[0]}, G Loss: {g_loss}")

        # 绘制生成的图片
        if epoch % 1000 == 0:
            generated_images = generated_images * 255.0
            generated_images = generated_images.astype(np.uint8)
            for i in range(4):
                plt.subplot(2, 2, i+1)
                plt.imshow(generated_images[i].reshape(28, 28), cmap='gray')
            plt.show()

这个示例展示了如何使用 TensorFlow 实现简单的 GAN，生成手写数字图片。代码中首先定义了生成器和判别器模型，然后构建 GAN 模型。通过循环训练生成器和判别器，使它们相互竞争和优化，最终生成具有相似特征的新图片。

gan

Bagging（Bootstrap Aggregating）是一种集成学习方法，旨在提高模型的稳定性和泛化能力。它通过随机从训练集中有放回地抽取样本，然后训练多个独立的基本模型，最终通过投票或取平均来融合这些模型的预测结果。随机样本抽取和多模型组合有助于减小模型的方差，提高整体性能。

以下是使用 Python 的 scikit-learn 库实现 Bagging 的示例代码。我们将使用决策树作为基本模型：

首先，确保已安装 scikit-learn 库，可以通过以下命令安装：

1

pip install scikit-learn

接下来，使用下面的代码示例：

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

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.ensemble import BaggingClassifier
from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import accuracy_score

# 加载鸢尾花数据集
iris = load_iris()
X, y = iris.data, iris.target

# 划分训练集和测试集
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# 创建 Bagging 分类器，基本模型为决策树
base_model = DecisionTreeClassifier(random_state=42)
bagging_model = BaggingClassifier(base_model, n_estimators=10, random_state=42)

# 训练模型
bagging_model.fit(X_train, y_train)

# 在测试集上进行预测
y_pred = bagging_model.predict(X_test)

# 计算准确率
accuracy = accuracy_score(y_test, y_pred)
print("Bagging Accuracy:", accuracy)

在上述代码中，我们使用了 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<T> parent, RBTNode<T> left, RBTNode<T> 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<T> uncle = gparent.right;
            if ((uncle!=null) && isRed(uncle)) {
                setBlack(uncle);
                setBlack(parent);
                setRed(gparent);
                node = gparent;
                continue;
            }

            // Case 2条件：叔叔是黑色，且当前节点是右孩子
            if (parent.right == node) {
                RBTNode<T> tmp;
                leftRotate(parent);
                tmp = parent;
                parent = node;
                node = tmp;
            }

            // Case 3条件：叔叔是黑色，且当前节点是左孩子。
            setBlack(parent);
            setRed(gparent);
            rightRotate(gparent);
        } else {    //若“z的父节点”是“z的祖父节点的右孩子”
            // Case 1条件：叔叔节点是红色
            RBTNode<T> uncle = gparent.left;
            if ((uncle!=null) && isRed(uncle)) {
                setBlack(uncle);
                setBlack(parent);
                setRed(gparent);
                node = gparent;
                continue;
            }

            // Case 2条件：叔叔是黑色，且当前节点是左孩子
            if (parent.left == node) {
                RBTNode<T> 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)) &&
                (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)) &&
                (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<T> parent, RBTNode<T> left, RBTNode<T> 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) && isRed(parent)) {
            gparent = parentOf(parent);

            //若“父节点”是“祖父节点的左孩子”
            if (parent == gparent.left) {
                // Case 1条件：叔叔节点是红色
                RBTNode<T> uncle = gparent.right;
                if ((uncle!=null) && isRed(uncle)) {
                    setBlack(uncle);
                    setBlack(parent);
                    setRed(gparent);
                    node = gparent;
                    continue;
                }

                // Case 2条件：叔叔是黑色，且当前节点是右孩子
                if (parent.right == node) {
                    RBTNode<T> tmp;
                    leftRotate(parent);
                    tmp = parent;
                    parent = node;
                    node = tmp;
                }

                // Case 3条件：叔叔是黑色，且当前节点是左孩子。
                setBlack(parent);
                setRed(gparent);
                rightRotate(gparent);
            } else {    //若“z的父节点”是“z的祖父节点的右孩子”
                // Case 1条件：叔叔节点是红色
                RBTNode<T> uncle = gparent.left;
                if ((uncle!=null) && isRed(uncle)) {
                    setBlack(uncle);
                    setBlack(parent);
                    setRed(gparent);
                    node = gparent;
                    continue;
                }

                // Case 2条件：叔叔是黑色，且当前节点是左孩子
                if (parent.left == node) {
                    RBTNode<T> 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 < 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 待修正的节点
     */
    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)) &&
                    (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)) &&
                    (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) && (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);
    }

    /*
     * 销毁红黑树
     */
    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++;
        }
    }
}
    

链接：https://www.cnblogs.com/gaosheng-221/p/6133443.html

栈

先进后出(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--->" + queue.arrays[i]);

        //移动front
        i = (i + 1) % queue.arrays.length;
    }

}
    

动态队列

链表实现

树由根节点(root)和若干子树(T1,T2, … Tm-1)构成的具有层次关系的数据结构。

相关术语

节点的度 : 该节点子树个数，度为0的节点为叶子节点，度不为0的节点为分支节点

树的度 : 树中的节点的度最大值为树的度

节点的层次 : 根为第一层，往下依次递增

树的深度 : 节点层次最大值为树的深度

森林 : n棵不相交的树的集合为森林

二叉树

常用于实现二叉查找树、二叉堆

• 每个节点至多有两颗子树（树的度<=2）,子树分左右

• 第i层至多有2i-1个节点，深度为k的二叉树，最多节点数2^k-1个节点（具有最多节点的称作满二叉树），其中每个节点都与深度k满二叉树中1-n节点对应，则为完全二叉树

二叉排序树

• 左子树所有节点值小于根节点，右子树所有节点值大于根节点值
• 左右子树都是二叉排序树

二叉平衡树 AVL

• 左右子树深度差不超过1
• 左右子树都是二叉平衡树

哈夫曼树

最优二叉树

代码实现

哈夫曼编码

解决报文编码的问题，将字符串转换为唯一的二进制码，且二进制码的长度最小

每个字符在字符串中出现频率为W，其编码长度为L，编码字符n个，则编码后二进制码的总长度为W1L1+W2L2+…+WnLn，利用哈夫曼树特性求总长最小编码

B树

平衡的多路查找树

B树的阶：所有孩子节点树的最大值（m叉树：每个节点最多m棵子树）

分支节点最少有两颗子树

分支节点包含信息（n，A0，K1，A1，K2，A2，…，Kn，An），其中，n为结点中的关键字树，A为指向子树根结点的指针，K为关键字，且Ai-1所指子树中所有结点的关键字均小于Ki，An所指子树中所有结点的关键字均大于Kn；

所有的叶子结点都出现在同一层次上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空

B+树

B+树是应文件系统所需而出的一种B-树的变型树。一棵m阶B+树和m阶的B-树的差异在于

1. 有n棵子树的结点中含有n个关键字，每个关键字不保存数据，只用来索引，所有数据都保存在叶子节点；

2. 所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接

红黑树

红黑树，一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的简单路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因而是近似于平衡的。树中每个结点包含5个属性：color、key、left、right和p。如果一个结点没有子节点或父节点，则该结点相应的指针属性值为NIL，我们可以把这些NIL视为指向二叉搜索树的叶节点（外部结点）的指针，而把带关键字的结点视为树的内部结点。

性质

1. 每个结点或是红色的，或是黑色的
2. 根结点是黑色的
3. 每个叶结点（叶结点即指树尾端NIL指针或NULL结点）是黑的
4. 如果一个结点是红色的，则它的两个子结点都是黑色的
5. 对每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
6. 虽然本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)

键树

如果一个关键字可以表示成字符的序号，即字符串，那么可以用键树（keyword tree），又称数字搜索树或字符树，来表示这样的字符串的集合。键树的结构受启发于一部大型字典的“书边标目”。字典中标出首字母是 A，B，C，…，Z的单词所在页，再对各部分标出第二字母为A，B，C，…，Z的单词所在的页等等。
键树是一种特殊的查找树，它是一棵度大于等于2的树，树中的每个节点不是包含一个或几个关键字，而是只含有组成关键字的符号。
比如：如果关键字是数值，则节点中只包含一个数位；如果关键字是单词，则节点中只包含一个字母字符。根结点不代表任何字符，根以下第一层的结点对应于字符串的第一个字符，第二层的结点对应于字符串的第二个字符……每个字符串可由一个特殊的字符如“$”等作为字符串的结束符，用一个叶子结点来表示该特殊字符。把从根到叶子的路径上，所有结点（除根以外）对应的字符连接起来，就得到一个字符串。因此，每个叶子结点对应一个关键字。在叶子结点还可以包含一个指针，指向该关键字所对应的元素。整个字符串集合中的字符串的数目等于叶子结点的数目。如果一个集合中的关键字都具有这样的字符串特性，那么，该关键字集合就可采用这样一棵键树来表示。

键树的存储通常有两种方式：

1. 用树的孩子兄弟链来表示键树，称为双链树；每个Node有三个域：symbol域：存储关键字的一个字符；son域：存储指向第一棵子树的根的指针；brother域：存储指向右兄弟的指针。
2. 用多重链表来表示键树，称为Trie树或字典树。

字典树

如果以树的多重链表来表示键树，则树的每个结点应包含d个（d为关键字符的基，如：字符集由英文大写字母构成时，则d=26）指针域，此时的键树又称为字典树。
字典树典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。　
Tire树的三个基本性质：

1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符；
2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；
3. 每个节点的所有子节点包含的字符都不相同。
   Tire树的应用：
4. 串的快速检索
   给出N个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。在这道题中，我们可以用数组枚举，用哈希，用字典树，先把熟词建一棵树，然后读入文章进行比较，这种方法效率是比较高的。
5. “串”排序
   给定N个互不相同的仅由一个单词构成的英文名，让你将他们按字典序从小到大输出。用字典树进行排序，采用数组的方式创建字典树，这棵树的每个结点的所有儿子很显然地按照其字母大小排序。对这棵树进行先序遍历即可。
6. 最长公共前缀

后缀树

所谓后缀树，就是包含一则字符串所有后缀的压缩了的字典树。先说说后缀的定义。给定一长度为n的字符串S=S1S2..Si..Sn，和整数i，1 <= i <= n，子串SiSi+1…Sn都是字符串S的后缀。以字符串S=XMADAMYX为例，它的长度为8，所以S[1..8],S[2..8], … , S[8..8]都算S的后缀，我们一般还把空字串也算成后缀。这样，我们一共有如下后缀。对于后缀S[i..n]，我们说这项后缀起始于i。
键树只适合前缀匹配和全字匹配，并不适合后缀和子串匹配，而后缀树在这方面则非常合适。它与键树的最大不同在于，后缀树的单词集合是由指定字符串的后缀子串构成。

区间树与线段树

区间树是在红黑树基础上进行扩展得到的支持以区间为元素的动态集合的操作，其中每个节点的关键值是区间的左端点。通过建立这种特定的结构，可是使区间的元素的查找和插入都可以在O(lgn)的时间内完成。相比于基础的红黑树数据结构，增加了一个max[x]，即以x为根的子树中所有区间的端点的最大值。
线段树是一种平衡二叉查找树，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。主要的处理思想是基于分治的思想。
设根节点的区间为[a,b),区间长度为L = b - a，线段树的性质：
1）线段树是一个平衡树，树的高度为log(L)；
2）线段树把区间上的任意长度为L的线段都分成不超过2log(L)线段。

败者树与胜者树

胜者树和败者树都是完全二叉树，是树形选择排序的一种变型。在胜者树、败者树中，每个叶子结点相当于一个选手，每个中间结点相当于一场比赛，每一层相当于一轮比赛。不同的是，胜者树中的每个非终端结点均表示其左、右孩子结点中的“胜者”；而在败者树中，父结点中记下刚进行完的这场比赛中的败者，而让胜者去参加更高一层的比赛

哈夫曼树代码实现

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
 
public class HuffmanTree {
 
    public static class Node<E> {
        E data;
        double weight;
        Node leftChild;
        Node rightChild;
 
        public Node(E data, double weight) {
            super();
            this.data = data;
            this.weight = weight;
        }
 
        public String toString() {
            return "Node[data=" + data + ", weight=" + weight + "]";
        }
    }
 
    public static void main(String[] args) {
        List<Node> nodes = new ArrayList<Node>();
 
        nodes.add(new Node("A", 40.0));
        nodes.add(new Node("B", 8.0));
        nodes.add(new Node("C", 10.0));
        nodes.add(new Node("D", 30.0));
        nodes.add(new Node("E", 10.0));
        nodes.add(new Node("F", 2.0));
        
        Node root = HuffmanTree.createTree(nodes);
        
        System.out.println(breadthFirst(root));
 
    }
 
    /**
     * 构造哈夫曼树
     * 
     * @param nodes
     *            节点集合
     * @return 构造出来的哈夫曼树的根节点
     */
    private static Node createTree(List<Node> nodes) {
        // 只要nodes数组中还有2个以上的节点
        while (nodes.size() > 1) {
            quickSort(nodes);
            //获取权值最小的两个节点
            Node left = nodes.get(nodes.size()-1);
            Node right = nodes.get(nodes.size()-2);
            
            //生成新节点，新节点的权值为两个子节点的权值之和
            Node parent = new Node(null, left.weight + right.weight);
            
            //让新节点作为两个权值最小节点的父节点
            parent.leftChild = left;
            parent.rightChild = right;
            
            //删除权值最小的两个节点
            nodes.remove(nodes.size()-1);
            nodes.remove(nodes.size()-1);
            
            //将新节点加入到集合中
            nodes.add(parent);
        }
        
        return nodes.get(0);
    }
 
    /**
     * 将指定集合中的i和j索引处的元素交换
     * 
     * @param nodes
     * @param i
     * @param j
     */
    private static void swap(List<Node> nodes, int i, int j) {
        Node tmp;
        tmp = nodes.get(i);
        nodes.set(i, nodes.get(j));
        nodes.set(j, tmp);
    }
 
    /**
     * 实现快速排序算法，用于对节点进行排序
     * 
     * @param nodes
     * @param start
     * @param end
     */
    private static void subSort(List<Node> nodes, int start, int end) {
        if (start < end) {
            // 以第一个元素作为分界值
            Node base = nodes.get(start);
            // i从左边搜索，搜索大于分界值的元素的索引
            int i = start;
            // j从右边开始搜索，搜索小于分界值的元素的索引
            int j = end + 1;
            while (true) {
                // 找到大于分界值的元素的索引，或者i已经到了end处
                while (i < end && nodes.get(++i).weight >= base.weight)
                    ;
                // 找到小于分界值的元素的索引，或者j已经到了start处
                while (j > start && nodes.get(--j).weight <= base.weight)
                    ;
 
                if (i < j) {
                    swap(nodes, i, j);
                } else {
                    break;
                }
            }
 
            swap(nodes, start, j);
 
            //递归左边子序列
            subSort(nodes, start, j - 1);
            //递归右边子序列
            subSort(nodes, j + 1, end);
        }
    }
    
    public static void quickSort(List<Node> nodes){
        subSort(nodes, 0, nodes.size()-1);
    }
    
    //广度优先遍历
    public static List<Node> breadthFirst(Node root){
        Queue<Node> queue = new ArrayDeque<Node>();
        List<Node> list = new ArrayList<Node>();
        
        if(root!=null){
            //将根元素加入“队列”
            queue.offer(root);
        }
        
        while(!queue.isEmpty()){
            //将该队列的“队尾”元素加入到list中
            list.add(queue.peek());
            Node p = queue.poll();
            
            //如果左子节点不为null，将它加入到队列
            if(p.leftChild != null){
                queue.offer(p.leftChild);
            }
            
            //如果右子节点不为null，将它加入到队列
            if(p.rightChild != null){
                queue.offer(p.rightChild);
            }
        }
        
        return list;
    }
}

概念

图是由顶点集（VertexSet）和边集（EdgeSet）组成，针对图G，顶点集和边集分别记为V(G)和E(G)。依据图的边集是否为有向，可把图分为有向图和无向图，根据图是否有权重，可以分为有权图和无权图

术语

1. 邻接点-在一个无向图中，若存在一条边<Vi,Vj>，则称Vi，Vj为此边的两个端点，并称它们互为邻接点
2. 出/入边-在一个有向图张，若存在一条边<Vi,Vj>，则称此边为顶点Vi的出边，顶点Vj的一条入边
3. 度/入度/出度-无向图中的度定义为以该顶点为一个端点的边的数目，记为D(V)。有向图的入度定为多少边指向该顶点，出度是该顶点出边的个数

邻接矩阵

邻接矩阵是表示图形中顶点之间相邻关系的矩阵，对于n个顶点的图而言，矩阵是的row和col表示的是1....n个点。对于无向图 如果顶点b1和b2是连接的，那么在二维矩阵中matrix[b1,b2]和matrix[b2,b1]位置的值置为1，如果是有向图b1指向b2，那么 matrix[b1,b2]=1,matrix[b2,b1]=0；下面用一个例子表示无向图和有向图的邻接矩阵；

如果图是一个带权图，需要把1换为相应边上的权值，把非对角线上的换成一个很大的特定的实数则可，表示相应的边不存在，这个特定的实数通常用无穷大或MaxValue来表示，他要大于图G中所有边的权值

代码实现

邻接表

邻接矩阵与邻接表相比，它会造成空间的一定损失，它需要为每个顶点都分配n个边的空间，其实有很多边都是不存在边，但是邻接表的实现就不一样，它只关心存在的边，不关心不存在的边。邻接表由数组+链表组成对于上面的无向图，邻接表表示为（由于有向和无向的差别不是太大，所以只是画出了无向的邻接表表示）

代码实现

代码实现

邻接矩阵实现

package Graph;
//边集数组 ，存放边的信息
//邻域数组表示  和 邻域表表示  是两种不同的表示方式
//表示的是插入边的元素，边的起点和终点  边的权重
public class EdgeElement {
    int fromvex;
    int endvex;
    int weight;
    
    public EdgeElement(int v1,int v2){
        //对于无权重图的初始化
        fromvex=v1;
        endvex=v2;
        weight=1;
    }
    public EdgeElement(int v1,int v2,int wgt){
        //对于有权重图的初始化
        fromvex=v1;
        endvex=v2;
        weight=wgt;
    }	
}


package Graph;
//可以通过边集来得到一个图的构成
public interface Graph {
    void creatGraph(EdgeElement d[]);		//通过边结点来构建一个图
    GraphType graphType();				//返回图的类型  无向无权图 无向有权图  有向无权图  有向有权图 定义一个枚举变量
    int vertices();					//返回图的顶点数
    int edges();					//返回图的边数
    boolean find(int i,int j);			//从图中查找一条边(i,j)是否存在
    void putEdge(EdgeElement theEdge);		//像图中插入一条边 theEdge
    void removeEdge(int i,int j);			//从图中删除一条边
    int degree(int i);				//返回顶点i的度
    int inDegree(int i);				//返回顶点i的入度
    int outDegree(int i);				//返回顶点i的出度
    void output();					//以图的顶点集和边集的形式输出一个图
    void depthFirstSearch(int v);			//从顶点v开始深度优先搜索整幅图
    void breadthFirstSearch(int v);			//从顶点v开始广度优先搜索整幅图
}

//在邻域数组中写数据
public void creatGraph(EdgeElement[] d) {
    int i;
    for(i=0;i<d.length;i++){
        if(d[i]==null) break;
        int v1,v2;
        v1=d[i].fromvex;
        v2=d[i].endvex;
        if(v1<0 || v1>n-1 || v2<0 || v2>n-1 || v1==v2){
            System.out.println("边的顶点序号无效，退出运行");
            System.exit(0);
        }
        if(type==GraphType.NoDirectionNoWeight){
            a[v1][v2]=a[v2][v1]=1;
        }else if(type==GraphType.NoDirectionWeight){
            a[v1][v2]=a[v2][v1]=d[i].weight;
        }else if(type==GraphType.DirectionNoWeight){
            a[v1][v2]=1;
        }else{
            a[v1][v2]=d[i].weight;
        }
    }
    e=i;			//边的数目
}

public void putEdge(EdgeElement theEdge) {
    int v1,v2;
    v1=theEdge.fromvex;
    v2=theEdge.endvex;
    if(v1<0 || v1>n-1 || v2<0 || v2>n-1 || v1==v2){
        System.out.println("边的顶点序号无效，退出运行！");
        System.exit(0);
    }
    if(a[v1][v2]==0 || a[v1][v2]==MaxValue) e++;		//边数e的值加一
    if(type==GraphType.NoDirectionNoWeight || type==GraphType.NoDirectionWeight){
        if(type==GraphType.NoDirectionNoWeight){
            a[v1][v2]=a[v2][v1]=1;
        }else{
            a[v1][v2]=a[v2][v1]=theEdge.weight;
        }
    }else{
        if(type==GraphType.DirectionNoWeight) a[v1][v2]=1;
        else{
            a[v1][v2]=theEdge.weight;
        }
    }
}

public void removeEdge(int i, int j) {
    if(i<0 || i>n-1 || j<0 || j>n-1 || i==j){
        System.out.println("边的顶点序号无效，退出运行！");
        System.exit(0);
    }
    if(a[i][j]==0 || a[i][j]==MaxValue){
        System.out.println("要删除的边不存在，退出运行！");
        System.exit(0);			
    }
    if(type==GraphType.NoDirectionNoWeight){
        a[i][j]=a[j][i]=0;
    }else if(type==GraphType.NoDirectionWeight){
        a[i][j]=a[j][i]=MaxValue;
    }else if(type==GraphType.DirectionNoWeight){
        a[i][j]=0;
    }else a[i][j]=MaxValue;
    e--;
}

//得到该结点的度
public int degree(int i) {
    if(i<0 || i> n-1){
        System.out.println("参数的顶点序号值无效，退出运行");
        System.exit(0);
    }
    int k=0;
    if(type==GraphType.NoDirectionNoWeight || type==GraphType.NoDirectionWeight){
        for(int j=0;j<n;j++){
            if(a[i][j]!=0 && a[j][i]!=MaxValue) k++;
            
        }
    }else{
        k = inDegree(i)+outDegree(i);
    }
    return k;
}
//入度
public int inDegree(int i) {					
    if(i<0 || i> n-1){
        System.out.println("参数的顶点序号值无效，退出运行");
        System.exit(0);
    }
    if(type==GraphType.NoDirectionNoWeight || type==GraphType.NoDirectionWeight){
        return -1;
    }
    int k=0;
    for(int j=0;j<n;i++){
        if(a[j][i]!=0 && a[j][i]!=MaxValue) k++;
    }
    return k;
}
//出度
public int outDegree(int i) {
    if(i<0 || i> n-1){
        System.out.println("参数的顶点序号值无效，退出运行");
        System.exit(0);
    }
    if(type==GraphType.NoDirectionNoWeight || type==GraphType.NoDirectionWeight){
        return -1;
    }
    int k=0;
    for(int j=0;j<n;i++){
        if(a[i][j]!=0 && a[i][j]!=MaxValue) k++;
    }
    return k;
}

//输出
public void output() {
    int i,j;
    System.out.print("V={");//输出顶点集合
    for(i=0;i<n-1;i++){
        System.out.print(i+",");
    }
    System.out.print(n-1+"}");//输出顶点集合
    //输出边集合
    System.out.print("E={");
    if(type==GraphType.NoDirectionNoWeight || type==GraphType.DirectionNoWeight){
        for(i=0;i<n;i++){
            for(j=0;j<n;j++){
                if(a[i][j]!=0 && a[i][j]!=MaxValue){
                    if(type==GraphType.NoDirectionNoWeight){
                        if(i<j)System.out.print("("+i+","+j+"),");
                    }else{
                        System.out.print("<"+i+","+j+">");
                    }
                }
            }
        }
    }else{
        for(i=0;i<n;i++){
            for(j=0;j<n;j++){
                if(a[i][j]!=0 && a[i][j]!=MaxValue){
                    if(type==GraphType.NoDirectionWeight){
                        if(i<j)System.out.print("("+i+","+j+")"+a[i][j]+",");
                    }else System.out.print("<"+i+","+j+">"+a[i][j]+",");
                }
            }
        }
    }
    System.out.print("}");
}

//深度优先进行搜索   是从哪个顶点开始遍历，这里可以用顶点序号表示顶点
public void depthFirstSearch(int v) {		//驱动函数
    boolean visited[]=new boolean[n];
    for(int i=0;i<n;i++){
        visited[i]=false;
    }
    dfs(v,visited);							//把每个结点遍历一次。
    System.out.println();
}
//进行深度优先搜索的内部递归方法使用
private void dfs(int i,boolean visited[]){	//工作函数
    System.out.print(i+" ");
    visited[i]=true;
    for(int j=0;j<n;j++){
        if(a[i][j]!=0 && a[i][j]!=MaxValue && !visited[j]){
            dfs(j,visited);
        }
    }
}

邻接表实现

package GraphLink;
//定义邻接表类型
public class EdgeNode{
    //需要一个存储自身结点
    int adjvex;
    int weight;
    EdgeNode next;
    //无权图
    public EdgeNode(int adj,EdgeNode nt){
        this.adjvex=adj;
        this.next=nt;
        this.weight=1;
    }
    //有权图
    public EdgeNode(int adj,int wgt,EdgeNode nt){
        this.adjvex=adj;
        this.weight=wgt;
        this.next=nt;
    }
}

//生成图函数
@Override
public void creatGraph(EdgeElement[] d) {
    int i;
    for(i=0;i<d.length;i++){//处理边集合  如果边集合重复 那程序不就有问题了么  这点要处理
        if(d[i]==null) break;
        int v1,v2,weight;
        v1=d[i].fromvex;
        v2=d[i].endvex;
        weight=d[i].weight;
        if(v1<0||v1>n-1||v2<0||v2>n-1||v1==v2){
            System.out.println("边的顶点序号无效，退出运行");
            System.exit(0);
        }
        if(type==GraphType.NoDirectionNoWeight){//处理无方向 无权重的图
            a[v1]=new EdgeNode(v2,a[v1]);//把边挂载在主干上,a为EdgeNode类型的一维数组
            a[v2]=new EdgeNode(v1,a[v2]);//处理第二条边
        }else if(type==GraphType.NoDirectionWeight){//处理无向有权图
            a[v1]=new EdgeNode(v2,weight,a[v1]);
            a[v2]=new EdgeNode(v1,weight,a[v2]);
        }else if(type==GraphType.DirectionNoWeight){//处理有向无权图
            a[v1]=new EdgeNode(v2,a[v1]);
        }else {
            a[v1]=new EdgeNode(v2,weight,a[v1]);
        }
    }
    e=i;
}

//在图中查找一条边
public boolean find(int v1,int v2){
    if(v1<0||v1>n-1||v2<0||v2>n-1||v1==v2){
        System.out.println("边的顶点序号无效，退出运行");
        System.exit(0);
    }
    EdgeNode p=a[v1];
    while(p!=null){
        if(p.adjvex==v2){
            return true;
        }
        p=p.next;
    }
    return false;
}

//向图中插入一条边
public void putEdge(EdgeElement theEdge){
    int v1,v2,weight;
    v1=theEdge.fromvex;
    v2=theEdge.endvex;
    weight=theEdge.weight;
    if(v1<0||v1>n-1||v2<0||v2>n-1||v1==v2){
        System.out.println("边的顶点序号无效，退出运行");
        System.exit(0);
    }
    EdgeNode p=a[v1];
    while(p!=null){
        if(p.adjvex==v2){
            break;//退出后处理
        }
        p=p.next;
    }
    if(p==null) e++;
    else{
        if(type==GraphType.DirectionWeight || type==GraphType.NoDirectionWeight){
            p.weight=weight;
        }
        if(type==GraphType.NoDirectionWeight){//无向有权重的另一条边也要处理
            EdgeNode q=a[v2];
            while(q!=null){
                if(q.adjvex==v1) break;
                q=q.next;
            }
            q.weight=weight;
        }
        return;
    }
    if(type==GraphType.NoDirectionNoWeight){//如果是无向无权重
        a[v1]=new EdgeNode(v2, a[v1]);
        a[v2]=new EdgeNode(v1, a[v2]);
    }else if(type==GraphType.NoDirectionWeight){//处理无向有权重
        a[v1]=new EdgeNode(v2,weight,a[v1]);
        a[v2]=new EdgeNode(v1,weight,a[v2]);
    }else if(type==GraphType.DirectionNoWeight){//有向无权重
        a[v1]=new EdgeNode(v2,a[v1]);
    }else{
        a[v1]=new EdgeNode(v2, weight,a[v1]);
    }
}

public void removeEdge(int v1,int v2){
    if(v1<0||v1>n-1||v2<0||v2>n-1||v1==v2){
        System.out.println("边的顶点序号无效，退出运行");
        System.exit(0);
    }
    EdgeNode p=a[v1],q=null;//拿到主干结点
    while(p!=null){
        if(p.adjvex==v2) break;
        q=p;
        p=p.next;
    }
    if(p==null){
        System.out.println("要删除的边不存在，程序退出运行");
        System.exit(0);
    }
    if(q==null){//该结点在表头上 主干的节点就是需要找的结点
        a[v1]=a[v1].next;
    }else{
        q.next=p.next;//嫁接上
    }
    //删除无向图的另一个结点上的边
    if(type==GraphType.NoDirectionNoWeight||type==GraphType.NoDirectionWeight){
        EdgeNode p1=a[v2],q1=null;
        while(p1!=null){
            if(p1.adjvex==v1){
                break;
            }
            q1=p1;
            p1=p1.next;
        }
        if(q1==null){
            a[v2]=a[v2].next;
        }else{
            q1.next=p1.next;
        }
    }
    e--;
}

//返回一个顶点的度，度分为入度和出度，要分别处理
public int degree(int i){
    if(i<0||i>n-1){
        System.out.println("顶点超过了范围，程序退出运行");
        System.exit(0);			
    }
    int k=0;
    if(type==GraphType.NoDirectionNoWeight||type==GraphType.NoDirectionWeight){
        EdgeNode p=a[i];
        while(p!=null){
            k++;
            p=p.next;
        }
        return k;
    }else return inDegree(i)+outDegree(i);
}
//求出并返回一个顶点的入度
public int inDegree(int i){//返回指向该顶点的度，入度，用双循环来实现
    int k=0;//记录入度个数
    if(i<0||i>n-1){
        System.out.println("顶点超过了范围，程序退出运行");
        System.exit(0);			
    }
    if(type==GraphType.NoDirectionNoWeight||type==GraphType.NoDirectionWeight){
        return -1;
    }else{
        for(int j=0;j<n;j++){
            EdgeNode p=a[j];
            while(p!=null){
                if(p.adjvex==i)k++;
                p=p.next;
            }
        }
    }
    return k;
}
//返回一个顶点的出度
public int outDegree(int i){
    int k=0;//记录出度的数目
    EdgeNode p=a[i];
    while(p!=null){
        k++;
        p=p.next;
    }
    return k;
}

//得到邻接矩阵
public int[][] getAdjacencyMatrix(){
    int adjacencyMatrix[][]=new int[n][n];
    if(type==GraphType.DirectionNoWeight||type==GraphType.DirectionWeight){//有向性
        //有向 那不存在的边是存在一个InfinityValue
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(i==j) adjacencyMatrix[i][j]=0;
                else adjacencyMatrix[i][j]=InfinityValue;
            }
        }
    }else{
        //无向 都设置为0
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                 adjacencyMatrix[i][j]=0;
            }
        }			
    }
        //遍历整个图
        for(int i=0;i<n;i++){
            EdgeNode p=a[i];
            while(p!=null){
                adjacencyMatrix[i][p.adjvex]=p.weight;
                p=p.next;
            }
        }	
    return adjacencyMatrix;
}