哈夫曼编码译码
发布日期:2022-03-08 21:50:46
浏览次数:4
分类:技术文章
本文共 8716 字,大约阅读时间需要 29 分钟。
在这里插入代码片#include#include //为exit()提供原型#include //哈夫曼树结点的结构typedef struct { char ch; //该字符域用于存放节点的关键字 int weight; int parent, lchild, rchild;}HTNode, * HuffmanTree; //动态分配数组存储哈夫曼树typedef char** HuffmanCode; //动态分配数组存储哈夫曼编码表void Menu(); //显示菜单void HuffmanCoding(HuffmanTree& HT, char* character, int* w, int n); //建立哈夫曼树void select(HuffmanTree HT, int j, int* x, int* y); //从已建好的哈夫曼树中选择parent为0,weight最小的两个结点void Init();void Coding(); //编码void Decoding(); //译码void Print_code(); //打印译码好的代码void Print_tree(); //打印哈夫曼树int Read_tree(HuffmanTree&); //从文件中读入哈夫曼树void find(HuffmanTree& HT, char* code, char* text, int i, int m); //译码时根据01字符串寻找相应叶子节点的递归算法void Convert_tree(unsigned char T[100][100], int s, int* i, int j); //将内存中的哈夫曼树转换成凹凸表形式的赫夫曼树HuffmanTree HT; //全局变量int n = 0; //全局变量,存放赫夫曼树叶子结点的数目int main(){ char select; while (1) { Menu(); scanf("%c", &select); switch (select) //选择操作,根据不同的序号选择不同的操作 { case '1':Init(); break; case '2':Coding(); break; case '3':Decoding(); break; case '4':Print_code(); break; case '5':Print_tree(); break; case '0':exit(1); default:printf("Input error!\n"); } getchar(); } return 0;}void Menu() //操作选择界面{ printf(" -----------------------------------------------------\n"); printf(" -- 请选择操作 --\n"); printf(" -----------------------------------------------------\n"); printf(" \n"); printf(" ---------------------1初始化哈夫曼树 ---------------\n"); printf(" ---------------------2编码 ---------------\n"); printf(" ---------------------3译码 ---------------\n"); printf(" ---------------------4打印代码文件 ---------------\n"); printf(" ---------------------5打印哈夫曼树 ---------------\n"); printf(" ---------------------0退出 ---------------\n"); printf(" -----------------------------------------------------\n");}//初始化函数,输入n个字符及其对应的权值,根据权值建立哈夫曼树,并将其存于文件hfmtree中void Init(){ FILE* fp; int i, n, w[52]; //数组存放字符的权值 char character[52]; //存放n个字符 printf("\n输入字符个数 n:"); scanf("%d", &n); //输入字符集大小 printf("输入%d个字符及其对应的权值:\n", n); for (i = 0; i < n; i++) { char b = getchar(); scanf("%c", &character[i]); scanf("%d", &w[i]); //输入n个字符和对应的权值 } HuffmanCoding(HT, character, w, n); //建立赫夫曼树 if ((fp = fopen("D:\\hfmtree.txt", "w")) == NULL) printf("Open file hfmtree.txt error!\n"); for (i = 1; i <= 2 * n - 1; i++) { if (fwrite(&HT[i], sizeof(HTNode), 1, fp) != 1) //将建立的赫夫曼树存入文件hfmtree.txt中 printf("File write error!\n"); } printf("\n赫夫曼树建立成功,并已存于文件hfmtree.txt中\n"); fclose(fp);}//构造哈夫曼树的算法void HuffmanCoding(HuffmanTree& HT, char* character, int* w, int n){ //w存放n个字符的权值(均>0),构造哈夫曼树HT int m, i, x, y; HuffmanTree p; if (n <= 1) return; m = 2 * n - 1; HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode)); for (p = HT + 1, i = 1; i <= n; ++i, ++p, ++character, ++w) { p->ch = *character; p->weight = *w; p->parent = 0; p->lchild = 0; p->rchild = 0; } for (; i <= m; ++i, ++p) { p->ch = 0; p->weight = 0; p->parent = 0; p->lchild = 0; p->rchild = 0; } for (i = n + 1; i <= m; ++i) { select(HT, i - 1, &x, &y); HT[x].parent = i; HT[y].parent = i; HT[i].lchild = x; HT[i].rchild = y; HT[i].weight = HT[x].weight + HT[y].weight; }}//从HT[1]到HT[j]中选择parent为0,weight最小的两个结点,用x和y返回其序号void select(HuffmanTree HT, int j, int* x, int* y){ int i; //查找weight最小的结点 for (i = 1; i <= j; i++) if (HT[i].parent == 0) { *x = i; break; } for (; i <= j; i++) if ((HT[i].parent == 0) && (HT[i].weight < HT[*x].weight)) *x = i; HT[*x].parent = 1; //查找weight次小的结点 for (i = 1; i <= j; i++) if (HT[i].parent == 0) { *y = i; break; } for (; i <= j; i++) if ((HT[i].parent == 0) && (i != *x) && (HT[i].weight < HT[*y].weight)) *y = i;}//对文件tobetrans中的正文进行编码,然后将结果存入文件codefile中void Coding(){ FILE* fp, * fw; int i, f, c, start; char* cd; HuffmanCode HC; if (n == 0) n = Read_tree(HT);//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数 //求赫夫曼树中各叶子节点的字符对应的的编码,并存于HC指向的空间中 { HC = (HuffmanCode)malloc((n + 1) * sizeof(char*)); 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)); strcpy(HC[i], &cd[start]); } free(cd); } if ((fp = fopen("D:\\tobetrans.txt", "rb")) == NULL) printf("Open file tobetrans.txt error!\n"); if ((fw = fopen("D:\\codefile.txt", "wb+")) == NULL) printf("Open file codefile.txt error!\n"); char temp; fscanf(fp, "%c", &temp); //从文件读入第一个字符 while (!feof(fp)) { for (i = 1; i <= n; i++) if (HT[i].ch == temp) break; //在赫夫曼树中查找字符所在的位置 for (int r = 0; HC[i][r] != '\0'; r++) //将字符对应的编码存入文件 fputc(HC[i][r], fw); fscanf(fp, "%c", &temp); //从文件读入下一个字符 } fclose(fw); fclose(fp); printf("\n已将文件hfmtree.txt成功编码,并已存入codefile.txt中!\n\n");}//将文件codefile中的代码进行译码,结果存入文件textfile中void Decoding(){ FILE* fp, * fw; int m, i; char* code, * text, * p; if (n == 0) n = Read_tree(HT);//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数 if ((fp = fopen("D:\\codefile.txt", "rb")) == NULL) printf("Open file codefile.txt error!\n"); if ((fw = fopen("D:\\textfile.txt", "wb+")) == NULL) printf("Open file textfile.txt error!\n"); code = (char*)malloc(sizeof(char)); fscanf(fp, "%c", code); //从文件读入一个字符 for (i = 1; !feof(fp); i++) { code = (char*)realloc(code, (i + 1) * sizeof(char)); //增加空间 fscanf(fp, "%c", &code[i]); //从文件读入下一个字符 } code[i - 1] = '\0'; // codefile.txt文件中的字符已全部读入,存放在code数组中 text = (char*)malloc(100 * sizeof(char)); p = text; m = 2 * n - 1; if (*code == '0') find(HT, code, text, HT[m].lchild, m); //从根节点的左子树去找 else find(HT, code, text, HT[m].rchild, m); //从根节点的右子树去找 for (i = 0; p[i] != '\0'; i++) //把译码好的字符存入文件textfile.txt中 fputc(p[i], fw); fclose(fp); fclose(fw); printf("\n已将codefile.txt文件成功译码,并已存入textfile.txt文件!\n\n");}//将文件codefi1e以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码文件写入文件codeprint中。void Print_code(){ FILE* fp, * fw; char temp; int i; if ((fp = fopen("D:\\codefile.txt", "rb")) == NULL) printf("Open file codefile.txt error!\n"); if ((fw = fopen("D:\\codeprint.txt", "wb+")) == NULL) printf("Open file codeprint.txt error!\n"); printf("\n文件codefi1e显示如下:\n"); fscanf(fp, "%c", &temp); //从文件读入一个字符 for (i = 1; !feof(fp); i++) { printf("%c", temp); if (i % 50 == 0) printf("\n"); fputc(temp, fw); //将该字符存入文件codeprint.txt中 fscanf(fp, "%c", &temp); //从文件读入一个字符 } printf("\n\n已将此字符形式的编码写入文件codeprint.txt中!\n\n"); fclose(fp); fclose(fw);}//将已在内存中的哈夫曼树显示在屏幕上,并将此字符形式的哈夫曼树写入文件treeprint中。void Print_tree(){ unsigned char T[100][100]; int i, j, m = 0; FILE* fp; if (n == 0) n = Read_tree(HT); //从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数 Convert_tree(T, 0, &m, 2 * n - 1); //将内存中的赫夫曼树转换成凹凸表形式的树,存于数组T中 if ((fp = fopen("D:\\treeprint.txt", "wb+")) == NULL) printf("Open file treeprint.txt error!\n"); printf("\n打印已建好的赫夫曼树:\n"); for (i = 1; i <= 2 * n - 1; i++) { for (j = 0; T[i][j] != 0; j++) { if (T[i][j] == ' ') { printf(" "); fputc(T[i][j], fp); } else { printf("%d", T[i][j]); fprintf(fp, "%d\n", T[i][j]); } } printf("\n"); } fclose(fp); printf("\n已将该字符形式的哈夫曼树写入文件treeprint.txt中!\n\n");}//从文件hfmtree.txt中读入赫夫曼树,返回叶子节点数int Read_tree(HuffmanTree& HT){ FILE* fp; int i, n; HT = (HuffmanTree)malloc(sizeof(HTNode)); if ((fp = fopen("D:\\hfmtree.txt", "r")) == NULL) printf("Open file hfmtree.txt error!\n"); for (i = 1; !feof(fp); i++) { HT = (HuffmanTree)realloc(HT, (i + 1) * sizeof(HTNode)); //增加空间 fread(&HT[i], sizeof(HTNode), 1, fp); //读入一个节点信息 } fclose(fp); n = (i - 1) / 2; return n;}//译码时根据01字符串寻找相应叶子节点的递归算法void find(HuffmanTree& HT, char* code, char* text, int i, int m){ if (*code != '\0') //若译码未结束 { code++; if (HT[i].lchild == 0 && HT[i].rchild == 0) //若找到叶子节点 { *text = HT[i].ch; //将叶子节点的字符存入text中 text++; if ((*code == '0')) find(HT, code, text, HT[m].lchild, m); //从根节点的左子树找 else find(HT, code, text, HT[m].rchild, m); //从根节点的右子树找 } else //如果不是叶子节点 if (*code == '0') find(HT, code, text, HT[i].lchild, m); //从该节点的左子树去找 else find(HT, code, text, HT[i].rchild, m); //从该节点的右子树去找 } else *text = '\0'; //译码结束}//将文件中的赫夫曼树转换成凹凸表形式的赫夫曼树打印出来void Convert_tree(unsigned char T[100][100], int s, int* i, int j){ int k, l; l = ++(*i); for (k = 0; k < s; k++) T[l][k] = ' '; T[l][k] = HT[j].weight; if (HT[j].lchild) Convert_tree(T, s + 1, i, HT[j].lchild); if (HT[j].rchild) Convert_tree(T, s + 1, i, HT[j].rchild); T[l][++k] = '\0';}
转载地址:https://blog.csdn.net/m0_55673081/article/details/121988565 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
初次前来,多多关照!
[***.217.46.12]2024年03月27日 19时22分37秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
浅论各种调试接口(SWD、JTAG、Jlink、Ulink、STlink)的区别
2019-04-25
C++深度解析 内联函数分析 内联inline和宏#define(5)
2019-04-25
C++深度解析 函数重载分析(7)
2019-04-25
报表的 SQL 注入风险是什么意思?如何防范?
2019-04-25
JS-part3.3-复杂数据类型之 数组和排序方法
2019-04-25
求和与平均值
2019-04-25
if选择结构
2019-04-25
switch多选择结构
2019-04-25
计算1+2+3+...+100
2019-04-25
用while或for循环输出1-1000之间能被5整除的数,并且每行输出3个
2019-04-25
学习的总结
2019-04-25
学习的总结
2019-04-25
66天街欢抢节 北京长安天街 6.5-6.6
2019-04-25
武田中国创新挑战赛重磅启动,诚邀初创企业共赴数字医疗之途
2019-04-25
九巨龙集团安全大检查行动,践行“客户满意工程”牢筑安全防线!
2019-04-25
最好吃的8款粽子,看看有没有你家乡的!
2019-04-25