精华内容
下载资源
问答
  • 哈夫曼树算法压缩文件

    千次阅读 2016-03-12 15:22:31
    今天上午上了哈夫曼算法压缩的课,我学习到了用哈夫曼算法压缩文件,可以将一个文件压缩百分之六十左右的大小。 具体原理是:文件是由一个个字节组成,而字节有自己的ASCII码值,然后用一个整形数组把文件的ASCII...

    今天上午上了哈夫曼算法压缩的课,我学习到了用哈夫曼算法压缩文件,可以将一个文件压缩百分之六十左右的大小。

    具体原理是:文件是由一个个字节组成,而字节有自己的ASCII码值,然后用一个整形数组把文件的ASCII码值记下来,出现了一个就在其对应的ASCII值得int数组下标加一。然后用哈夫曼算法处理这个整形数组,得到哈夫曼编码值,然后读入文件的哈夫曼编码值,最后写入压缩文件。

    哈夫曼压缩需要三个容器,一个是存数据字节,一个是哈夫曼节点,一个是存哈夫曼编码

    代码如下:

    private int[] data = new int[256];
    	private LinkedList<HuffmNode> list = new LinkedList<HuffmNode>();
    	private String[] codestr = new String[256];
    	//代码块:让哈夫曼编码置为空字符串
    	{
    		for(int i=0;i<codestr.length;i++){
    			codestr[i] = "";
    		}
    	}

    压缩文件分五个步骤执行:

    public static void main(String[] args) {
    		Compress com = new Compress();
    		//1.读取源文件,统计每个字节出现次数
    		com.datatime();
    		//2.构建哈夫曼节点
    		com.creatNode();
    		//3.构建哈夫曼树
    		com.creatHuffmTree();
    		//4.得到哈夫曼编码
    		com.getCode(com.list.get(0),"");
    		//5.再次读入文件的哈夫曼编码,并写入压缩文件(保存数据顺序,用于解压);
    		com.writeFile();
    	}

    具体方法代码如下:

    public void datatime(){
    		try {
    			//文件输入流读取test.txt文件
    			FileInputStream fis = new FileInputStream("C:\\Users\\asus\\Desktop\\test.txt");
    			int value = fis.read();
    			while(value!=-1){
    				data[value] ++;
    				value = fis.read();
    			}
    		} catch (Exception e) {
    			e.printStackTrace();
    		}
    	}

    创建节点、哈夫曼树和构造哈夫曼编码和上一个博客一样,略。

    <span style="font-size:24px;">//压缩文件的实现
    	public void writeFile(){
    		//1.读文件,得到编码串
    		try {
    			FileOutputStream fos = new FileOutputStream("C:\\Users\\asus\\Desktop\\test.zip");
    			FileInputStream fis = new FileInputStream("C:\\Users\\asus\\Desktop\\test.txt");
    			int value = fis.read();
    			String str = "";
    			while(value!=-1){
    				String c = codestr[value];
    				str = str + c ;
    				value = fis.read();
    			}
    			//2.压缩结果写入压缩文件
    			while(str.length()>=8){
    				String s = str.substring(0,8);
    				int v = StringToInt(s);
    				fos.write(v);
    				fos.flush();
    				str = str.substring(8);	//截取从第八位字节后面的字节数
    			}
    			//3.把最后一点字节写出去
    			int zero = 8 - str.length();
    			for(int i=0;i<zero;i++){
    				str = str + "0";
    			}
    			int v = StringToInt(str);
    			fos.write(v);
    			fos.flush();
    			//4.把补零个数写入文件
    			fos.write(zero);
    			fos.flush();
    			fis.close();
    			fos.close();
    		} catch (Exception e) {
    			e.printStackTrace();
    		}
    	}</span>
    这里涉及到了八位字符串转成int型的方法:

    public int StringToInt(String s){
    		int c1 = (int)s.charAt(0)-48;
    		int c2 = (int)s.charAt(1)-48;
    		int c3 = (int)s.charAt(2)-48;
    		int c4 = (int)s.charAt(3)-48;
    		int c5 = (int)s.charAt(4)-48;
    		int c6 = (int)s.charAt(5)-48;
    		int c7 = (int)s.charAt(6)-48;
    		int c8 = (int)s.charAt(7)-48;
    		int result = c8*1+c7*2+c6*4+c5*8+c4*16+c3*32+c2*64+c1*128;
    		return result;
    	}

    下面是程序操作的结果(图):






    这就是今天所学到的哈夫曼压缩,明天就学习哈夫曼解压了,加油!奋斗奋斗奋斗



    展开全文
  • 输入一串字符,根据给定的字符串中字符出现的频率建立相应的哈夫曼树,构造哈夫曼编码表,在此基础上可以对压缩文件进行压缩(即编码),同时可以对压缩后的二进制编码文件进行解压(即译码)。 输入要求 多组数据,每组数据1...

    写在前边:这是一个菜鸡的19年秋季学期数据结构实验课,趁寒假整理一下,欢迎各位大佬指正)
    【实验目的】

    1. 掌握哈夫曼树的构造算法。
    2. 掌握哈夫曼编码的构造算法。
      【实验内容】
      问题描述
      输入一串字符,根据给定的字符串中字符出现的频率建立相应的哈夫曼树,构造哈夫曼编码表,在此基础上可以对压缩文件进行压缩(即编码),同时可以对压缩后的二进制编码文件进行解压(即译码)。
      输入要求
      多组数据,每组数据1行,为一个字符串(只考虑26个小写字母即可)。当输入字符串为"0”时,输入结束。
      输出要求
      每组数据输出2n+3行(n为输入串中字符类别的个数)。第1行为统计出来的字符出现频率(只输出存在的字符,格式为字符:频度),每两组字符之间用一个空格分隔,字符按照ASCII码从小到大的顺序排列。第2行至第2n行为哈夫曼树的存储结构的终态(参照实验提示表5.2,一行当中的数据用空格分隔)。第2n+1行为每个字符的哈夫曼编码(只输出存在的字符,格式为字符:编码),每两组字符之间用一个空格分隔,字符按照ASCII码从小到大的顺序排列。第2n+2行为编码后的字符串,第2n+3行为解码后的字符串(与输入的字符串相同)。
      输入样例
      aaaaaaabbbbbccdddd
      aaccb
      0
      输出样例
      a:7 b:5 c2 d:4
      1 7 7 0 0
      2 5 6 0 0
      3 2 5 0 0
      4 4 5 0 0
      5 6 6 3 4
      6 1 1 7 2 5
      7 1 8 0 1 6
      a:0 b:10 c:110 d:111
      00000001010101011011011111
      aaaaaaabbbbbccdddd
      a:2 b:1 c:3
      1 2 4 0 0
      2 1 4 0 0
      3 3 5 0 0
      4 3 5 2 1
      5 6 0 3 4
      a:11 b:10 c:0
      111110000
      aabccc
      【实验提示】
      首先,读入一行字符串,统计每个字符出现的频率;然后,根据字符出现的频率利用提示算法1建立相应的哈夫曼树;最后,根据得到的哈夫曼树利用算法2求出每个字符的哈夫曼编码。
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<string>
    #define MAX 100
    using namespace std;
    
    int coun[26]; //频率 
    char saveletter[26];//存字母 
    char temp[MAX];//暂存被译码串 
    
    typedef struct htnode
    {
        int weight;
        int lchild, rchild, parent;
        char data;
        int frequency;//出现频率 
    }*huftree;
    
    typedef char **hufcode;
    
    void select(huftree &hf, int x, int &s1, int &s2)//在叶子结点里找最小的两个 
    {
        
    int min = 999, cmin = 999;//最小值和次小值 
        int i = 1;
        while (i <= x)
        {
            if (hf[i].parent == 0)
            {
                if (hf[i].weight < min)//寻找权值最小 
                {
                    min = hf[i].weight;
                    s1 = i;
                }
                i++;
            }
            else
                i++;
        }
        int flag = s1;
        i = 1;
        while (i <= x)
        {
            if (hf[i].parent == 0)
            {
                if ((hf[i].weight > min && hf[i].weight < cmin) || (hf[i].weight == min && flag != i))//找次小值 
                {
                    cmin = hf[i].weight;
                    s2 = i;
                }
                i++;
            }
            else
                i++;
        }
    
       
    }
    
    void Create(huftree &hf, int n)//叶子为n的哈树有2n-1个结点 
    {
        int m = 2 * n - 1, s1 = 0, s2 = 0;
    
        if (n <= 1) return;
    
        hf = new htnode[m + 1];//0号单元不用
    
        for (int i = 1; i <= m; i++)//都初始化为0 
        {
            hf[i].parent = 0;
            hf[i].rchild = 0;
            hf[i].lchild = 0;
            hf[i].data = saveletter[i - 1];//字母
        }
    
        for (int i = 1; i <= n; i++)
            hf[i].weight = coun[i - 1];//输入权值 
    
        for (int i = n + 1; i <= m; i++)//前n个为叶子,后面需要构建 
        {
            select(hf, i - 1, s1, s2);//选择最小的两个节点,返回序号 
            hf[s1].parent = i;
            hf[s2].parent = i;//结点双亲变为i
            hf[i].lchild = s1;
            hf[i].rchild = s2;//i的左右孩子
            hf[i].weight = hf[s1].weight + hf[s2].weight;
            //i权值更改 
        }
    
    }
    
    
    void Show(huftree &hf, int x)
    {
        for (int i = 1; i <= 2 * x - 1; i++)
        {
            cout << i << " ";
            cout << hf[i].weight << " " << hf[i].parent << " " << hf[i].lchild << " " << hf[i].rchild << endl;
        }
    }
    
    void count(char str[], huftree &hf, int &n)//出现频率 ,字母个数 
    
    {
        int num[26];
        char ch;
        int i = 0, j = 0;
        memset(num, 0, sizeof(num));
        while (str[i] != '\0')
        {
            j = str[i] - 97;
            num[j]++;
            i++;
        }
        j = 0;
        for (i = 0; i < 26; i++)
        {
            if (num[i] != 0)
            {
                saveletter[j] = char(i + 97);
                coun[j] = num[i];
                j++;
            }
        }
        n = j;
        for (int i = 0; i < n; i++)
        {
            if (i == n - 1)
                cout << saveletter[i] << ":" << coun[i];
            else
                cout << saveletter[i] << ":" << coun[i] << " ";
        }
        cout << endl;
    }
    
    void hfcode(huftree &hf, hufcode &hc, int n)
    {
        char *cd;
        int start = 0, c, f;
        hc = new char*[n + 1];//编码表 
        cd = new char[n];//每个字符的编码一定小于n 
        cd[n - 1] = '\0';
        for (int i = 1; i <= n; i++)
        {
            start = n - 1;
            c = i;
            f = hf[i].parent;
    
            while (f != 0)//不是根节点
            {
                start--;
    
                if (hf[f].lchild == c)
                    cd[start] = '0';
                else
                    cd[start] = '1';
    
                c = f;//向上回溯 
                f = hf[f].parent;
            }
            hc[i] = new char[n - start];
            strcpy(hc[i], &cd[start]);//把临时空间的编码复制到编码表中 
        }
        delete cd;
    
        int i, j, z = 0;
        for (j = 1; j <= n; j++)//输出字母编码 
        {
            if (j == n)
                cout << saveletter[j - 1] << ":" << hc[j];
            else
                cout << saveletter[j - 1] << ":" << hc[j] << " ";
        }
        cout << endl;
    }
    void transtonum(huftree &hf, hufcode &hc, int n, char str[])
    {
        for (int i = 0; str[i] != '\0'; i++)
            for (int j = 1; j <= n; j++)
                if (str[i] == saveletter[j - 1])
                {
                    cout << hc[j];
                    strcat(temp, hc[j]);
                }
    
        cout << endl;
    }
    void transtoletter(huftree &hf, hufcode &hc, int n)
    {
        int i = 2 * n - 1;
        int j = 0;
    
        while (temp[j] != '\0')
        {
            if (temp[j] == '0')
                i = hf[i].lchild;   //左孩子
            else if (temp[j] == '1')
                i = hf[i].rchild;    //右孩子
            if (hf[i].lchild == 0)
            {
                cout << hf[i].data;
                i = 2 * n - 1;
            }
            j++;   //无论是否找到叶子节点都读取下一个编码串字符
        }
        cout << endl;
    }
    
    int main()
    {
    
        while (1)
        {
            huftree hf;
            hufcode hc;
            int n;
            char str[MAX];
            scanf("%s", &str);
            if (str[0] == '0')
                break;
            count(str, hf, n);
            Create(hf, n);
            Show(hf, n);
            hfcode(hf, hc, n);
            transtonum(hf, hc, n, str);
            transtoletter(hf, hc, n);
            memset(coun, 0, sizeof(coun));
            memset(saveletter, '\0', sizeof(saveletter));
            memset(temp, '\0', sizeof(temp));
            delete hf;
            delete hc;
        }
        return 0;
    }
    
    展开全文
  • Java小项目之哈夫曼树文件压缩和解压缩(一)哈夫曼树的构造 前言:在了解哈夫曼树之前,我们还是先看下树的相关知识吧! 一、数据结构中树的相关知识 数据结构是计算机存储、组织数据的方式。数据结构是指...

    Java小程序之哈夫曼树与文件压缩和解压缩(一)哈夫曼树构造篇

    前言:在了解哈夫曼树之前,我们还是先看下树的相关知识吧!

    一、数据结构中树的相关知识
    数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集      合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和               索引技术有关。数据结构主要包含集合、线性结构、树行结构和图行结构;

    这次主要看下树形结构:

    1、树的定义:树:是由n(n>=1)个有限节点组成一个具有层次关系的集合
    2、的相关术语
    节点度:一个节点含有子树的个数称为该节点的度
    树的度:一棵树中,最大的节点的度为树的度
    叶子节点:度为零的节点
    父亲节点:若一个节点含有子节点,则当前节点为改子节点的父亲节点
    子节点:一个节点含有子树,则子树的根节点为改节点的子节点
    兄弟节点:具有相同父亲节点的子节点互为兄弟节点
    节点层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推
    树的深度(高度):树中节点最大的层次
    其他:堂兄弟节点、子孙、森林

    3、树的分类
    无序树:树中的节点次序是没有规律的
    有序树:指树中同层结点从左到右有次序排列,这样的树称为有序树。
    1)二叉树:每个节点最多含有两个子树的树称为二叉树
    2)非二叉树:所有不是二叉树的树都属于非二叉树
    4、二叉树
    定义:二叉树是一种特殊的树形结构,每个节点至多只有两颗子树,并且子树有左右之分,其次序不能随意颠倒,是有序树的一种。
    注意:二叉树是由一个根结点、两棵互不相交的左子树和右子树组成。
    二叉树分类
          满二叉树:对于上述的完全二叉树,如果去掉其第d层的所有节点,那么剩下的部分就构成一个满二叉树
          完全二叉树:对于一颗二叉树,假设其深度为d(d>1)。除了第d层外,其它各层的节点数目均已达最大值,且第d层所有节点从左向右连续地紧密排列,这样的二叉树被称为完全二叉树;
    5、完全二叉树性质
    若根结点的层次为1,则二叉树第i层最多有2的(i-1)次方个结点。
    在高度为k的二叉树中,则最多有2k-1个结点(k≥0)
    设一棵二叉树节点个数为n,则父节点个数为n/2。
    一棵具有n个结点的完全二叉树,对序号为i(0≤i<n)的结点,则:
    若i=0,则i为根结点,无父母结点;若i >0,则i的左右子结点序号为:
    若2i+1<n,则i的左孩子结点序号为2i+1;否则i无左孩子。
    若2i+2<n,则i的右孩子结点序号为2i+2;否则i无右孩子。

    6、哈夫曼树
    给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。

    有关哈夫曼树的术语
    路径长度:
    节点路径长度:从一个节点(根节点)到另外一个节点所经过的路径的分支数目
    树的路径长度:指树种所有节点的路径长度之和
    权值:
    指的是所有叶子节点的date域,存放一个数值,用来表示当前叶子节点的数据,那这个值就是权值
    带权路径长度:
    所有叶子节点的带权路径长度之和
    最优二叉树(哈弗曼树):
    1、通过所有权值节点,形成一个二叉树,最终这个二叉树的带权路径最小,则此二叉树是哈夫曼树(最优二叉树)
    2、树的结构不止一个,同一层的节点,可以左右替换

      构造哈夫曼树的思路:

    1、新建一个节点类

    2把数据封装成节点,放到容器中,用于建立一个森林

    3循环寻找权值最小的两个节点,用于构造新的节点

        需要定义一个方法,来寻找当前节点插入到森林中的位置

    获取哈夫曼编码(用于后面文件的压缩与解压缩)


    二、二叉树的构造源代码:

     节点类:

    package MyTree;
    
    public class Node {
    	//节点类、
    	public int data;
    	public Node left;
    	public Node right;
    
    }
    

    二叉树的构造过程以及遍历:
    package MyTree;
    
    import java.util.ArrayList;
    
    public class TreeList {
    	
    	public int [] values ={1,2,3,4,5,6,7,8,9};
    	public ArrayList<Node> list = new ArrayList<Node>();
    	
    	public static void main(String[] args) {
    		TreeList tree = new TreeList();
    		Node root=tree.createTree();
    		System.out.println("前序遍历:");
    		tree.lookTree1(root);
    		System.out.println("中序遍历:");
    		tree.lookTree2(root);
    		System.out.println("后序遍历:");
    		tree.lookTree3(root);
    	}
    	
    	public Node createTree(){
    		//封装成节点
    		for (int i = 0; i < values.length; i++) {
    			Node node = new Node();
    			node.data=values[i];
    			list.add(node);
    		}
    		//构造二叉树
    		for (int i = 0; i < list.size()/2-1; i++) {
    			Node node =list.get(i);
    			node.left=list.get(2*i+1);
    			node.right=list.get(2*i+2);
    		}
    		//构造最后一个父节点
    		Node lastNode = list.get(list.size()/2-1);
    		lastNode.left=list.get((list.size()/2-1)*2+1);
    		if(list.size()%2==1){
    		lastNode.right=list.get((list.size()/2-1)*2+2);
    		}
    		
    		return list.get(0);
    	}
    	
    	//前序遍历
    	public void lookTree1(Node root){
    		
    		System.out.print(root.data+"  ");
    		if(root.left!=null){
    			lookTree1(root.left);
    		}
    		if(root.right!=null){
    			lookTree1(root.right);
    		}
    	}
    	
    	//中序遍历
    	public void lookTree2(Node root){
    		
    		if(root.left!=null){
    			lookTree2(root.left);
    		}
    		System.out.print(root.data+"  ");
    		if(root.right!=null){
    			lookTree2(root.right);
    		}
    	}
    	
    	//后续遍历
    	public void lookTree3(Node root){
    		
    		if(root.left!=null){
    			lookTree3(root.left);
    		}
    		
    		if(root.right!=null){
    			lookTree3(root.right);
    		}
    		
    		System.out.print(root.data+"  ");
    	}
    
    }
    



    、构造哈夫曼树的源代码:
    哈夫曼节点类:
    package com.bluesky.huffm;
    
    public class HuffmNode {
    	//构造HuffmNode类
    	private int data;
    	private HuffmNode left;
    	private HuffmNode right;
    	//HuffmNode类构造函数
    	public  HuffmNode(int data) {
    		this.data=data;
    	}
    	
    	//封装属性
    	public int getData() {
    		return data;
    	}
    	public void setData(int data) {
    		this.data = data;
    	}
    	public HuffmNode getLeft() {
    		return left;
    	}
    	public void setLeft(HuffmNode left) {
    		this.left = left;
    	}
    	public HuffmNode getRight() {
    		return right;
    	}
    	public void setRight(HuffmNode right) {
    		this.right = right;
    	}
    
    }
    

    哈夫曼树的构造:
    package com.bluesky.huffm;
    
    import java.util.LinkedList;
    
    public class HuffmTree {
    	
    	public int [] datas ={2,1,6,4,7,9,12,3};
    	public LinkedList<HuffmNode> list = new LinkedList<HuffmNode>();
    	
    	public HuffmNode createTree() {
    		//按照从小到大的将数据封装成节点
    		for (int i = 0; i < datas.length; i++) {
    			HuffmNode node = new HuffmNode(datas[i]);
    			//得到需要插入的位置索引
    			int index=getIndex(node);
    			//将数据添加到容器中
    			list.add(index, node);
    		}
    		//构造哈夫曼树
    		while(list.size()>1){
    			//移除容器中的第一个节点
    			HuffmNode firstNode =list.removeFirst();
    			//容器中原来的第二个节点变成新的第一个节点
    			HuffmNode secondNode =list.removeFirst();
    			//构造父节点数据域
    			HuffmNode fatherNode = new HuffmNode(firstNode.getData()+secondNode.getData());
    			//构造父节点左子叶
    			fatherNode.setLeft(firstNode);
    			//构造父节点右子叶
    			fatherNode.setRight(secondNode);
    			//得到构造好的父节点的索引
    			int index=getIndex(fatherNode);
    			//将父节点加入森林
    			list.add(index, fatherNode);
    		}
    		//返回根节点
    		return list.getFirst();
    	}
    	
    	//得到索引
    	public int getIndex(HuffmNode node) {
    		for (int i = 0; i < list.size(); i++) {
    			if(node.getData()>list.get(i).getData()){
    				continue;
    			}else {
    				return i;
    			}
    		}
    		//如果比容器中的任何一个数大,则插入最后面
    		return list.size();
    	}
    	
    	//得到哈夫曼编码
    	public void getHuffmCode(HuffmNode root,String code) {
    		if(root.getLeft()!=null){
    			getHuffmCode(root.getLeft(),code+"0");
    		}
    		if(root.getRight()!=null){
    			getHuffmCode(root.getRight(),code+"1");
    		}
    		if(root.getLeft()==null && root.getRight()==null){
    			System.out.println(code);
    		}
    	}
    }
    

    程序入口:
    package com.bluesky.huffm;
    
    public class Test {
    	
    	public static void main(String[] args) {
    		HuffmTree tree = new HuffmTree();
    		HuffmNode root = tree.createTree();
    		tree.getHuffmCode(root, "");
    	}
    
    }
    

    四、总结:
    树是属于数据结构方面的知识,以前自己在学数据结构的时候,就被老师要求自己去构造一些诸如链表,队列等数据结构,并且要能够实现这些数据结构的增删查改等功能!链表和队列还算简单的了,树和图就真的有点蒙了,其实数据结构这门课程还是挺重要的了,这不,我们马上就要看到哈夫曼树的用处了;树的递归遍历真的有点难理解,都不知道递归到哪里去了;一直纠结就会陷入死循环,有时也不要那么纠结,你递归下去,脑袋立马蒙了,当然,有些逻辑非常清楚的人就不会,只能说,我还需要历练!
    哈夫曼树,也称最优二叉树,是树型结构中比较重要的知识,以前只知道它大有用处,却不知到它该怎么用,现在算是见证到哈夫曼树的威力了!构造哈弗曼树的过程中,需要注意,移除子节点后,第二字节点就变成了第一个节点,这里需要注意下!
    共勉!

    展开全文
  • Tips:注意二进制读写文件回车为:\r\n 代码详细分析改天再填坑。。。 还有单纯形算法--> github:https://github.com/caitian521/algorithm #include <stdio.h> #include <stdlib.h> #...

    Tips:注意二进制读写文件回车为:\r\n

    代码详细分析改天再填坑。。。

    还有单纯形算法-->  github:https://github.com/caitian521/algorithm

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <algorithm>
    #include <iostream>
    #include <list>
    #include <string>
    using namespace std;
    
    template<class Type> 
    struct huffnode{
        int weight;
        Type ch;
        char code[50];
        int parent,leftchild,rightchild;
    public:
        huffnode():ch(Type()),weight(0),parent(-1),leftchild(-1),rightchild(-1)
        {}
    
    };
    class hufftree
    {
        list<huffnode<char> > hufflist;
        huffnode<char> *nodetable;
        char file[200];
        int num;
    public:
        hufftree(const char *filename);
        ~hufftree();
        void Addchar(const char s);
        void CreateTree();
        bool SelectMin(const int pos,int &minst);
        void CreateCode();
        void Compression();
        void showcode();
        void CreateConfig();
        void Decompression();
        int Match(const char prebuff[],const char buff[],int &endat,FILE *fout,int &cnt);
        void print(int p,FILE *fout,int &cnt);
    };
    
    hufftree::hufftree(const char *filename)
    {
        strcpy(file,filename);
        FILE *fin1 = fopen(file,"rb");
        char s;
        s = fgetc(fin1);
        while(s !=EOF)
        {
            if(s=='\r')
                s = fgetc(fin1);
            Addchar(s);
            s = fgetc(fin1);
        }
        num = hufflist.size();
        printf("%d\n",num);
        nodetable = new huffnode<char>[num*2-1];
        list<huffnode<char> >::iterator iter = hufflist.begin();
        for(int i = 0;i<num && iter!=hufflist.end();i++,iter++)
        {
            nodetable[i].ch = iter->ch;
            nodetable[i].weight = iter->weight;
        }
        fclose(fin1);
    }
    
    void hufftree::Addchar(const char s)
    {
        list<huffnode<char> >::iterator iter = hufflist.begin();
        for(;iter!=hufflist.end();iter++)
        {
            if(iter->ch==s)
            {
                iter->weight++;
                break;
            }
        }
        if(iter==hufflist.end())
        {
            huffnode<char> node;
            node.weight = 1;
            node.ch = s;
            hufflist.push_back(node);
        }
    
    }
    
    void hufftree::CreateTree()
    {
        int left = 0,right=0;
        for(int i = num;i<2*num-1;i++)
        {
            SelectMin(i-1,left);
            nodetable[left].parent = i;
            SelectMin(i-1,right);
            nodetable[right].parent = i;
            nodetable[i].weight = nodetable[left].weight+nodetable[right].weight;
            nodetable[i].leftchild = left;
            nodetable[i].rightchild = right;
        }
    }
    bool hufftree::SelectMin(const int pos,int &minst)
    {
        int i=0,minnum=0;
        while(minnum<pos)
        {
            if(nodetable[i].parent==-1)
                break;
            minnum++;
        }
        if(minnum>pos)//上一个while的目的
            return false;//ruguo false???
        while(i<=pos)
        {
            if(nodetable[i].parent == -1 && nodetable[minnum].weight>nodetable[i].weight)
                minnum = i;
            i++;
        }
        minst = minnum;
    }
    void hufftree::CreateCode()
    {
        int i;
        int c,p;
        int start;
        char *tmpcode = new char[num];
        tmpcode[num] = '\0';
        for(i = 0;i<num;i++)
        {
            start = num;
            c = i;
            while((p=nodetable[c].parent)>0)
            {
                start--;
                tmpcode[start]=(nodetable[p].leftchild==c)?'0':'1';
                c = p;
            }
            strcpy(nodetable[i].code,&tmpcode[start]);//
        }
    }
    
    void hufftree::Compression()
    {
        //freopen(file,"r",stdin);
        FILE *fin = fopen(file,"rb");
        FILE *fout = fopen("compression.txt","wb");
        char s;
        char *thiscode = new char[256];
        unsigned char inch = 0;
        int index = 0;
        s = fgetc(fin);
        int countch = 10;
        while(s != EOF)
        {
            if(s=='\r')
                s = fgetc(fin);
            for(int i = 0;i<num;i++)
            {
                if(nodetable[i].ch==s)
                {
                    thiscode = nodetable[i].code;
                    break;
                }
            }
            countch--;
            if(countch>0)
                cout<<s<<"  "<<thiscode<<endl;
            for(int t = 0;t<strlen(thiscode);t++)
            {
    
                inch <<= 1;
                if(thiscode[t]=='1')
                    inch|=1;
                index++;
                if(index==8)
                {
                    fputc(inch,fout);
                    index = 0;
                    inch = 0;
                }
            }
            s = fgetc(fin);
        }
        if(index>0)
        {
            inch =inch<<(8-index);
            fputc(inch,fout);
        }
        fclose(fin);
        fclose(fout);
    }
    hufftree::~hufftree()
    {
    
    }
    void hufftree::showcode()
    {
        for(int i = 0;i<num;i++)
        {
            cout<<nodetable[i].ch<<"--"<<nodetable[i].code<<endl;
        }
    }
    void hufftree::CreateConfig()
    {
        char configname[200];
        strcpy(configname,"huffman.config");
        cout<<configname<<endl;
        FILE *fout = fopen(configname,"w");
        for(int i = 0;i<num;i++)
        {
            fputs(nodetable[i].code,fout);
            fputc(',',fout);
            fputc(nodetable[i].ch,fout);
            fputc('\n',fout);
        }
        fclose(fout);
    }
    void hufftree::print(int p,FILE *fout,int &cnt)
    {
        if(cnt>0)
        {
            if(nodetable[num*2-2].weight-cnt<10)
                cout<<"yes:"<<nodetable[p].ch<<endl;
            char ch;
            ch = nodetable[p].ch;
            if(ch=='\n')
                fputc('\r',fout);
            fputc(nodetable[p].ch,fout);
        }
        cnt--;
    }
    int hufftree::Match(const char prebuff[],const char buff[],int &endat,FILE *fout,int &cnt)
    {
        int p = num*2-2;
        int Child = nodetable[p].leftchild;
        int flag = 0;
        int start = 0;
        int sign = 0;
        for(int i = 0;prebuff[i]!='\0';i++)
        {
            if(Child == -1)
            {
                print(p,fout,cnt);
                p = num*2-2;
                start = i;
            }
            if(prebuff[i]=='0')
            {
                p = nodetable[p].leftchild;
            }
            else{
                p = nodetable[p].rightchild;
            }
            Child = nodetable[p].leftchild;
        }
        if(Child == -1)//
        {
            print(p,fout,cnt);
            p = num*2-2;
            start = 0;
        }
        else
            if(prebuff[0]!='\0')
                flag = 1;
        for(int i = 0;i<8;i++)
        {
            if(Child == -1)
            {
                print(p,fout,cnt);
                p = num*2-2;
                sign = i;
                flag = 0;
            }
            if(buff[i]=='0')
            {
                p = nodetable[p].leftchild;
            }
            else{
                p = nodetable[p].rightchild;
            }
            Child = nodetable[p].leftchild;
        }
        if(Child == -1)
        {
            print(p,fout,cnt);
            sign = 8;//
            endat = sign;
        }
        else{
                endat = sign;
            if(flag)
                return start;
        }
        return -1;
    }
    
    void hufftree::Decompression()
    {
        FILE *fin = fopen("compression.txt","rb");
        FILE *fout = fopen("new.txt","wb");
        unsigned char readnum;
        readnum = fgetc(fin);
        int endat = 0;
        int sign = 0;
        char buff[9];
        char prebuff[33];
        prebuff[0] = '\0';
        buff[8] = '\0';
        for(int i = 0;i<8;i++)
            buff[i] = '0';
        cout<<"depression"<<endl;
        int cnt = nodetable[num*2-2].weight;
    
        while(!feof(fin))//readnum!=EOF
        {
    
            for(int i = 7;i>=0;i--)
            {
                buff[i]=(readnum&1)?'1':'0';
                readnum >>= 1;
            }
            sign = Match(prebuff,buff,endat,fout,cnt);
            if(sign>=0)
            {
                char temp[32];
                strcpy(temp,&prebuff[sign]);
                prebuff[0]='\0';
                strcpy(prebuff,temp);
                strcat(prebuff,buff);
                cout<<"doushengle:"<<prebuff<<endl;
            }
            else
            {
                if(endat<8)
                    strcpy(prebuff,&buff[endat]);
                else
                    prebuff[0] = '\0';
            }
            readnum = fgetc(fin);
            endat = 0;
            sign = 0;
        }
        fclose(fin);
        fclose(fout);
    }
    int main()
    {
        hufftree hf("E:\\我会编程啦\\我的练习\\算法设计-研究生\\哈夫曼\\Aesop_Fables.txt");
        hf.CreateTree();
        hf.CreateCode();
        hf.showcode();
        hf.Compression();
        hf.Decompression();
    }
    //这里要说一个背景,那就是在windows下,它会做一个处理,就是写文件时,换行符会被转换成回车,换行符存在磁盘文件上,而读磁盘上的文件时,它又会进行逆处理,就是把文件中连续的回车,换行符转换成换行符。
    //因此,在读取一个磁盘文件时,文本方式读取到文件内容很有可能会比二进制文件短,因为文本方式读取要把回车,换行两个字符变成一个字符,相当于截短了文件。但是为什么仅仅是可能呢?因为可能文中中不存在连着的45,42这两个字节(45是CR回车的ASCII码,42是换行符CL的ASCII码),也就不存在“截短”操作了,因此读到的内容是一样的。
    //具体的来说,文件文件(以文本方式写的),最好以文本方式读。二进制文件(以二进制方式写的),最好以二进制方式读。不然可能会不正确。上面的已经分析了。

     

    转载于:https://www.cnblogs.com/caitian/p/8001148.html

    展开全文
  • 输入一串字符串,根据给定的字符串中字符出现的频率建立相应哈夫曼树,构造哈夫曼编码表,在此基础上可以对待压缩文件进行压缩(即编码),同时可以对压缩后的二进制编码文件进行解压(即译码)。 输入 多组数据,每...
  • 输入一串字符串,根据给定的字符串中字符出现的频率建立相应的哈夫曼树,构造哈夫曼编码表,在此基础上对字符串进行压缩(即编码),同时对压缩后的二进制编码文件进行解压(即译码)。
  • 利用哈夫曼树编写的解压缩算法,可以对文件进行解压缩
  • 1.哈夫曼树哈夫曼树又称最优树(二叉树),是一类带权路径最短的树。构造这种树的算法最早是由哈夫曼(Huffman)1952年提出,这种树在信息检索中很有用。结点之间的路径长度:从一个结点到另一个结点之间的分支数目。...
  • 输入一串字符串,根据给定的字符串中字符出现的频率建立相应哈夫曼树,构造哈夫曼编码表,在此基础上可以对待压缩文件进行压缩(即编码),同时可以对压缩后的二进制编码文件进行解压(即译码)。 输入 多组数据,每...
  • 1.哈夫曼树 哈夫曼树又称最优树(二叉树),是一类带权路径最短的树。构造这种树的算法最早是由哈夫曼(Huffman)1952年提出,这种树在信息检索中很有用。 结点之间的路径长度:从一个结点到另一个结点之间的分支...
  • 输入一串字符串,根据给定的字符串中字符出现的频率建立相应哈夫曼树,构造哈夫曼编码表,在此基础上可以对待压缩文件进行压缩(即编码),同时可以对压缩后的二进制编码文件进行解压(即译码)。 输入 多组数据,每...
  • 问题描述:输入一串字符串,根据给定的字符串中字符出现的频率建立相应的哈夫曼树,构造哈夫曼树编码表,在此基础上可以对压缩文件进行压缩(即编码),同时可以对压缩后的二进制编码文件进行解码(即译码)。...
  • 输入一串字符串,根据给定的字符串中字符出现的频率建立相应哈夫曼树,构造哈夫曼编码表,在此基础上可以对待压缩文件进行压缩(即编码),同时可以对压缩后的二进制编码文件进行解压(即译码)。 输入 多组数据,...
  • 问题描述:输入一串字符串,根据给定的字符串中字符出现的频率建立相应的哈夫曼树,构造哈夫曼树编码表,在此基础上可以对压缩文件进行压缩(即编码),同时可以对压缩后的二进制编码文件进行解码(即译码)。...
  • 应用场景文件压缩,又叫压缩算法 现在有3课二叉树,都有四个节点,分别带权13,7,8,3 一段字符串中计算每一个字符重复的次数 let a = 'ab cbdal abc' console.log(a.split('').reduce((acc, val) => ...
  • 1.哈夫曼树哈夫曼树又称最优树(二叉树),是一类带权路径最短的树。构造这种树的算法最早是由哈夫曼(Huffman)1952年提出,这种树在信息检索中很有用。结点之间的路径长度:从一个结点到另一个结点之间的分支数目。...
  • 哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法,该...算法:1、给定一个具有n个权值{ w1,w2,………wn }的结点的集合 F = { T
  • 给定N个权值作为N个叶子节点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。 在计算机...
  • 最终结果哈夫曼树,如图所示:直接上代码:public class HuffmanCode {public static void main(String[] args) {//获取哈夫曼树并显示Hnode root = createHuffmanTree(createNodes());root.beforePrint();System.out....
  • 设计并实现一个使用哈夫曼算法文件进行压缩的工具软件。 通过命令行参数指定操作模式(压缩/解压)、源文件名、目标文件名。 压缩操作将源文件按字节读入并统计字节频率,生成字节的哈夫曼编码,将编码和用...
  • 输入一串字符串,根据给定的字符串中字符出现的频率建立相应的哈夫曼树,构造哈夫曼编码表,在此基础上可以对压缩文件进行压缩(即编码),同时可以对压缩后的二进制编码文件进行解压(即译码)。 输入要求 多组数据,每...
  • 最终结果哈夫曼树,如图所示:直接上代码:public class HuffmanCode {public static void main(String[] args) {//获取哈夫曼树并显示Hnode root = createHuffmanTree(createNodes());root.beforePrint();System.out....
  • 哈夫曼树的树使用贪心算法。 每次选择该集合中权值最小的两个作为叶子结点,父亲节点的权值为叶子节点权值之和。然后又将其父亲重新放进此集合里。重复前面的做法,直到完成哈夫曼树的建立。 每次都要在集合中找...
  • 1、根据给定的一个文本文件,读出其内容,统计各个字符出现的频度,建立哈夫曼树,求出各个字符的哈夫曼码;打印哈夫曼树形结构,然后对文件进行编码;最后,对编码后的文件在解码,对哈夫曼算法进行验证。 扩展功能...
  • 哈夫曼压缩算法与解压

    千次阅读 2018-06-13 21:28:49
    算法思路如下:压缩:这个实验一开始将文件中的字符串读取到一个vector中,然后通过处理vector中的字符,建立了n个节点,每个节点包括每个字符和出现的频率,然后建立2*n个哈夫曼节点,前n个哈夫曼节点和节点的内容...
  • 算法】java实现用哈夫曼编码对文件进行压缩和解压1、什么是哈夫曼编码?2、哈夫曼编码如何对信息进行压缩?3、哈夫曼编码如何生成4、java实现用哈夫曼编码对文件进行压缩和解压 聊哈夫曼编码前建议先了解一下 ...

空空如也

空空如也

1 2 3 4 5 ... 10
收藏数 190
精华内容 76
关键字:

哈夫曼树压缩文件算法