数据结构哈夫曼编码c语言

《数据结构哈夫曼编码c语言》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构哈夫曼编码c语言实现#include"stdafx.h"#include#include#include#include#includetypedefstruct{//赫夫曼树的结构体charch;intweight;//权值intparent,lchild,rchild;}htnode,*hfmtree;typedefchar**hfmcode;voidSelect(hfmtree&HT,inta,int*p1,int*p2)//Select函数，选出HT树

2、到a为止，权值最小且parent为0的2个节点{inti,j,x,y;for(j=1;j<=a;++j){if(HT[j].parent==0){x=j;break;}}for(i=j+1;i<=a;++i){if(HT[i].weight

3、&&x!=i){y=i;//选出次小的节点}}if(x>y){*p1=y;*p2=x;}else{*p1=x;*p2=y;}}voidhfmcoding(hfmtree&HT,hfmcode&HC,intn)//构建赫夫曼树HT，并求出n个字符的赫夫曼编码HC{inti,start,c,f,m,w;intp1,p2;char*cd,z;if(n<=1){return;}m=2*n-1;HT=(hfmtree)malloc((m+1)*sizeof(htnode));for(i=1;i<=n;++i)//初始化n个叶子结点{printf("请输入第%d字符信息和权值：",

4、i);scanf("%c%d",&z,&w);while(getchar()!=''){continue;}HT[i].ch=z;HT[i].weight=w;HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}for(;i<=m;++i)//初始化其余的结点{HT[i].ch='0';HT[i].weight=0;HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}for(i=n+1;i<=m;++i)//建立赫夫曼树{Select(HT,i-1,&p1,&p2);HT[p1].par

5、ent=i;HT[p2].parent=i;HT[i].lchild=p1;HT[i].rchild=p2;HT[i].weight=HT[p1].weight+HT[p2].weight;}HC=(hfmcode)malloc((n+1)*sizeof(char*));cd=(char*)malloc(n*sizeof(char));cd[n-1]='';for(i=1;i<=n;++i)//给n个字符编码{start=n-1;for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent){if(HT[f].lchild==c){c

6、d[--start]='0';}else{cd[--start]='1';}}HC[i]=(char*)malloc((n-start)*sizeof(char));strcpy(HC[i],&cd[start]);}free(cd);}intmain(){charcode[100],h[100],hl[100];intn,i,j,k,l;ifstreaminput_file;ofstreamoutput_file;charchoice,str[100];hfmtreeHT;hfmcodeHC;cout<<"";while(choice!='Q'&&choice!=

7、'q'){if(1)//初始化赫夫曼树{cout<<"请输入字符个数：";cin>>n;hfmcoding(HT,HC,n);for(i=1;i<=n;++i){cout<

8、

9、choice=='e')//进行编码{printf("请输入字符：");gets(str);output_file.open("ToBeTran.txt");if(!output_file){cout<<"can'toenfile!"<