用C++实现哈夫曼树的代码

韩山师范学院

数据结构中的哈夫曼树的实现

班级：2015级软工班 作者：黄俊聪

#include #include #include #include using namespace std; typedefstruct{ char data; int weight;

intparent,lchild,rchild; }HTNode,*HuffmanTree;

typedef char ** HuffmanCode;

void Select(HuffmanTree&HT,intn,int m) {

HuffmanTree p=HT; inttmp;

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

int tag1,tag2,s1,s2;

tag1=tag2=256; for(int x=1;x<=j-1;x++) { if(p[x].parent==0&&p[x].weight

tag1=p[x].weight; s1=x; } }

for(int y=1;y<=j-1;y++) {

if(p[y].parent==0&&y!=s1&&p[y].weight

if(s1>s2) //将选出的两个节点中的序号较小的始终赋给s1 { tmp=s1; s1=s2; s2=tmp; }

p[s1].parent=j; p[s2].parent=j; p[j].lchild=s1; p[j].rchild=s2; p[j].weight=p[s1].weight+p[s2].weight; } }

voidHuffmanCoding(HuffmanTree&HT,intn,char *w1,int*w2) {

int m=2*n-1;

if(n<=1) return;

HT=new HTNode[m+1]; HuffmanTree p=HT; for(int i=1;i<=m;i++) {

p[i].weight=p[i].parent=p[i].lchild=p[i].rchild=0; }

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

p[i].data=w1[i-1]; p[i].weight=w2[i];

p[i].parent=p[i].lchild=p[i].rchild=0; }

Select(HT,n,m);

ofstreamoutfile(\ //生成hfmTree文件

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

outfile<

outfile.close();

cout<<\初始化结果已保存在hfmTree文件中\\n\}

void ToBeTree() //将正文写入文件ToBeTree中 { ofstreamoutfile(\ outfile<<\ outfile.close(); }

void Encoding(HuffmanTree&HT,int n) //编码 {

HuffmanCode HC;

HC=new char*[n+1];//分配储存n个字符编码的编码表空间 char *cd;

cd=new char[n];//分配临时存放每个字符编码的动态数组空间 cd[n-1]='\\0';//编码结束

for(int i=1;i<=n;i++)//逐个字符求哈夫曼编码 { int start=n-1;//start开始时指向最后，即编码结束位置 int c=i;

int f=HT[i].parent;//f指向结点c的双亲结点 while(f!=0) { if(HT[f].lchild==c) cd[--start]='0';//结点c是f的左孩子，即生成代码0 else cd[--start]='1';//结点c是f的右孩子，即生成代码1 c=f; f=HT[f].parent;//继续向上回溯 }//求出第i个字符的编码 HC[i]=new char[n-start];//为第i个字符编码分配空间 strcpy(HC[i],&cd[start]);//将求得的编码从临时空间cd复制到HC的当前行中 }

delete cd;//释放临时空间

cout<<\输出哈夫曼编码:\

for(int h=1;h<=n;h++) //输出编码 { cout<

if (h%8==0) cout<

cout<

//读取TOBETREE文件里的正文，并进行编码 fstreaminfile(\

char s[80];

while(!infile.eof())//判断是否到达文件尾部，以防止出现文件读取错误。 {

infile.getline(s,sizeof(s)); }

infile.close();

fstreamoutfile(\int count=0;

for (int h=0;s[h]!='\\0';h++) { for(int k=1;k<=n;k++) if (s[h]==HT[k].data) { cout<

if (count%9==0) cout<

outfile.close();

cout<<\编码结果已保存在文件CodeFile中.\cout<

void Decoding(HuffmanTree&HT,int n) //译码 {

int f=2*n-1;

fstreaminfile(\

char s[1000];

while(!infile.eof()) {

infile.getline(s,sizeof(s)); }