数据结构实验报告(哈夫曼编码加密文件)

《数据结构》实验报告题目：利用哈夫曼编码给文件或者文字加密班级：xxxx学号：xxxxxxxxxxx姓名：xxx完成时间：2010年12月19日任课教师：xxx一、问题描述用哈夫曼编码，将输入的文字，或者文件中的文字进行编码，并输出加密后的文字。二、程序总体结构主程序main显示系统时间showtime()给用户提供选择方式chioce1()显示界面告诉用户程序名称show()打开文件进行加密openfile()退出程序输入电文进行加密input()将输入(文件中)的电文进行哈夫曼编码CrtHuffmanCode(ht,hc,n)统计输入(文件中)字母的出现频率CrW(data,w,count)【fcount(alldata,data,count)】输出每一个字母所对应的哈夫曼编码Printf(hc,n,data,alldata,count)将输入(文件中)的电文创建成哈夫曼树CrtHuffmantree(ht,w,n)对输入(文件中)的文字进行哈夫曼加密showall(hc,alldata,count,data,n)1、数据结构此函数中运用到的数据结构知识就是哈夫曼树的建立以及遍历，建立主要就是每一次选择权值最小的两个数并将其求和，然后用他们的和代替这两个数，再进行求两个最小值，最后构成一个哈夫曼数；遍历是采用从叶子结点开始向根节点确定唯一的路径。2、主要函数：（1）voidCrtHuffmantree(HuffmanTree&ht,intw[],intn)，功能是建立一个哈夫曼树；（2）voidCrtHuffmanCode(HuffmanTreeht,HuffmanCodehc,intn)，功能是计算哈夫曼编码；（3）voiddianwen(intcount[],charalldata[])，功能是统计输入电文的字母种类以及频率；（4）intfcount(charalldata[],chardata[],intcount[])，功能是统计打开文件中出现的字母的种类以及频率；（5）voidshowtime()，功能是查看系统当前的时间；（6）intsearch(charch,chardata[],intn)，查询电文中的每一个字母所对应得哈夫曼编码的下标；（7）voidPrintf(HuffmanCode&hc,intn,chardata[],charalldata[],intcount[])，功能是输出每一个字母所对应的哈夫曼编码；（8）voidshowall(HuffmanCodehc,charalldata[],intcount[],chardata[],intn)，功能是输出经过加密后的密文。三、源代码#includestdio.h#includestdlib.h#includetime.h#includestring.h#defineN27//定义最大叶子结点个数#defineM2*N-1typedefstruct//定义哈夫曼结构体{intweight;intparent;intLChild;intRChild;}HTNode,HuffmanTree[M+1];//0号单元不用typedefchar*HuffmanCode[N+1];//存储哈夫曼编码串的头指针//调用系统的时间voidshowtime(){time_tt;tm*tp;t=time(NULL);tp=localtime(&t);printf(\n\n\t\t\t%d/%d/%d\n,tp-tm_mon+1,tp-tm_mday,tp-tm_year+1900);printf(\n\t\t\t%d:%d:%d\n,tp-tm_hour,tp-tm_min,tp-tm_sec);}//**************计算电文中各个英文字母出现的次数*******************voiddianwen(intcount[],charalldata[]){intn,i;printf(〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓);printf(\n\n\n\t\t\t\t请输入电文：\n);fflush(stdin);for(i=0;i27;i++)//将数组计数器初始化count[i]=0;printf(%c,7);alldata[0]=getchar();while(alldata[count[0]]!='\n'){n=(alldata[count[0]]-'a')+1;count[n]++;count[0]++;//所有字母的总个数alldata[count[0]]=getchar();}}voidCrW(chardata[],intw[],intcount[])//存储数据以及权值信息{inti,j;j=0;for(i=1;i=26;i++){if(count[i]!=0){j++;data[j]=char(i-1+'a');w[j]=count[i];}}w[0]=j;//用于存储字母出现的种类个数}voidselect(HuffmanTree&ht,intn,int&s1,int&s2)//查找一串数字中的两个最小值{inti,t;s1=0;s2=0;ht[0].weight=65535;for(i=1;i=n;i++){if(ht[i].weightht[s1].weight&&ht[i].parent==0){t=s1;s1=i;if(ht[t].weightht[s2].weight){s2=t;}}elseif(ht[i].weightht[s2].weight&&ht[i].parent==0)s2=i;else;}}voidCrtHuffmantree(HuffmanTree&ht,intw[],intn)//创建哈夫曼树{inti,m;ints1,s2;for(i=1;i=n;i++)//初始化叶子结点{ht[i].weight=w[i];ht[i].parent=0;ht[i].LChild=0;ht[i].RChild=0;}m=2*n-1;for(i=n+1;i=m;i++)//初始化其他结点{ht[i].weight=0;ht[i].parent=0;ht[i].LChild=0;ht[i].RChild=0;}for(i=n+1;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;}}//计算哈夫曼编码voidCrtHuffmanCode(HuffmanTreeht,HuffmanCodehc,intn){inti,start,c,p;char*cd;cd=(char*)malloc((n+1)*sizeof(char));cd[n-1]='\0';for(i=1;i=n;i++){start=n-1;c=i;p=ht[i].parent;while(p!=0){--start;if(ht[p].LChild==c)cd[start]='0';elsecd[start]='1';c=p;p=ht[p].parent;}hc[i]=(char*)malloc((n-start)*sizeof(char));strcpy(hc[i],&cd[start]);}free(cd);}//查找字母所对应的哈夫曼编码intsearch(charch,chardata[],intn){inti;for(i=1;i=n;i++){if(ch==data[i])returni;elsei++;}return1;}//显示所有文字的哈夫曼编码voidshowall(HuffmanCodehc,charalldata[],intcount[],chardata[],intn){inti,m;system(cls);printf(〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓\n\n);printf(\t\t\t所有电文经过哈夫曼编码加密之后如下\n%c,7);printf(\n\n◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆);for(i=0;icount[0];i++){m=search(alldata[i],data,n);printf(%s,hc[m]);}printf(\n◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆\n\n);system(pause);}//输出哈夫曼编码voidPrintf(HuffmanCode&hc,intn,chardata[],charalldata[],intcount[]){inti;system(cls);printf(\n\n★★★各个字母所对应的哈夫曼编码★★★\n\n%c,7);for(i=1;i=n;i++){printf(\t字母%c对应的哈夫曼码为：,data[i]);puts(hc[i]);}printf(\n\n★★★各个字母所对应的哈夫曼编码★★★\n\n);printf(\n\n按任意键查看所有文字的加密结果……\n\n);system(pause);showall(hc,alldata,count,data,n);//查看文字的加密结果}//首界面窗口界面美化工作voidshow(){inti;printf(\n\n\n%c,7);for(i=0;i30;i++)printf(%c=,2);printf(\n\n\n\t\t欢迎使用哈夫曼编码加密系统\n\n\n);for(i=0;i30;i++)printf(%c=,2);printf(\n\n\t\t);system(pause);system(cls);}//输入文字加密voidinput(){charalldata[1000];intn,w[N];//w[]用于存储所出现的字母频率，w[0]用于存储出现字母种类的个数intcount[27];//用于存储所有字母出现的频率，count[0]用于存储字母的总个数chardata[N];//用于存储所出现过的字母HuffmanTreeht;HuffmanCodehc;dianwen(count,alldata);CrW(data,w,count);n=w[0];CrtHuffmantree(ht,w,n);CrtHuffmanCode(ht,hc,n);Printf(hc,n,data,alldata,count);}//计算文件中每一个字母出现的频率intfcount(charalldata[],chardata[],intcount[]){inti=0,k=0,n,j;HuffmanTreeht;HuffmanCodehc;for(j=0;j27;j++)count[j]=0;while(alldata[i]!='\0'){n=alldata[i]-'a'+1;count[n]++;//统计每一个字符出现的频率data[n]=char(n-1+'a');count[0]++;//统计文件中字母的总个数i++;}for(j=0;j27;j++){if(count[j]==0){k++;}if(k!=0&&count[j]!=0){count[j-k]=count[j];count[j]=0;k++;}}n=26-k;CrtHuffmantree(ht,count,n);CrtHuffmanCode(ht,hc,n);Printf(hc,n,data,alldata,count);return0;}//打开文件加密voidopenfile(){FILE*fp;charalldata[1000];intcount[27],i=0;chard