赫夫曼树实验报告

《数据结构》课程设计报告课程名称：《数据结构》课程设计课程设计题目：姓名：院系：专业：年级：学号：指导教师：2011年月日目录程序设计的目的设计题目分析设计思想算法测试结果调试分析小结课程设计的目的熟练使用C++语言编写程序，解决实际问题；了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；练习树和哈夫曼树的有关操作，和各个算法程序，理解哈夫曼树的编码和译码熟悉哈夫曼树的基本操作。掌握哈夫曼编码的实现以及实际应用2、设计题目（略）这是书上的程序，我是读了这个程序之后写的实验报告。3、分析赫夫曼树是给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小。就是当你输入每个树叶结点个数及字符和权值时，通过赫夫曼编码就能得到它的赫夫曼编码。4、设计思想构造赫夫曼数的结点结构：#ifndef_HTnode_#define_HTnode_//哈夫曼树节点结构structHTnode{charch;intweight,parent,lchild,rchild;};#endif#ifndef_HCnode_#define_HCnode_//哈夫曼编码表结构structHCnode{charch;char*pstring;};#endif然后构造赫夫曼树类，建立函数进行建立赫夫曼树，显示赫夫曼树，建立赫夫曼编码表，还有就是编码译码的函数。5、算法#ifndef_HCnode_#define_HCnode_//哈夫曼编码表结构structHCnode{charch;char*pstring;};#endif#ifndef_HTnode_#define_HTnode_//哈夫曼树节点结构structHTnode{charch;intweight,parent,lchild,rchild;};#endif#ifndef_HuffmanCoder_#define_HuffmanCoder_#include<fstream>//#include"HTnode.h"#include"HCnode.h"//#include"HuffmanTree.h"usingnamespacestd;classHuffmanCoder{public:HuffmanCoder(constint&n){m_HC=newHCnode[n];m_HCsize=n;}~HuffmanCoder();voidCreateBook(HuffmanTree&);//建立n个字符的赫夫曼编码表HCvoidCoder(charch[]);//编码voidDecoder(HuffmanTree&);//译码private:HCnode*m_HC;//外结点个数intm_HCsize;//哈夫曼编码表基地址指针};HuffmanCoder::~HuffmanCoder(){for(inti=0;i<m_HCsize;i++)delete[]m_HC[i].pstring;delete[]m_HC;}//建立n个字符的哈夫曼编码表HCvoidHuffmanCoder::CreateBook(HuffmanTree&ht){inti,j,c,f,start;char*cd=newchar[m_HCsize];cd[m_HCsize-1]='\0';cout<<"以下是各字符的哈夫曼编码:"<<endl<<endl;for(i=0;i<m_HCsize;i++){//逐个字符求赫夫曼编码start=m_HCsize-1;//编码结束符位置m_HC[i].ch=ht.m_HT[i].ch;for(c=i,f=ht.m_HT[i].parent;f!=-1;c=f,f=ht.m_HT[f].parent){//从叶子到根逆向求编码if(ht.m_HT[f].lchild==c)cd[--start]='0';elsecd[--start]='1';}m_HC[i].pstring=newchar[m_HCsize-start];cout<<"第"<<i<<"个字符"<<ht.m_HT[i].ch<<"的编码是:";for(j=start;j<m_HCsize;j++){cout<<cd[j];m_HC[i].pstring[j-start]=cd[j];}cout<<endl;}cout<<endl;delete[]cd;//释放工作空间}//对用字符串组成的电文用哈夫曼编码表进行编码voidHuffmanCoder::Coder(charch[]){ofstreamoutfile("f1.dat",ios::out);//打开数据文件f1for(unsignedinti=0;i<strlen(ch);i++){for(intj=0;j<m_HCsize;j++){if(ch[i]==m_HC[j].ch){for(intk=0;m_HC[j].pstring[k];k++){cout<<m_HC[j].pstring[k];//编码结果打印outfile.put(m_HC[j].pstring[k]);//编码结果写入数据文件f1}break;}}}cout<<endl;outfile.close();//关闭数据文件}//对用0，1串组成的电文用哈夫曼树表进行译码voidHuffmanCoder::Decoder(HuffmanTree&ht){charch[256];intj(0),i(0),p,pre,root=ht.m_HTsize-1;ifstreaminfile("f1.dat",ios::in);//打开数据文件f1while(infile.get(ch[j]))j++;//从数据文件f1中读取0，1串组成的电文至chcout<<"需译码的二进制电文是:"<<endl;j=0;while(ch[j]){cout<<ch[j];j++;}cout<<endl;cout<<"译码结果:"<<endl;p=root;while(i<strlen(ch)){while(p!=-1){if(ch[i]=='0'){pre=p;p=ht.m_HT[p].lchild;}else{pre=p;p=ht.m_HT[p].rchild;}i++;}cout<<ht.m_HT[pre].ch;i--;p=root;}cout<<endl;infile.close();//关闭数据文件}#endif#ifndef_HuffmanTree_#define_HuffmanTree_//#include<fstream>#include"HTnode.h"//#include"HCnode.h"#definemax10000usingnamespacestd;//哈夫曼树类classHuffmanTree{friendclassHuffmanCoder;public://构造函数：分配2*n-1个存储单元的顺序空间(正则树）。HuffmanTree(intn,charchA[],intweightA[]):m_HTsize(0),m_HT(NULL){_Create(n,chA,weightA);//根据字符表和相应权值，创建哈夫曼树}~HuffmanTree(){delete[]m_HT;}voidDisplay();//显示哈夫曼树private:intm_HTsize;//树叶结点个数HTnode*m_HT;//静态树表基地址指针void_Create(int,charchA[],intweightA[]);//根据字符表和相应权值，建立哈夫曼树int_MinVal(constint&);void_Select(constint,int&,int&);};//根据字符表和相应权值，建立哈夫曼树voidHuffmanTree::_Create(intn,charcha[],intweighta[]){inti,s1,s2;m_HT=newHTnode[2*n-1];m_HTsize=2*n-1;if(n>1){for(i=0;i<n;i++){m_HT[i].ch=cha[i];m_HT[i].weight=weighta[i];m_HT[i].parent=-1;m_HT[i].lchild=-1;m_HT[i].rchild=-1;}//在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2for(;i<m_HTsize;++i){_Select(i,s1,s2);m_HT[s1].parent=m_HT[s2].parent=i;m_HT[i].lchild=s1;m_HT[i].rchild=s2;m_HT[i].weight=m_HT[s1].weight+m_HT[s2].weight;m_HT[i].parent=-1;}}cout<<"哈夫曼树建毕！"<<endl;}//显示哈夫曼树voidHuffmanTree::Display(){inti;cout<<"所建哈夫曼树的静态链表表示如下："<<endl;cout<<"位置"<<"字符"<<"权值"<<"双亲"<<"左孩子"<<"右孩子"<<endl;for(i=0;i<(m_HTsize+1)/2;i++){cout<<""<<i<<""<<m_HT[i].ch<<""<<m_HT[i].weight<<"";cout<<m_HT[i].parent<<""<<m_HT[i].lchild<<""<<m_HT[i].rchild<<endl;}for(;i<m_HTsize;i++){cout<<""<<i<<""<<m_HT[i].weight<<""<<m_HT[i].parent<<"";cout<<m_HT[i].lchild<<""<<m_HT[i].rchild<<endl;}cout<<endl;}//在前ｉ个节点中选择parent为0且weight最小的结点,获得其序号intHuffmanTree::_MinVal(constint&i){intj,k,min=max;//取k为不小于可能的值for(j=0;j<i;j++)if(m_HT[j].parent==-1&&m_HT[j].weight<min){min=m_HT[j].weight;k=j;}m_HT[k].parent=max;returnk;}//s1为最小的两个值中序号小的那个voidHuffmanTree::_Select(constinti,int&s1,int&s2){ints;s1=_MinVal(i);s2=_MinVal(i);if(s1>s2){s=s1;s1=s2;s2=s;}}#endif#include<iostream>#include"HuffmanTree.h"#include"HuffmanCoder.h"usingnamespacestd;intmain(){intn;cout<<"---此程序实现建立哈夫曼树并求哈夫曼编码---"<<endl<<endl;cout<<"请输入树叶结点的个数(小于等于1结束)："<<endl;cin>>n;