java数据结构
利用哈夫曼编码进行信息通讯可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数 据进行译码(复原)。对于双工信道 (即可以双向传输信息的信道)，每端都需要一个完整的编 /译码系统。试对于任意的一段文本（可能是直接输入的，也可能是保存在本地文件中或者 网络上的)，写一个哈夫曼码的编译码系统。
(1)哈夫曼编码 在初始化的过程中间，要用户输入的字符建立哈夫曼树并求得哈夫曼编码。先将输入的字符和权值存放到一个优先队列中，再建立哈夫曼树，根据树分布求得哈夫曼编码。 (2)串的匹配 在编码的过程中间，要对已经编码过的代码译码,可利用循环，将代码中的与哈夫曼编码的长度相同的串与这个哈夫曼编码比较，如果相等就回显。 (3)二叉树的遍历 在打印哈夫曼树(T)的过程中，因为哈夫曼树也是二叉树，所以就要利用二叉树的中序遍历将哈夫曼树输出。 (4)构建哈夫曼树的贪婪数算 1.从由树构建的森林开始。每棵树都包含一个字符的结点。每个节点的权重就是文本中字符的出现次数。 2.重复这个步骤直到只有一棵树为止： 选择两颗最小权重的树，创建一个新的字符节点。这棵树的权重就是两颗子树权重之和。 对于每个内部结点，给它左边赋值0，右边赋值1。所有的叶子节点都表示文本的字符。
一副牌中抽去大小王剩下 52 张（如果初练也可只用 1～10 这 40 张牌)，任意抽取 4 张 牌（称牌组)，用加、减、乘、除（可加括号)把牌面上的数算成 24。每张牌必须用一次且只 能用一次，如抽出的牌是 3、8、8、9，那么算式为（9-8)×8×3 或 3×8+（9-8)或（9- 8÷8)×3 等。 本题主要考查栈、集合、数组、递归、穷举等知识。
算法可逐步求解如下：
现有三个集合
集合1={N1, N2, N3, N4},
集合2={op1, op2, op3},
集合3={"(", ")"}
N1,N2,N3,N4可以是1-13中的任意一个数字，op1,op2,op3可以是"+","-","","/"中的任意一个操作符
(1)首先从集合1中随机抽取一个元素，并删除抽取出来的元素，然后再从集合2中随机抽取一个元素组成字符数组；
(2)重复第一步操作，直到集合1为空，集合1为空时不再从集合2中抽取元素，最后得到的表达式表示如下所示：
expression = N1 op1 N2 op2 N3 op3 N4
(3)将集合3的元素组合插入到表达式expression中，这样的话，根据排列和组合原理，将会得到C41C31C21C11C41C41C4110=4!44410个合法的表达式，然后逐一分析这些表达式是否已经重复出现，然后再逐一将这些表达式转换成实际的数学运算式，并计算结果，判断计算结果是否等于24。
//所有花色不重复的组合
for (int i = 1; i <= 13; i++) {
for (int j = i; j <= 13; j++) {
for (int k = j; k <= 13; k++) {
for (int l = k; l <= 13; l++) {
List<Integer> temp = new ArrayList<>();
temp.add(i);
temp.add(j);
temp.add(k);
temp.add(l);
listOfDiffColor.add(temp);
}
}
}
}
不考虑花色仅考虑牌面数字，每次抽取四张牌，共有1820种组合情况。
由于运算符号尚未确定，即使是同样的四张牌，不同的排序也会得到不同的运算结果，因此每四张牌的组合情况也要考虑。 即为四个数字的全排序：
public void getNumArrays(int[] array,int begin,int end){
if(end == begin){ //一到递归的出口就输出数组，此数组为全排列
//sentence[count] = "";
for(int i=0;i<=end;i++){
num[count][i] = array[i];
//System.out.print(array[i]+" ");
}
count++;
//System.out.println();
return;
}
else{
for(int j=begin;j<=end;j++){
swap(array,begin,j); //for循环将begin~end中的每个数放到begin位置中去
getNumArrays(array,begin+1,end); //假设begin位置确定，那么对begin+1~end中的数继续递归
swap(array,begin,j); //换过去后再还原
}
}
}
因此每组数据有 4！ = 24 种情况。
private String[] str = {"+","-","*","/"};
一共有四种运算符号，可重复出现，每四个数据可以抽取三个运算符号。
public void getChars(){
int count1 = 0;
for(int i=0;i<str.length;i++){
for(int j=0;j<str.length;j++){
for(int k=0;k<str.length;k++){
int index = 0;
chars[count1][index++] = str[i];
chars[count1][index++] = str[j];
chars[count1++][index] = str[k];
}
}
}
}
所以运算符号共有 4^3 = 64 种情况。
private String[] ch = {"(", ")"};
//用数组标识括号可能出现的位置
private int[][] index1 = {{0, 4}, {2, 6}, {4, 8}, {0, 6}, {2, 8}};
private int[][][] index2 = {
{{0, 6}, {1, 5}},
{{0, 6}, {3, 7}},
{{2, 8}, {3, 7}},
{{2, 8}, {5, 9}},
{{0, 4}, {6, 10}}};
所以插入括号的情况共有10种。
由上述分析可知共有1820 * 24 * 64 * 10 = 2795520 种组合方式。
但是在这2795520组组合方式之中是存在大量重复的，比如 (7/1)-2/1 与 (7/1)-(2/1) 是等价的。 因此要考虑去重的问题。虽然是重复在做很多人以前做过的工作，但还是有些自认为别出心裁的思路，因为并没从代数形式上做分析，而是通过试数的办法做的，试的是π、e、lnπ和arctan e这四个超越数，对近似值做比较（浮点数运算总是有误差的）来判断两个表达式是否等价。
//设置对应的超越数
public void setMap(int[] num){
map.put(num[0],Math.PI);
map.put(num[1],Math.E);
map.put(num[2],Math.log(Math.PI));
map.put(num[3],Math.atan(Math.E));
}
去重时注意数据要和超越数一一对应。
最后利用Stack计算表达式，并判断结果是否等于24即可。
教材中的 9 枚硬币问题使用的是 3 3 的矩阵，假设在一个 4 4 的矩阵中放置了 16 枚硬 币。该问题可进一步变化为如 2 3，2 4，3 4 等等任意结构的情形。 本题主要考查对图的结构和图的广度优先遍历操作的掌握。
将这个问题抽象成为一个图问题。 因为这个4＊4的矩阵所有的状态是有限的，每个硬币只可能是正和反，所以矩阵所有的状态为 2^16 = 65536。那么，就可以对每个状态进行编码，将每个状态对应为一个二进制数。正好是0～65535。而在这些状态中，每一个状态只能向固定的另外几个状态发生转变。在这些条件下，就可以进行抽象了。将这65536个状态看作是图中的顶点，而从一个状态到另外一个状态的转变可以看作是这两个顶点间的边。在对状态进行编码的时候，最终状态因为是每一个硬币朝向都一致，所以是65535= （1111111111111111）。所以从某一个状态通过一些翻转到最终状态的过程可以看作是，在图中的某一点找到一条路径达到编号为65535顶点的。因为这一个边无权重的图，所以只是一个搜索问题。用广度优先搜索就可以解决这个问题。
线性表、树、图的操作和演示
使用数组来实现MyArrayList，再对MyArrayList进行增删改查。MyLinkedList的算法设计也相似。MyStack找到第一个元素的下标进行插入，和最后一个元素的下标进行删除。MyQueue通过对队列的首尾位置的元素进行改变达到出队和入队的效果。BinaryTree里面的每个元素都是一个Node，并且每个元素都有左孩子右孩子，根据创建二叉树的原理初始化二叉树，然后根据已有的树进行增删改查`````````
一个农夫带着—只狼、一只羊和—棵白菜，身处河的南岸。他要把这些东西全部运到 北岸。他面前只有一条小船，船只能容下他和—件物品，另外只有农夫才能撑船。如果农夫 在场，则狼不能吃羊，羊不能吃白菜，否则狼会吃羊，羊会吃白菜，所以农夫不能留下羊和 白菜自己离开，也不能留下狼和羊自己离开，而狼不吃白菜。请求出农夫将所有的东西运过 河的方案。
首先，有四样“货物”，人，狼，羊，白菜。因此在左岸，可能有16种状态，我们可以用一个二进制数来表示，比如 1111表示都在左岸，0110表示狼和羊在左岸。显然当左岸为state时，右岸为15-state。下面就是构造状态转移矩阵。在这一步，我们要弄清楚一个状态，可能变为哪些状态。如果两个状态可以互相转换，我们就将矩阵对应的位置设为1。先考虑人不在左岸，也就是state<8的情况，显然下一时刻，必然是船从右侧过来，船上有人，还可能有另外一个在右岸的货物。注意我们可以只考虑左岸没有人的状态，因为左岸与右岸是相反的。 这实际上就是一个图的邻接矩阵，每个状态就是图的一个结点。但是要注意，因为狼不能和羊在一起，羊不能和白菜在一起，也就是说 0110 0011 0111以及它们的补数，是无效的状态，是不能达到的，因此要把这些状态去掉。 现在的问题就是找一条路径从 1111 到 NULL。这就是一个图的搜索问题了。然后利用图的广度优先搜索或者深度优先搜索即可解决问题。
以一个 m*n 的长方阵表示迷宫，0 和 1 分别表示迷宫中的通路和障碍。设计一个程序， 对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
1、 随机生成迷宫：
用一个二维数组maze[9][8]来表示迷宫，0表示无障碍，1表示有障碍。利用随Random()函数生成的随机数乘以100转换成int类型的数，再与3求余数等于0即为障碍。这样是为了每次生成的迷宫不会有太多的障碍。
2、利用栈寻找出口
1)将起点压入栈内
2)取出栈顶元素，依次探索这个点的右下左上。
3)将访问过的点记录为2，重复2,3步骤，知道到达终点为止。
3、利用递归寻找出口
采用递归的方式来求迷宫的路径，递归终止条件是当X等于endX并且Y等于endY时或没有通路时也结束当前方法。每次都通过递归遍历四个方向，将访问过的点设置为2状态安全则继续往下探索，不能探索则返回上一个状态。