[构建哈夫曼树及输出哈夫曼代码及算法思想.docx

哈夫曼树描述文档思路通过一个argv[]数组存储从test文件中读取字母，然后利用ascal码循环计算每个字母的权值，利用weight[]是否为零，确定叶子节点，节点个数为count，传入到构建哈夫曼树的子程序中，然后利用cd[]数组存储每一个叶子节点的哈夫曼代码.输出代码时，通过与argv[]数组的比对，扫描ht数组，进而读出所有的数据。截图代码#includestdio.h#include iostream #include fstreamtypedef struct{char data;int weight;int parent;int lchild;int rchild;}HTNode;typedef struct{char cd[50];int start;}HCode;using namespace std;int enter(char argv[])//进行读入操作{ fstream in;ofstream out; char c;int number=0;//字母个数置为0in.open(test.txt,ios::in); //打开文件test.txtout.open (code.txt,ios::trunc); //打开文件code.txt，如果不存在就新建一个，如果存在就清空if(!in.eof()) inc; //从test.txt中读取一个字符存入cprintf(原文本是:\n);while(! in.eof()){ //文件不为空，循环读取一个字符coutc; //将文件中的内容输出到屏幕上argv[number]=c;//存储c的值到数组number++;outc; // 将c中的字符存入文件code.txt中inc; //从test.txt中读取一个字符存入c}argv[number]=\0;printf(\n); in.close; out.close; //使用完关闭文件return(number);//返回叶子节点数目}void CreateHT(HTNode ht[],int n){int i,j,k,lnode,rnode;double min1,min2;for(i=0;i2*n-1;i++)ht[i].parent=ht[i].lchild=ht[i].rchild=-1;//置初值for(i=n;i2*n-1;i++){min1=min2=32167;lnode=rnode=-1;for(k=0;k=i-1;k++)if(ht[k].parent==-1){if(ht[k].weightmin1){min2=min1;rnode=lnode;min1=ht[k].weight;lnode=k;}else if(ht[k].weightmin2){min2=ht[k].weight;rnode=k;}}ht[i].weight=ht[lnode].weight+ht[rnode].weight;ht[i].lchild=lnode;ht[i].rchild=rnode;//双亲ht[lnode].parent=i;ht[rnode].parent=i;}}void CreateHcode(HTNode ht[],HCode hcd[],int n){int i,f,c;HCode hc;for(i=0;in;i++){hc.start=n;c=i;f=ht[i].parent;while(f!=-1){if(ht[f].lchild==c)hc.cd[hc.start--]=0;elsehc.cd[hc.start--]=1;c=f;f=ht[f].parent;}hc.start++;hcd[i]=hc;}}int main(){int enter(char argv[]);void CreateHT(HTNode ht[],int n);//创建哈夫曼树void CreateHcode(HTNode ht[],HCode hcd[],int n);//哈夫曼编码char argv[500];int n,i,j,k;char zimu=A;n=enter(argv);HTNode ht[100];//创建结点HCode hcd[200];int weicount[58];//频度计数int count;for(i=0;i58;i++)//对58个字母求频度{count=0;for(j=0;jn;j++){if(zimu==argv[j])count++;}zimu++;//跳到第二个字母weicount[i]=count;}zimu=A;for(i=0;i58;i++){printf(The %c s weight is: %d\n,zimu,weicount