数据结构前缀编码课程设计

《数据结构前缀编码课程设计》由会员分享，可在线阅读，更多相关《数据结构前缀编码课程设计（10页珍藏版）》请在毕设资料网上搜索。

1、 数数 据据 结结 构构 课程设计报告课程设计报告 题 目： 专 业： 班 级： 学 号： 姓 名： 指导老师： 时 间： 一、课程设计题目及所涉及知识点一、课程设计题目及所涉及知识点 设计题目是： “前缀编码问题” 。 所涉及的知识点主要是： 本课程设计利用二叉树来设计二进制的前缀编码，前缀编码顾名思义就是任意一字符的 编码都不是另一个字符的编码的前缀，主要难点在于如何根据输入的字符和使用频度构造出 最优二叉树，并根据构造的最优二叉树输出每个字符的编码，这主要设计到对每个字符的权 值进行冒泡排序找出最小的两个权值作为左右孩子结点，以他们的和作为父母结点，并把父 母结点作为新的权值数重新排序，

2、最终构造出完整的哈夫曼树，以根的左右路径分别代表值 “0”与“1”连续存储，得到每个字符的编码。 二、课程设计思路及算法描述二、课程设计思路及算法描述 设计思路：通过构造哈夫曼树的结构体定义一个哈夫曼树组，对用户输入的字符以及使 用频率进行存储和初始化，然后对字符进行编译处理，通过构造哈夫曼树编译出每个字符的 编码，然后对每个编码进行存储并与字符相关联，并输出每个字符以及对应的编码。最终根 据用户选择的功能进行编码和译码操作。 问题一：哈夫曼树的表示。问题一：哈夫曼树的表示。 设计哈夫曼树的结构体，其中包含使用频率（权重） 、左孩子、右孩子、双亲和要编码的 字符。用这个结构体定义个一个哈夫曼数

3、组。 哈夫曼结构体定义如下： typedef struct int weight; int lchild; int rchild; int parent; char key; htnode; typedef htnode hfmtMAXLEN; 问题二：对输入字符进行编码。问题二：对输入字符进行编码。 初始化哈夫曼树，每个节点的孩子及双亲默认值为-1，使用频率为 0。根据用户选择输 入字符个数 n，以及 n 个字符和 n 个权值，构造出哈夫曼树，并显示出每个字符及对应编码。 1.void creathfmt(hfmt t)/创建哈夫曼树的函数 2.void selectmin(hfmt t,i

4、nt i,int *p1,int *p2)/选出两个最小的字符权值 3.void phfmnode(hfmt t)/对字符进行初始编码 问题三：对用户输入的电文进行编码。问题三：对用户输入的电文进行编码。 用户输入一连串原本输入的字符构成电文，电文长度在 1000 字符以内，由程序进行编码 转换。并输出转换后的编码。 void encoding(hfmt t)/对用户输入的电文进行编码 char r1000;/用来存储输入的字符串 int i,j; printf(“n请输入需要编码的字符:“); gets(r); printf(“编码结果为:“); for(j=0;rj!=0;j+) for(i=0;in;i+) if(rj=ti.key) hfmtpath(t,i,j); prin