一个哈夫曼的实习题,大家帮一下忙,小女子感激不尽
为了方便起见我们将压缩程序命名为huff,解压缩程序命名为unhuff。
1) I:初始化:从给定的一个文件中读入全部字符,统计出现了哪些字符以及各字符的个数(即字符出现的频度),将每个字符出现的频度作为该字符的权值,构建哈夫曼树,并将它存入文件hfmTree中。
2) E:压缩(编码):利用已经建好的哈夫曼树对给定的文件进行编码,然后将结果存入文件名为<目标文件名>_hf的文件中。
3) D:解压缩(解码):利用已经建好的哈夫曼树对压缩文件中的内容进行解压缩并将结果输出到文件名为<目标文件名>_uhf的文件中。
4) 将2个程序做成一个系统,给出一个菜单界面,菜单项包括I,E,D,Q。其中I,E,D为基本要求中的3个功能(步骤),Q为Quit(退出程序)。
【实现提示】
1) 为每个字符生成一个节点,节点的权值就是对应字符出现的次数,将生成的节点插入按权值升序排列的链表中(这个链表初始时为空)。链表建成之后,从中选出最小的2个(即链表的头2个)节点,将它们作为一个新节点的孩子节点,新节点的权值为2个孩子节点的权值之和,并把新节点按其权值大小插入到链表中。不断重复此过程直到链表中仅有一个节点,则该节点为哈夫曼树的根节点。这里也可以考虑用基于堆(排序)的思想来依次找权值最小的2个节点,不过堆排序每次只能输出1个权值最小的节点,输出该节点后(即将该节点从堆中删除),以及由2个节点作为孩子节点生成了新节点后(要将该节点插入堆中),堆的结构需要重构。