2022年C语言哈夫曼编码、译码器 2.pdf

《2022年C语言哈夫曼编码、译码器 2.pdf》由会员分享，可在线阅读，更多相关《2022年C语言哈夫曼编码、译码器 2.pdf（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、#include #include #include #include #include /typedef int TElemType; const int UINT_MAX = 1000; typedef struct int weight; int parent, lchild, rchild; HTNode, *HuffmanTree; typedef char *HuffmanCode; /- 全局变量 - HuffmanTree HT; HuffmanCode HC; int *w, i, j, n; char *z; int flag = 0; int numb = 0; / -

2、求赫夫曼编码- int min(HuffmanTree t, int i) / 函数 void select() 调用int j, flag; int k = UINT_MAX; / 取 k 为不小于可能的值for (j = 1; j = i; j+) if (tj.weight s2) j = s1; s1 = s2; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 14 页 - - - - - - - - - s2 = j; / - 算法 6.12- void Huf

3、fmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n) / w 存放 n 个字符的权值 (均0),构造赫夫曼树HT,并求出 n 个字符的赫夫曼编码HC int m, i, s1, s2, start; /unsigned c,f; int 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

4、+ 1, i = 1; i weight = *w; p-parent = 0; p-lchild = 0; p-rchild = 0; for (; i parent = 0; for (i = n + 1; i = m; +i) / 建赫夫曼树 / 在 HT1i-1 中选择 parent 为 0 且 weight 最小的两个结点,其序号分别为s1 和 s2 select(HT, i - 1, s1, s2); HTs1.parent = HTs2.parent = i; HTi.lchild = s1; HTi.rchild = s2; HTi.weight = HTs1.weight +

5、 HTs2.weight; / 从叶子到根逆向求每个字符的赫夫曼编码HC = (HuffmanCode)malloc(n + 1) *sizeof(char*); / 分配 n 个字符编码的头指针向量(0不用 ) cd = (char*)malloc(n *sizeof(char); / 分配求编码的工作空间cdn - 1 = 0; / 编码结束符for (i = 1; i = n; i+) / 逐个字符求赫夫曼编码名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 14 页

6、 - - - - - - - - - start = n - 1; / 编码结束符位置for (c = i, f = HTi.parent; f != 0; c = f, f = HTf.parent) / 从叶子到根逆向求编码if (HTf.lchild = c) cd-start = 0; else cd-start = 1; HCi = (char*)malloc(n - start) *sizeof(char); / 为第 i 个字符编码分配空间strcpy(HCi, &cdstart); / 从 cd 复制编码 (串)到 HC free(cd); / 释放工作空间 /- 初始化赫夫曼

7、链表- void Initialization() flag = 1; int num; int num2; cout 下面初始化赫夫曼链表 endl num; n = num; w = (int*)malloc(n *sizeof(int); z = (char*)malloc(n *sizeof(char); cout n 请依次输入 n 个字符 (字符型 )n 注意:必须以回车结束： endl; char base2; for (i = 0; i n; i+) cout 第 i + 1 个字符 : endl; gets(base); *(z + i) = *base; for (i =

8、0; i = n - 1; i+) cout setw(6) *(z + i); cout n 请依次输入 n 个权值 (n 注意 :必须以回车结束)： endl; for (i = 0; i = n - 1; i+) cout endl 第 i + 1 num2; *(w + i) = num2; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 14 页 - - - - - - - - - HuffmanCoding(HT, HC, w, n); /-打印编码 - co

9、ut 字符对应的编码为: endl; for (i = 1; i = n; i+) /cout 字符 *(z+i-1)的编码 ; puts(HCi); /-将赫夫曼编码写入文件- cout 下面将赫夫曼编码写入文件 endl . endl; FILE *htmTree; char r = , 0 ; if (htmTree = fopen(htmTree.txt, w) = NULL) cout can not open file endl; return ; fputs(z, htmTree); for (i = 0; i n + 1; i+) fprintf(htmTree, %6d, *

10、(w + i); fputs(r, htmTree); for (i = 1; i = n; i+) fputs(HCi, htmTree); fputs(r, htmTree); fclose(htmTree); cout 已将字符与对应编码写入根目录下文件htmTree.txt 中 endl endl; /-获取报文并写入文件- void InputCode() /cout 请输入你想要编码的字符endl; FILE *tobetran; char str100; if (tobetran = fopen(tobetran.txt, w) = NULL) cout 不能打开文件 endl;

11、 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 14 页 - - - - - - - - - return ; cout 请输入你想要编码的字符 endl; gets(str); fputs(str, tobetran); cout 获取报文成功 endl; fclose(tobetran); /-编码函数 - void Encoding() cout 下面对目录下文件tobetran.txt 中的字符进行编码 endl; FILE *tobetran, *codefi

12、le; if (tobetran = fopen(tobetran.txt, rb) = NULL) cout 不能打开文件 endl; if (codefile = fopen(codefile.txt, wb) = NULL) cout 不能打开文件 endl; char *tran; i = 99; tran = (char*)malloc(100 *sizeof(char); while (i = 99) if (fgets(tran, 100, tobetran) = NULL) cout 不能打开文件 endl; break; for (i = 0; *(tran + i) !=

13、0; i+) for (j = 0; j n) cout 字符错误，无法编码! endl; break; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 14 页 - - - - - - - - - cout 编码工作完成 endl 编码写入目录下的codefile.txt 中 endl endl; fclose(tobetran); fclose(codefile); free(tran); /- 译码函数 - void Decoding() cout 下面对根目录下文

14、件codefile.txt 中的字符进行译码 endl; FILE *codef, *txtfile; if (txtfile = fopen(Textfile.txt, w) = NULL) cout 不能打开文件 endl; /txtfile=fopen(Textfile.txt,w); if (codef = fopen(codefile.txt, r) = NULL) cout 不能打开文件 endl; /codef=fopen(codefile.txt,r); char *work, *work2, i2; int i4 = 0, i, i3; unsigned long lengt

15、h = 10000; work = (char*)malloc(length *sizeof(char); fgets(work, length, codef); work2 = (char*)malloc(length *sizeof(char); i3 = 2 * n - 1; for (i = 0; *(work + i - 1) != 0; i+) i2 = *(work + i); if (HTi3.lchild = 0) *(work2 + i4) = *(z + i3 - 1); i4+; i3 = 2 * n - 1; i-; else if (i2 = 0) i3 = HTi

16、3.lchild; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 14 页 - - - - - - - - - else if (i2 = 1) i3 = HTi3.rchild; *(work2 + i4) = 0; fputs(work2, txtfile); cout 译码完成 endl 内容写入根目录下的文件txtfile.txt 中 endl endl; cout work2; free(work); free(work2); fclose(txtfile);

17、 fclose(codef); /-打印赫夫曼树的函数- void coprint(HuffmanTree start, HuffmanTree HT) if (start != HT) FILE *TreePrint; if (TreePrint = fopen(TreePrint.txt, a) = NULL) cout 创建文件失败 rchild, HT); cout setw(5 *numb) weight weight); coprint(HT + start-lchild, HT); numb-; fclose(TreePrint); void Tree_printing(Huff

18、manTree HT, int w) HuffmanTree p; p = HT + w; cout 下面打印赫夫曼树 endl; coprint(p, HT); cout 打印工作结束 endl; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 14 页 - - - - - - - - - /-主函数 - void main() char choice; while (choice != q) cout 赫夫曼编码解码系统 endl; cout 1. 要初始化赫夫曼链表

19、请输入i endl; cout 2. 要编码请输入e endl; cout 3. 要译码请输入d endl; cout 4. 要打印编码请输入p endl; cout 5. 要打印赫夫曼树请输入t endl; cout 6. 要离开请输入q endl; / if(flag=0)coutn请先初始化赫夫曼链表,输入i choice; switch (choice) case i: Initialization(); break; case w: InputCode(); break; case e: Encoding(); break; case d: Decoding(); break; ca

20、se t: Tree_printing(HT, 2 *n - 1); break; case q: default: cout input error endl; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 14 页 - - - - - - - - - free(z); free(w); free(HT); 运行结果：赫夫曼编码解码系统1.要初始化赫夫曼链表请输入i 2.要编码请输入e 3.要译码请输入d 4.要打印编码请输入p 5.要打印赫夫曼树请输入t 6.要离开

21、请输入q i 下面初始化赫夫曼链表数请输入结点的个n：8 请依次输入8 个字符 (字符型 ) 注意 :必须以回车结束：第 1 个字符 : a 第 2 个字符 : b 第 3 个字符 : c 第 4 个字符 : d 第 5 个字符 : e 第 6 个字符 : f 第 7 个字符 : g 第 8 个字符 : h a b c d e f g h 请依次输入8 个权值 ( 注意 :必须以回车结束)：第 1 个字符的权值:5 第 2 个字符的权值:29 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - -

22、- 第 9 页，共 14 页 - - - - - - - - - 第 3 个字符的权值:7 第 4 个字符的权值:8 第 5 个字符的权值:14 第 6 个字符的权值:23 第 7 个字符的权值:3 第 8 个字符的权值:11 字符对应的编码为: 0110 10 1110 1111 110 00 0111 010 下面将赫夫曼编码写入文件. 已将字符与对应编码写入根目录下文件htmTree.txt 中赫夫曼编码解码系统1.要初始化赫夫曼链表请输入i 2.要编码请输入e 3.要译码请输入d 4.要打印编码请输入p 5.要打印赫夫曼树请输入t 6.要离开请输入q i 下面初始化赫夫曼链表数请输入结

23、点的个n：27 请依次输入27 个字符 (字符型 ) 注意 :必须以回车结束：第 1 个字符 : 第 2 个字符 : a 第 3 个字符 : b 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 14 页 - - - - - - - - - 第 4 个字符 : c 第 5 个字符 : d 第 6 个字符 : e 第 7 个字符 : f 第 8 个字符 : g 第 9 个字符 : h 第 10 个字符 : i 第 11 个字符 : j 第 12 个字符 : k 第 13 个

24、字符 : l 第 14 个字符 : m 第 15 个字符 : n 第 16 个字符 : o 第 17 个字符 : p 第 18 个字符 : q 第 19 个字符 : r 第 20 个字符 : s 第 21 个字符 : t 第 22 个字符 : u 第 23 个字符 : v 第 24 个字符 : w 第 25 个字符 : x 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 14 页 - - - - - - - - - 第 26 个字符 : y 第 27 个字符 : z a

25、 b c d e f g m n o p q r s t z 请依次输入27 个权值 ( 注意 :必须以回车结束)：第 1 个字符的权值:186 第 2 个字符的权值:64 第 3 个字符的权值:13 第 4 个字符的权值:22 第 5 个字符的权值:32 第 6 个字符的权值:103 第 7 个字符的权值:21 第 8 个字符的权值:15 第 9 个字符的权值:47 第 10 个字符的权值:57 第 11 个字符的权值:1 第 12 个字符的权值:5 第 13 个字符的权值:32 第 14 个字符的权值:20 第 15 个字符的权值:57 第 16 个字符的权值:63 第 17 个字符的权值

26、:15 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 14 页 - - - - - - - - - 第 18 个字符的权值:1 第 19 个字符的权值 :48 第 20 个字符的权值 :51 第 21 个字符的权值 :80 第 22 个字符的权值 :23 第 23 个字符的权值 :8 第 24 个字符的权值 :18 第 25 个字符的权值 :1 第 26 个字符的权值 :16 第 27 个字符的权值 :1 字符对应的编码为: 110 1010 100100 00010

27、 10110 010 111110 100101 0000 0110 1111011100 11110110 10111 111111 0111 1000 100110 1111011101 0010 0011 1110 00011 1111010 111100 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 14 页 - - - - - - - - - 1111011110 100111 1111011111 下面将赫夫曼编码写入文件. 已将字符与对应编码写入根目录下文件htmTree.txt 中名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 14 页 - - - - - - - - -