1、#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAX 100#define MAXVALUE 10000 typedef struct    int weight;    int flag;    int parent;    char ch;    int lchild

2、;    int rchild;HafNode; typedef struct    int bitMAX;    int start;    int weight;    char ch;Code; typedef struct    char bitMAX;    char ch; &

3、#160;  int weight;Coding; void haffman(int weight,char ch,int n,HafNode haffTree)  /生成哈夫曼樹的函數    int i,j,m1,m2,x1,x2;    for (i=0;i<2*n-1;i+)           if(i<n)  

4、60;               haffTreei.weight=weighti;           haffTreei.ch=chi;              else  

5、;     haffTreei.weight=0;       haffTreei.parent=-1;       haffTreei.flag=0;       haffTreei.lchild=-1;       haffTreei.rchild=-1; 

6、;       for (i=0;i<n-1;i+)           m1=m2=MAXVALUE;       x1=x2=0;       for (j=0;j<n+i;j+)       

7、           if (haffTreej.weight<m1&&haffTreej.flag=0)                         m2=m1;    &

8、#160;         x2=x1;              m1=haffTreej.weight;              x1=j;       

9、               else if(haffTreej.weight<m2 && haffTreej.flag=0)                         m

10、2=haffTreej.weight;              x2=j;                         haffTreex1.parent= n + i;   

11、;    haffTreex2.parent = n + i;       haffTreex1.flag = 1;       haffTreex2.flag = 1;       haffTreen+i.weight = haffTreex1.weight + haffTreex2.weight;    

12、   haffTreen+i.lchild = x1;       haffTreen+i.rchild = x2;        FILE *fp;    fp=fopen("huffman.txt","w+");    printf("%d/n",n);  

13、;  fprintf(fp,"%d/n",n);    for (i=0;i<n;i+)       fprintf(fp,"%c %d %d %d/n",haffTreei.ch,haffTreei.parent,haffTreei.lchild,haffTreei.rchild);    for (i=n;i<2*n-1;i+)   

14、0;   fprintf(fp,"%d %d %d/n",haffTreei.parent,haffTreei.lchild,haffTreei.rchild);     fclose(fp); void HaffmanCode (HafNode haffTree,int n,Code haffCode)/*生成哈夫曼編碼的函數*/    Code *cd=( Code *) malloc (sizeof (Code);  &

15、#160; int i,j,child,parent;       for (i=0; i<n; i+)           cd->start=n-1;       cd->weight=haffTreei.weight;       cd->

16、ch=haffTreei.ch;       child=i;       parent=haffTreechild.parent;       while (parent !=-1)                 &

17、#160;if (haffTreeparent.lchild=child)              cd->bitcd->start=0;           else              

18、cd->bitcd->start=1;           cd->start-;           child =parent;           parent=haffTreechild.parent;   

19、60;          for (j=cd->start+1; j<n; j+)           haffCodei.bitj=cd->bitj;       haffCode i.start = cd->start+1;     

20、0; haffCode i.weight=cd->weight;       haffCode i.ch=cd->ch;     void Init(int weight,char ch)       /初始化操作，生成哈夫曼樹及哈夫曼編碼    FILE *fp;    int i,j,n; &

21、#160;  char ch1,wj15;    printf("現在進行初始化操作。/n請選擇:/nA.鍵盤輸入           B.文件輸入/n");    scanf("%c",&ch1);    if (ch1='A')    

22、60;      printf("請輸入字符集大小n:/n");       scanf("%d",&n);        if (ch1='B')           printf("請輸入文件名:/n&

23、quot;);       scanf("%s",wj);       fp=fopen(wj,"r");       fscanf(fp,"%d",&n);             HafN

24、ode *myHaffTree=(HafNode *)malloc(sizeof (HafNode)*(2*n+1);    Code *myHaffCode =(Code *)malloc (sizeof (Code)*n);    for (i=0;i<n;i+)           if (ch1='A')      &

25、#160;           printf("請輸入字符和權值:/n");           scanf("%s %d",&chi,&weighti);              

26、if (ch1='B')           fscanf(fp,"%s %d",&chi,&weighti);        if (ch1='B')    fclose(fp);    haffman(weight,ch,n,myHaffTree);

27、0;   HaffmanCode(myHaffTree,n,myHaffCode);    fp=fopen("hfmtree.txt","w+");         for (i=0;i<n;i+)           printf("%c %d ",myHaf

28、fCodei.ch,myHaffCodei.weight);       fprintf(fp,"%c %d ",myHaffCodei.ch,myHaffCodei.weight);        for ( j=myHaffCodei.start; j<n; j+)             

29、;       printf("%d",myHaffCodei.bitj);           fprintf(fp,"%d",myHaffCodei.bitj);                  

30、; fprintf(fp,"/n");       printf("/n");        fclose(fp);    printf("初始化成功!/n"); void Caozuo_C()     /哈夫曼編碼過程的函數，用于將文件編碼   &

31、#160;FILE *fp,*fp1,*fp2;    char zf500;    fp=fopen("hfmtree.txt","r");    Coding ch100;    char c;    int i=0;    while (feof(fp)=0)    

32、60;                 fscanf(fp,"%s %d %s",&chi.ch,&chi.weight,&chi.bit);            i+;       fclos

33、e(fp);      printf("現在進行編碼操作。/n請選擇:/nA.鍵盤輸入           B.文件輸入/n");    scanf("%s",&c);    if (c='A')       

34、60;      printf("請輸入字符串:/n");       scanf("%s",zf);          char ch120,ch220;    int j;    if (c='B')  

35、60;        printf("請輸入正文的文件名:/n");       scanf("%s",&ch1);       fp1=fopen(ch1,"r");           printf

36、("請輸入保存結果的文件名:/n");       scanf("%s",&ch2);       fp2=fopen(ch2,"w+");       if (c='A')           

37、       int len,k;           len=strlen(zf);           for (k=0;k<len;k+)             &#

38、160;for (j=0;j<i;j+)                  if (chj.ch=zfk)                         

39、0;             fprintf(fp2,"%s",chj.bit);                     printf("%s",chj.bit);    

40、60;                                  printf("/n");           

41、0;  if (c='B')                  while(feof(fp1)=0)                       

42、0; fscanf(fp1,"%c",&c);              for (j=0;j<i;j+)           /對文件中的每一個字符進行編碼            &#

43、160;     if (chj.ch=c)                                       fprintf(fp2,"%

44、s",chj.bit);                     printf("%s",chj.bit);                     

45、                   fprintf(fp2,"/n");              printf("/n");        

46、60;  fclose(fp1);                   fclose(fp2);       printf("編碼過程完成!同時已將結果存入%s中./n/n",ch2); void Caozuo_D()      

47、         /譯碼操作    FILE *fp,*fp1;      fp=fopen("huffman.txt","r");    int i,n;    fscanf(fp,"%d",&n);    HafNod

48、e *myHaffTree=(HafNode *)malloc(sizeof (HafNode)*(2*n+1);    for (i=0;i<n;i+)        fscanf(fp,"%s %d %d %d/n",&myHaffTreei.ch,&myHaffTreei.parent,&myHaffTreei.lchild,&myHaffTreei.rchild);    

49、;for (i=n;i<2*n-1;i+)       fscanf(fp,"%d %d %d/n",&myHaffTreei.parent,&myHaffTreei.lchild,&myHaffTreei.rchild);    fclose(fp);    printf("請輸入譯碼文件的文件名:/n");    char ch120

50、,ch220;    scanf("%s",ch1);    printf("請輸入結果文件的文件名:/n");    scanf("%s",ch2);     fp=fopen(ch1,"r");    fp1=fopen(ch2,"w+");   

51、0;char ch;    i=2*n-2;    while (!feof(fp)            fscanf(fp,"%c",&ch);           if (ch='0')    

52、60;               /若編碼為，則找此結點的左孩子；           i=myHaffTreei.lchild;       if (ch='1')       &

53、#160;            /若編碼為，則找此結點的右孩子；           i=myHaffTreei.rchild;         if (i<n)         &

54、#160;        printf("%c",myHaffTreei.ch);            fprintf(fp1,"%c",myHaffTreei.ch);           i=2*n-2;   &#

55、160;           printf("/n");    fprintf(fp1,"/n");    fclose(fp);    fclose(fp1);    printf("譯碼過程完成!已將結果存入%s中./n/n",ch2); void Cao

56、zuo_P()                /打印代碼文件的操作；    FILE *fp1,*fp2;    printf("請輸入輸入文件的文件名：/n");    char ch120,ch220;    scanf("%s",ch

57、1);    printf("請輸入結果保存的文件名：/n");    scanf("%s",ch2);    fp1=fopen(ch1,"r");    fp2=fopen(ch2,"w+");    int count=0;    char ch;  &

58、#160; while (!feof(fp1)            fscanf(fp1,"%c",&ch);          printf("%c",ch);       fprintf(fp2,"%c",ch); 

59、      count+;       if (count=50)                  printf("/n");           fprin

60、tf(fp2,"/n");            count=0;               printf("/n");    fprintf(fp2,"/n");    fclose(f

61、p1);    fclose(fp2);    printf("打印代碼過程完成!已將結果存入%s中./n/n",ch2);  void PrintTree(HafNode *huf,int n,int p,FILE *fp)    int i;    if (n=-1)       return;  

62、60; PrintTree(huf,hufn.rchild,p+1,fp);    for (i=0;i<p;i+)            printf("   ");        fprintf(fp,"   ");  

63、      if (p>=0&&hufn.rchild=-1)           printf("-");       printf("%c/n",hufn.ch);           

64、; /如果此結點為葉子結點，則將此結點輸出；       fprintf(fp,"-%c/n",hufn.ch);        else           printf("/n");        

65、0;            /如果此結點為非葉子結點，則輸出""       fprintf(fp,"/n");        PrintTree(huf,hufn.lchild,p+1,fp); void Caozuo_T()    &#

66、160;       /打印哈夫曼樹的操作    FILE *fp;    fp=fopen("huffman.txt","r");    int i,n;    fscanf(fp,"%d",&n);    HafNode *myHaffTree=(HafNo

67、de *)malloc(sizeof (HafNode)*(2*n+1);    for (i=0;i<n;i+)       fscanf(fp,"%s %d %d %d/n",&myHaffTreei.ch,&myHaffTreei.parent,&myHaffTreei.lchild,&myHaffTreei.rchild);    for (i=n;i<2*n-1;i+)&#

68、160;      fscanf(fp,"%d %d %d/n",&myHaffTreei.parent,&myHaffTreei.lchild,&myHaffTreei.rchild);    fclose(fp);    printf("請輸入保存結果的文件名:/n");    char ch120;    s

69、canf("%s",ch1);    fp=fopen(ch1,"w+");    PrintTree(myHaffTree,2*n-2,0,fp);    fclose(fp);    printf("打印哈夫曼樹過程完成!同時已將結果存入%s中./n/n",ch1); void print()   printf("*/n&q

70、uot;);   printf("*                                           

71、0;                        */n");   printf("*                  

72、60;                                                 */n

73、");    printf("*                       歡迎使用哈夫曼編譯碼器                 

74、60;    */n");   printf("*                                      &#

75、160;                             */n");   printf("*             &

76、#160;                                                 &

77、#160;    */n");    printf("* C.編碼D.譯碼T.印哈夫曼樹P.印代碼文件E.退出  */n");   printf("*                       &#

78、160;                                            */n");   pri

79、ntf("*/n"); int main()    int i,j,n=4;    int weight100;    char ch100,cha;    print();    Init(weight,ch);    while (1)       

80、60;  printf("請輸入要執行的操作:/nC.編碼D.譯碼T.印哈夫曼樹P.印代碼文件E.退出/n");       printf("請輸入要執行的操作:/n");       scanf("%s",&cha);       if (cha='E')  &#

81、160;        break;       switch (cha)              case 'C':Caozuo_C();break;      /執行編碼操作    

82、60;  case 'D':Caozuo_D();break;      /執行譯碼操作       case 'T':Caozuo_T();break;      /打印哈夫曼樹       case 'P':Caozuo_P();break;  &

83、#160;   /打印代碼文件               return 0; 在電報通訊中，電文是以二進制的0、1序列傳送的。字符集中的字符的使用頻率是不同的（比如e和t的使用較之q和z要頻繁得多），哈夫曼編碼可以使得編碼的總長最短，從而相同的位長可以傳送更多的信息。 本程序以下面的字符及使用頻率為例：字符權值a0.12b0.40c0.15d0.08e0.25 首先建立哈夫曼樹：i01

84、2345678treei.chabcde    treei.weight0.120.400.150.080.250.200.350.601.00treei.parent586576780treei.lchild-1-1-1-1-13241treei.rchild-1-1-1-1-10567 得到哈夫曼樹和哈夫曼編碼如下：下面是哈夫曼編碼的存儲結構：序號bitschstart01111a21   0b52 110c331110d24  10e4 程序清單如下：#include&

85、lt;stdio.h>#define n 5  /葉子數目#define m (2*n-1)    /結點總數#define maxval 10000.0#define maxsize 100   /哈夫曼編碼的最大位數typedef struct char ch; float weight; int lchild,rchild,parent;hufmtree;typedef struct char bitsn;   /位串

86、60;int start;      /編碼在位串中的起始位置 char ch;        /字符codetype;void huffman(hufmtree tree);/建立哈夫曼樹void huffmancode(codetype code,hufmtree tree);/根據哈夫曼樹求出哈夫曼編碼void decode(hufmtree tree);/依次讀入電文，根據哈夫曼樹譯碼void main() printf(&qu

87、ot;                            哈夫曼編碼n"); printf("總共有%d個字符n",n); hufmtree treem; codetype coden; int i,j;/循環變量 huffman(tr

88、ee);/建立哈夫曼樹 huffmancode(code,tree);/根據哈夫曼樹求出哈夫曼編碼 printf("【輸出每個字符的哈夫曼編碼】n"); for(i=0;i<n;i+)   printf("%c: ",codei.ch);  for(j=codei.start;j<n;j+)   printf("%c ",codei.bitsj);  printf("n");

89、  printf("【讀入電文，并進行譯碼】n"); decode(tree);/依次讀入電文，根據哈夫曼樹譯碼void huffman(hufmtree tree)/建立哈夫曼樹 int i,j,p1,p2;/p1,p2分別記住每次合并時權值最小和次小的兩個根結點的下標 float small1,small2,f; char c; for(i=0;i<m;i+)    /初始化   treei.parent=0; &#

90、160;treei.lchild=-1;  treei.rchild=-1;  treei.weight=0.0;  printf("【依次讀入前%d個結點的字符及權值(中間用空格隔開)】n",n); for(i=0;i<n;i+)  /讀入前n個結點的字符及權值   printf("輸入第%d個字符為和權值",i+1);  scanf("%c %f",&c,&f);

91、0; getchar();  treei.ch=c;  treei.weight=f;  for(i=n;i<m;i+)      /進行n-1次合并，產生n-1個新結點   p1=0;p2=0;  small1=maxval;small2=maxval;   /maxval是float類型的最大值  for(j=0;j<i;j+)  

92、  /選出兩個權值最小的根結點   if(treej.parent=0)    if(treej.weight<small1)         small2=small1;  /改變最小權、次小權及對應的位置     small1=treej.weight;     p2=p1; &

93、#160;   p1=j;        else     if(treej.weight<small2)           small2=treej.weight;  /改變次小權及位置      p2=j;  

94、0;    treep1.parent=i;  treep2.parent=i;  treei.lchild=p1;  /最小權根結點是新結點的左孩子  treei.rchild=p2;  /次小權根結點是新結點的右孩子  treei.weight=treep1.weight+treep2.weight; /huffmanvoid huffmancode(codetype code,hufmtree tree)/根據哈夫曼樹求

95、出哈夫曼編碼/codetype code為求出的哈夫曼編碼/hufmtree tree為已知的哈夫曼樹 int i,c,p; codetype cd;   /緩沖變量 for(i=0;i<n;i+)   cd.start=n;  cd.ch=treei.ch;  c=i;       /從葉結點出發向上回溯  p=treei.parent;  

96、0;/treep是treei的雙親  while(p!=0)     cd.start-;   if(treep.lchild=c)    cd.bitscd.start='0'   /treei是左子樹，生成代碼'0'   else    cd.bitscd.start='1'  

97、0;/treei是右子樹，生成代碼'1'   c=p;   p=treep.parent;    codei=cd;    /第i+1個字符的編碼存入codei /huffmancodevoid decode(hufmtree tree)/依次讀入電文，根據哈夫曼樹譯碼 int i,j=0; char bmaxsize; char endflag='2'  

98、0; /電文結束標志取2 i=m-1;             /從根結點開始往下搜索 printf("輸入發送的編碼(以'2'為結束標志)："); gets(b); printf("譯碼后的字符為"); while(bj!='2')   if(bj='0')  

99、0;i=treei.lchild;   /走向左孩子  else   i=treei.rchild;   /走向右孩子  if(treei.lchild=-1)     /treei是葉結點     printf("%c",treei.ch);   i=m-1;     

100、; /回到根結點    j+;  printf("n"); if(treei.lchild!=-1&&bj!='2')   /電文讀完，但尚未到葉子結點  printf("nERRORn");  /輸入電文有錯/decode  #include<iostream.h>#include<stdio.h>#include<stdl

101、ib.h>#include<string.h>#include<fstream.h>typedef struct         /赫夫曼樹的結構體char ch;int weight;              /權值int parent,lchild,rchild;htnode,*hfmtree

102、;typedef char *hfmcode;void Select(hfmtree &HT,int a,int *p1,int *p2) /Select函數，選出HT樹到a為止，權值最小且parent為0的2個節點int i,j,x,y;for(j=1;j<=a;+j)if(HTj.parent=0)x=j;break;for(i=j+1;i<=a;+i)if(HTi.weight<HTx.weight&&HTi.parent=0)x=i;  

103、;                /選出最小的節點for(j=1;j<=a;+j) if(HTj.parent=0&&x!=j)y=j;break;for(i=j+1;i<=a;+i)if(HTi.weight<HTy.weight&&HTi.parent=0&&x!=i)y=i;       

104、;           /選出次小的節點if(x>y)*p1=y;*p2=x;else*p1=x;*p2=y;void hfmcoding(hfmtree &HT,hfmcode &HC,int n) /構建赫夫曼樹HT，并求出n個字符的赫夫曼編碼HCint i,start,c,f,m,w;int p1,p2;char *cd,z;if(n<=1)return;m=2*n-1;H

105、T=(hfmtree)malloc(m+1)*sizeof(htnode);for(i=1;i<=n;+i)            /初始化n個葉子結點printf("請輸入第%d字符信息和權值：",i);scanf("%c%d",&z,&w);while(getchar()!='n')continue;HTi.ch=z;HTi.weight=w;HTi.parent=0;HTi.lchild=0;

106、HTi.rchild=0; for(;i<=m;+i)        /初始化其余的結點HTi.ch='0'HTi.weight=0;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(i=n+1;i<=m;+i)        /建立赫夫曼樹Select(HT,i-1,&p1,&p2);HTp1.parent=i;HTp2.parent=i;HTi

107、.lchild=p1;HTi.rchild=p2;HTi.weight=HTp1.weight+HTp2.weight; HC=(hfmcode)malloc(n+1)*sizeof(char *);cd=(char *)malloc(n*sizeof(char);cdn-1='0' for(i=1;i<=n;+i)              /給n個字符編碼start=n-1;for(c=i,

108、f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c)cd-start='0'elsecd-start='1'HCi=(char*)malloc(n-start)*sizeof(char);strcpy(HCi,&cdstart);free(cd);  int main()char code100,h100,hl100;int n,i,j,k,l;ifstream input_file;    /文件輸入輸出

109、流ofstream output_file;char choice,str100;hfmtree HT;hfmcode HC;cout<<"n"cout<<"          "<<"計算機（3）班"<<"    "<<" n"while(choice!='Q'&&choice!='q')                /當choice的值不為q且不為Q時循環cout<<"       "<<"