【问题描述】
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成 本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道)，每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。
【基本要求】
一个完整的系统应具有以下功能：
(1)I：初始化(Initialization)。从终端读入字符集大小n , 以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。
(2)E：编码(Encoding)。利用已建好的哈夫曼树(如不在内存，则从文件hfmTree中读人)，对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。
(3)D: 译码(Decoding)。利用已建好的哈夫曼树将文件 CodeFile 中的代码进行译码，结果存入文件TextFile中。
(4)P：打印代码文件(Print)。将文件CodeFile以紧凑格式显示在终端上，每行 50 个代码。同时将此字符形式的编码文件写入文件 CodePrint中。
(5)T:打印哈夫曼树（Tree printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。
【测试数据】
用下表给出的字符集和频度的实际统计数据建立哈夫曼树 , 并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。
| 字符 | A | B | C | D | E | F | G | H | I | J | K | L | M | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 频度 | 186 | 64 | 13 | 22 | 32 | 103 | 21 | 15 | 47 | 57 | 1 | 5 | 32 | 20 |
| 字符 | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | |
| 频度 | 57 | 63 | 15 | 1 | 48 | 51 | 80 | 23 | 8 | 18 | 1 | 16 | 1 |
头文件huffman.h
#pragma once #include#include #include #include #include #include #include using namespace std; #define MAXLEN 100 char str[20]; int h = 0; typedef struct { int weight; //存放各个点的权值 int parent, LChild, RChild;//指向双亲，孩子结点的指针 char key; }HTNode; typedef HTNode HuffmanTree[MAXLEN]; void PrintHuffmanCode(HuffmanTree ht, int n); void CrtHuffmanCode(HuffmanTree ht, int i, int j); void hide() //隐藏光标函数实现 { HANDLE hout = GetStdHandle(STD_OUTPUT_HANDLE); CONSOLE_CURSOR_INFO cor_info = { 1,0 }; SetConsoleCursorInfo(hout, &cor_info); } void gotoxy(int x, int y) { COORD coord; coord.X = x; coord.Y = y; SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), coord); } void InitHuffmanTree(HuffmanTree ht, int n)//对结构体进行初始化 { int i; for (i = 1; i <= 2 * n - 1; i++) { ht[i].weight = 0; ht[i].parent = 0; ht[i].RChild = 0; ht[i].LChild = 0; ht[i].key = '#'; } printf("n"); } void InputWeight(HuffmanTree ht, int n)//输入函数 { int w, i;//w表示权值 char k;//k表示获取的字符 for (i = 1; i <= n; i++) { printf("请输入第%d个字符：", i); scanf("%c", &k); getchar(); ht[i].key = k; printf("请输入第%d个字符的权值：", i); scanf("%d", &w); getchar(); ht[i].weight = w; printf("n"); } } void Select(HuffmanTree ht, int n, int* s1, int* s2) { int i, min; for (i = 1; i <= n; i++) { if (ht[i].parent == 0) { min = i; break; } } for (i = 1; i <= n; i++) { if (ht[i].parent == 0) { if (ht[i].weight < ht[min].weight) { min = i; } } } *s1 = min; for (i = 1; i <= n; i++) { if (ht[i].parent == 0 && i != (*s1)) { min = i; break; } } for (i = 1; i <= n; i++) { if (ht[i].parent == 0 && i != (*s1)) { if (ht[i].weight < ht[min].weight) { min = i; } } } *s2 = min; } //构造哈夫曼树ht void CrtHuffmanTree(HuffmanTree ht, int n) { int m, i, s1, s2; m = 2 * n - 1; InitHuffmanTree(ht, n); InputWeight(ht, n); printf("n -----------------------------------------------------n"); printf(" *************** 哈 夫 曼 树 结 构 为 ****************n"); printf(" -----------------------------------------------------n"); printf(" tt权重t左孩子权值t右孩子权值tn"); for (i = n + 1; i <= m; i++) //创建非叶子节点，建哈夫曼树 {//在ht[0]——ht[i]内选择两个parent为0 //且weight最小的点分别赋值给s1,s2 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; printf(" tt%dt %dtt%dtn", ht[i].weight, ht[s1].weight, ht[s2].weight); } printf(" -----------------------------------------------------nn"); PrintHuffmanCode(ht, n); FILE* fp; fp = fopen("hfmTree.txt", "w"); for (i = 1; i <= n; ++i) { h = 0; memset(str, ' ', sizeof(str)); CrtHuffmanCode(ht, i, 0); fprintf(fp, "(%c %s)n", ht[i].key, str); } fclose(fp); cout << "赫夫曼树已经创建完毕，并且已经放入hfmTree.txt文件中!" << endl; gotoxy(80, 25); printf("按任意键返回上级菜单"); hide(); //隐藏光标 char ch = _getch(); system("cls"); } void CrtHuffmanCode(HuffmanTree ht, int i, int j) { int a, b; a = i; b = j = ht[i].parent; if (ht[j].parent != 0) { i = j; CrtHuffmanCode(ht, i, j); } if (ht[b].LChild == a) { printf("0"); str[h] = '0'; h++; } else { str[h] = '1'; h++; printf("1"); } } void PrintHuffmanCode(HuffmanTree ht, int n) { int i, j, a; printf("n -----------------------------------------------------n"); printf(" **************** 哈 夫 曼 编 码 为 ******************n"); printf(" -----------------------------------------------------n"); for (i = 1; i <= n; i++) { j = 0; printf("n tt %c ttt", ht[i].key); CrtHuffmanCode(ht, i, j); printf("n"); } printf(" -----------------------------------------------------nn"); } void encoding(HuffmanTree ht, int n)//对用户输入的电文进行编码 { FILE* fp1, * fp2; char r[1000];//用来存储输入的字符串 int i, j; printf("nn请输入要编码的字符:"); gets_s(r); fp1 = fopen("ToBeTran.txt", "w"); fprintf(fp1, "%s", r); fclose(fp1); int a = strlen(r); fp2 = fopen("CodeFile.txt", "w"); printf("编译结果为:"); for (j = 0; r[j] != ' '; j++) { for (i = 1; i <= n; i++) { if (r[j] == ht[i].key) { h = 0; memset(str, ' ', sizeof(str)); CrtHuffmanCode(ht, i, j); fprintf(fp2, "%s", str); } } } fclose(fp2); printf("n编码完毕，并且已经存入CodeFile.txt文件！n"); printf("按任意键返回上级菜单"); hide(); //隐藏光标 char ch = _getch(); system("cls"); } void decoding(HuffmanTree ht, int n)//对输入的密码进行译码 { ifstream input_file; ofstream output_file; input_file.open("CodeFile.txt"); if (!input_file) { cout << "can't open file!" << endl; exit(0); } char r[100]; int i, j, len; j = 2 * n - 1; //初始节点从根节点开始 input_file >> r; input_file.close(); output_file.open("Textfile.txt"); if (!output_file) { cout << "can't open file!" << endl; exit(0); } len = strlen(r); printf("译码的结果是："); for (i = 0; i < len; i++) { if (r[i] == '0') { j = ht[j].LChild; if (ht[j].LChild == 0) { printf("%c", ht[j].key); output_file << ht[j].key; j = 2 * n - 1; } } else if (r[i] == '1') { j = ht[j].RChild; if (ht[j].RChild == 0) { printf("%c", ht[j].key); output_file << ht[j].key; j = 2 * n - 1; } } } output_file.close(); printf("n译码结果已存入Textfile.txt中n"); printf("按任意键返回上级菜单"); hide(); //隐藏光标 char ch = _getch(); system("cls"); } void print() { char a[500]; FILE* fp,*fp1; fp = fopen("CodeFile.txt", "r"); fgets(a, 500, fp); printf("打印代码文件:n" ); int num = strlen(a); for (int j = 0; j < num; j++) { printf("%c", a[j]); if ((j + 1) % 50 == 0) printf("n"); } fclose(fp); fp1 = fopen("CodePrint.txt", "w"); for (int k = 0; k < num; k++) { fprintf(fp1, "%c", a[k]); if ((k + 1) % 50 == 0) { fprintf(fp1, "n"); } } printf( "n该字符形式已存入CodePrint.txt中n"); fclose(fp1); printf("按任意键返回上级菜单"); hide(); //隐藏光标 char ch = _getch(); system("cls"); } //非叶子结点用权值表示，叶子结点用字符表示 void PrintTree(HuffmanTree ht, int n, int type, int level) { //int m, i, s1, s2; int i; if (NULL == n) return; PrintTree(ht,ht[n].RChild, 2, level + 1); switch (type) { case 0: printf("%2dn", ht[n].weight); break; case 1: for (i = 0; i < level; i++) printf("t"); printf("\n"); for (i = 0; i < level; i++) printf("t"); printf(" %2dn", ht[n].weight); break; case 2: for (i = 0; i < level; i++) printf("t"); printf(" %2dn", ht[n].weight); for (i = 0; i < level; i++) printf("t"); printf("/n"); break; } PrintTree(ht,ht[n].LChild, 1, level + 1); } int menu() { gotoxy(40, 12); //定位光标位置 printf("欢迎来到哈夫曼编译/编码器"); gotoxy(43, 14); printf("1.初始化"); gotoxy(43, 16); printf("2.编码"); gotoxy(43, 18); printf("3.译码"); gotoxy(43, 20); printf("4.印代码文件"); gotoxy(43, 22); printf("5.印哈夫曼树"); gotoxy(43, 28); printf("其他任意键退出游戏"); hide(); //隐藏光标 char ch; int result = 0; ch = _getch(); //接收用户输入的菜单选项 switch (ch) { //根据选项设置返回结果值 case '1': result = 1; break; case '2': result = 2; break; case '3': result = 3; break; case '4': result = 4; break; case '5': result = 5; break; } system("cls"); //调用系统命令cls完成清屏操作 return result; }
源文件main.cpp
#includeint main(void) { HuffmanTree ht; int n=0; int flag=1; int result; while (flag) { result=menu(); switch (result) { case 1: printf("初始化界面"); gotoxy(20, 15); printf("请输入字符个数："); scanf("%d", &n); getchar(); printf("n"); CrtHuffmanTree(ht, n); break; case 2: printf("编码界面"); gotoxy(20, 15); encoding(ht,n); break; case 3: printf("译码界面"); gotoxy(20, 15); decoding(ht, n); break; case 4: printf("印代码界面"); gotoxy(20, 15); print(); break; case 5: { printf("印哈夫曼树界面"); int i, min; min = 1; for (i = 1; i<=(2 * n - 1); i++) { if (ht[i].parent == 0) { min = i; break; } } gotoxy(10, 15); PrintTree(ht, min, 0, 0); printf("按任意键返回上级菜单"); hide(); //隐藏光标 char ch = _getch(); system("cls"); } break; case 0: flag = 0; break; } } system("pause"); return 0; }
