数据结构__课程设计之哈夫曼编码

第一篇：数据结构__课程设计之哈夫曼编码

哈夫曼编码与解码的实现

一、设计思想

(一)哈夫曼树的设计思想

对于一组具有确定权值的叶子结点可以构造出多个具有不同带权路径长度的二叉树，其中具有最小带权路径长度的二叉树称作哈夫曼树或最优二叉树。

首先给定n个权值制造n个只含根结点的二叉树，得到一个二叉树林；再在这二叉树林里面找根结点的权值最小和次小的两棵树作成新的二叉树，其中新的二叉树的根结点的权值为左右子根结点权值之和；最后在二叉树林中把组合过的二叉树删除，再重复第二步，直到最后就剩一颗二叉树的时候得到的这棵二叉树就是哈夫曼树。

（二）哈夫曼编码与解码的设计思想

在数据通讯中，经常要将传送的文字转换为二进制字符0和1组成的二进制串，称这个过程为编码。与子相对的是解码或是译码，就是用与编码相同的方式将二进制串转换称编码前的文字的过程称作解码。在这里是通过哈夫曼树实现编码与解码的，所以称作是哈夫曼编码与解码。

首先输入一个字符串，还有相应的在哈夫曼树里的权值，这样用哈夫曼树把字符串用二进制串代替它，这个过程要注意树和编码问题，其中树的问题在上面已经解决，主要看编码的问题，就是根据我们输入的字符串和权值建立相应的树模型，这一步完成那编码就已经完成了，最后打印就行了；然后就是解码，完成编码相应的解码就相对简单了，就是先找到在编码的时候建的那个模型树，将编码中的二进制串再根据权值转换为相应的字符串，这样一步步解码就行了。

以上就是通过用哈夫曼树进行哈夫曼编码与解码如何实现的主要设计思想。

哈夫曼编码与解码的实现

for(i=n+1;i<=2*n-1;i++)

{

s1=s2=10000;

x1=x2=0;

for(j=1;j<=i-1;j++)

{

if(myHaffTree[j].parent==0&&myHaffTree[j].weight

{

s2=s1;x2=x1;

s1=myHaffTree[j].weight;x1=j;

}

else if(myHaffTree[j].parent==0&&myHaffTree[j].weight

{

s2=myHaffTree[j].weight;x2=j;

}

}

myHaffTree[x1].parent=i;

myHaffTree[x2].parent=i;

myHaffTree[i].weight=s1+s2;

myHaffTree[i].lchild=x1;

myHaffTree[i].rchild=x2;

} } void HaffmanCode(int n){ int start,c,f,i,j,k;char *cd;cd=(char *)malloc(n*sizeof(char));myHaffCode=(struct Coding *)malloc((n+1)*sizeof(struct Coding));cd[n-1]='';for(i=1;i<=n;++i){

start=n-1;

for(c=i,f=myHaffTree[i].parent;f!=0;c=f,f=myHaffTree[f].parent)

if(myHaffTree[f].lchild==c)cd[--start]='0';

else cd[--start]='1';

for(j=start,k=0;j

{

myHaffCode[i].bit[k]=cd[j];

k++;

}

myHaffCode[i].ch=myHaffTree[i].ch;

myHaffCode[i].weight=myHaffTree[i].weight;}

/*取编码对应的权值*/

/*n个叶子结点的哈夫曼编码*/

/*构造n个结点哈夫曼编码*/

/*左右子组合为新树*/

/*分配左右结点*/

/*构造哈夫曼树的非叶子结点*/ /*树的初始化*/

哈夫曼编码与解码的实现

{

for(j=1;j<=m;j++)

if(myHaffCode[j].ch==*p)

printf(“%sn”,myHaffCode[j].bit);} }

void Caozuo_D(int n){ int i,c;char code[1000],*p;printf(“please input the coding：”);scanf(“%s”,code);for(p=code,c=2*n-1;*p!='';p++)

{

if(*p=='0')

{

c=myHaffTree[c].lchild;

{

printf(“%c”,myHaffTree[c].ch);

c=2*n-1;

continue;

}

}

else if(*p=='1')

{

c=myHaffTree[c].rchild;

if(myHaffTree[c].lchild==0)

{

printf(“%c”,myHaffTree[c].ch);

c=2*n-1;

continue;

}

} } printf(“n”);}

void main(){

int n;

char char1;

n=Init();

/*定义字符*/

/*函数的调用*/

/*赋值*/

/*结束*/

/*赋值*/ /* 扫描*/

if(myHaffTree[c].lchild==0)

/*结束条件*/

/*进行解码*/

/*输入二进制编码*/

/*解码函数*/

哈夫曼编码与解码的实现

五、遇到的问题及解决

这部分我主要遇到了如下三个问题，其内容与解决方法如下所列：  问题1:

刚开始不知道如何建一个好树，因为我开始试着建了几个二叉树，不知道什么原因运行的时候那编码总是不对，跟在草稿纸上自己画的那个二叉树总是不相符，就找原因。解决方法:

开始时总是编码出错，就试着找错，树的初始化不可能出错，所以首先看那叶子结点的for函数，没什么错误，接着看非叶子结点的for函数，非叶子结点不好弄，找起来麻烦一些，就是费时间，盘查到最后也没什么错，最后就是左右子结点重生结点的一块了，这也比较好查，可是结果却是错处在这儿了，没想到最放心的一块

第二篇：数据结构课程设计-哈夫曼编码译码器

课 程 设 计

课程名称_ _数据结构课程设计_ 题目名称_ 哈夫曼编码译码器_ 学生学院 专业班级 学 号 学生姓名 指导教师

2011 年

12月

23日

摘要：

在当今信息爆炸时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度尽可能最短，即采用最短码。

关键字：

哈夫曼树

编码 解码 数据压缩技术 1

目

录

摘要：.........................................................................................................1 关键字：.....................................................................................................1 第一章 需求分析......................................................................................3 第二章 数据结构定义及其操作实现......................................................3 第三章 程序设计及其实现......................................................................3 3.1 从文件读入原文...........................................................................3 3.2 统计原文中各字符的权值.........................................................4 3.3 编码..............................................................................................5 3.4

解码............................................................................................6 3.5 主函数............................................................................................7 第四章 运行结果及其分析......................................................................8 第五章 问题及其解决方法....................................................................10 第六章 心得体会（设计总结）............................................................10 附录——源程序......................................................................................11

1、头文件.........................................................................................11

2、赫夫曼编码算法........................................................................12

3、主函数.........................................................................................18 参

考

文

献......................................................................................21

第一章 需求分析

1．问题要求：打开一篇英文文章，统计出每个字符出现的次数，然后以他们为权值，对每个字符进行编码，编码完成后对其编码进行译码。2．程序运行环境：windows、visual c++或java等 3．要求：

a)输入一篇英文文章，根据字符出现的次数给出哈夫曼编码方式。b)对英文文章进行编码；

c)对编码进行译码核对正确性

第二章 数据结构定义及其操作实现

2.1 哈弗曼树节点

typedef struct { unsigned int weight;unsigned int parent;unsigned int lchild;unsigned int rchild;}HuffTreeNode,*HuffTree;

2.2 字符-权值-编码映射

typedef struct { char c;unsigned int weight;char *code;}CharMapNode,*CharMap;

第三章 程序设计及其实现

3.1 从文件读入原文

void Huffman::ReadTextFromFile(char *filename){

} ifstream infile(filename);if(!infile){

} char c;while(infile.get(c)){ } text += c;cerr << “无法打开文件！” <

void Huffman::CountCharsWeight(){

if(text.empty())return;delete chars;if(chars!= NULL)int i = 0;n = 0;chars = new CharMapNode[2];chars[1].c = text[i];chars[1].weight = 1;++n;for(i = 1;i!= text.size();++i){ int j;

//遍历当前字符表，如果已存在该字符，for(j = 1;j <= n;++j)权值+1

{

if(text[i] == chars[j].c){

++chars[j].weight;4

} }

break;

if(j > n)//该字符不存在，添加该字符

{

++n;

CharMap newchars = new CharMapNode[n + 1];

memcpy(newchars, chars, n * sizeof(CharMapNode));

delete chars;

chars = newchars;

chars[n].c = text[i];

chars[n].weight = 1;

} } } 3.3 编码

void Huffman::MakeCharMap(){ if(n <= 1)

return;int m = 2 * n1, s1, s2);

huffTree[s1].parent = huffTree[s2].parent = i;

huffTree[i].lchild = s1;

huffTree[i].rchild = s2;

huffTree[i].weight = huffTree[s1].weight + huffTree[s2].weight;}

//从叶子到根节点逆向求每个字符的哈弗曼编码

char *cd = new char[n];//分配求编码的工作空间（每个字符编码结果最长n-1再加上''）

cd[n-1] = '';

//编码结束符

for(i = 1;i <= n;++i)//逐个字符求哈弗曼编码

{

int start = nstart];//为第i个字符编码分配空间

strcpy(chars[i].code,&cd[start]);} delete cd;}

3.4

解码

void Huffman::Decode(){ text = “";string::size_type i,count;for(i = 0;i < code.size();i += count){

//每个字符的编码结果最长n-1，从1至n-1依次尝试

for(count = 1;count < n;++count)

{

for(int j = 1;j <= n;++j)

if(code.substr(i, count)== chars[j].code)

{

next:

} }

3.5 主函数

};

}

text += chars[j].c;goto next;int main(){ cout << ”

************************************************************“ << endl;cout << ”

*

*“ << endl;cout << ”

*

哈夫曼编码译码器

*“ << endl;cout << ”

*

1、打开一篇英文文章或输入一篇文章

*“<< endl;cout << ”

*

2、根据字符出现的次数以他们为权值给出哈夫曼编码方式

*“ << endl;cout << ”

*

3、对英文文章进行编码

*“ << endl;cout << ”

*

4、对编码进行译码核对正确性

*“ << endl;cout << ”

*

*“ << endl;cout << ”

************************************************************“ << endl<

cout << ”程序自动统计字符和权值“ << endl;huffman.CountCharsWeight();cout << endl;cout << ”字符及对应权值：“ << endl;huffman.PrintCharWeight();cout << endl;system(”pause“);

cout << endl;huffman.MakeCharMap();cout << ”字符及对应编码：“ << endl;huffman.PrintCharCode();cout << endl;system(”pause“);cout << endl;

cout << ”对原文进行编码：“ << endl;cout << ”原文：“ << endl;huffman.PrintText();huffman.Encode();cout << endl;cout << ”编码：“ << endl;huffman.PrintCode();huffman.SaveCodeToFile(”code.txt“);cout << endl;system(”pause“);cout << endl;

cout << ”对编码进行解码：“ << endl;huffman.ReadCodeFromFile(”code.txt“);cout << ”编码：“ << endl;huffman.PrintCode();huffman.Decode();cout << endl;cout << ”原文：“ << endl;huffman.PrintText();huffman.SaveTextToFile(”resulttext.txt“);cout << endl;

return 0;}

第四章 运行结果及其分析

本次测试是先建立一个名为test.txt的文本文档，内容为：HuffmanCoding.运行程序，结果

This is my 如图：

第五章 问题及其解决方法

1、编码不熟练，经常出现漏符号或多符号，多次调试改正

2、C++不熟练，读取保存文件出错，回归课本，改正代码

第六章 心得体会（设计总结）

在课程设计过程中，我们每个人选择一个课题，认真研究，根据课堂讲授内容，借助书本，自己动手实践。这样不但有助于我们消化课堂所讲解的内容，还可以增强我们的独立思考能力和动手能力；通过编写实验代码和调试运行，我们可以逐步积累调试C程序的经验并逐渐培养我们的编程能力、用计算机解决实际问题的能力。

在课程设计过程中，我们不但有自己的独立思考，还借助各种参考文献来帮助我们完成系统。更为重要的是，我们同学之间加强了交流，在对问题的认识方面可以交换不同的意见。

数据结构课程具有比较强的理论性，同时也具有较强的可应用性和实践性。课程设计是一个重要的教学环节。我们在一般情况下都能够重视实验环节，但是容易忽略实验的总结，忽略实验报告的撰写。通过这次实验让我们明白：作为一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。只有这样，我们的综合素质才会有好的提高。

附录——源程序

1、头文件 // Huffman.h #pragma once #endif // _MSC_VER > 1000

#include

/***********************数据结构***********************/

//哈弗曼树节点 typedef struct { unsigned int weight;unsigned int parent;unsigned int lchild;unsigned int rchild;}HuffTreeNode,*HuffTree;

//字符-权值-编码映射 typedef struct { char c;unsigned int weight;char *code;}CharMapNode,*CharMap;

/*************************类定义****************************/

class Huffman

{ private: void select(int n, int &s1, int &s2);HuffTree huffTree;//哈弗曼树

CharMap chars;//字符表

int n;

//字符数

std::string text;//原文

std::string code;//编码 public:

void InputCharsWeight();void CountCharsWeight();void Decode();

void ReadTextFromFile(char *filename);void ReadCodeFromFile(char *filename);void SaveTextToFile(char *filename);void SaveCodeToFile(char *filename);void PrintCode();void MakeCharMap();void PrintText();void PrintCharCode();void PrintCharWeight();void SetCharMap(CharMap m, int number);void Encode();Huffman();virtual ~Huffman();};

2、赫夫曼编码算法 // Huffman.cpp

#include ”Huffman.h“ #include #include

using namespace std;Huffman::Huffman(){ huffTree = NULL;chars = NULL;n = 0;}

Huffman::~Huffman(){ }

void Huffman::Encode(){ code = ”“;for(string::size_type i = 0;i!= text.size();++i){

for(int j = 1;j <= n;++j)

if(chars[j].c == text[i])

code += chars[j].code;

} }

void Huffman::SetCharMap(CharMap m, int number){ chars = m;n = number;}

void Huffman::select(int n, int &s1, int &s2){ s1 = s2 = 0;for(int i = 1;i <= n;++i){

if(huffTree[i].parent!= 0)

continue;

if(s1 == 0)

s1 = i;

else if(s2 == 0)

{

if(huffTree[i].weight < huffTree[s1].weight)

{

s2 = s1;

s1 = i;

}

else

s2 = i;

}

else

{

if(huffTree[i].weight < huffTree[s1].weight)

{

s2 = s1;

s1 = i;

}

else if(huffTree[i].weight < huffTree[s2].weight)

s2 = i;

} } }

void Huffman::PrintCharWeight()

{ for(int i = 1;i <= n;++i){

switch(chars[i].c)

{

case 't':

cout << ” “;

break;

case 'n':

cout << ”“;

break;

default:

cout << chars[i].c;

break;

}

cout << ”——“ << chars[i].weight << endl;} }

void Huffman::PrintCharCode(){ for(int i = 1;i <= n;++i){

switch(chars[i].c)

{

case 't':

cout << ” “;

break;

case 'n':

cout << ”“;

break;

default:

cout << chars[i].c;

break;

}

cout << ”——“ << chars[i].code << endl;} }

void Huffman::PrintText(){ cout << text << endl;}

void Huffman::PrintCode(){ cout << code << endl;}

void Huffman::MakeCharMap(){ if(n <= 1)

return;int m = 2 * n1, s1, s2);

huffTree[s1].parent = huffTree[s2].parent = i;

huffTree[i].lchild = s1;

huffTree[i].rchild = s2;

huffTree[i].weight = huffTree[s1].weight + huffTree[s2].weight;}

char *cd = new char[n];

cd[n-1] = '';

for(i = 1;i <= n;++i)

{

int start = nstart];

strcpy(chars[i].code,&cd[start]);} delete cd;}

void Huffman::ReadTextFromFile(char *filename){ ifstream infile(filename);if(!infile){

cerr << ”无法打开文件！“ <

return;} char c;while(infile.get(c)){

text += c;} }

void Huffman::SaveCodeToFile(char *filename){ ofstream outfile(filename);if(!outfile){

cerr << ”保存文件出错！“ << endl;

return;} outfile << code;}

void Huffman::ReadCodeFromFile(char *filename)

{ ifstream infile(filename);if(!infile){

cerr << ”无法打开文件！“ <

return;} infile >> code;}

void Huffman::Decode(){ text = ”“;string::size_type i,count;for(i = 0;i < code.size();i += count){

for(count = 1;count < n;++count)

{

for(int j = 1;j <= n;++j)

if(code.substr(i, count)== chars[j].code)

{

text += chars[j].c;

goto next;

}

} next:

;} }

void Huffman::CountCharsWeight(){ if(text.empty())

return;if(chars!= NULL)

delete chars;int i = 0;n = 0;chars = new CharMapNode[2];chars[1].c = text[i];chars[1].weight = 1;

++n;for(i = 1;i!= text.size();++i){

int j;

for(j = 1;j <= n;++j)

{

if(text[i] == chars[j].c)

{

++chars[j].weight;

break;

}

}

if(j > n)

{

++n;

CharMap newchars = new CharMapNode[n + 1];

memcpy(newchars, chars, n * sizeof(CharMapNode));

delete chars;

chars = newchars;

chars[n].c = text[i];

chars[n].weight = 1;

} } }

void Huffman::SaveTextToFile(char *filename){ ofstream outfile(filename);if(!outfile){

cerr << ”保存文件出错！“ << endl;

return;} outfile << text;}

3、主函数 //main.cpp #include #include ”Huffman.h“

using namespace std;

int main(){ cout << ”

************************************************************“ << endl;cout << ”

*

*“ << endl;cout << ”

*

哈夫曼编码译码器

*“ << endl;cout << ”

*

1、打开一篇英文文章或输入一篇文章

*“<< endl;cout << ”

*

2、根据字符出现的次数以他们为权值给出哈夫曼编码方式

*“ << endl;cout << ”

*

3、对英文文章进行编码

*“ << endl;cout << ”

*

4、对编码进行译码核对正确性

*“ << endl;cout << ”

*

*“ << endl;cout << ”

************************************************************“ << endl<

cout << ”程序自动统计字符和权值“ << endl;huffman.CountCharsWeight();cout << endl;cout << ”字符及对应权值：“ << endl;huffman.PrintCharWeight();cout << endl;system(”pause“);cout << endl;

huffman.MakeCharMap();cout << ”字符及对应编码：“ << endl;huffman.PrintCharCode();cout << endl;system(”pause“);cout << endl;

cout << ”对原文进行编码：“ << endl;cout << ”原文：“ << endl;huffman.PrintText();huffman.Encode();cout << endl;cout << ”编码：“ << endl;huffman.PrintCode();huffman.SaveCodeToFile(”code.txt“);cout << endl;system(”pause“);cout << endl;

cout << ”对编码进行解码：“ << endl;huffman.ReadCodeFromFile(”code.txt“);cout << ”编码：“ << endl;huffman.PrintCode();huffman.Decode();cout << endl;cout << ”原文：“ << endl;huffman.PrintText();huffman.SaveTextToFile(”resulttext.txt");cout << endl;

return 0;}

参

考

文

献

[1] 严蔚敏，数据结构(C语言版)，清华大学出版社，2007 [2] 郑莉，C++语言程序设计（第4版），清华大学出版社，2010 [3] 谭浩强，C程序设计（第三版），清华大学出版社，2005

第三篇：数据结构哈夫曼树编码译码实验报告

【需求分析】

本实验需要设计程序，输入叶子结点和权值，建立一颗哈弗曼树，并根据哈弗曼树进行编码和译码操作。键盘中输入或者从文件中读入哈弗曼树；键盘中输入或者从源文件中读入需要编码的源文，然后将源文根据哈弗曼树的权值，译码为二进制代码。最后实现凹入显示法显示哈弗曼树。【概念设计】

本程序由HaffmanTree.h、HaffmanTree.cpp、main.cpp三个文件构成。HaffmanTree.h中定义了哈弗曼树的储存结构体HaffmanNode，里面定义了weight、parent、lchild、rchild四个变量来描述哈弗曼树的储存结构。在HaffmanTree.h中还定义了一个名为HaffmanTree的类，里面定义的是建树、编码、译码和凹入显示哈弗曼树等函数，而相关的实现代码则在HaffmanTree.cpp中给出。main.cpp中主要是实现内部函数与用户界面的对接。【详细设计】

具体代码实现如下： //HaffmanTree.h #include #include #include struct HuffmanNode //哈夫曼树的一个结点 { int weight;int parent;int lchild,rchild;};

class HuffmanTree //哈夫曼树 {

private: HuffmanNode *Node;//Node[]存放哈夫曼树

char *Info;//Info[]存放源文用到的字符——源码，如'a','b','c','d','e'，此内容可以放入结点中，不单独设数组存放

int LeafNum;//哈夫曼树的叶子个数，也是源码个数 public: HuffmanTree();~HuffmanTree();void CreateHuffmanTree();/*在内存中建立哈夫曼树，存放在Node[]中。让用户从两种建立哈夫曼树的方法中选择：

1.从键盘读入源码字符集个数，每个字符，和每个字符的权重，建立哈夫曼树，并将哈夫曼树写入文件hfmTree中。2.从文件hfmTree中读入哈夫曼树信息，建立哈夫曼树*/ void CreateHuffmanTreeFromKeyboard();void CreateHuffmanTreeFromFile();void Encoder();/*使用建立好的哈夫曼树（如果不在内存，则从文件hfmTree中读入并建立内存里的哈夫曼树），对文件ToBeTran中的正文进行编码，并将码文写入文件CodeFile中。

ToBeTran的内容可以用记事本等程序编辑产生。*/ void Decoder();/*待译码的码文存放在文件CodeFile中，使用建立好的哈夫曼树（如果不在内存，则从文件hfmTree中读入并建立内存里的哈夫曼树）将码文译码，得到的源文写入文件TextFile中，并同时输出到屏幕上。*/ void PrintCodeFile();/*将码文文件CodeFile显示在屏幕上*/ void PrintHuffmanTree();/*将哈夫曼树以直观的形式（凹入表示法，或广义表，或其他树形表示法）显示在屏幕上，同时写入文件TreePrintFile中*/ void PrintHuffmanTree_aoru(int T,int layer=1);/*凹入表示法显示哈夫曼树，由PrintHuffmanTree()调用*/ };

///////////////////////////////////////////////////////////////////HuffmanTree.cpp #include #include //为使用整型最大值 #include“HuffmanTree.h” using namespace std;

//****************************************************** HuffmanTree::HuffmanTree(){ Node=NULL;}

//****************************************************** HuffmanTree::~HuffmanTree(){ delete[]Node;} //****************************************************** void HuffmanTree::CreateHuffmanTree(){ char Choose;cout<<“你要从文件中读入哈夫曼树(按1)，还是从键盘输入哈夫曼树(按2)？”;cin>>Choose;if(Choose=='2'){//键盘输入建立哈夫曼树

CreateHuffmanTreeFromKeyboard();}//choose=='2' else { //从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树

CreateHuffmanTreeFromFile();} } //****************************************************** void HuffmanTree::CreateHuffmanTreeFromKeyboard(){

int Num;

cout<<“n请输入源码字符集个数：”;

cin>>Num;

if(Num<=1)

{

cout<<“无法建立少于2个叶子结点的哈夫曼树。nn”;

return;

}

LeafNum=Num;

Node=new HuffmanNode[2*Num-1];

Info=new char[2*Num-1];

for(int i=0;i

cout<<“请输入第”<

getchar();

Info[i]=getchar();//源文的字符存入字符数组Info[]

getchar();

cout<<“请输入该字符的权值或频度”;

cin>>Node[i].weight;//源文的字符权重存入Node[].weight

Node[i].parent=-1;

Node[i].lchild=-1;

Node[i].rchild=-1;

}

for(i=Num;i<2*Num-1;i++)

{//循环建立哈夫曼树内部结点

int pos1=-1,pos2=-1;

int max1=32767,max2=32767;

for(int j=0;j

if(Node[j].parent==-1)//是否为根结点

if(Node[j].weight

{

max2=max1;

max1=Node[j].weight;

pos2=pos1;

pos1=j;

}

else

if(Node[j].weight

{

max2=Node[j].weight;

pos2=j;

} Node[pos1].parent=i;

Node[pos2].parent=i;

Node[i].lchild=pos1;

Node[i].rchild=pos2;

Node[i].parent=-1;

Node[i].weight=Node[pos1].weight+Node[pos2].weight;

} //for

cout<<“哈夫曼树已成功构造完成。n”;

//把建立好的哈夫曼树写入文件hfmTree.dat

char ch;

cout<<“是否要替换原来的哈夫曼树文件(Y/N):”;

cin>>ch;

if(ch!='y'&&ch!='Y')return;

else

{

ofstream fop;

fop.open(“hfmTree.dat”,ios::out|ios::binary|ios::trunc);//打开文件

if(fop.fail())

{

cout<<“n哈夫曼树文件打开失败，无法将哈夫曼树写入hfmTree.dat文件。n”;

return;

}

fop.write((char*)&Num,sizeof(Num));//先写入哈夫曼树的叶子结点个数

for(i=0;i

{ //再写入源文字符集的所有字符（存储在Info[]中）

fop.write((char*)&Info[i],sizeof(Info[i]));

flush(cout);

}

for(i=0;i<2*Num-1;i++)

{ //最后写入哈夫曼树的各个结点（存储在Node[]中）

fop.write((char*)&Node[i],sizeof(Node[i]));

flush(cout);

}

fop.close();//关闭文件

cout<<“n哈夫曼树已成功写入hfmTree.dat文件。n”;

} }

//****************************************************** void HuffmanTree::CreateHuffmanTreeFromFile(){ ifstream fip;fip.open(“hfmTree.dat”,ios::binary|ios::in);if(fip.fail()){

cout<<“哈夫曼树文件hfmTree.dat打开失败，无法建立哈夫曼树。n”;

return;} fip.read((char*)&LeafNum,sizeof(LeafNum));if(LeafNum<=1){

cout<<“哈夫曼树文件中的数据有误，叶子结点个数少于2个，无法建立哈夫曼树。n”;

fip.close();

return;} Info=new char[LeafNum];Node=new HuffmanNode[2*LeafNum-1];for(int i=0;i

fip.read((char*)&Info[i],sizeof(Info[i]));for(i=0;i<2*LeafNum-1;i++)

fip.read((char*)&Node[i],sizeof(Node[i]));fip.close();cout<<“哈夫曼树已成功构造完成。n”;}

//****************************************************** void HuffmanTree::Encoder(){ if(Node==NULL){//内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树

CreateHuffmanTreeFromFile();

if(LeafNum<=1)

{

cout<<“内存无哈夫曼树。操作撤销。nn”;

return;

} }//if

char *SourceText;//字符串数组，用于存放源文

//让用户选择源文是从键盘输入，还是从源文文件ToBeTran.txt中读入

char Choose;cout<<“你要从文件中读入源文(按1)，还是从键盘输入源文(按2)？”;cin>>Choose;if(Choose=='1'){

ifstream fip1(“ToBeTran.txt”);

if(fip1.fail())

{

cout<<“源文文件打开失败!无法继续执行。n”;

return;

}

char ch;

int k=0;

while(fip1.get(ch))k++;//第一次读文件只统计文件中有多少个字符，将字符数存入k

fip1.close();

SourceText=new char[k+1];//申请存放源文的字符数组空间

ifstream fip2(“ToBeTran.txt”);//第二次读源文文件，把内容写入SourceText[]

k=0;

while(fip2.get(ch))SourceText[k++]=ch;

fip2.close();

SourceText[k]='';

cout<<“需编码的源文为：”;

cout<

string SourceBuff;

cin.ignore();

cout<<“请输入需要编码的源文(可输入任意长，按回车键结束):n”;

getline(cin,SourceBuff,'n');

int k=0;

while(SourceBuff[k]!='')

k++;

SourceText=new char[k+1];

k=0;

while(SourceBuff[k]!='')

{

SourceText[k]=SourceBuff[k];

k++;

}

SourceText[k]='';

cout<<“覆盖已有的编码原文件?（Y/N）”;

char ch;

cin>>ch;

if(ch=='y'||ch=='Y')

{

ofstream fip2;

fip2.open(“ToBeTran.txt”);

if(!fip2)

{

cerr<<“文件打开失败！”<

abort();

}

fip2<

fip2.close();

cout<<“需编码的源文已写入ToBeTran.txt中”<

} }

//开始编码

ofstream fop(“CodeFile.dat”,ios::trunc);//打开码文存放文件

char *code;code=new char[LeafNum];//存放一个源文字符的编码

int k=0;while(SourceText[k]!='')//源文串中从第一个字符开始逐个编码 {

int star=0;

char ch=SourceText[k];

for(int i=0;i

if(Info[i]==ch)//求出该文字所在的单元编号

break;

int j=i;

while(Node[j].parent!=-1)

{

j=Node[j].parent;

if(Info[Node[j].lchild]==Info[i])code[star++]='0';

else code[star++]='1';

i=j;

}

code[star]='';

for(i=0;i

{

int j=code[i];

code[i]=code[star-i-1];

code[star-i-1]=j;

} i=0;//将源文的当前字符的对应编码写入码文文件

while(code[i]!='')

{

fop<

i++;

}

k++;//源文串中的字符后移一个

} fop.close();cout<<“已完成编码，码文已写入文件CodeFile.dat中。nn”;}

//****************************************************** void HuffmanTree::Decoder(){

//如果内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树

if(Node==NULL){

CreateHuffmanTreeFromFile();

if(LeafNum<=1)

{

cout<<“内存无哈夫曼树。操作撤销。nn”;

return;

} }

//将码文从文件CodeFile.dat中读入 CodeStr[] ifstream fip1(“CodeFile.dat”);if(fip1.fail()){

cout<<“没有码文，无法译码。n”;

return;}

char* CodeStr;int k=0;char ch;while(fip1.get(ch)){

k++;} fip1.close();CodeStr=new char[k+1];ifstream fip2(“CodeFile.dat”);k=0;while(fip2.get(ch))CodeStr[k++]=ch;fip2.close();CodeStr[k]='';

cout<<“经译码得到的源文为：”;ofstream fop(“TextFile.dat”);

int j=LeafNum*2-1-1;//j指向哈夫曼树的根

int i=0;//码文从第一个符号开始，顺着哈夫曼树由根下行，按码文的当前符号决定下行到左孩子还是右孩子

while(CodeStr[i]!=''){ //下行到哈夫曼树的叶子结点处，则译出叶子结点对应的源文字符

if(CodeStr[i]=='0')j=Node[j].lchild;

else j=Node[j].rchild;

if(Node[j].rchild==-1)

{

cout<

fop<

j=LeafNum*2-1-1;

}

i++;} fop.close();

cout<<“n译码成功且已存到文件TextFile.dat中。nn”;} //****************************************************** void HuffmanTree::PrintCodeFile(){ char ch;int i=1;ifstream fip(“CodeFile.dat”);ofstream fop(“CodePrin.dat”);if(fip.fail()){

cout<<“没有码文文件，无法显示码文文件内容。n”;

return;} while(fip.get(ch)){

cout<

fop<

if(i==50)

{

cout<

fop<

i=0;

}

i++;} cout<

if(Node==NULL){

CreateHuffmanTreeFromFile();

if(LeafNum<=1)

{

cout<<“内存无哈夫曼树。操作撤销。nn”;

return;

}

}

ofstream fop(“TreePrint.dat”,ios_base::trunc);fop.close();PrintHuffmanTree_aoru(2*LeafNum-1-1,0);return;} //****************************************************** void HuffmanTree::PrintHuffmanTree_aoru(int T,int layer){ for(int i=0;i

}

///////////////////////////////////////////////////////////////////main.cpp #include“HuffmanTree.h” #include #include

using namespace std;

int main(){ HuffmanTree huftree;char Choose;while(1){

cout<<“nn**********************欢迎使用哈夫曼编码/译码系统***********************”<

cout<<“您可以进行以下操作:”<

cout<<“1 建立哈夫曼树 3 译码(码文已在文件CodeFile中)5 显示哈夫曼树”<

cout<<“2 编码(源文已在文件ToBeTran中，或键盘输入)4 显示码文 6 退出 ”<

cout<<“请选择一个操作:”;

cin>>Choose;

switch(Choose)

{

case '1':

huftree.CreateHuffmanTree();

break;

case '2':

huftree.Encoder();

break;

case '3':

huftree.Decoder();

break;

case '4':

huftree.PrintCodeFile();

break;

case '5':

huftree.PrintHuffmanTree();

break;

case '6':

cout<<“n*************************统!***********************nn”;

system(“pause”);

return 0;

}//switch }//while }//main

感谢使用本系【用户手册】

进入哈弗曼树系统，出现以下界面：

1建立弗曼树

2、编码（源文中读入，键盘输入）

3、译码

4、显示码文

5、显示哈弗曼树

6、退出

用户根据该提示，选择前面数字，就能进入各个功能函数，实现函数功能。【运行结果】

截图一：

截图二：

截图三：

【心得体会】

本实验是有老师提供模板，然后自己增加功能函数的代码实现的。因此，在完成未完成的功能函数之前还必须要细心阅读所给出代码，整体观察各个部分之前的联系，搞清楚已给出和未完成的代码功能之后，才根据算法，设计出该功能的函数代码。

在完成实验时，有发现老师所给出代码也有纰漏的地方，如在源

文件读入的时候，多出了一个值，得要增加下表减这个代码来去掉。还有就是在译码的时候，由于变量定义的混淆，在编译的时候通过，但执行时却出现意料不到的结果，在自己细心观察、思考之前也还没找出错误之处。后来通过请教老师，在和老师讨论检查之后才知道了错误之所在，最后改正错误。实验成功完成。

【参考文献】

数据结构与算法（课本）

C++语言基础

第四篇：哈夫曼编码的JAVA实现课程设计

哈夫曼编码的JAVA实现课程设计

目 录

摘 要.............................................................................................................................2

一、问题综述...............................................................................................................2

二、求解方法介绍.......................................................................................................3

三、实验步骤及结果分析...........................................................................................4

四、程序设计源代码...................................................................................................5 参考文献.......................................................................................................................8

摘要

利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本，试用java语言设计一个哈夫曼编码系统。通过本课程设计，应使学生掌握哈夫曼编码的特点、储存方法和基本原理，培养学生利用java语言正确编写程序及调试程序的能力，运用数据结构知识解决实际问题的能力。

关键字：哈夫曼编码 JAVA语言 类 方法

一、问题综述 哈夫曼编码的算法思想 哈夫曼编码也称前缀编码，它是根据每个字符出现的频率而进行编码的，要求任一字符的编码都不是其它任意字符编码的前缀且字符编码的总长度为最短。它主要应用于通信及数据的传送以及对信息的压缩处理等方面。哈夫曼编码的基础是依据字符出现的频率值而构造一棵哈夫曼树，从而实现最短的编码表示最常用的数据块或出现频率最高的数据，具体的方法是： 1.1 建立哈夫曼树

把N 个字符出现的频率值作为字符的权值,然后依据下列步骤建立哈夫曼树。

1.1.1 由N 个权值分别作N 棵树的根结点而形成一个森林。

1.1.2 从中选择两棵根值最小的树T1 和T2 组成一棵以结点T 为根结点的增长树，根结点T = T1 + T2 ,即新树的根值为原来两棵树的根值之和，而T1 和T2 分别为增长树的左右子树。

1.1.3 把这棵新树T 加入到森林中，把原来的两棵树T1 和T2 从森林中删除。

1.1.4 重复1.1.2～1.1.3 步，直到合并成一棵树为止。1.2 生成各字符的哈夫曼编码 在上面形成的哈夫曼树中，各个字符的权值结点都是叶子结点，从叶子结点开始向根搜索，如果是双亲的左分支，则用“0”标记，右分支用“1”标记，从叶子结点到根结点所经过的分支编码“0”、“1”的组合序列就是各字符的哈夫曼编码。构造哈夫曼树的算法

1）对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,..., Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。

2）在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。

3）从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。4）重复2）和3），直到集合F中只有一棵二叉树为止。

例如，对于4个权值为1、3、5、7的节点构造一棵哈夫曼树，其构造过程如下图所示：

图1 构造哈夫曼树的过程示例

二、求解方法介绍

以往的哈夫曼编码程序实现都是利用PASCAL 或C 语言描述的，而这两门语言都有相应的指针类型来解决，实现起来较为容易，但是，JAVA语言是面向对象的编程语言，没有提供指针类型，所以在实现上应该结合JAVA 的应用环境，采用静态的方法解决。同时，JAVA 语言是具有平台无关性的网络编程语言，用JAVA 语言实现哈夫曼编码不论在教学中或是在实际应用中都有一定的意义。

本程序是用哈夫曼树来实现哈夫曼编码的功能，根据输入的报文进行分析，建立哈夫曼树。统计输入字符串的长度，并对每个字符的频度进行计算。对每个字符及相应的频度作为叶结点建立哈夫曼树。哈夫曼树的建立过程采用把结点看作树每次选最小的两个建立树，并把他们的频度相加，再继续选取最小的两个数建立，直到所有的结点建立完，才形成完整的哈夫曼树。接下来是对没个结点进行编码，从第一个结点开始看它的双亲，若它双亲做左孩子则记0，若是右孩子则记1，依次往上推，直到哈夫曼的根结点为止。记录编码打印出来。

为了体现程序中各个功能的独立性，结合JAVA 语言的编程要求，对程序中所用到的类和方法进行说明：

公共类Tree：组成哈夫曼树的最小单元。其成员变量有：

1.1 lchild：最小单元的左孩子。1.2 rchild：最小单元的右孩子。1.3 parents：最小单元的双亲。公共类Huffman：描述哈夫曼编码的整个过程,其成员变量有： 2.1 numsMo：储存要进行编码的一组数。

2.2 nums：临时储存要进行编码的这组数，会随着后面的调用而变化。2.3 trees：储存哈夫曼树，由若干最小单元构成。2.4 temp：中间变量，是字符串类型。3 核心方法及流程 3.1 main 方法：用于程序的执行入口。其中定义了一个Huff 类实体，调用方法start()完成数组初始排序，实现哈夫曼编码等一系列的操作。

3.2 addNum 方法：用于方法初始化给定的要进行编码的数组，数组通过控制台键盘录入。

3.3 minTo 方法：在一组数中选择最小的两个，按递增顺序返回。3.4 compareNum 方法：是公共类Huffman的核心算法之一，该方法是将一组树形成哈夫曼树，左孩子为较小值。

3.5 print 方法：是公共类Huffman的核心算法之一，该方法利用递归打印出编码。其流程图如下：

三、实验步骤及结果分析 测试数据： 0.01 0.03 0.07 0.13 0.19 0.26 0.31

程序运行：

请输入一组数，中间用空格分隔： 0.01 0.03 0.07 0.13 0.19 0.26 0.31

输出结果为：

0.01 : 01000 码长：5 0.03 : 01001 码长：5 0.07 : 0101 码长：4 0.13 : 011 码长：3 0.19 : 00 码长：2 0.26 : 10 码长：2 0.31 : 11 码长：2

心得体会：

在本次的课程设计中，就在编写好源代码后的调试中出现了不少的错误，遇到了很多麻烦及困难。我的调试及其中的错误和我最终找出错误，修改为正确的能够执行的程序中，通过分析，我学到了：在递归调用方法时最好不要有返回值，否则会使程序变得逻辑混乱，复杂难懂；当从叶结点向上编码时，根据本程序的特点会有可能重复的tree，所以要分成同tree和不同tree进行不同的逻辑编程。

通过本次的课程设计，我学习了很多在上课没懂的知识，并对求哈夫曼树及哈夫曼编码的算法有了更加深刻的了解，更巩固了课堂中学习有关于哈夫曼编码的知识，真正学会了一种算法。当求解一个算法时，不是拿到问题就不加思索地做，而是首先要先对它有个大概的了解，接着再详细地分析每一不怎么做，无论自己以前是否有处理过相似的问题，只要按照以上的步骤，必定会顺利地做出来。

四、程序设计源代码

import java.util.ArrayList;import java.util.List;import java.util.Scanner;

public class Huffman { private List nums;private List numsMo;private List trees;private String temp;

public Huffman(){

nums = new ArrayList();

numsMo = new ArrayList();

trees = new ArrayList();temp=“";} public void addNums(){// 给定一组数 System.out.println(”请输入一组数，中间用空格分隔：“);

Scanner sca = new Scanner(System.in);

String str = sca.nextLine();

String[] strs = str.split(” “);

for(int i = 0;i < strs.length;i++){

nums.add(Double.parseDouble(strs[i]));

numsMo.add(Double.parseDouble(strs[i]));

} }

public void compareNum(List nums,List trees){// 递归算法

} double[] min = new double[2];if(nums.size()>1){ min = minTwo(nums);Tree t = new Tree(min[0],min[1],min[0]+min[1]);nums.remove(Double.valueOf(min[0]));nums.remove(Double.valueOf(min[1]));nums.add(min[0]+min[1]);trees.add(t);compareNum(nums,trees);} public void print(double num){// 递归打印编码

for(Tree t : trees){ if(num == t.getRchild()){

temp = 1+temp;

print(t.getParents());

break;}else if(num == t.getLchild()){

temp = 0+temp;

print(t.getParents());

break;}

} }

public void write(double d){ temp = ”“;System.out.print(d+” : “);print(d);System.out.print(temp);} public double[] minTwo(List nums){// 在一组数中System.out.println(” 码长："+temp.length());选则最小的两个，按递增排序返回

Double temp = 0.0;

for(int j = 0;j < 2;j++){

for(int i = 1;i < nums.size();i++){

if(nums.get(i1));

nums.set(i-1, temp);

}

}

}

double[] n = {nums.get(nums.size()-1),nums.get(nums.size()-2)};

return n;}

public void start(){

addNums();

compareNum(nums,trees);

while(numsMo.size()>1){

double[] mins = minTwo(numsMo);

if(mins[0]!=mins[1]){

numsMo.remove(Double.valueOf(mins[0]));

write(mins[0]);

}

}

if(!numsMo.isEmpty()){

write(numsMo.get(0));

} }

public static void main(String[] args){

new Huffman().start();} }

参考文献

1(美)Stuart Reges，(美)Marty Stepp著 陈志等译，java程序设计教程，机械工业出版社,2008

2（英）David J.C.Mackay著 肖明波，席斌，许芳，王建新译，信息论、推理与学习算法，高等教育出版社，2006

第五篇：数据结构实验三哈夫曼树实验报告

实验报告3：哈夫曼编/译码器

题目：哈夫曼编/译码器

一、题目要求：

写一个哈夫曼码的编/译码系统，要求能对要传输的报文进行编码和解码。构造哈夫曼树时，权值小的放左子树，权值大的放右子树，编码时右子树编码为1，左子树编码为0.二、概要设计：

数据结构：

typedef struct { int bit[MAXBIT];int start;} HCodeType;/* 编码结构体 */

typedef struct { int weight;int parent;int lchild;int rchild;char value;} HNode;/* 结点结构体 */ 函数：

void DEMONHuffmanTree(HNode HuffNode[MAXNODE], int n)作用：构造一个哈夫曼树，并循环构建 int main()作用：运用已经构建好的哈弗曼树，进行节点的处理，达到成功解码编译

三、详细设计： 哈夫曼树的建立：

void DEMONHuffmanTree(HNode HuffNode[MAXNODE], int n){

int i = 0, j, m1, m2, x1, x2;

char x;

/* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */

while(i

{

HuffNode[i].weight = 0;//权值 实验报告3：哈夫曼编/译码器

HuffNode[i].parent =-1;

HuffNode[i].lchild =-1;

HuffNode[i].rchild =-1;

scanf(“%c”,&x);

scanf(“%c”,&HuffNode[i].value);//实际值，可根据情况替换为字母

i++;

}

/* 输入 n 个叶子结点的权值 */ scanf(“%c”,&x);for(i=0;i

{

scanf(“%d”, &HuffNode[i].weight);

}

for(i=n;i<2*n-1;i++)

{

HuffNode[i].weight = 0;//权值

HuffNode[i].parent =-1;

HuffNode[i].lchild =-1;

HuffNode[i].rchild =-1;

HuffNode[i].value=i;

}

/* 循环构造 Huffman 树 */

for(i=0;i

{

m1=m2=MAXQZ;

// m1、m2中存放两个无父结点且结点权值最小的两个结点

x1=x2=0;//找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树

for(j=0;j

{

if(HuffNode[j].weight < m1 && HuffNode[j].parent==-1)

{

m2=m1;//m1中是最小

x2=x1;

m1=HuffNode[j].weight;

x1=j;

}

else if(HuffNode[j].weight < m2 && HuffNode[j].parent==-1)

{

m2=HuffNode[j].weight;

x2=j;

}

实验报告3：哈夫曼编/译码器

} /* end for */

/* 设置找到的两个子结点 x1、x2 的父结点信息 */

HuffNode[x1].parent = n+i;

HuffNode[x2].parent = n+i;

HuffNode[n+i].weight = HuffNode[x1].weight + HuffNode[x2].weight;

HuffNode[n+i].lchild = x1;

HuffNode[n+i].rchild = x2;

} }

叶子节点的哈夫曼编码的保存： for(j=cd.start+1;j

HuffCode[i].bit[j] = cd.bit[j];

HuffCode[i].start = cd.start;

主函数展示： int main(){

HNode HuffNode[MAXNODE];

HCodeType HuffCode[MAXLEAF],cd;

int i, j, c, p, n,k=0;

char wen[100];

char z;

scanf(“%d”, &n);

HuffmanTree(HuffNode, n);

for(i=0;i < n;i++)

{

cd.start = n-1;

c = i;

p = HuffNode[c].parent;

while(p!=-1)

/* 父结点存在 */

{

if(HuffNode[p].lchild == c)

cd.bit[cd.start] = 0;

else

cd.bit[cd.start] = 1;

cd.start--;

/* 求编码的低一位 */

c=p;

p=HuffNode[c].parent;

/* 设置下一循环条件 */

} /* end while */ 实验报告3：哈夫曼编/译码器

for(j=cd.start+1;j

HuffCode[i].bit[j] = cd.bit[j];

HuffCode[i].start = cd.start;

} /* end for */

z=getchar();

z=getchar();

for(;z!='n';z=getchar()){

wen[k++]=z;

for(i=0;i

{

if(z==HuffNode[i].value)

{

for(j=HuffCode[i].start+1;j < n;j++)

printf(“%d”, HuffCode[i].bit[j]);

break;

}

else;

} } printf(“n”);for(i=0;i

{

printf(“%c”,wen[i]);

}

printf(“n”);

return 0;}

四、调试分析与心得体会：

虽然哈夫曼树的建立有书上的参考，但是实际写整个代码的时候还是问题重重。首先就是哈弗曼树忘记了初始的赋值，导致最后出现了问题。这样的错误还是很容易解决，但是之后就出现了WA的情况。在同学的帮助下，最后发现是因为在选取节点的时候，循环出现了问题，虽然看起来编译没有错，但是边缘情况就会出现数据错误，这个还是很令人警醒，而这种思考的不全面的问题，在debug的过程中会耗去大量的时间，这是要注意的。

五、用户操作说明：

输入表示字符集大小为n（n <= 100）的正整数，以及n个字符和n个权值（正整数，值

越大表示该字符出现的概率越大）； 输入串长小于或等于100的目标报文。实验报告3：哈夫曼编/译码器

六、运行结果：

附带自己的算法完成的结果图，可以通过Prt Sc和图片编辑器获得；

实验报告3：哈夫曼编/译码器

七、附录：

#include #include

#define MAXBIT 100 #define MAXLEAF 30 #define MAXNODE MAXLEAF*2-1 #define MAXQZ 10000 //权值

typedef struct { int bit[MAXBIT];int start;} HCodeType;/* 编码结构体 */

实验报告3：哈夫曼编/译码器 typedef struct { int weight;int parent;int lchild;int rchild;char value;} HNode;/* 结点结构体 */

/* 构造一颗哈夫曼树 */ void HuffmanTree(HNode HuffNode[MAXNODE], int n){

int i = 0, j, m1, m2, x1, x2;char x;/* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */ while(i

scanf(“%c”,&x);scanf(“%c”,&HuffNode[i].value);//实际值，可根据情况替换为字母 i++;}

/* 输入 n 个叶子结点的权值 */ scanf(“%c”,&x);i = 0;while(i

for(i=n;i<2*n-1;i++){ HuffNode[i].weight = 0;//权值 HuffNode[i].parent =-1;HuffNode[i].lchild =-1;HuffNode[i].rchild =-1;HuffNode[i].value=i;}

实验报告3：哈夫曼编/译码器

/* 循环构造 Huffman 树 */ for(i=0;i

x1=x2=0;//找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树 for(j=0;j

} }

int main(){

HNode HuffNode[MAXNODE];/* 定义一个结点结构体数组 */ HCodeType HuffCode[MAXLEAF],cd;/* 定义一个编码结构体数组，同时定义一个临时变量来存放求解编码时的信息 */ int i, j, c, p, n,k=0;char wen[100];char z;scanf(“%d”, &n);HuffmanTree(HuffNode, n);8 3：哈夫曼编/译码器

for(i=0;i < n;i++){ cd.start = n-1;c = i;p = HuffNode[c].parent;while(p!=-1)/* 父结点存在 */ { if(HuffNode[p].lchild == c)cd.bit[cd.start] = 0;else cd.bit[cd.start] = 1;cd.start--;/* 求编码的低一位 */ c=p;p=HuffNode[c].parent;/* 设置下一循环条件 */ } /* end while */

/* 保存求出的每个叶结点的哈夫曼编码和编码的起始位 */ for(j=cd.start+1;j

z=getchar();z=getchar();for(;z!='n';z=getchar()){

wen[k++]=z;

for(i=0;i

{

if(z==HuffNode[i].value)

{

for(j=HuffCode[i].start+1;j < n;j++)

printf(“%d”, HuffCode[i].bit[j]);

break;

}

else;

} } printf(“n”);i = 0;while(i

{

printf(“%c”,wen[i]);实验报告 实验报告3：哈夫曼编/译码器

}

printf(“n”);return 0;}  i++;

实验报告3：哈夫曼编/译码器

上机实习要求：

1、认真准备，按时参加上机实习，不得无故缺席，抽查不到者扣分；

2、独立完成老师布置的题目，上机完成程序并调试正确，课后完成实验报告的编写，将上机程序和实验报告打包后交给辅导老师评定分数，实验报告要求和评分标准见后面；

3、提倡创新，可对课本上提供的算法进行改进；

4、上机程序必须在程序中提供足够的注释，详细为好。

5、实验报告不用写出算法，只要写出对课程设计的见解，如对某一算法的改进思想，算法设计思想，调试算法过程中出现的问题及改进方法，调试程序的体会等。只要是自己编程和调试就会写出相应的报告。

考核标准

1、机试程序和结果、设计报告缺一不可，机试程序和结果压缩打包后上交给辅导老师，设计报告主要是自己的设计过程和调试心得，报告中不必附带全部的源程序）。机试成绩占总成绩60%，设计报告占40%。

2、上机程序和设计报告必须独立完成，严禁抄袭，若发现雷同，原创者视上机结果最多60分，抄袭者按0分计，若找不到原创，都按0分计。

所以原创同学注意，我们的检查专门针对抄袭情况，一旦发现将严肃处理！！