标签：roman loading 删除 parent time 构造 退出 树根 sizeof
一、实验目的
1、了解文件的概念。
2、掌握线性链表的插入、删除等算法。
3、掌握Huffman树的概念及构造方法。
4、掌握二叉树的存储结构及遍历算法。
5、利用Huffman树及Huffman编码，掌握实现文件压缩的一般原理。
二、设备与环境
微型计算机、Windows系列操作系统 、Visual C++6.0软件等。
三、实验内容
根据ASCII码文件中各ASCII字符出现的频率情况创建Huffman树，再将各字符对应的哈夫曼编码写入文件中，实现文件压缩。
四、实验结果及分析
1、概要设计
（1）构造哈夫曼树的哈夫曼算法
构造哈夫曼树步骤：
根据给定的n个权值{w1,w2……wn},构造n棵树只有根结点的二叉树，起权值为wj。
在森林中选取两棵根结点权值最小和次小的树作为左右子树，构造一棵新的二叉树，置新的二叉树根结点权值为其左右子树根结点权值之和。
在森林中删除这两棵树，同时将新得到的二叉树加入森林中。
重复上述两步，直到只含一棵树为止，这棵树即为哈夫曼树。
算法结构如图：
（2）哈夫曼编码：数据通信用的二进制编码
思想：根据字符出现的频率编码，使电文总长最短
编码：根据字符出现的频率构造哈夫曼树，然后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列。
（3）文本编码
读取存放在文本中的字母，一对一的进行编译，将对应的编码存放在另一个文本中。
2、详细设计
（1）压缩过程图解
（2）详细代码
1 #include 2 #include string.h>
3 #include 4 #include 5
6 /*哈夫曼树结构定义*/
7 struct head
8 {
9 unsigned char b; /*定义一个字符*/
10 long count; /*频率数据*/
11 long parent,lch,rch; /*创建哈夫曼树*/
12 char bits[256]; /*哈夫曼结点*/
13 }header[512],tmp;
14
15
16 /*压缩文件*/
17 void yasuo()
18 {
19 char filename[255],outputfile[255],buf[512];
20 unsigned char c;
21 char wenjianming[255];
22 long i,j,m,n,f;
23 long min1,pt1,flength;
24 FILE *ifp,*ofp;
25 printf("请输入文件地址及文件名：");
26 gets(filename);
27 ifp = fopen(filename,"rb"); /*打开源文件并读取*/
28 while(ifp==NULL)
29 {
30 printf("打开文件时出错！\n");
31 printf("请重新输入文件地址及文件名：");
32 gets(filename);
33 ifp=fopen(filename,"rb");
34 }
35 printf("请输入压缩后的文件地址和文件名及后缀：");
36 gets(wenjianming);
37 ofp = fopen(wenjianming,"wb"); /*创建并打开目的文件*/
38
39 while(ofp==NULL)
40 {
41 printf("请重新输入压缩后的文件地址和文件名及后缀：");
42 ofp=fopen(wenjianming,"wb");
43 }
44 flength = 0;
45
46 /*读取ifp文件*/
47 while(!feof(ifp))
48 {
49 fread(&c,1,1,ifp); /*按位读取文件*/
50 header[c].count++; /*记录文件的字符总数*/
51 flength++;
52 }
53 flength = -1;
54 header[c].count = -1; /*读取文件结束*/
55 /*构造哈弗曼树，初始结点的设置*/
56 for(i=0;i512;i++)
57 {
58 if(header[i].count != 0)
59 header[i].b = (unsigned char)i;
60 else
61 header[i].b = 0;
62 header[i].parent = -1;
63 header[i].lch = header[i].rch = -1;
64 }
65 /*按结点出现的次数排序*/
66 for(i=0;i256;i++)
67 {
68 for(j=i+1;j256;j++)
69 {
70 if(header[i].count header[j].count)
71 {
72 tmp=header[i];
73 header[i] = header[j];
74 header[j] = tmp;
75 }
76 }
77 }
78 /*统计不同字符的数量*/
79 for(i=0;i256;i++)
80 if(header[i].count==0)
81 break;
82 n=i;
83 m=2*n-1;
84 for(i=n;i)
85 {
86 min1=999999999;
87 for(j=0;j)
88 {
89 if(header[j].parent!=-1)
90 continue;
91 if(min1>header[j].count)
92 {
93 pt1=j;
94 min1=header[j].count;
95 continue;
96 }
97 }
98 header[i].count=header[pt1].count;
99 header[pt1].parent=i;
100 header[i].lch=pt1;
101 min1=999999999;
102 for(j=0;j)
103 {
104 if(header[j].parent!=-1)
105 continue;
106 if(min1>header[j].count)
107 {
108 pt1=j;
109 min1=header[j].count;
110 continue;
111 }
112 }
113 header[i].count+=header[pt1].count;
114 header[i].rch=pt1;
115 header[pt1].parent=i;
116 }
117 /*构造哈夫曼树，设置字符编码*/
118 for(i=0;i)
119 {
120 f = i;
121 header[i].bits[0] = 0;
122 while(header[f].parent != -1)
123 {
124 j = f;
125 f = header[f].parent;
126 if(header[f].lch==j)
127 {
128 j = strlen(header[i].bits);
129 memmove(header[i].bits+1,header[i].bits,j+1);
130 header[i].bits[0]=‘0‘;
131 }
132 else
133 {
134 j=strlen(header[i].bits);
135 memmove(header[i].bits+1,header[i].bits,j+1);
136 header[i].bits[0]=‘1‘;
137 }
138 }
139 } /*哈弗曼构造结束*/
140
141 //读取源文件中的每一个字符，按照设置好的编码替换文件中的字符
142 fseek(ifp,0,SEEK_SET); /*把文件指针指向文件的开头*/
143 fwrite(&flength,sizeof(int),1,ofp); /*把哈弗曼代码写入ofp文件*/
144 fseek(ofp,8,SEEK_SET); /*以8位二进制数为单位读取*/
145 buf[0] = 0;
146 f = 0;
147 pt1 = 8;
148 while(!feof(ifp))
149 {
150 c=fgetc(ifp); //从流中读取一个字符，并增加文件指针的位置
151 f++;
152 for(i=0;i)
153 {
154 if(c==header[i].b)
155 break;
156 }
157 strcat(buf,header[i].bits); //把header[i].bits所指字符串添加到buf结尾处
158 j = strlen(buf); //计算字符串buf的长度
159 c = 0;
160 while(j>=8) /*按八位二进制数转化成十进制ASCII码写入文件一次进行压缩*/
161 {
162 for(i=0;i8;i++)
163 {
164 if(buf[i]==‘1‘) c=(c1)|1;
165 else c=c1;
166 }
167 fwrite(&c,1,1,ofp);
168 pt1++;
169 strcpy(buf,buf+8);
170 j=strlen(buf);
171 }
172 if(f==flength)
173 break;
174 }
175 if(j > 0) /*剩余字符数量少于8个*/
176 {
177 strcat(buf,"00000000");
178 for(i=0;i8;i++)
179 {
180 if(buf[i]==‘1‘) c=(c1)|1;
181 else c = c 1; /*对不足的位数补0*/
182 }
183 fwrite(&c,1,1,ofp);
184 pt1++;
185 }
186 //将编码信息写入存储文件
187 fseek(ofp,4,SEEK_SET); /*fseek 用于二进制方式打开的文件,移动文件读写指针位置.第一个是文件流,第3个是指针零点位置,第2个是把指针移动到的地点. */
188 fwrite(&pt1,sizeof(long),1,ofp); /*是要输出数据的地址,每次写入的位数,数据项的个数，目标文件地址*/
189 fseek(ofp,pt1,SEEK_SET);
190 fwrite(&n,sizeof(long),1,ofp);
191 for(i=0;i)
192 {
193 fwrite(&(header[i].b),1,1,ofp);
194 c=strlen(header[i].bits);
195 fwrite(&c,1,1,ofp);
196 j=strlen(header[i].bits);
197 if(j % 8!=0) /*按八位读取，位数不满8位时，对该位补0*/
198 {
199 for(f=j%8;f8;f++)
200 strcat(header[i].bits,"0");
201 }
202 while(header[i].bits[0]!=0)
203 {
204 c=0;
205 for(j=0;j8;j++)
206 {
207 if(header[i].bits[j]==‘1‘) c=(c1)|1;
208 else c = c 1;
209 }
210 strcpy(header[i].bits,header[i].bits+8); /*把从header[i].bits+8地址开始且含有NULL结束符的字符串赋值到以header[i].bits开始的地址空间 */
211 fwrite(&c,1,1,ofp);
212 }
213 }
214 fclose(ifp);
215 fclose(ofp);
216 printf("压缩成功\n");
217
218 }
219 /*主函数*/
220 void main()
221 {
222 printf("输入a开始压缩\n");
223 printf("输入b结束压缩\n");
224 while(1)
225 {
226 char c;
227 c=getch();
228 if(c==‘a‘)
229 yasuo();
230 else
231 {
232 if(c==‘b‘)
233 return;
234 }
235 }
236 }
3、测试结果及分析
（1）运行截图如下
键入a,输入文件地址及文件名和压缩后的文件地址及文件名，在出现“压缩成功”后键入b，退出代码运行。
（2）压缩结果展示
a.压缩前(只有一个文件)
打开后文件内容
b.压缩后（出现两个文件）
打开后文件内容
五、实验总结
本学期要学习课程很多，留给综合实验的时间并不是特别多。通过本次的实验，我又重新拿出了上学期的《C语言程序设计》，重新复习了一下一些关于文件读取、写入等函数。对于本次的实验内容，不仅仅是对本学期《数据结构与算法分析》的一个学习总结，更是对上学期C语言的复习回顾。
本次实验代码调试了很久，还是会出现一些C语言语法上的小错误，还有一部分内容参考了网上的代码。除了技术上的错误，在本次实验中我觉得还是要保持一个良好的心态去解决错误，在我的代码出现多次报错时，要能沉得住气去纠错，忌浮躁。
总之要学习的东西还有很多，每完成一次实验对我自己的能力来说都是一个很好的提升过程。作为大数据专业的学生，数学虽说是基础，但能够更好解决实际问题还是要靠计算机程序代码，学会一门语言不仅仅限于书本，更是要能够熟练地在实际中应用。学习是一个逐渐进步的过程，每次实验内容不仅仅是一次实验，更是一次对自己知识掌握的检验，更是对自己在面对新的挑战前的磨练。
数据结构与算法分析综合实验：用哈夫曼编码实现文件压缩
标签：roman loading 删除 parent time 构造 退出 树根 sizeof
原文地址：https://www.cnblogs.com/SLXii/p/14331487.html