课程设计--哈夫曼编码与译码

课程 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 --哈夫曼编码与译码 《哈夫曼编码与译码》 第 1 页 共 34 页 哈夫曼编码与译码 学生姓名: 指导老师: 摘 要 本课程设计主要解决的是利用哈夫曼树生成的哈夫曼编码进行字符串的加密和解密，并将加密的编码写入文件。在此课程设计中，系统开发平台为Windows XP，程序设计语言采用面向过程的高级语言C和面向对象的高级语言C++，程序运行平台为Visual C++ 6.0。在程序设计中，采用了结构化与面向过程两种解决问题的方法。程序通过调试运行，初步实现了设计目标，并且经过适当完善后，将可以应用在商业中解决实际问题。 关键词 哈夫曼树，编码，译码，文件操作，C，C++; 1 引 言 1.1 课题背景 随着信息时代的到来，各种信息日益丰富，信息迅速膨胀，对信息管理的工作量也日益增大。在信息化未到来之前，信息的存储编码也变得尤为重要，公司之间的信息需要编码，用户个人数据需要编码，都需要占用很大的空间，所以一个好的、高效的编码译码算法是十分重要的。好的加密算法不仅可以降低管理方的工作量和存储量，还可以对用户的信息进行高效的管理，同时使在用中可以避免不必要的麻烦。 数据结构是指相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。数据的逻辑结构(logical structure)是指数据元素之间逻辑关系的整体。所谓逻辑关系是指数据元素之间的关联方式或邻接关系。根据数据元素之间逻辑关系的不同，数据结构分为四类:集合、线性结构、树结构、图结构。数据的逻辑结构属于用户视图，是面向问题的，反映了数据内部的构成方式。为了区别于数据的存储结构，常常将数据的逻辑结构称为数据结构。数据的存储结构(storage structure)又称为物理结构，是数据及其逻辑结构在计算机中的表示，换言之，存储结构除了数据元素 《哈夫曼编码与译码》 第 2 页 共 34 页 之外，必须隐式或显示地存储数据元素之间的逻辑关系。通常有两种存储结构:顺序存储结构和链接存储结构。 树是一种在实际应用中被广泛使用的数据结构。它是由同一类型的记录构成的集合。哈夫曼树是树的一种子类型，又称最优树，是一类带权路径最短的树，利用哈夫曼树可以得到合适的字符编码，这样我们既可以对数据加密，也可以实现高效的存储信息。因此哈夫曼编码是一种常用的编码方式。 1.2 课程设计目的 哈夫曼编码与译码系统是为了实现信息的高效存储与管理、加密、解密而设计的。通过建立一个有效，低存储量，易于管理的编码译码系统，使得企业对信息管理更加高效、准确，更加科学化和正规化，降低企业对信息管理的难度。 本课程设计主要是用数据结构和文件实现的，通过程序的编写、调试和运行可以进一步掌握数据结构及算法的程序实现的基本方法。理解对数据结构的基本知识及应用，同时加深对哈夫曼树的运用及理解。本课程设计是利用哈夫曼编码实现对字符串的加密、解密和低存储量存储，程序实现哈夫曼树的建立和哈夫曼编码的生成，实现字符串的快速编码、解密和保存。掌握哈夫曼编码的工作原理，熟悉建立哈夫曼树、利用哈夫曼编码进行实际编码、解码等功能的实现，同时加深对文件的操作原理。 1.3课程设计内容 本课程设计主要是采用哈夫曼编码对字符串的编码、解码，同时实现地存储量要求。在设计的过程中，共用到两种数据元素，第一种是哈夫曼树建立是用到树的结构，树节点信息包括父节点、左子树节点、右子树节点以及该节点的权值其信息如图1-1所示，第二种是在存储个字符对应编码时用到的结构，其中包括字符、字符密文以及其长度，如图1-2所示: 《哈夫曼编码与译码》 第 3 页 共 34 页 树节点信息 父节点 左子树节点 右子树节点 权值 图1-1 树节点数据元素 编码信息 字符 编码 编码长度 图1-2 每个字符密文数据元素 程序功能是实现对用户输入信息的编码与解码，并存入文件中，具体如图1-3所示: 《哈夫曼编码与译码》 第 4 页 共 34 页 哈夫曼编码与译码 利得将对输 用到编用入 字哈码户字 符夫存输符 和曼入入串 权编文字或 值件符码 字 建保串符 立编存 及 哈码权 夫解值 曼 码信 树 息 图1-3 功能模块图 《哈夫曼编码与译码》 第 5 页 共 34 页 2 设计思路与方案 2.1 设计思路 C语言是结构化和模块化的语言，它是面向过程的。在处理较小规模的程序时，程序员用C语言还比较得心应手。 C++是由C语言发展而来的，与C语言兼容。用C语言编写的程序基本上可以不加修改地用于C++。从C++的名字可以看出它是C的超集。C++既可以用于面向过程的结构化程序设计，又可用于面向对象的程序设计，是一种功能强大的混合型的程序设计语言。 C++对C的“增强”，表现在两个方面: 1)在原来面向过程的机制基础上，对C语言的功能做了不少扩充。 ( (2)增加了面向对象的机制。 作为一种编程约定，C++程序员倾向于只有当所有的成员均为公共时才使用结构。结构(struct)是一种特殊的类，它的特殊之处在于其成员都是公共的(除非另作声明)。C++程序员只有在所有成员都是公共的时候才会使用结构。 在计算机中进行编码的方法有很多种，此文选择哈弗曼编码。哈弗曼编码由哈弗曼树得到，所以我们要选择存储树的数据结构，为了高效的产生哈弗曼编码，树的存储采用三叉链表的方式，同时增加一个选项以存储各个树结点的权值。同时将得到的密文存储到文件中，以便我们进行查看。 2.2 设计方案 通过 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 可知，本课程设计主要功能是通过哈弗曼树得到哈弗曼编码，利用得到的哈弗曼编码对字符串进行编码与译码，并存入文件便于查看。由于构造哈弗曼树和根据哈弗曼树得到编码时要经常对节点的父结点，左右子树结点进行访问，所以采用三叉链表的方式存储树结点，同时在该结点信息中还需要增加一个选项存储结点的权值。其次，为了解决得到的哈弗曼编码的存储问题，再建立一个结构体，用于存储每个字符所对应编码及编码长度，编码的存储简化了编码与译码的操作。同时，将得到的密文存储到文 《哈夫曼编码与译码》 第 6 页 共 34 页 件中，便于我们查看。 定义一个结构体HTNode将树结点，父结点，左右子树结点及该结点的权值联系在 一起，便于操作。具体定义如下: 建立树结点 typedef struct // { int weight; int parent,lchild,rchild; }HTNode; 定义一个结构体CodeNode将各个字符对应编码及编码的长度联系在一起，便于操 作。具体定义如下: typedef struct //建立每个编码的结构体 { char ch; char bits[10]; int len; }CodeNode; 同时，为了操作的方便，我们做如下处理: typedef HTNode HafumanTree[m+1]; //重命名HTNode typedef CodeNode HafumanCode[n+1]; //重命名CodeNode 《哈夫曼编码与译码》 第 7 页 共 34 页 3 详细设计 3.1 menu菜单功能 Menu菜单主要用于让用户选择何种方式构造哈弗曼树，此时需要用户输入0或者1来进行控制。该段代码位于viod main()函数中。其代码如下: printf(" -------------------------------------------------------------------------- \n"); printf(" 欢迎使用编码译码系统\n"); printf(" -------------------------------------------------------------------------- \n"); printf("请输入获得权值的方法,输入1表示自己输入每个节点的权值,输入0表示将每个字符在输入字符串中出现的次数作为其权值:"); scanf("%d",&method); //通过用户的输入来判断使用何种方式 其流程图如图3-1所示: 开始 第一种方式编码 第二种方式编码 输入错误 图3-1 menu菜单 《哈夫曼编码与译码》 第 8 页 共 34 页 3.2 int counttotal(char *s,int quan[],char str[])函数 当用户选择通过输入的字符串自动获取权值(统计出现的字符种数以及每种字符出 现的次数， 将该种字符出现的次数作为它的权值)时，main函数将会调用该函数计算各个节点的权值，将相应的字符存入str[]字符数组，同时该字符对应的权值存入quan[] 数组中。算法流程图如图3-1: 开始 获得输入的字符串getstr[]， i=0。 判断getstr[i]是 i++; 否为26个小写 否 字母 是 k=getstr[i]-96;quantemp[k] ++( quantemp为int型数组 开始值都为0)i++; i=1,j=0 否 i<27? 是 结束 是 quantemp[i]=i++; 0? 否 j++;str[j]=i+96; quan[j]=quantemp[i]; 图3-1计算字符权值及字符种类算 说明:counttotal()函数代码见附录。 《哈夫曼编码与译码》 第 9 页 共 34 页 3.3 void selectmin()函数 该函数的作用是在所有给定权值的结点中选出权值最小的两个结点并返回，用于构造哈弗曼树。代码如下: void selectmin(HafumanTree HT,int k,int *s1,int*s2) //选择权值最小的两个 { int i,j; int min=9999; //声明一个int类型的数值min，赋个较大的输给它 for(i=1;i<=k;i++) //选择权值最小的一个节点(且该节点无父节点) { if((HT[i].weight0) //根据节点是其父节点的左右子来记录它的位置 { cd[--start]=(HT[p].lchild==c)?'0':'1'; c=p; //将父节点转为子节点 } strcpy(HC[i].bits,&cd[start]); //将得到的0、1字串存入结构体HC printf("%c:%s\n",HC[i].ch,HC[i].bits); HC[i].len=num-start; //求每个字符0、1编码长度 } } 《哈夫曼编码与译码》 第 13 页 共 34 页 3.6 void codenum( )函数 codenum()函数主要用于对输入字符串进行编码。根据Hafumanencode( )函数得到的编码，将字符串转化为密文，为了方便查看，最后会将得到的密文存入文件code.txt中。该函数由于要涉及到文件操作，故定义了文件流指针fp。该函数的算法流程图如图3-4所示: 《哈夫曼编码与译码》 第 14 页 共 34 页 开始 将str[i]的值依次赋给 HC[i].ch i=0;cd[num]='\0'; i<=num, 是 c=i start=num; 否 i++ 否 HT[c].parent strcpy(HC[i].bits, >0, &cd[start]); 是 HC[i].len=num-start; cd[--start]=(HT[p].lchild= =c)?'0':'1'; c= HT[c].parent; 打开code.txt文件,获得字符 串str指针，i=0; 否 i<=num, 是 结束否 否 HC[i].ch=*str? i++ 是 将HC[i].bits[j]存进文件 图3-4 编码算法 《哈夫曼编码与译码》 第 15 页 共 34 页 3.7 char *decode( )函数 decode()函数用于将已加密的密文进行译码翻译为原字符串。解码时从code.txt 文件夹中，一个一个字符的读出那串0、1代码赋给一个临时字符串cd[]，用该字符串与每个字符的HC[i].bins密文比较，直到与一个字符的密文相同时，译出该字符，将字符存放在临时字符数组tempstr[]中，清空临时字符串继续读取0、1代码进行翻译，直至文件密文结束为止。于是就得到了原先被加密的那串字符串。该函数的算法流程图如图3-5所示: 《哈夫曼编码与译码》 第 16 页 共 34 页 开始 打开文件夹code.txt, cjs=0, i=0 !feof(fp) 结束 (i 体会 针灸治疗溃疡性结肠炎昆山之路icu常用仪器的管理名人广告失败案例两会精神体会 到自身知识和能力能在实际中的应用和发挥。不但可以激发创新意识，还可以开发创造能力、培养沟通能力。这次数据结构课程设计的时间里虽然时间有限，但确实使我受益非浅。通过实践课程设计我丰富了编译工具操作经验，更加深了对C和C++语言的了解，熟悉了其环境，更增强了对哈夫曼树的理解与运用。 而且，在完成本课程设计的过程中，也充满磨练了我的意志，锻炼了我的耐心、认真。在实践的过程中，需要不倦的查阅资料，甚至需要求助于老师、同学。要善于思考，多动手。我深知，独立完成这样一项任务需要克服许多困难。 总之，数据结构课程设计让我受益良多，我会好好珍惜像这种难得的机会，努力学习知识。也感谢帮助了我的老师、同学。 《哈夫曼编码与译码》 第 24 页 共 34 页 参考文献 [1] 严蔚敏，吴伟民.数据结构(C语言版).清华大学出版社，2011.5 [2] 汪洁，数据结构经典算法实现与习题解答.人民邮电出版社，2004.1 [3] 谭浩强，C++程序设计(第一版).北京:清华大学出版社，2010.6 [4] 谭浩强，C程序设计(第三版).北京:清华大学出版社，2005.7 附 录 :源程序 // 程序名称:哈夫曼编码与译码 // 程序作者: // 最后修改日期:2012-6-27 #include #include #include using namespace std; #define n 100 //叶节点的个数小等于n #define m 2*n-1 //总结点的个数为m=2*n-1 int num; //定义一个全局变量用于存放字符种类个数 typedef struct //结构体用于存放树节点包括节点的父节点、左子、右子以及权值 { int weight; int parent,lchild,rchild; }HTNode; typedef HTNode HafumanTree[m+1]; //重命名HTNode HT typedef struct //结构体由于存放每个字符的密文和长度 { char ch; char bits[10]; int len; }CodeNode; typedef CodeNode HafumanCode[n+1]; //重命名CodeNode HC int main(int argc, char* argv[]) { int quan[27],k=1,length,count=1,total,method; //声明一个数组用以存放26字符的权 值,length表示要加密字符串的长度 //count用于控制输入字符和权值的次数 ,total 用于循环控制,k用于控制解密，加密的次数 //method用于控制使用何种方法进行输入权值 char getstr[300],str[27]; //声明两个字符串数组一个用于存输入,一个由于存放 输入中含有的字符 char *s; //声明一个char型指针用于指向字符HafumanTree HT; HafumanCode HC; //声明m+1个树节点 HafumanTree HT; //声明n+1个code int counttotal(char *s,int quan[],char str[]); //声明需要调用的函数 void creathafumantree(HafumanTree HT,HafumanCode HC,int quan[],char str[]); void Hafumanencode(HafumanTree HT,HafumanCode HC); void codenum(HafumanCode HC,char *str); char *decode(HafumanCode HC); while(k) { printf(" --------------------------------------------------------------------- \n"); printf(" 欢迎使用编码译码系统\n"); printf(" --------------------------------------------------------------------- \n"); printf("请输入获得权值的方法,输入1表示自己输入每个节点的权值,输 入0表示将每个字符在输入字符串中出现的次数作为其权值:"); scanf("%d",&method); if(method==0) { printf("请输入要编码的字符串(请输入小写字母):"); gets(getstr); // scanf("%s",&getstr); //获得输入的字符串 num=counttotal(getstr,quan,str); //统计字符串中含有字符种类个数 creathafumantree(HT,HC,quan,str); //根据字符权值构建哈夫曼树 Hafumanencode(HT,HC); //根据哈夫曼树确定每个字符的code codenum(HC,getstr); //将字符串译码存入文件夹 s=decode(HC); //将暗文解码 printf("解密为:\n"); printf("%s\n",s); printf("是否想继续编码、解码,是输入1回车,否输入0回车:"); scanf("%d",&k); } else if(method==1) { total=1; //每次都要将其清零，以达到控制循环的效果 printf("请输入要编码字符所出现的种类数:"); scanf("%d",&length); for(count=1;count<=length;count++) { printf("请输入第%d个字符和该字符的权值(中间留一个空格):",count); cin>>str[total]>>quan[total]; total++; } num=length; creathafumantree(HT,HC,quan,str); //根据字符权值构建哈夫曼树 Hafumanencode(HT,HC); //根据哈夫曼树确定每个字符的code printf("请输入要编码的字符串:"); cin>>getstr; codenum(HC,getstr); //将字符串译码存入文件夹 s=decode(HC); //将暗文解码 printf("解密为:\n"); printf("%s\n",s); ,否输入0回车:\n"); printf("是否想继续编码、解码,是输入1回车 scanf("%d",&k); } else { printf("错误输入!\n"); exit(0); } } system("pause"); return 0; } int counttotal(char *s,int quan[],char str[]) //计算字符串中字符权值 { char *p; int i,j,k,quantemp[27]; for(i=1;i<27;i++) //将所有字符的权值赋成0 quantemp[i]=0; for(p=s;*p!='\0';p++) //判断字符串是否结束 if(*p>='a'&&*p<='z') //判断字符是否为26字母 { k=*p-96; //看是26个字符中的哪个字符 quantemp[k]++; //字符权值加1 } j=0; for(i=1,j=0;i<27;i++) { if(quantemp[i]!=0) { j++; //用于统计字符种类个数 str[j]=i+96; //str按字母表顺序存储出现过的字符 quan[j]=quantemp[i]; } } return j; //返回该数据给num赋值 } void selectmin(HafumanTree HT,int k,int *s1,int*s2) //选择权值最小的两个 { int i,j; int min=9999; //声明一个int类型的数值min，赋个较大的输给它 for(i=1;i<=k;i++) //选择权值最小的一个节点(且该节点无父节点) { if((HT[i].weight0) //根据节点是其父节点的左右子来记录它的位置 { cd[--start]=(HT[p].lchild==c)?'0':'1'; c=p; //将父节点转为子节点 } strcpy(HC[i].bits,&cd[start]); //将得到的0、1字串存入结构体HC printf("%c:%s\n",HC[i].ch,HC[i].bits); HC[i].len=num-start; //求每个字符0、1编码长度 } } //根据哈夫曼树确定每个字符的0、1代码code void codenum(HafumanCode HC,char *str) { int i,j; FILE *fp; //声明一个文件夹指针 fp=fopen("code.txt","w"); //打开文件夹codefile printf("密文为:\n"); while(*str) //字符串未结束时 { for(i=1;i<=num;i++) { if(HC[i].ch==*str) //判断字符是否在Codenode中存在 { for(j=0;j