哈夫曼树实验报告_2.doc

PAGE 1软件 PAGE 1 第 第 PAGE 1 页 哈夫曼树及其应用实验报告 实验 四 哈夫曼树及其的应用 一、实验目的 1．在二叉树基本操作的基础上，掌握对二叉树的一些其它操作的具体实现方法。 2.掌握构造哈夫曼树以及哈夫曼编码的方法。 3、熟练掌握哈夫曼树（最优二叉树）特征及其应用 二、实验内容 题目一、哈夫曼树和哈夫曼编码： 从终端输入若干个字符，统计（或指定）字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，然后对各字符进行哈夫曼编码。 设计要求： ⑴ 哈夫曼殊和哈夫曼编码的存储表示参考教材事例 ⑵ 在程序中构造四个子程序为 ① int freqchar(char *text, HTree *t) /*统计字符出现的频率*/ ② int createhtree(HTree *t) /*根据字符出现的频率建立哈夫曼树*/ ③ void coding(HTree *t,int head_i,char *code) /*对哈夫曼树进行编码*/ ④ void printhtree(HTree *t,int head_i,int deep,int* path) /*中序打印树* 三、实验步骤 ㈠、数据结构与核心算法的设计描述 struct frequence//统计频率 { char a; int n; } typedef struct { unsigned int weight;// 用来存放各个结点的权值 unsigned int parent,lchild,rchild;//指向双亲、 孩子结点的指针 }HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树 typedef char **HuffmanCode; void Frequent() void HuffmanCoding(HuffmanTree HT,HuffmanCodeHC,int *w,int n) //w存放n个权值, 构造哈夫曼树p, 并求出哈夫曼编码hc ㈡、函数调用及主函数设计 Main()调用HuffmanTree()函数； HuffmanTree（）函数调用Frequent()函数 ㈢ 程序调试及运行结果分析 以下是程序调试结果的截图及说明 上图是从终端输入一串字符，并把并且统计字符个数作为权值的运行结果。 上图是打印哈夫曼树运行结果 上图是输出哈夫曼编码的运行结果 ㈣ 实验总结 哈夫曼编码是二叉树的具体应用，哈夫曼编码的实验不仅巩固了我对二叉树应用和理解，还加深了我对树的具体应用的理解，在实验过程中，刚开始对哈夫曼的编程没有头绪，突然发现自己书看的太少，并且对算法理解的不透彻，课后也没有好好复习所学知识。总的来说，哈夫曼树的操作我还不是很熟练，因此还要好好练习，才能真正理解哈夫曼树的应用，所以在课后，我还会好好练习树的使用。 四、主要算法流程图及程序清单 struct frequence//统计频率 { char a; int n; } typedef struct { unsigned int weight;// 用来存放各个结点的权值 unsigned int parent,lchild,rchild;//指向双亲、 孩子结点的指针 }HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树 typedef char **HuffmanCode; void Frequent() { frequence ch[27]; int i=0; for(;i=26;i++)//初始化结构体数组 { ch[i].n=0; } cout输入一串字符（输入#键结束输入）：endl; char c; cinc; bool flag; while(c!=#) { i=1; flag=false; for(;i=ch[0].n;i++) { if(c==ch[i].a) { flag=true; break; } } if(flag)//已存在 { ch[i].n++; } else//不存在 { ch[0].n++; ch[ch[0].n].n++; ch[ch[0].n].a=c; } cinc; } for(int j=1;j=ch[0].n;j++) { coutch[j].a ch[j].nendl; } } void Select(HuffmanTree HT,int i,int s1,int s2) { int j,k=1; while(HT[k].parent!=0) k++; s1=