128kj
- 浏览: 600467 次
- 来自: ...
-
最新评论
-
lgh1992314：
相同的元素呢
一种离散化方法 -
HelloSummerR：
圆心的位置是随机的，于是圆的部分会落到canvas外，那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio：
好久没见到sokuban了，这有个java版的，带源码，可以参 ...
求推箱子的最小步数（java) -
肖泽文：
太好了，谢谢你。。有中文注释！
HTML5 推箱子游戏过关演示动画 -
swm8023：
删除操作，将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)（JAVA）
文章列表
一、什么是并查集
并查集：即不相交集合。一种简单的用途广泛的集合，实现了较快的合并和判断元素所在集合的操作，应用很多，如其求无向图的连通分量个数等。最完美的应用当属：实现Kruskar算法求最小生成树。
并查 ...
克鲁斯卡尔kruskal 算法
假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：
先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至子图中含有 n-1条边为止。
POJ1679:The Unique MST
...
继续前文"哈夫曼压缩与解压缩学习笔记（二）"http://128kj.iteye.com/blog/1706818
下面两个类主要是根据字节计数器的统计结果,创建哈夫曼树,计算字节的哈夫曼编码及由哈夫曼编码在树中找节点,往文件中写码表,读码表.
(5)HuffNode.java
//哈夫曼树节点
public class HuffNode implements Comparable<HuffNode>
{
public int value;//节点的字节值
public int weight;//节点的权值(字节出现的频率)
...
无前趋的顶点优先的拓扑排序方法
该方法的每一步总是输出当前无前趋(即人度为零)的顶点，其抽象算法可描述为：
NonPreFirstTopSort(G){//优先输出无前趋的顶点
while(G中有人度为0的顶点)do{
从G中选择一个人度为0的顶点v且输出之；
从G中删去v及其所有出边；
}
if(输出的顶点数目<|V(G)|)
//若此条件不成立，则表示所有顶点均已输出，排序成功。
Error("G中存在有向环，排序失败！")；
}
imp ...
继续前文"哈夫曼压缩与解压缩学习笔记（一）"
http://128kj.iteye.com/blog/1706760
(3)BitOutputStream.java
这个类用于写压缩文件,主要方法writeBits(int[] val)用于将某一个字节的哈夫曼编码val写入文件,写的时候是一位一位先写入缓存区（写的顺序是先写缓存区的低位,后到高位),只有满八位时才flush()真正写入,如果没有八位,从下一字节中读入。
例:上面提到的文件"ASCTASCTAAAAACCTTT"，共有18个字符,压缩写时先写第一个字符A,其哈夫曼编码只有一位0,先 ...
前言
看了两个哈夫曼压缩程序,学习了一把,选一个压缩和解压缩效率高的作些笔记.
一、哈夫曼压缩原理
我们知道计算机中的文件采用二进制编码，为了使文件尽可能的缩短(压缩)，可以对文件中每个字节出现的次数进行统计,设法让出现次数多的字节的二进制码短些，而让那些很少出现的字节的二进制码长一些,这便使整个文件编码之后的总长度的平均期望长度降低，从而达到无损压缩数据的目的。哈夫曼uffman于1952年提出一种编码方法(算法)，该方法完全依据字符(字节)出现概率来生成字符的二进制编码，而且可以证明 Huffman 算法在无损压缩算法中是最优的, 一般就叫作Huffman编码。Huffman ...
prim算法是用来实现图最小生成树的2种常用方法之一，Prim算法的主要步骤如下：
1.设图的顶点集为V，首先选取一个点作为起始点，比如说1顶点，加入到U集合中
2.在所有u∈U,v∈V－U的边(u,v)∈E中,找一条权最小的边(u,v)，将此边加进集合T中，并将此边的非U中顶点加入U中。此步骤的功能是在边集E中找一条边,要求这条边满足以下条件:首先边的两个顶点要分别在顶点集合U和V－U中,其次边的权要最小。找到这条边以后,把这条边放到边集T中,并把这条边上不在U中的那个顶点加入到U中。
3:如果U=V,则算法结束;否则重复步骤2。可以把本步骤看成循环终止 ...
题意：
给出N个城镇的坐标和M条已经建好的路, 求连接所有城镇且长度之和最小的高速公路系统的每条公路, 已经存在的公路不用输出。
样例：
Sample Input
9 （城镇个数及坐标）
1 5
0 0
3 2
4 5
5 1
0 4
5 2
1 2
5 3
3 //M条已建好的路,城镇1-->3，9--->7,1--->2
1 3
9 7
1 2
Sample Output
1 6
3 7
4 9
5 7
8 3
由于最后不用输出长度值, 而且坐标的绝对值不超过10000, 所以在算城镇距离的时候就直接省去了sqrt(),由 ...
1、生成树
如果连通图G的一个子图是一棵包含G的所有顶点的树，则该子图称为G的生成树(SpanningTree)。
生成树是连通图的包含图中的所有顶点的极小连通子图,图的生成树不惟一。从不同的顶点出发进行遍历，可以得到不同的 ...
栈是一种先进后出的数据结构, 定义栈需要实现的接口:
public interface MyStack<T> {
/**
* 判断栈是否为空
*/
boolean isEmpty();
/**
* 清空栈
*/
void clear();
/**
* 栈的长度
*/
int length();
/**
* 数据入栈
*/
boolean ...
题意描述：
一个房间上有红色的瓦和黑色的瓦片，给出红瓦和黑瓦的位置和人所占的位置，求人最多能走过多少片瓦？
（条件为：人行走过程中只能走黑瓦，且人的初始位置为黑瓦）
输入描述：输入的字符里面只有三种字符：
“@”-----表示人（只能有一个该字符）
“.”-----表示黑瓦
“#”-----表示红瓦
样例：
Sample Input
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
Sample Output
45
AC代码:
i ...
一、深度优先搜索遍历磁盘文件目录
import java.io.File;
import java.io.IOException;
import java.util.Stack;
import java.util.Queue;
import java.util.LinkedList;
public class ListFile{
public static void main(String[] args) throws IOException {
File file = new File("c:/java");
...
先继续“深度优先搜索学习五例之三”http://128kj.iteye.com/admin/blogs/1702286中的迷宫,那里用栈实现了深搜,但只输出了一条路径,下面程序用递归实现深搜,输出所有到出口的路径和数目：
import java.util.Stack;
////////////////////////////////////////////////
//深度优先搜索之迷宫问题:输出所有到出口的路径
public class MazeDsf{
private static final int M=9;
private static f ...
一、深度优先搜索框架一递归实现,流程如下:
public void dfs(int v) {
visited[v] = true; //访问起点v
System.out.print(v+" ");
for (int i = 0; i < k; i++) {
//递归调用搜索没有被访问过的当前节点的下一个节点（邻接点）
if (G[v][i] == 1 && !visited[i])//G[v][i]是图的邻接矩阵
...
继续“深度优先搜索学习五例之一 ”中的第一例子:http://128kj.iteye.com/blog/1701628
例:写出数字1,2,3,4,5的所有全排列（深搜用栈实现,上文中是用递归）
import java.util.Stack;
public class Permutation{
private int M=5;
//访问标记, visited[i]=true表示顶点i已访问
private boolean visited[];
public Permutation(){
visited=new boolean[5 ...