课程设计赫夫曼编码系统设计

1、数据结构数据结构课程设计报告课程设计报告课程名称课程名称 ：赫夫曼编码系统姓姓 名名 ： 学学 号号 ： 专专 业业 ： 班班 级级 ： 指导教师指导教师 ： 二二一二年一二年 十二月十二月目录目录 contents1.课程小组课程小组 -21.1.小组成员及分工-22.设计目的和要求设计目的和要求-23.需求分析需求分析 -24.设计说明设计说明 -24.1.文件编码（加密） -24.2.文件解码（解密） -35.详细设计详细设计 -35.1.程序主体结构-35.2.主要算法说明-35.2.1.huffman树-35.2.2.huffman编码-55.2.3.字符权重计算-65.2.4.字符

2、解码-96.实验结果实验结果-106.1.实验结果说明 -106.2.程序运行截图 -117.设计体会设计体会-128.参考文献参考文献-139.附：程序代码附：程序代码 -131. 课程小组课程小组1.1.小组成员及分工小组成员及分工2. 设计目的和要求设计目的和要求通过课程设计，让学生进一步熟悉与巩固数据结构中常用算法，加深体会利用数据结构的算法解决实际问题的能力,培养学生进行复杂程序设计的技能，提高学生的思维能力、并促进其综合应用能力、分析能力和团队合作能力的提高。3. 需求分析需求分析随着网络信息科技的不断高速发展，网络上的问题也不断显露出来，特别是人们特别关注的安全隐私问题，所以文件

3、的传输安全性要特别地亟待解决和提高。本次的课程设计以赫夫曼编码为题，设计出赫夫曼文件编码系统，旨在对文件中的内容进行分析、统计、处理，进而按照赫夫曼编码的理论，对文件进行简单加密。特别是，不同的文本文件有不同的字符处理形式，所以因此每一个文本都会有一个相应的密钥，用于对文本的解码。4. 设计说明设计说明本次编写的程序按着对文件的编码（加密）和解码（解密）的两大步骤展开。4.1.文件编码（加密）文件编码（加密）首先选择文件编码程序。进入程序后，会要求操作人员选择将要编码的文件，并将其导入到程序中，程序正确导入文件后将会对文件从开始至结束扫描一遍，对文件中的字符进行统计，在最后计算出每个字符出现的

4、频率，并将频率换算成每个字符相应的权重。然后根据得到的字符权重，构造赫夫曼树并因此完成赫夫曼编码（至此，文件的导入分析过程已完成） 。然后让操作人员选择对文件进行编码。此时，程序将会继续打开文件，继续扫描一遍，并在扫描的过程中将扫描到得字符根据刚才编好的赫夫曼编码进行对照，将对应的赫夫曼编码写入另一个文件（即加密的文件） ，所以，如果用户代开加密的文件即看到里面全是二进制代码，并不能分析出里面究竟是什么内容。 （至此，加密的文件应经生成） 。最后，因为每个文件中的内容不同，所以每个文件的赫夫曼编码也不同，而赫夫曼编码是根据字符的权重生成的，所以每个文件都对应一个字符权重系列（即密钥） ，如果失

5、去这个密钥，即使对文件进行了加密，也不同解密文件的内容，即文件加密失效，所以在生成加密文件后，一定要导出文件的字符权重（即密钥） ，以待之后的解码使用。 （至此，文件的加密工作应经全部完成） 。4.2.文件解码（解密）文件解码（解密）文件的解码程序是一步完成的，即要求操作者首先将之前生成的字符权重（即密钥）导入程序，程序根据获取到得字符权重，调用赫夫曼编码子程序，进行赫夫曼编码。然后程序会提示操作者将加密后的文件导入程序中，程序会根据在程序中获取到的二进制编码与赫夫曼编码进行对照识别，显示出对应的字符，因此，文件的解密工作完成。5. 详细设计详细设计5.1.程序主体结构程序主体结构程序主体结构

6、分为文件编码与文件解码两个子程序。文件编码后分别导出编码后文件与文件密钥。文件解码需导入编码文件与文件密钥，然后显示文本内容。5.2.主要算法说明主要算法说明5.2.1.huffman 树树/huffmantree list: list 为赫夫曼树.typedef struct char data; /存放字符数据 int weight; /存放字符权重int parent, lchild, rchild; /分别为根、左子树、右子树huffmantree;/static info: info 为存放字符权重的数组指针. typedef structchar data; /存放字符数据int

7、weight; /存放字符权重static;/int codesize: codesize 为字符种类个数.void creathuffmantree(huffmantree *&list, static *info, int codesize)int i, j, limit; int lnode, rnode; int value1, value2;huffmantree *ptr;limit = codesize * 2 - 1;/limit 为赫夫曼树结点个数if (list = (huffmantree *)malloc(sizeof(huffmantree) * limit) = n

8、ull)printf( 内存不足, 操作失败!n);exit(0);/*初始化赫夫曼树各结点信息*/ for(i=0, ptr=list; idata = infoi.data;ptr-weight = infoi.weight;ptr-parent = ptr-lchild = ptr-rchild = -1;for(; idata = 0;ptr-weight = 0;ptr-parent = ptr-lchild = ptr-rchild = -1;/*开始建立赫夫曼树*/ for(i=codesize; ilimit; +i) value1 = value2 = 32767; lnod

9、e = rnode = -1;/此部分函数功能为选择权值最小的两个结点 for(j=0; ji; +j) if (listj.parent = -1) if (listj.weight value1) value2 = value1;rnode = lnode; value1 = listj.weight;lnode = j; else if (listj.weight value2) value2 = listj.weight;rnode = j;/此部分函数功能为选择出的结点建立关系 listlnode.parent = i;listrnode.parent = i; listi.weig

10、ht = listlnode.weight + listrnode.weight; listi.lchild = lnode;listi.rchild = rnode;5.2.2.huffman 编码编码void creathuffmancode(huffmantree *list, huffmancode &code, int codesize)int i, start;int flag1, flag2; char *tempcode;if (code = (char *)malloc(sizeof(char *) * codesize) = null)printf( 内存不足, 操作失败!

11、n);exit(0);if (tempcode = (char *)malloc(sizeof(char) * codesize) = null)printf( 内存不足, 操作失败!n);exit(0);tempcodecodesize-1 = 0;/*从叶子结点到根结点逆向求编码*/for(i=0; idata = ch;ptr-number = 1;ptr-next = characterlist.next;characterlist.next = ptr;+typenumber;elsewhile (current != null) & (current-data != ch)prev

12、ious = current;current = current-next;if (current != null)+(current-number);+characternumber;elseif (ptr = (data *)malloc(sizeof(data) = null)printf( 内存不足, 操作失败!n);exit(0);ptr-data = ch;ptr-number = 1;ptr-next = current;previous-next = ptr;+typenumber;+characternumber;fclose(fp);codesize = typenumbe

13、r;info = (static *)malloc(sizeof(static) * codesize);current = characterlist.next;/将统计好的字符权重信息存入权重文件中for (int i=0; idata;infoi.weight = (int)(current-number * 100.0 / characternumber);current = current-next;5.2.4.字符解码字符解码/此代码用于比较查找赫夫曼编码bool comparedata(char *tempcode, int &position)for (position = 0

14、; position codesize; +position)if (strcmp(tempcode, codeposition) = 0)return true;return false;void displaycontext()inportcharacterweight();creathuffmantree(list, info, codesize);creathuffmancode(list, code, codesize);inportfilecoding();file *fp;int position;int end;char *tempcode;char ch;fp = fopen

15、(filename, rb);if (tempcode = (char *)malloc(sizeof(char) * codesize) = null)printf( 内存不足, 操作失败!n);exit(0);end = 0;/*此部分为解码过程*/printf(n 文件内容为:nn );while (ch = fgetc(fp) != eof)tempcodeend = ch;+end;tempcodeend = 0;if (comparedata(tempcode, position)printf(%c, infoposition.data);end = 0;printf(nn 按任意

16、键结束!);getch();6. 实验结果实验结果6.1.实验结果说明实验结果说明经过多次对本程序的实验，此次编译完成的程序可以对简单的文本文件进行加密和解密，因为限于对文件的基本操作不是太完全清楚，只是匆匆查阅了一些关于 c 语言文件操作部分的资料，所以这也是文件操作方面的一个瑕疵。所以综上，次此的程序只能进行简单的加密与解密操作。6.2.程序运行截图程序运行截图（图 1：赫夫曼加密程序主体窗口）（图 2：赫夫曼文件编码程序窗口）（图 3：用于测试的文本 原始文本内内容）（图 4：导出文件编码后，在创建的编码文件中生成的二进制数）（图 5：导出的文本密钥（即字符权重） ）（图 6：赫夫曼文件

17、译码程序窗口）（图 7：将之前生成的编码文件与密钥导入进来后显示出原来的文本内容）7. 设计体会设计体会进过此次的实验，让我对树结构及最优二叉树概念与操作的理解。在此次选择赫夫曼编码操作的时候，本打算用赫夫曼编码的程序对文件进行压缩存储，可是限于不知道怎样将生成的赫夫曼编码进行 bit 级别的存储（只知道进行 byte 级别的存储） ，所以压缩存储的想法失败了，之后根据赫夫曼编码的结构及生成的文件，不得不让我想到了文件的加密与解密，于是按着这个思路来设计了本文件加密解密系统。在设计的时候，曾准备根据网上之前对 26 个英文字符的使用统计来事先对字符权重进行分配（这样加密的文件可解密性增加了）

18、，而且考虑到文件中不仅有 26 个英文字母，如果对各种字符的使用频率进行统计，这个事先工作的负担会很重，所以之后编写了自动统计文本字符的频率程序，这样工作量会减小很多（而且文件的可解密性大大减小，但是也带来了记录密钥的不方便） 。总体感觉程序还行，就是代码的简洁性还是有点差，条理还是不那么清晰。8. 参考文献参考文献1严蔚敏、吴伟明.数据结构.清华大学出版社.1997.42thomas h.cormen、charles e.leiserson .算法导论.机械工业出版社.2006.99. 附：程序代码附：程序代码#include#include#include#include/赫夫曼树结构ty

19、pedef struct char data; int weight; int parent, lchild, rchild;huffmantree; /字符权重结构typedef structchar data;int weight;static;/统计字符时所用到的链表结构typedef struct nodechar data;int number;struct node *next;data;/赫夫曼代码结构typedef char* huffmancode;/创建赫夫曼树void creathuffmantree(huffmantree *&list, static *info, i

20、nt codesize);/创建赫夫曼代码void creathuffmancode(huffmantree *list, huffmancode &code, int codesize);/从文件中读取数据并计算各字符出现频率void datacount(static *&info);/文件编码程序void fileencoding();/创建文件编码void creatfilecoding();/导出编码后文件void exportfileencoding(huffmantree *list, huffmancode code, int codesize);/导出文件中字符权重void e

21、xportcharacterweight();/文件译码程序void filedecoding();/导入编码后的文件void inportfilecoding();/导入文件中字符权重void inportcharacterweight();/显示译码后的文件内容void displaycontext();bool comparedata(char *tempcode, int &position);void bound(char character, int size);/赫夫曼树huffmantree *list;/赫夫曼代码huffmancode code;/字符权重信息static

22、*info;/字符种数int codesize;/文件名char filename30;int main()char choice;while (true)system(cls);printf( 赫夫曼编码加密程序n);bound(-, 25);printf( 1. 文 件 编 码 n);printf( 2. 文 件 译 码 n);printf( 0. 退 出 程 序 n);bound(-, 25);printf( 请选择: );fflush(stdin);choice = getchar();switch (choice)case 1:fileencoding();break;case 2:

23、filedecoding();break;case 0:printf(n);system(pause);return 0;break;default:printf(n 您的输入有误, 按任意键后请从新输入!);getch();break;void creathuffmantree(huffmantree *&list, static *info, int codesize)int i, j, limit; int lnode, rnode; int value1, value2;huffmantree *ptr;limit = codesize * 2 - 1;if (list = (huff

24、mantree *)malloc(sizeof(huffmantree) * limit) = null)printf( 内存不足, 操作失败!n);exit(0); for(i=0, ptr=list; idata = infoi.data;ptr-weight = infoi.weight;ptr-parent = ptr-lchild = ptr-rchild = -1;for(; idata = 0;ptr-weight = 0;ptr-parent = ptr-lchild = ptr-rchild = -1; for(i=codesize; ilimit; +i) value1 =

25、 value2 = 32767; lnode = rnode = -1; for(j=0; ji; +j) if (listj.parent = -1) if (listj.weight value1) value2 = value1;rnode = lnode; value1 = listj.weight;lnode = j; else if (listj.weight value2) value2 = listj.weight;rnode = j; listlnode.parent = i;listrnode.parent = i; listi.weight = listlnode.wei

26、ght + listrnode.weight; listi.lchild = lnode;listi.rchild = rnode;void creathuffmancode(huffmantree *list, huffmancode &code, int codesize)int i, start;int flag1, flag2; char *tempcode;if (code = (char *)malloc(sizeof(char *) * codesize) = null)printf( 内存不足, 操作失败!n);exit(0);if (tempcode = (char *)ma

27、lloc(sizeof(char) * codesize) = null)printf( 内存不足, 操作失败!n);exit(0);tempcodecodesize-1 = 0;for(i=0; idata = ch;ptr-number = 1;ptr-next = characterlist.next;characterlist.next = ptr;+typenumber;elsewhile (current != null) & (current-data != ch)previous = current;current = current-next;if (current != n

28、ull)+(current-number);+characternumber;elseif (ptr = (data *)malloc(sizeof(data) = null)printf( 内存不足, 操作失败!n);exit(0);ptr-data = ch;ptr-number = 1;ptr-next = current;previous-next = ptr;+typenumber;+characternumber;fclose(fp);codesize = typenumber;info = (static *)malloc(sizeof(static) * codesize);c

29、urrent = characterlist.next;for (int i=0; idata;infoi.weight = (int)(current-number * 100.0 / characternumber);current = current-next;void fileencoding()char choice;while (true)system(cls);printf( 文件编码程序n);bound(-, 25);printf( 1. 创 建 文 件 编 码 n);printf( 2. 导 出 文 件 编 码 n);printf( 3. 导 出 文 件 密 钥 n);pri

30、ntf( 0. 返 回 主 菜 单 n);bound(-, 25);printf( 请选择: );fflush(stdin);choice = getchar();switch (choice)case 1:creatfilecoding();break;case 2:exportfileencoding(list, code, codesize);break;case 3:exportcharacterweight();break;case 0:return;default:printf(n 您的输入有误, 按任意键后请从新输入!);getch();break;void creatfilec

31、oding()datacount(info);creathuffmantree(list, info, codesize);creathuffmancode(list, code, codesize);printf(n 创建文件编码成功! 按任意键继续!);getch();void exportfileencoding(huffmantree *list, huffmancode code, int codesize)int i;char ch;char outfilename30;file *infile, *outfile;system(cls);infile = fopen(filena

32、me, rb);printf(n 请创建导出文件名: );fflush(stdin);gets(outfilename);if (outfile = fopen(outfilename, wb) = null)printf( 输出文件创建失败!n);exit(0);while (ch = fgetc(infile) != eof)for(i=0; icodesize; +i)if (listi.data = ch)fputs(codei, outfile);break;fcloseall();printf(n 导出文件成功! 按任意键继续!);getch();void exportcharac

33、terweight()char outfilename30;file *fp;system(cls);printf(n 请创建导出文件名: );fflush(stdin);gets(outfilename);if (fp = fopen(outfilename, wb) = null)printf( 输出文件创建失败!n);exit(0);for(int i=0; idata = data;ptr-number = weight;ptr-next = characterlist.next;characterlist.next = ptr;+characternumber;fclose(fp);

34、codesize = characternumber;if (info = (static *)malloc(sizeof(static) * codesize) = null)printf( 内存不足, 操作失败!n);exit(0);ptr = characterlist.next;for (int i=codesize-1; i=0; -i)infoi.data = ptr-data;infoi.weight = ptr-number;ptr = ptr-next;printf(n 文件导入成功! 下一步.n);bool comparedata(char *tempcode, int &

35、position)for (position = 0; position codesize; +position)if (strcmp(tempcode, codeposition) = 0)return true;return false;void displaycontext()inportcharacterweight();creathuffmantree(list, info, codesize);creathuffmancode(list, code, codesize);inportfilecoding();file *fp;int position;int end;char *t

36、empcode;char ch;fp = fopen(filename, rb);if (tempcode = (char *)malloc(sizeof(char) * codesize) = null)printf( 内存不足, 操作失败!n);exit(0);end = 0;printf(n 文件内容为:nn );while (ch = fgetc(fp) != eof)tempcodeend = ch;+end;tempcodeend = 0;if (comparedata(tempcode, position)printf(%c, infoposition.data);end = 0

37、;printf(nn 按任意键结束!);getch();void bound(char character, int size)while (size-)putchar(character);putchar(n);employment tribunals sort out disagreements between employers and employees.you may need to make a claim to an employment tribunal if:you dont agree with the disciplinary action your employer h

38、as taken against youyour employer dismisses you and you think that you have been dismissed unfairly.for more information about dismissal and unfair dismissal, see dismissal.you can make a claim to an employment tribunal, even if you havent appealed against the disciplinary action your employer has t

39、aken against you. however, if you win your case, the tribunal may reduce any compensation awarded to you as a result of your failure to appeal.remember that in most cases you must make an application to an employment tribunal within three months of the date when the event you are complaining about h

40、appened. if your application is received after this time limit, the tribunal will not usually accept it.if you are worried about how the time limits apply to you, take advice from one of the organisations listed under further help.employment tribunals are less formal than some other courts, but it i

41、s still a legal process and you will need to give evidence under an oath or affirmation.most people find making a claim to an employment tribunal challenging. if you are thinking about making a claim to an employment tribunal, you should get help straight away from one of the organisations listed un

42、der further help.if you are being represented by a solicitor at the tribunal, they may ask you to sign an agreement where you pay their fee out of your compensation if you win the case. this is known as a damages-based agreement. in england and wales, your solicitor cant charge you more than 35% of

43、your compensation if you win the case.if you are thinking about signing up for a damages-based agreement, you should make sure youre clear about the terms of the agreement. it might be best to get advice from an experienced adviser, for example, at a citizens advice bureau. to find your nearest cab,

44、 including those that give advice by e-mail, click on nearest cab.for more information about making a claim to an employment tribunal, see employment tribunals.the (lack of) air up there watch mcayman islands-based webb, the head of fifas anti-racism taskforce, is in london for the football associat

45、ions 150th anniversary celebrations and will attend citys premier league match at chelsea on sunday.i am going to be at the match tomorrow and i have asked to meet yaya toure, he told bbc sport.for me its about how he felt and i would like to speak to him first to find out what his experience was.ue

46、fa has opened disciplinary proceedings against cska for the racist behaviour of their fans during citys 2-1 win.michel platini, president of european footballs governing body, has also ordered an immediate investigation into the referees actions.cska said they were surprised and disappointed by tour

47、es complaint. in a statement the russian side added: we found no racist insults from fans of cska.age has reached the end of the beginning of a word. may be guilty in his seems to passing a lot of different life became the appearance of the same day; may be back in the past, to oneself the paranoid

48、weird belief disillusionment, these days, my mind has been very messy, in my mind constantly. always feel oneself should go to do something, or write something. twenty years of life trajectory deeply shallow, suddenly feel something, do it.一字开头的年龄已经到了尾声。或许是愧疚于自己似乎把转瞬即逝的很多个不同的日子过成了同一天的样子；或许是追溯过去，对自己那

49、些近乎偏执的怪异信念的醒悟，这些天以来，思绪一直很凌乱，在脑海中不断纠缠。总觉得自己自己似乎应该去做点什么，或者写点什么。二十年的人生轨迹深深浅浅，突然就感觉到有些事情，非做不可了。the end of our life, and can meet many things really do?而穷尽我们的一生，又能遇到多少事情是真正地非做不可？during my childhood, think lucky money and new clothes are necessary for new year, but as the advance of the age, will be more

50、and more found that those things are optional; junior high school, thought to have a crush on just means that the real growth, but over the past three years later, his writing of alumni in peace, suddenly found that isnt really grow up, it seems is not so important; then in high school, think dont w

51、ant to give vent to out your inner voice can be in the high school children of the feelings in a period, but was eventually infarction when graduation party in the throat, later again stood on the pitch he has sweat profusely, looked at his thrown a basketball hoops, suddenly found himself has alrea

52、dy cant remember his appearance.童年时，觉得压岁钱和新衣服是过年必备，但是随着年龄的推进，会越来越发现，那些东西根本就可有可无；初中时，以为要有一场暗恋才意味着真正的成长，但三年过去后，自己心平气和的写同学录的时候，突然就发现是不是真正的成长了，好像并没有那么重要了；然后到了高中，觉得非要吐露出自己的心声才能为高中生涯里的懵懂情愫划上一个句点，但毕业晚会的时候最终还是被梗塞在了咽喉，后来再次站在他曾经挥汗如雨的球场，看着他投过篮球的球框时，突然间发现自己已经想不起他的容颜。originally, this world, can produce a chemica

53、l reaction to an event, in addition to resolutely, have to do, and time.原来，这个世界上，对某个事件能产生化学反应的，除了非做不可的坚决，还有，时间。a persons time, your ideas are always special to clear. want, want, line is clear, as if nothing could shake his. also once seemed to be determined to do something, but more often is he bac

54、ked out at last. dislike his cowardice, finally found that there are a lot of love, there are a lot of miss, like shadow really have been doomed. those who do, just green years oneself give oneself an arm injection, or is a self-righteous spiritual.一个人的时候，自己的想法总是特别地清晰。想要的，不想要的，界限明确，好像没有什么可以撼动自己。也曾经好

55、像已经下定了决心去做某件事，但更多的时候是最后又打起了退堂鼓。嫌恶过自己的怯懦，最终却发现有很多缘分，有很多错过，好像冥冥之中真的已经注定。那些曾经所谓的非做不可，只是青葱年华里自己给自己注射的一支强心剂，或者说，是自以为是的精神寄托罢了。at the moment, the sky is dark, the air is fresh factor after just rained. suddenly thought of blue plaid shirt; those were broken into various shapes of stationery; from the corne

56、r at the beginning of deep friendship; have declared the end of the encounter that havent start planning. those years, those days of do, finally, like youth, will end in our life.此刻，天空是阴暗的，空气里有着刚下过雨之后的清新因子。突然想到那件蓝格子衬衫；那些被折成各种各样形状的信纸；那段从街角深巷伊始的友谊；还有那场还没有开始就宣告了终结的邂逅计划那些年那些天的非做不可，终于和青春一样，都将在我们的人生中谢幕。baumgartner the disappointing news: mission aborted. r plays an important role in this mission. starting at the ground, conditions have to be very calm - winds less than 2 mph, with no precipitation or humidity and limited cloud cover. the balloon, with capsule atta