haffmantree.c

在双工通讯中利用哈夫曼编码和译码,使其权值最小.

#include<string.h>
#include<stdlib.h> 
#include<stdio.h>
#include "conio.h"
#define ok 1
#define error 2
int m,s1,s2,n,k;

typedef struct { 
               unsigned int weight;
               unsigned int parent,lchild,rchild;
               }HTNode,*HuffmanTree; /*动态分配数组存储哈夫曼树*/
typedef char *HuffmanCode; /*动态分配数组存储哈夫曼编码表*/
typedef struct{
               int *w;
               char *sl;
               HuffmanCode *HC;
               }*sq,sf;
void Select(HuffmanTree HT,int n) {
int i,j; 
for(i = 1;i <= n;i++) 
if(!HT[i].parent){s1 = i;break;} 
for(j = i+1;j <= n;j++) 
if(!HT[j].parent){s2 = j;break;} 
for(i = 1;i <= n;i++) 
if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i))s1=i; 
for(j = 1;j <= n;j++) 
if((HT[s2].weight>HT[j].weight)&&(!HT[j].parent)&&(s1!=j))s2=j; 
} 

void HuffmanCoding(HuffmanTree HT, HuffmanCode HC[], int *w, int n) {
/*w存放n个字符的权值(均>0)，构造哈夫曼树HT，
并求出n个字符的哈夫曼编码HC*/
int i, j; 
char *cd; 
int p; 
int cdlen; 

if (n<=1) return; 
m = 2 * n - 1; 
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); /* 0号单元未用*/
for (i=1; i<=n; i++) { /*初始化*/
HT[i].weight=w[i-1]; 
HT[i].parent=0; 
HT[i].lchild=0; 
HT[i].rchild=0; 
} 
for (i=n+1; i<=m; i++) {  /*初始化*/
HT[i].weight=0; 
HT[i].parent=0; 
HT[i].lchild=0; 
HT[i].rchild=0; 
} 
puts("\nprocess");
printf("HTbegin:\n node weight parent lchild rchild");
for (i=1; i<=m; i++) 
printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight, 
HT[i].parent,HT[i].lchild, HT[i].rchild); 
printf(" enter ...");
getchar(); 
for (i=n+1; i<=m; i++) { /* 建哈夫曼树
 在HT[1..i-1]中选择parent为0且weight最小的两个结点，
 其序号分别为s1和s2*/
Select(HT, i-1); 
HT[s1].parent = i; HT[s2].parent = i; 
HT[i].lchild = s1; HT[i].rchild = s2; 
HT[i].weight = HT[s1].weight + HT[s2].weight; 
printf("\nselect: s1=%d s2=%d\n", s1, s2); 
printf(" node weight parent lchild rchild");
for (j=1; j<=i; j++) 
printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight, 
HT[j].parent,HT[j].lchild, HT[j].rchild); 
printf(" enter ...");
getch();
} 

/*------无栈非递归遍历哈夫曼树，求哈夫曼编码*/
cd = (char *)malloc(n*sizeof(char)); /* 分配求编码的工作空间*/
p = m; cdlen = 0; 
for (i=1; i<=m; ++i) /* 遍历哈夫曼树时用作结点状态标志*/
HT[i].weight = 0; 
while (p) { 
if (HT[p].weight==0) { /* 向左*/
HT[p].weight = 1; 
if (HT[p].lchild != 0) { p = HT[p].lchild; cd[cdlen++] ='0'; } 
else if (HT[p].rchild == 0) { /* 登记叶子结点的字符的编码*/
HC[p] = (char *)malloc((cdlen+1) * sizeof(char)); 
cd[cdlen] ='\0'; strcpy(HC[p], cd); /*复制编码(串) */
} 
} else if (HT[p].weight==1) { /* 向右 */
HT[p].weight = 2; 
if (HT[p].rchild != 0) { p = HT[p].rchild; cd[cdlen++] ='1'; } 
} else { /* HT[p].weight==2，退回退到父结点，编码长度减1  */
HT[p].weight = 0; p = HT[p].parent; --cdlen; 
} 
} 
} /*HuffmanCoding*/

void start() { FILE *A;     /*初使化编码*/
     HuffmanTree HT;HuffmanCode *HC;int i;  sq ql;
     puts("put node:");
     scanf("%d",&n);
     HT=(HuffmanTree)malloc(2*n*sizeof(HTNode));
     ql=(sq)malloc(sizeof(sf));
     ql->HC=(HuffmanCode *)malloc(n*sizeof(HuffmanCode));
     ql->sl=(char *)malloc(n*sizeof(char));
     ql->w=(int *)malloc(n*sizeof(int));
     printf("put in weight\n");
     for(i =0;i<n;i++)         /*输入相应权值*/
     scanf("%d",&ql->w[i]);
     printf("put in words\n"); /*输入n个字符*/
     for(i =0;i<n+1;i++)
     scanf("%c",&ql->sl[i]);
     HuffmanCoding(HT,ql->HC,ql->w,n); /*建立哈夫树*/
     if((A=fopen("data","wb"))!=NULL) /*写入文件A*/
     fwrite(ql,sizeof(sf),1,A);
     fclose(A);
     printf("\nallnodecode\n");
     for(i=1;i<=n;i++)
     printf("%c(%2d):%s\n",ql->sl[i],ql->w[i-1],ql->HC[i]); /*输出相应编码*/
     getch(); free(ql);
}

void create(){FILE *B;char *cd;int i;
      printf("put in leight\n");     /*输入字符长度*/
      scanf("%d",&k);
      cd=(char *)malloc(k*sizeof(char));
      printf("put in words\n");
      for(i=0;i<=k;i++)    /*输入字符*/
      scanf("%c",&cd[i]);
      if((B=fopen("data1","wb"))!=NULL) /*写入文件B*/
      fwrite(cd,sizeof(char),k+1,B);
      fclose(B);
      printf("\nok\n");
      getch();
      }
 void biancode(){FILE *fp8,*fp9,*C;char *sl;sq q;int i,l;HuffmanCode *HL; /*对文字进行编码*/
     q=(sq)malloc(sizeof(sf));
     q->HC=(HuffmanCode *)malloc(n*sizeof(HuffmanCode));
     q->sl=(char *)malloc(n*sizeof(char));
     q->w = (int *)malloc(n*sizeof(int));
     sl=(char *)malloc(k*sizeof(char));
     HL=(HuffmanCode *)malloc(k*sizeof(HuffmanCode));
     if((fp8=fopen("data","rb"))!=NULL) /*读取文件*/
     fread(q,sizeof(sf),1,fp8);
     fclose(fp8);
     if((fp9=fopen("data1","rb"))!=NULL)/*读取文件*/
     fread(sl,sizeof(char),k+1,fp9);
     fclose(fp9);
     for(i=1;i<=k;i++){
     for(l=1;!(sl[i]==q->sl[l])&&l<=n;l++); /*找出与B中相同的字符*/
     strcpy(HL[i],q->HC[l]);/*复制相应编码*/
     printf("codes:");
     printf("%s\n",HL[i]);}
     getch();
     if((C=fopen("data2","wb"))!=NULL)/*将编码写入文件C中*/
     fwrite(HL,sizeof(HuffmanCode),k+1,C);
     fclose(C);
     printf("\nok\n");
     getch();}
void translate(){FILE *fp8,*fp9,*D;sq l;HuffmanCode *HV;int i,t;char *cl;/*利用已经建好的哈夫曼树
     将文件C中的代码进行译码*/
     l=(sq)malloc(sizeof(sf));
     l->HC=(HuffmanCode *)malloc(n*sizeof(HuffmanCode));
     l->sl=(char *)malloc(n*sizeof(char));
     l->w = (int *)malloc(n*sizeof(int));
     cl=(char *)malloc(k*sizeof(char));
     HV=(HuffmanCode *)malloc(k*sizeof(HuffmanCode));
     if((fp8=fopen("data","rb"))!=NULL)
     fread(l,sizeof(sf),1,fp8); /*读取文件*/
     fclose(fp8);
     if((fp9=fopen("data2","rb"))!=NULL)
     fread(HV,sizeof(HuffmanCode),k+1,fp9);/*读取文件*/
     fclose(fp9);
     for(i=1;i<=k;i++){
     for(t=1;strcmp(HV[i],l->HC[t])&&t<=n;t++); /*比较文件代码*/
     cl[i]=l->sl[t];/*复制字符*/
     printf("words:");
     printf("%c\n",cl[i]);}
     getch();
     if((D=fopen("data3","wb"))!=NULL)
     fwrite(cl,sizeof(char),k+1,D);
     fclose(D);
      printf("\nok\n");
     getch();}

void main(){char ch;
loop:printf("*************\n");
     printf("*1 start    *\n");
     printf("*2 create   *\n");
     printf("*3 write    *\n");
     printf("*4 translate*\n");
     printf("*5 exit     *\n");
     printf("*************\n");
     ch=getch();
     switch(ch)
     {case '1':start();goto loop;
      case '2':create();goto loop;
      case '3':biancode();goto loop;
      case '4':translate();goto loop;
      case '5':printf("*******Thank you!!!*******\n");getch();break;
      default:printf("*******error replay*********\n");getch();goto loop;}
      }