七：哈夫曼编码及应用

-.z.**中医药大学医学信息工程学院实验报告课程名称：数据构造与算法专业班级：计算机科学与技术()级学生**：学生**：实验名称：实验成绩：课程类别：必修限选□公选□其它□哈夫曼编码及应用实验目的：了解哈夫曼树的应用，掌握哈夫曼树的构造方法及前缀码的应用。实验性质：设计性，应用性。实验步骤：输入一串字符，统计其中所有的不同字符及其个数，得出每个不同字符在文中出现的频率。根据每个字符频率建立哈夫曼树，输出字符对应的编码。[实验要求]实验要求独立完成。迟交或不交的或源代码雷同者一律不做作业登记评分。[作业提交](实验报告写在此处)给出含有6，8，11个字符的实例，统计他们的频率，画出哈夫曼树，并用算法验证结果。662424D1C11B2A21)1D1C11B2A21)1代码写在此处#include"stdio.h"#include<malloc.h>#defineMA*NODE20#defineMA*LEAF30#defineMA*INT234567structHtNode{ intww; intparent,lchild,rchild;};structHtTree{ introot; structHtNodeht[MA*NODE];};typedefstructHtTreePHtTree;PHtTree*huffman(intm,int*w);voidmain(){chars[MA*NODE];intm=0;charw[MA*NODE];intcount=0;intt=0;inta[MA*NODE];int*b;char*code; code=(char*)malloc(sizeof(char));b=(int*)malloc(sizeof(int));printf("请输入字符窜：\n");for(inti=0;i<MA*NODE;i++){ scanf("%c",&s[i]);++count; if(s[i]=='#') break;}for(i=0;i<count-1;i++){a[i]=0;b[m]=0; for(intj=0;j<count-1;j++) { if(s[i]==s[j]&&i<=j){ a[i]=a[i]+1; } if(s[i]==s[j]&&i>j){ a[i]=a[i]+1; s[i]=NULL; } } if(s[i]!=NULL){ b[m]=a[i]; w[m]=s[i]; m++; printf("%c的个数%d,频率为%f\n",w[m-1],b[m-1],(float)a[i]/(count-1)); }}PHtTree*pht;pht=(PHtTree*)malloc(sizeof(PHtTree));pht=huffman(m,b);for(i=0;i<2*m-1;i++){printf("%d",pht->ht[i].ww);}printf("\n");for(i=0;i<m;i++){intc;c=i;t=0;int p=pht->ht[i].parent; while(p!=-1) { if(pht->ht[p].lchild==c) {code[t]='0'; t++; } if(pht->ht[p].rchild==c) { code[t]='1'; t++; } pht->root--;c=p; p=pht->ht[p].parent; } printf("%c的编码是",w[i]); for(inty=t-1;y>=0;y--) printf("%c",code[y]); printf("\n");}}PHtTree*huffman(intm,int*w)//构造具有m各节点的哈弗曼树{PHtTree*pht;inti,j,*1,*2,m1,m2;pht=(PHtTree*)malloc(sizeof(PHtTree));if(pht==NULL){printf("outofspace!\n");returnpht;}for(i=0;i<2*m-1;i++){pht->ht[i].lchild=-1;pht->ht[i].rchild=-1;pht->ht[i].parent=-1; if(i<m) pht->ht[i].ww=w[i]; else pht->ht[i].ww=-1;}for(i=0;i<m-1;i++){ m1=MA*INT; m2=MA*INT; *1=-1; *2=-1; for(j=0;j<m+i;j++) if(pht->ht[j].ww<m1&&pht->ht[j].parent==-1) { m2=m1; *2=*1; m1=pht->ht[j].ww; *1=j; } elseif(pht->ht[j].ww<m2&&pht->ht[j].parent==-1) { m2=pht->ht[j].ww; *2=j; } pht->ht[*1].parent=m+i; pht->ht[*2].parent=m+i; pht->ht[m+i]