20182301 2019-2020-1 《数据结构与面向对象程序设计》哈夫曼实验报告

课程：《程序设计与数据结构》
班级： 1823
姓名： 赵沛凝
学号：20182301
实验教师：王志强
实验日期：2019年11月18日
必修/选修： 必修

1.实验内容

• 设有字符集：S={a,b,c,d,e，f,g,h,i,j,k,l,m,n.o.p.q,r,s,t,u,v,w,x,y,z}。
  给定一个包含26个英文字母的文件，统计每个字符出现的概率，根据计算的概率构造一颗哈夫曼树。
  并完成对英文文件的编码和解码。
  要求：
  1. 准备一个包含26个英文字母的英文文件（可以不包含标点符号等），统计各个字符的概率
  2. 构造哈夫曼树
  3. 对英文文件进行编码，输出一个编码后的文件
  4. 对编码文件进行解码，输出一个解码后的文件
  5. 撰写博客记录实验的设计和实现过程，并将源代码传到码云
  6. 把实验结果截图上传到云班课

2. 实验过程及结果

• 定义：
• 哈夫曼树（霍夫曼树）又称为最优树.
  • 路径和路径长度
    在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长
  • 结点的权及带权路径长度
    若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
  • 树的带权路径长度
    树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL
• 第一步，了解文件读入和文件写入的方法

//读取文件
File file = new File("E:\\idea\\week_12s\\input.txt");
Scanner scan = new Scanner(file);//Scanner的新用法
String s =scan.nextLine();//读取出来字符串
//写入文件
File file2 = new File("E:\\idea\\week_12s\\put.txt");
FileWriter fileWriter1 = new FileWriter(file1);
fileWriter1.write(result2);

• 第二步，打印频率

System.out.println("打印各字母出现频率：");
for (int i = 0; i < array.length; i++) {
        System.out.print((char) ('a' + i) + ":" + (double) array[i] / s.length() + "\n");
        }//把26个字母的概率都打出来

• 第三步：将数组转换为哈夫曼结点

HuffmanTreeNode[] huffmanTreeNodes = new HuffmanTreeNode[array.length];//构建哈夫曼树的结点
for (int i = 0; i < array.length; i++) {
         huffmanTreeNodes[i] = new HuffmanTreeNode(array[i], (char) ('a' + i), null, null, null);
        }

• 第四步：构建哈夫曼树

package com.company;



import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Stack;

public class HuffmanTree {
    HuffmanTreeNode root; // 根结点
    private String[] codes = new String[26];

    public HuffmanTree(HuffmanTreeNode[] a) throws EmptyCollectionException {
        HuffmanTreeNode parent = null;
        ArrayHeap<HuffmanTreeNode> heap;

        // 建立数组a对应的最小堆
        heap = new ArrayHeap<>();

        for(int i=0; i<a.length; i++) {
            heap.addElement(a[i]);
        }


        for(int i=0; i<a.length-1; i++) {
            HuffmanTreeNode left = heap.removeMin();  // 最小节点是左孩子
            HuffmanTreeNode right = heap.removeMin();


            parent = new HuffmanTreeNode(left.weight+right.weight,' ',left,right,null);
            left.parent = parent;
            right.parent = parent;

            heap.addElement(parent);
        }

        root = parent;
    }

    public String printTree() throws EmptyCollectionException {
        UnorderedListADT<HuffmanTreeNode> nodes =
                new ArrayUnorderedList();
        UnorderedListADT<Integer> levelList =
                new ArrayUnorderedList<Integer>();
        HuffmanTreeNode current;
        String result = "";
        int printDepth = this.getHeight()-1;
        int possibleNodes = (int)Math.pow(2, printDepth + 1);
        int countNodes = 0;

        nodes.addToRear(root);
        Integer currentLevel = 0;
        Integer previousLevel = -1;
        levelList.addToRear(currentLevel);

        while (countNodes < possibleNodes)
        {
            countNodes = countNodes + 1;
            current = nodes.removeFirst();
            currentLevel = levelList.removeFirst();
            if (currentLevel > previousLevel)
            {
                result = result + "\n\n";
                previousLevel = currentLevel;
                for (int j = 0; j < ((Math.pow(2, (printDepth - currentLevel))) - 1); j++)
                    result = result + " ";
            }
            else
            {
                for (int i = 0; i < ((Math.pow(2, (printDepth - currentLevel + 1)) - 1)) ; i++)
                {
                    result = result + " ";
                }
            }
            if (current != null)
            {
                result = result + current.weight;
                nodes.addToRear(current.left);
                levelList.addToRear(currentLevel + 1);
                nodes.addToRear(current.right);
                levelList.addToRear(currentLevel + 1);
            }
            else {
                nodes.addToRear(null);
                levelList.addToRear(currentLevel + 1);
                nodes.addToRear(null);
                levelList.addToRear(currentLevel + 1);
                result = result + " ";
            }
        }
        return result;
    }

    private int getHeight() {
        return height(root);
    }

    private int height(HuffmanTreeNode node)
    {
        if(node==null){
            return 0;
        }
        else {
            int leftTreeHeight = height(node.left);
            int rightTreeHeight= height(node.right);
            return leftTreeHeight>rightTreeHeight ? (leftTreeHeight+1):(rightTreeHeight+1);
        }
    }

    protected void inOrder( HuffmanTreeNode node,
                            ArrayList<HuffmanTreeNode> tempList)
    {
        if (node != null)
        {
            inOrder(node.left, tempList);
            if (node.element!=' ')
                tempList.add(node);

            inOrder(node.right, tempList);
        }
    }

    public String[] getEncoding() {
        ArrayList<HuffmanTreeNode> arrayList = new ArrayList();
        inOrder(root,arrayList);
        for (int i=0;i<arrayList.size();i++)
        {
            HuffmanTreeNode node = arrayList.get(i);
            String result ="";
            int x = node.element-'a';
            Stack stack = new Stack();
            while (node!=root)
            {
                if (node==node.parent.left)
                    stack.push(0);
                if (node==node.parent.right)
                    stack.push(1);

                node=node.parent;
            }
            while (!stack.isEmpty())
            {
                result +=stack.pop();
            }
            codes[x] = result;
        }
        return codes;
    }

    public HuffmanTreeNode getRoot() {
        return root;
    }
}

• 第五步：进行加密

//进行编码：二进制加法
        String result = "";
        for (int i = 0; i < s.length(); i++) {
            int x = s.charAt(i) - 'a';
            result += codes[x];
        }
        System.out.println("编码结果：" + result);

• 第六步：解码

//进行解码
        String result2 = "";
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) == '0') {
                if (huffmanTreeNode.left != null) {
                    huffmanTreeNode = huffmanTreeNode.left;
                }
            } else {
                if (s1.charAt(i) == '1') {
                    if (huffmanTreeNode.right != null) {
                        huffmanTreeNode = huffmanTreeNode.right;
                    }
                }
            }
            if (huffmanTreeNode.left == null && huffmanTreeNode.right == null) {
                result2 += huffmanTreeNode.element;//把一个个字母加起来
                huffmanTreeNode = huffmanTree.getRoot();//移到上一个结点
            }
        }

3. 实验过程中遇到的问题和解决过程

• 问题1：为什么写入文件，但是文件不出现内容呢？
• 问题1解决方案：

代码链接

其他（感悟、思考等）

到现在，我已经学习了很多树了，逐渐有了树的思维，以后也会多多运用的。

参考资料

• 哈夫曼树的java实现
• (哈夫曼树)HuffmanTree的java实现

20182301 2019-2020-1 《数据结构与面向对象程序设计》哈夫曼实验报告

原文：https://www.cnblogs.com/zhaopeining/p/11900292.html