一、实习题目
题目3.在一个加密应用中,要处理的信息来自下面的字符集,各个字符的相关使用频度如下:
字符空格ABCDEFGHIJKLM
频度1806413233210322154757153120
字符NOPQRSTUVWXYZ
频度5563151485680257182161
现请编写程序你实现如下功能:
(1)运行时,由用户输入来初始化字符集大小和相应用字符。
(2)输入一个要加密的字符串,将其加密。
(3)输出解密字符串。
二、程序的功能
依次输入26个字符(A到Z)的使用频度,使用频度作为字符的权值,利用权值进行创建哈夫曼树的操作,再进行哈夫曼编码,得到各个字符的编码。根据用户输入的字符串,将其字符串加密,再输出解密字符串。
三、要求
1、用户输入字符的权值
2、输入需要加密的字符串
4、译码
四、分析
createtree函数:创建哈夫曼树。先初始化哈夫曼树,然后根据输入的A到Z各个字母权值创建一棵哈夫曼树。
bianma函数:根据已建好的哈夫曼树,设置左子树为0,右子树为1,得到字符的哈夫曼编码。用户输入需要加密的字符串,输出其密文。
jiema函数:根据用户输入的要解码的0,1代码,输出其字符串内容。
main函数:依次调用createtree函数、bianma函数、jiema函数。
五、代码
#include<iostream> using namespace std; const int n=26; struct htree { int weight; int parent,lchild,rchild; }; htree hfmt[2*n]; //定义结构体数组,2*n=2*n-1+1 struct hcode { int bits[n+1]; int start; char ch; }; hcode hfmc[n+1]; void creattree() //创建哈夫曼树 { int i,j; int i1,i2; int w1,w2; for(i=1;i<=2*n-1;i++) { hfmt[i].weight=0; hfmt[i].parent=0; hfmt[i].lchild=0; hfmt[i].rchild=0; } cout<<"请按顺序输入A到Z各个字母的权值:"<<endl; for(i=1;i<=n;i++) cin>>hfmt[i].weight; for(i=n+1;i<=2*n-1;i++) { i1=i2=0; //i1和i2指向两个最小值得位置 w1=w2=10000; //w1和w2分别指两个最小的权值 for(j=1;j<=i-1;j++) //选择两个最小值 if(hfmt[j].parent==0) if(hfmt[j].weight<w1) { w2=w1; w1=hfmt[j].weight; i2=i1; i1=j; } else if(hfmt[j].weight<w2) { w2=hfmt[j].weight; i2=j; } hfmt[i1].parent=i; hfmt[i2].parent=i; hfmt[i].weight=hfmt[i1].weight+hfmt[i2].weight; hfmt[i].lchild=i1; hfmt[i].rchild=i2; } } void bianma() //哈夫曼编码 { hcode cd; int a,b; int i; for(i=1;i<=n;i++) { cd.start=n+1; cd.ch=64+i; a=i; b=hfmt[i].parent; while(b!=0) { cd.start--; if(hfmt[b].lchild==a) cd.bits[cd.start]=0; else cd.bits[cd.start]=1; a=b; b=hfmt[b].parent; } hfmc[i]=cd; } cout<<endl; for(i=1;i<=n;i++) { cout<<"字符"<<hfmc[i].ch<<"的权值为:"<<hfmt[i].weight<< endl<<"编码为:"; for(int j=hfmc[i].start;j<=n;j++) cout<<hfmc[i].bits[j]; cout<<endl; } cout<<endl; char z; cout<<"请输入要加密的字符串:"; cin>>z; cout<<"密文为:"; if(z==hfmc[i].ch) for(int j=hfmc[i].start;j<=n;j++) cout<<hfmc[i].bits[j]; } void jiema() { int i=2*n-1; char s; cout<<"请输入要解码的0,1代码:"; cin>>s; cout<<endl; cout<<"所输入的内容为:"; while((s=='0')||(s=='1')) { if(s=='0') i=hfmt[i].lchild; else i=hfmt[i].rchild; if(hfmt[i].lchild==0) { cout<<hfmc[i].ch; i=2*n-1; } cin>>s; } } void main() { creattree(); bianma(); jiema(); }
六、运行结果
1、根据题目给定的使用频度,输入其权值:
2、然后各个字符的权值及哈夫曼编码显示为:
3、输入需要加密的字符串:
4、密文为:(因程序虽然可通过编译,但运行时没得到预期的结果,所以此处出现错误)
5、如果删除需要加密的字符串以及显示密文的相关代码,则可得:
(1)请输入需要解码的0,1代码:
七、收获和体会及不足
收获和体会:
经过这次的课程设计,我深刻地了解到自己的不足。一开始拿到题目的时候我还认为挺好写的,但等我真正开始去写的时候才知道无从下手。首先要用到哈夫曼编码,这是在课堂上讲过的,我也细看了书本上的哈夫曼算法,要补充书本上的算法不容易。我也上网查阅过了一些资料,有些是加密文件里的字符串,这些可以借鉴,但是我没打算用文件加密。最后,我也试着开始下手写代码,先构思算法的思想,再一步一步设计算法。
完成了代码后,我加深了对哈夫曼编码算法的了解,也重温了一边C++的一些知识应用,实践就是对知识最好的应用。不过在编写代码的过程中我遇到了很多问题,比如有些知识点我已经遗忘了,我就去翻找C++课本;又比如编译是没问题的,可是运行的时候没有得到我预期的效果,改来改去总是改不好。编写代码最重要的是细心,错写一个字母也会运行不了,以后我编写代码的时候还要更加细心。
不足:
因为时间关系我没有设置界面,所以界面看起来不美观,还有代码其实还是有错误的,虽然能运行,但是结果不理想,代码比较简单。根据这些不足,我以后会改进的。