1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 //////////////////////////////////////////////////////////////////////////////
5 /*定义赫夫曼树结点的结构体变量，存放结点的权值、字符、双亲、坐孩子和右孩子*/
6 typedef struct{
7 int weight;//权值
8 char ch; //增加一个域用于存放该节点的字符
9 int parent, lchild, rchild;
10 }HTNode, *HuffmanTree;
11 typedef char **HuffmanCode; //指向赫夫曼编码的指针
12 //////////////////////////////////////////////////////////////////////////////
13 /*本程序用到的函数原型*/
14 void welcome(); //打印操作选择界面
15 void HuffmanCoding(HuffmanTree &, char *, int *, int);//建立赫夫曼树的算法
16 void select(HuffmanTree HT, int j, int *s1, int *s2); //从目前已建好的赫夫曼树中选择parent为0且weight最小的两个结点
17 void Init(); //输入n个字符及其对应的权值，根据权值建立哈夫曼树
18 void Coding(); //编码
19 void Decoding(); //译码
20 void Print_code(); //打印译码好的代码文件
21 void Print_tree(); //以凹凸表形式打印哈夫曼树
22 int Read_tree(HuffmanTree &HT); //从文件中读入赫夫曼树
23 void find(HuffmanTree &HT, char *code, char *text, int i, int m);//译码时根据01字符串寻找相应叶子节点的递归算法
24 void Convert_tree(unsigned char T[100][100], int s, int *i, int j);//将内存中的赫夫曼树转换成凹凸表形式的赫夫曼树
25 HuffmanTree HT; //全局变量，指向存放赫夫曼树的存储空间
26 int n = 0; //全局变量，存放赫夫曼树叶子结点的数目
27 int main()
28 {
29 char select;
30 while (1)
31 {
32 welcome();
33 scanf("%c", &select);
34 switch (select)
35 {
36 case 'i':
37 case 'I':Init(); break;
38 case 'c':
39 case 'C':Coding(); break;
40 case 'd':
41 case 'D':Decoding(); break;
42 case 'p':
43 case 'P':Print_code(); break;
44 case 't':
45 case 'T':Print_tree(); break;
46 case 'e':
47 case 'E':exit(1);
48 default:printf("Input error!
");
49 }
50 getchar();
51 }
52 return 0;
53 }
54 void welcome() //打印操作选择界面
55 {
56 printf("*-----------------------------------------------------*
");
57 printf("| What do you want to do? |
");
58 printf("|-----------------------------------------------------|
");
59 printf("| |
");
60 printf("| I--------------------------Init the Huffman tree. |
");
61 printf("| C--------------------------Code your file. |
");
62 printf("| D--------------------------Decode the code. |
");
63 printf("| P--------------------------Print the codefile. |
");
64 printf("| T--------------------------Print the Huffman tree. |
");
65 printf("| |
");
66 printf("*-----------------------------------------------------*
");
67 }
68 //////////////////////////////////////////////////////////////////////////////////////
69 /*初始化函数，输入n个字符及其对应的权值，根据权值建立哈夫曼树，并将其存于文件hfmtree中*/
70 void Init()
71 {
72 FILE *fp;
73 int i, n, w[52]; //w数组存放n个字符的权值
74 char character[52]; //存放n个字符
75 printf("
输入字符个数 n:");
76 scanf("%d", &n); //输入字符集大小
77 printf("输入%d个字符及其对应的权值:
", n);
78 for (i = 0; i < n; i++)
79 {
80 char b = getchar();//?
81 scanf("%c", &character[i]);
82 scanf("%d", &w[i]); //输入n个字符和对应的权值
83 }
84 HuffmanCoding(HT, character, w, n); //建立赫夫曼树
85 if ((fp = fopen("hfmtree.txt", "w")) == NULL)
86 printf("Open file hfmtree.txt error!
");
87 for (i = 1; i <= 2 * n - 1; i++)
88 {
89 if (fwrite(&HT[i], sizeof(HTNode), 1, fp) != 1) //将建立的赫夫曼树存入文件hfmtree.txt中
90 printf("File write error!
");
91 }
92 printf("
建立赫夫曼树成功，已将其存于文件hfmtree.txt中
");
93 fclose(fp);
94 }
95 ///////////////////////////////////////////////////////////////////////////////////
96 //////建立赫夫曼树的算法///////////////////////////////////////////////////////////
97 void HuffmanCoding(HuffmanTree &HT, char *character, int *w, int n)
98 {
99 int m, i, s1, s2;
100 HuffmanTree p;
101 if (n <= 1)
102 return;
103 m = 2 * n - 1;
104 HT = (HuffmanTree)malloc((m + 1)*sizeof(HTNode));
105 for (p = HT + 1, i = 1; i <= n; ++i, ++p, ++character, ++w)
106 {
107 p->ch = *character;
108 p->weight = *w;
109 p->parent = 0;
110 p->lchild = 0;
111 p->rchild = 0;
112 }
113 for (; i <= m; ++i, ++p)
114 {
115 p->ch = 0;
116 p->weight = 0;
117 p->parent = 0;
118 p->lchild = 0;
119 p->rchild = 0;
120 }
121 for (i = n + 1; i <= m; ++i)
122 {
123 select(HT, i - 1, &s1, &s2);
124 HT[s1].parent = i;
125 HT[s2].parent = i;
126 HT[i].lchild = s1;
127 HT[i].rchild = s2;
128 HT[i].weight = HT[s1].weight + HT[s2].weight;
129 }
130 }
131 ///////////////////////////////////////////////////////////////////////////////
132 /*从HT[1]到HT[j]中选择parent为0且weight最小的两个结点，用s1和s2返回其序号*/
133 void select(HuffmanTree HT, int j, int *s1, int *s2)
134 {
135 int i;
136 //找weight最小的结点
137 for (i = 1; i <= j; i++)
138 if (HT[i].parent == 0)
139 {
140 *s1 = i;
141 break;
142 }
143 for (; i <= j; i++)
144 if ((HT[i].parent == 0) && (HT[i].weight < HT[*s1].weight))
145 *s1 = i;
146 HT[*s1].parent = 1;
147 //找weight次小的结点
148 for (i = 1; i <= j; i++)
149 if (HT[i].parent == 0)
150 {
151 *s2 = i; break;
152 }
153 for (; i <= j; i++)
154 if ((HT[i].parent == 0) && (i != *s1) && (HT[i].weight < HT[*s2].weight))
155 *s2 = i;
156 }
157 ///////////////////////////////////////////////////////////////////////////////
158 /*对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中*/
159 void Coding()
160 {
161 FILE *fp, *fw;
162 int i, f, c, start;
163 char *cd;
164 HuffmanCode HC;
165 if (n == 0)
166 n = Read_tree(HT);//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数
167 /////以下程序段求赫夫曼树中各叶子节点的字符对应的的编码，并存于HC指向的空间中
168 {
169 HC = (HuffmanCode)malloc((n + 1)*sizeof(char*));
170 cd = (char *)malloc(n*sizeof(char));
171 cd[n - 1] = '
