精华内容
下载资源
问答
  • 哈夫曼树的创建,哈夫曼编码哈夫曼译码C语言实现代码 哈夫曼树的创建哈夫曼编码哈夫曼译码C语言实现代码markdown书写的html格式 如果需要将文件编码或译码,则应该加入文件操作,将文件的字符读入。其权重应该为...

    哈夫曼树的创建,对文件进行哈夫曼编码哈夫曼译码C语言实现代码下载(代码详细注释,便于理解):

    对文件进行哈夫曼编码哈夫曼译码C语言实现代码下载

    (课设题目)输入节点信息与权重,创建哈夫曼树,将编码信息存储至文件中,译码时从文件中再读取编码信息,对输入的二进制码串进行译码,C语言代码实现下载:

    创建哈夫曼树进行编码到文件并从文件读编码进行译码下载

    (课设题目)输入字符串从而计算字符串中每个字符出现的次数作为权重,依据节点信息和权重创建哈弗曼树,进行哈夫曼编码,再对二进制码串进行译码下载:

    输入字符串从而计算字符串中每个字符出现的次数_并创建哈弗曼树_并进行哈夫曼编码及译码代码下载devc++编译器版本

    输入字符串从而计算字符串中每个字符出现的次数_并创建哈弗曼树_并进行哈夫曼编码及译码代码下载vs编译器版本

    (课设题目)输入字符集及其权重生成哈弗曼树_并将树保存至文件_从文件读取哈弗曼树进行编码与译码C语言实现下载:

    输入字符集及其权重生成哈弗曼树_并将树保存至文件_从文件读取哈弗曼树进行编码与译码

    • 图例
      1.手动输入节点信息以及节点所对应的权值,创建哈弗曼树进行编码与译码
      在这里插入图片描述在这里插入图片描述
      在这里插入图片描述在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      2.输入一个字符串,计算字符串中每种字符出现的次数作为权重,创建哈弗曼树,并哈弗曼编码,再对二进制码串进行译码。
      在这里插入图片描述
      以上图例解释:
      这里写图片描述
    • 如果需要将文件编码或译码,则应该加入文件操作,将文件的字符读入。其权重应该为在整个文件中该字符所出现的次数。
    展开全文
  • 哈夫曼树的编码及译码(含代码

    千次阅读 2019-07-23 10:39:10
    此程序是利用哈夫曼树实现对文本文件的加密与解密,程序所能达到的内容:使用从文件中读取显示原文本文件、使用哈夫曼树编码对文本文件进行加密、使用哈夫曼表显示字符编码、显示加密文件、使用哈夫曼树译码文本文件...

    **

    哈夫曼树(编码及译码)

    **
    初学数据结构哈夫曼树(小菜鸟),借用了一些经典教材案例,编译软件为vs2013,有问题能指点,当然不喜勿喷哦,谢谢大家。
    此程序是利用哈夫曼树实现对文本文件的加密与解密,程序所能达到的内容:使用从文件中读取显示原文本文件、使用哈夫曼树编码对文本文件进行加密、使用哈夫曼表显示字符编码、显示加密文件、使用哈夫曼树译码文本文件解密、显示解密文件、这些程序执行完以后,退出系统。主要包含以下内容:
    1.输入文件所存在的位置;
    2.进入主菜单界面,显示所有可操作的选项;
    3.显示jiemi.txt文件的内容;
    4.对文件进行加密,将其与字符转换为二进制编码;
    5.对文件进行解密,将二进制编码写入;
    6.从文件中读取二进制编码转换为字符,再写入文件;
    7.退出系统。
    原文件内容:

    构建哈夫曼树

    从文件中读入字符个数,判定权值最大值,因为了方便给构建哈夫曼树,每个节点的权值相差为1,也就是{1 2 3 4 5 ……n}第一步先取两个最小权值作为左右子树构造一个新树,取1,2构成新树,其结点为1+2=3 虚线为新生成的结点,第二步再把新生成的权值为3的结点放到剩下的集合中,再根据第二步,取最小的两个权值构成新树,再不断重复步骤建立哈夫曼树。

    void Great(hufmantree &ht, int n)//n为从文件中读入字符的个数
    {
    	int m, S1, i, S2;
    	m = 2 * n - 1;
    	for (i = n + 1; i <= m; ++i)
    	{
    
    		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;
    }
    

    实现哈夫曼编码

    void HuffmanCode(hufmantree ht, int n, huffmancode &hc)
    {
    	char *cd;
    	int strat;
    	hc = new char*[n + 1];
    	cd = new char[n];
    	cd[n - 1] = '\0';//最后一个给‘\0’
    	int c, i, f;
    	for (i = 1; i <= n; ++i)
    	{
    		strat = n - 1;//确定最后一个
    		c = i;
    		f = ht[i].parent;//f—>第i个的节点的双亲
    		while (f != 0)
    		{
    			--strat;//cd倒数第二个空
    			if (ht[f].lchild == c)//看看左边有没有孩子
    				cd[strat] = '0';
    			else cd[strat] = '1';//右边有没有孩子
    			c = f; f = ht[f].parent;//回到双亲,f->i的双亲
    
    
    		}
    		hc[i] = new char[n - strat];
    		strcpy_s(hc[i], strlen(cd) + 1, &cd[strat]);
    	}
    
    //	delete cd;
    }
    

    实现哈夫曼译码

    void HuffmanCoding(hufmantree ht, int n, huffmancode hc, char b[100])
    {
    	cout << endl;
    	int d, i = 1, j;
    	char *cd;
    	d = n * 2 - 1;
    	cd = new char[n];
    	char c;
    	for (i = 1; i <= n; i++)
    	{
    		strcpy_s(cd, strlen(hc[i]) + 1, hc[i]);//从hc里把编码调过来
    	for (j = 0; j <strlen(cd); j++)
    		{
    			c = cd[j];
    			if (c == '0')
    			{
    				d = ht[d].lchild;/如果是0往走孩子走
    
    			}
    			if (c == '1')
    			{
    
    				d = ht[d].rchild;//如果是1往右孩子走
    			}
    		}
    	cout << ht[d].weight << "   " << ht[d].zifu<<endl;
    		d = n * 2 - 1;
    	}
    	delete cd;
    	//往文件里写入编译好的字符
    	char bf[100];
    for (i = 0; i < n;i++)
    	bf[i] = '\0';
    	FILE *fp = fopen(b, "w+");
    	for (i = 1; i <= n; i++)
    	if (ht[i].zifu != '\0')
    	{
    		bf[i - 1] = ht[i].zifu;
    		fprintf_s(fp,"%c", bf[i-1]);
    		}
    	
    	fclose(fp);
    }
    

    **

    完整代码

    **

    #include <iostream>
    #include <string>
    using namespace std;
    typedef char elemtype;
    typedef int status;
    typedef char **huffmancode;
    typedef struct
    {
    	char zifu;
    	status weight;
    	status parent, lchild, rchild;
    }hufman, *hufmantree;
    void Great(hufmantree &ht, int n);
    status  chushihua(hufmantree &ht, char a[100],int n);
    status select(hufmantree ht, int m, int &S1, int &S2);
    void HuffmanCode(hufmantree ht, int n, huffmancode &hc);
    void HuffmanCoding(hufmantree ht, int n, huffmancode hc, char b[100]);
    
    void Zifubianma(huffmancode hc, int n, char a[]);
    status wenben(char a[]);
    void jiemi(hufmantree ht,  int n);
    void Menu();
    status duxu(char a[],char b[100]);
    void xianshi(huffmancode hc, int n, char b[100]);
    	int main()
    {
    		hufmantree ht;
    		huffmancode hc;
    		char a[100];
    		char b[100];
    		int  n;
    	    n=duxu(a,b);
    	    chushihua(ht, a,n);
    		Great(ht, n);
    		while (1)
    		{
    			Menu();
    			printf("输入要做的操作:(1-7):  \n");
    			int x;
    			cin >> x;
    			switch (x)
    			{
    			case 1:wenben(a); break;
    			case 2: HuffmanCode(ht, n, hc); system("pause"); break;
    			case 3:Zifubianma(hc, n,a); system("pause"); break;
    			case 4:xianshi(hc,n,b);system("pause");break; 
    			case 5: jiemi(ht,  n); system("pause"); break;
    			case 6:HuffmanCoding(ht, n, hc,b); system("pause"); break;
    			case 7:
    			case 0:exit(0);
    
    			}
    			system("cls");
    		}
    
    		return 0;
    	}
    	
    
    void Menu()
    {
    	printf_s("\n\t\t         ---------------------超级文件加密系统-------------------\n");
    	printf_s("\n\t\t\t ψ卍ψ                   0.退出                    ψ卍ψ\n");
    	printf_s("\n\t\t\t ψ卍ψ                   1.显示原文本文件          ψ卍ψ\n");
    	printf_s(" \n\t\t\t ψ卍ψ                   2.文本文件加密            ψ卍ψ    \n");
    	printf_s(" \n\t\t\t ψ卍ψ                   3.显示字符编码            ψ卍ψ\n");
    	printf_s(" \n\t\t\t ψ卍ψ                   4.显示加密文件            ψ卍ψ \n");
    	printf_s("\n\t\t\t ψ卍ψ                   5.文本文件解密            ψ卍ψ \n ");
    	printf_s(" \n\t\t\t ψ卍ψ                   6.显示解密文件            ψ卍ψ \n");
    	printf_s(" \n\t\t\t ψ卍ψ                   7.退出系统                ψ卍ψ \n");
    	printf_s("\n\t\t         --------------------------------------------------------\n");
    }
    status wenben(char a[])
    {
    	int i;
    	for (i = 0; i <= strlen(a) - 1; i++)
    cout << a[i];
    	system("pause");
    	return 0;
    
    }
    status duxu(char a[],char b[100])
    {
    	
    	cout << "输入文件所在位置"<<endl;
    	gets(b);
    	FILE *fp = fopen(b, "r");
    	int i=100;
    fgets(a,i, fp);
    
    	fclose(fp);
    	i = 0; 
    	while (a[i] !='\0')
    	{
    		i++;
    	}
    	
    	return i;
    }
    status  chushihua(hufmantree &ht,char a[100],int n)
    {
    	int  i, m;
    	//cin >> n;/*输入结点1--n之间的节点*/
    	m = 2 * n - 1;/*m用于开辟两倍的ht的空间*/
    	ht = new hufman[m + 1];/*同上*/
    	for (i = 1; i <= m; i++)
    	{
    		ht[i].parent = 0; ht[i].lchild = 0; ht[i].rchild = 0;
    		ht[i].zifu = '0';
    	}
    
    	for (i = 1; i <= n; i++)
    	{
    			
    		 ht[i].weight=i;/*输入前几个节点的权值课本p138*/	
    		ht[i].zifu = a[i-1];
    	}
    
    	return n;
    }
    void Great(hufmantree &ht, int n)
    {
    	int m, S1, i, S2;
    	m = 2 * n - 1;
    	for (i = n + 1; i <= m; ++i)
    	{
    		
    		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;
    
    	}
    	
    
    }status select(hufmantree ht, int m, int &S1, int &S2)
    {
    	int j;
    	for (j = 1; j <= m; j++)
    	{
    		if (ht[j].parent == 0)
    		{
    			S1 = j;
    			break;
    		}
    	}
    	for (j = 1; j <= m; j++)
    	{
    		if (ht[j].parent == 0 && j != S1)
    		{
    			S2 = j;
    			break;
    		}
    	}
    	for (j = 1; j <= m; j++)
    	{
    
    
    
    		if (ht[j].parent == 0 && ht[j].weight < ht[S1].weight)
    		{
    			S1 = j;
    	
    		}
    
    	}
    	for (j = 1; j <= m; j++)
    	{
    
    		if (ht[j].parent == 0 && j != S1&&ht[j].weight < ht[S2].weight)//双亲为0j不等于上
    		{
    			S2 = j;
    			}
    
    
    	}
    	return 0;
    }
    
    
    void HuffmanCode(hufmantree ht, int n, huffmancode &hc)
    {
    	char *cd;
    	int strat;
    	hc = new char*[n + 1];
    	cd = new char[n];
    	cd[n - 1] = '\0';//最后一个给o
    	int c, i, f;
    	for (i = 1; i <= n; ++i)
    	{
    		strat = n - 1;//确定最后一个
    		c = i;
    		f = ht[i].parent;//f—>第i个的节点的双亲
    		while (f != 0)
    		{
    			--strat;//cd倒数第二个空
    			if (ht[f].lchild == c)//看看左边有没有孩子
    				cd[strat] = '0';
    			else cd[strat] = '1';//右边有没有孩子
    			c = f; f = ht[f].parent;//回到双亲,f->i的双亲
    
    
    		}
    		hc[i] = new char[n - strat];
    		strcpy_s(hc[i], strlen(cd) + 1, &cd[strat]);
    	}
    	cout << "文本文件加密成功!";
    //	delete cd;
    }
    void jiemi(hufmantree ht ,int n){
    	printf_s("   显示字符编码(哈夫曼表)\n");cout << "位置 右子树 左子树 双亲 对应字符"<<endl;
    	int i; for (i = 1; i <= 2 * n - 1; i++)
    	{
    		
    		printf_s("%2d", i);
    		printf_s("%6d%6d%6d%6c\n", ht[i].rchild, ht[i].lchild, ht[i].parent, ht[i].zifu);
    	}
    	
    	cout << "解密成功!";
    }
    void HuffmanCoding(hufmantree ht, int n, huffmancode hc, char b[100])
    {
    	cout << endl;
    	int d, i = 1, j;
    	char *cd;
    	d = n * 2 - 1;
    	cd = new char[n];
    	char c;
    	for (i = 1; i <= n; i++)
    	{
    		strcpy_s(cd, strlen(hc[i]) + 1, hc[i]);
    
    	for (j = 0; j <strlen(cd); j++)
    		{
    			c = cd[j];
    			if (c == '0')
    			{
    				d = ht[d].lchild;
    
    			}
    			if (c == '1')
    			{
    
    				d = ht[d].rchild;
    			}
    		}
    	cout << ht[d].weight << "   " << ht[d].zifu<<endl;
    		d = n * 2 - 1;
    	}
    	delete cd;
    	char bf[100];
    
    	for (i = 0; i < n;i++)
    	bf[i] = '\0';
    	FILE *fp = fopen(b, "w+");
    	for (i = 1; i <= n; i++)
    	if (ht[i].zifu != '\0')
    	{
    		bf[i - 1] = ht[i].zifu;
    		fprintf_s(fp,"%c", bf[i-1]);
    		}
    	
    	fclose(fp);
    }
    void Zifubianma(huffmancode hc, int n, char a[])
    {
    	printf_s("   显示字符编码\n");
    	int i; for (i = 1; i <= n; i++)
    	{
    		cout << a[i - 1] << "  " << hc[i] << endl;
    	}
    }
    void xianshi(huffmancode hc, int n,char b[100])
    {
    	int i;
    
    	printf_s("\n         4. 显示加密文件\n");
    FILE *fp = fopen(b, "w+");
    	for (i = 1; i <= n; i++)
    	{
    		cout <<hc[i];	fputs(hc[i], fp);	
    	}
    fclose(fp);
    }
    
    展开全文
  • 源于一次实验课,要求实现哈夫曼树、哈夫曼编码与译码;我就直接贴实验要求和代码实现了。 注:因为当时时间有限,故其实该代码还有优化空间,且输出文件是0/1字符串文本(UTF-8)并不是ASCII码编码文件,计算压缩率...

    源于一次实验课,要求实现哈夫曼树、哈夫曼编码与译码;我就直接贴实验要求和代码实现了。
    注:因为当时时间有限,故其实该代码还有优化空间,且输出文件是0/1字符串文本(UTF-8)并不是ASCII码编码文件,计算压缩率除以8即可。

    实验项目:哈夫曼编码与译码方法

    哈夫曼编码是一种以哈夫曼树(最优二叉树,带权路径长度最小的二叉
    树)为基础的基于统计学的变长编码方式。其基本思想是:将使用次数多的代
    码转换成长度较短的编码,而使用次数少的采用较长的编码,并且保持编码的
    唯一可解性。在计算机信息处理中,经常应用于数据压缩。是一种一致性编码
    法(又称"熵编码法"),用于数据的无损耗压缩。本实验要求利用贪心算法实
    现一个完整的哈夫曼编码与译码系统。

    实验内容和实验要求:

    1. 从文件中读入任意一篇英文文本文件,分别统计英文文本文件中各字符(包
      括标点符号和空格)的使用频率;
    2. 根据已统计的字符使用频率构造哈夫曼编码树,并给出每个字符的哈夫曼编
      码(字符集的哈夫曼编码表);
    3. 将文本文件利用哈夫曼树进行编码,存储成压缩文件(哈夫曼编码文件);
    4. 计算哈夫曼编码文件的压缩率;
    5. 将哈夫曼编码文件译码为文本文件,并与原文件进行比较。
      C代码:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define n 65
    
    //哈夫曼树节点存储结构
    typedef struct{
        char data;
        int weight;
        int lchild;
        int rchild;
        int parent;
    }Htnode;
    
    typedef Htnode HuffmanT[129];
    
    //哈夫曼编码表的存储结构
    typedef struct{
        char ch;        //储存被编码的字符
        char bits[n+1]; //字符编码位串
    }CodeNode;
    
    typedef CodeNode HuffmanCode[n];
    
    
    //0-9为数字;10-35为小写字母;36-61为大写字母;62-64为特殊字符
    void InitHT(HuffmanT T)   //初始化
    {
        char sz = '0';
        char xzm = 'a';
        char dzm = 'A';
        char kong = ' ';
        char dh = ',';
        char jh = '.';
    
        for(int i=0; i<n; i++)        
        {
            T[i].lchild = T[i].rchild = T[i].parent = -1;
            T[i].weight = 0;
            if(i>=0&&i<=9)
            {
                T[i].data = sz;
                sz++;
            }
            if(i>=10&&i<=35)
            {
                T[i].data = xzm;
                xzm++;
            }
            if(i>=36&&i<=61)
            {
                T[i].data = dzm;
                dzm++;
            }
            if(i>=62&&i<=64)
            {
                T[62].data = kong;
                T[63].data  = dh;
                T[64].data= jh;
            }
        }
    
        for(int j = n; j<2*n-1; j++)
        {
            T[j].weight = 0;
            T[j].lchild = T[j].rchild = T[j].parent = -1;
        }
    
        printf("initHT over\n");
    }
    
    void InputW(HuffmanT T)         //读入文件中字符并输入权值
    {
        FILE *fp;
        char ch;
        char Filename[20];
    
        printf ("input the filename:");
        scanf("%s",Filename);
       
        if((fp=fopen(Filename,"r"))==NULL)    printf("faild\n");
        ch = fgetc(fp);
    
        while(ch != EOF)
        {
            for(int i = 0; i<n; i++)
            {
                if(T[i].data == ch) T[i].weight++;
            }
            ch = fgetc(fp);
        }
    
        for(int i =0; i<n; i++)
        {
            printf("%c weight is:",T[i].data);
            printf("%d\n",T[i].weight);
            // printf("%d,%d,%d\n",T[i].parent,T[i].lchild,T[i].rchild);
        }
        
        fclose(fp);
       
        printf("inputW over\n");
    }
    
    void SelectMin(HuffmanT T, int length, int *p1, int *p2)    //选择权值最小的两个元素,返回下标
    {
        int min1,min2;              //min1标记最小,min2标记次小
        int i=0;
        int k,j=0;
        for(j; j<length; j++)
        {
            if(T[j].parent == -1)
            {
                min1=j;
                break;
            }
        }
    
        for(k=min1+1;k<length;k++)
        {
            if(T[k].parent == -1)
            {
                min2 = k;
                break;
            }
        }
        // for(i = 0;i<length;i++)
        while(i<length)
        {
            if(T[i].parent == -1)
            {
                
                if(T[i].weight<T[min1].weight)
                {
                    min2 = min1;
                    min1 = i;
                }
                else if((i!=min1)&&(T[i].weight<T[min2].weight))
                {
                    min2 = i;
                }
            }
    
            i++;
        }
    
        // printf("%d,%d:%d,%d ",min1,min2,T[min1].weight,T[min2].weight);
        *p1 = min1;
        *p2 = min2;
    
        // printf("selectmin\n");
    }
    
    void CreartHT(HuffmanT T)       //构造哈夫曼编码树
    {
        int i,p1,p2;
        int wei1,wei2;
        InitHT(T);      //初始化
        InputW(T);      //输入权值
        for(i=n; i<129; i++)
        {
            SelectMin(T,i,&p1,&p2);
            wei1 = T[p1].weight;
            wei2 = T[p2].weight;
            T[p1].parent = i;
            T[p2].parent = i;
            T[i].lchild = p1;
            T[i].rchild = p2;
            T[i].weight = wei1 + wei2;
        }
    
        printf("creatHT over\n");
    }
    
    void CharSetHuffmEncoding(HuffmanT T, HuffmanCode H)    //根据哈夫曼树求哈夫曼编码表H
    {
        int c,p,i;          //c和p分别指示T中孩子和双亲位置
        char cd[n+1];       //临时存放编码
        int start;          //指示编码在cd中的位置
        cd[n]='\0';         //编码结束符
        for(i=0; i<n; i++)
        {
            H[i].ch = T[i].data;
            start = n;
            c=i;
            while((p=T[c].parent)>=0)   //回溯到T[c]是树根位置
            {
                cd[--start] = (T[p].lchild==c) ? '0':'1';   //T[c]是T[p]的左孩子,生成代码0否则生成1
                c=p;
            }
            strcpy(H[i].bits,&cd[start]);
        }
        printf("creatHcode over\n");
    }
    
    void PHUM(char *file,char *s);
    
    char s[30000]={3};
    void PrintHUffmancode(HuffmanCode H)        //将文件中字符的哈夫曼编码打印出来并将其写入指定txt文件
    {
        
        FILE *fp;
        char ch;
        char Filename[80];
        char file[80];
    
        printf ("output the Huffmancode of which file:");
        scanf("%s",Filename);
        if((fp=fopen(Filename,"r"))==NULL)    printf("failda\n");
        ch = fgetc(fp);
        int L =0;
        printf("1");
        while(ch != EOF)
        {
    
            for(int i = 0; i<n; i++)
            {
                if(H[i].ch == ch) 
                {
                    printf("%s",H[i].bits);
                    sprintf(s+L,"%s",H[i].bits);
                    L=strlen(s);
                }
            }
    
            ch = fgetc(fp);
        }
        printf("\n");
    
        for(int k =0;k<n;k++)
        {
            printf("%c-%s\n",H[k].ch, H[k].bits);
        }
    
        // printf("3\n");
        fclose(fp);
        printf("stand by\n");
    
        PHUM(file,s);
        
    }
    
    void PHUM(char *file,char *s)
    {
        FILE *fp;
        int i=0;
        printf ("save your Huffmancode to the file:");
        scanf("%s",file);
        if((fp=fopen(file,"w"))==NULL)    printf("faild\n");
    
        while(s[i]!='\0')
        {
            // fwrite(s,1,strlen(s),fp);
            // fprintf(fp,'%c',s[i]);
            fprintf(fp,"%c",s[i]);
            i++;
        }
        
        fclose(fp);
        printf("write over\n");
    
        
    }
    
    void Printftxt(HuffmanT T,char a[])  //左0右1
    {
        int root,c;
        int i = 0;
        FILE *fp;
        char ch;
        char Filename[30];
    
        printf ("print words acroding to Huffmancode:");
        scanf("%s",Filename);
        if((fp=fopen(Filename,"r"))==NULL)    printf("faild\n");
    
        // printf("1\n");
        for(int j =0; j<129; j++)     //找到根节点
        {
            if(T[j].parent==-1)
            {
                root = j;
                break;
            }
        }
        
        ch=fgetc(fp);
        while(ch!=EOF)
        {
            c=root;
    
            while((T[c].lchild != -1) || (T[c].rchild != -1))
            {
                if(ch=='0')
                {
                    c=T[c].lchild;
                    ch = fgetc(fp);
                }
                else if(ch=='1')
                {
                    c=T[c].rchild;
                    ch = fgetc(fp);
                }
                // printf("2");
            }
    
            printf("%c",T[c].data);
           
            // ch = fgetc(fp);
    
        }
    
        fclose(fp);
    }
    
    int main()
    {
        HuffmanT T;
        HuffmanCode H;
    
        CreartHT(T);     //读入文件构造一个哈夫曼树初始化并输入权值 输出各字符权值
        CharSetHuffmEncoding(T,H);   //根据哈夫曼树构造哈夫曼表,并输出各字符的编码
        PrintHUffmancode(H);        //输出某个文件中文本的哈夫曼编码,并把它保存在指定文件中
        
        Printftxt(T,s);   //根据哈夫曼编码打印文本文件字符
    
    }
    
    展开全文
  • 哈夫曼树编码代码实现 #include<stdio.h> #include<iostream> #include<queue> #include<vector> #include<stack> using namespace std; struct TreeNode { int power; int ascii; ...

    哈夫曼树编码代码实现

    首先用的是优先队列和STL pair实现的树的构建

    对于结构体
    struct TreeNode {
    int power;
    int ascii;
    TreeNode* Left;
    TreeNode* Right;
    TreeNode* Parent;
    TreeNode() {
    Left = NULL;
    Right = NULL;
    Parent = NULL;
    power = -1;
    ascii = 0;
    }

    };
    建立parent指针指向父结点可以更方便的实现编码的回溯。
    1.pair中存储结点和ascii值,存在优先队列中,
    2.每次提出队列中power值最小的两个元素,将其与新建的Temp父结点构成一棵子树;父结点的power值等于两子树power之和;
    3.将构成的新的父结点重新放入优先队列,如此循环
    4.当优先队列中只剩下一个结点时,说明哈夫曼树已经构造完成

    (利用结构体cmp可以设置优先队列的优先级
    关键代码:return a.first->power > b.first->power; )
    (结点的第二个数值为ascii的原因是为了更好的将含有字符的结点用数组保存下来,新生成的结点second值都是-1,所以当second的值不为-1,
    可以有代码 HufmNodeAdress[que.top().second - 65] = TempNode;)

    编码:
    对于哈夫曼树的编码,由于之前建树时已经顺便将每个含字符的结点的位置存起来,可以从根结点向上回溯,我使用的方法是用栈;
    1.将追溯到根节点前的结点都用栈保存起来
    2.将栈的结点出栈,与当前栈顶元素进行进行比较
    若为左子树,输出 0,右子树为1
    由此可以得出所选字符的哈夫曼编码;
    译码:
    编码之后直接可以进行译码,0往左,1往右
    每完成一个字符的译码记得将指针指回头结点。

    ps:代码如下

    #include<stdio.h>
    #include<iostream>
    #include<queue>
    #include<vector>
    #include<stack>
    using namespace std;
    struct TreeNode {
    	int power;
    	int ascii;
    	TreeNode* Left;
    	TreeNode* Right;
    	TreeNode* Parent;
    	TreeNode() {
    		Left = NULL;
    		Right = NULL;
    		Parent = NULL;
    		power = -1;
    		ascii = 0;
    	}
    	
    };
    typedef pair<TreeNode*, int> P;   //<节点,ascii>
    
    struct cmp {
    	bool operator()(const P a, const P b)
    	{
    		return a.first->power > b.first->power;       //频率小的优先 
    	}
    };
    priority_queue<P, vector<P>, cmp> que;    //优先队列
    TreeNode* HufmNodeAdress[26] = {0};
    void MakeHufmTree(TreeNode* Node) {
    	if (que.size() <= 1)
    		return;
    	while (que.size()!=1)
    	{
    		TreeNode* TempLeft = new TreeNode;
    		TreeNode* TempRight = new TreeNode;
    		TreeNode* TempParent = new TreeNode;
    		//TempLeft->power = que.top().first->power;
    		//TempLeft->Left = que.top().first->Left;
    		//TempLeft->Right = que.top().first->Right;
    		TempLeft = que.top().first;
    		if (que.top().second != -1)
    			HufmNodeAdress[que.top().second - 65] = TempLeft;
    		que.pop();
    		//TempRight->Left = que.top().first->Left;
    		//TempRight->Right = que.top().first->Right;
    		//TempRight->power = que.top().first->power;
    		TempRight = que.top().first;
    		if (que.top().second != -1)
    			HufmNodeAdress[que.top().second - 65] = TempRight;
    		que.pop();
    		TempParent->Left = TempLeft;
    		TempParent->Right = TempRight;
    		TempParent->power = TempLeft->power + TempRight->power;
    		TempLeft->Parent = TempParent;
    		TempRight->Parent = TempParent;
    		P temp(TempParent, -1);
    		que.push(temp);
    	}
    	Node->Left = que.top().first->Left;
    	Node->Right = que.top().first->Right;
    	Node->power = que.top().first->power;
    	
    }
    void GetCode(TreeNode* pos)
    {
    	stack<TreeNode*> stk;
    	TreeNode* p;
    	while (pos->Parent)
    	{
    		stk.push(pos);
    		pos = pos->Parent;
    	}
    	stk.push(pos);
    	while (stk.size()!=1)
    	{
    		p = stk.top();
    		stk.pop();
    		if (p->Left == stk.top())
    			cout << 0;
    		else if (p->Right == stk.top())
    			cout << 1;
    	}
    	
    	
    }
    void ShowCode()
    {
    	for (int i = 0;i < 26;i++)
    	{
    		if (NULL != HufmNodeAdress[i]) {
    			printf("%c的编码为:", i + 65);
    			GetCode(HufmNodeAdress[i]);
    			cout << endl;
    		}
    			
    	}
    }
    void Decoding(char ch[])
    {
    	int cnt = 0;
    	while (1)
    	{
    		if (ch[cnt] == '\0')
    			break;
    		GetCode(HufmNodeAdress[ch[cnt++] - 65]);
    
    	}
    	cout << endl;
    }
    void check(TreeNode* Node)
    {
    	if (Node->Parent)
    		cout << Node->power << "has the parent" << Node->Parent->power<<endl;
    	cout << Node->power << " ";
    	if (Node->Left)
    		check(Node->Left);
    	if (Node->Right)
    		check(Node->Right);
    }
    void Coding(TreeNode* pos,char ch[])
    {
    	int i = 0;
    	TreeNode* p = new TreeNode;
    	p = pos;
    	while (ch[i] != 0)
    	{
    		if (ch[i] == '0')
    			p = p->Left;
    		else if (ch[i] == '1')
    			p = p->Right;
    		if (p->ascii != 0)
    		{
    			printf("%c", p->ascii);
    			p = pos;
    		}
    		i++;
    	}
    }
    int main()
    {
    	char Ch[1000];
    	cin >> Ch;
    	int Fre[26] = { 0 };
    	for (int i = 0;;i++)
    	{
    		if (Ch[i] == '\0')
    			break;
    		Fre[Ch[i] - 65]++;
    	}
    	for (int i = 0;i < 26;i++)
    	{
    		if (Fre[i] != 0)
    		{
    			TreeNode* NewNode = new TreeNode;
    			NewNode->power = Fre[i];
    			NewNode->ascii = i + 65;
    			P temp(NewNode, i + 65);//结点,ascii
    			que.push(temp);
    		}
    	}
    	TreeNode* Node = new TreeNode;
    	MakeHufmTree(Node);
    	ShowCode();
    	Decoding(Ch);
    	//check(Node);
    	char num[1000];
    	cin >> num;
    	Coding(Node, num);
    	return 0;
    
    }
    
    
    
    展开全文
  • 哈夫曼编码译码

    2015-12-03 20:59:05
    (3)D:译码:利用已建好的哈夫曼树将文件CODEFILE中的代码进行译码,结果存入文件TEXTFILE中。 (4)P:印代码文件:将文件CODEFILE显示在显示器上,每行50的代码。同时将此字符形式的编码文件写入文件CODEPRIN中...
  • 哈夫曼编码译码系统

    2021-01-15 08:04:05
    文章目录实验目的实验设备与环境实验过程及结果分析1. 构造哈夫曼树2. SelectSmall函数3. 哈夫曼编码4. 哈夫曼译码5. 实验结果实验代码main.cppHuffman.h 实验目的 完成Huffman Tree 编码、译码系统的设计 自行设计...
  • 哈夫曼树代码整合

    2018-12-29 22:51:29
    给定权值,哈弗曼编码、译码 题目描述 假设某通信报文的字符集由A,B,C,D,E,F这6个字符组成,它们在报文中出现的频度(频度均为整数值)。 (1)构造一棵哈弗曼,依次给出各字符编码结果。 (2)给字符串进行编码。 ...
  • 利用已建好的哈夫曼树将文件codefile中的代码进行译码,结果存入文件textfile中。 (4)用下表给出的字符集和频度的实际统计数据建立哈夫曼树,并实现以下报文的编码和译码:“THIS PROGRAM IS MY FAVORITE”。
  • 开发环境:VC++ 6.0 (1) I:初始化(Initialization)。 (2) E:编码(Encoding)。 (3) D:译码(Decoding)。 (4) P:打印代码文件...(5)T:打印哈夫曼树(HuffmanTreePrint)。 (6)Q:退出程序(Quit)。
  • 哈夫曼树编码与译码(完整C/C++实现代码)

    万次阅读 多人点赞 2019-07-02 22:51:06
    哈夫曼编码的设计与应用 问题需求分析 用哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来...
  • 输入的一串电文字符实现哈夫曼编码,再对哈夫曼编码生成的 代码串进行译码,输出电文字符串。即以字符串字母出现次数为权值,生成哈夫曼树。 #include<stdio.h> #include<string.h> #include<stdlib....
  • 具体包括哈夫曼树的建立、哈夫曼编码的生成和编码文件的译码。 假设举如下例子 存储结构: 模型: 哈夫曼树节点类: package keshe; public class HuffNode { Character ch;//字符 int val;//判断值,往左走即...
  • 1、创建哈夫曼树 2、编码函数 3、译码函数 编写代码时为了方便,在这里混用了c++的输入输出流。主体用c语言实现。 下面是代码部分: 1、头文件,以及储存结构: #include<stdio.h> #include<iostream> ...
  • 求一段可以将我写的哈夫曼树打印出来的代码,谢谢!!我正在写一个huffman的编码和译码的程序可是不会写打印的,请大家帮忙
  • 2.建立哈夫曼树 3.建立密码本并对文件编码 4.选择需要进行解码的文件并解码 5.按位压缩方式对文件进行压缩 6.解压压缩文件为编码文件 一共三个类,Huffman类也是程序的入口 下面的代码中注释将对代码有详细的讲解 ...
  • 代码是使用vc++6.0完成的,不同编译器一些内部判断机制可能存在差异,导致代码不能进行正常运行 本代码直接复制下来,肯定会存在问题,原因在于文件是如何操作的,如果你一点基础都没有的话,不建议您看这篇博客...
  • 大二根据小甲鱼的数据结构写的代码
  • 问题描述和求解方法:首先根据给定的n个字符的权值构造哈夫曼树。通过遍历此二叉树完成各字符的哈夫曼编码,另输入一组‘0’、‘1’代码构成的报文将其翻译成对应的字符信息。
  • 利用已建好的哈夫曼树将文件CodeFile中的代码进行译码,结果存入文件TextFile中。 (4)P:印代码文件(Print)。将文件CodeFile以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码写入文件CodePrint中...
  • 利用已建好的哈夫曼树将文件CodeFile中的代码进行译码,结果存入文件TextFile中。 (4)P:印代码文件(Print)。将文件CodeFile以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码写入文件CodePrint中...
  • 1.建立哈夫曼树 以数组的形式建立哈夫曼树类似于一下形式 每次找出两个最小的权,将其和放在数组weight位置第一个权为空的位置,将两个最小权的下标放入该点的lchild,rchild中,将两个最小权的parent改为该点,第...
  • 数据结构中哈夫曼树水题代码

    千次阅读 2016-04-27 15:32:45
    构造哈夫曼树时,权值小的放左子树,权值大的放右子树,编码时右子树编码为1,左子树编码为0.   输入: 输入表示字符集大小为n(n  输入串长小于或等于100的目标报文。 输出: 经过编码后的二进制码...
  • 哈夫曼编码可以有效的压缩数据,通常可以节省20~90%的空间,具体压缩率依赖于数据的特性。我们将待压缩数据看作字符序列,根据每个字符出现的频率(也可以是字符对应的权重),通过哈夫曼贪心算法构造出字符的最优二...
  • 电文的编码和译码哈夫曼树的应用)

    千次阅读 多人点赞 2016-12-30 16:33:50
    一、 实验环境 学宝虚拟机,VC6.0二、 实验目的 从键盘接收一串电文字符,输出对应的哈夫曼编码,同时能翻译哈夫曼编码生成的...3.定义二叉树的静态链表结构,并利用这种结构存储哈夫曼树,利用哈夫曼树解决编...

空空如也

空空如也

1 2 3 4 5 6
收藏数 101
精华内容 40
关键字:

哈夫曼树译码代码