哈弗曼编码译码程序代码,C代码库,德仔网

代码语言
代码分类
【C】哈弗曼编码译码程序
作者:OliverChu / 发布于2015/1/4/ 1132
打印树还不是很完整。数据结构专周写的，分享出来。

	package MySnackGame;
	
	import java.awt.Color;
	import java.awt.Graphics;
	import java.util.Random;
	
	public class Food {
	 // 食物参数
	 public static Point foodPoint = null;
	 public static final Color foodColor = Color.BLACK;
	
	 public Food() {
	 nextFood();
	 }
	
	 // 绘制食物
	 public static void drawFood(Graphics g) {
	 if (foodPoint == null)
	 return;
	 Point p = Snack.toPos(foodPoint);
	 g.setColor(foodColor);
	 g.fill3DRect(p.x, p.y, GameArea.EDGE, GameArea.EDGE, true);
	 }
	
	 // 新建食物
	 public void nextFood() {
	 Random rand = new Random();
	 while (true) {
	 int x = Math.abs(rand.nextInt()) % GameArea.COL;
	 int y = Math.abs(rand.nextInt()) % GameArea.ROW;
	 Point p = new Point(x, y);
	 if (!Snack.onBody(p)) {
	 foodPoint = new Point(p);
	 return;
	 }
	 }
	 }
	}

	

	

	

	/****************************************************************************************
	* @项目：赫夫曼解码/译码器
	* @作者：Oliver Chu
	* @时间：2014.12
	* @编译环境： Win10 Build9879 预览版 Visual Studio 2013 社区版
	*****************************************************************************************/
	
	#include <iostream>
	#include <String>
	#include <windows.h>
	#include <fstream>
	#include <iomanip>
	using namespace std;
	
	const string FILE_FOLDER_PATH = "D://"; //文件保存工作路径
	const string TO_BE_TREE_CONTENT = "THIS IS MY FAVORITE PROGRAM"; //设定ToBeTree的正文内容
	
	int len = 0; //节点长度
	int str_len; //译码长度
	string codeline; //全局的译码变量
	bool flag = false; //是否存在文件
	
	struct element
	{
	 int weight, lchild, rchild, parent;
	 string code;
	 char data;
	 void clear()
	 {
	 this->weight = 0;
	 this->lchild = 0;
	 this->rchild = 0;
	 this->parent = 0;
	 this->data = '\0';
	 this->code = "";
	 }
	};
	element huffTree[1000];
	
	
	/*********************************/
	
	string ReadString(string);
	void PrintTree();
	void EncodeFile();
	void WriteHuffTree();
	void WriteString(string, string);
	void ToBeTree();
	void Select(element huffTree[], int, int &, int &);
	void HuffmanTree(element huffTree[]);
	void Print();
	void Encoding(element huffTree[], int);
	void Decoding(element huffTree[], int);
	void InScreen();
	bool isFileExit(string);
	void MainScr();
	void WriteTreeFile();
	void InitHuffman();
	void ShowExitScr();
	inline int StringToInt(string);
	
	int main()
	{
	
	 InScreen();
	 while (1)
	 {
	 MainScr();
	 char value = '\0'; //初始化
	 cout << "(?)请输入您的选择> ";
	 LOOP:
	 cin >> value;
	 cin.clear();
	 switch (value)
	 {
	 case 'I':
	 InitHuffman();
	 break;
	 case 'E':
	 Encoding(huffTree, len);
	 system("pause");
	 break;
	 case 'D':
	 Decoding(huffTree, 2 * (len - 1));
	 break;
	 case 'P':
	 Print();
	 break;
	 case 'T':
	 PrintTree();
	 break;
	 case 'F':
	 EncodeFile();
	 break;
	 case 'Q':
	 ShowExitScr();
	
	 default:
	 cout << "\n(!)请输入对应的英文字母> ";
	 goto LOOP;
	 }
	 }
	 cin.get();
	 return 0;
	}
	
	void InScreen()
	{
	 system("color 0c");
	 cout << "\n\n\n\n";
	 cout << " **************************** 欢 迎 使 用 ****************************" << endl;
	 cout << " * *" << endl;
	 cout << " * 赫 夫 曼 编 码 / 译 码 器 *" << endl;
	 cout << " * 2014-12 @ Write by Oliver *" << endl;
	 cout << " *********************************************************************" << endl;
	 cout << endl;
	 Sleep(2000);
	}
	
	inline int StringToInt(string str)
	{
	 return atoi(str.c_str());
	}
	
	void MainScr()
	{
	 system("cls");
	 system("color 0b");
	 cout << " ************************* 赫夫曼编码/译码器 *************************" << endl;
	 cout << " * *" << endl;
	 cout << " * I.初始化(Init) E.编码(Encoding) D.解码(Decoding) Q.退出(Quit) *" << endl;
	 cout << " * *" << endl;
	 cout << " * P.打 印(Print) F.编码文件(EncodingFile) T.打印树(PrintTree) *" << endl;
	 cout << " * *" << endl;
	 cout << " *********************************************************************" << endl;
	 cout << endl;
	 if (!isFileExit("hfmTree.txt"))
	 cout << "\a(!)未找到赫夫曼树文件，请执行初始化操作(!)" << endl << endl;
	 else
	 {
	 if (len == 0)
	 {
	 ifstream fin(FILE_FOLDER_PATH + "hfmTree.txt");
	 string str;
	 while (getline(fin, str))
	 {
	 int j = str.find("@");
	 int k = str.find("#");
	 int f = str.find("*") + 1;
	 huffTree[len].data = str[0];
	 huffTree[len].weight = StringToInt(str.substr(2, j - 2));
	 huffTree[len].code = str.substr(f);
	 huffTree[len].parent = StringToInt(str.substr(j + 1, k - j - 1));
	 len++;
	 }
	 fin.close();
	 HuffmanTree(huffTree);
	 cout << "(!)找到赫夫曼树文件，您可以进行后续操作(!)" << endl << endl;
	 }
	 }
	}
	
	bool isFileExit(string filename)
	{
	 fstream file;
	 string path = FILE_FOLDER_PATH + filename;
	 file.open(path, ios::in);
	 if (!file)
	 return false;
	 else
	 {
	 return true;
	 }
	}
	
	/********** 赫 夫 曼 核 心 代 码 ************/
	void Select(element huffTree[], int m, int &x1, int &x2)
	{
	 int min, min2, i;
	 min = min2 = 1000;
	 for (i = 0; i < m; i++)
	 if (huffTree[i].parent == -1)
	 if (min > huffTree[i].weight)
	 {
	 min2 = min;
	 min = huffTree[i].weight;
	 x2 = x1;
	 x1 = i;
	 }
	 else if (min2 > huffTree[i].weight)
	 {
	 min2 = huffTree[i].weight;
	 x2 = i;
	 }
	}
	
	void HuffmanTree(element huffTree[])
	{
	 int x1, x2;
	 for (int i = 0; i < 2 * len - 1; i++)
	 {
	 huffTree[i].parent = -1;
	 huffTree[i].lchild = -1;
	 huffTree[i].rchild = -1;
	 }
	 for (int k = len; k < 2 * len - 1; k++)
	 {
	 Select(huffTree, k, x1, x2);
	 huffTree[x1].parent = k;
	 huffTree[x2].parent = k;
	 huffTree[k].weight = huffTree[x1].weight + huffTree[x2].weight;
	 huffTree[k].lchild = x1;
	 huffTree[k].rchild = x2;
	 }
	 int i, j = 0;
	 for (i = 2 * (len - 1); i > len - 1; i--)
	 {
	 huffTree[huffTree[i].lchild].code = "0";
	 huffTree[huffTree[i].rchild].code = "1";
	 }
	
	 for (i = 0, j = 0; j < len; j++)
	 {
	 while (huffTree[i].parent != -1)
	 {
	 huffTree[j].code = huffTree[huffTree[i].parent].code + huffTree[j].code;
	 i = huffTree[i].parent;
	 }
	 i = j + 1;
	 }
	 for (int i = 0; i < len; i++)
	 cout << "叶子节点的权值为: " << setw(3) << huffTree[i].weight << " 的编码为: " << huffTree[i].data << " = " << huffTree[i].code << endl;
	 cout << endl;
	
	
	}
	
	void WriteHuffTree()
	{
	 ofstream fout(FILE_FOLDER_PATH + "hfmTree.txt");
	 for (int i = 0; i < len; i++)
	 {
	 fout << huffTree[i].data << '~' << huffTree[i].weight << '@' << huffTree[i].parent << '#' << huffTree[i].lchild << '%' << huffTree[i].rchild << '*' << huffTree[i].code << endl;
	 }
	 fout.close();
	 cout << "(!)赫夫曼树写入完成... 路径为： " + FILE_FOLDER_PATH + "hfmTree.txt" << endl;
	 cout << endl;
	}
	
	void Encoding(element huffTree[], int n)
	{
	 system("cls");
	 system("color 07");
	 cout << "\t<************* 编码文本文件 *************>" << endl << endl;
	 string allstr = "";
	 string filename = "";
	 if (flag == false)
	 {
	 cout << "\n(!)开始编码ToBeTree文件(!)" << endl << endl;
	 ToBeTree();
	 allstr = ReadString("ToBeTree.txt");
	 }
	 else
	 {
	 cout << "\n(!)开始编码自定义文件，请输入文件名> ";
	
	 getline(cin, filename);
	 getline(cin, filename);
	 allstr = ReadString(filename);
	 }
	 int str_len = allstr.length();
	 for (int l = 0; l < str_len; l++)
	 {
	 for (int j = 0; j < len; j++)
	 {
	 if (allstr[l] == huffTree[j].data)
	 {
	 codeline += huffTree[j].code;
	 }
	 }
	 }
	 cout << "\n(!)对其内容进行编码后为： \n" << codeline << endl << endl;
	 if (flag == false)
	 {
	 WriteString(codeline, "CodeFile.txt");
	 }
	 else
	 {
	 WriteString(codeline, "MyTextCodeFile.txt");
	
	 }
	 cout << endl;
	}
	
	string ReadString(string filename)
	{
	 ifstream fin(FILE_FOLDER_PATH + filename);
	 string allstr, str;
	 cout << "(!)该文本内容为:" << endl << endl;
	 while (getline(fin, str))
	 {
	 allstr += str;
	 cout << str << endl;
	 }
	 fin.close();
	 cout << "\n\n(!)读取" + FILE_FOLDER_PATH + filename + " 成功(!)" << endl << endl;
	 return allstr;
	}
	
	void WriteString(string thisdata, string filename)
	{
	 ofstream fout(FILE_FOLDER_PATH + filename);
	 fout << thisdata;
	 fout.close();
	 cout << "(!)" << FILE_FOLDER_PATH + filename << "，写入成功(!)" << endl;
	}
	
	void Print()
	{
	
	 system("cls");
	 system("color 0d");
	 cout << "\t<************* 打印码文件 *************>" << endl << endl;
	 string getcode = "";
	 string filename = "";
	 if (flag == false)
	 {
	 cout << "(!)现在开始打印CodeFile文件，每行50个代码(!)" << endl << endl;
	 getcode = ReadString("CodeFile.txt");
	 }
	 else
	 {
	 cout << "(!)现在开始打印自定义代码文件，每行50个代码，请输入文件名> ";
	 getline(cin, filename);
	 getline(cin, filename);
	 getcode = ReadString(filename);
	 }
	 int t = getcode.length();
	
	 for (int i = 1; i <= t; i++)
	 {
	 cout << getcode[i - 1];
	 if (i % 50 == 0)
	 cout << endl << endl;
	 }
	 cout << endl << endl;
	 if (flag == false)
	 {
	 WriteString(getcode, "CodePrin.txt");
	 }
	 else
	 {
	 WriteString(getcode, "MyTextCodePrin.txt");
	 }
	 cout << endl;
	 system("pause");
	}
	
	void PrintTree() //打印树
	{
	 system("cls");
	 for (int i = 0; i < 2 * len - 1; i++)
	 cout << huffTree[i].data << " " << huffTree[i].weight << " " << huffTree[i].parent << " " << huffTree[i].lchild << " " << huffTree[i].lchild << " " << huffTree[i].code << endl;
	 cout << endl;
	 string pattern[100][100] = { "0" };
	 int num = 0;
	 pattern[0][50] = "*";
	 while (num < len)
	 {
	 int y = 0, x = 50;
	 string nowcode = huffTree[num].code;
	 int nowcode_length = nowcode.length();
	 for (int k = 0; k < nowcode_length; k++)
	 {
	 if (nowcode[k] == '0')
	 {
	 x += 3;
	 y += 4;
	 pattern[y][x] = "*";
	 }
	 if (nowcode[k] == '1')
	 {
	 x -= 2;
	 y += 4;
	 pattern[y][x] = "*";
	 }
	 if (k == nowcode_length - 1)
	 {
	 pattern[y][x] = huffTree[num].data;
	 if (huffTree[num].data == ' ') pattern[y][x] = "@";
	 }
	 }
	 num++;
	 }
	 for (int i = 0; i < 100; i++)
	 {
	 for (int j = 0; j < 100; j++)
	 cout << pattern[i][j] << " ";
	 cout << endl;
	 }
	
	 system("pause");
	}
	
	void Decoding(element huffTree[], int n)
	{
	 system("cls");
	 system("color 09");
	 cout << "\t<************* 解码赫夫曼编码 *************>" << endl << endl;
	 string filename = "";
	 if (flag == false)
	 {
	 cout << "(!)现在解码CodeFile文件(!)" << endl << endl;
	 codeline = ReadString("CodeFile.txt");
	 }
	 else
	 {
	 cout << "(!)现在解码自定义文件，请输入文件名> ";
	 getline(cin, filename);
	 getline(cin, filename);
	 codeline = ReadString(filename);
	 }
	 int mm = codeline.length();
	 int j = n, j1;
	 int i = 0;
	 string transcodeline = "";
	 while (huffTree[j].lchild != -1 && i < mm)
	 {
	 if (codeline[i] == '1') j = huffTree[j].rchild;
	 else j = huffTree[j].lchild;
	 i++;
	 if (huffTree[j].lchild == -1)
	 {
	 transcodeline += huffTree[j].data;
	 j1 = j;
	 j = n;
	 }
	 else j1 = j;
	 }
	 cout << "(!)解码成功！解码内容为： " + transcodeline << "(!)" << endl << endl;
	 if (flag == false)
	 {
	 WriteString(transcodeline, "TextFile.txt");
	 }
	 else
	 {
	 WriteString(transcodeline, "MyTextFile.txt");
	 }
	 cout << endl;
	 system("pause");
	}
	
	void ToBeTree() //将正文写入文件ToBeTree中
	{
	 ofstream outfile;
	 outfile.open(FILE_FOLDER_PATH + "ToBeTree.txt", ios::out);
	 outfile << TO_BE_TREE_CONTENT;
	 outfile.close();
	}
	
	/*****************************/
	
	void InitHuffman()
	{
	 using namespace std;
	 system("cls");
	 cout << "\t<************* 初始化赫夫曼树 *************>" << endl << endl;
	 cout << "(!)需要编码的字符串> ";
	 string input;
	 getline(cin, input);
	 getline(cin, input);//为何输入两个才能读取
	 cout << "\n(!)您输入的字符串是：" << input << endl;
	 len = input.length();
	 for (int i = 0; i < len; i++)
	 {
	 cout << "\n(!)请输入第" << setw(3) << i + 1 << "个字符" << setw(2) << input[i] << "的权值>";
	 cin >> huffTree[i].weight;
	 cin.clear();
	 huffTree[i].data = input[i];
	 cout << endl;
	 }
	 HuffmanTree(huffTree);
	 WriteHuffTree();
	 system("pause");
	}
	
	void ShowExitScr()
	{
	 system("cls");
	 system("color 0e");
	 cout << "\t\t@@@@@@@@@@@@@@@@@@@@@@@@@" << endl;
	 cout << "\t\t@ 代码：Oliver Chu @\n\t\t@ 地点：成都工业学院 @\n\t\t@ 课题：哈夫曼解码/译码 @\n";
	 cout << "\t\t@@@@@@@@@@@@@@@@@@@@@@@@@" << endl;
	 cout << "\n\t\t ! 谢谢使用 Good-bye !" << endl;
	 Sleep(4000);
	 exit(0);
	}
	
	void EncodeFile()
	{
	 system("cls");
	 string filename = "";
	 cout << "(?)请输入工作路径下的文件名> ";
	 getline(cin, filename);
	 getline(cin, filename);
	 string str = ReadString(filename);
	 int getstrlen = str.length();
	 int STR_LEN = getstrlen;
	 int count = 1;
	 struct
	 {
	 char ch;
	 int freq;
	 } STR[1000];
	 int tag = 0;
	 while (getstrlen != 0)
	 {
	 count = 1;
	 getstrlen = str.length();
	 STR[tag].ch = str[0];
	 for (int j = 1; j < getstrlen; j++)
	 {
	 // cout << str[0] << " " << str[j] << "j=" << j << " " << getstrlen << endl;
	 if (str[0] == str[j])
	 {
	 count++;
	 str.erase(j, 1);
	 j--;
	 getstrlen--;
	 }
	 }
	 STR[tag].freq = count;
	 str.erase(0, 1);
	 tag++;
	 }
	 for (int i = 0; i < tag - 1; i++)
	 {
	 cout << STR[i].ch << " " << (int)((STR[i].freq / (double)(STR_LEN)) * 100) << endl;
	 STR[i].freq = (int)((STR[i].freq / (double)(STR_LEN)) * 100);
	 } //为频率
	
	 for (int i = 0; i < 2 * (len - 1); i++)
	 huffTree[i].clear();
	 len = tag - 1;
	 for (int i = 0; i < len; i++)
	 {
	 huffTree[i].data = STR[i].ch;
	 huffTree[i].weight = STR[i].freq;
	 }
	 HuffmanTree(huffTree);
	 WriteHuffTree();
	 flag = true;
	 cout << endl;
	 system("pause");
	}
试试其它关键字
　哈弗曼　　哈弗曼编码　
同语言下
可能有用的
OliverChu贡献的其它代码(4)