- #include<bits/stdc++.h>
- #define N 8
- typedef struct hm
- {
- char ch;
- char code[20];
- } HuffM;
- typedef struct s
- {
- char ch;
- int frq;
- } mytype;
- typedef struct bt
- {
- struct bt *lchild;
- mytype dt;
- struct bt *rchild;
- } bitree;
- int g_flag=0;
- int Encoding(HuffM d[]);
- int PreOrderPrint(bitree *HT,int cont);
- void PrintCodeFile();
- int Decoding(HuffM d[]);
- int reaData(mytype d[])// 载入数据
- {
- FILE * fp;
- int i=0;
- fp=fopen("data.txt","r");
- if(NULL==fp)
- {
- return -1;
- }
- while(!feof(fp))
- {
- fscanf(fp,"%c",&(d[i].ch));
- fscanf(fp,"%d",&(d[i].frq));
- fseek(fp,2,SEEK_CUR);
- i++;
- if(i==N-2) break;
- }
- g_flag=1;
- fclose(fp);
- return 0;
- }
- int reaHFData(HuffM d[])// 从 hfmTree.txt 文件读取数据
- {
- FILE * fp;
- int i=0,td;
- char c,data[20];
- fp=fopen("hfmTree.txt","r");
- if(NULL==fp)
- {
- printf("打开哈夫曼编码数据文件出错.\n");
- return -1;
- }
- while(1)
- {
- fscanf(fp,"%c%d%s",&c,&td,data);
- if(feof(fp))
- break;
- //printf("%c\t%d\t%s\n",c,td,data);
- d[i].ch=c;
- strcpy(d[i].code,data);
- i++;
- fseek(fp,2,SEEK_CUR);
- }
- g_flag=1;
- fclose(fp);
- return 0;
- }
- int printData(mytype d[]) // 数据显示 字符 频度
- {
- int i=0;
- if(g_flag<1)
- {
- printf("请先载入数据文件.\n");
- return 0;
- }
- for(; i<N-3; i++)
- {
- printf("%c\t%d\n",d[i].ch,d[i].frq);
- }
- return 0;
- }
- int printHFData(HuffM d[]) // 显示哈夫曼树 字符 编码
- {
- int i=0;
- if(g_flag<1)
- {
- printf("请先载入数据文件.\n");
- return 0;
- }
- for(; i<N-3; i++)
- {
- printf("%c\t%s\n",d[i].ch,d[i].code);
- }
- return 0;
- }
- int sort(mytype d[])// 对数据频度大小排序 建哈夫曼树时调用
- {
- int i,j;
- mytype temp;
- if(g_flag<1)
- {
- printf("请先载入数据文件.\n");
- return 0;
- }
- for(i=0; i<N-4; i++)
- {
- for(j=0; j<N-4-i; j++)
- {
- if(d[j].frq>d[j+1].frq)
- {
- temp=d[j];
- d[j]=d[j+1];
- d[j+1]=temp;
- }
- }
- }
- }
- int sortHMC(HuffM d[])// 对哈夫曼树字符排序 译码文件时调用
- {
- int i,j;
- HuffM temp;
- if(g_flag<1)
- {
- printf("请先载入数据文件.\n");
- return 0;
- }
- for(i=0; i<N-4; i++)
- {
- for(j=0; j<N-4-i; j++)
- {
- if(d[j].ch>d[j+1].ch)
- {
- temp=d[j];
- d[j]=d[j+1];
- d[j+1]=temp;
- }
- }
- }
- }
- int sort1(bitree* temp[N],int n)// 对新的数据重新 频度大小排序 建树时调用
- {
- int i,j;
- bitree* tmp;
- for(i=0; i<n-1; i++)
- {
- for(j=0; j<n-1-i; j++)
- {
- if(temp[N-3-n+j]->dt.frq>temp[N-3-n+j+1]->dt.frq)
- {
- tmp=temp[N-3-n+j];
- temp[N-3-n+j]=temp[N-3-n+j+1];
- temp[N-3-n+j+1]=tmp;
- }
- }
- }
- }
- bitree * createbt(mytype d[])// 建哈夫曼树
- {
- bitree* head=NULL;
- bitree* temp[N]= {NULL};
- int i=0;
- if(g_flag<1)
- {
- printf("请先载入数据文件.\n");
- return 0;
- }
- sort(d);
- while(i<N-3)
- {
- temp[i]=(bitree *)malloc(sizeof(bitree));
- temp[i]->dt=d[i];
- temp[i]->lchild=NULL;
- temp[i]->rchild=NULL;
- i++;
- }
- i=0;
- while(i<N-4)
- {
- head=(bitree *)malloc(sizeof(bitree));
- head->dt.ch='*';
- head->dt.frq=temp[i]->dt.frq + temp[i+1]->dt.frq;
- head->lchild=temp[i];
- head->rchild=temp[i+1];
- temp[i+1]=head;
- temp[i]=NULL;
- sort1(temp,N-i-4);
- i++;
- }
- g_flag = 11;
- return head;
- }
- bitree * destroybt(bitree * head)// 销毁哈夫曼树, 释放空间 递归调用
- {
- bitree *temp;
- if(head==NULL)
- return NULL;
- temp=head;
- if(head->lchild)
- head->lchild=destroybt(temp->lchild);
- if(head->rchild)
- head->rchild=destroybt(temp->rchild);
- free(head);
- head=NULL;
- return NULL;
- }
- void HuffManCoding(bitree *BT, int len,FILE *fp) // 哈夫曼树编码 利用 static 函数 并写入文件
- {
- static int a[10];
- int i;
- if(g_flag<11)
- {
- printf("请先建立哈夫曼树.\n");
- return ;
- }
- if(BT!=NULL)
- {
- if(BT->lchild==NULL&&BT->rchild==NULL)
- {
- //printf("字符 %c 的权值为 %d 的编码:",BT->dt.ch,BT->dt.frq);
- fprintf(fp,"%c\t%d\t",BT->dt.ch,BT->dt.frq);
- for(i=0; i<len; i++)
- //printf("%d",a[i]);
- fprintf(fp,"%d",a[i]);
- fprintf(fp,"\n");
- //printf("\n");
- }
- else
- {
- a[len]=0;
- HuffManCoding(BT->lchild, len+1,fp);
- a[len]=1;
- HuffManCoding(BT->rchild, len+1,fp);
- }
- }
- }
- int menu()
- {
- int n;
- printf("*****************************\n");
- printf("字符集和频度操作:\n");
- printf("\t1. 载入数据文件.\n");
- printf("\t2. 显示数据.\n");
- printf("\t3. 排序.\n");
- printf("哈夫曼树操作:\n");
- printf("\t4. 建立哈夫曼树.\n");
- printf("\t5. 写入哈夫曼编码文件.\n");
- printf("\t6. 显示哈夫曼编码文件.\n");
- printf("\t7. 销毁哈夫曼树.\n");
- printf("哈夫曼编译码操作:\n");
- printf("\t8. 载入哈夫曼编码.\n");
- printf("\t9. 显示哈夫曼编码.\n");
- printf("\t10. 编码 ToBeTran 文件.\n");
- printf("\t11. 译码 CodeFile 文件.\n");
- printf("\t12. 打印 CodeFile 文件.\n");
- printf("\t13. 打印哈夫曼树.\n");
- printf("\t14. 退出 \ n");
- printf("*****************************\n");
- printf("请输入选择:");
- while(1)
- {
- scanf("%d",&n);
- if(n>0&&n<15)
- break;
- printf("输入错误, 请重输:");
- }
- system("cls");
- return n;
- }
- int printHuffManfile() // 输出哈夫曼树 字符 频度 编码
- {
- FILE * fp;
- char data[50],c;
- int d;
- fp=fopen("hfmTree.txt","r");
- if(NULL==fp)
- {
- printf("打开文件哈夫曼编码错误.\n");
- return -1;
- }
- while(1)
- {
- fscanf(fp,"%c%d%s",&c,&d,data);
- if(feof(fp))
- break;
- printf("%c\t%d\t%s\n",c,d,data);
- fseek(fp,2,SEEK_CUR);
- }
- fclose(fp);
- }
- main()
- {
- mytype data[N]= {0};
- HuffM hmdata[N]= {0};
- int flag;
- int choose,cont;
- FILE *fp;
- bitree *bthead=NULL;
- cont=0;
- g_flag=0;// 刚开始时数据为空.
- while(1)
- {
- choose=menu();
- switch(choose)
- {
- case 1:
- flag=reaData(data);
- if(-1==flag)
- {
- printf("Open data.txt file error!\n");
- return 0;
- }
- break;
- case 2:
- printData(data);
- break;
- case 3:
- sort(data);
- break;
- case 4:
- bthead=createbt(data);
- break;
- case 5:
- fp=fopen("hfmTree.txt","w+");
- if(NULL==fp)
- {
- printf("写入哈夫曼编码错误!\n");
- return 0;
- }
- HuffManCoding(bthead,0,fp);
- g_flag=111;
- fclose(fp);
- break;
- case 6:
- printHuffManfile();
- break;
- case 7:
- if(g_flag<11)
- {
- printf("请先建立哈夫曼树.\n");
- break;
- }
- bthead=destroybt(bthead);
- g_flag=1;
- break;
- case 8:
- flag=reaHFData(hmdata);
- if(-1==flag)
- {
- printf("Open data.txt file error!\n");
- return 0;
- }
- sortHMC(hmdata);
- break;
- case 9:
- printHFData(hmdata);
- break;
- case 10:
- Encoding(hmdata);
- break;
- case 11:
- Decoding(hmdata);
- break;
- case 12:
- PrintCodeFile();
- break;
- case 13:
- PreOrderPrint(bthead,cont);
- break;
- case 14:
- destroybt(bthead);
- return 0;
- break;
- }
- }
- }
- int Encoding(HuffM d[])// 编码
- {
- FILE *fp,*pfc;
- char data[256]= {0},c;
- fp=fopen("ToBeTran.txt","r");
- pfc=fopen("CodeFile.txt","w");
- if(NULL==fp)
- {
- printf("打开文件 ToBeTran.txt 出错, 编码未完成.\n");
- return -1;
- }
- if(NULL==pfc)
- {
- fclose(fp);
- printf("CodeFile.txt 出错, 编码未完成.\n");
- return -1;
- }
- while(1)
- {
- fread(&c,1,1,fp);
- if(c>='a'&&c<='z')
- c-=32;
- if(c>='A'&&c<='Z')
- {
- //printf("%s",d[c-'A'+1].code);
- fprintf(pfc,"%s",d[c-'A'+1].code);
- }
- else if (c==' ')
- //printf("%s",d[0].code);
- fprintf(pfc,"%s",d[0].code);
- else
- //printf("%c",c);
- fprintf(pfc,"%c",c);
- //printf("%c",c);
- if(feof(fp))
- break;
- }
- fclose(fp);
- fclose(pfc);
- }
- int Decoding(HuffM d[])// 编码
- {
- FILE *fp, *pfc;
- char data[20] = { 0 },c;
- int i;//, flag
- fp = fopen("ToBeTran.txt", "r");
- pfc = fopen("TextFile.txt", "w+");
- if (NULL == fp)
- {
- printf("打开文件 ToBeTran.txt 出错, 译码未完成.\n");
- return -1;
- }
- if (NULL == pfc)
- {
- fclose(fp);
- printf("TextFile.txt 出错, 译码未完成.\n");
- return -1;
- }
- while (1)
- {
- fread(&c, 1, 1, fp);
- if (c=='1' || c=='0')
- {
- // return 1;
- for(i=0; i<27; i++)
- {
- data[i]=c;
- while (strcmp(d[i].code,data)==0)
- fprintf(pfc,"%c",d[i].ch);
- }
- }
- else
- //printf("%c",c);
- fprintf(pfc,"%c",c);
- //printf("%c",c);
- if (feof(fp))
- break;
- }
- fclose(fp);
- fclose(pfc);
- return 1;
- }
- void PrintCodeFile()
- {
- FILE *fc;
- int flag;
- char ch;
- printf("打印编码后的文件:\n");
- fc=fopen("CodeFile.txt", "r");
- if (NULL==fc)
- {
- printf("打印编码后的文件失败!!");
- exit(0);
- }
- flag = 1;
- while (!feof(fc))
- {
- ch = fgetc(fc);
- if (ch == -1)
- {
- printf("结束打印 \ n");
- }
- else
- {
- printf("%c", ch);
- if (flag <= 49)
- flag++;
- else
- {
- flag = 1;
- printf("\n");
- }
- }
- }
- fclose(fc); // 关闭文件
- }
- int PreOrderPrint(bitree *HT,int cont)
- {
- int n = 2 * (N - 3) - 1, i;
- if(NULL!=HT)
- {
- for (i = 0; i<cont; i++) printf(" ");
- printf("%c%d\n",HT->dt.ch,HT->dt.frq);
- PreOrderPrint(HT->lchild, ++cont);
- PreOrderPrint(HT->rchild, ++cont);
- }
- return 1;
- }
课程设计
来源: http://www.bubuko.com/infodetail-3105157.html