数据结构课程设计-赫夫曼编码系统.doc

数据结构数据结构课程设计报告课程设计报告 课程名称课程名称 ：赫夫曼编码系统 姓姓 名名 ： 学学 号号 ： 专专 业业 ： 班班 级级 ： 指导教师指导教师 ： 二二一二年一二年 十二月十二月 1 / 29 目录目录 contents 1.课程小组课程小组 -2 1.1.小组成员及分工-2 2.设计目的和要求设计目的和要求-2 3.需求分析需求分析 -2 4.设计说明设计说明 -2 4.1.文件编码（加密） -2 4.2.文件解码（解密） -3 5.详细设计详细设计 -3 5.1.程序主体结构-3 5.2.主要算法说明-3 5.2.1.huffman树-3 5.2.2.huffman编码-5 5.2.3.字符权重计算-6 5.2.4.字符解码-9 6.实验结果实验结果-10 6.1.实验结果说明 -10 6.2.程序运行截图 -11 7.设计体会设计体会-12 8.参考文献参考文献-13 9.附：程序代码附：程序代码 -13 2 / 29 1. 课程小组课程小组 1.1.小组成员及分工小组成员及分工 2. 设计目的和要求设计目的和要求 通过课程设计，让学生进一步熟悉与巩固数据结构中常用算法，加深体会利用数据结 构的算法解决实际问题的能力,培养学生进行复杂程序设计的技能，提高学生的思维能力、 并促进其综合应用能力、分析能力和团队合作能力的提高。 3. 需求分析需求分析 随着网络信息科技的不断高速发展，网络上的问题也不断显露出来，特别是人们特别 关注的安全隐私问题，所以文件的传输安全性要特别地亟待解决和提高。 本次的课程设计以赫夫曼编码为题，设计出赫夫曼文件编码系统，旨在对文件中的内 容进行分析、统计、处理，进而按照赫夫曼编码的理论，对文件进行简单加密。特别是， 不同的文本文件有不同的字符处理形式，所以因此每一个文本都会有一个相应的密钥，用 于对文本的解码。 4. 设计说明设计说明 本次编写的程序按着对文件的编码（加密）和解码（解密）的两大步骤展开。 4.1.文件编码（加密）文件编码（加密） 首先选择文件编码程序。进入程序后，会要求操作人员选择将要编码的文件，并将其 导入到程序中，程序正确导入文件后将会对文件从开始至结束扫描一遍，对文件中的字符 进行统计，在最后计算出每个字符出现的频率，并将频率换算成每个字符相应的权重。然 后根据得到的字符权重，构造赫夫曼树并因此完成赫夫曼编码（至此，文件的导入分析过 程已完成） 。 然后让操作人员选择对文件进行编码。此时，程序将会继续打开文件，继续扫描一遍， 并在扫描的过程中将扫描到得字符根据刚才编好的赫夫曼编码进行对照，将对应的赫夫曼 编码写入另一个文件（即加密的文件） ，所以，如果用户代开加密的文件即看到里面全是二 进制代码，并不能分析出里面究竟是什么内容。 （至此，加密的文件应经生成） 。 最后，因为每个文件中的内容不同，所以每个文件的赫夫曼编码也不同，而赫夫曼编 3 / 29 码是根据字符的权重生成的，所以每个文件都对应一个字符权重系列（即密钥） ，如果失去 这个密钥，即使对文件进行了加密，也不同解密文件的内容，即文件加密失效，所以在生 成加密文件后，一定要导出文件的字符权重（即密钥） ，以待之后的解码使用。 （至此，文 件的加密工作应经全部完成） 。 4.2.文件解码（解密）文件解码（解密） 文件的解码程序是一步完成的，即要求操作者首先将之前生成的字符权重（即密钥） 导入程序，程序根据获取到得字符权重，调用赫夫曼编码子程序，进行赫夫曼编码。然后 程序会提示操作者将加密后的文件导入程序中，程序会根据在程序中获取到的二进制编码 与赫夫曼编码进行对照识别，显示出对应的字符，因此，文件的解密工作完成。 5. 详细设计详细设计 5.1.程序主体结构程序主体结构 程序主体结构分为文件编码与文件解码两个子程序。 文件编码后分别导出编码后文件与文件密钥。 文件解码需导入编码文件与文件密钥，然后显示文本内容。 5.2.主要算法说明主要算法说明 5.2.1.huffman 树树 /huffmantree list: list 为赫夫曼树. typedef struct char data; /存放字符数据 int weight; /存放字符权重 int parent, lchild, rchild; /分别为根、左子树、右子树 huffmantree; /static info: info 为存放字符权重的数组指针. typedef struct char data; /存放字符数据 int weight; /存放字符权重 static; /int codesize: codesize 为字符种类个数. 4 / 29 void creathuffmantree(huffmantree * int lnode, rnode; int value1, 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 = 0; ptr-weight = 0; ptr-parent = ptr-lchild = ptr-rchild = -1; /*开始建立赫夫曼树*/ for(i=codesize; idata = ch; ptr-number = 1; ptr-next = characterlist.next; characterlist.next = ptr; +typenumber; else while (current != null) current = current-next; if (current != null) +(current-number); +characternumber; else if (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); 9 / 29 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 #include #include #include /赫夫曼树结构 typedef struct char data; int weight; int parent, lchild, rchild; huffmantree; /字符权重结构 typedef struct char data; int weight; static; /统计字符时所用到的链表结构 typedef struct node char data; int number; struct node *next; data; /赫夫曼代码结构 typedef char* huffmancode; 14 / 29 /创建赫夫曼树 void creathuffmantree(huffmantree * /创建赫夫曼代码 void creathuffmancode(huffmantree *list, huffmancode /从文件中读取数据并计算各字符出现频率 void datacount(static * /文件编码程序 void fileencoding(); /创建文件编码 void creatfilecoding(); /导出编码后文件 void exportfileencoding(huffmantree *list, huffmancode code, int codesize); /导出文件中字符权重 void exportcharacterweight(); /文件译码程序 void filedecoding(); /导入编码后的文件 void inportfilecoding(); /导入文件中字符权重 void inportcharacterweight(); /显示译码后的文件内容 void displaycontext(); bool comparedata(char *tempcode, int void bound(char character, int size); /赫夫曼树 huffmantree *list; /赫夫曼代码 huffmancode code; /字符权重信息 static *info; /字符种数 int codesize; /文件名 char filename30; int main() char choice; 15 / 29 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: filedecoding(); break; case 0: printf(“n“); system(“pause“); return 0; break; default: printf(“n 您的输入有误, 按任意键后请从新输入!“); getch(); break; void creathuffmantree(huffmantree * int lnode, rnode; int value1, value2; huffmantree *ptr; 16 / 29 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-parent = ptr-lchild = ptr-rchild = -1; for(i=codesize; idata = ch; ptr-number = 1; ptr-next = characterlist.next; characterlist.next = ptr; +typenumber; else while (current != null) current = current-next; if (current != null) +(current-number); +characternumber; else 20 / 29 if (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); 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(“ 1. 创 建 文 件 编 码 n“); printf(“ 2. 导 出 文 件 编 码 n“); 21 / 29 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); 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; 22 / 29 system(“cls“); infile = fopen(filename, “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; idata = data; ptr-number = weight; ptr-next = characterlist.next; characterlist.next = ptr; +characternumber; fclose(fp); 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 文件导入成功! 下一步