huftree.java

本软件是使用java 开发的

package datastructure;

import javax.swing.*;
import java.awt.*;
import java.awt.event.*;

class HufTree
    extends Panel
    implements ActionListener, Runnable {

  private Thread runner;
  private HfmPersonGroup hfmPersonGroup;
  //演示控制按钮
  public JButton newButton;
  public JButton runButton;
  public JButton stepButton;
  public JButton stayButton;
  private Image image;
  private Graphics graphics;
  //控制演示速度
  private GlobalControls controlsPanel = new GlobalControls();
  private int controls;
  //runFlag用来控制线程runner的执行，runFlag为true时执行,为false时不执行
  private boolean runFlag;
  //用来控制代码的同步显示
  private CodeAnimationPanel codePanel;
  //panel用来panel1面板和panel2面板,设置为BorderLayout布局
  private Panel panel;
  //panel1用来添加代码显示面板和滚动条,设置为BorderLayout布局
  private Panel panel1;

  //panel1用来添加显示变量值变化情况的文本框,设置为GridLayout布局
  private JPanel panel2;
  // 以下文本框用于显示演示过程中算法变量的变化
  private JTextField text1 = new JTextField("    变 量 名  ");
  private JTextField text11 = new JTextField("  变 量 当 前 值 ");
  private JTextField text22 = new JTextField("           w");
  static JTextField text2;
  private JTextField text33 = new JTextField("           n");
  static JTextField text3;
  private JTextField text44 = new JTextField("           m");
  static JTextField text4;
  private JTextField text55 = new JTextField("           i");
  static JTextField text5;
  private JTextField text66 = new JTextField("           s1");
  static JTextField text6;
  private JTextField text77 = new JTextField("           s2");
  static JTextField text7;
  private JTextField text88 = new JTextField("          cd");
  static JTextField text8;
  private JTextField text99 = new JTextField("           start");
  static JTextField text9;
  private JTextField text100 = new JTextField("           c");
  static JTextField text10;
  private JTextField text112 = new JTextField("           f");
  static JTextField text12;

  private JScrollBar scroll;
  private ScrollPane scrollPane;
  private Panel panel3 = new Panel();

  public HufTree() {
    init();
  }

  public void init() {
    String as[] = {
        "赫夫曼编码的算法伪代码：",
        "void HfmCoding(HfmTree &HT,HfmCode &HC,",
        "         int *w,int n){",
        "//w存放n个字符权值,构造赫夫曼树HT",
        "//求出n个字符的编码HC",
        " if(n<=1) return;",
        " m=2*n-1;",
        " HT=(HfmTree)malloc((m+1)*sizeof(HTNode));",
        " for(p=HT,i=1;i<=n;++i,++w,++p) *p={*w,0,0,0};",
        " for(;i<=m;++i,++p)  *p={0,0,0,0};",
        " for(i=n+1;i<=m;++i){  //建赫夫曼树",
        "  //在HT[1..i-1]选择parent为0且weight最小的两个节点",
        "   Select(HT,i-1,s1,s2);",
        "   HT[s1].parent=i;  HT[s2].parent=i;",
        "   HT[i].lchild=s1;  HT[i].rchild=s2;",
        "   HT[i].weight=HT[s1].weight+HT[s2].weight;",
        " } ",
        " //从叶子节点到根逆向求每个字符的赫夫曼编码",
        " HC=(HfmCode)malloc((n+1)*sizeof(char*));",
        " cd=(char*)malloc(n*sizeof(char));",
        " cd[n-1]= ”0“;     // 编码结束符",
        " for(i=1;i<=n;++i){  //逐个字符求赫夫曼编码",
        "   start=n-1;       //编码结束符位置 ",
        "   for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)",
        "     if(HT[f].lchild==c)",
        "       cd[--start]=”0“;",
        "     else cd[--start]=”1“;",
        "   HC[i]=(char*)malloc((n-start)*sizeof((char));",
        "   strcpy(HC[i],&cd[start]);",
        " }",
        " free(cd);",
        "}"
    };
    codePanel = new CodeAnimationPanel(as);
    panel = new Panel();
    controlsPanel.delay = 900;
    panel3.setLayout(new BorderLayout());
    scroll = new JScrollBar();
    scrollPane = new ScrollPane(ScrollPane.SCROLLBARS_AS_NEEDED);
    panel.setLayout(new BorderLayout());
    this.setLayout(new BorderLayout());
    this.setBackground(Color.lightGray);
    panel1 = new Panel();
    panel2 = new JPanel();
    text2 = new JTextField("    ");
    text3 = new JTextField("    ");
    text4 = new JTextField("   ");
    text5 = new JTextField("   ");
    text6 = new JTextField("   ");
    text7 = new JTextField("   ");
    text8 = new JTextField("   ");
    text9 = new JTextField("   ");
    text10 = new JTextField("   ");
    text12 = new JTextField("   ");
    text11.setEditable(false);
    text1.setEditable(false);
    text22.setEditable(false);
    text2.setEditable(false);
    text33.setEditable(false);
    text3.setEditable(false);
    text44.setEditable(false);
    text4.setEditable(false);
    text55.setEditable(false);
    text5.setEditable(false);
    text66.setEditable(false);
    text6.setEditable(false);
    text77.setEditable(false);
    text7.setEditable(false);
    text88.setEditable(false);
    text8.setEditable(false);
    text99.setEditable(false);
    text9.setEditable(false);
    text100.setEditable(false);
    text10.setEditable(false);
    text112.setEditable(false);
    text12.setEditable(false);
    panel2.add(text1);
    panel2.add(text11);
    panel2.add(text22);
    panel2.add(text2);
    panel2.add(text33);
    panel2.add(text3);
    panel2.add(text44);
    panel2.add(text4);
    panel2.add(text55);
    panel2.add(text5);
    panel2.add(text66);
    panel2.add(text6);
    panel2.add(text77);
    panel2.add(text7);
    panel2.add(text88);
    panel2.add(text8);
    panel2.add(text99);
    panel2.add(text9);
    panel2.add(text100);
    panel2.add(text10);
    panel2.add(text112);
    panel2.add(text12);

    panel2.setLayout(new GridLayout(11, 2));
    newButton = new JButton("新 建");
    newButton.addActionListener(this);
    runButton = new JButton("执 行");
    runButton.addActionListener(this);
    stepButton = new JButton("单 步");
    stepButton.addActionListener(this);
    stayButton = new JButton("暂 停");
    stayButton.addActionListener(this);
    newButton.setToolTipText("建立演示数据");
    stayButton.setToolTipText("暂停演示");
    runButton.setToolTipText("执行演示");
    stepButton.setToolTipText("单步执行演示");
    hfmPersonGroup = new HfmPersonGroup(codePanel);
    panel3.add(codePanel, BorderLayout.CENTER);
    panel3.add(scroll, BorderLayout.EAST);
    scrollPane.add(panel3);
    panel.add(scrollPane, BorderLayout.CENTER);
    panel.add(panel2, BorderLayout.SOUTH);
    this.add(panel, BorderLayout.EAST);
    repaint();
  }

  public void paint(Graphics g) {
    if (this.hfmPersonGroup != null)
      hfmPersonGroup.draw(g);
  }

  public void update(Graphics g) {
    image = createImage(450, 450);
    graphics = image.getGraphics();
    graphics.setColor(getBackground());
    paint(graphics);
    g.drawImage(image, 0, 0, null);
  }

//启动线程
  public void start() {
    if (runner == null) {
      runner = new Thread(this);
      runner.start();
    }
  }

  public void actionPerformed(ActionEvent e) {
    if (e.getSource() == newButton) {
      stop();
      text2.setText("");
      text3.setText("");
      text4.setText("");
      text5.setText("");
      text6.setText("");
      text7.setText("");
      text8.setText("");
      text9.setText("");
      text10.setText("");
      HfmFrame.hufData.setVisible(true);
      runFlag = false;
      runButton.setEnabled(true);
      stepButton.setEnabled(true);
      hfmPersonGroup = new HfmPersonGroup(codePanel);
      repaint();
    }
    else if (e.getSource() == runButton) {
      runFlag = true;
      start();
    }
    else if (e.getSource() == stepButton) {
      stop();
      runFlag = false;
      hfmPersonGroup.HuffmanCoding();
      repaint();
      if (hfmPersonGroup.getDoneFlag()) {
        runFlag = false;
        runButton.setEnabled(false);
        stepButton.setEnabled(false);
        JOptionPane.showConfirmDialog(this,
                                      "    算法演示完成！\n  \n 单击相关按钮重新开始\n",
                                      "演示完成", JOptionPane.DEFAULT_OPTION);
        stop();
      }
    }
    else if (e.getSource() == stayButton) {
      runFlag = false;
    }
  }

  public void run() {
    while (Thread.currentThread() == runner) {
      if (runFlag) {
        hfmPersonGroup.HuffmanCoding();
        repaint();
        try {
          controls = controlsPanel.delay;
          Thread.sleep(controls);
        }
        catch (InterruptedException _ex) {}
        if (hfmPersonGroup.getDoneFlag()) {
          runFlag = false;
          runButton.setEnabled(false);
          stepButton.setEnabled(false);
          JOptionPane.showConfirmDialog(this,
                                        "    算法演示完成！\n  \n 单击相关按钮重新开始\n",
                                        "演示完成", JOptionPane.DEFAULT_OPTION);
          stop();
        }
      }
    }
  }

//终止线程
  public void stop() {
    if (runner != null) {
      runner.yield();
      runner = null;
    }
  }
}