Category

Development Platform
Home > SourceCode/Document > Mathimatics-Numerical algorithms > Data structs > View Code
(10)哈夫曼编码.CPP
Package: datastruct1　[view]
Upload User: wxj1219
Upload Date: 2013-01-31
Package Size: 6k
Code Size: 3k
Category:

Data structs

Development Platform:

C/C++

(10)哈夫曼编码.CPP：Code Content
  1. #include <iostream.h>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5. #define NUM 8;
  6. typedef struct
  7. { unsigned int weight;
  8.   unsigned int parent,lchild,rchild;
  9.   unsigned char data;
  10. } HTNode,*HuffmanTree;
  11. typedef char **HuffmanCode;
  13. unsigned int pop;
  15. void select(HuffmanTree HT,int i,int &s1,int &s2)
  16. {
  17.   unsigned int temp;
  18.   unsigned int min=100;
  19.   for(temp=1;temp<=i;temp++)
  20. if((HT[temp].weight<min)&&(HT[temp].parent==0))
  21. {
  22. min=(HT+temp)->weight;
  23. s1=temp;
  24. }
  25.    min=100;
  26.    for(temp=1;temp<=i;temp++)
  27. if((HT[temp].weight<min)&&(HT[temp].parent==0)&&(temp!=s1))
  28. {
  29. min=(HT+temp)->weight;
  30. s2=temp;
  31. }
  32. }
  34. void GetCord(HuffmanCode HC,char *dm0,char *st,char *ch)
  35. {
  36. int i=0;
  37. while(st[i]!=0)
  38. {
  39. strcat(dm0,HC[st[i]-0x60]);
  40. i++;
  41. }
  42. *ch=*ch;
  43. }
  45. void GetText(HuffmanTree HT,char *dm1,char *s)
  46. {
  47. int Tree;
  48. int u;
  49. int c=0;
  50. while(*dm1)
  51. {
  52. Tree=pop-1;
  53. while(HT[Tree].lchild&&HT[Tree].rchild)
  54. {
  55. if(*dm1=='0')
  56. Tree=HT[Tree].lchild;
  57. else
  58. Tree=HT[Tree].rchild;
  59. dm1++;
  60. }
  61. s[c]=HT[Tree].data+1;
  62. c++;
  63. }
  64. s[c]=0;
  65. }
  67. void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n,char ch[])
  68. { int m,i,s1,s2,start,c,f;
  69. int u;
  70.   HuffmanTree p;
  71.   char * cd;
  72.   if(n<=1)return;
  73.   m=2*n-1;
  74.   HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
  75.   for(u=1;u<9;u++)
  76. HT[u].data=95+u;
  77.   for(p=HT+1,i=1;i<=n;++i,++p,++w)
  78.    { (*p).weight=*w;(*p).parent=0;(*p).lchild=0;(*p).rchild=0;}
  79.   for(;i<=m;++i,++p)
  80.    { (*p).weight=0;(*p).parent=0;(*p).lchild=0;(*p).rchild=0;}
  82.   for(i=n+1;i<=m;++i)
  83. { select(HT,i-1,s1,s2);
  84.   HT[s1].parent=i;HT[s2].parent=i;
  85.   HT[i].lchild=s1;HT[i].rchild=s2;
  86.   HT[i].weight=HT[s1].weight+HT[s2].weight;
  87. }
  88.   pop=i;
  89.  printf("%2d:%6d%6d%6d%6dn",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
  90.   HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
  91.   cd=(char *)malloc(n*sizeof(char));
  92.   cd[n-1]='';
  93.   for(i=1;i<=n;++i)
  94. { start=n-1;
  95.   for( c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
  96. if(HT[f].lchild==c) cd[--start]='0';
  97. else cd[--start]='1';
  98.   HC[i]=(char*)malloc((n-start)*sizeof(char));
  99.   strcpy(HC[i],&cd[start]);
  100.   }
  101.   printf(" char   weight   huffmancord n");
  102.   for(i=1;i<=n;++i)printf("%4c%10d%10sn",ch[i],HT[i].weight,HC[i]);
  103. }
  105. void main()
  106. { int *w,*k,i,j,p,n;
  107.   char ch[8+1];
  108.   char dm1[256]="";
  109.   char st[256]="";
  110.   char dm0[256]="";
  111.   char s[256];
  112.   n=8;
  113.   HuffmanTree HT;
  114.   HuffmanCode HC;
  115.   w=(int *)malloc(n*sizeof(int));
  116.   for(i=1,k=w;i<=n;++i,++k)
  117.    {ch[i]=96+i;printf("Enter the weight(%c):  ",ch[i]);scanf("%d",k);}
  118.   HuffmanCoding(HT,HC,w,n,ch);
  119.   printf("input the text :     ");
  120.   scanf("%s",st);
  121.   GetCord(HC,dm0,st,ch);
  122.   printf("the cord is :%s n",dm0);
  123.   printf("Enter cord : ");
  124.   scanf("%s",dm1);
  125.   GetText(HT,dm1,s) ;
  126.   printf("the decord text is : %sn",s);
  127. }