数据结构课设-哈夫曼编码译码器

#include<stdio.h> #include<stdlib.h> #include<string.h> #include<windows.h> #define N 100 //最大叶子结点数 #define M 2*N-1 //最大结点数 #define MAXINT 32767 #define ch 30 #define NUM 100 typedef char numcode;//编码 typedef char charcode;//字符 typedef char* HuffmanCode[N] ; typedef struct{ char data;//字符 int weight;//权值 int parent; int lchild; int rchild; }HTNode,HuffmanTree[M]; void CrtHuffmanTree(HuffmanTree ht,int w[],int n); void select(HuffmanTree ht,int pos,int *s1,int *s2); void CrtHuffmanTree(HuffmanTree ht,int w[],int n)//创建哈夫曼树 { int i,s1,s2;//s1,s2分别为最小的和次小的 int m=2*n-1;//m为总共的结点数 for(i=0;i<n;i++){//前n个结点赋权值，父亲以及左右孩子全部初值为-1 ht[i].weight=w[i];ht[i].parent=-1; ht[i].lchild=-1;ht[i].rchild=-1; } for(i=n;i<m;i++){//前n个结点赋权值0，父亲以及左右孩子全部初值为-1 ht[i].weight=0;ht[i].parent=-1; ht[i].lchild=-1;ht[i].rchild=-1; } for(i=n;i<m;i++) {//生成新结点 select(ht,i-1,&s1,&s2); //调用选择函数 ht[i].weight=ht[s1].weight+ht[s2].weight; ht[s1].parent=i; ht[s2].parent=i; ht[i].lchild=s1; ht[i].rchild=s2; } } void select(HuffmanTree ht,int pos,int *s1,int *s2)//选择节点 ,pos为新结点以前所有节点 { int i,j,m1,m2; m1=m2=MAXINT; for(j=0;j<=pos;j++) {//寻找的过程中相当于s2每次都指向s1指过的， //每次s1都指向更小的一个 if(ht[j].weight<m1&&ht[j].parent==-1){//权值小于m1,且没有被选过 m2=m1;//最小和次小同时进行寻找 *s2=*s1;//s2指向前一次s1指向的位置 *s1=j;m1=ht[j].weight;//最小 } else if(ht[j].weight<m2&&ht[j].parent==-1){ m2=ht[j].weight; *s2=j;//次小 } } } void CrtHuffmanCode(HuffmanTree ht,HuffmanCode hc,int n){ char *cd;//编码指针 int start,c,p,i;//孩子，父亲 cd=(char*)malloc(n*sizeof(char));//存放编码 cd[n-1]='\0';//末尾设置 标志 for(i=0;i<n;i++){ start=n-1;c=i;//i从第一个叶子结点开始,共n个叶子结点 p=ht[i].parent; while(p!=-1){//最顶端的结点parent=-1 start--;//每走一步，没到头，则start往前 走一步 if(ht[p].lchild==c)//走的结点是左孩子 cd[start]='0'; else //走的孩子是右孩子 cd[start]='1'; c=p;p=ht[p].parent;//继续往上走，更换新的孩子和父亲 } hc[i]=(char*)malloc((n-start)*sizeof(char));//n-start为真正译码的长度个数 strcpy(hc[i],&cd[start]);//每次循环后将译码复制到haffcode中 } free(cd); } void printcode(char s[],HuffmanCode hc,int length)//打印输出各字符 //有序无重复字符 树码 叶子数 { int i; for( i=0;i<length;i++){ printf("\t\t\t\t%c:",s[i]); printf("%s\n",hc[i]); } } void chartocode(charcode c[],char s[],HuffmanCode hc,int length){ printf("\n"); int i=0,j; FILE *fp; if((fp=fopen("C:\\Users\\yangxueqian\\Desktop\\编码后文件.txt","wt"))==NULL) //编码后的文件 { printf("写文件出错！！按任意键退出。"); //getch(); exit(0); } while(c[i]!='\0'){ //比对到文件末尾 for(j=0;j<length;j++){ if(c[i]==s[j]) { printf("%s",hc[j]); fprintf(fp,"%s",hc[j]) ;//将标准数组中比对的编码写入编码后文件中 // printf("%s",hc[j]); } } i++; } printf("\n"); fclose(fp); //printf("按任意键返回主菜单！！！"); //getch(); } void numtochar(numcode ns[],HuffmanTree ht,char s[],int length) { printf("\n"); FILE *fp; if((fp=fopen("C:\\Users\\yangxueqian\\Desktop\\译码后文件.txt","wt"))==NULL)//译码后的文件 { printf("写文件出错！！按任意键退出。"); exit(0); } int m,i=0; int key; HTNode g;//哈夫曼结点 m=2*length-1; while(ns[i]!='\0'){ g=ht[m-1];//第m个结点下标为m-1,表中最后一个元素，树的最上面元素 while(g.lchild!=-1&&g.rchild!=-1){//当没有到叶子节点 switch(ns[i]){//根据数组中的编码换左右孩子 case '0':key=g.lchild;g=ht[g.lchild];break; case '1':key=g.rchild;g=ht[g.rchild];break; } i++; }//跳出时到叶子，打印 printf("%c",s[key]); fprintf(fp,"%c",s[key]) ;//根据比对有序不重复数组s,并写入到文件中去 } fclose(fp); } void print1() { int i; system("cls"); printf("\n\n"); printf("\t\t|******************************|\n"); printf("\t\t||****************************||\n"); printf("\t\t||| |||\n"); printf("\t\t||| 欢迎进入1.0版编码系统 |||\n"); printf("\t\t||| |||\n"); printf("\t\t||****************************||\n"); printf("\t\t|******************************|\n"); printf("\n\t\t\t系统开始启动.........\n"); printf("============================================================================\r"); // for(i=1;i<77;i++) // { // Sleep(30); // printf(">"); // } } void print2() { system("cls"); printf("\n\n\n\n"); printf("\t\t\t|******************************|\n"); printf("\t\t\t||****************************||\n"); printf("\t\t\t||| |||\n"); printf("\t\t\t||| 谢谢使用 |||\n"); printf("\t\t\t||| |||\n"); printf("\t\t\t||****************************||\n"); printf("\t\t\t|******************************|\n"); Sleep(2000); } void print3() { system("cls"); printf("\t\t\t|*******************************|\n"); printf("\t\t\t| 欢迎来到1.0版编码世界 |\n"); printf("\t\t\t|*******************************|\n"); printf("\t\t\t| 1.初始化源文件 |\n"); printf("\t\t\t| 2.查询字符的编码 |\n"); printf("\t\t\t| 3.查询编码后的文件 |\n"); printf("\t\t\t| 4.查询译码后的文件 |\n"); printf("\t\t\t|-------------------------------|\n"); printf("\t\t\t|-------------------------------|\n"); printf("\t\t\t| 0.退出程序 |\n"); printf("\t\t\t|===============================|\n"); } void save_in_f1()//创建文件 { char ch1[100]; FILE *fp; if((fp=fopen("C:\\Users\\yangxueqian\\Desktop\\新建文本文件.txt","wt"))==NULL) { printf("写文件出错！！按任意键退出。"); //getch(); exit(0); } printf("请输入原始文档：\n"); scanf("%s",ch1);//写原始文件中的内容 fprintf(fp,"%s",ch1) ;//将所写内容存到新文件中 printf("%s",ch1);//显示文档内容 printf("保存成功！！请按任意键继续。\n"); fclose(fp); printf("按任意键返回主菜单！！！"); //getch(); } int main(){ print1(); HuffmanTree ht;//ht哈夫曼树 HuffmanCode hc;//hc哈夫曼编码 charcode c[1000];//存放字符char numcode ns[1000];//存放译码char int n;//叶子结点个数 int count[95]={0};//存放出现次数，共95个字符 int w[N]={0};//存放权值 int i,j,k; int loop; int num=0; int length;//长度 int choice;//用户选择 int back;//0\1返回 char s[1000]={0};//存放有序无重复的字符 char b[1000]={0};//存放文件中所有的字符 FILE *fp; loop1: if((fp=fopen("C:\\Users\\yangxueqian\\Desktop\\新建文本文件.txt", "rw"))==NULL) printf("读取失败!"); else { i=0; while(!feof(fp)) { b[i]=fgetc(fp);//将fp指向的文件中的内容一个字符逐一放到b[]中 i++; // printf("%d\t",i); } } length=i; for( j=0;j<length;j++) { ++count[b[j]-32];//统计,ASCII码从32开始才是字符，因此减去32 } for(k=0,j=0;k<95;k++)//从32-127之间是字符，之间相差95个 if(count[k])//当字符出现过 { w[j]=count[k];//将频率作为权值 s[j]=k+32; j++;//不能将j++放在for循环里面，因为这样子就相当于将count复制了，存在k才++ } length=j;//计算的真正字符个数 CrtHuffmanTree(ht,w,length);// 建树 //树 权值 叶子个数 CrtHuffmanCode(ht,hc,length);//编码 //树 码数组 叶�