一小只团子️️️
2021-05-17 21:25
采纳率: 80%
浏览 221

哈夫曼树的编码与解码

综合训练2 利用哈夫曼树进行编码与解码 一、主要目的: 理解哈夫曼树的概念、掌握哈夫曼树的建立以及利用利用哈夫曼树进行哈夫曼编码的方法。 二、主要内容: 在基于哈夫易树进行哈夫易编码的基础理论之上,完成对英文文竟的编码和解码,要求如下: 1、使用文件流方式。 自行查阅关于文件流的相关资料。 2、要求提供编码和解码两种方式 3、能够打开原文文件(dataxt),统计其中英文字母(假设均为小写)出现的频率,并以此进行哈夫曼编码(空格以及其他字符不加处理),将每个字母的哈夫曼编码输出到屏幕,并将编码后的结果输出到码文文件(code.xt)中。 4、能够根据3中得到的字符编码,将码文文件中的码文进行解码,得到解码后的原文(result.txt) 5、本综合训练以个人方式完成。 上交方法:各班班长统一收齐发送给我。(只要 CPP 文件,不用 data.txt 文件。)命名格式:数学X班 xxx.cpp 提示: (1)建立的哈夫曼树结点应添加保存字母的域 (2)教材中求哈夫曼编码的算法为递归算法,每次在递归中输出所求编码,而我们需要在对原文编码时使用每个字母的哈夫曼编码,所以应该将递归中求得的字母编码保存下来,以备后用。保存方式自行考虑。 (3)对原文进行编码时,根据读取到的每个字符进行处理:如果是字母,则往code.txt中输出相应编码(根据2中所得编码);如果是其它字符,则不加处理,直接输出到code.txt。(4)解码应在所建立的哈夫曼树基础上进行。依次读取code.txt 文件中字符,若为0或1.则0进左子树1进右子树,直到叶子结点然后取出叶子节点中的字母输出到result.txt:如果是其它字符,则不加处理,直接输出到result.txt。

  • 写回答
  • 好问题 提建议
  • 追加酬金
  • 关注问题
  • 邀请回答

2条回答 默认 最新

  • CSDN专家-sinJack 2021-05-17 21:40
    最佳回答
    tips:
    1,二进制文件读写(无法使用string)
    2,ASCII码和字符转换
    3,哈夫曼算法
    4,哈希思想的妙用(计算字频;编码使用) 
    
    数据结构
    typedef struct
    {
    	int ascii,weight,parent,lchild,rchild;//哈夫曼树,它们依次表示:字符的ASCII码,双亲,左孩子,右孩子 
    }HTNode,*HuffmanTree;
    
    算法
    假设有n个字符,申请2n个空间,0号不用 ,HTree数组首地址 
    1,初始化1,所有成员赋0;初始化2,读入字符及相应的权值
    2,令下个根节点j = n+1,在parent=0的点中挑选出最小值,次小值分别记录其下标index1,index2;
    3,最小值和次小值的parent=j;  
    */
    #include<iostream>
    using namespace std;
    #include<stdlib.h> 
    #include<fstream>
    #include<string>
    #include<stack>
    
    #define MIN1 0x1fffffff
    #define MIN2 0x2fffffff
    
    
    //Attention:只可以识别英文输入法下的所有字符,中文打出来的‘?’都不行 
    char code[20];//二进制读写准备 
    
    typedef struct
    {
    	int ascii,weight,parent,lchild,rchild;//哈夫曼树,它们一次表示:字符的ASCII码,双亲,左孩子,右孩子 
    }HTNode,*HuffmanTree;
    
    //统计每个字符出现次数:只有英文符号,否则报错 
    void Count_Character_Occur_Frequency()
    {
    	int cof[256];//存储相应字符出现的次数,字符ASCII为下标。charater_occur_frequency 
    	for(int i = 0; i < 256; i++)//初始化字符出现次数统计表 
    	{
    		cof[i] = 0;
    	}
    	//从源文件按行读取,并统计字符个数,由于字符个数有限,所以用字符的ASCII码作为数组下标,数组值作为次数,类似哈希映射 
    	fstream inFile("source.txt",ios::in); 
    	if(!inFile)cout<<"source.txt 打开失败!"<<endl;
    	
    	int sum = 0;//总行数,记录换行个数 
    	string s;//存放一行 
    	while(true)
    	{
    		getline(inFile,s);
    		if(!inFile)break;//避免重复读取最后一个字符 
    		sum++;
    		for(int i = 0; i < s.size(); i++)
    		{
    			int a = s[i];//cout<<"a:"<<a<<endl;中文会溢出 
    			cof[a]++; //计数 
    		}
    	}
    	inFile.close();//好习惯 
    	int a = '\n';//换行符 
    	cof[a] = sum; //换行符个数 
    	//=======将所有出现的字符及其次数写入文件(类似全局数组)========= 
    	int n = 0;//计算出现字符总个数 
    	for(int i = 0; i < 256; i++)
    	{
    		if(cof[i] != 0)n++; 
    	}
    	fstream outFile("data.txt",ios::out);
    	if(!outFile)cout<<"data.txt 打开失败!"<<endl;
    	outFile<<n<<endl;//写入字符总个数 
    	//打印调试 
    	for(int i = 0; i < 256; i++)
    	{
    		if(cof[i] != 0)
    		{
    			char ch = i - '\0';
    	//		cout<<"i: "<<i<<"  字符:"<<ch<<" cof[i]: "<<cof[i]<<endl;
    			outFile<<i<<" "<<cof[i]<<endl;//写入文件 
    		}
    	}
    	outFile.close();
    }
    //创建哈夫曼树 
    void CreateHT()
    {
    	HuffmanTree HTree;
    	fstream inFile("data.txt",ios::in);
    	if(!inFile)cout<<"data.txt 打开失败!"<<endl;
    	
    	int n;//节点个数
    	inFile>>n;
    	HTree = (HTNode*)malloc(2*n*sizeof(HTNode));//哈夫曼构造,共需2n-1个,0号单元不用
    	for(int i = 1; i < 2*n; i++)//初始化 1
    	{
    		HTree[i].ascii = HTree[i].lchild = HTree[i].parent = HTree[i].rchild = HTree[i].weight = 0;//0号单元无用 
    	} 
    	for(int i = 1; i <= n; i++)//初始化 2,从文件读取ASCII码及相应权值 
    	{
    		inFile>>HTree[i].ascii>>HTree[i].weight;
    	} 
    	inFile.close();
    /*	for(int i = 1; i < 2*n; i++)//打印输出调试 
    	{
    		cout<<HTree[i].ascii <<" "<<HTree[i].weight<<endl;
    	} 
    */	
    	for(int i = n+1; i < 2*n; i++)//从n+1开始,进行n-1次计算 
    	{
    		//寻找最小,次小值,记录其下标 
    		int min1 = MIN1,min2 = MIN2;
    		int index1 = 0,index2 = 0;
    		
    		for(int j = 1; j < i; j++)//i是即将要被填入的根节点 
    		{
    			if(HTree[j].parent == 0)//双亲为0表示尚待操作 
    			{
    				if(min1 > HTree[j].weight)
    				{
    					min2 = min1;//先赋给次小值 
    					index2 = index1;
    					min1 = HTree[j].weight;
    					index1 = j;
    				}
    				else if(min2 > HTree[j].weight)
    				{
    					min2 = HTree[j].weight;
    					index2 = j;
    				}
    			}
    		}//cout<<index1<<" "<<index2<<endl; 
    		
    		HTree[i].weight = HTree[index1].weight + HTree[index2].weight;//双亲权值更新 
    		HTree[index1].parent = HTree[index2].parent = i;//孩子的双亲节点更新
    		if(HTree[index1].weight < HTree[index2].weight)//1,两个节点权值不同,左小右大 ;相同,下标小者在左 
    		{
    			HTree[i].lchild = index1;//下标赋值 
    			HTree[i].rchild = index2;
    		}
    		else if(HTree[index1].weight > HTree[index2].weight)
    		{
    			HTree[i].lchild = index2;
    			HTree[i].rchild = index1;
    		}
    		else 
    		{
    			if(index1 < index2)
    			{
    				HTree[i].lchild = index1;
    				HTree[i].rchild = index2;
    			}
    			else
    			{
    				HTree[i].lchild = index2;
    				HTree[i].rchild = index1;
    			}
    		}
    	} 
    	fstream outFile("result.txt",ios::out);
    	if(!outFile)cout<<"result.txt 无法打开!"<<endl;
    	outFile<<n<<endl;//节点个数 
    	for(int i = 1; i < 2*n; i++)//打印输出调试 
    	{
    //		cout<<"i:"<<i<<" ascii:"<<HTree[i].ascii <<" weight:"<<HTree[i].weight<<" parent:"<<HTree[i].parent<<" lchild:"<<HTree[i].lchild<<" rchild:"<<HTree[i].rchild<<endl;
    		outFile<<" "<<HTree[i].ascii <<" "<<HTree[i].weight<<" "<<HTree[i].parent<<" "<<HTree[i].lchild<<" "<<HTree[i].rchild<<endl;	
    	} 
    	outFile.close();
    	
    	//==========建立编码表,写入字符,权值,编码==================
    	outFile.open("result.txt",ios::out);
    	if(!outFile)cout<<"result.txt 打开失败!"<<endl;
    	//利用栈从叶子出发读取每个字符的编码,在写入文件 
    	stack<char> code;//存储编码 
    	for(int i = 1; i <= n; i++)//对n个字符分别求编码 
    	{
    		int j = i;
    		do{
    			int p = HTree[j].parent;
    			if(p != 0)
    			{
    				int l,r;
    				l = HTree[p].lchild;
    				r = HTree[p].rchild;
    				if(j == l)code.push('0');
    				if(j == r)code.push('1');
    				j = p;
    			}
    		}while(HTree[j].parent != 0);
    		
    		outFile<<HTree[i].ascii<<" "<<HTree[i].weight<<" ";//写入字符,权值 
    		while(!code.empty())
    		{
    			outFile<<code.top();//写入编码 
    			code.pop();
    		}outFile<<endl;
    	} 
    	outFile.close();
    } 
    void Encode()
    {
    	fstream inFile("result.txt",ios::in);
    	if(!inFile)cout<< "result.txt"<<endl;
    	string s,codeList[256];//将编码表从文件读入该数组中,ASCII码为下标,类似哈希映射 
    	int ch,w;
    	while(true)
    	{
    		inFile>>ch>>w>>s;
    		if(!inFile)break;
    		codeList[ch] = s; 
    	}
    	inFile.close();
    	
    	inFile.open("source.txt",ios::in);
    	if(!inFile)cout<<"source.txt 打开失败!"<<endl;
    	fstream outFile("code.dat",ios::out|ios::binary);
    	if(!outFile)cout<<"code.dat打开失败!"<<endl;
    	string s2;
    	while(true)
    	{
    		getline(inFile,s);
    		if(!inFile)break;
    		int a;
    		for(int i = 0; i < s.size(); i++)
    		{
    			a = s[i];//转化为ASCII码 
    			int j; 
    			for(j = 0; j < codeList[a].size();j++)
    			{	
    				s2 = codeList[a];
    				code[j] = s2[j];
    			}code[j]='\0';//!!!关键的一句 
    			outFile.write((char*)code,20*sizeof(char));
    		}
    		a = '\n';
    		for(int j = 0; j < codeList[a].size();j++)
    		{
    			code[j]  = (codeList[a])[j];
    		}
    		outFile.write((char*)code,20*sizeof(char));
    	}
    	inFile.close();
    	outFile.close(); 
    }
    //解码 
    void Decode()
    {
    	fstream inFile("data.txt",ios::in);
    	if(!inFile)cout<<"data.txt 打开失败!"<<endl; 
    	int n;
    	inFile>>n;
    	HuffmanTree HTree;
    	HTree = (HTNode*)malloc(2*n*sizeof(HTNode));
    	for(int i = 1; i < 2*n; i++)
    	{
    		inFile>>HTree[i].ascii >>HTree[i].weight>>HTree[i].parent>>HTree[i].lchild>>HTree[i].rchild;	
    	}
    	inFile.close();
    	for(int i = 1; i < 2*n; i++)//打印输出调试 
    	{
    	//	cout<<"i:"<<i<<" ascii:"<<HTree[i].ascii <<" weight:"<<HTree[i].weight<<" parent:"<<HTree[i].parent<<" lchild:"<<HTree[i].lchild<<" rchild:"<<HTree[i].rchild<<endl;
    	} 
    /*	inFile.open("code.txt",ios::in);
    	if(!inFile)cout<<"code.txt 打开失败!"<<endl;
    */
    	inFile.open("code.dat",ios::in|ios::binary);
    	if(!inFile)cout<<"code.dat 打开失败!"<<endl;
    	
    	fstream outFile("recode.txt",ios::out);
    	if(!outFile)cout<<"recode.txt 打开失败!"<<endl;
    	char ch;
    	int root = 2*n - 1;//char code[100];
    //	string s;
    	while(true)
    	{
    		inFile.read((char*)code,20*sizeof(char));
    		if(!inFile)break;
    	//	cout<<"ch: "<<ch<<" root: "<<root<<endl;	
    		for(int i = 0; code[i] != '\0'; i++)
    		{//cout<<ch;
    			ch = code[i];
    			if(ch == '0')root = HTree[root].lchild;
    		else if(ch == '1')root = HTree[root].rchild;
    		
    		if(HTree[root].lchild == 0)
    		{//cout<<endl;
    			char cht = HTree[root].ascii;
    			outFile<<cht;
    			root = 2*n - 1;
    		} 
    		
    		}//cout<<endl;
    	}
    	outFile.close();
    }
    int main()
    {
    	Count_Character_Occur_Frequency();
    	CreateHT();
    	Encode();
    	Decode();
    	return 0;
    } 
    
    评论
    解决 无用
    打赏 举报
查看更多回答(1条)