首页 > 代码库 > 数据结构课程设计-哈夫曼编码译码
数据结构课程设计-哈夫曼编码译码
//******************************************** //程序功能:哈夫曼编码及译码 // //日期:2014年11月18 // //******************************************** #include<stdio.h> #include<stdlib.h> #include<string.h> #include <windows.h> #define MAX 128 //叶子节点个数(对应ASCII码) #define M 2*MAX-1 //树的节点个数 typedef struct node{ int weight; //权值 int parent; //双亲位置 int LChild; //左孩子位置 int RChild; //右孩子位置 }HTNode,HuffmanTree[M+1]; typedef struct Node{ char letter;//字符 char* code;//编码 int w;//权值(对应文章中字母(letter)出现次数) }Huffman[MAX+1]; HuffmanTree ht; //存储哈夫曼树 Huffman qz; //权值相关信息 int weight[M+1]={0}; //存储临时权值 int t=0; //存储叶子节点个数 /*********************函数声明**********************/ void select(int *s1,int *s2);//建立哈夫曼树时的选择权值 int ReadWeight();//从文件中读文章获得权值,返回权值个数 void CrtHuffmanTree();//建立哈夫曼树 void Encoding();//编码 void Print();//打印 void WriteTree();//向文件中写入哈夫曼树 void Initialization();//初始化 void WriteCode();//向文件中写入编码 void Decoding();//译码 int find_letter(char ch);//查找字符 int find_code(char s[]);//查找编码 void InitTree();//初始化树 void TreePrinting();//打印哈夫曼树 void Menu();//菜单 void load();//loading void _print(FILE *fp,node hft,int n); //主函数 int main() { Menu();//调用菜单,完成一系列工作 return 0; } void Menu() { char chose; load(); InitTree(); printf("**************************Menu*************************\n"); printf("******初始化(I)***********编码(E)********译码(D)*******\n"); printf("****打印代码文件(P)***打印哈夫曼树(T)****退出(O)*******\n"); printf("*******************************************************\n"); while(true){ printf("请选择:"); scanf("%c",&chose); getchar();//除去回车 switch(chose){ case 'I':Initialization();break; //初始化 case 'E':Encoding();break; //对叶子节点进行编码 case 'D':Decoding();break; //译码 case 'P':Print();break; //打印编码 case 'T':TreePrinting();break; //打印哈夫曼树 case 'O': printf("要退出了哦!\n"); //退出提醒 Sleep(2000); //挂起 exit(1); //退出程序 default:printf("怎么能选错呢!\n"); } } } //loading void load() { printf("loading"); for(int i=1;i<=10;i++){ printf("."); Sleep(500); } printf("\n就要进入啦!\n"); Sleep(2000); } //初始化树 void InitTree() { ht[0].weight = 0;//标志哈夫曼树是否存在 qz[0].w = 0; //标志是否编码 } //初始化 void Initialization() { ht[0].weight = 1; //初始化标志,说明哈夫曼树以存在 t=ReadWeight(); //读取权值 CrtHuffmanTree(); //建立哈夫曼树 WriteTree(); //将哈夫曼树写入文件 printf("耶!'初始化'成功啦!\n"); } //将哈夫曼树写入文件 void WriteTree() { FILE *fp;//hfmTree 文件指针 int m=2*t-1; int i; //打开文件 if((fp=fopen("F:\\hfmTree.txt","w")) == NULL){ printf("open hfmTree.txt--file error\n"); exit(0); }//else printf("open hfmTree.txt--file sucess!\n"); //哈夫曼树写入文件 for(i=1;i<=m;i++) fprintf(fp,"%d %d %d %d\n",ht[i].weight,ht[i].parent,ht[i].LChild,ht[i].RChild); //关闭文件 if(fclose(fp)){ printf("close hfmTree.txt--file error!\n"); exit(0); }//else printf("close hfmTree.txt--file success!\n"); } //选择s1,s2 void select(int n,int *s1,int *s2) { int i; int min; //寻找一个没有双亲的节点,找到后退出循环 for(i=1; i<=n; i++){ if(ht[i].parent == 0){ min = i; break; } } //寻找最小无双亲节点 for(i=1; i<=n; i++){ if(ht[i].weight<ht[min].weight && ht[i].parent == 0) min = i; } *s1 = min; //寻找次最小无双亲节点 for(i=1; i<=n; i++){ if(ht[i].parent == 0 && i != *s1){ min = i; break; } } for(i=1; i<=n; i++){ if(ht[i].weight < ht[min].weight && i != *s1 && ht[i].parent == 0) min = i; } *s2 = min; } //读取文章,获取权值 int ReadWeight()//返回权值个数 { int n=1; FILE *fp; char ch; //打开文件 if((fp=fopen("F:\\ToBeTran.txt","r")) == NULL){ printf("Open ToBeTran.txt--file error!\n"); exit(0); }//else printf("open ToBeTran.txt--file sucess!\n"); //读取字符 while(!feof(fp)){//一直循环,知道文件结束 ch = fgetc(fp); if(ch != EOF){ weight[ch]++; } } //关闭文件 if(fclose(fp)){ printf("close ToBeTran.txt--file error!\n"); exit(0); }//else printf("close ToBeTran.txt--file success!\n"); //临时权值转化到qz[]中 for(int i=0;i<M;i++){ //printf("%d ",weight[i]); if(weight[i]>=1){ qz[n].letter = (char)i; qz[n].w = weight[i]; n++; } } return n-1;//n从1开始计数 } //建立哈夫曼树 void CrtHuffmanTree() { int i,s1,s2,m = 2*t-1; //*初始化*// for(i=1; i<=t; i++){//第1到n个位置放置n个叶子节点 ht[i].weight = qz[i].w; ht[i].parent = ht[i].LChild = ht[i].RChild = 0; } for(i=t+1;i<=m;i++){//第n+1个到第m个位置放置非叶子节点 ht[i].weight = ht[i].parent = ht[i].LChild = ht[i].RChild = 0; } //*建立*// for(i=t+1; i<=m; i++){ select(i-1,&s1,&s2); //printf("s1 = %d,s2 = %d\n",s1,s2); ht[i].weight = ht[s1].weight + ht[s2].weight; ht[s1].parent = ht[s2].parent = i; ht[i].LChild = s1; ht[i].RChild = s2; } } //哈夫曼编码 void Encoding() { if(ht[0].weight == 0){ printf("哇哦!!居然没初始化!!\n"); Sleep(2000);//挂起一段时间 return; } int i,start,c,p; char *cd; cd = (char*)malloc(t*sizeof(char)); cd[t-1]='\0'; for(i=1; i<=t; i++){//对n个叶子节点进行编码 start = t-1;//定位到临时编码数组的最后一位 c = i;//记录当前节点位置 p = ht[i].parent;//记录当前节点的双亲位置 while(p!=0){ --start; if(ht[p].LChild == c)//若该节点是其双亲的左孩子,则编码0 cd[start]='0'; else//若为右孩子则编码1 cd[start]='1'; c = p;//下次循环的准备条件 p = ht[p].parent; } qz[i].code=(char*)malloc((t-start)*sizeof(char)); strcpy(qz[i].code,&cd[start]); } free(cd); //以上代码完成编码工作 /*测试代码 for(i=1;i<=n;i++) printf("%c %d %s\n",hc[i].letter,hc[i].w,hc[i].code);*/ //将编码写入文件 WriteCode(); /*for(i=1;i<=n;i++){ printf("%s\n",hc[i].code); }*/ qz[0].w = 1;//标志以编码 printf("耶!'编码'成功啦!\n"); } //编码写入函数 void WriteCode() { FILE *fp_code,*fp_text; char ch; int i; //打开编码存储文件 if((fp_code=fopen("F:\\CodeFile.txt","w")) == NULL){ printf("open CodeFile.txt--file error !\n"); exit(0); }//else printf("open CodeFile.txt--file success!\n"); //打开需要编码的文本文件 if((fp_text=fopen("F:\\ToBeTran.txt","r")) == NULL){ printf("open ToBeTran.txt--file error !\n"); exit(0); }//else printf("open ToBeTran.txt--file success!\n"); while(!feof(fp_text)){ ch = fgetc(fp_text); //printf("%c ",ch); i = find_letter(ch); //printf("i = %d\n",i); if(i!=0) fprintf(fp_code,"%s ",qz[i].code); } //关闭文件 if(fclose(fp_code)){ printf("close CodeFile.txt--file error!\n"); exit(0); }//else printf("close CodeFile.txt--file success !\n"); if(fclose(fp_text)){ printf("close ToBeTran.txt--file error!\n"); exit(0); }//else printf("close ToBeTran.txt--file success !\n"); } //查找字符 int find_letter(char ch) { int low,high,i; low = 1;high = t; //二分查找 while(high - low >= 0){ i=(low+high)/2; if(qz[i].letter == ch) return i; else if(qz[i].letter < ch){ low = i+1; } else high = i-1; } return 0; } //打印哈夫曼树的节点权值 void Print() { if(ht[0].weight == 0){ printf("哇哦!!居然没初始化!\n"); Sleep(2000);//挂起一段时间 return; } if(qz[0].w == 0){ printf("哇塞!!居然没编码!!\n"); Sleep(2000); return; } int i=0; char code[100]; FILE *fp_r,*fp_w; if((fp_r=fopen("F:\\CodeFile.txt","r")) == NULL){ printf("open CodeFile.txt--file error!\n"); exit(0); }//else printf("open CodeFile.txt success!\n"); if((fp_w=fopen("F:\\CodePrint.txt","w")) == NULL){ printf("open CodePrint.txt--file error!\n"); exit(0); }//else printf("open CodePrint.txt success!\n"); while(!feof(fp_r)){ fscanf(fp_r,"%s\n",code); printf("%s ",code); fprintf(fp_w,"%s",code); i++; if(i%5 == 0){ printf("\n"); fprintf(fp_w,"\n"); } } printf("耶!'打印'成功啦!\n"); } //译码 void Decoding() { if(ht[0].weight == 0){ printf("哇哦!!居然没初始化!\n"); Sleep(2000);//挂起一段时间 return; } if(qz[0].w == 0){ printf("哇塞!!居然没编码!!\n"); Sleep(2000);//挂起一段时间 return; } char code[100]; FILE *fp_r,*fp_w; int i; //打开CodeFile.txt文件,从中读取编码 if((fp_r=fopen("F:\\CodeFile.txt","r")) == NULL){ printf("open CodeFile.txt--file error!\n"); exit(0); }//else printf("open CodeFile.txt success!\n"); //打开TextFile.txt文件,存储翻译的内容 if((fp_w=fopen("F:\\TextFile.txt","w")) == NULL){ printf("open TextFile.txt--file error!\n"); exit(0); }//else printf("open TextFile.txt success!\n"); while(!feof(fp_r)){ fscanf(fp_r,"%s\n",code); i = find_code(code); if(i!=0) fprintf(fp_w,"%c",qz[i].letter); } if(fclose(fp_r)){ printf("close CodeFile.txt--file error!\n"); exit(0); }//else printf("close CodeFile.txt--file success !\n"); if(fclose(fp_w)){ printf("close TextFile.txt--file error!\n"); exit(0); }//else printf("close TextFile.txt--file success !\n"); printf("耶!'译码'成功啦!\n"); } int find_code(char s[])//查找编码 { int i; for(i=1;i<=t;i++){ if(strcmp(qz[i].code,s) == 0) return i; } return 0; } void TreePrinting() { if(ht[0].weight == 0){ printf("哇哦!!居然没初始化!\n"); Sleep(2000);//挂起一段时间 return; } FILE *fp; int i,r=t*2-1; //打开文件 if((fp=fopen("F:\\TreePrint.txt","w")) == NULL){ printf("open CodeFile.txt--file error !\n"); exit(0); } for(i=1;i<=r;i++){ if(ht[i].parent == 0) break; } //printf("%d\n",ht[i].parent ); _print(fp,ht[i],0); if(fclose(fp)){ printf("close hfmTree.txt--file error!\n"); exit(0); } printf("耶!'打印'成功啦!\n"); } //哈夫曼树纵向显示并写入文件 void _print(FILE *fp,node hft,int n) { if(hft.LChild == 0 && hft.RChild == 0){ for(int i=0;i<n;i++){ printf(" "); fprintf(fp," "); } printf("%-6d\n",hft.weight); fprintf(fp,"%-6d\n",hft.weight); return ; } _print(fp,ht[hft.RChild],n+2); for(int i=0;i<n;i++){ printf(" "); fprintf(fp," "); } printf("%-6d\n",hft.weight); fprintf(fp,"%-6d\n",hft.weight); _print(fp,ht[hft.LChild],n+2); }
数据结构课程设计-哈夫曼编码译码
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。