logo设计在线生成免费网站,wordpress文件目录结构,南阳东莞网站建设公司哪家好,南京网站定制南京一、摘要 在计算机技术突飞猛进的今天#xff0c;加密程序的开发越来越受到开发者的青睐。本次数据结构课程设计选择文件加密系统#xff0c;系统主要使用了哈夫曼编码技术#xff0c;开发了一个对英文文本文件进行加密和解密的程序。在技术上对哈弗曼编码中的最优二叉树进…一、摘要在计算机技术突飞猛进的今天加密程序的开发越来越受到开发者的青睐。本次数据结构课程设计选择文件加密系统系统主要使用了哈夫曼编码技术开发了一个对英文文本文件进行加密和解密的程序。在技术上对哈弗曼编码中的最优二叉树进行改进由二叉树变为三叉树森林减少了编码文件的空间并且在编码过程中我们采用动态分配叶子的方法一旦密码本中的字符计数出现增加或者减少或者说密码本中字符的顺序发生改变生成的 012 串也会相应的做出改变而不会把每一个字符的编码给写死。同时支持用户自定义选择密码本以及加密解密文件。二、课程设计内容2.1 设计目的目前大多数用户常用的对文件进行加密的方法就是密码保护, 而这种加密方法简单适用, 但它同时也留下了巨大的安全隐患。对于一些破译高手而言, 往往很容易攻破这种密码保护。要想让非法用户很难破译甚至是几乎不可能破译, 他才会望而却步, 而这样做的惟一方法就是使密码尽可能复杂同时对用户而言又满足某种规律。由于计算机文件中的字符具有统计特性, 能够统计出每种字符在文件中出现的概率。当文件中所有字符的概率统计出来后, 就可以用多元哈夫曼编码的方法给文件生成对应的哈夫曼编码表, 然后用这个哈夫曼编码表对文件进行加密。由于这个哈夫曼编码表足够复杂同时又满足编码的规律, 非法用户想要破解密文几乎是不可能的。[1]因为在上学期已经实现了二叉树的基本结构以及基本算法所以本次实际应用我们选择该课题再次深入了解树或者森林的魅力。本次课程设计的目标回顾《数据结构》中线性表以及二叉树的基本知识加深对数据结构理解。掌握 C 编程方法以及程序调试的基本技能。尝试对数据结构进行创新以及改进改变其空间复杂度以及时间复杂度。2.2 完成功能对密码本进行字符的统计以及计算其权值存储在线性表中。梁沃辉对二叉树结构修改为三叉树结构森林并利用 1 中的线性表建立三叉树结构形成 012 串与文件中字符进行比对生成文件编码 Code.txt。林凯对需要解密的文件以及密码本进行比对解密并形成解密文件 decode.txt甘倩茵前端界面以及选择功能。甘倩茵2.3 设计要求以某文件为样本进行哈夫曼编码或其它编码输入待加密文件进行加密输入待解密文件解密2.4 功能要求能够对一个文件其中的字符进行统计统计其出现的字母中文个数。能够对一个文件进行加密并输出加密文件以及其密码本能够将加密生成的文件还原成源文件三、系统分析3.1 系统结构图系统结构图3.2 函数结构图函数结构图四、详细设计算法设计功能描述和核心算法设计与实现4.1 HuffmanTreeLib.h 文件三叉树结构主要实现层4.1.1 void init(huffmanhuffmanTree,intw,char *z,int n)//构建三叉树算法 void init(huffman *huffmanTree,int *w,char *z,int n) { int i; //(3n-1)/2) n为奇数时计算结点个数 if(n%2 1) { for(i0;i(3*n-1)/2;i) { huffmanTree[i].chz[i]; huffmanTree[i].weightw[i]; huffmanTree[i].parent-1; huffmanTree[i].lChild-1; huffmanTree[i].mChild-1; huffmanTree[i].rChild-1; } } //3n/2 n为偶数时计算结点个数 else { for(i0;i(3*n)/2;i) { huffmanTree[i].chz[i]; huffmanTree[i].weightw[i]; huffmanTree[i].parent-1; huffmanTree[i].lChild-1; huffmanTree[i].mChild-1; huffmanTree[i].rChild-1; } } }因为本次课程设计我们使用的是三叉树所以与二叉树在结构上有根本性不同主要体现在结点数为奇数和偶数时的树结构不同当叶子结点为偶数时设权值 weight2、4、5、8、9、10、12、13、18、20、24、25、30、32构成最优三叉树的结构如图 1 所示。设叶子结点个数为 n度为 1 的结点个数为 m度为 2 的结点为 p根节点度为 3 的结点个数为 q。即npmqeq2pm1三叉树的结点数等于这个树的度 1得n2q1其中 m0p1∴ 总结点个数 Nnmpq3n/2当叶子结点个数为 14 时总的叶子结点个数是 21 个∴ 当叶子结点个数为 n 时最优三叉树的结点总数为 3n/2图 1当叶子结点数为奇数时(设权值 weight2、4、5、8、9、10、12、13、14、18、20、24、25、30、32构成最优三叉树的结构如图 2 所示设叶子结点个数为 n度为 2 的结点为 p根节点度为 1 的结点个数为 m度为 3 的结点个数为 q。即 npmq3q2pm1一颗三叉树的结点数这棵树的度加 1得n2q1其中 m0,p0总结点个数 Nnmpq(3n-1)/2当叶子结点个数为 15 时总的叶子结点个数是 22 个正确所以当叶子结点个数为 n 时最优三叉树的结点总数是(3n-1)/2这个函数的主要功能是新建空结点并将孩子结点和双亲结点置为-1。图二4.1.2 void setHuffmanTree(huffman *huffmanTree,int n) 构建最优三叉树//构建最优三叉树 void setHuffmanTree(huffman *huffmanTree,int n) { int m,m1,m2,m3,x1,x2,x3,i,j; if(n%2 1) { m(3*n-1)/2; } else m3*n/2; for(in;im;i) { //定义m1m2m3,的值为1000作为比较大小交换的载体 m1m2m3MaxValue; //初始化x1x2x3 x1x2x30; //比较最小权值然后相加 for(j0;ji;j) { //交换过程 if(huffmanTree[j].parent-1huffmanTree[j].weightm1) { m2m1; x2x1; m1huffmanTree[j].weight; x1j; } else if (huffmanTree[j].parent-1huffmanTree[j].weightm2) { m2huffmanTree[j].weight; x2j; } else if (huffmanTree[j].parent-1huffmanTree[j].weightm3) { m3huffmanTree[j].weight; x3j; } } //偶数个节点时生成双亲节点 if(n%2 1) { huffmanTree[x1].parenti; huffmanTree[x2].parenti; huffmanTree[x3].parenti; huffmanTree[i].lChildx1; huffmanTree[i].mChildx2; huffmanTree[i].rChildx3; huffmanTree[i].weightm1m2m3; } //奇数节点时生成双亲节点 else { huffmanTree[x1].parenti; huffmanTree[x2].parenti; huffmanTree[x3].parenti; huffmanTree[i].lChildx1; huffmanTree[i].mChildx2; huffmanTree[i].rChildx3; if(n!m-1) { //计算双亲节点权值方便用于循环中进行构建三叉树 huffmanTree[i].weightm1m2m3; } else huffmanTree[i].weightm1m2; } } }最优三叉树奇数如图三所示偶数同理4.1.3 字符编码函数 void huffmanTreeCode(huffman *huffmanTree,int n)void huffmanTreeCode(huffman *huffmanTree,int n) { //定义数组存储树节点的字符 char hc[Max]; //叶子节点的012编码长度 int hcLen; int i,j,k,parent,p; //先生成叶子节点对应的012编码然后存储到叶子节点中 for(i0;in;i) { hcLen0; //待编码字符的双亲结点下标 parenthuffmanTree[i].parent; pi; while(parent!-1)//未到达根结点 { if(huffmanTree[parent].lChildp)//是左孩子 hc[hcLen]0,hcLen; else if(huffmanTree[parent].mChildp)//是中孩子 hc[hcLen]1,hcLen; else if(huffmanTree[parent].rChildp)//是右孩子 hc[hcLen]2,hcLen; pparent; parenthuffmanTree[parent].parent;//继续向根结点查找 } //将编码写入相应字符数组 for(j0,khcLen-1;jhcLen;j,k--) huffmanTree[i].hCode[j]hc[k]; huffmanTree[i].hCode[j]\0;//加上字符串结束符 } return; }根据哈夫曼编码规则将 012 赋予每个字符图如图一所示。4.1.4 HuffmanTreeLib ADThuffmanTree存放字符 ch;存放权值 weight;存放左子树 lChild;存放中子数 mChild;存放右子树 rChild;存放该结点的父亲节点 parent;存放该结点的 012 串 hCode[Max];Operation init前置条件三叉树不存在功能三叉树的初始化后置条件构造一个空的三叉树输入无输出无调用规则无编写者林凯最后修改时间2020 年 11 月 10 日setHuffmanTree前置条件三叉树存在功能最优三叉树的构建后置条件交换结点使得形成最优三叉树输入无输出无调用规则无编写者林凯最后修改时间2020 年 11 月 10 日huffmanTreeCode前置条件最优三叉树存在功能三叉树编码后置条件形成三叉树编码并用链表存储输入无输出无调用规则无编写者林凯最后修改时间2020 年 11 月 10 日Encode前置条件有 Source.txt 字符文件功能用流方式使得文件内字符形成编码后置条件关闭输入输出流输入Source.txt输出Code.txt调用规则无编写者林凯最后修改时间2020 年 11 月 29 日decode前置条件有 Code.txt 012 编码文件功能使得密码解码后置条件关闭输入输出流输入Code.txt输出Code2.txt调用规则无编写者甘倩茵最后修改时间2020 年 11 月 29 日4.2 Count.h密码本字符计数功能4.2.1 链表线性表结构函数 LNodetypedef struct LNode { char key; int number; LNode *next; }*Link;由于本次线性表结构主要用来统计出现的字符以及其出现的次数所以线性表采用链表结构链表结构如图四所示。图四4.2.2 初始化链表函数 CreatNodeLink CreateNode(void) { //初始化链表节点 Link newnode (LNode*)malloc(sizeof(LNode)); if(newnode!NULL) { newnode-number0; newnode-nextNULL; } return newnode; }把 number 初始化为-14.2.3 计数函数 Number()int *Number() { char c; bool flag; int i 0; static int W[Max]; Link headNULL;//头指针 Link currenthead;//当前结点 ifstream in_stream;//源文件 in_streamnoskipws; ofstream out_stream;//输出文件 in_stream.open(Source.txt); //打开源文件错误 if(in_stream.fail()) { coutinserting to the file is failing; exit(1); } out_stream.open(Output.txt); //打开输出文件错误 if(out_stream.fail()) { coutinserting to the file is failing; exit(1); } //遍历文件依次读取每个字符 while(in_streamc) { flagtrue;//标志c不存在于链表中 //遍历链表判断c是否已经存在于链表中 for(currenthead;current!NULL;currentcurrent-next) { //c已经存在c对应的频数加1 if(current-keyc) { current-number; flagfalse;//flag置为false break;//跳出for循环 } } if(flag) { //c不存在创建新结点 Link newnodeCreateNode(); newnode-keyc; newnode-number; newnode-nexthead; headnewnode; } //w[i]current-number; //z[i]current-key; //i; } //coutThe result:endl;//控制台输出 //输出至输出文件 out_stream字母\t频数endl; //遍历链表分别输出至控制台和文件中 for(currenthead;current!NULL;currentcurrent-next) { //coutcurrent-key current-number\n; out_streamcurrent-key\tcurrent-numberendl; W[i]current-number; i; } return W; //关闭流 in_stream.close(); out_stream.close(); //释放链表空间 for(currenthead;current!NULL;currentcurrent-next) delete current; }① 计数函数是将文件中的字符通过文件流 ofstream 以及 ifstream 的方式从磁盘流入内存中或者从内存流入磁盘中。② 由于文件流默认会不读取空格以及回车符等空白符所以在文件输入流的时候进行一个操作即 in_streamnoskipws; 设置 in_stream 读取空白符。③ 函数读取字符的过程中也会检索链表中的其他元素查看是否有重复元素如果有则会在 number 上 1。、④ 文件流需要在使用后关闭否则会造成读操作的内存溢出问题以及写操作的缓存转移至硬盘内。4.2.4 Count.h ADTLNode存放字符 key;存放权值 number;Operation CreateNode前置条件没有形成链表功能初始化链表并将 number 赋 0后置条件无输入无输出无调用规则无编写者梁沃辉最后修改时间2020 年 11 月 10 日Number前置条件 无功能给 Source.txt 文件内出现的字符计数并输出至链表以及文件 Output.txt 中后置条件关闭输入输出流输入用户输入输出Output.txt调用规则无编写者梁沃辉最后修改时间2020 年 11 月 10 日五、运行与测试5.1 用户界面5.2 选择密码本用户自定义密码本密码本选择不同时其中 Select.txt 有所有的英文字符24000 多个中文字符以及所有标点符号涵盖了所有常用字符。当然用户也可以自定义其中的密码本只要双方约定使用一个密码本即可双方都加密以及解密成功。只要输入密码本之后也就进入了三叉树中进行字符编码其中编码后字符存在程序的链表中提供加密以及解密依据。5.3 文件加密需在选择密码本后进行根据用户输入的文件名进行加密下面是两个示例1.txt中信息输入 1.txt 进行加密加密后的文件存储在根目录下的 Code.txt 中选择另一密码本Select1.txt并进行另一个文件加密密码本 Select1.txt选择 Source.txt 进行加密Source.txt 内容加密后文件同样存在 Code.txt5.4 文件解密需在选择密码本后进行对 Code1.txt 进行解密Code1.txt 中内容为加密中 ① 的内容我将其复制到 Code1.txt 中作区分选择密码本选择与加密相同的密码本 Select.txtCode1.txt 解密解密后文件放在 deCode.txt 中与加密中 ① 的 1.txt 相同说明解密成功对 Code.txt 进行解密其中 Code.txt 中的文件是加密中 ② 的密文选择密码本 Select1.txt选择 Code.txt 进行解密解密结果同样放在 deCode.txt 中与加密中的 ②Sorce.txt 相同说明解密成功六、总结6.1 系统优点本系统中由于使用了三叉树相较于二叉树更优的是三叉树在编码的时候可以更加节省空间不单单是节省 012 串的空间更加的是节省了开辟树的内存空间这样一来即使文件内字符太多也不会因为树的结点太多导致爆内存或者是打不开程序。使用了三叉树的创新可以使得我们更好的了解树结构的形成以及其原理即使变成更多分支的树的结构也可以按照原理一步一步形成更多分支的树结构。程序中允许用户自行选择密码本而且对于密码本中的字符进行动态分配即密码本有一个字符发生改变加密后所有密文都会发生改变。6.2 系统缺点由于中文字符进入程序中需要两个字符而我们的程序是单字符进入所以中文字符所需要的空间大大增加。比对的过程是顺序查找在解密的过程中如果密码本的字符过多导致字符编码过长时会可以使用折半查找或者把 012 串编码再次进行编码的方法减少查找时间。6.3 设计体会本次数据结构课程设计中我再次复习了数据结构中的二叉树结构前驱后继根叶子线性表结构链表结构并且通过对二叉树的了解进行创新使得这次课程设计所使用的由二叉树改变为三叉树森林结构。因为这次在组内担任的是组长这也是第一次参与到这样的软件分工协调工作还是很多东西需要注意的首先第一点是工作的分配问题所以在选好课题的时候的第二天我已经给队友准备好了这次课程设计的分工合作我负责文件读取并获得字符以及其权值林凯负责使用字符及其权值并进行编码工作甘倩茵负责前端的设计以及解码工作如下图这是我第一次写的程序流程图其中有许多不成熟的地方以及两个不同数据结构之间的传参问题这些都是我第一次作为组长没有想到的东西所以这是我还需要解决并且提高的地方。第二我说一下我们小组的想法问题在一开始选题的时候我们的想法非常的多首先我们想到的不是稳稳的做完一个编码我们想到的是做一个图片的编码因为我们想到每一个像素其实都是由RGB三种不同颜色组成而这个数据我们也可以进行编码对不同位置的像素RGB值进行编码得到这个像素的颜色值但是一个问题是如果使用cmd命令行进行的话并不能做到彩色所以我们又想到了二维码的编码问题我们知道现在的二维码都带着非常多的应用信息或者说是网站信息我们可以使用01串代表更多的信息然后0代表一个单位的黑像素1代表一个单位的白像素然后用这样的黑白像素代表一个网站的全部信息并可以超链接过去但是想一想这好像又有点脱离题目。所以这次实验我们从算法入手改变二叉树结构为三叉树这样不仅能更深入的了解哈夫曼树的结构更加加深我们对其他进制编码的了解以及理解。11.30更新部分通过答辩与老师沟通之后我发现了我在开始设计的时候就已经存在了的问题在设计的时候我是想着发送的时候像计算机网络一样发送密码本会随着密文一起发送到对方之后解密会利用密码本进行比对再解码成正常的文章但是我忽略了一点如果密码本012串跟着发送的话别人一比对就能解密所以我这个加密做的是没有效果的。一开始答辩的时候我还懵着其实就是一开始就是错的设计思路。但是好在我们的功能都是逐个逐个功能去写就不需要去重写功能只需要将我们的功能函数顺序进行对调先密码本编码再对明文进行加密。有了这一次的教训之后我会更加懂得设计理念的重要性一定要理解好题目的要求再进行功能设计很感激在大学期间有一次这样的经历。最后这次课程设计让我懂得了团队协作的魅力自己作为一个组长需要跟队员进行沟通以及交流还有在一些时候需要跟队友有舍有得不要盲目执着。这次课程设计也让我更多的了解到了数据结构的线性表以及哈夫曼树的结构了解了编码解码的过程。七、参考文献[1] 王防修 多元哈夫曼编码在加密技术中的应用[J] 武汉工业学院 2009-03-01[2] 数据结构实验指导手册2017版.pdf♻️ 资源大小3.40MB➡️资源下载https://download.csdn.net/download/s1t16/87415704注更多内容可关注微信公众号【神仙别闹】如当前文章或代码侵犯了您的权益请私信作者删除