API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Apr 7th, 2019
471
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 14.00 KB | None | 0 0
raw download clone embed print report
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. //对位进行相关操作
  6. //这里的unsigned char对于位是0或1，对于偏移是0到7
  7. #pragma region Bit
  8.  
  9. //设byte为10101100（对应offset为76543210），即172，读取offset为4和5的位
  10. //
  11. //offset=4
  12. //00010000 1<<offset
  13. //10101100 byte
  14. //00000000 byte&(1<<offset)
  15. //00000000 (byte&(1<<offset))>>offset
  16. //
  17. //offset=5
  18. //00100000 1<<offset
  19. //10101100 byte
  20. //00100000 byte&(1<<offset)
  21. //00000001 (byte&(1<<offset))>>offset
  22. unsigned char ReadBit(unsigned char byte, unsigned char offset) {
  23.     return (byte & (1 << offset)) >> offset;
  24. }
  25.  
  26. //设byte为10101100（对应offset为76543210），即172，将offset为4的位write为0和1
  27. //
  28. //offset=4 write=0
  29. //00000000 write<<offset
  30. //10101100 byte
  31. //10101100 byte|(write<<offset)
  32. //
  33. //offset=4 write=1
  34. //00010000 write<<offset
  35. //10101100 byte
  36. //10111100 byte|(write<<offset)
  37. void WriteBit(unsigned char *byte, unsigned char offset, unsigned char write) {
  38.     *byte |= write << offset;
  39. }
  40.  
  41. #pragma endregion
  42.  
  43. #pragma region Huffman
  44.  
  45. //动态分配数组存储H树
  46. typedef struct {
  47.     unsigned int weight; //字符的权
  48.     unsigned int parent; //双亲的地址
  49.     unsigned int lchild; //左子树的地址
  50.     unsigned int rchild; //右子树的地址
  51. } HTNode, *HuffmanTree;
  52.  
  53. //动态分配数组存储H树编码表
  54. typedef char **HuffmanCode;
  55.  
  56. //在HT[1..range]的范围中找到parent=0，权最小的两项，下标分别为s1和s2，且s1<s2
  57. void Select(HuffmanTree HT, unsigned int range, unsigned int *s1, unsigned int *s2) {
  58.     unsigned int v1 = 4294967295, v2 = 4294967295; //unsigned int的最大值
  59.     *s1 = 0;
  60.     *s2 = 0;
  61.     for (unsigned int i = 1; i <= range; i++) {
  62.         if (HT[i].parent) {
  63.             continue;
  64.         }
  65.         if (HT[i].weight < v1) {
  66.             v2 = v1;
  67.             v1 = HT[i].weight;
  68.             *s2 = *s1;
  69.             *s1 = i;
  70.         } else if (HT[i].weight < v2) {
  71.             v2 = HT[i].weight;
  72.             *s2 = i;
  73.         }
  74.     }
  75.     //保证s1<s2
  76.     v1 = *s1;
  77.     v2 = *s2;
  78.     *s1 = (v1 < v2) ? v1 : v2;
  79.     *s2 = (v1 > v2) ? v1 : v2;
  80. }
  81.  
  82. //构造H树
  83. void InitHuffmanTree(HuffmanTree *HT, unsigned int *w, unsigned int n) {
  84.     unsigned int m = 2 * n - 1; //H树一共有2n-1个节点
  85.     *HT = malloc((m + 1) * sizeof(HTNode)); //留一个0号结点表示指向空树，相当于二叉树中的NULL
  86.  
  87.     //为每个字符构建只有根结点，没有左右子树的二叉树
  88.     (*HT)[0].weight = 0;
  89.     (*HT)[0].parent = 0;
  90.     (*HT)[0].lchild = 0;
  91.     (*HT)[0].rchild = 0;
  92.     HTNode *p = *HT + 1; //从1号结点开始
  93.     unsigned int i = 1;
  94.     while (i <= n) {
  95.         (*p).weight = *w;
  96.         (*p).parent = 0;
  97.         (*p).lchild = 0;
  98.         (*p).rchild = 0;
  99.         i++;
  100.         p++;
  101.         w++;
  102.     }
  103.     //剩下的树是空树
  104.     while (i <= m) {
  105.         (*p).weight = 0;
  106.         (*p).parent = 0;
  107.         (*p).lchild = 0;
  108.         (*p).rchild = 0;
  109.         i++;
  110.         p++;
  111.     }
  112.  
  113.     //开始生成H树
  114.     unsigned int s1, s2;
  115.     for (i = n + 1; i <= m; i++) {
  116.         Select(*HT, i - 1, &s1, &s2);
  117.         (*HT)[s1].parent = i;
  118.         (*HT)[s2].parent = i;
  119.         (*HT)[i].lchild = s1;
  120.         (*HT)[i].rchild = s2;
  121.         (*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
  122.     }
  123. }
  124.  
  125. //根据H树求每个字符的编码
  126. void InitHuffmanCode(HuffmanCode *HC, HuffmanTree HT, unsigned int n) {
  127.     *HC = malloc((n + 1) * sizeof(char*)); //HC相当于一个由字符数组组成的数组，里面的元素类型是char*
  128.     char *cd = malloc(n * sizeof(char)); //求编码的工作区，每个字符的编码长度一定不会超过n
  129.     cd[n - 1] = '\0'; //字符数组以\0结尾
  130.     unsigned int start; //表示一个编码从cd的哪一项开始
  131.     unsigned int c, f; //c指当前指向的树，f是c的双亲
  132.  
  133.     //对每个字符逆向求编码
  134.     for (unsigned int i = 1; i <= n; i++) {
  135.         start = n - 1;
  136.         //求编码从叶子结点开始，到c指向根结点为止，此时f为0
  137.         for (c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent) {
  138.             start--; //向前移一位
  139.             if (HT[f].lchild == c) {
  140.                 cd[start] = '0'; //左子树的路径用0表示
  141.             }
  142.             else {
  143.                 cd[start] = '1'; //右子树的路径用1表示
  144.             }
  145.         }
  146.         //从cd复制到HC
  147.         (*HC)[i] = malloc((n - start) * sizeof(char));
  148.         strcpy_s((*HC)[i], n - start + 1, &cd[start]);
  149.     }
  150.     free(cd);
  151. }
  152.  
  153. //HT存放构造的H树
  154. //HC存放构造的编码
  155. //w指向存放了每个字符的权的数组
  156. //n是字符数量
  157. //把建树和编码的部分分开了
  158. void HuffmanCoding(HuffmanTree *HT, HuffmanCode *HC, unsigned int *w, unsigned int n) {
  159.     //只有一个或者没有字符还有什么编码的必要吗？
  160.     if (n <= 1) {
  161.         return;
  162.     }
  163.  
  164.     InitHuffmanTree(HT, w, n);
  165.     InitHuffmanCode(HC, *HT, n);
  166. }
  167.  
  168. #pragma endregion
  169.  
  170. //以表的形式输出对n个字符进行编码的HT
  171. void PrintHuffmanTree(HuffmanTree HT, unsigned int n) {
  172.     for (unsigned int i = 0; i <= 2 * n - 1; i++) {
  173.         printf("%3d w:%3d p:%3d lc:%3d rc:%3d\n", i, HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild);
  174.     }
  175. }
  176.  
  177. int main() {
  178.     unsigned int Select = 1;
  179.  
  180.     HuffmanTree HT = NULL;
  181.     HuffmanCode HC = NULL;
  182.     unsigned int CharSetSize; //字符集大小
  183.     char *CharSet = NULL; //字符
  184.     unsigned int *CharWeight = NULL; //每个字符对应的权
  185.     FILE *fpHuff = NULL, *fpText = NULL, *fpCode = NULL;
  186.     unsigned long long FileSize, CodeSize; //进行编码时源文件的大小和编码的位数
  187.     unsigned int Status; //0表示正常，1表示出错
  188.     unsigned int Index; //指向的编码表索引
  189.     unsigned char Offset, Byte, Read; //读写二进制位用
  190.     unsigned char *pCode = NULL; //读取编码表用
  191.    
  192.     while (Select) {
  193.         puts("\n-- Huffman树编码演示 --");
  194.         puts("1 - 建立并保存Huffman树到Huffman.bin");
  195.         puts("2 - 从TextFile.txt读取文件，以Huffman.bin的数据作为Huffman树进行编码");
  196.         puts("3 - 从CodeFile.bin读取文件，以Huffman.bin的数据作为Huffman树进行解码");
  197.         puts("0 - 退出");
  198.         puts("输入选项：");
  199.         scanf_s("%d", &Select);
  200.         switch (Select) {
  201.             case 1:
  202.                 puts("输入字符集大小：");
  203.                 scanf_s("%d", &CharSetSize);
  204.                 CharSet = malloc(CharSetSize * sizeof(char));
  205.                 CharWeight = malloc(CharSetSize * sizeof(unsigned int));
  206.                 for (unsigned int i = 0; i < CharSetSize; i++) {
  207.                     printf("输入第%d个字符：\n", i + 1);
  208.                     scanf_s(" %c", &CharSet[i], 1);
  209.                     printf("输入第%d个字符的权：\n", i + 1);
  210.                     scanf_s("%d", &CharWeight[i]);
  211.                 }
  212.                 HuffmanCoding(&HT, &HC, CharWeight, CharSetSize);
  213.                 puts("\n生成的Huffman树：");
  214.                 PrintHuffmanTree(HT, CharSetSize);
  215.                 puts("\n字符对应的编码：");
  216.                 for (unsigned int i = 0; i < CharSetSize; i++) {
  217.                     printf("%c %s\n", CharSet[i], HC[i + 1]);
  218.                 }
  219.  
  220.                 //保存H树
  221.                 fopen_s(&fpHuff, "Huffman.bin", "wb");
  222.                 fwrite(&CharSetSize, sizeof(unsigned int), 1, fpHuff);
  223.                 fwrite(CharSet, sizeof(char), CharSetSize, fpHuff);
  224.                 fwrite(CharWeight, sizeof(unsigned int), CharSetSize, fpHuff);
  225.                 fwrite(HT, sizeof(HTNode), 2 * CharSetSize, fpHuff);
  226.                 fclose(fpHuff);
  227.  
  228.                 puts("\n已保存Huffman树。");
  229.                 break;
  230.             case 2:
  231.                 //读取H树
  232.                 if (CharSet) {
  233.                     free(CharSet);
  234.                 }
  235.                 if (CharWeight) {
  236.                     free(CharWeight);
  237.                 }
  238.                 if (HT) {
  239.                     free(HT);
  240.                 }
  241.                 if (HC) {
  242.                     free(HC);
  243.                 }
  244.                 fopen_s(&fpHuff, "Huffman.bin", "rb");
  245.                 fread(&CharSetSize, sizeof(unsigned int), 1, fpHuff);
  246.                 CharSet = malloc(CharSetSize * sizeof(char));
  247.                 CharWeight = malloc(CharSetSize * sizeof(unsigned int));
  248.                 HT = malloc(2 * CharSetSize * sizeof(HTNode));
  249.                 fread(CharSet, sizeof(char), CharSetSize, fpHuff);
  250.                 fread(CharWeight, sizeof(unsigned int), CharSetSize, fpHuff);
  251.                 fread(HT, sizeof(HTNode), 2 * CharSetSize, fpHuff);
  252.                 fclose(fpHuff);
  253.  
  254.                 //根据H树建立编码表
  255.                 InitHuffmanCode(&HC, HT, CharSetSize);
  256.  
  257.                 //读取TextFile
  258.                 fopen_s(&fpCode, "CodeFile.bin", "wb");
  259.                 fopen_s(&fpText, "TextFile.txt", "rb");
  260.                 fseek(fpText, 0L, SEEK_END);
  261.                 FileSize = ftell(fpText);
  262.                 fseek(fpText, 0L, SEEK_SET);
  263.  
  264.                 CodeSize = 0;
  265.                 Offset = 7;
  266.                 Byte = 0;
  267.                 //对TextFile中的每个字符进行编码
  268.                 for (unsigned long long i = 0; i < FileSize; i++) {
  269.                     Status = 1;
  270.                     fread(&Read, sizeof(char), 1, fpText);
  271.                     //从编码表中查找对应的编码
  272.                     for (unsigned int j = 0; j < CharSetSize; j++) {
  273.                         if (CharSet[j] == Read) {
  274.                             pCode = HC[j + 1];
  275.                             while (*pCode) {
  276.                                 CodeSize++;
  277.                                 WriteBit(&Byte, Offset, *pCode - '0');
  278.                                 if (Offset) {
  279.                                     //字节没有写满，offset-1
  280.                                     Offset--;
  281.                                 } else {
  282.                                     //字节写满了就写入文件，然后清空字节
  283.                                     Offset = 7;
  284.                                     fwrite(&Byte, sizeof(unsigned char), 1, fpCode);
  285.                                     Byte = 0;
  286.                                 }
  287.                                 pCode++;
  288.                             }
  289.                             Status = 0;
  290.                             break;
  291.                         }
  292.                     }
  293.                     if (Status) {
  294.                         printf("提示：已忽略没有在字符集中出现的字符%c\n", Read);
  295.                     }
  296.                 }
  297.                 //最后一个字节没有写满也要写入，没有写满的位都是0
  298.                 if (Offset != 7) {
  299.                     fwrite(&Byte, sizeof(unsigned char), 1, fpCode);
  300.                 }
  301.                 //在文件最后写入编码位数
  302.                 fwrite(&CodeSize, sizeof(unsigned long long), 1, fpCode);
  303.  
  304.                 fclose(fpCode);
  305.                 fclose(fpText);
  306.  
  307.                 puts("\n编码完成。");            
  308.                 break;
  309.             case 3:
  310.                 //读取H树
  311.                 if (CharSet) {
  312.                     free(CharSet);
  313.                 }
  314.                 if (CharWeight) {
  315.                     free(CharWeight);
  316.                 }
  317.                 if (HT) {
  318.                     free(HT);
  319.                 }
  320.                 if (HC) {
  321.                     free(HC);
  322.                 }
  323.                 fopen_s(&fpHuff, "Huffman.bin", "rb");
  324.                 fread(&CharSetSize, sizeof(unsigned int), 1, fpHuff);
  325.                 CharSet = malloc(CharSetSize * sizeof(char));
  326.                 CharWeight = malloc(CharSetSize * sizeof(unsigned int));
  327.                 HT = malloc(2 * CharSetSize * sizeof(HTNode));
  328.                 fread(CharSet, sizeof(char), CharSetSize, fpHuff);
  329.                 fread(CharWeight, sizeof(unsigned int), CharSetSize, fpHuff);
  330.                 fread(HT, sizeof(HTNode), 2 * CharSetSize, fpHuff);
  331.                 fclose(fpHuff);
  332.  
  333.                 //根据H树建立编码表
  334.                 InitHuffmanCode(&HC, HT, CharSetSize);
  335.  
  336.                 //读取CodeFile
  337.                 Index = 2 * CharSetSize - 1;
  338.                 fopen_s(&fpCode, "CodeFile.bin", "rb");
  339.                 fopen_s(&fpText, "TextFile.txt", "wb");
  340.                 //读取编码位数
  341.                 fseek(fpCode, -1L * (long)sizeof(unsigned long long), SEEK_END);
  342.                 fread(&CodeSize, sizeof(unsigned long long), 1, fpCode);
  343.                 fseek(fpCode, 0L, SEEK_SET);
  344.  
  345.                 Offset = 7;
  346.                 fread(&Byte, sizeof(unsigned char), 1, fpCode); //先读取一个字节
  347.                 //对CodeFile中的每个位进行读取
  348.                 for (unsigned long long i = 0; i < CodeSize; i++) {
  349.                     Read = ReadBit(Byte, Offset);
  350.                     if (Read) {
  351.                         //读到1就移向右子树
  352.                         Index = HT[Index].rchild;
  353.                     } else {
  354.                         //读到0就移向右子树
  355.                         Index = HT[Index].lchild;
  356.                     }
  357.                     //移到叶子结点就写入字符，同时移回根结点
  358.                     if (!HT[Index].lchild && !HT[Index].rchild) {
  359.                         fwrite(&CharSet[Index - 1], sizeof(char), 1, fpText);
  360.                         Index = 2 * CharSetSize - 1;
  361.                     }
  362.                     if (Offset) {
  363.                         //字节没有读完，offset-1
  364.                         Offset--;
  365.                     } else {
  366.                         //字节读完了就读下一个字节
  367.                         Offset = 7;
  368.                         fread(&Byte, sizeof(unsigned char), 1, fpCode);
  369.                     }
  370.                 }
  371.                
  372.                 fclose(fpCode);
  373.                 fclose(fpText);
  374.  
  375.                 puts("\n解码完成。");
  376.                 break;
  377.         }
  378.     }
  379.  
  380.     return 0;
  381. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!