【数据结构】哈夫曼树实现编码译码

首页 > 代码库 > 【数据结构】哈夫曼树实现编码译码

【数据结构】哈夫曼树实现编码译码

2024-10-28 01:59:01 210人阅读

根据一段字符串中字符的个数作为该字符的权值生成哈夫曼树。

然后根据生成的哈夫曼编码，对任意字符串实现编码，对任意二进制串实现译码。

程序运行结果：

1.程序主界面：

技术分享

2.根据字符串创建哈夫曼树及编码：

技术分享

3.生成的编码表如下：

技术分享

4.根据生成的哈夫曼编码对字符串编码：

技术分享

5.生成的编码保存在文件中：

技术分享

6.对二进制串译码：

技术分享

结果：

技术分享

代码：

哈夫曼树的生成和编码的常见，以及编码和译码函数

//_HuffmanTree_H
#ifndef _HuffmanTree_H
#define _HuffmanTree_H

typedef struct
 {
   unsigned int weight;
   char ch;
   unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; 
 typedef char **HuffmanCode; 

//这三个是哈夫曼树的生成
int min1(HuffmanTree t,int i);     //选出权值数组中最小的一个 ，，

void select(HuffmanTree t,int i,int *s1,int *s2);   //权值数组中最小的两个，，，并把临时数组对应位置改为1防止重复选择

void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n);  //根据权值数组W，和元素个数N开辟空间，HC存放编码

void getWeightInfile(int *w);// 从MyTxt.TXT里读入字母，以字母个数为权值，生成数组并返回

void bianMaInFile(HuffmanTree *p,HuffmanCode cd);    //根据编码.txt里面字母，找到对应的下标，在hc里面匹配编码

void yimaInFile(HuffmanTree *p);   //分析出  数的根结点下标应该为2n-1。。。所以只需根据编码 0 1确定向左还是向右 最终直到=遇到有意义的字母停止



#endif  //

对指定文件的读和写

//myfile.h
#ifndef _MYFILE_H
#define _MYFILE_H
#define MY_STRMAX 100

void changMyTxtFile();
void showMyTxtFile();
void showBianMaFile();
void showYiMaFile();
void changBianMaFile();

#endif   //myfile.h

//HuffmanTree.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "HuffmanTree.h"



int min1(HuffmanTree t,int i)
 { /* 返回i个结点中权值最小的树的根结点序号，函数select()调用 */
	int j,flag;
	unsigned int k=10000000; /* 取k为不小于可能的值(无符号整型最大值) */
	for(j=1;j<=i;j++)
		if(t[j].weight<k&&t[j].parent==0) /* t[j]是树的根结点 */
			k=t[j].weight,flag=j;
		t[flag].parent=1; /* 给选中的根结点的双亲赋1，避免第2次查找该结点 */
		return flag;
 }


void select(HuffmanTree t,int i,int *s1,int *s2)
{ /* 在i个结点中选择2个权值最小的树的根结点序号，s1为其中序号小的那个 */
	int j;
	*s1=min1(t,i);
	*s2=min1(t,i);
	if(*s1>*s2)
	{
		j=*s1;
		*s1=*s2;
		*s2=j;
	}
 }

void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n) /* 算法6.12 */
{ /* w存放n个字符的权值(均>0)，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC */
	int m,i,s1,s2,start,num=0;
	unsigned c,f;
	HuffmanTree p;
	char *cd;
	if(n<=1)
		return;
	m=2*n-1;    //开辟的空间 比元素个数多 因为后续生成的新子树要用到
	*HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /* 0号单元未用 */
	for(p=*HT+1,i=1;i<=n;++i,++p,++w,++num)
	{
		(*p).weight=*w; //这部分是给确定的子树赋值，包括字母a-z 权值从数组中得出
			if(i<26)
				(*p).ch=97+num;
			else if(i==26)
			{
				(*p).ch=97+num;
				num=-1;
			}
			else if(i<=52&&i>26)
				(*p).ch=65+num;
			else if(i==53)
				(*p).ch=32;
			else if(i==54)
				(*p).ch='\n';
		(*p).parent=0;
		(*p).lchild=0;
		(*p).rchild=0;
	}
	for(;i<=m;++i,++p)
		(*p).parent=0;
	for(i=n+1;i<=m;++i) /* 建赫夫曼树 */
	{ /* 在HT[1～i-1]中选择parent为0且weight最小的两个结点，其序号分别为s1和s2 */
		select(*HT,i-1,&s1,&s2);
		(*HT)[s1].parent=(*HT)[s2].parent=i;     //这部分给后面要用到的新节点 初值
		(*HT)[i].lchild=s1;
		(*HT)[i].rchild=s2;
		(*HT)[i].ch='!';                        //他们存放的是!   所以可以判断此节点是否有意义
		(*HT)[i].weight=(*HT)[s1].weight+(*HT)[s2].weight;
	}


//哈夫曼 编码 的求出  保存在HC里面（二维数组）



	/* 从叶子到根逆向求每个字符的赫夫曼编码 */
	*HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
	/* 分配n个字符编码的头指针向量([0]不用) */
	cd=(char*)malloc(n*sizeof(char)); /* 分配求编码的工作空间 */
	cd[n-1]='\0'; /* 编码结束符 */
	for(i=1;i<=n;i++)
	{ /* 逐个字符求赫夫曼编码 */
		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));
			/* 为第i个字符编码分配空间 */
			strcpy((*HC)[i],&cd[start]); /* 从cd复制编码(串)到HC */
	}
	free(cd); /* 释放工作空间 */
}


void getWeightInfile(int *w)    
{
	FILE *pfr;
	int i=0;
	pfr = fopen("记录信息\\mytxt.txt", "r");//读取文件
	if (pfr==NULL)
	{
		printf("文件操作失败");
		return ;
	}
	else
	{
		while (!feof(pfr))     //直到文件读取完毕，每次读取一行
		{
			char str[256] = {0};
			fgets(str, 256, pfr);//读取一行
			i=0;
			while(str[i]!=0)    //如果这是个字母，那么对应数组的从0-25 发现一个 对应的值加加  实现计算文件中字母的个数
			{	
				if(str[i]<='z' && str[i]>='a')      //97-122   65-90  32
					w[str[i]-97]++;
				if(str[i]<='Z'&& str[i]>='A')
					w[str[i]-65+26]++;
				if(str[i]==' ')
					w[26*2]++;
				if(str[i]=='\n')
					w[26*2+1]++;
				i++;
				
			}			
		}
	}
	fclose(pfr);
}                    //文件用完要关闭



void bianMaInFile(HuffmanTree *p,HuffmanCode cd)
{
	FILE *pfr;
	FILE *pfw;
	//HuffmanTree ptr=(*p)+1;
	int i;
	int num;
	int count=1;
	pfr = fopen("记录信息\\mytxt.txt", "r");//读取文件
	pfw = fopen("记录信息\\编码.txt","w");//写入文件
	if (pfr==NULL || pfw==NULL)
	{
		printf("文件操作失败");
		return ;
	}
	else 
	{
		while (!feof(pfr))
		{
			char str[256] = {0};
			fgets(str, 256, pfr);//读取一行
			i=0;
			num=-1;
			while(str[i]!=0)
			{	
				
				if(str[i]<=122 && str[i]>=97)     //1-26
							num=str[i]-96;
				else if(str[i]<=90 && str[i]>=65)  //27-52
							num=str[i]-64+26;
				else if(str[i]==32)   
							num=53;
				else if(str[i]=='\n')
							num=54;
				if(num!=-1)//就把cd里面的编码 输出到 编码.txt里面
				{
					if(count==1)
						count++;
					else
						//fputs(cd[num], pfw); 
						fprintf(pfw,"%s\n",cd[num]);
				}
				i++;
				num=-1;
				
			}			
		}
		fclose(pfr);
		fclose(pfw);
	}
}

void yimaInFile(HuffmanTree *p)
{
	FILE *pfr;
	FILE *pfw;
	char s[2]={0};
	int i=0,num=107;  //51=2*26-1    2*54-1
	int n;
	pfr = fopen("记录信息\\编码.txt", "r");//读取文件
	pfw = fopen("记录信息\\译码.txt","w");//写入文件
	if (pfr==NULL || pfw==NULL)
	{
		printf("文件操作失败");
		return ;
	}
	else 
	{
		while (!feof(pfr))
		{
			char str[255] = {0};			
			fgets(str, 255, pfr);
			i=0;//读取一行
			num=107;
			while(str[i]!=0)
			{	n=i;
				while(str[i]!=0)
				{
					if((*p)[num].ch!='!')            //如果发现 左右移动找到了字母 立马退出 匹配下一个
						break;
					if(str[i]=='0')                 //0左1右
						num=(*p)[num].lchild;
					else if(str[i]=='1')
						num=(*p)[num].rchild;					
					i++;
				}
				if((*p)[num].ch=='!' && str[i]!='\0')
					printf("因为编码不全,%d-%d个编码被舍掉\n",n+1,i);
				else if(str[i]!='\0')
				{	
					s[0]=(*p)[num].ch;
					fputs(s, pfw);
				}
				num=107;
				
			}
		}
	}
	fclose(pfr);
	fclose(pfw);
}

//myfile.c
#include <stdlib.h>
#include <stdio.h>
#include "myfile.h"
#include <conio.h>

void changMyTxtFile()
{
	FILE *pfw;
	int s;
	int num=1;
	pfw=fopen("记录信息\\mytxt.txt","w");
	if (pfw==NULL)
	{
		printf("文件操作失败");
		return;
	}
	while(s=getchar(),s!=-1)
	{
		fprintf(pfw,"%c",s);
	}
	fclose(pfw);
}
void showMyTxtFile()
{
	FILE *pfr;
	pfr=fopen("记录信息\\mytxt.txt","r");
	if (pfr==NULL)
	{
		printf("文件操作失败");
		return ;
	}
	else 
	{	
		while (!feof(pfr))
		{
			char str[256] = {0};			
			fgets(str, 256, pfr);          //动态  遍历文件
			puts(str);
		}
	}
	fclose(pfr);
}

void showBianMaFile()
{
	FILE *pfr;
	pfr=fopen("记录信息\\编码.txt","r");
	if (pfr==NULL)
	{
		printf("文件操作失败");
		return ;
	}
	else 
	{	
		while (!feof(pfr))
		{
			char str[256] = {0};			
			fgets(str, 256, pfr);
			puts(str);
		}
	}
	fclose(pfr);
}

void showYiMaFile()
{
	FILE *pfr;
	pfr=fopen("记录信息\\译码.txt","r");
	if (pfr==NULL)
	{
		printf("文件操作失败");
		return ;
	}
	else 
	{	
		while (!feof(pfr))
		{
			char str[256] = {0};			
			fgets(str, 256, pfr);
			puts(str);
		}
	}
	fclose(pfr);
}

void changBianMaFile()
{
	
	FILE *pfw;
	int s;
	pfw=fopen("记录信息\\编码.txt","w");
	if (pfw==NULL)
	{
		printf("记录信息\\文件操作失败");
		return ;
	}
	while(s=getchar(),s!=-1)
	{
		fprintf(pfw,"%c",s);
	}
	fclose(pfw);
	
}

//main.c
#include <STDLIB.H>
#include <STDIO.H>
#include "HuffmanTree.h"
#include "myfile.h"


#define MYHFMNUM 26*2+2

int  main()
{
	   HuffmanTree HT;
	   HuffmanCode HC;
	   int w[MYHFMNUM]={0},n=MYHFMNUM,i;
	   char s[MY_STRMAX]={0};
	   int num;
		system("color 3e");    //改颜色
MENU:
			system("cls");
	   puts("***********************************************");
	   puts("		1.创建新的编码");
	   puts("		2.编码");
	   puts("		3.译码");
	   puts("		4.退出");
	   puts("***********************************************");

	   puts("输入想要的操作:");
       scanf("%d",&num);
	   switch(num)
	   {
	   case 1: 
		   {	 FILE *pfw;	
			   system("cls");	 //每次操作清理屏幕
				puts("输入一段字符串，会根据字符数累加权值，从而生成树");
			   changMyTxtFile();
			   getWeightInfile(w);
			   HuffmanCoding(&HT,&HC,w,n);
			   pfw=fopen("记录信息\\编码表.txt","w");
			   if (pfw==NULL)
			   {
				   printf("文件操作失败");
				   return 0;
				}
					fprintf(pfw,"       编码    字母      权值\n");  
			   for(i=1;i<=n;i++) //把生成的   编码表  存在文件中 便于对照
			   {             
				   fprintf(pfw,"%10s\t%c\t%2d\n",HC[i],HT[i].ch,HT[i].weight);   
			   }

			   fclose(pfw);
				system("pause");
			   goto MENU;
		   }
	   case 2: 
		   {	system("cls");
			   puts("输入要编码的字符串");
			   changMyTxtFile();
			   bianMaInFile(&HT,HC); 
			   showBianMaFile();
			   system("pause");
			   goto MENU;
		   }
	   case 3:
			{	system("cls");
			   puts("输入要译码的二进制数字");
			   changBianMaFile();
			   yimaInFile(&HT);
			   showYiMaFile();
				system("pause");    //暂停一下  相当于getch
			   goto MENU;
		   }
	   case 4:return 0;
	   default:puts("输入有误!");system("pause");goto MENU;           
	   }
	   
	   return  0;
}

【数据结构】哈夫曼树实现编码译码

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > 【数据结构】哈夫曼树实现编码译码

【数据结构】哈夫曼树实现编码译码

看完仍有疑问？有类似问题直接问程序猿