c++实现哈夫曼树算法数据结构

#include <iostream> #include <stdio.h> #include <stdlib.h> #include <string> #include <math.h> using namespace std; #define N 1000 //定义结点数最大值 #define M 2*N-1 #define maxval 10000.0 //定义float的最大值 static int n,m; //定义静态全局变量n储存需要的结点数 //m为构建哈夫曼树后的总结点数 struct HuffmanTree { char data; float weight; int lchild,rchild,parent; } ; /* 结点结构*/ HuffmanTree tree[M]; struct HCodeType { char bits[N]; int start; char data; }; /*哈夫曼编码结构体*/ HCodeType code[N]; char character[N]={'I','l','o', 'v', 'e','d', 'a', 't','S','s','r', 'u', 'c', 'C', 'm', 'p', 'y', 'w', 'i', 'b','\t',',','.' ,0}; char word[N]={'I','\t', 'l','o', 'v', 'e','\t', 'd', 'a', 't', 'a','\t', 'S', 't', 'r', 'u', 'c', 't', 'u', 'r', 'e', ',', 'I', '\t', 'l', 'o', 'v', 'e','\t', 'C', 'o', 'm', 'p', 'u', 't' ,'e', 'r', '.', 'I', '\t', 'w', 'i', 'l', 'l','\t', 't', 'r', 'y','\t', 'm', 'y', '\t', 'b','e', 's','t','\t', 't','o','\t', 's', 't', 'u', 'd', 'y', '\t', 'd', 'a', 't', 'a','\t', 'S', 't', 'r', 'u', 'c', 't', 'u', 'r', 'e', '.', 0}; float WordWeight[N]={3,4,4,2,6,3,4,11,2,2,6,6,2,1,2,1,3,1,1,1,13,1,2}; void HUFFMAN(HuffmanTree t[]); void HUFFMAN(HCodeType code[],HuffmanTree t[],char w[],char c[],float ww[]); void HuffmanCoding(HCodeType code[],HuffmanTree t[]); void HuffmanCoding(HCodeType code[],HuffmanTree t[],int* pcount,char w[]); void Coding(HCodeType code[],HuffmanTree t[],char w[],char c[],float ww[],int* pcount); void HuffmanDecode(HCodeType code[],HuffmanTree t[]); void OutTree(HuffmanTree t[]); /*创建已知字符串的哈夫曼树*/ void HUFFMAN(HCodeType code[],HuffmanTree t[],char w[],char c[],float ww[]){ int i,j,p1,p2; char ch; float small1,small2,f; n=23; m=2*n-1; for(i=0;i<m;i++) //初始化哈夫曼树 { tree[i].parent=-1; tree[i].lchild=-1; tree[i].rchild=-1; tree[i].data='0'; tree[i].weight=0.0; } for(i=0;i<n;i++) { ch=c[i]; f=ww[i]; tree[i].data=ch; tree[i].weight=f; } for(i=n;i<m;i++) //进行n-1次合并 产生n-1个新结点 { p1=0;p2=0; //最小次小权值的下标为0 small1=maxval; //最小次小权值为float型最大值 small2=maxval; for(j=i-1;j>=0;j--) //找出最小、次小权值和下标 if(tree[j].parent==-1) if((tree[j].weight-small1)<0.0001) //float精度，当两者之差小于0.0001认为相等 { small2=small1; //小于当前最小权值，更新最小权值和次小权值以及位置 small1=tree[j].weight; p2=p1; p1=j; } else if((tree[j].weight-small2)<0.0001) //小于当前次小权值，更新次小权值和位置 { small2=tree[j].weight; p2=j; } tree[p1].parent=i; //修改最小、次小结点的双亲为新生成的结点 tree[p2].parent=i; tree[i].lchild=p1; //新结点的左右孩子指向最小次小值的结点 tree[i].rchild=p2; tree[i].weight=tree[p1].weight+tree[p2].weight; //新生成结点权值为两小之和 } OutTree(tree); } /*创建哈夫曼树CreatTree*/ void HUFFMAN(HuffmanTree t[]) { int i,j,p1,p2; char ch; float small1,small2,f; cout<<"请输入叶子节点数"; cin>>n; m=2*n-1; for(i=0;i<m;i++) //初始化哈夫曼树 { tree[i].parent=-1; tree[i].lchild=-1; tree[i].rchild=-1; tree[i].data='0'; tree[i].weight=0.0; } for(i=0;i<n;i++) { getchar(); //getchar 吃掉回车 cout<<"请输入第"<<i+1<<"个结点的字符和权重（空格隔开）"<<endl; cin>>ch; cin>>f; tree[i].data=ch; tree[i].weight=f; } for(i=n;i<m;i++) //进行n-1次合并 产生n-1个新结点 { p1=0;p2=0; //最小次小权值的下标为0 small1=maxval; //最小次小权值为float型最大值 small2=maxval; for(j=i-1;j>=0;j--) //找出最小、次小权值和下标 if(tree[j].parent==-1) if((tree[j].weight-small1)<0.0001) //float精度，当两者之差小于0.0001认为相等 { small2=small1; //小于当前最小权值，更新最小权值和次小权值以及位置 small1=tree[j].weight; p2=p1; p1=j; } else if((tree[j].weight-small2)<0.0001) //小于当前次小权值，更新次小权值和位置 { small2=tree[j].weight; p2=j; } tree[p1].parent=i; //修改最小、次小结点的双亲为新生成的结点 tree[p2].parent=i; tree[i].lchild=p1; //新结点的左右孩子指向最小次小值的结点 tree[i].rchild=p2; tree[i].weight=tree[p1].weight+tree[p2].weight; //新生成结点权值为两小之和 } OutTree(tree); } /*哈夫曼编码Coding*/ void HuffmanCoding(HCodeType code[],HuffmanTree t[]) { int i,j,c,p; HCodeType cd; //定义缓冲变量 for(i=0;i<n;i++) { cd.start=n; c=i; //从叶子节点出发线上回溯 p=tree[c].parent; //p指向c的双亲结点 cd.data=tree[c].data; while(p!=-1) { cd.start--; if(tree[p].lchild==c) //判断是否是左孩子，是编码为‘0’ cd.bits[cd.start]='0'; else //否则 编码为‘1’ cd.bits[cd.start]='1'; c=p; //更新p的双亲结点，进行下一次循环 p=tree[c].parent; } code[i]=cd; //把一个字符的编码赋给相应code[i] } cout<<"输出每个字符的哈夫曼编码:"<<endl; //输出每个字符的哈弗曼编码 for(i=0;i<n;i++) { cout<<code[i].data; for(j=code[i].start;j<n;j++) cout<<" "<<code[i].bits[j]; cout<<endl; } } /*已知字符串的哈夫曼显示*/ void HuffmanCoding(HCodeType code[],HuffmanTree t[],int* pcount,char w[]) { int i,j,c,p; HCodeType cd; //定义缓冲变量 for(i=0;i<n;i++) { cd.start=n; c=i; //从叶子节点出发线上回溯 p=tree[c].parent; //p指向c的双亲结点 cd.data=tree[c].data; while(p!=-1) { cd.start--; if(tree[p].lchild==c) //判断是否是左孩子，是编码为‘0’ cd.bits[cd.start]='0'; else //否则 编码为‘1’ cd.bits[cd.start]='1'; c=p; //更新p的双亲结点，进行下一次循环 p=tree[c].parent; } code[i]=cd; //把一个字符的编码赋给相应code[i] } cout<<"输出每个字符的哈夫曼编码:"<<endl; //输出每个字符的哈弗曼编码 for(i=0;i<n;i++) { cout<<code[i].data; for(j=code[i].start;j<n;j++){ cout<<" "<<code[i].bits[j]; } cout<<endl; } cout<<"输出已知字符串的哈夫曼编码:"<<endl; for(int k=0;k<81;k++){ for(int i=0;i<n;i++){ if(w[k]==code[i].data){ for(j=code[i].start;j<n;j++){ cout<<" "<<code[i].bits[j]; (*pcount)++; } } } } cout<<endl; } /*已知字符串的哈夫曼显示*/ void Coding(HCodeType code[],HuffmanTree t[],char w[],char c[],float ww[],int* pcount){ cout<<"字符串为："; for(int i=0;i<81;i++) cout<<w[i]; cout<<endl; HUFFMAN(code,t,w,c,ww); float s=8*81; HuffmanCoding(code,t,pcount,w); cout<<"哈夫曼编码前长度为"<<s<<"比特"<<endl; cout<<"哈夫曼编码后长度为"<<*pcount<<"比特"<<endl; float a=s/(*pcount); cout<<"压缩比为："<<a<<endl; } /*解码哈夫曼树decoding*/ void HuffmanDecode(HCodeType code[],HuffmanTree t[]) { int i,c=0; char b[100]; //定义字符数组储存输入的字符串 int endflag='$';