《数据结构课程设计-赫夫曼编码系统.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计-赫夫曼编码系统.doc（29页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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.字符解码96.实验结果106.1.实验结果说明106.2.程序运行截图117.设计体会128.参考文献139.附：程序代码131. 课程小组1.1. 小组成员
2、及分工2. 设计目的和要求通过课程设计，让学生进一步熟悉与巩固数据结构中常用算法，加深体会利用数据结构的算法解决实际问题的能力,培养学生进行复杂程序设计的技能，提高学生的思维能力、并促进其综合应用能力、分析能力和团队合作能力的提高。3. 需求分析随着网络信息科技的不断高速发展，网络上的问题也不断显露出来，特别是人们特别关注的安全隐私问题，所以文件的传输安全性要特别地亟待解决和提高。本次的课程设计以赫夫曼编码为题，设计出赫夫曼文件编码系统，旨在对文件中的内容进行分析、统计、处理，进而按照赫夫曼编码的理论，对文件进行简单加密。特别是，不同的文本文件有不同的字符处理形式，所以因此每一个文本都会有一个
3、相应的密钥，用于对文本的解码。4. 设计说明本次编写的程序按着对文件的编码（加密）和解码（解密）的两大步骤展开。4.1. 文件编码（加密）首先选择文件编码程序。进入程序后，会要求操作人员选择将要编码的文件，并将其导入到程序中，程序正确导入文件后将会对文件从开始至结束扫描一遍，对文件中的字符进行统计，在最后计算出每个字符出现的频率，并将频率换算成每个字符相应的权重。然后根据得到的字符权重，构造赫夫曼树并因此完成赫夫曼编码（至此，文件的导入分析过程已完成）。然后让操作人员选择对文件进行编码。此时，程序将会继续打开文件，继续扫描一遍，并在扫描的过程中将扫描到得字符根据刚才编好的赫夫曼编码进行对照，将
4、对应的赫夫曼编码写入另一个文件（即加密的文件），所以，如果用户代开加密的文件即看到里面全是二进制代码，并不能分析出里面究竟是什么内容。（至此，加密的文件应经生成）。最后，因为每个文件中的内容不同，所以每个文件的赫夫曼编码也不同，而赫夫曼编码是根据字符的权重生成的，所以每个文件都对应一个字符权重系列（即密钥），如果失去这个密钥，即使对文件进行了加密，也不同解密文件的内容，即文件加密失效，所以在生成加密文件后，一定要导出文件的字符权重（即密钥），以待之后的解码使用。（至此，文件的加密工作应经全部完成）。4.2. 文件解码（解密）文件的解码程序是一步完成的，即要求操作者首先将之前生成的字符权重（即密
5、钥）导入程序，程序根据获取到得字符权重，调用赫夫曼编码子程序，进行赫夫曼编码。然后程序会提示操作者将加密后的文件导入程序中，程序会根据在程序中获取到的二进制编码与赫夫曼编码进行对照识别，显示出对应的字符，因此，文件的解密工作完成。5. 详细设计5.1. 程序主体结构程序主体结构分为文件编码与文件解码两个子程序。文件编码后分别导出编码后文件与文件密钥。文件解码需导入编码文件与文件密钥，然后显示文本内容。5.2. 主要算法说明5.2.1. Huffman树/HuffmanTree list: list为赫夫曼树.typedef struct char data; /存放字符数据 int weigh
6、t; /存放字符权重int parent, lchild, rchild; /分别为根、左子树、右子树HuffmanTree;/Static info: info为存放字符权重的数组指针. typedef structchar data; /存放字符数据int weight; /存放字符权重Static;/int codeSize: codeSize为字符种类个数.void CreatHuffmanTree(HuffmanTree *&list, Static *info, int codeSize)int i, j, limit; int lnode, rnode; int value1,
7、value2;HuffmanTree *ptr;limit = codeSize * 2 - 1;/limit为赫夫曼树结点个数if (list = (HuffmanTree *)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 =
8、0;ptr-weight = 0;ptr-parent = ptr-lchild = ptr-rchild = -1;/*开始建立赫夫曼树*/ for(i=codeSize; ilimit; +i) value1 = 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 i
9、f (listj.weight value2) value2 = listj.weight;rnode = j;/此部分函数功能为选择出的结点建立关系 listlnode.parent = i;listrnode.parent = i; listi.weight = listlnode.weight + listrnode.weight; listi.lchild = lnode;listi.rchild = rnode;5.2.2. Huffman编码void CreatHuffmanCode(HuffmanTree *list, HuffmanCode &code, int codeSiz
10、e)int i, start;int flag1, flag2; char *tempCode;if (code = (char *)malloc(sizeof(char *) * codeSize) = NULL)printf( 内存不足, 操作失败!n);exit(0);if (tempCode = (char *)malloc(sizeof(char) * codeSize) = NULL)printf( 内存不足, 操作失败!n);exit(0);tempCodecodeSize-1 = 0;/*从叶子结点到根结点逆向求编码*/for(i=0; idata = ch;ptr-numbe
11、r = 1;ptr-next = characterList.next;characterList.next = ptr;+typeNumber;elsewhile (current != NULL) & (current-data != ch)previous = current;current = current-next;if (current != NULL)+(current-number);+characterNumber;elseif (ptr = (Data *)malloc(sizeof(Data) = NULL)printf( 内存不足, 操作失败!n);exit(0);p
12、tr-data = ch;ptr-number = 1;ptr-next = current;previous-next = ptr;+typeNumber;+characterNumber;fclose(fp);codeSize = typeNumber;info = (Static *)malloc(sizeof(Static) * codeSize);current = characterList.next;/将统计好的字符权重信息存入权重文件中for (int i=0; idata;infoi.weight = (int)(current-number * 100.0 / charac
13、terNumber);current = current-next;5.2.4. 字符解码/此代码用于比较查找赫夫曼编码bool CompareData(char *tempCode, int &position)for (position = 0; position codeSize; +position)if (strcmp(tempCode, codeposition) = 0)return true;return false;void DisplayContext()InportCharacterWeight();CreatHuffmanTree(list, info, codeSiz
14、e);CreatHuffmanCode(list, code, codeSize);InportFileCoding();FILE *fp;int position;int end;char *tempCode;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)
15、tempCodeend = ch;+end;tempCodeend = 0;if (CompareData(tempCode, position)printf(%c, infoposition.data);end = 0;printf(nn 按任意键结束!);getch();6. 实验结果6.1. 实验结果说明经过多次对本程序的实验，此次编译完成的程序可以对简单的文本文件进行加密和解密，因为限于对文件的基本操作不是太完全清楚，只是匆匆查阅了一些关于C语言文件操作部分的资料，所以这也是文件操作方面的一个瑕疵。所以综上，次此的程序只能进行简单的加密与解密操作。6.2. 程序运行截图（图1：赫夫曼加
16、密程序主体窗口）（图2：赫夫曼文件编码程序窗口）（图3：用于测试的文本 原始文本内内容）（图4：导出文件编码后，在创建的编码文件中生成的二进制数）（图5：导出的文本密钥（即字符权重）（图6：赫夫曼文件译码程序窗口）（图7：将之前生成的编码文件与密钥导入进来后显示出原来的文本内容）7. 设计体会进过此次的实验，让我对树结构及最优二叉树概念与操作的理解。在此次选择赫夫曼编码操作的时候，本打算用赫夫曼编码的程序对文件进行压缩存储，可是限于不知道怎样将生成的赫夫曼编码进行bit级别的存储（只知道进行Byte级别的存储），所以压缩存储的想法失败了，之后根据赫夫曼编码的结构及生成的文件，不得不让我想到了文
17、件的加密与解密，于是按着这个思路来设计了本文件加密解密系统。在设计的时候，曾准备根据网上之前对26个英文字符的使用统计来事先对字符权重进行分配（这样加密的文件可解密性增加了），而且考虑到文件中不仅有26个英文字母，如果对各种字符的使用频率进行统计，这个事先工作的负担会很重，所以之后编写了自动统计文本字符的频率程序，这样工作量会减小很多（而且文件的可解密性大大减小，但是也带来了记录密钥的不方便）。总体感觉程序还行，就是代码的简洁性还是有点差，条理还是不那么清晰。8. 参考文献1严蔚敏、吴伟明.数据结构.清华大学出版社.1997.42Thomas H.Cormen、Charles E.Leiser
18、son .算法导论.机械工业出版社.2006.99. 附：程序代码#include#include#include#include/赫夫曼树结构typedef 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* Hu
19、ffmanCode;/创建赫夫曼树void CreatHuffmanTree(HuffmanTree *&list, Static *info, int codeSize);/创建赫夫曼代码void CreatHuffmanCode(HuffmanTree *list, HuffmanCode &code, int codeSize);/从文件中读取数据并计算各字符出现频率void DataCount(Static *&info);/文件编码程序void FileEncoding();/创建文件编码void CreatFileCoding();/导出编码后文件void ExportFileEn
20、coding(HuffmanTree *list, HuffmanCode code, int codeSize);/导出文件中字符权重void ExportCharacterWeight();/文件译码程序void FileDecoding();/导入编码后的文件void InportFileCoding();/导入文件中字符权重void InportCharacterWeight();/显示译码后的文件内容void DisplayContext();bool CompareData(char *tempCode, int &position);void Bound(char charact
21、er, int size);/赫夫曼树HuffmanTree *list;/赫夫曼代码HuffmanCode code;/字符权重信息Static *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(st
22、din);choice = getchar();switch (choice)case 1:FileEncoding();break;case 2: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
23、 value1, value2;HuffmanTree *ptr;limit = codeSize * 2 - 1;if (list = (HuffmanTree *)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-p
24、arent = ptr-lchild = ptr-rchild = -1; for(i=codeSize; ilimit; +i) value1 = 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 =
25、j; listlnode.parent = i;listrnode.parent = i; listi.weight = listlnode.weight + 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 *)
26、* codeSize) = NULL)printf( 内存不足, 操作失败!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) & (cur
27、rent-data != ch)previous = 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);
28、codeSize = typeNumber;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;void FileEncoding()char choice;while (true)system(CLS);printf( 文件编码程序n);Bound(-, 25);printf(
29、 1. 创 建 文 件 编 码 n);printf( 2. 导 出 文 件 编 码 n);printf( 3. 导 出 文 件 密 钥 n);printf( 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 CreatFileCoding()DataCount(info);CreatHuffmanT