数据结构与算法期末作业-哈夫曼算法压缩和解压ASCII文件
需积分: 0 24 浏览量
2023-05-12
21:44:22
上传
评论 1
收藏 664KB PDF 举报
1. 需求分析
本程序主要是利用哈夫曼算法实现一个能对 ASCII 字符文件进行压缩和还原的程序。
用户可以修改 main 函数中 buildTree 函数里的字符串，程序会根据所输入的字符串形成一棵哈夫
曼树。然后，用户可以在 encode 中输入字符，通过刚才形成的哈夫曼树形成哈夫曼编码；用户也可以
在 decode 函数中输入二进制字符，程序将通过所建立的哈夫曼树解码，打印出字符串。
注意：所输入的解码字符不得出现在创建哈夫曼树时没有出现的字符，否则解码失败，将不出现解
码结果。如果待解码的二进制数有 0 和 1 之外的数字，则会报错，输出“The input string is not coded
correctly!”的字样。
2. 概要设计
2.1 主程序流程
先创建一个哈夫曼树；再创建一个 codeTable 用来存放各个字符的编码；然后 encode 打印编码，decode
解码。
2.2 抽象数据类型的定义
pQueue 为队列的头指针；pQueueNode 为队列中的结点；htNode 是树的结点；htTree 是一个根结点;hlNode
为存放编码和字符的结点；hlTable 为存放编码的链表。
2.3 各程序模块之间的层次关系
main 函数使用了 buildTree 函数、buildTable 函数、encode 函数和 decode 函数；buildTree 函数又调
用了 initPQueue 函数、addPQueue 函数和 getPQueue 函数；buildTable 函数则调用了 traverseTree 函
数。
3. 详细设计
3.1 数据类型定义
3.1.1 数据类型定义的伪代码
typedef struct _htNode{
ElemType symbol;
struct _htNode *left,*right;
}htNode;
typedef struct _htTree{
htNode *root;
}htTree;
typedef struct _pQueueNode{
htNode * val;
ElemType priority;
struct _pQueueNode *next;
}pQueueNode;
//定义一个队列
资源评论
