数据结构课程设计-哈弗曼树编码译码

#include<stdio.h> #include<string.h> #include<stdlib.h> #include<fstream> using namespace std; //1.结构体 typedef struct { char data; //节点的值 int weight; //权重 int parent; //双亲节点 int lchild; //左孩子节点 int rchild; //有孩子节点 }HTNode, *HuffmanTree; //存储哈弗曼树的节点类型 HuffmanTree HT; typedef char **HuffmanCode; //存储字符集编码 void Select(HuffmanTree HT,int t,int &s1,int &s2) { int i=1; s1=s2=0; HT[0].weight = 171717; while(i<=t) { if(HT[i].parent==0&&HT[i].weight<HT[s1].weight) s1=i; i++; } i=1; while(i<=t) { if(i!=s1&&HT[i].parent==0&&HT[i].weight<HT[s2].weight) s2=i; i++; } } //编码 int HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int w[],int n) { int s1,s2,m,i,start; int c,f; HTNode *p; //哈弗曼树 char *cd; if(n<=1) return 0; m=2*n-1; //形成雏树HT HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); p=HT+1; for(i=1;i<=n;i++) { p->weight=w[i]; p->parent=p->lchild=p->rchild=0; p++; } for(i=n+1;i<=2*n-1;i++) { p->weight=p->parent=p->lchild=p->rchild=0; p++; } for(i=n+1;i<=2*n-1;i++) { Select(HT,i-1,s1,s2); 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; } //编码 HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); cd =(char *)malloc (n*sizeof(char)); cd[n-1]='\0';//编码结束符 for(i=1;i<=n;i++) { start=n-1; c=i; f=HT[i].parent; while(f!=0) { if(HT[f].lchild==c) cd[--start]='0'; else cd[--start]='1'; c=f; f=HT[f].parent; } HC[i]=(char *)malloc((n-start)*sizeof(char));//第i个字符 strcpy(HC[i],&cd[start]); } free(cd); //释放空间 return 1; } ////初始化哈弗曼树，要求用户输入字符和相应权值 void InitHuff_T(HuffmanTree &HT,HuffmanCode &HC,char ch[],int &n) { int i,tem,w[100],j; //w权值 char c; char EncodeFile_Name[100]; ofstream output_file; FILE *EncodeFile,*save,*fp; /* printf("请输入编码字符集的大小 n:"); scanf("%d",&n); for(i=1;i<=n;i++) { printf("请输入第%d个字符和该字符的权值w:",i); fflush(stdin); scanf("%c%d",&ch[i],&w[i]); } */ printf("请输入你想要编码的文件名："); scanf("%s",EncodeFile_Name); if((EncodeFile=fopen(EncodeFile_Name,"r"))==NULL) { printf("Open file fail...\n"); exit(0); } c=fgetc(EncodeFile); n=(int)c-'0'; fgetc(EncodeFile); for(i=1;i<=n;i++) { c=fgetc(EncodeFile); ch[i]=c; fgetc(EncodeFile); c=fgetc(EncodeFile); w[i]=(int)c -'0'; fgetc(EncodeFile); } fclose(EncodeFile); printf("成功读取文件信息并存储！！\n"); printf("%d\n",n); //向屏幕输出字符集大小n output_file.open("data,txt"); if(!output_file) { printf("can't open file!"); } if((fp=fopen("data.txt","w"))==NULL) printf("Open file data.txt error!\n"); for(i=1;i<=n;i++) fprintf(fp,"%d\n",w[i]); fclose (fp); ch[i]='\0'; HuffmanCoding(HT,HC,w,n); //根据用户的输入，生成哈弗曼树及各个字符相应的哈弗曼编码，分别存放在HT树和HC中 if((save=fopen("htfTree.txt","w"))==NULL) { printf("OPen file fail ....\n"); exit(0); } fputc(n+'0',save); fputc('\n',save); for(i=1;i<=n;i++) { fputc(ch[i],save); printf("%c\t",ch[i]); fputc('\t',save); fputs(HC[i],save); printf("%s\n",HC[i]); fputc('\n',save); } fclose(save); } //根据哈弗曼编码将用户指定的文件中的字符编成相应的编码，并将所得编码存储到用户指定文件 void Encoding (HuffmanTree &HT,HuffmanCode &HC,char ch[],char str[]) { FILE *CodeFile; char CodeFile_Name[100]; int i,j; char c; printf("请输入编码后编码表示的信息所存到的文件的文件名："); scanf("%s",CodeFile_Name); if((CodeFile=fopen(CodeFile_Name,"w"))==NULL) {//打开文件 printf("Open file fail...\n"); exit(0); } for(i=0;i<strlen(str);i++) { c=str[i]; j=1; while(c!=ch[j]&&ch[j]!='\0') j++; if(ch[j]=='\0') { printf("字符%c无法识别",c); exit(1); } fputs(HC[j],CodeFile); printf("%s",HC[j]); } printf("\n"); fclose(CodeFile); } //译码，翻译成相应的字符表示，并存储到指定文件 void Decoding(HuffmanTree HT,char ch[],int n) { int m,i=1; char code[1000],c; char CodeFile_Name[100]; FILE *CodeFile; printf("请输入所要译的文件名："); scanf("%s",CodeFile_Name); if((CodeFile=fopen(CodeFile_Name,"r"))==NULL) { printf("Open file fail....\n"); exit(0); } c=fgetc(CodeFile); if(c==EOF) { printf("文件夹是空的！\n"); } while(c!=EOF) { code[i]=c; i++; c=fgetc(CodeFile); }//code[]译码 i=1; m=2*n-1; while(code[i]!='\0'&&m!=0) { if(code[i]=='0') m=HT[m].lchild; else m=HT[m].rchild; if(!HT[m].lchild&&!HT[m].rchild) { printf("%c",ch[m]); m=2*n-1; } i++; } printf("\n"); } //将内存中的哈夫曼树转换成凹凸表形式的树，存放在数组 T中 void Convert_tree(char T[100][100],int s,int *i,int j) { int k,l; (*i)++; l=*i; for(k=0;k<s;k++) T[l][k]=' '; T[l][k]=HT[j].weight; T[l][++k]='\0'; if(HT[j].lchild) Convert_tree(T,s+1,i,HT[j].lchild); if(HT[j].rchild) Convert_tree(T,s+1,i,HT[j].rchild); } void Print_tree(int &n) { char T[100][100]; int i,j,m=0; FILE *fp; Convert_tree(T,0,&m,2*n-1); if((fp=fopen("treeprint.txt","wb+"))==NULL) printf("Open file treeprint.txt error !\n"); printf("\n以凹凸表形式打印已经建好的哈夫曼树：\n"); for(i=1;i<=2*n-1;i++) { for(j=0;T[i][j]!=0;j++) { if(T[i][j]==' ') { printf(" "); fputc(T[i][j],fp); } else { printf("%d",T[i][j]); fprintf(fp,"%d",T[i][j]); } } printf("\n"); } fclose(fp); printf("\n此文字形式的哈夫曼树已写入文件 treeprint.txt 中\n\n"); } void welcome() { printf("\n\n"); printf("===================*============================================================\t\n"); printf(" *================================\t\n"); printf(" *==========输出哈夫曼树==========\t\n"); printf(" *================================\t\n"); printf(" *============1. 初始化===========\t\n"); printf(" *============2. 编码=============\t\n"); printf(" *============3. 译码=============\t\n"); printf(" *============4. 显示=============\t\n"); printf(" *============5. 退出=============\t\n"); printf(" *================================\t\n"); printf(" *===请输入相应操作的序号（1-5）==\t\n"); printf("===================*============================================================\t\n"); } int main() { ofstream output_file; char str[100]; HuffmanCode HC; char ch[100]; char mode; welcome(); scanf("%c",&mode); while(mode !='5') { switch(m