精华内容
下载资源
问答
  • 哈夫曼树编码译码
    2021-12-13 17:31:01

    设计任务 


    1、文本文件的编码解码(文本文件压缩为01编码,解码01编码为文本文件)
    有一篇英文文章存储在一个文本文件中,现在要以报文形式将文章发送。编写程序,设计Haffman编码将文章转换为01编码。报文接收端要将01编码转换为英文文章,编写程序将Haffman编码报文译码。

    基本要求:
    (1)读英文文章“Text.txt”,统计每个字符在文章中出现的频率;将结果打印到文件“Freq.txt”
    (2)构建Haffman树,求出每个字符的Haffman编码;将结果打印到文件“HaffCode.txt”
    (3)将英文文章“Text.txt”转换为01字符串,将结果打印到文件“EngtoCode.txt” 
    (4)读文件“EngtoCode.txt”,将01字符串转换成英文文章。(译码)  

    数据描述  

    定义一个哈夫曼树结构体

    typedef struct{

            int weight,flag;

            int parent,Lchild,Rchild;

    }HTNode,*HuffmanTree;

    定义一个结构体来存储文本的每个字符和出现的次数

    typedef struct{

            char c;

            int n=1;

    }character;

    算法思想 

    1. 先读取Text.txt文本统计每个字母出现的次数存储到character结构体中;
    2. 将每个字符出现次数当做HTNode.weight;
    3. 建立哈夫曼树;
    4. 从根出发向左为0向右为1直到左右孩子都为0,此时该结点的字符01编码即可得出
    5. 读取文件,将字符代替成哈夫曼编码;
    6. 读取解码文件从根出发,每次读取一个字符,当读取字符为0到左孩子当字符为1到右孩子直到左右孩子都为0,读取字符。

    源码 

    #include<bits/stdc++.h>
    using namespace std;
    
    #define MAX 999999
    
    typedef struct{
    	char c;
    	int n=1;
    }character;
    
    typedef struct{
    	int weight,flag;
    	int parent,Lchild,Rchild;
    }HTNode,*HuffmanTree;
    
    typedef char ** HuffmanCode; 
    HuffmanCode HC;
    character z[128];
    
    int ReadFile(){
    	FILE *p=fopen("Text.txt","r");
    	FILE *pf=fopen("Freq.txt","w+");
    	if((p=fopen("Text.txt","r"))==NULL){
    		cout<<"ERROR";
    		exit(0);
    	}
    	int i=1;
    	char ch='1';
    	while(ch!=EOF){
    		int page=0;
    		ch=fgetc(p);
    		for(int j=1;j<=i;j++){
    			if(ch==z[j].c){
    				z[j].n++;
    				page=1;
    				break;
    			}
    		}
    		if(page==0){
    			z[i].c=ch;
    			i++;
    		}
    	}
    	for(int k=1;k<i-1;k++){
    		cout<<z[k].c<<":"<<z[k].n<<endl;
    		fputs("字符",pf);
    		fputc(z[k].c,pf);
    		fputs("的频率:",pf);
    		fprintf(pf,"%d",z[k].n);
    		fputc('\n',pf);
    	}
    	fclose(p);
    	fclose(pf);
    	return i-2;
    }
    
    void InitHuffmanTree(HuffmanTree &HT, int n)
    {
    	if(n>1){
    		int i;
    		HT=(HTNode *)malloc(2*n*sizeof(HTNode));
    		for(i=1;i<2*n;i++){
    			HT[i].parent = 0;
    			HT[i].Lchild = 0;
    			HT[i].Rchild = 0;
    			HT[i].weight =MAX;
    			HT[i].flag = 0;
    		}
    		for(i=1;i<=n;i++)
    			HT[i].weight=z[i].n;
    	}
    }
    
    int Select(HuffmanTree &HT, int n){
    	int i,temp,min;
    	for(i=1;i<=n;i++){
    		if(HT[i].flag==0){
    			temp=HT[i].weight;
    			min=i;
    			break;
    		}
    	}
    	while(i<=n){
    		if(!HT[i].flag&&temp>HT[i].weight){
    			temp=HT[i].weight;
    			min=i;
    		}
    		i++;
    	}
    	HT[min].flag=1;
    	return min;
    }
    
    
    void DispHuffmanTree(HuffmanTree HT, int n)
    {
    	printf("\n结点i\tweight\tparent\tLchild\tRchild\n");
    	for(int i=1;i<2*n;i++)
    	{
    		printf("%d\t",i);
    		if(HT[i].weight==MAX)
    			printf("%c\t",'-');
    		else
    			printf("%d\t", HT[i].weight);
    		printf("%d\t%d\t%d\n", HT[i].parent, HT[i].Lchild, HT[i].Rchild);
    	}
    }
    
    void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n){
    	FILE *pc=fopen("HaffCode.txt","w+");
    	if(n<=1) return;
    	int m,c,f;
    	m=2*n-1;
    	HuffmanTree p;
    	int i,s1,s2;
    	for(p=HT,i=1;i<=n;++i,++p,++w) *p={*w,0,0,0};
    	*p++;
    	for(;i<=m;++i,++p) *p={0,0,0,0};
    	for(i=n+1;i<2*n;i++){
    		s1=Select(HT,i-1);
    		s2=Select(HT,i-1);
    		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=(HuffmanCode)malloc((n+1)*sizeof(char *));
    	char *cd=(char *)malloc(n*sizeof(char));
    	cd[n-1]='\0';
    	for(int i=1;i<=n;++i){
    		int 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);
    	for(int i=1;i<=n;i++){
    		fputs("权值为",pc);
    		fputc(z[i].c,pc);
    		fputs("的哈夫曼编码:",pc);
    		fputs(HC[i],pc);
    		fputc('\n',pc);
    	}
    }
    
    void HuffmanPutF(int n){
    	FILE *pu=fopen("EngtoCode.txt","w+");
    	FILE *p=fopen("Text.txt","r");
    	if((p=fopen("Text.txt","r"))==NULL){
    		cout<<"ERROR";
    		exit(0);
    	}
    	int i=1,x;
    	char ch='1';
    	while(ch!=EOF){
    		int page=0;
    		ch=fgetc(p);
    		for(int j=1;j<=n;j++){
    			if(ch==z[j].c){
    				x=j;
    				break;
    			}
    		}
    		if(ch!=EOF) fprintf(pu,"%s",HC[x]);
    	}
    	fclose(pu);
    	fclose(p);
    }
    
    void HuffmanEcoding(HuffmanTree &HT,int n){
    	FILE *pe=fopen("EngtoCode.txt","r");
    	int p=2*n-1;
    	char ch;
    	while((ch=fgetc(pe))!=EOF){
    		if(ch=='0') p=HT[p].Lchild;
    		else p=HT[p].Rchild;
    		if(HT[p].Lchild==0&&HT[p].Rchild==0){
    			cout<<z[p].c;
    			p=2*n-1;
    		}
    	}
    	fclose(pe);
    }
    
    int main(){
    	int n,w[128];
    	HuffmanTree HT;
    	n=ReadFile();
    	for(int i=1;i<=n;i++)
    		w[i]=z[i].n;
    	InitHuffmanTree(HT,n);
    //	DispHuffmanTree(HT,n);
    	HuffmanCoding(HT,HC,w,n);
    	HuffmanPutF(n);
    //	DispHuffmanTree(HT,n);
    	HuffmanEcoding(HT,n);
    	return 0;
    }

    测试  

    The discovery of the Omicron version of the coronavirus is demonstrating the risks linked to world vaccine inequality.South African scientists informed the World Health Organization (WHO) last week about the new Omicron version, or variant.The WHO has declared Omicron a "very high" risk worldwide because it contains some "concerning" mutations. A mutation is a change in the genetic material of a virus. Early evidence suggests the new variant may spread more easily than other coronavirus versions.Many countries have closed their borders in an attempt to block new infections of the variant. The United States, Brazil, Britain and the European Union have placed travel restrictions on eight African nations where the variant was first identified.

    更多相关内容
  • 2.根据创建好的哈夫曼树创建一张哈夫曼编码表 3.输入一串哈夫曼序列,输出原始字符 三.设计思想: 1.首先要构造一棵哈夫曼树哈夫曼树的结点结构包括权值,双亲,左右孩子;假如由n个字符来构造一棵哈夫曼树,则...
  • 使用文件的技术对输入的数据进行哈夫曼编码,并能产生相应的编码表和译码
  • 2. 编码:利用建好的哈夫曼树,对从文件ToBeTran中读入的正文进行编码,然后将结果存入文件CodeFile中。 3. 译码:利用建好的哈夫曼,从CodeFile中读取编码数据并进行译码,结果存入文件TextFile中。 4. 在终端上以...


    一、问题描述

    1. 初始化:从配置文件Conf中读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树。
    2. 编码:利用建好的哈夫曼树,对从文件ToBeTran中读入的正文进行编码,然后将结果存入文件CodeFile中。
    3. 译码:利用建好的哈夫曼,从CodeFile中读取编码数据并进行译码,结果存入文件TextFile中。
    4. 在终端上以直观的方式显示构造出来的哈夫曼树。 【测试数据】 基于下表给出字符集及频度,实现以下报文的编码和译码:THIS PROGRAM IS MY FAVORITE”。

    二、代码实现

    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    //输入字符频度的最大字符数
    #define MaxSize 51
    //待编码语句的最大长度 
    #define MaxWordSize 201
    
    typedef struct{
    	unsigned int weight;
    	unsigned int lchild, rchild, parent;
    }Hnode, *Htree;
    
    void Create_Htree(Htree &HT, int &n, char ch[]);
    void Encode_Htree(Htree HT, char** &HC, int n, char ch[]);
    int Decode(char** HC, Htree HT, char ch[], int n);
    int get_conf(char ch[], int frequency[]);
    void Display_Htree(Htree HT, int end);
    void find_min_node(Htree HT,int &min1,int &min2,int end);
    void Encode(char** HC, char ch[], int n);
    
    int main()
    {
        int operate_num, n;
        Htree HT;
        char ch[MaxSize];
        char **HC;
        int flag = 0;
        printf("[1]创建哈夫曼树 [2]编码 [3]译码\n[4]显示哈夫曼树 [0]退出\n请输入操作:");
        scanf("%d", &operate_num);
        while(operate_num)
        {
            if(operate_num == 1)
            {
            	Create_Htree(HT, n, ch);
            	Encode_Htree(HT, HC, n, ch);
            	flag = 1;
    		}
            else if(operate_num == 2)
            {
            	if(flag == 1)
            	{
            		//Encode_Htree(HT, HC, n, ch);
            		Encode(HC, ch, n);
            		flag = 1;
    			}
            	else
            		printf("请先建立哈夫曼树!\n");
    		}
            else if(operate_num == 3)
            {
            	int code_not_exist = 0;
            	if(flag == 1)
            	{
            		code_not_exist = Decode(HC, HT, ch, n);
            			if(code_not_exist)
            				printf("缺少待译码文件请先编码!\n");
    			}
            	else
            		printf("请先建立哈夫曼树!\n");
    		}
            else if(operate_num == 4)
            	if(flag == 1)
                	Display_Htree(HT, 2 * n - 1);
                else
                	printf("请先建立哈夫曼树!\n");
            else if(operate_num == 0)
            	break;
            
            else
            	printf("输入有误请重新输入\n");
            printf("[1]创建哈夫曼树 [2]编码 [3]译码\n[4]显示哈夫曼树 [0]退出\n请输入操作:");
        	scanf("%d", &operate_num);
        }
        printf("已退出"); 
    
    	system("pause");
        return 0;
    }
    
    //创建哈夫曼树 
    void Create_Htree(Htree &HT, int &n, char ch[])
    {
    	int frequency[MaxSize];
    	int m;
    	//读入字符权重的个数
    	n = get_conf(ch, frequency);
    	if(!n)
    		return;
    	m = 2 * n - 1;
    	//第0个结点不存内容 
    	HT = (Htree)malloc((m + 1) * sizeof(Hnode));
    	Htree ptr;
    	ptr = HT;
    	int i;
    	//初始化n个叶子结点
    	for(i = 1; i <= n; i++)
    	{
    		(ptr + i)->weight = frequency[i - 1];
    		(ptr + i)->parent = 0;
    		(ptr + i)->lchild = 0;
    		(ptr + i)->rchild = 0;
    	}
    	//初始化除叶子结点外的结点
    	for(i = n + 1; i <= m; i++)
    	{
    		(ptr + i)->weight = 0;
    		(ptr + i)->parent = 0;
    		(ptr + i)->lchild = 0;
    		(ptr + i)->rchild = 0;
    	}
    	for(i = n + 1; i <= m; i++)
    	{
    		//找到最小的两个叶子结点,并且min1要小于min2 
    		int min1, min2;
    		find_min_node(HT, min1, min2, i - 1);
    		HT[i].weight = HT[min1].weight + HT[min2].weight;
    		HT[min1].parent = HT[min2].parent = i;
    		HT[i].lchild = min1;
    		HT[i].rchild = min2;
    	}
    	printf("哈夫曼树已经创建\n");
    }
    
    //从文件中读取字符频度 
    int get_conf(char ch[], int frequency[])
    {
    	FILE *fp = fopen("Conf.txt", "r");
    	int i;
    	fgets(ch, MaxSize, fp);
    	for(i = 0; fscanf(fp, "%d", &frequency[i]) != EOF; i++);
    
    	fclose(fp);
    	return i;
    }
    
    //创建哈夫曼编码表 
    void Encode_Htree(Htree HT, char** &HC, int n, char ch[])
    {
    	HC = (char**)malloc(n * sizeof(char*));
    	char *temp = (char*)malloc(n * sizeof(char));
    	temp[n - 1] = '\0';
    	int i, j, j_parent, start;
    	for(i = 1; i <= n; i++)
    	{
    		//从第一个结点开始向上求哈夫曼编码 
    		j = i;
    		j_parent = HT[j].parent;
    		//因为是从叶子结点向根节点,所以要倒序的存入权重 
    		start = n - 1;
    		while(j_parent)
    		{
    			if(j == HT[j_parent].lchild)
    			{
    				temp[--start] = '0';
    			}
    			else if(j == HT[j_parent].rchild)
    			{
    				temp[--start] = '1';
    			}
    			j = j_parent;
    			j_parent = HT[j].parent;
    		}
    		HC[i - 1] = (char*)malloc((n - start) * sizeof(char));
    		strcpy(HC[i - 1], &temp[start]);
    	}
    	
    	temp = NULL;
    	free(temp);
    }
    
    //对文本进行哈夫曼编码 
    void Encode(char** HC, char ch[], int n)
    {
    	FILE *fp1 = fopen("ToBeTran.txt", "r");
    	char word[MaxWordSize];
    	fgets(word, MaxWordSize, fp1);
    	fclose(fp1);
    	int length = strlen(word);
    	//给数组初始化初值,防止拼接的时候出现错误 
    	char encoder[MaxWordSize * 4] = {0};
    	int i;
    	for(i = 0; i <= length - 1; i++)
    	{
    		int j;
    		for(j = 0; j <= n - 1; j++)
    		{
    			if(word[i] == ch[j])
    				strcat(encoder, HC[j]);
    		}
    	}
    	
    	FILE *fp2 = fopen("CodeFile.txt", "w");
    	fputs(encoder, fp2);
    	fclose(fp2);
    	printf("编码为:%s\n", encoder);
    }
    
    //用哈夫曼树译码 
    int Decode(char** HC, Htree HT, char ch[], int n)
    {
    	FILE *fp1 = fopen("CodeFile.txt", "r");
    	if(!fp1)
    		return 1;
    	char code[MaxWordSize * 4] = {0};
    	fscanf(fp1, "%s", code);
    	int i, j = 2 * n - 1;
    	int k = 0;
    	int length = strlen(code);
    	char decoder[MaxWordSize] = {0};
    	for(i = 0; i <= length - 1; i++)
    	{
    		//从根结点开始向下,0则进左孩子,1则进右孩子
    		//一直到叶子结点输出 
    		if(code[i] == '0')
    			j = HT[j].lchild;
    		else if(code[i] == '1')
    			j = HT[j].rchild;
    		if(HT[j].lchild == 0 && HT[j].rchild == 0)
    		{
    			decoder[k] = ch[j - 1];
    			k++;
    			j = 2 * n - 1;
    		}
    	}
    	printf("译码为:%s\n", decoder);
    	FILE *fp2 = fopen("TextFile.txt", "w");
    	
    	fclose(fp1);
    	fclose(fp2);
    	return 0;
    }
    
    //在终端上显示创建的哈夫曼树 
    void Display_Htree(Htree HT, int end)
    {
    	int i;
    	printf("序号\t权值\t左孩子\t右孩子\t双亲\n");
    	for(i = 1; i <= end; i++)
    	{
    		printf("%d\t%d\t%d\t%d\t%d\n", i, HT[i].weight, HT[i].lchild, HT[i].rchild, HT[i].parent);
    	}
    }
    
    //找到树中权值最小的两个结点 
    void find_min_node(Htree HT,int &min1,int &min2,int end)
    {
    	int i;
    	//先找min1 
    	for(i = 1; i <= end; i++)
    	{
    		if(!HT[i].parent)
    		{
    			min1 = i;
    			break;
    		}
    	}
    	for(; i <= end; i++)
    	{
    		if(!HT[i].parent && HT[min1].weight > HT[i].weight)
    			min1 = i;
    	}
    	//再找min2 
    	for(i = 1; i <= end; i++)
    	{
    		//并且要保证不能和min1重复 
    		if(!HT[i].parent && i != min1)
    		{
    			min2 = i;
    			break;
    		}
    	}
    	for(i = 1; i <= end; i++)
    	{
    		if(!HT[i].parent && HT[min2].weight > HT[i].weight && i != min1)
    			min2 = i;
    	}
    }
    
    展开全文
  • 信息论课程设计-哈夫曼编码。将英文字符的统计概率作为待编码节点权值。编程得出哈夫曼的码表;输入一段英文字符,利用码表对其编码译码。显示整个流程
  • 数据结构哈夫曼树编码译码实验报告--15页.pdf
  • 哈夫曼树编码译码实验报告.doc
  • 哈夫曼树编码译码[归类].pdf
  • 数据结构哈夫曼树编码译码实验报告.doc
  • 数据结构课程设计哈夫曼树编码解码。
  • 数据结构-哈夫曼树编码译码-课程设计-实验报告_免费下载.doc.doc
  • 利用已建好的哈夫曼树将文件 CodeFile 中的代码进行译码,结果存入文件TextFile中。 (4)P:打印代码文件(Print)。将文件CodeFile以紧凑格式显示在终端上,每行 50 个代码。同时将此字符形式的编码文件写入文件 ...
  • 数据结构实验,实现哈夫曼树的创建,并且实现编码译码功能,满足任意字符串的输入,输出编码;也可满足任意编码输入,输出字符串。在创建哈夫曼树时输入权值与对应的字符。
  • 78 /*-----------创建工作---------------------------*/79 int s1,s2;80 for (int i = n + 1;... ++i)81 {//通过n-1次的选择,删除,合并来构造哈夫曼树82 Select(HT, i - 1, s1, s2);83 /*cout <&...

    78 /*-----------创建工作---------------------------*/

    79     int s1,s2;

    80     for (int i = n + 1; i <= m; ++i)

    81     {//通过n-1次的选择,删除,合并来构造哈夫曼树

    82         Select(HT, i - 1, s1, s2);

    83         /*cout << HT[s1].weight << " , " << HT[s2].weight << endl;*/

    84         /*将s1,s2的双亲域由0改为i

    85         (相当于把这两个结点删除了,这两个结点不再参与Select()函数)*/

    86         HT[s1].parent = i;

    87         HT[s2].parent = i;

    88         //s1,与s2分别作为i的左右孩子

    89         HT[i].lchild = s1;

    90         HT[i].rchild = s2;

    91         //结点i的权值为s1,s2权值之和

    92         HT[i].weight = HT[s1].weight + HT[s2].weight;

    93     }

    94 }

    95

    96 //从叶子到根逆向求每个字符的哈夫曼编码,储存在编码表HC中

    97 void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n)

    98 {

    99     HC = new char*[n + 1];//分配储存n个字符编码的编码表空间

    100     char *cd = new char[n];//分配临时存储字符编码的动态空间

    101     cd[n - 1] = '\0';//编码结束符

    102     for (int i = 1; i <= n; i++)//逐个求字符编码

    103     {

    104         int start = n - 1;//start 开始指向最后,即编码结束符位置

    105         int c = i;

    106         int f = HT[c].parent;//f指向结点c的双亲

    107         while (f != 0)//从叶子结点开始回溯,直到根结点

    108         {

    109             --start;//回溯一次,start向前指向一个位置

    110             if (HT[f].lchild == c) cd[start] = '0';//结点c是f的左孩子,则cd[start] = 0;

    111             else cd[start] = '1';//否则c是f的右孩子,cd[start] = 1

    112             c = f;

    113             f = HT[f].parent;//继续向上回溯

    114         }

    115         HC[i] = new char[n - start];//为第i个字符编码分配空间

    116         strcpy(HC[i], &cd[start]);//把求得编码的首地址从cd[start]复制到HC的当前行中

    117     }

    118     delete cd;

    119 }

    120

    121 //哈夫曼译码

    122 void TranCode(HuffmanTree HT,char a[],char zf[],char b[],int n)

    123 {

    124     /*

    125     HT是已经创建好的哈夫曼树

    126     a[]用来传入二进制编码

    127     b[]用来记录译出的字符

    128     zf[]是与哈夫曼树的叶子对应的字符(叶子下标与字符下标对应)

    129     n是字符个数,相当于zf[]数组得长度

    130     */

    131

    132     int q = 2*n-1;//q初始化为根结点的下标

    133     int k = 0;//记录存储译出字符数组的下标

    134     int i = 0;

    135     for (i = 0; a[i] != '\0';i++)

    136     {//for循环结束条件是读入的字符是结束符(二进制编码)

    137         //此代码块用来判断读入的二进制字符是0还是1

    138         if (a[i] == '0')

    139         {/*读入0,把根结点(HT[q])的左孩子的下标值赋给q

    140          下次循环的时候把HT[q]的左孩子作为新的根结点*/

    141             q = HT[q].lchild;

    142         }

    143         else if (a[i] == '1')

    144         {

    145             q = HT[q].rchild;

    146         }

    147         //此代码块用来判断HT[q]是否为叶子结点

    148         if (HT[q].lchild == 0 && HT[q].rchild == 0)

    149         {/*是叶子结点,说明已经译出一个字符

    150         该字符的下标就是找到的叶子结点的下标*/

    151             b[k++] = zf[q];//把下标为q的字符赋给字符数组b[]

    152             q = 2 * n - 1;//初始化q为根结点的下标

    153             //继续译下一个字符的时候从哈夫曼树的根结点开始

    154         }

    155     }

    156     /*译码完成之后,用来记录译出字符的数组由于没有结束符输出的

    157     时候回报错,故紧接着把一个结束符加到数组最后*/

    158     b[k] = '\0';

    159 }

    160 //菜单函数

    161 void menu()

    162 {

    163     cout << endl;

    164     cout << "       ┏〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓┓" << endl;

    165     cout << "       ┃      ★★★★★★★哈夫曼编码与译码★★★★★★★        ┃" << endl;

    166     cout << "       ┃                   1.  创建哈夫曼树                       ┃" << endl;

    167     cout << "       ┃                   2.  进行哈夫曼编码                     ┃" << endl;

    168     cout << "       ┃                   3.  进行哈夫曼译码                     ┃" << endl;

    169     cout << "       ┃                   4.  退出程序                           ┃" << endl;

    170     cout << "       ┗〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓┛" << endl;

    171     cout << "                       <><>" << endl;

    172     cout << endl;

    173 }

    174 void main()

    175 {

    176     int falg;//记录要编码的字符个数

    177     char a[MAX_MA];//储存输入的二进制字符

    178     char b[MAX_ZF];//存储译出的字符

    179     char zf[MAX_ZF];//储存要编码的字符

    180     HuffmanTree HT = NULL;//初始化树为空数

    181     HuffmanCode HC = NULL;//初始化编码表为空表

    182     menu();

    183     while (true)

    184     {

    185         int num;

    186         cout << "<><>: ";

    187             cin >> num;

    188             switch (num)

    189             {

    190             case 1 :

    191                 cout << "<><>:";

    192                 cin >> falg;

    193                 //动态申请falg个长度的字符数组,用来存储要编码的字符

    194                 /*char *zf = new char[falg];*/

    195                 cout << "<><>: ";

    196                 for (int i = 1; i <= falg; i++)

    197                     cin >> zf[i];

    198                 cout << "<><>: ";

    199                 CreateHuffmanTree(HT, falg);//调用创建哈夫曼树的函数

    200                 cout << endl;

    201                 cout << "<><>:" << endl;

    202                 cout << endl;

    203                 cout << "结点i"<

    204                 for (int i = 1; i <= falg * 2 - 1; i++)

    205                 {

    206                     cout << i << "\t"<

    207                 }

    208                 cout << endl;

    209                 break;

    210             case 2:

    211                 CreatHuffmanCode(HT, HC, falg);//调用创建哈夫曼编码表的函数

    212                 cout << endl;

    213                 cout << "<><>:" << endl;

    214                 cout << endl;

    215                 cout << "结点i"<

    216                 for (int i = 1; i <= falg; i++)

    217                 {

    218                     cout << i << "\t"<

    219                 }

    220                 cout << endl;

    221                 break;

    222             case 3:

    223                 cout << "<><>:";

    224                 /*这样可以动态的直接输入一串二进制编码,

    225                 因为这样输入时最后系统会自动加一个结束符*/

    226                 cin >> a;

    227                 TranCode(HT, a, zf, b, falg);//调用译码的函数,

    228                  /*这样可以直接把数组b输出,因为最后有

    229                  在数组b添加输出时遇到结束符会结束输出*/

    230                 cout << endl;

    231                 cout << "<><>:" << b << endl;

    232                 cout << endl;

    233                 break;

    234             case 4:

    235                 cout << endl;

    236                 cout << "<><>" << endl;

    237                 exit(0);

    238             default:

    239                 break;

    240             }

    241     }

    242

    243     //-abcdefghijklmnopqrstuvwxyz

    244     //186 64 13 22 32 103 21 15 47 57 1 5 32 20 57 63 15 1 48 51 80 23 8 18 1 16 1

    245     //000101010111101111001111110001100100101011110110

    246

    247 }

    展开全文
  • 用C++实现的哈夫曼编译码器,可以实现创建哈夫曼树、对txt文件进行编码译码,也可以查看生成的哈夫曼树。数据结构作业参考之必备品。
  • 哈夫曼树编码译码 用下表给出的字符集和频度的实际统计数据建立哈夫曼树,并实现以下报文的编码和译码:“THIS PROGRAM IS MY FAVORITE” 字符 A B C D E F G H I J K L M 频度 64 13 22 32 103 21 15 47 57 1 5 32...
  • C语言 哈夫曼树编码译码、输出。

    千次阅读 2022-02-15 21:10:07
    使用下标模拟指针和结构体指针构建哈夫曼树

    哈夫曼树的知识点概述网上有很多了,就不再补充,主要是分享一下自己对一道题的解题思路。
    在这里插入图片描述
    在这里插入图片描述

    概述:构建哈夫曼树时,先用下标模拟数组,从叶子结点开始往上构建完整棵哈夫曼树。但和普通二叉树不同,叶子结点在1-n (0号位不用,n为输入的字符个数),根结点在 2n-1 ,其他位置为构造出的中介结点。
    在这里插入图片描述

    虽然哈夫曼树构建好了,很多操作树的方法得依赖于下标模拟的指针实现,每次方法调用的参数都得传入整个结构体数组。所以在构建时,多定义一个结构体指针。构建好哈夫曼树之后,每次操作树的时候可以通过传入树根的指针,当作一棵普通的二叉树来操作整棵树。(详细代码在哈夫曼树构建。)

    (笔者第一次写博客,内容难免有些浅显或错误之处,还请大家指出一起探讨,共勉。)

    走个流程。

    1. 树结点结构体。
    二叉树可以用下标模拟指针(属性 L、R),也可以自己定义结构体指针(LChild、RChild)。这里笔者为了方便后面的先序输出哈夫曼树存储的字符,就定义了结构体指针。

    #define M N * 2 - 1   // 30个字符,计算可得出总节点个数。
    #define N 30          // 叶子节点个数。假设最多输入30个字符。
    #define MAX 999
    // 哈夫曼树结构体。
    typedef struct tree {
        char ch;         // 字符。
        double weight;   // 权重。
        int parent;     // 父结点。
        int L, R;        // 左右子树的下标。
        struct tree *LChild;	// 左孩子结点指针。
        struct tree *RChild;	// 右孩子结点指针。
        char hashcode[N];   // 字符的哈希编码。
        int is_leaves;		// 是否是叶子结点标记。
    } tree, Htree[M];		// tree 是单个结点,Htree 是结构体数组。
    

    2. 哈夫曼树构建。

    // 选择最小权重的两个节点
    // 具体代码实现大同小异。找出权重最小的两个结点,标记下标位置,再修改父亲结点参数,下次不再进行参与比较排序。
    void Select(Htree ht, int n, int *s1, int *s2) {
        int i;
        double min1 = MAX, min2 = MAX;
        *s1 = 0;
        *s2 = 0;
        for (i = 1; i <= n; i++) {
            if (ht[i].parent == 0) {
                if (ht[i].weight < min1) {
                    min2 = min1;
                    *s2 = *s1;
                    min1 = ht[i].weight;
                    *s1 = i;
                } else if (ht[i].weight < min2) {
                    min2 = ht[i].weight;
                    *s2 = i;
                }
            }
        }
    }
    
    // 构建哈夫曼树
    void crateHtree(Htree ht, int n) {
        int i;
        // 初始化叶子节点。
        // 叶子结点从1-n。(0号位不用)
        char s[10];
        for (i = 1; i <= n; i++) {
            ht[i].parent = 0;
            ht[i].L = 0;
            ht[i].R = 0;
            ht[i].is_leaves = 1;
            ht[i].RChild = NULL;
            ht[i].LChild = NULL;
        }
        // 初始化树的非叶子节点。 n+1项开始。
        for (i = n + 1; i <= 2 * n - 1; i++) {
            ht[i].weight = 0;
            ht[i].parent = 0;
            ht[i].L = 0;
            ht[i].R = 0;
            ht[i].is_leaves = 0;	
            ht[i].RChild = NULL;
            ht[i].LChild = NULL;
        }
        // 开始构建哈夫曼树。
        // 和平时的构建树方法不同,从下往上构建,新的结点为现有结点的父亲结点,新结点的左右孩子指针指向原有参与构建的两个结点。
        int s1, s2;
        for (i = n + 1; i <= n * 2 - 1; i++) {
            Select(ht, i - 1, &s1, &s2);
            // 新的中介结点。
            ht[i].weight = ht[s1].weight + ht[s2].weight;
            ht[i].parent = 0;
            ht[s1].parent = i;
            ht[s2].parent = i;
            // 新结点下标模拟的指针初始化。
            ht[i].L = s1;
            ht[i].R = s2;
            // 新节点结构体指针初始化。
            ht[i].RChild = &ht[s2];		
            ht[i].LChild = &ht[s1];
        }
    }
    
    

    3. 哈夫曼编码。

    // 根据哈夫曼树创建哈夫曼编码,从叶子节点开始。
    void crateTcode(Htree ht, int n) {
        int i;
        char cd[n];
        for (i = 1; i <= n; i++) {
        	// 编码长度最大为n-1。c为当前结点的下标,p为当前结点的父亲结点下标
            int start = n - 1, c = i, p = ht[i].parent;
            while (p != 0) {
                start--;
                if (ht[p].L == c)
                    cd[start] = '0';
                else
                    cd[start] = '1';
                // 迭代更新
                c = p;
                p = ht[c].parent;
            }
            // 将处理后的哈希节点存入哈希结构体数组。
            // tps: 编码不一定是最大长度,中间可能有没处理的其他字符,需要判断是否是0,1编码才存入字符串中。
            int t = 0;
            for (int j = 0; j < n; j++) {
                if (cd[j] == '0' || cd[j] == '1') {
                    ht[i].hashcode[t] = cd[j];
                    t++;
                }
            }
            memset(cd, 0, sizeof cd);     // 清空cd字符串。
        }
    }
    

    4. 译码。

    // 翻译编码
    // 优:不用预先设置字符串数组存储翻译后的内容,也不用考虑长度范围。
    // 缺:无论编码是否能翻译,都会输出"original:"。
    void Search(Htree ht, const char String[2000], int n) {
        int t = 2 * n - 1;
        printf("original:");
        unsigned long len = strlen(String); // 函数结果返回无符号长整型。
        for (int i = 0; i < len; i++) {
            if (String[i] == '0') {
                t = ht[t].L;
                if (ht[t].is_leaves) {
                    printf("%c", ht[t].ch);
                    t = 2 * n - 1;
                }
            } else {
                t = ht[t].R;
                if (ht[t].is_leaves) {
                    printf("%c", ht[t].ch);
                    t = 2 * n - 1;
                }
            }
        }
    }
    

    5. 输出。

    // 先序输出所有的节点哈希编码。
    // 递归实现先序遍历。
    void PreOder(tree *root) {
        if (root->is_leaves)
            printf("%c:%s\n", root->ch, root->hashcode);
        if (root->LChild) PreOder(root->LChild);
        if (root->RChild) PreOder(root->RChild);
    }
    

    6. 主函数

    int main() {
        Htree ht;
        char String[2000];
        int n;
        scanf("%d", &n);
        // 输出并存储数据。
        for (int i = 1; i <= n; i++) {
            char s[10];
            scanf("%s", s);
            ht[i].ch = s[0];                                            // 取出第一个字符。
            ht[i].weight = strtod(strcpy(s, s + 1), NULL);  // 取出字符后的权值。
        }
        scanf("%s", String);            // 读入需要翻译的编码。
        crateHtree(ht, n);              // 构建哈夫曼树。
        crateTcode(ht, n);              // 构建哈夫曼编码。
        PreOder(&ht[2 * n - 1]);        // 哈夫曼树树根最后形成。传入树根,可以通过指针遍历(先序)。
        Search(ht, String, n);          // 传入结构体数组。(传入指针可以更优,注:这里写的方法参数是结构体数组。)
        return 0;
    }
    

    完整代码。

    #include<stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    #define M N * 2 - 1   // 30个词频,叶子节点个数。
    #define N 30          // 总节点个数。
    #define MAX 999
    // 哈夫曼树结构体。
    typedef struct tree {
        char ch;         // 字符
        double weight;   // 权重
        int parent;     // 父节点
        int L, R;        // 左右子树
        struct tree *LChild;
        struct tree *RChild;
        char hashcode[N];   // 字符的哈希编码
        int is_leaves;
    } tree, Htree[M];
    
    // 选择最小权重的两个节点
    void Select(Htree ht, int n, int *s1, int *s2) {
        int i;
        double min1 = MAX, min2 = MAX;
        *s1 = 0;
        *s2 = 0;
        for (i = 1; i <= n; i++) {
            if (ht[i].parent == 0) {
                if (ht[i].weight < min1) {
                    min2 = min1;
                    *s2 = *s1;
                    min1 = ht[i].weight;
                    *s1 = i;
                } else if (ht[i].weight < min2) {
                    min2 = ht[i].weight;
                    *s2 = i;
                }
            }
        }
    }
    
    // 构建哈夫曼树
    void crateHtree(Htree ht, int n) {
        int i;
        // 初始化叶子节点。
        char s[10];
        for (i = 1; i <= n; i++) {
            ht[i].parent = 0;
            ht[i].L = 0;
            ht[i].R = 0;
            ht[i].is_leaves = 1;
            ht[i].RChild = NULL;
            ht[i].LChild = NULL;
        }
        // 初始化树的非叶子节点。 n+1项开始。
        for (i = n + 1; i <= 2 * n - 1; i++) {
            ht[i].weight = 0;
            ht[i].parent = 0;
            ht[i].L = 0;
            ht[i].R = 0;
            ht[i].is_leaves = 0;
            ht[i].RChild = NULL;
            ht[i].LChild = NULL;
        }
        // 开始构建哈夫曼树。
        int s1, s2;
        for (i = n + 1; i <= n * 2 - 1; i++) {
            Select(ht, i - 1, &s1, &s2);
            ht[i].weight = ht[s1].weight + ht[s2].weight;
            ht[i].parent = 0;
            ht[s1].parent = i;
            ht[s2].parent = i;
            ht[i].L = s1;
            ht[i].R = s2;
            ht[i].RChild = &ht[s2];
            ht[i].LChild = &ht[s1];
        }
    }
    
    // 根据哈夫曼树创建哈夫曼编码,从叶子节点开始。
    void crateTcode(Htree ht, int n) {
        int i;
        char cd[n];
        for (i = 1; i <= n; i++) {
            int start = n - 1, c = i, p = ht[i].parent;
            while (p != 0) {
                start--;
                if (ht[p].L == c)
                    cd[start] = '0';
                else
                    cd[start] = '1';
                c = p;
                p = ht[c].parent;
            }
            // 将处理后的哈希节点存入哈希结构体数组。
            // tps: 中间可能有其他字符。
            int t = 0;
            for (int j = 0; j < n; j++) {
                if (cd[j] == '0' || cd[j] == '1') {
                    ht[i].hashcode[t] = cd[j];
                    t++;
                }
            }
            memset(cd, 0, sizeof cd);     // 清空cd字符串。
        }
    }
    
    // 先序输出所有的节点哈希编码。
    // 递归实现先序遍历。
    void PreOder(tree *root) {
        if (root->is_leaves)
            printf("%c:%s\n", root->ch, root->hashcode);
        if (root->LChild) PreOder(root->LChild);
        if (root->RChild) PreOder(root->RChild);
    }
    
    // 翻译编码
    void Search(Htree ht, const char String[2000], int n) {
        int t = 2 * n - 1;
        printf("original:");
        unsigned long len = strlen(String); // 函数结果返回无符号长整型。
        for (int i = 0; i < len; i++) {
            if (String[i] == '0') {
                t = ht[t].L;
                if (ht[t].is_leaves) {
                    printf("%c", ht[t].ch);
                    t = 2 * n - 1;
                }
            } else {
                t = ht[t].R;
                if (ht[t].is_leaves) {
                    printf("%c", ht[t].ch);
                    t = 2 * n - 1;
                }
            }
        }
    }
    
    int main() {
        Htree ht;
        char String[2000];
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            char s[10];
            scanf("%s", s);
            ht[i].ch = s[0];                                            // 取出第一个字符。
            ht[i].weight = strtod(strcpy(s, s + 1), NULL);  // 取出字符后的权值。
        }
        scanf("%s", String);            // 读入需要翻译的编码。
        crateHtree(ht, n);              // 构建哈夫曼树。
        crateTcode(ht, n);              // 构建哈夫曼编码。
        PreOder(&ht[2 * n - 1]);   		// 传入树根,可以通过结构体指针遍历(先序)。
        Search(ht, String, n);          // 传入结构体数组。(传入指针可以更优,注:这里写的方法参数是结构体数组。)
        return 0;
    }
    
    
    
    展开全文
  • 哈夫曼编码的c语言实现,代码中有注释。有编码译码功能,能输出每个字符的Huffman码。可以输入一段Huffman码反应成文本,也可以输入一段文本翻译成Huffman码。计算了信源熵,编码效率,和平均编码长度。
  • 哈夫曼树编码译码器(你们懂的)

    千次阅读 多人点赞 2019-04-09 20:00:19
    哈夫曼树编码译码器 希望点赞一下,哈哈哈哈哈 #include<stdio.h> #include<malloc.h> #define maxval 10000.0 #define maxsize 100 //哈夫曼编码的最大位数 typedef struct { char ch; float ...
  • 给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。
  • 建立哈夫曼树 编码 译码 详细的步骤 程序和流程图 心得体会等
  • 哈夫曼树编码译码

    2012-11-26 01:18:13
    根据哈夫曼算法思想做的数据结构实验的小工具,提供对文件的哈夫曼思想编码译码。提供给大家参考。(注:欲参考代码,请联系,将发送代码并欢迎提出意见互相交流学习)
  • C++数据结构,利用哈夫曼树进行编码译码,结课实训等可用

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,628
精华内容 1,051
关键字:

哈夫曼树编码译码