霍夫曼编译器课设

沈阳航空航天大学

课 程 设 计 报 告

课程设计名称：数据结构课程设计 课程设计题目：霍夫曼编/译码器

院（系）： 专 业： 班 级： 学 号： 姓 名： 指导教师：

沈阳航空航天大学课程设计报告

目 录

1 需求分析 .................................................................................................................... 1 1.1 问题描述 ................................................................................................................ 1 1.2 问题理解 ................................................................................................................ 1 2 系统设计 .................................................................................................................... 2 2.1 总体方案设计 ........................................................................................................ 2 2.2 数据结构设计 ........................................................................................................ 2 2.3 函数设计 ................................................................................................................ 3 2.4 关键流程 ................................................................................................................ 4 2.4.1 系统主流程 ..................................................................................................... 4 2.4.3 创建霍夫曼树函数流程函数 ......................................................................... 7 2.4.4 霍夫曼树建立霍夫曼表的函数流程 ............................................................. 8 3 调试分析 .................................................................................................................. 10 4 测试及运行结果 ....................................................................................................... 11 参考文献 ........................................................................................................................ 13 附 录 .......................................................................................................................... 14

I

沈阳航空航天大学课程设计报告

1 需求分析

1.1 问题描述

设计一个利用霍夫曼算法的编码与译码系统，可以接收来自键盘输入的字符集大小、字符和权值信息，创建霍夫曼树生成霍夫曼编码并能对其进行译码的系统。

1.2 问题理解

首先，建立的霍夫曼编码与译码器并能够接受字符集大小、字符和权值信息，因此用字符数组存储字符串，把相同字符出现的次数作为每个字符的权值，用数组存储，建立一个链表，依次存储字符串中的字符，建立霍夫曼树，选取两个权值最小的字符组合，依次构成霍夫曼树，以左孩子码为0，右孩子为1，对霍夫曼树中的节点进行编码以及译码的应用。

1

沈阳航空航天大学课程设计报告 错误！未指定书

签。

2 系统设计

2.1 总体方案设计

打开存放字符或编码的文件，将文件中的字符串存入字符串数组里，查找字符串中字符的个数和每个字符出现的次数，创建霍夫曼树，将各个字符出现的次数作为权值，存入霍夫曼链表的前n个单元中，将后n-1个节点赋权值，建树，从每个叶子节点开始，利用霍夫曼树对每个字符进行编码，最终建立一个霍夫曼表，利用霍夫曼编码表对整个字符串进行编码，对霍夫曼编码进行解码，放入字符串s中。

2.2 数据结构设计

本程序的数据结构设计用了霍夫曼树的节点结构体，编码结构体其结构体如下：

typedef struct node { int weight;

struct node *LChild,*RChild,*Parent; struct node *next; } HFMNode,*HFMTree;

typedef struct {

char ch; char code[N+1]; int start;

}CodeNode;

2