下载文档原格式
哈弗曼编码实现无损压缩实验报告一、实验内容通过C++编程实现。
要求：1) 字符串的输入是手工输入的；2) 通过程序实现编码，最终在屏幕上显示编码结果，例如，如果选用huffman编码，则要显示字符串的编码以及平均码长；二、源代码#include<iostream.h>#include<math.h>#include<string.h>#include<stdlib.h>#if !defined _HUFFMANTREE_H_#define _HUFFMANTREE_H_class HuffmanTree{public:unsigned int Weight;unsigned int Parent;unsigned int lChild;unsigned int rChild;};typedef char **HuffmanCode;/*从结点集合中选出权值最小的两个结点将值分别赋给s1和s2*/ void Select(HuffmanTree* HT,int Count,int *s1,int *s2){unsigned int temp1=0;unsigned int temp2=0;unsigned int temp3;for(int i=1;i<=Count;i++){if(HT[i].Parent==0){if(temp1==0){temp1=HT[i].Weight;(*s1)=i;}else{if(temp2==0){temp2=HT[i].Weight;(*s2)=i;if(temp2<temp1){temp3=temp2;temp2=temp1;temp1=temp3;temp3=(*s2);(*s2)=(*s1);(*s1)=temp3;}}else{if(HT[i].Weight<temp1){temp2=temp1;temp1=HT[i].Weight;(*s2)=(*s1);(*s1)=i;}if(HT[i].Weight>temp1&&HT[i].Weight<temp2){temp2=HT[i].Weight;(*s2)=i;}}}}}}/*霍夫曼编码函数*/void HuffmanCoding(HuffmanTree * HT,HuffmanCode * HC,int *Weight,int Count){int i;int s1,s2;int TotalLength;char* cd;unsigned int c;unsigned int f;int start;if(Count<=1) return;TotalLength=Count*2-1;HT = new HuffmanTree[(TotalLength+1)*sizeof(HuffmanTree)];for(i=1;i<=Count;i++){HT[i].Parent=0;HT[i].rChild=0;HT[i].lChild=0;HT[i].Weight=(*Weight);Weight++;}for(i=Count+1;i<=T otalLength;i++){HT[i].Weight=0;HT[i].Parent=0;HT[i].lChild=0;HT[i].rChild=0;}//建造霍夫曼树for(i=Count+1;i<=T otalLength;++i){Select(HT, i-1, &s1, &s2);HT[s1].Parent = i;HT[s2].Parent = i;HT[i].lChild = s1;HT[i].rChild = s2;HT[i].Weight = HT[s1].Weight + HT[s2].Weight;}//输出霍夫曼编码(*HC)=(HuffmanCode)malloc((Count+1)*sizeof(char*)); cd = new char[Count*sizeof(char)];cd[Count-1]='\0';for(i=1;i<=Count;++i){start=Count-1;for(c = i,f = HT[i].Parent; f != 0; c = f, f = HT[f].Parent) {if(HT[f].lChild == c)cd[--start]='0';elsecd[--start]='1';(*HC)[i] = new char [(Count-start)*sizeof(char)];strcpy((*HC)[i], &cd[start]);}}delete [] HT;delete [] cd;}/** 在字符串中查找某个字符* 如果找到，则返回其位置*/int LookFor(char *str, char letter, int count){int i;for(i=0;i<count;i++){if(str[i]==letter) return i;}return -1;}void OutputWeight(char *Data,int Length,char **WhatLetter,int **Weight,int *Count){int i;char* Letter = new char[Length];int* LetterCount = new int[Length];int AllCount=0;int Index;int Sum=0;float Persent=0;for(i=0;i<Length;i++){if(i==0){Letter[0]=Data[i];LetterCount[0]=1;AllCount++;}else{Index=LookFor(Letter,Data[i],AllCount);if(Index==-1){Letter[AllCount]=Data[i];LetterCount[AllCount]=1;AllCount++;}else{LetterCount[Index]++;}}}for(i=0;i<AllCount;i++){Sum=Sum+LetterCount[i];}(*Weight) = new int[AllCount];(*WhatLetter) = new char[AllCount];for(i=0;i<AllCount;i++){Persent=(float)LetterCount[i]/(float)Sum;(*Weight)[i]=(int)(1000*Persent);(*WhatLetter)[i]=Letter[i];}(*Count)=AllCount;delete [] Letter;delete [] LetterCount;}#endif//*********************************main.cppvoid main(){HuffmanTree * HT = NULL;HuffmanCode HC;char Data[100];char *WhatLetter;int *Weight;int Count;cout<<"请输入一行文本数据:"<<endl;cin>>Data;cout<<endl;OutputWeight(Data,strlen(Data),&WhatLetter,&Weight,&Count); HuffmanCoding(HT, &HC, Weight, Count);cout<<"字符出现频率编码结果"<<endl;int k=0;for(int i = 0; i<Count; i++){cout<<WhatLetter[i]<<" ";cout<<Weight[i]/10<<"%\t";cout<<HC[i+1]<<endl;int j=strlen(HC[i+1]);k=k+Weight[i]*j;}cout<<"平均码长为"<<k/10;cout<<endl;}三、程序运行。
东北大学信息科学与工程学院数据结构课程设计报告题目哈夫曼压缩软件设计课题组长王健课题组成员张颖刘琪张晓雨专业名称计算机科学与技术班级计1307指导教师杨雷2015 年1月课程设计任务书目录1 课题概述 (4)1.1 课题任务 (4)1.2 课题原理 (4)1.3 相关知识 (4)2 需求分析 (5)2.1 课题调研 (5)2.2 用户需求分析 (5)3 方案设计 (5)3.1 总体功能设计 (5)3.2 数据结构设计 (6)3.3 函数原型设计 (6)3.4 主算法设计 (7)3.5 用户界面设计 (9)4 方案实现 (12)4.1 开发环境与工具 (12)4.2 程序设计关键技术 (12)4.3 个人设计实现（按组员分工）4.3.1 王健设计实现 (12)4.3.2 张颖设计实现 (17)4.3.3 刘琪设计实现 (20)4.3.4 张晓雨设计实现 (22)5 测试与调试 (25)5.1 个人测试（按组员分工） (25)5.1.1 王健测试 (25)5.1.2 张颖测试 (26)5.1.3 刘琪测试 (27)5.1.4 张晓雨测试 (31)5.2 组装与系统测试 (32)5.3 系统运行 (32)6 课题总结 (33)6.1 课题评价 (33)6.2 团队协作 (33)6.3 下一步工作 (33)6.4 个人设计小结（按组员分工） (33)6.4.1 王健设计小结 (33)6.4.2 张颖设计小结 (34)6.4.3 刘琪设计小结 (34)6.4.4 张晓雨设计小结 (34)7 附录A 课题任务分工 (35)A-1 课题程序设计分工 (35)A-2 课题报告分工 (36)附录B 课题设计文档（光盘） (37)B-1源程序代码（*.H，*.CPP） (37)B-2工程与可执行文件） (37)附录C 用户操作手册（可选） (37)C.1 运行环境说明 (37)C.2 操作说明 (37)1 课题概述1.1课题任务采用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。
《数据结构与算法》实验报告一、需求分析1.问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。
但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码(复原)。
对于双工通道（及可以双向传输信息的通道），每端都需要一个完整的编/译码系统。
试为这样的信息收发站写一个哈夫曼的编/译码系统。
2.基本要求一个完整的系统应具有以下功能：（1）I：初始化（Initialization）。
从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。
（2）E：编码（Encoding）。
利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。
（3）D：译码（Decoding）。
利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。
（4）P：印代码文件（Print）。
将文件CodeFile以紧凑格式显示在终端上，每行50个代码。
同时将此字符形式的编码文件写入文件CodePrin中。
（5）T：印哈夫曼树（Tree printing）。
将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示出，同时将此字符形式的哈夫曼树写入文件TreePrint中。
3.测试数据（1）利用教科书例6-2中的数据调试程序。
（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。
4,实现提示（1）编码结果以文本方式存储在文件CodeFile中。
（2）用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”表示退出运行Quit。
请用户键入一个选择功能符。
此功能执行完毕后再显示此菜单，直至某次用户选择了“Q”为止。
（3）在程序的一次执行过程中，第一次执行I、D或C命令之后，哈夫曼树已经在内存了，不必再读入。
数据结构哈夫曼编码实验报告数据结构哈夫曼编码实验报告1·实验目的1·1 理解哈夫曼编码的基本原理1·2 掌握哈夫曼编码的算法实现方式1·3 熟悉哈夫曼编码在数据压缩中的应用2·实验背景2·1 哈夫曼编码的概念和作用2·2 哈夫曼编码的原理和算法2·3 哈夫曼编码在数据压缩中的应用3·实验环境3·1 硬件环境：计算机、CPU、内存等3·2 软件环境：编程语言、编译器等4·实验过程4·1 构建哈夫曼树4·1·1 哈夫曼树的构建原理4·1·2 哈夫曼树的构建算法4·2 哈夫曼编码4·2·1 哈夫曼编码的原理4·2·2 哈夫曼编码的算法4·3 实现数据压缩4·3·1 数据压缩的概念和作用4·3·2 哈夫曼编码在数据压缩中的应用方法5·实验结果5·1 构建的哈夫曼树示例图5·2 哈夫曼编码表5·3 数据压缩前后的文件大小对比5·4 数据解压缩的正确性验证6·实验分析6·1 哈夫曼编码的优点和应用场景分析6·2 数据压缩效果的评估和对比分析6·3 实验中遇到的问题和解决方法7·实验总结7·1 实验所获得的成果和收获7·2 实验中存在的不足和改进方向7·3 实验对于数据结构学习的启示和意义附件列表：1·实验所用的源代码文件2·实验中用到的测试数据文件注释：1·哈夫曼编码：一种用于数据压缩的编码方法，根据字符出现频率构建树形结构，实现高频字符用较短编码表示，低频字符用较长编码表示。
2·哈夫曼树：由哈夫曼编码算法构建的一种特殊的二叉树，用于表示字符编码的结构。
数据结构哈夫曼编码实验报告数据结构哈夫曼编码实验报告1. 实验目的本实验旨在通过实践理解哈夫曼编码的原理和实现方法，加深对数据结构中树的理解，并掌握使用Python编写哈夫曼编码的能力。
2. 实验原理哈夫曼编码是一种用于无损数据压缩的算法，通过根据字符出现的频率构建一棵哈夫曼树，并根据哈夫曼树对应的编码。
根据哈夫曼树的特性，频率较低的字符具有较长的编码，而频率较高的字符具有较短的编码，从而实现了对数据的有效压缩。
实现哈夫曼编码的主要步骤如下：1. 统计输入文本中每个字符的频率。
2. 根据字符频率构建哈夫曼树，其中树的叶子节点代表字符，内部节点代表字符频率的累加。
3. 遍历哈夫曼树，根据左右子树的关系对应的哈夫曼编码。
4. 使用的哈夫曼编码对输入文本进行编码。
5. 将编码后的二进制数据保存到文件，同时保存用于解码的哈夫曼树结构。
6. 对编码后的文件进行解码，还原原始文本。
3. 实验过程3.1 统计字符频率首先，我们需要统计输入文本中每个字符出现的频率。
可以使用Python中的字典数据结构来记录字符频率。
遍历输入文本的每个字符，将字符添加到字典中，并递增相应字符频率的计数。
```pythondef count_frequency(text):frequency = {}for char in text:if char in frequency:frequency[char] += 1else:frequency[char] = 1return frequency```3.2 构建哈夫曼树根据字符频率构建哈夫曼树是哈夫曼编码的核心步骤。
我们可以使用最小堆（优先队列）来高效地构建哈夫曼树。
首先，将每个字符频率作为节点存储到最小堆中。
然后，从最小堆中取出频率最小的两个节点，将它们作为子树构建成一个新的节点，新节点的频率等于两个子节点频率的和。
将新节点重新插入最小堆，并重复该过程，直到最小堆中只剩下一个节点，即哈夫曼树的根节点。
数据结构实验报告----约瑟夫环一、需求分析：约瑟夫环是程序的一道经典例题，可以使用数据结构的单链表进行编写。
二、概要设计：大体上可以使用单链表通过节点的创建和删除来达到人数出列的效果，可以大大缩短程序量。
三、详细设计：1、首先定义一个单链表，然后分别做创建链表、以及对应的输入数据，删除节点对应的删除数据，以及输出功能。
最后用主函数实现上述功能。
下为程序源代码：#include<stdio.h>#include<malloc.h>typedef struct Lnode //创建一个单链表{int num;int key;struct Lnode *next;}Joseph;struct Lnode *head,*p,*p1;int creatlinklist(int n) //为节点分配内存，创建节点{int i=0;head = (struct Lnode*)malloc(sizeof(struct Lnode));if(!head){return 0;}p=head;for(i = 0;i<n-1;i++){p1=(struct Lnode*)malloc(sizeof(struct Lnode));if(!p1){return 0;}p->next=p1;p=p1;}p->next=head;p1=head;return 0;}int input(int n) //在分配的节点上输入数据{int i=0;int j=0;printf("please input the keys:\n");for(i =1;i<n+1;i++){scanf("%d",&j);p1->num=i;p1->key=j;p1=p1->next;}p1=p;return j;}int output(int m,int n) \\在约瑟夫环的规定上输出数据删除节点{int i=0;int a=0;for(i =0;i <n;i++){for(a=0;a<m-1;a++){p1=p1->next;}p=p1->next;m=p->key;printf("%d\n",p->num);p1->next=p->next;free(p);}return 0;}void main(){int m=0;int n=0;printf("请输入上限值和人数值：\n");scanf("%d%d",&m,&n);creatlinklist(n);input(n);printf("出对的人：\n");output(m,n);}四、调试分析：程序仅能使用一次，并且输入格式没有提示，容易犯错。
数据结构哈夫曼编码实验报告数据结构哈夫曼编码实验报告一、实验背景1：引言在日常生活中，信息传输已经成为了一个非常重要的环节。
通过对信息进行编码，可以有效地减少信息传输的开销和存储空间。
哈夫曼编码是一种常见的无损数据压缩方法，广泛应用于图像、音频和视频等领域。
本实验旨在通过实现哈夫曼编码算法，深入理解其工作原理，并对其性能进行评估。
2：实验目的本实验旨在：a：了解哈夫曼编码算法的基本原理；b：实现哈夫曼编码算法，并将其应用于对文本进行压缩；c：评估哈夫曼编码算法在不同文本数据上的性能。
二、实验内容1：哈夫曼编码原理介绍2：哈夫曼编码的实现思路a：构建哈夫曼树b：哈夫曼编码表c：对文本进行编码和解码3：实验环境介绍a：硬件环境b：软件环境4：实验步骤详解a：构建哈夫曼树的实现方法b：哈夫曼编码表的实现方法c：文本编码和解码的实现方法5：实验数据与结果分析a：不同文本数据的压缩结果对比 b：压缩性能的评估指标6：实验心得与建议a：实验过程中遇到的问题b：改进与优化方向三、实验结果与分析1：实验数据a：不同文本数据的大小与内容b：压缩率等性能指标数据2：实验结果分析a：不同文本数据对压缩效果的影响b：压缩率与文本数据的关系c：哈夫曼编码的运行时间分析四、结论根据实验结果和分析，可以得出以下结论：1：哈夫曼编码算法能够有效地减少文本数据的存储空间。
2：不同文本数据的压缩率存在差异，与文本的特性有关。
3：哈夫曼编码算法的运行时间与文本数据的长度成正比关系。
附件：1：实验源代码2：实验数据和结果法律名词及注释：1：无损数据压缩：指通过编码和解码过程，在不导致数据信息损失的情况下减少数据量。
2：哈夫曼编码：一种变长编码方式，通过更少的编码长度来表示频率较高的字符，从而达到减少编码长度的目的。
数据结构与程序设计实验实验报告哈尔滨工程大学实验报告四一、问题描述哈夫曼编码是一种常用的数据压缩技术，对数据文件进行哈夫曼编码可大大缩短文件的传输长度，提高信道利用率及传输效率。
要求采用哈夫曼编码原理，统计文本文件中字符出现的词频，以词频作为权值，对文件进行哈夫曼编码以达到压缩文件的目的，再用哈夫曼编码进行译码解压缩。
统计待压缩的文本文件中各字符的词频，以词频为权值建立哈夫曼树，并将该哈夫曼树保存到文件HufTree.dat 中。
根据哈夫曼树（保存在HufTree.dat 中）对每个字符进行哈夫曼编码，并将字符编码保存到HufCode.txt 文件中。
压缩：根据哈夫曼编码，将源文件进行编码得到压缩文件CodeFile.dat。
解压：将CodeFile.dat 文件利用哈夫曼树译码解压，恢复为源文件。
二、数据结构设计由于哈夫曼树中没有度为1的结点，则一棵树有n个叶子结点的哈夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中，而且对每个结点而言，即需知双亲结点的信息，又需知孩子结点的信息，由此可采用如下数据结构。
1.使用结构体数组统计词频，并存储:typedef struct Node{int weight; //叶子结点的权值char c; //叶子结点int num; //叶子结点的二进制码的长度}LeafNode[N];2.使用结构体数组存储哈夫曼树:typedef struct{unsigned int weight;//权值unsigned int parent, LChild, RChild;}HTNode,Huffman[M+1]; //huffman树3.使用字符指针数组存储哈夫曼编码表：typedef char *HuffmanCode[2*M]; //haffman编码表三、算法设计1.读取文件，获得字符串void read_file(char const *file_name, char *ch){FILE *in_file = Fopen(file_name, "r");unsigned int flag = fread(ch, sizeof(char), N, in_file);if(flag == 0){printf("%s读取失败\n", file_name);fflush(stdout);}printf("读入的字符串是: %s\n\n", ch);Fclose(in_file);int len = strlen(ch);。
《用哈夫曼编码实现文件压缩》实验报告课程名称数据结构（B）实验学期2009 至2010 学年第 1 学期学生所在系部计算机系年级2007 专业班级计算机B071学生姓名陆永芳学号200707014105任课教师盛建瓴实验成绩用哈夫曼编码实现文件压缩1、了解文件的概念。
2、掌握线性链表的插入、删除等算法。
3、掌握Huffman树的概念及构造方法。
4、掌握二叉树的存储结构及遍历算法。
5、利用Huffman树及Huffman编码，掌握实现文件压缩的一般原理。
微型计算机、Windows 系列操作系统、Visual C++6.0软件根据ascii码文件中各ascii字符出现的频率情况创建Haffman树，再将各字符对应的哈夫曼编码写入文件中，实现文件压缩。
本次实验采用将字符用长度尽可能短的二进制数位表示方法，即对于文件中出现的字符，无须全部都用8位的ASCII码进行存储，根据他们在文件中出现色频率不同，我们利用Haffman算法使每个字符都能以最短的二进制字符进行存储，以达到节省存储空间，压缩文件的目的。
解决了压缩需采用的算法，程序的思路就清晰了：1.统计需压缩文件中每个字符出现的频率2.将每个字符的出现频率作为叶子结点构建Haffman树，然后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径得到0、1的序列，这样便能完成了Haffman的编码，将每个字符用最短的二进制字符表示。
3.打开需压缩文件，再将需压缩文件中的每个ascii码对应的Haffman编码按bit单位输出。
4.文件压缩结束。
（1）构造Huffman树的方法——Haffman算法构造Huffman树步骤：I．根据给定的n个权值{w1,w2，……，wn}，构造n棵只有根结点的二叉树，令起权值为wj。
II．在森林中选取两棵根结点权值最小的树作为左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和。
用哈夫曼编码实现文件压缩实验目的⒈了解有关文件的基本概念⒉掌握哈夫曼树的概念及其构造方法⒊正确实现线性链表的插入，删除等运算⒋掌握遍历二叉树的方法⒌运用哈夫曼树及其编码实验环境Windows XP VC++ 6.0实验内容根据ascii码文件中各ascii字符出现的频率情况创建哈夫曼树，再将各字符对应的哈夫曼编码相连，每八位作为一个字符，写入文件中，同时Huffman树也要压缩后写入压缩文件，以实现文件压缩。
设计概要压缩部分1.构造哈夫曼树，对其进行前缀编码（1）扫描待压缩文件，得出各字符出现频率。
（2）根据给定的n个权值{W1,W2,...Wn}构成n棵二叉树的集合F={T1，T2，…，Tn}，每棵二叉树Ti中只有一个带权为Wi的根节点，其左右子树均空。
（3）在F中选取两棵根节点的权值最小的树作为左右子树构造一棵新的二叉树，且值新的二叉树的根节点的权值为其左右子树上根节点的全值之和。
（4）在F中删除这两棵树。
同时将新得到的二叉树加入F中。
重置（2）和（3），直到F只含一棵树为止。
这棵树便是哈夫曼树。
2.由Huffman树得到各字符前缀编码。
3.根据前缀编码，对文件中各个字符进行编码，并按每八位一次写入压缩文件。
4.处理剩余不到八位部分，写入压缩文件。
5.将前缀编码及相关信息写入压缩文件。
6.关闭指针，完成压缩。
计算压缩率。
解压部分1.读入压缩文件长度和源文件长度。
读入前缀编码。
2.对文件中各字符解码，写入解压文件。
3.判断解压文件是否完好（对比压缩前文件长度），关闭指针，完成解压。
源码部分：#include <stdio.h>#include <string.h>#include <stdlib.h>#include <conio.h>struct head {unsigned char b; //记录字符在数组中的位置long count; //字符出现频率（权值）long parent,lch,rch; //定义哈夫曼树指针变量char bits[256]; //定义存储哈夫曼编码的数组}header[512],tmp;void compress(){char filename[255],outputfile[255],buf[512];unsigned char c;long n,m,i,j,f; //作计数或暂时存储数据用long min1,pt1,flength=0,length1,length2; //记录最小结点、文件长度double div; //计算压缩比用FILE *ifp,*ofp; //分别为输入、输出文件指针printf("\t请您输入需要压缩的文件（需要路径）：");gets(filename);ifp=fopen(filename,"rb");if(ifp==NULL){printf("\n\t文件打开失败!\n ");system("pause");return;}printf("\t请您输入压缩后的文件名（如无路径则默认为桌面文件）：");gets(outputfile);ofp=fopen(outputfile,"wb");if(ofp==NULL){printf("\n\t压缩文件失败!\n ");system("pause");return;}flength=0;while(!feof(ifp)){fread(&c,1,1,ifp);header[c].count++; //字符重复出现频率+1flength++; //字符出现原文件长度+1 }flength--;length1=flength; //原文件长度用作求压缩率的分母header[c].count--;for(i=0;i<512;i++){if(header[i].count!=0)header[i].b=(unsigned char)i;/*将每个哈夫曼码值及其对应的ASCII码存放在一维数组header[i]中，且编码表中的下标和ASCII码满足顺序存放关系*/ elseheader[i].b=0;header[i].parent=-1;header[i].lch=header[i].rch=-1; //对结点进行初始化}for(i=0;i<256;i++){ //按出现权值从大到小排序for(j=i+1;j<256;j++){if(header[i].count<header[j].count){tmp=header[i];header[i]=header[j];header[j]=tmp;}}}for(i=0;i<256;i++) //找到第一个空的header结点if(header[i].count==0)break;n=i;m=2*n-1;for(i=n;i<m;i++){min1=999999999; //预设的最大权值，即结点出现的最大次数for(j=0;j<i;j++){if(header[j].parent!=-1)continue; /*parent!=-1说明该结点已存在哈夫曼树中，跳出循环重新选择新结点*/ if(min1>header[j].count){pt1=j;min1=header[j].count;continue;}}header[i].count=header[pt1].count;header[pt1].parent=i;header[i].lch=pt1;min1=999999999;for(j=0;j<i;j++){if(header[j].parent!=-1)continue;if(min1>header[j].count){pt1=j;min1=header[j].count;continue;}}header[i].count+=header[pt1].count;header[i].rch=pt1;header[pt1].parent=i; //哈夫曼无重复前缀编码}for(i=0;i<n;i++){f=i;header[i].bits[0]=0; //根结点编码0while(header[f].parent!=-1){j=f;f=header[f].parent;if(header[f].lch==j){ //置左分支编码0j=strlen(header[i].bits);memmove(header[i].bits+1,header[i].bits,j+1);//依次存储连接"0""1"编码，此处语句为网络借鉴header[i].bits[0]='0';}else{ //置右分支编码1j=strlen(header[i].bits);memmove(header[i].bits+1,header[i].bits,j+1);header[i].bits[0]='1';}}}fseek(ifp,0,SEEK_SET); //从文件开始位置向前移动0字节，即定位到文件开始位置fwrite(&flength,sizeof(int),1,ofp); /*用来将数据写入文件流中，参数flength 指向欲写入的数据地址，总共写入的字符数以参数size*int来决定，返回实际写入的int数目*/fseek(ofp,8,SEEK_SET);buf[0]=0; //定义缓冲区,它的二进制表示00000000f=0;pt1=8; /*假设原文件第一个字符是"A"，8位2进制为01000001，编码后为0110识别编码第一个'0'，那么将其左移一位，看起来没什么变化。
XXX學院数据结构课程设计报告题目：基于哈夫曼编码的压缩软件系部名称：计算机专业名称：软件工程班级：0802学号：XXXXXX学生姓名：稻草人指导教师：XXXXX时间：2010 XX--2010 YY一、课程设计目的通过运用哈夫曼树的知识编写该压缩与解压软件，能使学生将所学的理论知识应用起来，有效地运用到解决实际问题中去，提高学生的自身的编程能力，从而达到学以致用的目的。
二、课程设计内容1．应用系统分析，建立该系统的功能模块框图及界面的组织和设计；2．分析系统中的各个函数及它们之间的关系；3．根据问题描述，设计系统的结构体及各个函数；4．设计哈弗曼树的构造算法和哈弗曼编码算法；5．完成设计的系统各个应用模块；6．将各个模块整合进行功能测试。
三、需求分析哈弗曼压缩软件1.需求分析目的为明确软件需求、安排项目规划与进度、组织软件开发与测试，供设计人员、开发人员参考。
2. 项目开发计划3.能比较完善的对txt文件进行压缩和解压缩。
4. 数据字典名称：字符频率别名：weight描述：读取文本文件，并统计文件中字母个数定义：字符频率= 字符+ 数量名称：结点别名：HTNode描述：建立huffman树的叶子和非叶子结点定义：结点= 数量+ 字符+ 双亲结点+ 左孩子结点+ 右孩子结点位置：编码文件5. 功能划分⏹压缩⏹解压缩四、概要设计哈弗曼压缩软件1 建立哈夫曼树。
根据哈夫曼编码技术，可以将已经给出的字母的使用频率建立一个哈夫曼树，即以二叉树的形式将英文字母和空格存储。
2 编码。
利用二叉树的遍历知识，左孩子用“0”表示，右孩子用“1”表示，将输入的一组英文句子进行编码。
3测试和输出。
程序要求的测试的英文句子是：“knowledge is power”，输出每一个字母然后给出相应的哈夫曼编码。
本程序输入字母以“#”结束。
4译码。
本程序要求对已编码的数字能够给以反编码。
.函数调用示意图六、调试情况，设计技巧及体会1．测试结论◆能较好地进行压缩和解压◆不足的是对最后所补的0未处理，解压会多出几个字符。
2.设计技巧本软件可对字母、汉字可以实现共同压缩，压缩率在50%以上，压缩后对哈夫曼树进行保存，以便后面解压，对叶子结点只保存其字符、左孩子、右孩子，对非叶子结点保存左孩子和右孩子。
解压时从根结点开始，利用哈夫曼树进行解压，遇到0，找左孩子，遇到1找右孩子，到叶子结点时，输出字符。
3．心得体会：通过这次课题实验的程序实践，我实在获益匪浅！数据结构是上个学期开展的一门学科，学习好这门学科是非常重要的，在以后的程序设计方面这门学科能给我们很大的帮助。
同时，学习这门学科也是艰辛的，因为它比较难懂，这不仅需要我们要发挥我们的聪明才志，还需要我们在不断的实践中领悟。
这次的程序设计对我来说无疑是一个具大的考验，从接起课题后，我就一直为实现程序而努力，翻阅相关书籍、在网上查找资料。
因为开始时基础不是很好，过程中遇到了不少的阻碍，编写程序的进度也比较慢。
虽然如此，但是通过自己的努力与老师的指导，我对这次实验的原理有了一定的理解，通过参照从网上找到的源程序，终于在其它源程序的基础下写出了本次实验的核心算法，并使其能够正常的运行。
这一个多月的设计工作，让我体会到了作为一个编程人员的艰难，一个算法到具体实现，再到应用层面的开发是需要有一段较长的路要走的，不是一朝一夕就可以实现的，而且在编好程序后，编程人员还要花很多的时间去完善它，其中包含的心酸，外人是不会明白的。
非常感谢在背后一直给我指导的老师和同学，他们的支持和鼓励让我在遇到挫折时能够站起来战胜它，也让我走到了今天这一步，完成了实验的设计。
今后，我会更加努力的学习专业知识，提高自我的能力。
七、参考文献《c语言程序设计》谭浩强主编八、附录：源代码#include<stdio.h>#include<stdlib.h>#include<malloc.h>#include<string.h>#include<io.h>typedef struct word{char word[3];unsigned long times;struct word *next;}word,*word_list;typedef struct Tnode{unsigned long weight;char word[3];long parent,lchild,rchild;}Tnode,HuffTree;HuffTree ht[5000];char *hc[5000];int n=0;void stat(word_list head,char *filename){FILE *fp;char ch[3];int flag=0;word *p,*q,*s;fp=fopen(filename,"rt");if(fp==NULL)printf("\n无法打开要压缩的文件,或该文件不存在!");p=head;while((ch[0]=fgetc(fp))!=EOF){if(ch[0]<0||ch[0]>254){ch[1]=fgetc(fp);ch[2]='\0';}else ch[1]='\0';if(ch[0]==10) strcpy(ch,"-n");if(ch[0]==32) strcpy(ch,"-t");for(q=head->next;q!=NULL;q=q->next){if(!strcmp(q->word,ch)){(q->times)++;flag=1;break;}}if(flag==0){s=(word *)malloc(sizeof(word));strcpy(s->word,ch);s->times=1;p->next=s;p=s;p->next=NULL;++n;}flag=0;}p->next=NULL;fclose(fp);return;}void protect1(char *filename){FILE *fp2;char ch[26]="编码：";int i;strcat(ch,filename);fp2=fopen(ch,"wt");if(fp2==NULL){printf("\n编码文件无法创建!");exit(1);}for(i=1;i<=2*n-1;i++){fprintf(fp2,"%s %ld %ld %ld\n",ht[i].word,ht[i].parent,ht[i].lchild,ht[i].rchild);}fclose(fp2);return;}void out(char *filename){FILE *fp2;char ch[26]="编码：";int i;strcat(ch,filename);fp2=fopen(ch,"rt");if(fp2==NULL){printf("\n编码文件无法打开!");exit(1);}for(i=1;!feof(fp2);i++){fscanf(fp2,"%s %ld %ld %ld\n",ht[i].word,&ht[i].parent,&ht[i].lchild,&ht[i].rchild);n=i;}fclose(fp2);return;}void sort(){int i,j;unsigned long min;char ch[3];for(i=1;i<n;i++)for(j=i+1;j<=n;j++){if(ht[i].weight>ht[j].weight){min=ht[j].weight;ht[j].weight=ht[i].weight;ht[i].weight=min;strcpy(ch,ht[i].word);strcpy(ht[i].word,ht[j].word);strcpy(ht[j].word,ch);}}return;}void select(int t,int *s1,int *s2){int i;unsigned long min1,min2;min1=min2=4294967295;*s1=*s2=0;for(i=1;i<=n;i++){if(ht[i].parent==0){if((ht[i].parent==0)&&(ht[i+1].parent==0)&&i+1<=n){min1=ht[i].weight;*s1=i;min2=ht[i+1].weight;*s2=i+1;break;}else{min1=ht[i].weight;*s1=i;break;}}}for(i=n+1;i<=t;i++){if(ht[i].weight<min1&&ht[i].parent==0){min2=min1;*s2=*s1;min1=ht[i].weight;*s1=i;continue;}else if(ht[i].weight<min2&&ht[i].parent==0){min2=ht[i].weight;*s2=i;}}return;}void ctrHuffTree(word *head){int i,m,s1,s2;word *p;for(i=1,p=head->next;i<=n&&p!=NULL;i++,p=p->next){ht[i].weight=p->times;strcpy(ht[i].word,p->word);ht[i].parent=ht[i].rchild=ht[i].lchild=0;}m=2*n-1;for(i=n+1;i<=m;i++){ht[i].parent=ht[i].rchild=ht[i].lchild=ht[i].weight=0;}sort();for(i=n+1;i<=m;i++){select(i-1,&s1,&s2);strcpy(ht[i].word,"无");ht[i].weight=ht[s1].weight+ht[s2].weight;ht[s2].parent=ht[s1].parent=i;ht[i].lchild=s2; ht[i].rchild=s1;}return;}void ctrHuffmancode(){char *cd;int c,p,start,i;cd=(char *)malloc((n+1)*sizeof(char));cd[n]='\0';for(i=1;i<=n;i++){start=n;c=i; p=ht[i].parent;while(p!=0){--start;if(ht[p].lchild==c)cd[start]='0';else if(ht[p].rchild==c)cd[start]='1';c=p; p=ht[p].parent;}hc[i]=(char *)malloc((n-start)*(sizeof(char)));strcpy(hc[i],&cd[start]);}free(cd);return;}void compress(char *filename,char *filename1){FILE *fp1,*fp2;int t,i=0,j=0,sum=0;char ch[3], tr[8];unsigned char c;fp1=fopen(filename,"rt");if(fp1==NULL){printf("\n无法打开%s 文件,或该文件不存在!",filename);exit(0);}fp2=fopen(filename1,"wb");if(fp2==NULL){printf("\n无法创建%s 文件!",filename1);exit(0);}system("cls");printf("\n\n\n\n\n\n\n\n 压缩中，请稍候...");while((ch[0]=fgetc(fp1))!=EOF){if(ch[0]<0||ch[0]>254){ch[1]=fgetc(fp1);ch[2]='\0';}elsech[1]='\0';for(t=1;t<=n;t++){if(ch[0]==10&&ch[1]=='\0') strcpy(ch,"-n");if(ch[0]==32&&ch[1]=='\0') strcpy(ch,"-t");if(!strcmp(ht[t].word,ch)){while(j<=7){for(;*(hc[t]+i)!='\0';i++,j++){tr[j]=*(hc[t]+i);if(j==7){sum=(tr[7]-48)*1+(tr[6]-48)*2+(tr[5]-48)*4+(tr[4]-48)*8+(tr[3]-4 8)*16+(tr[2]-48)*32+(tr[1]-48)*64+(tr[0]-48)*128;c=(unsigned char)sum;fputc(c,fp2);j=0;i++;break;}}if(*(hc[t]+i)=='\0'){i=0;t=n+1;break;}}}}}if(j<=7&&j!=0){for(;j<=7;j++){ tr[j]=48;if(j==7){sum=(tr[7]-48)*1+(tr[6]-48)*2+(tr[5]-48)*4+(tr[4]-48)*8+(tr[3]-4 8)*16+(tr[2]-48)*32+(tr[1]-48)*64+(tr[0]-48)*128;c=(unsigned char)sum;fputc(c,fp2);break;}}fclose(fp1);fclose(fp2);system("cls");printf("\n\n\n\n\n\n\n\n 压缩完成!(按任意键返回)\n");getch();return;}void re_compress(char *filename1,char *filename2){int m[8],i=0,j=0,flag=1;HuffTree p;char ch,cha='\t';unsigned char c;FILE *fp1,*fp2;p=ht[n];fp1=fopen(filename1,"rb");if(fp1==NULL){printf("\n无法打开压缩文件%s,或该文件不存在!",filename1);exit(0);}fp2=fopen(filename2,"wt");if(fp2==NULL){printf("\n无法创建%s 文件!",filename2);exit(0);}system("cls");printf("\n\n\n\n\n\n\n\n 解压中，请稍候...");ch=fgetc(fp1);c=(unsigned char)ch;while(!feof(fp1)){while(flag!=0){for(i=7;i>=0;i--){m[i]=c%2;flag=c=c/2;if(i==0||c==0){break;}}if((unsigned char)ch<128&&(c==0)&&(i!=0))for(i=--i;i>=0;i--){m[i]=0;if(i==0) break;}}for(j=i;j<=7;j++){if(m[j]==0) p=ht[p.lchild];else if(m[j]==1) p=ht[p.rchild];if(p.lchild==0&&p.rchild==0){if(strcmp(p.word,"-n")==0){fputc('\n',fp2);}else if(strcmp(p.word,"-t")==0){fputc(' ',fp2);}elseif(strcmp(p.word,"-n")!=0&&strcmp(p.word,"-t")!=0){fprintf(fp2,"%s",p.word);}p=ht[n];}}}ch=fgetc(fp1);c=(unsigned char)ch;flag=1;}fclose(fp1);fclose(fp2);system("cls");printf("\n\n\n\n\n\n\n\n 解压完成!(按任意键返回)\n");getch();return;}main(){char filename[20],filename1[20],filename2[20];word_list head;char choise;head=(word *)malloc(sizeof(word));head->next=NULL;while(1){system("cls");printf("\n\n\n\n\n************************************");printf("\n\n 请选择您要执行的操作:\n\n 1.压缩文件\n\n 2.解压文件\n\n 3.退出\n");printf("\n\n************************************");flushall();choise=getch();switch(choise){case '1':{system("cls");printf("\n\n\n\n\n\n\n\n请输入要压缩的文件名:");flushall();scanf("%s",filename);printf("\n\n 请输入压缩后的文件名:");flushall();scanf("%s",filename1);stat(head,filename);ctrHuffTree(head);ctrHuffmancode();protect1(filename1);compress(filename,filename1);break;}case '2':{system("cls");printf("\n\n\n\n\n 请输入要解压的文件名:");flushall();scanf("%s",filename1);printf("\n 请输入解压后的文件名:");flushall();scanf("%s",filename2);out(filename1);re_compress(filename1,filename2);break;}case '3':{exit(1);printf("\n\n ");}default:{system("cls");printf("\n您的选择有误!");break;}}}printf("\nmain over!\n");return;}。
