hfmpersongroup.java

本软件是使用java 开发的

package datastructure;

import java.awt.*;
import java.util.*;

class HfmPersonGroup {
  private CodeAnimationPanel codePanel;
  private String w;
  private int n;
  private int m;
  private int i;
  private int f;
  private int s1;
  private int s2;
  private int start;
  private int c;
  private String cd[];
  private String hc;
  private int record[];
  //记录数组record[]的当前下标
  private int tag;
  private HTNode HT[];
  private HTNode animationHTNode;
  //变量codePart用来控制源代码的同步显示,初始化为0
  private int codePart;
  //doneFlag记录演示是否完成,为真是表示已经完成
  private boolean doneFlag;
  private int a[];

  public HfmPersonGroup(CodeAnimationPanel codePanel) {
    this.codePanel = codePanel;
    codePanel.highlight(12);
    a = HfmFrame.hufData.a;
    n = a.length;
    HufTree.text3.setText("     " + String.valueOf(n));
    HT = new HTNode[2 * n];
    record = new int[2 * n];
    tag = 0;
    codePart = 0;
    cd = new String[n];
    for (int j = 0; j < cd.length; j++)
      cd[j] = "";
    w = "(";
    hc = "";
    doneFlag = false;
    this.codePanel.highlight(2);
    for (int j = 1; j < HT.length; j++)
      HT[j] = new HTNode( -1);
    HufTree.text5.setText("     " + String.valueOf(i));
    for (i = 0; i < a.length; i++) {
      HT[i + 1].setWeight(a[i]);
      HT[i + 1].y = 60;
      if (i != a.length - 1)
        w = w + String.valueOf(a[i]) + ",";
      else
        w = w + String.valueOf(a[i]) + ")";
    }
    HT[1].x = 50;
    HT[2].x = 90;
    HT[3].x = 130;
    HT[4].x = 170;
    HT[5].x = 210;
    HT[6].x = 250;
    HT[7].x = 290;
    HT[8].x = 330;
    HufTree.text2.setText("     " + w);
  }

  public boolean getDoneFlag() {
    return doneFlag;
  }

  public void draw(Graphics g) {
    for (int j = 1; j < HT.length; j++) {
      if (HT[j].getWeight() != -1) {
        drawTreeHTNode(g, HT[j], j);
        if (codePart > 2) {
          g.setColor(Color.blue);
          g.drawString("HT[" + String.valueOf(j) + "]", HT[j].x,
                       HT[j].y + 43);
        }
        if (!HT[j].number.equals("")) {
          g.setColor(Color.red);
          g.drawString("'" + HT[j].number + "'", HT[j].x,
                       HT[j].y + 58);
        }
        if (!HT[j].number.equals("")) {
          g.setColor(Color.red);
          g.drawString("'" + HT[j].number + "'", HT[j].x,
                       HT[j].y + 58);
        }
        if (!HT[j].c.equals("")) {
          if (HT[j].flag)
            g.setColor(Color.red);
          else
            g.setColor(Color.black);
          g.drawString(HT[j].c, HT[j].x + 20,
                       HT[j].y - 25);
        }
      }
    }
    g.setColor(Color.white);
    g.fill3DRect(20, 10, 80, 28, true);
    g.setColor(Color.black);
    g.draw3DRect(20, 10, 80, 28, true);
    g.setColor(Color.red);
    if (codePart > 13) {
      if (codePart >= 23)
        g.drawString(" 编  码 结 束 ", 25, 30);
      else
        g.drawString("    编      码 ", 25, 30);
    }
    else
      g.drawString("构造赫夫曼树", 25, 30);
  }

  public void HuffmanCoding() {
    switch (codePart) {
      case 0:
        codePanel.highlight(6);
        if (n <= 1)
          doneFlag = true;
        else
          codePart = 1;
        break;
      case 1:
        codePanel.highlight(7);
        m = 2 * n - 1;
        HufTree.text4.setText("     " + String.valueOf(m));
        codePart = 2;
        break;
      case 2:
        codePanel.highlight(8);
        codePart = 3;
        break;
      case 3:
        codePanel.highlight(9);
        HufTree.text5.setText("     " + String.valueOf(i));
        codePart = 4;
        break;
      case 4:
        codePanel.highlight(10);
        HufTree.text5.setText("     " + String.valueOf(m + 1));
        i = n + 1;
        codePart = 5;
        break;
      case 5:
        codePanel.highlight(11);
        HufTree.text5.setText("     " + String.valueOf(i));
        if (i <= m)
          codePart = 6;
        else
          codePart = 11;
        break;
      case 6:
        codePanel.highlight(13);
        Select(i - 1);
        HT[s1].setHighlight(true);
        HT[s2].setHighlight(true);
        HT[i].setLeftNode(HT[s1]);
        HT[i].setRightNode(HT[s2]);
        HufTree.text6.setText("     " + String.valueOf(s1));
        HufTree.text7.setText("     " + String.valueOf(s2));
        codePart = 7;
        break;
      case 7:
        codePanel.highlight(14);
        if (i == 9) {
          HT[1].x = 320;
          HT[2].x = 40;
          HT[3].x = 90;
          HT[4].x = 380;
          HT[5].x = 140;
          HT[6].x = 190;
          HT[7].x = 240;
          HT[8].x = 290;
          HT[9].x = 350;
          HT[9].setWeight(0);
          HT[1].y = HT[4].y = 130;
          HT[2].y = HT[3].y = HT[5].y = HT[6].y = HT[7].y = HT[8].y = HT[9].y =
              50;
        }
        else if (i == 10) {
          HT[1].x = 220;
          HT[2].x = 320;
          HT[3].x = 50;
          HT[4].x = 280;
          HT[5].x = 100;
          HT[6].x = 380;
          HT[7].x = 150;
          HT[8].x = 200;
          HT[9].x = 250;
          HT[10].x = 350;
          HT[10].setWeight(0);
          HT[3].y = HT[5].y = HT[7].y = HT[8].y = HT[9].y = HT[10].y = 50;
          HT[1].y = HT[2].y = HT[4].y = HT[6].y = 130;
        }
        else if (i == 11) {
          HT[1].x = 270;
          HT[2].x = 180;
          HT[3].x = 60;
          HT[4].x = 330;
          HT[5].x = 110;
          HT[6].x = 240;
          HT[7].x = 400;
          HT[8].x = 160;
          HT[9].x = 300;
          HT[10].x = 210;
          HT[11].x = 350;
          HT[11].setWeight(0);
          HT[3].y = HT[5].y = HT[8].y = HT[10].y = HT[11].y = 50;
          HT[2].y = HT[6].y = HT[7].y = HT[9].y = 130;
          HT[1].y = HT[4].y = 210;
        }
        else if (i == 12) {
          HT[1].x = 120;
          HT[2].x = 270;
          HT[3].x = 400;
          HT[4].x = 180;
          HT[5].x = 50;
          HT[6].x = 330;
          HT[7].x = 250;
          HT[8].x = 100;
          HT[9].x = 150;
          HT[10].x = 300;
          HT[11].x = 200;
          HT[12].x = 350;
          HT[12].setWeight(0);
          HT[5].y = HT[8].y = HT[11].y = HT[12].y = 50;
          HT[3].y = HT[7].y = HT[9].y = HT[10].y = 130;
          HT[1].y = HT[2].y = HT[4].y = HT[6].y = 210;
        }
        else if (i == 13) {
          HT[1].x = 270;
          HT[2].x = 70;
          HT[3].x = 200;
          HT[4].x = 330;
          HT[5].x = 250;
          HT[6].x = 130;
          HT[7].x = 400;
          HT[8].x = 60;
          HT[9].x = 300;
          HT[10].x = 100;
          HT[11].x = 350;
          HT[12].x = 150;
          HT[13].x = 300;
          HT[13].setWeight(0);
          HT[12].y = HT[13].y = 50;
          HT[3].y = HT[5].y = HT[10].y = HT[11].y = 130;
          HT[2].y = HT[6].y = HT[7].y = HT[9].y = 210;
          HT[1].y = HT[4].y = 290;
        }
        else if (i == 14) {
          HT[1].x = 70;
          HT[2].x = 240;
          HT[3].x = 350;
          HT[4].x = 130;
          HT[5].x = 40;
          HT[6].x = 300;
          HT[7].x = 180;
          HT[8].x = 210;
          HT[9].x = 100;
          HT[10].x = 270;
          HT[11].x = 140;
          HT[12].x = 310;
          HT[13].x = 90;
          HT[14].x = 260;
          HT[14].setWeight(0);
          HT[13].y = HT[14].y = 50;
          HT[5].y = HT[8].y = HT[11].y = HT[12].y = 130;
          HT[3].y = HT[7].y = HT[9].y = HT[10].y = 210;
          HT[1].y = HT[2].y = HT[4].y = HT[6].y = 290;
        }
        else if (i == 15) {
          HT[1].x = 70;
          HT[2].x = 250;
          HT[3].x = 360;
          HT[4].x = 130;
          HT[5].x = 40;
          HT[6].x = 310;
          HT[7].x = 180;
          HT[8].x = 220;
          HT[9].x = 100;
          HT[10].x = 280;
          HT[11].x = 140;
          HT[12].x = 320;
          HT[13].x = 90;
          HT[14].x = 270;
          HT[15].x = 180;
          HT[15].setWeight(0);
          HT[15].y = 50;
          HT[13].y = HT[14].y = 100;
          HT[5].y = HT[8].y = HT[11].y = HT[12].y = 170;
          HT[3].y = HT[7].y = HT[9].y = HT[10].y = 240;
          HT[1].y = HT[2].y = HT[4].y = HT[6].y = 310;
        }
        HT[s1].setParentNode(HT[i]);
        HT[s2].setParentNode(HT[i]);
        HT[s1].parent = i;
        HT[s2].parent = i;
        codePart = 8;
        break;
      case 8:
        codePanel.highlight(15);
        HT[i].setHighlight(true);
        HT[i].lchild = s1;
        HT[i].rchild = s2;
        codePart = 9;
        break;
      case 9:
        codePanel.highlight(16);
        HT[i].setWeight(HT[s1].getWeight() + HT[s2].getWeight());
        codePart = 10;
        break;
      case 10:
        codePanel.highlight(17);
        HT[i].setHighlight(false);
        HT[s1].setHighlight(false);
        HT[s2].setHighlight(false);
        i++;
        codePart = 5;
        break;
      case 11:
        codePanel.highlight(19);
        codePart = 12;
        break;
      case 12:
        codePanel.highlight(20);
        codePart = 13;
        break;
      case 13:
        codePanel.highlight(21);
        i = 1;
        codePart = 14;
        break;
      case 14:
        codePanel.highlight(22);
        HufTree.text5.setText("     " + String.valueOf(i));
        if (i <= n) {
          codePart = 15;
          HT[i].setHighlight(true);
        }
        else
          codePart = 23;
        break;
      case 15:
        codePanel.highlight(23);
        start = n - 1;
        HufTree.text9.setText("     " + String.valueOf(start));
        c = i;
        f = HT[i].parent;
        codePart = 16;
        break;
      case 16:
        codePanel.highlight(24);
        HufTree.text10.setText("     " + String.valueOf(c));
        HufTree.text12.setText("     " + String.valueOf(f));
        if (f != 0)
          codePart = 17;
        else
          codePart = 20;
        break;
      case 17:
        codePanel.highlight(25);
        if (HT[f].lchild == c)
          codePart = 18;
        else
          codePart = 19;
        break;
      case 18:
        codePanel.highlight(26);
        start--;
        HufTree.text9.setText("     " + String.valueOf(start));
        cd[i - 1] = "0" + cd[i - 1];
        HT[c].c = "0";
        HT[c].flag = true;
        hc = "'" + cd[i - 1] + "'";
        HufTree.text8.setText("     " + hc);
        c = f;
        f = HT[f].parent;
        codePart = 16;
        break;
      case 19:
        codePanel.highlight(27);
        cd[i - 1] = "1" + cd[i - 1];
        HT[c].c = "1";
        HT[c].flag = true;
        hc = "'" + cd[i - 1] + "'";
        HufTree.text8.setText("     " + hc);
        start--;
        HufTree.text9.setText("     " + String.valueOf(start));
        c = f;
        f = HT[f].parent;
        codePart = 16;
        break;
      case 20:
        codePanel.highlight(28);
        HT[i].number = cd[i - 1];
        codePart = 21;
        break;
      case 21:
        codePanel.highlight(29);
        codePart = 22;
        break;
      case 22:
        codePanel.highlight(30);
        HT[i].setHighlight(false);
        HufTree.text8.setText(" ");
        for (int j = 1; j < HT.length; j++)
          HT[j].flag = false;
        i++;
        codePart = 14;
        break;
      case 23:
        codePanel.highlight(31);
        codePart = 24;
        break;
      case 24:
        codePanel.highlight(32);
        doneFlag = true;
        break;
    }
  }

//函数Select（）用于在HT[1..i-1]选择parent为0且weight最小的两个节点
  public void Select(int i) {
    int min1 = 100;
    int min2 = 100;
    s1 = s2 = 0;
    boolean flag = false;
    for (int k = 1; k <= i; k++) {
      for (int j = 0; j < tag; j++) {
        if (k == record[j]) {
          flag = true;
          break;
        }
        else
          flag = false;
      }
      if (HT[k].getWeight() < min1 && !flag) {
        s1 = k;
        min1 = HT[k].getWeight();
        flag = false;
      }
    }
    for (int k = 1; k <= i; k++) {
      for (int j = 0; j < tag; j++) {
        if (k == record[j]) {
          flag = true;
          break;
        }
        else
          flag = false;
      }
      if (HT[k].getWeight() >= min1 && k != s1 && HT[k].getWeight() < min2 &&
          !flag) {
        s2 = k;
        min2 = HT[k].getWeight();
        flag = false;
      }
    }
    record[tag] = s1;
    tag++;
    record[tag] = s2;
    tag++;
  }

//函数drawTreeHTNode()用于绘制一棵树形图形
  public void drawTreeHTNode(Graphics g, HTNode Node, int j) {
    if (Node.getHighlight())
      g.setColor(Color.red);
    else
      g.setColor(new Color(105, 190, 171));
    if (j <= n) {
      g.fillOval(Node.x, Node.y, 25, 30);
      g.setColor(Color.black);
      g.drawOval(Node.x, Node.y, 25, 30);
    }
    else {
      g.fillRect(Node.x, Node.y, 25, 30);
      g.setColor(Color.black);
      g.drawRect(Node.x, Node.y, 25, 30);
    }
    g.setColor(Color.white);
    if (Node.getWeight() >= 100)
      g.drawString(String.valueOf(Node.getWeight()), Node.x + 3,
                   Node.y + 22);
    else
      g.drawString(String.valueOf(Node.getWeight()), Node.x + 8,
                   Node.y + 22);
    if (Node.getLeftNode() != null) {
      g.setColor(Color.black);
      g.drawLine(Node.x + 8, Node.y + 30, Node.getLeftNode().x + 10,
                 Node.getLeftNode().y);
    }
    if (Node.getRightNode() != null) {
      g.drawLine(Node.x + 14, Node.y + 30, Node.getRightNode().x + 10,
                 Node.getRightNode().y);
    }
  }
}