树和哈夫曼树实验报告

第一篇：树和哈夫曼树实验报告

树和哈夫曼树实验报告

一．实验目的

练习树和哈夫曼树的有关操作，和各个算法程序，理解哈夫曼树的编码和译码 二．实验环境

Microsoft visual c++ 三．实验问题描述

1.问题描述：建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序和后序），打印输出遍历结果。

基本要求：从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立），并将此二叉树按照“树状形式”打印输出，然后对其进行遍历（先序、中序和后序），最后将遍历结果打印输出。在遍历算法中要求至少有一种遍历采用非递归方法。测试数据：

ABCØØDEØGØØFØØØ（其中Ø表示空格字符）输出结果为： 先序：ABCDEGF 先序：CBEGDFA 先序：CGEFDBA 2.问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接受端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。基本要求：(至少完成功能1-2）一个完整的系统应具有以下功能： I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。基本要求：

E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。

D：译码（Decoding)。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。

P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。T：印哈夫曼树（TreePrinting）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。测试数据：

设权值w=（5，29，7，8，14，23，3，11），n=8。

按照字符‘0’或‘1’确定找左孩子或右孩子，则权值对应的编码为：

5：0001，29：11，7：1110，8：1111 14：110，23：01，3：0000，11：001 用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。四．实验主要程序流

实验题目一主要程序：

1．void CreatBiTree(BitTree *bt)//用扩展先序遍历序列创建二叉树，如果是#当前树根置为空，否则申请一个新节点// { char ch;ch=getchar();if(ch=='.')*bt=NULL;else { *bt=(BitTree)malloc(sizeof(BitNode));(*bt)->data=ch;CreatBiTree(&((*bt)->LChild));CreatBiTree(&((*bt)->RChild));} } 2．void Visit(char ch)//访问根节点 { printf(“%c ”,ch);} 3．

void PreOrder(BitTree root){ if(root!=NULL){ Visit(root->data);PreOrder(root->LChild);PreOrder(root->RChild);} } 4． void InOrder(BitTree root){ if(root!=NULL){ InOrder(root->LChild);Visit(root->data);InOrder(root->RChild);} } 5．int PostTreeDepth(BitTree bt)//后序遍历求二叉树的高度递归算法// { int hl,hr,max;if(bt!=NULL){ hl=PostTreeDepth(bt->LChild);//求左子树的深度

hr=PostTreeDepth(bt->RChild);//求右子树的深度

max=hl>hr?hl:hr;//得到左、右子树深度较大者

return(max+1);//返回树的深度 } else return(0);//如果是空树，则返回0 } 6．void PrintTree(BitTree Boot,int nLayer)//按竖向树状打印的二叉树 // { int i;if(Boot==NULL)return;PrintTree(Boot->RChild,nLayer+1);for(i=0;idata);PrintTree(Boot->LChild,nLayer+1);} 7．void main(){ BitTree T;int h;int layer;int treeleaf;layer=0;printf(“请输入二叉树中的元素(以扩展先序遍历序列输入,其中.代表空子树):n”);CreatBiTree(&T);printf(“先序遍历序列为:”);PreOrder(T);printf(“n中序遍历序列为:”);InOrder(T);printf(“n后序遍历序列为:”);PostOrder(T);h=PostTreeDepth(T);printf(“此二叉树的深度为:%dn”,h);printf(“此二叉树的横向显示为：n”);PrintTree(T,layer);} 实验二主要程序流： 1．int main(){ HuffmanTree huftree;char Choose;while(1){ cout<<“n**********************欢迎使用哈夫曼编码/译码系统**********************n”;cout<<“*您可以进行以下操作: *n”;cout<<“*1.建立哈夫曼树 *n”;cout<<“*2.编码(源文已在文件ToBeTra中，或键盘输入)*n”;cout<<“* 3.译码(码文已在文件CodeFile中)*n”;cout<<“* 4.显示码文 *n”;cout<<“* 5.显示哈夫曼树 *n”;cout<<“* 6.退出 *n”;cout<<“***********************************************************************n”;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 2．// 建立哈夫曼树函数

// 函数功能：建立哈夫曼树（调用键盘建立哈夫曼树或调用从文件建立哈夫曼树的函数）void HuffmanTree::CreateHuffmanTree(){char Choose;cout<<“你要从文件中读入哈夫曼树(按1)，还是从键盘输入哈夫曼树(按2)？”;cin>>Choose;if(Choose=='2'){ //键盘输入建立哈夫曼树 CreateHuffmanTreeFromKeyboard();}//choose=='2' else { //从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树

CreateHuffmanTreeFromFile();} } 3.// 从键盘建立哈夫曼树函数

// 函数功能：从键盘建立哈夫曼树 //函数参数：无 //参数返回值：无

void HuffmanTree::CreateHuffmanTreeFromKeyboard(){ int Num;cout<<“n请输入源码字符集个数：”;cin>>Num;if(Num<=1){ cout<<“无法建立少于2个叶子结点的哈夫曼树。nn”;return;} LeafNum=Num;Node=new HuffmanNode[2*Num-1];for(int i=0;i

cout<<“请输入第”<>Node[i].weight;//源文的字符权重存入Node[].weight Node[i].parent=-1;Node[i].lchild=-1;Node[i].rchild=-1;Node[i].code=“”;} for(int j=Num;j<2*Num-1;j++){//循环建立哈夫曼树内部结点

int pos1,pos2;int max1,max2;pos2=pos1=j;max2=max1=numeric_limits::max();//在所有子树的根结点中，选权重最小的两个根结点，pos1最后应指向权重最小的根结点的下标

//pos2最后应指向权重第二小的根结点的下标 //max1存放当前找到的权重最小的根结点的权重 //max2存放当前找到的权重第二小的根结点的权重

for(int k=j-1;k>=0;k--){ if(Node[k].parent==-1){//如果是某棵子树的根结点

if(Node[k].weight

max2=max1;max1=Node[k].weight;pos2=pos1;pos1=k;} else if(Node[k].weight

max2=Node[k].weight;pos2=k;} }//if(Node[j].parent==-1)} //for //在下标i处新构造一个哈夫曼树的内部结点，其左、右孩子就是以上pos1、pos2所指向的结点

Node[pos1].parent=j;Node[pos2].parent=j;Node[j].lchild=pos1;Node[j].rchild=pos2;Node[j].parent=-1;Node[j].weight=Node[pos1].weight+Node[pos2].weight;} //for

//产生所有叶子结点中字符的编码

for(int m=0;m

int j=m;int j1;while(Node[j].parent!=-1){ //从叶结点开始往根结点走，每往上走一层，就产生一位编码存入code[] j1=Node[j].parent;if(Node[j1].lchild==j)Node[m].code.insert(0,“0”);else Node[m].code.insert(0,“1”);j=j1;}} cout<<“哈夫曼树已成功构造完成。n”;

//把建立好的哈夫曼树写入文件hfmTree.dat char ch;cout<<“是否要替换原来的哈夫曼树文件(Y/N):”;cin>>ch;if(ch!='y'&&ch!='Y')return;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(int n=0;n<2*Num-1;n++){ //最后写入哈夫曼树的各个结点（存储在Node[]中）

fop.write((char*)&Node[n],sizeof(Node[n]));flush(cout);} fop.close();//关闭文件

cout<<“n哈夫曼树已成功写入hfmTree.dat文件。n”;} 4.// 从文件建立哈夫曼树函数

// 函数功能：从文件建立哈夫曼树 //函数参数：无 //参数返回值：无

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;} Node=new HuffmanNode[2*LeafNum-1];for(int i=0;i<2*LeafNum-1;i++)fip.read((char*)&Node[i],sizeof(Node[i]));fip.close();cout<<“哈夫曼树已从文件成功构造完成。n”;} 5.// 编码函数

// 函数功能：为哈夫曼树编码 //函数参数：无 //参数返回值：无

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]='';} else { //从键盘输入源文

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<<“需编码的源文为：”;cout<

ofstream fop(“CodeFile.dat”,ios::trunc);//打开码文存放文件 int k=0;while(SourceText[k]!='')//源文串中从第一个字符开始逐个编码 { int i;for(i=0;i

if(Node[i].sourcecode==SourceText[k]){ //将对应编码写入码文文件

fop<=LeafNum){ cout<<“源文中存在不可编码的字符。无法继续执行。n”<

// 函数功能：对哈夫曼树进行译码 //函数参数：无 //参数返回值：无

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){ //因为哈夫曼树没有度为1的结点，所以此条件等同于Node[j]为叶结点

cout<

fop<

} i++;} fop.close();

cout<<“n译码成功且已存到文件TextFile.dat中。nn”;} 7.// 输出码文函数

// 函数功能：从文件中输出哈夫曼树的码文 //函数参数：无 //参数返回值：无

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<

// 函数功能：从内存或文件中直接输出哈夫曼树 //函数参数：无 //参数返回值：无

void HuffmanTree::PrintHuffmanTree(){ //如果内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树 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);return;}

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

题目：哈夫曼编/译码器

一、题目要求：

写一个哈夫曼码的编/译码系统，要求能对要传输的报文进行编码和解码。构造哈夫曼树时，权值小的放左子树，权值大的放右子树，编码时右子树编码为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;//权值

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;

}

} /* 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 */

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的目标报文。

六、运行结果：

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

七、附录：

#include #include

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

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

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;}

/* 循环构造 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

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]);

}

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

上机实习要求：

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

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

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

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

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

考核标准

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

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

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

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

实验报告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分计。

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

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

【需求分析】

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

本程序由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++语言基础

第五篇：哈夫曼树及应用

常熟理工学院微课教学比赛教学设计

1、课程基本信息

课程名称：哈夫曼树及应用

所属课程：数据结构与算法 课程所属专业：软件工程

适用专业：计算机类 选用教材：严蔚敏，吴伟明编著《数据结构（C语言版）》北京：清华大学出版社，2007 主讲人：周思林

时长：15分钟 所属学校：常熟理工学院

所属院系：计算机科学与工程学院

2.教学背景

《数据结构与算法》课程是计算机类专业的学科基础课程，本节微课“哈夫曼树及应用”属于数据结构课程中的“树与二叉树”章节中的重点及难点。2.1《数据结构与算法》课程简介及特点

《数据结构与算法》课程是计算机类专业的学科基础课程，同时也是计算机类专业的核心课程。课程的主要目标是使学生理解和掌握基本数据结构的概念、经典算法的思想及实现方法，具备为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作算法的能力。数据结构与算法课程的学习也是复杂程序设计的训练过程，通过算法设计和实践，培养学生的数据抽象和复杂程序设计能力。

《数据结构与算法》课程由线性结构、树形结构、图状结构三种逻辑结构和查找、排序算法为主体，结合应用型本科院校特点，通过实践理解和掌握基本数据结构与算法，在实践中提高学生的专业素养和专业技能。2.2本节微课课程特点

“树与二叉树——哈夫曼树及应用”是《数据结构与算法》课程中第六章“树与二叉树”的核心内容之一，同时也是该章节的教学难点。

本节微课采用案例驱动法进行教学，调动学生的学习积极性，引导学生发现问题、思考问题、解决问题，利用形象的多媒体动画展示案例的执行过程，将哈夫曼树及编码复杂的程序结构趣味化、形象化。由发送报文问题引入课程，循序渐进的介绍哈夫曼树的概念、逻辑特性、存储结构和算法实现，使学生掌握哈夫曼树及编码的基本概念和算法，提升学生的程序设计及逻辑思维能力。

3.教学设计

3.1教学目的

通过本节微课的学习，培养学生以下几个方面的能力：（1）理解哈夫曼树的应用范围和场景，并能灵活运用；

（2）掌握哈夫曼树及编码的概念、求解算法基本思想，针对实例，能构造哈夫曼树，求解哈夫曼编码；

（3）掌握哈夫曼树的存储结构，理解静态三叉链表结构；

（4）掌握哈夫曼树及编码的求解算法，并能在实验中实现并验证算法（难点）；

根据学生理论基础及程序编码能力，本微课教学目标分为三个水平：合格、中等、优秀，具体标准如下：

合格水平：熟练掌握哈夫曼树及编码的基本概念，能构造哈夫曼树，求解哈夫曼编码。中等水平：掌握概念和算法思想的基础上，能上机实现验证哈夫曼树及编码的求解过程。优秀水平：在上机实现算法的基础上，能理论联系实际，利用算法解决实际问题。3.2教学内容

树与二叉树中哈夫曼树的构造和哈夫曼编码的求解。（1）问题引入；

（2）哈夫曼树的定义；（3）哈夫曼树的构造；（4）哈夫曼编码的定义；（5）算法实现。3.3教学重点及难点

教学重点：哈夫曼树及编码求解的算法思想。教学难点：哈夫曼树的存储结构，算法的实现。3.4教学方法

本微课内容在算法思想上较为容易，但在具体实现上具有一定难度，因此采用启发式教学和案例驱动式教学相结合的方法，提出问题引入课题，通过实例求解哈夫曼树，循序渐进求解哈夫曼编码，通过多次提问的方式充分调动学生的学习积极性，使用动画的形式演示实例的求解过程，增强课堂的形象性及趣味性，增加课堂容量。

课程设置由问题引入、哈夫曼树的概念、哈夫曼树的构造、哈夫曼编码、算法的实现共同组成，由浅入深，由理论到实践，实现微课课堂的完整性和连贯性。

（1）问题引入

由报文传送问题引入，如何来构建传送效率高，即报文长度最短的二进制编码。哈夫曼编码也常用在数据压缩中，是一种非常有效的压缩方法。

问题：如何使报文长度最短？（2）哈夫曼树的定义

针对给出的二叉树实例T，回顾二叉树的基本概念，树的根节点、叶子结点，同时引入新的概念，结点的权值、路径长度、结点的带权路径长度，树的带权路径长度WPL。

分析实例，相同叶子结点权值，不同树的组成形态，WPL权值不一定，引出哈夫曼树的定义：带权路径长度最小的二叉树。

问题：如何构造哈夫曼树？（3）哈夫曼树的构造

通过二叉树的实例引出哈夫曼树的构造原则和哈夫曼树的构造思想。

通过流程图的方式逐步介绍哈夫曼树的构造方法，利用标注给出每步详细事项。通过动画的方式，逐步介绍以7、9、5、6、2为叶子结点的哈夫曼树构造过程。问题：哈夫曼树是否唯一？（4）哈夫曼编码

问题：哈夫曼树中是否存在度为1的结点？ 分析二进制编码和哈夫曼树的特点，讲解哈夫曼编码的求解过程。通过动画演示哈夫曼树进行“0”“1”编码的过程从而求解出哈夫曼编码。问题：n个叶子结点的哈夫曼树总共有多少结点？引导出哈夫曼树的存储结构。

（5）算法实现

分析：在哈夫曼树的构造过程中，需要用到孩子和双亲的信息，因此存储结构中需要保存双亲及左右孩子的信息，采用三叉链表来表示，同时在求解编码过程需要从根到叶子结点，因此采用静态链表作为存储结构。

具体实现分以下部分进行：

a：根据叶子结点给静态三叉链表赋初值；

b：在静态三叉链表中依次构造根权值为7、13、16、29的节点，删除所选两棵树的操作为修改该结点双亲的值；

c：产生哈夫曼编码，针对静态三叉链表的存储结构内容，从叶子结点a开始，依次找到双亲信息，并获得哈夫曼编码的逆序序列。

提炼出哈夫曼编码的产生方法，结合程序代码进行详细讲解。总结本次课程主要内容，提出课后思考题。

4、教学总结

本次微课由报文传送引出主题，由理论到实现，结合形象的动画演示循序渐进的描述了哈夫曼树和编码的定义与实现。通过问题导入和案例驱动式教学方法的使用，使学生难以理解的二叉树结构与算法形象化、趣味化。通过实例的讲解，使学生快速掌握了哈夫曼树及哈夫曼编码的算法思想，再由实例结合存储结构的方式，让学生理解哈夫曼树的相关程序设计，提升学生的学习兴趣，增强学生逻辑结构分析能力和程序设计能力。