用哈夫曼编码实现文件压缩实验报告

1、evaluation of scientific development. Nature security type-nature security is to maintenance people of health value for target, through strengthening security based management, and risk management, and equipment management and technology supervision, ensure production in the people, and real, and sy

2、stem, and system, elements security reliable, and harmony unified, full control various against factors, achieved thought no slack, and management no empty document, and equipment no hidden, and system no blocked, and unit zero non-stopped. Quality and efficiency-quality benefit is to adhere to the

3、enterprise survival, profit and development business truth, adhere to the all activity is economic activity, all costs can be controlled, money should not be wasted management philosophy, management analysis, to improve management quality, improve cost control capacity and market competitiveness. In

4、novation of science and technology-science and technology innovation is to play the role of science and technology as the primary productive force, active use of new technologies, new materials, new processes, new equipment, increase investment in science and technology, strengthening scientific and

5、 technological training, speeding up transforming scientific and technological achievements, forming a number of proprietary technology, enhancing core competitiveness. Resource-saving-the-resources saving enterprise was to reduce coal consumption, water consumption, electricity at the core, enhance

6、 the operation of lean management to realize low consumption, high efficiency, reduce production costs. Second is to strengthen the business, financial, material, information and the optimization of organization and management, saving the internal transaction costs. Harmonious development of harmoni

7、ous development-is to construct a foreign environment for development. XING refers to the internal security firm and internal management of the internal management measures are effective, harmonious. Foreign currency means Enterprise coordinating development of homeopathy, well, get along with the n

8、eighbors better. (B) XX 2013 five enterprises building intrinsic safety power company goals are: unplanned outage 0 times. Class of disorders 0, 0 is equivalent forced outage rate. No personal injury accident, material and equipment accidents do not occur, no fire, no environmental pollution acciden

9、t. Enterprise integrated to achieve zero cases of violation, zero accidents, zero. Quality goal is: when generating capacity 7.5 billion-kilowatt, sales of over 7.11 billion kWh, total profits of 306.6 million Yuan, . BFS+、PI、MIS、SCM Information systems infrastructure, fully integrated information s

10、ystem to realize information resources sharing; to expand the breadth and depth of the portal system, information system of Enterprise Management Assistant role to play; to improve the day-to-day operation and maintenance operation record of promoting causes and transfer system; to strengthen the tr

11、aining华北科技学院 用哈夫曼编码实现文件压缩实验报告用哈夫曼编码实现文件压缩实 验 报 告课程名称 数据结构B 实验学期 2013 至 2014 学年 第 一 学期学生所在系部 计算机学院 年级 2013 专业班级 学生姓名 学号 任课教师 实验成绩 一、实验题目：用哈夫曼编码实现文件压缩二、实验目的：1、 了解文件的概念。2、 掌握线性链表的插入、删除等算法。3、掌握Huffman树的概念及构造方法。4、掌握二叉树的存储结构及遍历算法。5、利用Huffman树及Huffman编码，掌握实现文件压缩的一般原理。三、实验设备与环境：微型计算机、Windows 系列操作系统 、Visual

12、C+6.0软件四、实验内容：根据输入小写英文字母和输入的对应权值创建哈夫曼树，可以求出每个小写英文字母的哈夫曼编码，将文本中的字母对应的哈夫曼编码写入文本中，实现对文本的编码。五、概要设计：（1）构造Hufffman树的Hufffman算法构造Huffman树步骤：1. 根据给定的n个权值w1,w2,wn，构造n棵只有根结点的二叉树，起权值为wj。2. 在森林中选取两棵根结点权值最小和次小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和。3. 在森林中删除这两棵树，同时将新得到的二叉树加入森林中。重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树。算法结构如图

13、：（2）Huffman编码：数据通信用的二进制编码思想：根据字符出现频率编码，使电文总长最短编码：根据字符出现频率构造Huffman树，然后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列。(3) 文本编码 读取存放在文本中的字母，一对一的进行编译，将对应的编码存放到另一个文本中。六、详细设计：#include #include #include /树结点定义 typedef struct int weight; int parent; int lchild; int rchild; HTNode,*HuffmanTre

14、e; static char N100;/用于保存字符 /赫夫曼编码，char型二级指针 typedef char *HuffmanCode; /封装最小权结点和次小权结点 typedef struct int s1; int s2; MinCode; /函数声明 void Error(); HuffmanCode HuffmanCoding(HuffmanTree &HT,HuffmanCode HC,int *w,int n); MinCode Select(HuffmanTree HT,int n); /当输入1个结点时的错误提示 void Error() printf(一个字符不进行编

15、码!n); exit(1); /构造赫夫曼HT，编码存放在HC中,w为权值,n为结点个数 HuffmanCode HuffmanCoding(HuffmanTree &HT,HuffmanCode HC,int *w,int n) int i,s1=0,s2=0; HuffmanTree p; char *cd; int f,c,start,m; MinCode min; if(n=1) Error();/只有一个结点不进行编码，直接exit(1)退出 m=2*n-1;/赫夫曼码需要开辟的结点大小为2n-1 HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);

16、/开辟赫夫曼树结点空间 m+1 /初始化n个叶子结点 for(p=HT,i=0;iweight=*w; p-parent=0; p-lchild=0; p-rchild=0; /将n-1个非叶子结点的初始化 for(;iweight=0; p-parent=0; p-lchild=0; p-rchild=0; /构造赫夫曼树 for(i=n+1;i=m;i+) min=Select(HT,i-1);/找出最小和次小的两个结点 s1=min.s1 ; /最小结点下标 s2=min.s2;/次小结点下标 HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HT

17、i.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight;/赋权和 /打印赫夫曼树 printf(HT List:n); printf(Numberttweightttparentttlchildttrchildn); for(i=1;i=m;i+) printf(%dtt%dtt%dtt%dtt%dtn,i,HTi.weight,HTi.parent,HTi.lchild,HTi.rchild); /从叶子结点到根节点求每个字符的赫夫曼编码 HC=(HuffmanCode)malloc(n+1)*sizeof(char *); cd=(char *)ma

18、lloc(n*sizeof(char *);/为赫夫曼编码动态分配空间 cdn-1=0;/编码结束符 /求叶子结点的赫夫曼编码 for(i=1;i=n;i+) start=n-1; /定义左子树为0，右子树为1 /* 从最下面的1号节点开始往顶部编码(逆序存放)，然后编码2号节点，3号. */ for(c=i,f=HTi.parent; f!=0; c=f,f=HTf.parent) if(HTf.lchild=c) cd-start=0; else cd-start=1; /为第i个字符分配编码空间 HCi=(char *)malloc(n-start)*sizeof(char *); /将

19、当前求出结点的赫夫曼编码复制到HC strcpy(HCi,&cdstart); free(cd); return HC; MinCode Select(HuffmanTree HT,int n) int min,secmin; int temp = 0; int i,s1,s2,tempi = 0; MinCode code ; s1=1; s2=1; min = 999999;/足够大 /找出权值weight最小的结点，下标保存在s1中 for(i=1;i=n;i+) if(HTi.weightmin & HTi.parent=0) min=HTi.weight; s1=i; secmin

20、= 999999;/足够大 /找出权值weight次小的结点，下标保存在s2中 for(i=1;i=n;i+) if(HTi.weightsecmin) & (i!=s1) & HTi.parent=0) secmin=HTi.weight; s2=i; /放进封装中 code.s1=s1; code.s2=s2; return code; void Compression(HuffmanCode HC)/翻译原文档字符为赫夫曼编码FILE *fp1,*fp2;char ch;if(fp1 = fopen(1.txt,r) = NULL)exit(0);if(fp2 = fopen(2.txt

21、,a) = NULL)exit(0);ch = fgetc(fp1);while(int)ch!= -1)switch(ch) case a: fputs(HC1,fp2); break;case b: fputs(HC2,fp2); break;case c: fputs(HC3,fp2); break;case d: fputs(HC4,fp2); break;case e: fputs(HC5,fp2); break;case f: fputs(HC6,fp2); break;case g: fputs(HC7,fp2); break;case h: fputs(HC8,fp2); br

22、eak;case i: fputs(HC9,fp2); break;case j: fputs(HC10,fp2); break;case k: fputs(HC11,fp2); break;case l: fputs(HC12,fp2); break;case m: fputs(HC13,fp2); break;case n: fputs(HC14,fp2); break; case o: fputs(HC15,fp2); break;case p: fputs(HC16,fp2); break;case q: fputs(HC17,fp2); break;case r: fputs(HC1

23、8,fp2); break;case s: fputs(HC19,fp2); break;case t: fputs(HC20,fp2); break;case u: fputs(HC21,fp2); break;case v: fputs(HC22,fp2); break;case w: fputs(HC23,fp2); break;case x: fputs(HC24,fp2); break;case y: fputs(HC25,fp2); break;case z: fputs(HC26,fp2); break;default:printf( 没有编码！n);ch = fgetc(fp1

24、);fclose(fp1);fclose(fp2); void main() HuffmanTree HT=NULL; HuffmanCode HC=NULL; int *w=NULL; int i,n; printf(输入字符：); gets(N); n = strlen(N); w=(int *)malloc(n+1)*sizeof(int *);/开辟n+1个长度的int指针空间 w0=0; printf(输入结点权值：n); /输入结点权值 for(i=1;i=n;i+) printf(w%d=,i); scanf(%d,&wi); /构造赫夫曼树HT，编码存放在HC中,w为权值,n为

25、结点个数 HC=HuffmanCoding(HT,HC,w,n); /输出赫夫曼编码 printf(赫夫曼:n); printf(NumberttWeightttCoden); for(i=1;i=n;i+) printf(%ctt%dtt%sn,Ni-1,wi,HCi); Compression(HC); 选取权值最小的结点的算法：选取权值次小的结点的算法：哈夫曼树建立的算法：开始读入n,S1,S2的值i=n+1i=2n-1 否 是HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weigh

26、t+HTs2.weight;i+输出S1的值结束哈夫曼编码的算法：开始读入ni=1i=n 否 是start=1c=if=HTi.parentf!=0 否 是HTf.lchild=c 否cd-start=1 是cd-start=0i+输出cd的值结束七、测试结果及分析：1.输入字符2.输入权值4. 输出哈夫曼树：5. 字符对应编码：6. 要编码的文本：7. 编译后的文本：八、教师评语：教 师 评 价评定项目ABCD评定项目ABCD算法正确界面美观，布局合理程序结构合理操作熟练语法、语义正确解析完整实验结果正确文字流畅报告规范题解正确其他：评价教师签名：年 月 日supervision in la

27、rge and medium goods vehicle. A is established large vehicles and small vehicles classification management of motor vehicle test mode, increased medium van car, and dangerous goods transport car, and school car test project; II is established motor vehicle test regulatory platform, achieved motor ve

28、hicle test full process video, and data remote regulatory; three is strictly motor vehicle identification management, equipped with unified of identification equipment and tool, using mobile identification Terminal, and law enforcement records instrument, technology identification means. As to 20XX

29、years June 20 statewide motor vehicle keep volume for 567,408 car, and last year earlier than growth 75,814 car, growth 13.36%; this year January-June, vehicles management section and license archives management section total accepted the motor vehicle registration business 42,543 car times, which r

30、egistered registration 6,905 car times, and transfer registration 3,592 car times, and change registration 1033 car times, and mortgage registration 696 car times, and cancellation registration 187 car times, and into business 980 car times, and Archives corrections 81 pieces times, and issued test

31、qualified logo 25,429 car times, and other vehicles business 3,640 car times; supervision Survey Section relies on motor vehicle detection remote issued test qualified logo software platform supervision motor vehicle test, and identification situation 7418l liangci, investigation motor vehicle excep

32、tion business 30 car times, his pards business warning 244 article, vehicles and driving people sound video regulatory screenshots 1852 Zhang, checks motor vehicle archives 716 pieces times, and medium bus, and medium above truck, and Of hazardous chemicals, vehicles and school buses and other key vehicle inspection record of 420. (C) based on their own, and strict adherence to defense, more cheating, false false fugitive suspects, robbery suspect vehicles and the Internet crackdown. DMV full p