E81086713E446D36F62B2AA2A3502B5EB155

置顶随笔

去年也大概是这个时候写了第一个Java2EXE,之后又加了写特性,但是每次我看代码都感觉惨不忍睹,很混乱,而且编译,链接的过程也有点绕。
现在又过了一年了,如果说上次版本的Load过程主要是靠Java(Java加密,解压),那么这次基本把这些费时的操作全交给CPP了。
好了,总结一下这次的改动
1)Loader以及Starter完全是CPP代码,结构很清晰了。
2)加密以及解压交给CPP,速度比以前快了。
3)整合了JNative,这个是重点,下文详述。
4)生成工具用MFC写,一个简单的向导。

OK,那么JNative是干什么的呢?
官方的描述是 “JNative, Java framework for DLL access for Windows and Linux”
就是说,有了这个框架,你访问DLL里的方法就不再需要写DLL了,只需要写Java Code了,可能有人问它是怎么做到的呢?
假如说你要访问Kernel32.dll里的某个方法A,你首先需要这个方法的句柄,这个句柄就是通过new一个org.xvolks.jnative.JNative实例来保持的,
类似如:
org.xvolks.jnative.Native methodA=new org.xvolks.jnative.JNative("Kernel32.dll","A");
有了这个句柄,你只要在上面设置参数,返回值,以及类型就可以调用它了。每个调用它上面的JNI里的本地方法就会自动来进行参数解析,解码,调用到目标DLL方法,这个过程基本不可避免需要少量的汇编代码。
JNative为了可移植性,代码是在Cygwin下可编译的,没有MSVC可编译的版本。

对此,本人改了部分代码用于直接一起链接(主要是把GCC嵌入汇编改为对应的MSVC的嵌入汇编代码),而不是让JNative生成一个动态链接库。

如上,由于JNative改成了静态库,程序发布的时候,只要是通过Java2EXE Builder来创建成EXE的话,你就不需要那个JNativeCpp.dll文件了,只有一个EXE.

你调试的时候可以用官方的版本,发布就只要你的代码(JNative的class也都在集成在生成工具里,不需要你自己添加进来)。

来看个简单的例子,我们从Java代码里取得当前进程的全路径名:
import org.xvolks.jnative.JNative;
import org.xvolks.jnative.Type;
import org.xvolks.jnative.exceptions.NativeException;
import org.xvolks.jnative.pointers.Pointer;
import org.xvolks.jnative.pointers.memory.HeapMemoryBlock;

/**
 * DWORD GetModuleFileName(
 * HMODULE hModule,
 * LPTSTR lpFilename,
 * DWORD nSize
 *);

 * 
@author yovn
 *
 
*/
public class TestReadProcessPath {

    
/**
     * 
     * 
@param args
     * 
@throws NativeException 
     * 
@throws IllegalAccessException 
     
*/
    
public static void main(String[] args) throws NativeException, IllegalAccessException {
        JNative v
=new JNative("Kernel32.dll","GetModuleFileNameA");
        
int i = 0;
        v.setRetVal(Type.INT);
        Pointer pName 
= new Pointer(new HeapMemoryBlock(1024));
        
        v.setParameter(i
++0);//module handle
        v.setParameter(i++, pName);//pFileName
        v.setParameter(i++1024);//nSize
        v.setRetVal(Type.INT);
        v.invoke();
        
int ret = Integer.parseInt(v.getRetVal());
        
if (ret == 0) {
            
// return "null";
            System.err.println(
                    
"GetModuleFileName failed!");
        } 
else {
            
            String path 
= pName.getAsString().substring(0,
                    ret);
            pName.dispose();
            v.dispose();
            System.out.println(
"current process's path is:"+path);
        }
    }

}

编译,把这个文件单独打包成一个jar文件,下面是个用这个工具生成EXE的截图:
生成EXE向导第一步
生成 EXE向导第二步



请从这里下载 Java2EXE Builder Platform











posted @ 2008-02-26 00:31 DoubleH 阅读(1008) | 评论 (7)编辑 收藏


2008年3月29日

如果Web服务器需要频繁传送文件给客户端时,大多数web容器会提供异步发送的支持,像IIS中的通过ServerSupportFunction(),Apache里面apr_sendfile(),Tomcat6.X通过设置Servlet Request的请求属性等等。。。都可以做到异步发送文件,从而提高服务器性能。

Jetty6.X默认也不提供相关支持,本文提供一种hack方法,仅供参考:

先看测试Servlet:
package com.yovn.labs.testweb;

import java.io.File;
import java.io.IOException;

import javax.servlet.ServletException;
import javax.servlet.http.HttpServlet;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;

import com.yovn.labs.sendfile.JettySendFile;
import com.yovn.labs.sendfile.NormalSendFile;
import com.yovn.labs.sendfile.SendFile;

/**
 * 
@author yovn
 *
 
*/
public class SendFileServlet extends HttpServlet {

    
protected void doGet(HttpServletRequest req, HttpServletResponse res)
            
throws ServletException, IOException {
    
        
        
try {
            
            File f
=new File("D:\\workspace\\TEST.rar");//about 45M
            String action
=req.getParameter("action");
            SendFile sf
=null;
            
if("1".equals(action))
            {
                sf
=new JettySendFile();
            }
            
else
            {
                sf
=new NormalSendFile();
            }
            
long start=System.currentTimeMillis();
            sf.doSend(req, res, f, 
null);
            System.out.println(
" service ok, action="+action+",use:"+(System.currentTimeMillis()-start)+"!!!");
        } 
catch (Exception e) {
            
throw new ServletException(e);
        }
      
    }
    
    

}
代码很简单明了,action=1时使用Jetty的异步发送,action=2时使用正常方式。

下面是通过firefox直输入地址回车后,下载文件,后台的程序运行结果:
 service ok, action=1,use:62!!!
 service ok, action
=2,use:10688!!!
 service ok, action
=2,use:9063!!!
 service ok, action
=1,use:47!!!
当运行1时,实际上客户端还没有下完文件,但是该段代码已经执行完了,IO的操作是异步的。
当运行2时,客户端下完代码才执行完。

以下是Jetty异步发送的代码:
package com.yovn.labs.sendfile;

import java.io.File;
import java.io.IOException;
import java.lang.reflect.Field;

import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;

import org.mortbay.io.EndPoint;
import org.mortbay.io.nio.NIOBuffer;

/**
 * 
@author yovn
 *
 
*/
public class JettySendFile implements SendFile {

    
static Field endpointField=null;
    
static Class reqCls=null;
    
static 
    {
        
try {
            reqCls
=Class.forName("org.mortbay.jetty.Request");
            endpointField
=reqCls.getDeclaredField("_endp");
            endpointField.setAccessible(
true);
        } 
catch (Exception e) {
            
// TODO Auto-generated catch block
            e.printStackTrace();
        } 
    }
        
    
    


    
public void doSend(HttpServletRequest req, HttpServletResponse res,File todo,String headerOpt)
            
throws IOException {
        
        
if(endpointField==null)throw new IOException("Jetty Not Available!!");
        
if(!req.getClass().equals(reqCls))
        {
            
throw new IOException("Not in Jetty Context!!");
        }
        EndPoint ep;
        
try {
            ep 
= (EndPoint)endpointField.get(req);
        
            
if(headerOpt==null)
            {
                headerOpt
="HTTP/1.1 200 OK \r\nContent-Type: APPLICATION/OCTET-STREAM\r\n"+
                      
"Content-Disposition: attachment;filename=\""+todo.getName()+"\"\r\n"+
                      
"Content-Length: "+todo.length()+"\r\n\r\n";
            }
            
byte[] headerBytes=headerOpt.getBytes("UTF-8");
            NIOBuffer header
=new NIOBuffer(headerBytes.length,false);
            header.put(headerBytes);
            
            NIOBuffer buffer
=new NIOBuffer(todo);
            
            ep.flush(header, buffer, 
null);
        } 
catch (IllegalArgumentException e) {
            
throw new IOException(e);
        } 
catch (IllegalAccessException e) {
            
throw new IOException(e);
        }
        
        
        
    }

}

正常发送文件的代码:
package com.yovn.labs.sendfile;

import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;

import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;

/**
 * 
@author yovn
 *
 
*/
public class NormalSendFile implements SendFile {

    
/* (non-Javadoc)
     * We simply ignore the 'headerOpt'
     * @see com.yovn.labs.sendfile.SendFile#doSend(javax.servlet.http.HttpServletRequest, javax.servlet.http.HttpServletResponse, java.io.File, java.lang.String)
     
*/
    
public void doSend(HttpServletRequest req, HttpServletResponse res,
            File todo, String headerOpt) 
throws IOException {
        res.setHeader(
"Content-Type""APPLICATION/OCTET-STREAM");
        res.setHeader(
"Content-Disposition""attachment;filename=\""+todo.getName()+"\"");
        res.setHeader(
"Content-Length", todo.length()+"");
        res.setStatus(HttpServletResponse.SC_OK);
        OutputStream out
=res.getOutputStream();
        InputStream in
=new FileInputStream(todo);
        
        
byte[] buffer=new byte[8192];
        
        
int read=0;
        
while((read=in.read(buffer))>0)
        {
            out.write(buffer, 
0, read);
        }
        out.flush();
        in.close();
        
        

    }

}


posted @ 2008-03-29 01:54 DoubleH 阅读(910) | 评论 (0)编辑 收藏


2008年3月5日

过道里依次挂着标号是1,2,3, ......,100的电灯泡,开始它们
都是灭着的。当第一个人走过时,他将标号为 1 的倍数的电灯泡的开关
线拉了一下;当第二个人走过时,他将标号为 2 的倍数的电灯泡的开关
线拉了一下;当第三个人走过时,他将标号为 3 的倍数的电灯泡的开关
线拉了一下;......  如此进行下去,当第一百个人走过时,他将标号为
100 的倍数的电灯泡的开关线拉了一下。
问:当第一百个人走过后,过道里亮着的电灯泡标号是多少?


我的思路:
设标号为K的灯泡被拉了L(K)次,那么当L(K)为奇数的时候,灯泡是亮的。
那么那些标号被拉了奇数次呢?
K=1时,很显然是只拉了1次,最后是亮的。
其次K>=2时,据题意,K号灯第1次,和第K次肯定是拉下了,其余的只会被第K的因子次拉,
据因式分解定理,数K分解为
K=p1^(n1)*p2^(n2)*.....pi^(ni)
其中p1,p2,...pi为素数。
那么,K有那些因子呢?
其实可以考虑任一个因子,他可能是从n1个p1中选若干个(0个到n1个),从n2个p2中选若干个。。。。。(当全是0个的时候,这个特殊的因子是1)
这样,根据乘法原理,总共有L(K)=(n1+1)*(n2+1)*(n3+1).....
比如,12=2^2*3
一种有3*2=6个因子,他们是1,2,3,4,6,12.

现在考虑要使L(K)为奇数,那么n1,n2,n3不能有一个是奇数,或则,有一个ni+1为偶数,而偶数与任何数相乘仍为偶数。
从而,n1,n2,n3都为偶数,都能被2除。
因为n1,n2,n3都为偶数,显然该数必须是个平方数,可写成K=(X)^2.
从而,1,4,9,16,25,36,49,64,81,100最后是亮的。

posted @ 2008-03-05 15:00 DoubleH 阅读(1140) | 评论 (5)编辑 收藏


2008年2月26日

去年也大概是这个时候写了第一个Java2EXE,之后又加了写特性,但是每次我看代码都感觉惨不忍睹,很混乱,而且编译,链接的过程也有点绕。
现在又过了一年了,如果说上次版本的Load过程主要是靠Java(Java加密,解压),那么这次基本把这些费时的操作全交给CPP了。
好了,总结一下这次的改动
1)Loader以及Starter完全是CPP代码,结构很清晰了。
2)加密以及解压交给CPP,速度比以前快了。
3)整合了JNative,这个是重点,下文详述。
4)生成工具用MFC写,一个简单的向导。

OK,那么JNative是干什么的呢?
官方的描述是 “JNative, Java framework for DLL access for Windows and Linux”
就是说,有了这个框架,你访问DLL里的方法就不再需要写DLL了,只需要写Java Code了,可能有人问它是怎么做到的呢?
假如说你要访问Kernel32.dll里的某个方法A,你首先需要这个方法的句柄,这个句柄就是通过new一个org.xvolks.jnative.JNative实例来保持的,
类似如:
org.xvolks.jnative.Native methodA=new org.xvolks.jnative.JNative("Kernel32.dll","A");
有了这个句柄,你只要在上面设置参数,返回值,以及类型就可以调用它了。每个调用它上面的JNI里的本地方法就会自动来进行参数解析,解码,调用到目标DLL方法,这个过程基本不可避免需要少量的汇编代码。
JNative为了可移植性,代码是在Cygwin下可编译的,没有MSVC可编译的版本。

对此,本人改了部分代码用于直接一起链接(主要是把GCC嵌入汇编改为对应的MSVC的嵌入汇编代码),而不是让JNative生成一个动态链接库。

如上,由于JNative改成了静态库,程序发布的时候,只要是通过Java2EXE Builder来创建成EXE的话,你就不需要那个JNativeCpp.dll文件了,只有一个EXE.

你调试的时候可以用官方的版本,发布就只要你的代码(JNative的class也都在集成在生成工具里,不需要你自己添加进来)。

来看个简单的例子,我们从Java代码里取得当前进程的全路径名:
import org.xvolks.jnative.JNative;
import org.xvolks.jnative.Type;
import org.xvolks.jnative.exceptions.NativeException;
import org.xvolks.jnative.pointers.Pointer;
import org.xvolks.jnative.pointers.memory.HeapMemoryBlock;

/**
 * DWORD GetModuleFileName(
 * HMODULE hModule,
 * LPTSTR lpFilename,
 * DWORD nSize
 *);

 * 
@author yovn
 *
 
*/
public class TestReadProcessPath {

    
/**
     * 
     * 
@param args
     * 
@throws NativeException 
     * 
@throws IllegalAccessException 
     
*/
    
public static void main(String[] args) throws NativeException, IllegalAccessException {
        JNative v
=new JNative("Kernel32.dll","GetModuleFileNameA");
        
int i = 0;
        v.setRetVal(Type.INT);
        Pointer pName 
= new Pointer(new HeapMemoryBlock(1024));
        
        v.setParameter(i
++0);//module handle
        v.setParameter(i++, pName);//pFileName
        v.setParameter(i++1024);//nSize
        v.setRetVal(Type.INT);
        v.invoke();
        
int ret = Integer.parseInt(v.getRetVal());
        
if (ret == 0) {
            
// return "null";
            System.err.println(
                    
"GetModuleFileName failed!");
        } 
else {
            
            String path 
= pName.getAsString().substring(0,
                    ret);
            pName.dispose();
            v.dispose();
            System.out.println(
"current process's path is:"+path);
        }
    }

}

编译,把这个文件单独打包成一个jar文件,下面是个用这个工具生成EXE的截图:
生成EXE向导第一步
生成 EXE向导第二步



请从这里下载 Java2EXE Builder Platform











posted @ 2008-02-26 00:31 DoubleH 阅读(1008) | 评论 (7)编辑 收藏


2007年12月20日

     摘要: 红黑树可能是要考虑情况最多的BST树了,它有自己的规则(见代码的注释),通过这些规则可以保证花费较小的代价来达到相对平衡。 注意,红黑树仍然不是平衡树,但是统计性能要好于AVL树。 要保持红黑树的规则,主要通过两类操作,一类是换色,一类还是旋转。 红黑树插入主要要解决红-红冲突,而删除主要则解决“双黑” 同样,红黑树的删除节点实现是最复杂的,不过,复杂也就在于考...  阅读全文

posted @ 2007-12-20 18:25 DoubleH 阅读(2027) | 评论 (5)编辑 收藏


2007年12月19日

     摘要: 伸展树与半伸展树属于自组织的数据结构,能按访问频率调整节点的位置 调整一般通过如下方式: 1)绕根的单旋转,跟AVL的单旋转类似 2)一字型旋转(ZigZig Rotation) 3)之字形旋转(ZigZag Rotation) 旋转操作较简单,有点点繁琐。 半伸展树不做完全的一字型旋转,它只让父节点绕祖父节点做单旋转。 不管怎样,每次访问(插入/查找 ,删除时展开被删除父节...  阅读全文

posted @ 2007-12-19 00:39 DoubleH 阅读(814) | 评论 (0)编辑 收藏


2007年12月18日

     摘要: AVL树的是一种平衡的二叉搜索树。每次插入,删除的时候需要一个局部的平衡化操作。 实现AVL树的插入操作一般不是很难,清楚的理解了平衡因子以及旋转操作实现起来就没多大问题了。 难点一般在于删除操作的实现,教科书上一般用很大的篇幅来详细说明各种情况,看起来很凌乱,理解起来很是费劲。考虑到可以把删除操作看成插入操作的逆操作,这里我给出另一种较为清晰的实现方式: 1)删除的时候做一个标记的过程 ...  阅读全文

posted @ 2007-12-18 18:30 DoubleH 阅读(953) | 评论 (0)编辑 收藏


2007年12月16日

外部排序实现使用堆来生成若干个顺串,然后使用多路归并算法来生成最终排序好的内容。

本来打算使用败者树,结果发现败者树当参与的竞赛者相对较多的情况下,没有全部完成就被空节点充满了。
这个按照它的严格算法,其实也是可以知道不能保证总是能排完的。天快亮了,才彻底放弃使用败者树。改成实现赢者树,结果发现赢者树能保证不出错,实现竟也顺手。

最后整了个测试文件500M的随机内容,2~3分钟排序完成了(应该还可以优化),感觉还行。

代码较多,最要考虑到以后可能要重用。

package algorithms.extsort;

import java.io.IOException;

import algorithms.MinHeap;

/**
 * 
@author yovn
 *
 
*/
public class ExternalSorter {
    
        
    
    
public void sort(int heapSize,RecordStore source,RunAcceptor mediator ,ResultAcceptor ra)throws IOException
    {
        MinHeap
<Record> heap=new MinHeap<Record>(Record.class,heapSize);
        
for(int i=0;i<heapSize;i++)
        {
            Record r
=source.readNextRecord();
            
if(r.isNull())break;
            heap.insert(r);
        }
        
        Record readR
=source.readNextRecord();
        
while(!readR.isNull()||!heap.isEmpty())
        {
        
            Record curR
=null;
            
//begin output one run
            mediator.startNewRun();
            
while(!heap.isEmpty())
            {
                curR
=heap.removeMin();
            
                mediator.acceptRecord(curR);
                
                
if (!readR.isNull()) {
                    
if (readR.compareTo(curR) < 0) {
                        heap.addToTail(readR);
                    } 
else
                        heap.insert(readR);
                }
                readR
=source.readNextRecord();
                
            }
            
//done one run
            mediator.closeRun();
            
            
//prepare for next run
            heap.reverse();
            
while(!heap.isFull()&&!readR.isNull())
            {
                
                heap.insert(readR);
                readR
=source.readNextRecord();
                
            }
            
            
        }
        RecordStore[] stores
=mediator.getProductedStores();
//        LoserTree  lt=new LoserTree(stores);
        WinnerTree  lt=new WinnerTree(stores);
        
        Record least
=lt.nextLeastRecord();
        ra.start();
        
while(!least.isNull())
        {
            ra.acceptRecord(least);
            least
=lt.nextLeastRecord();
        }
        ra.end();
        
        
for(int i=0;i<stores.length;i++)
        {
            stores[i].destroy();
        }
    }
    
    
    
public static void main(String[] args) throws IOException
    {
//        RecordStore store=new MemRecordStore(60004,true);
//        RunAcceptor mediator=new MemRunAcceptor();
//        ResultAcceptor ra=new MemResultAcceptor();
        ExternalSorter sorter=new ExternalSorter();
            
        RecordStore store
=new FileRecordStore("test_sort.txt");
        RunAcceptor mediator
=new FileRunAcceptor("test_sort");
        ResultAcceptor ra
=new FileRecordStore("test_sorted.txt");
        
        
        sorter.sort(
70000, store, mediator, ra);
    }
    
}

其余的都打包在此!

源码

posted @ 2007-12-16 08:08 DoubleH 阅读(918) | 评论 (0)编辑 收藏


2007年12月14日

六。 最小支撑树MST
给定一个简单有向图,要求权值最小的生成树,即求最小支撑树问题。
所谓生成树,就是说树的顶点集合等于给定图的顶点集合,且边集合包含于图的边集合。
也就说找出构成树的,经过所有顶点的,且权值最小的边集。
树的定义是要求无回路的,然后是要求连通的。

有两个比较经典的算法是:
1)Prim算法: 该算法的思想跟Dijstra算法非常相似,Dijstra算法中每次求出下一个顶点时依据的是离初始顶点最近的,而Prim算法则找离V1整个集合最近的,也就是从V1中某个节点出发到该顶点的边的权值最小。
其原理也是每次找局部最优,最后构成全局最优。
实现如下

@Override
    
public Edge[] prim() {
        MinHeap
<Edge> heap=new MinHeap<Edge>(Edge.class,numEdges);
        Edge[] edges
=new Edge[numVertexes-1];
        
//we start from 0
        int num=0;//record already how many edges;
        int startV=0;
        Arrays.fill(visitTags, 
false);
        Edge e;
        
for(e=firstEdge(startV);isEdge(e);e=nextEdge(e))
        {
            heap.insert(e);
        }
        visitTags[startV]
=true;
        
        
while(num<numVertexes-1&&!heap.isEmpty())//tree's edge number was n-1
        {
            
            e
=heap.removeMin();
        
            startV
=toVertex(e);
            
if(visitTags[startV])
            {
                
continue;
            }
            visitTags[startV]
=true;
            edges[num
++]=e;
            
for(e=firstEdge(startV);isEdge(e);e=nextEdge(e))
            {
                
if(!visitTags[toVertex(e)])//can't add already visit vertex, this may cause cycle
                heap.insert(e);
            }
            
                
            
        }
        
if(num<numVertexes-1)
        {
            
throw new IllegalArgumentException("not connected graph");
        }
        
return edges;
    }

/**
     * A Graph example
     * we mark the vertexes  with 0,1,2,.14 from left to right , up to down
     * S-8-B-4-A-2-C-7-D
     * |   |   |   |   |
     * 3   3   1   2   5
     * |   |   |   |   |
     * E-2-F-6-G-7-H-2-I
     * |   |   |   |   |
     * 6   1   1   1   2
     * |   |   |   |   |
     * J-5-K-1-L-3-M-3-T
     * 
     
*/
    
public static void testPrimMST() {
    

        
        DefaultGraph g
=new DefaultGraph(15);
        g.setEdge(
018);
        g.setEdge(
108);//its a undirected graph
        g.setEdge(124);
        g.setEdge(
214);
        g.setEdge(
232);
        g.setEdge(
322);
        g.setEdge(
347);
        g.setEdge(
437);
        
        g.setEdge(
053);
        g.setEdge(
503);
        g.setEdge(
163);
        g.setEdge(
613);
        g.setEdge(
271);
        g.setEdge(
721);
        g.setEdge(
382);
        g.setEdge(
832);
        g.setEdge(
495);
        g.setEdge(
945);
        
        
        g.setEdge(
562);
        g.setEdge(
652);
        g.setEdge(
676);
        g.setEdge(
766);
        g.setEdge(
787);
        g.setEdge(
877);
        g.setEdge(
892);
        g.setEdge(
982);
        
        
        g.setEdge(
1056);
        g.setEdge(
5106);
        g.setEdge(
1161);
        g.setEdge(
6111);
        g.setEdge(
1271);
        g.setEdge(
7121);
        g.setEdge(
1381);
        g.setEdge(
8131);
        g.setEdge(
1492);
        g.setEdge(
9142);
        
        g.setEdge(
10115);
        g.setEdge(
11105);
        g.setEdge(
11121);
        g.setEdge(
12111);
        g.setEdge(
12133);
        g.setEdge(
13123);
        g.setEdge(
13143);
        g.setEdge(
14133);
        
        g.assignLabels(
new String[]{"S","B","A","C","D","E","F","G","H","I","J","K","L","M","T"});
        Edge[] edges
=g.prim();
        
int total=0;
        
for(int i=0;i<edges.length;i++)
        {
            System.out.println(edges[i].toString(g));
            total
+=edges[i].getWeight();
        }
        System.out.println(
"MST total cost:"+total);
}

2)Kruskal算法:
该算法开始把,每个节点看成一个独立的两两不同的等价类,每次去权值最小的边,如果关联这条边的两个顶点在同一个等价类里那么这条边不能放入MST(最小生成树)中,否则放入MST中,并把这两个等价类合并成一个等价类。
继续从剩余边集里选最小的边,直到最后剩余一个等价类了。
该算法涉及等价类的合并/查找,一般用父指针树来实现。下面先给出父指针树实现的并查算法。
带路径压缩的算法,其查找时间代价可以看做是常数的。

package algorithms;

/**
 * 
@author yovn
 *
 
*/
public class ParentTree {
    
    
    
private static class PTreeNode
    {
        
int parentIndex=-1;
        
int numChildren=0;//only make sense in root

        
void setParent(int i) {
            
            parentIndex
=i;
            
        }
    }
    PTreeNode[] nodes;
    
int numPartions;
    
public ParentTree(int numNodes)
    {
        nodes
=new PTreeNode[numNodes];
        numPartions
=numNodes;
        
for(int i=0;i<numNodes;i++)
        {
            nodes[i]
=new PTreeNode();
            nodes[i].parentIndex
=-1;//means root
            
        }
        
    }
    
    
/**
     * use path compress
     * 
@param i
     * 
@return
     
*/
    
public int find(int i)
    {
        
if(nodes[i].parentIndex==-1)
        {
            
return i;
        }
        
else
        {
            nodes[i].setParent(find(nodes[i].parentIndex));
//compress the path
            return nodes[i].parentIndex;
        }
    }
    
    
public int numPartions()
    {
        
return numPartions;
    }
    
public boolean union(int i,int j)
    {
        
int pi=find(i);
        
int pj=find(j);
        
if(pi!=pj)
        {
            
if(nodes[pi].numChildren>nodes[pj].numChildren)
            {
                nodes[pj].setParent(pi);
                nodes[pj].numChildren
+=nodes[pi].numChildren;
                nodes[pi].numChildren
=0;
                
            }
            
else
            {
                nodes[pi].setParent(pj);
                nodes[pi].numChildren
+=nodes[pj].numChildren;
 &nb