logo资料库

数据结构哈夫曼编码报告.doc

发布时间：2022-06-15 发布人：admin 分类：说明书 资料大小：0.35M 资料格式：doc 举报 版权申诉
第1页 / 共9页
第2页 / 共9页
第3页 / 共9页
第4页 / 共9页
第5页 / 共9页
第6页 / 共9页
第7页 / 共9页
第8页 / 共9页
资料共9页，剩余部分请下载后查看
    哈夫曼编码与解码 一、设计思想 首先规定构建哈夫曼树，再去进行哈夫曼的译码，接着设计函数进行字符 串的编码过程，最后进行哈夫曼编码的译码。 定义一个结构体，用于存放构建哈夫曼树所需要的所有变量，开辟一块地 址空间，用于存放数组，数组中每个元素为之前定义的结构体。输入 n 个字符 及其权值。 构建哈夫曼树：在上述存储结构上实现的哈夫曼算法可大致描述为： 1、初始化 。将 ht[0．．m-1]中 2n-1 个结点里的三个指针均置为空，权值 置为 0。 2、输入 。 读入 n 个叶子的权值存于向量的前 n 个分量中。它们是初始森 林中 n 个孤立的根结点上的权值。 3、合并 。对森林中的树共进行 n-1 次合并，所产生的新结点依次放入向量 ht 的第 i 个分量中。每次合并分两步： ①在当前森林 ht[0．．i-1]的所有结点中，选取权最小和次小的两个根结点[s1] 和 [s2]作为合并对象，这里 0≤s1，s2≤i-1。 ② 将根为 ht[s1]和 ht[s2]的两棵树作为左右子树合并为一棵新的树，新树的 根是新结点 ht[i]。具体操作： 将 ht[s1]和 ht[s2]的 parent 置为 i， 将 ht[i]的 lchild 和 rchild 分别置为 s1 和 s2 新结点 ht[i]的权值置为 ht[s1]和 ht[s2]的权值之和。 哈夫曼的编码：约定左子为 0，右子为 1，则可以从根结点到叶子结点的路 径上的字符组成的字符串作为该叶子结点的编码。 当用户输入字母时。就在已经找好编码的编码结构体中去查找该字母。查 到该字母就打印所存的哈夫曼编码。接着就是完成用户输入 0、1 代码时把代码 转成字母的功能。这是从树的头结点向下查找，如果当前用户输入的 0、1 串中 是 0 则就走向该结点的左子。如果是 1 这就走向该结点的右结点，重复上面步 骤。直到发现该结点属于输入了字母的结构体则打印该结构体的字母。重复上 面步骤。直到找完用户输入 0、1 串为止。则就完成了程序所有的译码过程。 二、算法流程图 (1)建立哈夫曼树的算法： 定义各结点类型其中应包含两类数据一是权重域 weight；一是应该包括指 向左右孩子和指向双亲的指针这里分别用 lchild、rchild 和 parent 来表示，因此 可用静态三叉链表来实现。在实际构造中由于是叶子结点来构造新的根结点其 构造过程中仅与叶子结点的权重有关而与其数据域无关，所以构造过程中不用 考虑其数值域，并且在链表中从叶子开始存放，然后不断的将两个最小权值的 子树合并为一个权值为其和的较大的子树，逐步生成各自内部结点直到树根。 图 1 构建哈夫曼树图 （2）编码的算法 将建立的哈夫曼树从每个叶子结点开始沿着双亲回到根结点，每走一步进 行编码得到的一个编码值，由于每个叶子结点的哈夫曼编码是从根结点到相应 的叶子的路径的各个分支的代码组成的 0 和 1 序列，所以先得到了低位编码后 得到高位编码因此可用一维数组从后向前来存放各位编码值，并用 start 来记 - 1 - 开始 输入字符 和权值 对结构体进行 初始化，
    录编码的起始位置。 哈夫曼编码与解码 开始 i=0 start=n i 结点的父结点 Y 根结点 N 子结点为左子 Y 编码为 0 N 编码为 1 start=start-1 把父结点作为当前结点 i
    哈夫曼编码与解码 开始 i=0 输入字符以回车结束 C=0 c<=n Sting[i]=ht[c].dat j=dc[c].start N j<=n C++ Y j++ 输出代码 结束 图 3 哈夫曼编码 四、哈夫曼译码 当我们输入哈夫曼 01 代码时进行译码过程，输出字符串。 - 3 -
    哈夫曼编码与解码 三、源代码 图 4 哈夫曼译码流程图 //数组头文件 //宏定义 //定义哈夫曼编码的结构数组 //定义权值 #include #include #include #define MAX 999 typedef struct{ char data; int weight; int parent; int lchild; int rchild; }huffmannode; typedef struct{ char bits[50]; int start; }huffmancode ; void main() { //定义保存哈夫曼结构体 //定义储存权值的空间 //定义数组存储空间 huffmannode ht[100]; huffmancode cd[100]; char string[100]; char hcd[100]; int i,j,x,y,s1,s2,m1,m2,n,c,f,k; - 4 -
    哈夫曼编码与解码 //输入字符的个数 printf("please input the n="); scanf("%d",&n); printf("\n===============================\n"); for(i=0;i
    哈夫曼编码与解码 //记录父结点 y=ht[x].parent; while (y!=-1) { if (ht[y].lchild==x) cd[i].bits[cd[i].start]='0'; //给字符赋 0 值 else cd[i].bits[cd[i].start]='1'; //给字符赋 1 值 cd[i].start--; x=y; y=ht[y].parent; } } printf("\nout the huffmancode:\n"); for (i=0;i
    哈夫曼编码与解码 if(f
    哈夫曼编码与解码 图 6 叶子结点编码图 第三步，得到 huffmancode 后我们输入字符进行哈夫曼编码，如图 4。 第五步，的到哈夫曼编码后输入哈夫曼编码进行译码过程。 图 7 字符的编码图 图 8 哈夫曼编码的译码图 五、遇到的问题及解决 - 8 -
    分享到：
    赞 收藏

    相关推荐

    资料库

    后端

    共收录2142份资料，累计10个分类，关注成员有19位，主要包括：Perl,Docker,Delphi,VB,PHP,Java,C,C#,Python,C++

    热门标签

    Perl Docker Delphi VB PHP Java C C# Python C++

    最新资料