Java学习-Day14

Hanoi 塔问题

一、描述

有三根杆子A, B, C. A 杆上有 N 个 ( N > 1 ) 穿孔圆盘, 盘的尺寸由下到上依次变小. 要求按下列规则将所有圆盘移至 C 杆: 每次只能移动一个圆盘; 大盘不能叠在小盘上面.

提示: 可将圆盘临时置于 B 杆, 也可将从 A 杆移出的圆盘重新移回 A 杆, 但都必须遵循上述两条规则.

问: 如何移? 最少要移动多少次 ?

二、思考

在数据结构中, 一般把 Hanoi 塔放到栈这一章. 但我觉得, 将其展开更像是二叉树, 也有点三叉的味道.

最后还不是依靠递归来完成. 最简单的就是只有一个圆盘, 这样直接可以从 A 移动到 C. 当圆盘数 N 大于 1 时(N > 1)可以把只除去最后一个的剩余圆盘作为一个整体, 使它通过 C 移动到 B , 然后最后一个圆盘从 A 移动到 C. 这样问题就转换成了 N - 1 个圆盘从 B 经过 A 移动到 C 上.

三、具体实现

输入

三个字符代表杆, 一个整数代表需要移动的圆盘. 初始状态如下所示 

1
2
3
4
paraSource      需要移动的圆盘所在杆 整个函数开始初始为 A 杆
paraIntermedium 移动圆盘用作缓存的杆 整个函数开始初始为 B 杆
paraDestination 圆盘最终需要到达的杆 整个函数开始初始为 C 杆
paraNumber      需要移动圆盘的数量   整个函数开始初始为 3

输出

依照 Hanoi 规则输出的圆盘移动顺序

1. 完整代码

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
package datastructure.tree;

/**
 * Hanoi tower.
 * 
 * @author Shihuai Wen Email:wshysxcc@outlook.com
 */
public class Hanoi {

	/**
	 *********************
	 * Move a number of plates.
	 * 
	 * @param paraSource      The source pole.
	 * @param paraIntermedium The intermediary pole.
	 * @param paraDestination The destination pole.
	 * @param paraNumber      The number of plates.
	 *********************
	 */
	public static void hanoi(char paraSource, char paraIntermediary, char paraDestination, int paraNumber) {
		if (paraNumber == 1) {
			System.out.println(paraSource + "->" + paraDestination + " ");
			return;
		} // Of if

		hanoi(paraSource, paraDestination, paraIntermediary, paraNumber - 1);
		System.out.println(paraSource + "->" + paraDestination + " ");
		hanoi(paraIntermediary, paraSource, paraDestination, paraNumber - 1);

	}// Of hanoi

	/**
	 *********************
	 * The entrance of the program.
	 * 
	 * @param args Not used now.
	 *********************
	 */
	public static void main(String args[]) {
		hanoi('A', 'B', 'C', 3);
	}// Of main

} // Of class Hanoi

2. 运行截图

Huffman 编码 (节点定义与文件读取)

一、概念

哈夫曼编码 ( Huffman Coding ), 又称霍夫曼编码, 是一种编码方式, 哈夫曼编码是可变字长编码 ( VLC ) 的一种. Huffman 于 1952 年提出一种编码方法, 该方法完全依据字符出现概率来构造异字头的平均长度最短的码字, 有时称之为最佳编码, 一般就叫做 Huffman 编码（有时也称为霍夫曼编码）.

二、变量释义

每个节点的内容包括: 字符 (仅对叶节点有效)、权重 (用的整数, 该字符的个数)、指向子节点父节点的引用. 这里指向父节点的引用是必须的.

NUM_CHARS 是指 ASCII 字符集的字符个数. 为方便起见, 仅支持 ASCII.

inputText 的引入只是想把程序尽可能细分成独立的模块, 这样便于学习和调拭. 用于存储输入的字符串, 使得程序可以处理多种情况.

alphabet 仅存 inputText 出现过的字符.

alphabetLength 完全可以用 alphabet.length() 代替.

charCounts 要为所有的节点负责, 其元素对应于 HuffmanNode 里面的 weight. 为了节约, 可以把其中一个省掉.

charMapping 是为了从 ASCII 里面的顺序映射到 alphabet 里面的顺序. 这也是我只采用 ASCII 字符集 (仅 256 字符) 的原因.

huffmanCodes 将个字符映射为一个字符串, 其实应该是二进制串. 我这里不是想偷懒么.

nodes 要先把所有的节点存储在一个数组里面, 然后再链接它们. 这是常用招数. 构造方法仅初始化了 charMapping, 读入了文件.

readText 采用了最简单粗暴的方式. 还可以有其它的逐行读入的方式.

要自己弄个文本文件, 里面存放一个字符串 abcdedgsgs 之类, 或者几行英文文本.

三、本节代码

定义 Huffman 树及其节点, 编写其构造函数及其从文件读取字符串.

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

import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.stream.Collectors;

/**
 * Huffman tree, encoding, and decoding. For simplicity, only ASCII characters
 * are supported.
 * 
 * @author Shihuai Wen Email:wshysxcc@outlook.com
 */
public class Huffman {
	/**
	 * An inner class for Huffman nodes.
	 */
	class HuffmanNode {
		/**
		 * The char. Only valid for leaf nodes.
		 */
		char character;

		/**
		 * Weight. It can also be double.
		 */
		int weight;

		/**
		 * The left child.
		 */
		HuffmanNode leftChild;

		/**
		 * The right child.
		 */
		HuffmanNode rightChild;

		/**
		 * The parent. It helps constructing the Huffman code of each character.
		 */
		HuffmanNode parent;

		/**
		 ******************* 
		 * The first constructor
		 ******************* 
		 */
		public HuffmanNode(char paraCharacter, int paraWeight, HuffmanNode paraLeftChild, HuffmanNode paraRightChild,
				HuffmanNode paraParent) {
			character = paraCharacter;
			weight = paraWeight;
			leftChild = paraLeftChild;
			rightChild = paraRightChild;
			parent = paraParent;
		}// Of HuffmanNode

		/**
		 ******************* 
		 * To string.
		 ******************* 
		 */
		public String toString() {
			String resultString = "(" + character + ", " + weight + ")";

			return resultString;
		}// Of toString

	}// Of class HuffmanNode

	/**
	 * The number of characters. 256 for ASCII.
	 */
	public static final int NUM_CHARS = 256;

	/**
	 * The input text. It is stored in a string for simplicity.
	 */
	String inputText;

	/**
	 * The length of the alphabet, also the number of leaves.
	 */
	int alphabetLength;

	/**
	 * The alphabet.
	 */
	char[] alphabet;

	/**
	 * The count of chars. The length is 2 * alphabetLength - 1 to include non-leaf
	 * nodes.
	 */
	int[] charCounts;

	/**
	 * The mapping of chars to the indices in the alphabet.
	 */
	int[] charMapping;

	/**
	 * Codes for each char in the alphabet. It should have the same length as
	 * alphabet.
	 */
	String[] huffmanCodes;

	/**
	 * All nodes. The last node is the root.
	 */
	HuffmanNode[] nodes;

	/**
	 *********************
	 * The first constructor.
	 * 
	 * @param paraFilename The text filename.
	 *********************
	 */
	public Huffman(String paraFilename) {
		charMapping = new int[NUM_CHARS];

		readText(paraFilename);
	}// Of the first constructor

	/**
	 *********************
	 * Read text.
	 * 
	 * @param paraFilename The text filename.
	 *********************
	 */
	public void readText(String paraFilename) {
		try {
			inputText = Files.newBufferedReader(Paths.get(paraFilename), StandardCharsets.UTF_8).lines()
					.collect(Collectors.joining("\n"));
		} catch (Exception ee) {
			System.out.println(ee);
			System.exit(0);
		} // Of try

		System.out.println("The text is:\r\n" + inputText);
	}// Of readText

	/**
	 *********************
	 * The entrance of the program.
	 * 
	 * @param args Not used now.
	 *********************
	 */
	public static void main(String args[]) {
		Huffman tempHuffman = new Huffman("D:/wenshihuai/huffmantext-small.txt");
	}// Of main

} // Of class Huffman

四、运行截图

总结

对我来说比较难理解的时读取文件那一部分. 其实就是对 JDK 的各种函数不熟悉. 读取文件那个函数也就是以字符流的形式读取文件, 然后读取每行字符串并用换行符拼接.

还是需要多写多练多熟悉.