2 dtt 123 dtt_123 于 2017.01.04 10:55 提问

哈夫曼编码和译码,把相应的数据存入文件中 1C

手动输入权值并进行哈夫曼编码和译码,将这些数据写入文件中,并以直观的方式输出哈夫曼树用C语言实现

2个回答

qq_37241799
qq_37241799   2017.01.04 11:04

权值5 4 3 2 1第一步先取两个最小权值作为左右子树构造一个新树,即取1,2构成新树,其结点为1+2=3 虚线为新生成的结点,第二步再把新生成的权值为3的结点放到剩下的集合中,所以集合变成{5,4,3,3},再根据第二步,取最小的两个权值构成新树,

再依次建立哈夫曼树
各字符对应的编码为:A->11,B->10,C->00,D->011,E->010图片图片图片图片

qq_37241799
qq_37241799   2017.01.04 11:09

#include
#include

#define MAXBIT 100
#define MAXVALUE 10000
#define MAXLEAF 30
#define MAXNODE MAXLEAF*2 -1

typedef struct
{
int bit[MAXBIT];
int start;
} HCodeType; /* 编码结构体 /
typedef struct
{
int weight;
int parent;
int lchild;
int rchild;
int value;
} HNodeType; /
结点结构体 */

/* 构造一颗哈夫曼树 /
void HuffmanTree (HNodeType HuffNode[MAXNODE], int n)
{
/
i、j: 循环变量,m1、m2:构造哈夫曼树不同过程中两个最小权值结点的权值,
x1、x2:构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/
int i, j, m1, m2, x1, x2;
/* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 /
for (i=0; i<2*n-1; i++)
{
HuffNode[i].weight = 0;//权值
HuffNode[i].parent =-1;
HuffNode[i].lchild =-1;
HuffNode[i].rchild =-1;
HuffNode[i].value=i; //实际值,可根据情况替换为字母

} /
end for */

/* 输入 n 个叶子结点的权值 */
for (i=0; i<n; i++)
{
    printf ("Please input weight of leaf node %d: \n", i);
    scanf ("%d", &HuffNode[i].weight);
} /* end for */

/* 循环构造 Huffman 树 */
for (i=0; i<n-1; i++)
{
    m1=m2=MAXVALUE;     /* m1、m2中存放两个无父结点且结点权值最小的两个结点 */
    x1=x2=0;
    /* 找出所有结点中权值最小、无父结点的两个结点,并合并之为一颗二叉树 */
    for (j=0; j<n+i; j++)
    {
        if (HuffNode[j].weight < m1 && HuffNode[j].parent==-1)
        {
            m2=m1; 
            x2=x1; 
            m1=HuffNode[j].weight;
            x1=j;
        }
        else if (HuffNode[j].weight < m2 && HuffNode[j].parent==-1)
        {
            m2=HuffNode[j].weight;
            x2=j;
        }
    } /* end for */
        /* 设置找到的两个子结点 x1、x2 的父结点信息 */
    HuffNode[x1].parent  = n+i;
    HuffNode[x2].parent  = n+i;
    HuffNode[n+i].weight = HuffNode[x1].weight + HuffNode[x2].weight;
    HuffNode[n+i].lchild = x1;
    HuffNode[n+i].rchild = x2;

    printf ("x1.weight and x2.weight in round %d: %d, %d\n", i+1, HuffNode[x1].weight, HuffNode[x2].weight);  /* 用于测试 */
    printf ("\n");
} /* end for */

/* for(i=0;i<n+2;i++)
{
printf(" Parents:%d,lchild:%d,rchild:%d,value:%d,weight:%d\n",HuffNode[i].parent,HuffNode[i].lchild,HuffNode[i].rchild,HuffNode[i].value,HuffNode[i].weight);
}*///测试
} /* end HuffmanTree */

//解码
void decodeing(char string[],HNodeType Buf[],int Num)
{
int i,tmp=0,code[1024];
int m=2*Num-1;
char *nump;
char num[1024];
for(i=0;i<strlen(string);i++)
{
if(string[i]=='0')
num[i]=0;

else
num[i]=1;

}
i=0;
nump=&num[0];

while(nump<(&num[strlen(string)]))
{tmp=m-1;
while((Buf[tmp].lchild!=-1)&&(Buf[tmp].rchild!=-1))
{

if(*nump==0)
{
tmp=Buf[tmp].lchild ;

}
else tmp=Buf[tmp].rchild;
nump++;

}

printf("%d",Buf[tmp].value);

}

}

int main(void)
{

HNodeType HuffNode[MAXNODE];            /* 定义一个结点结构体数组 */
HCodeType HuffCode[MAXLEAF],  cd;       /* 定义一个编码结构体数组, 同时定义一个临时变量来存放求解编码时的信息 */
int i, j, c, p, n;
char pp[100];
printf ("Please input n:\n");
scanf ("%d", &n);
HuffmanTree (HuffNode, n);


for (i=0; i < n; i++)
{
    cd.start = n-1;
    c = i;
    p = HuffNode[c].parent;
    while (p != -1)   /* 父结点存在 */
    {
        if (HuffNode[p].lchild == c)
            cd.bit[cd.start] = 0;
        else
            cd.bit[cd.start] = 1;
        cd.start--;        /* 求编码的低一位 */
        c=p;                    
        p=HuffNode[c].parent;    /* 设置下一循环条件 */
    } /* end while */

    /* 保存求出的每个叶结点的哈夫曼编码和编码的起始位 */
    for (j=cd.start+1; j<n; j++)
    { HuffCode[i].bit[j] = cd.bit[j];}
    HuffCode[i].start = cd.start;
} /* end for */

/* 输出已保存好的所有存在编码的哈夫曼编码 */
for (i=0; i<n; i++)
{
    printf ("%d 's Huffman code is: ", i);
    for (j=HuffCode[i].start+1; j < n; j++)
    {
        printf ("%d", HuffCode[i].bit[j]);
    }
    printf(" start:%d",HuffCode[i].start);

    printf ("\n");

}

/* for(i=0;i<n;i++){
for(j=0;j<n;j++)
{
printf ("%d", HuffCode[i].bit[j]);

}
printf("\n");
}*/
printf("Decoding?Please Enter code:\n");
scanf("%s",&pp);
decodeing(pp,HuffNode,n);
getch();
return 0;
}

dtt_123
dtt_123 回复qq_37241799: 谢啦,不过还有一个问题那怎么将哈夫曼树打印出来
一年多之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
哈夫曼编码/译码(实验文档)
  哈夫曼编码/译码一、【实验内容】【问题描述】      利用哈夫曼编码进行住处通讯可以大大提高信道利用率,缩短住处传输时间,降低成本,但是,这要求在发送端通过一个编码系统将传输的数据预先编码,在接收端通过一个译码系统对传来的数据进行译码(复原),对于双向传输信息的信道,每端都一个完整的编码译码系统,试为这样的住处收发站写一个哈夫曼友的编码译码系统.【基本要求】:一个完整的系统应以下功能
对文件进行哈夫曼编码压缩与译码的C++实现 以及压缩率计算 ——HIT杨朔
对英文文本文件进行哈夫曼编码译码的C++实现 以及压缩率计算哈夫曼编码压缩原理:由于每个字符在内存中都是以ASCII码进行存储,所以每个字符都占用了八个01位,利用哈夫曼树对每个字符进行01编码,根据字符在文章中出现的频率调整01串长度,出现频率高的字符在哈夫曼树中的权重大,编码后01串短,从而使得最终计算出的平均编码长度小于8,在本代码中平均编码长度约为4.72,压缩率约为59%,从而达到压缩文本
数据结构课程设计-哈夫曼编码译码
//******************************************** //程序功能:哈夫曼编码及译码 // //日期:2014年11月18 // //******************************************** #include #include #include #include #define MAX 128 //
Huffman哈夫曼编码译码器(文件输入输出流)C语言(C++)
C语言(其中用到了c++) 哈夫曼编码译码器,做课程设计的,许多网上的资料都不能直接使用,以下是经过修改后能成功运行的,其中huffman.txt文件放在项目目录,需要的可以自己改代码 下面上代码: (现在scanf,getch都不能直接使用,需要在上面加上#define _CRT_SECURE_NO_WARNINGS或者是使用scanf_s,_getch,诸如此类) #define
数据结构:哈夫曼树,哈夫曼编码与译码系统
将文本文件利用哈夫曼树进行编码,存储成压缩文件
哈夫曼编码与译码器
题目:哈夫曼编译码系统(Huffman) ① 问题描述:给定n个字符的全值数组w,根据哈夫曼编码与译码规则,实现一个哈夫曼编译码系统(利用实验指导书上的27个字符的数据进行实验)。 ② 利用顺序表存储Huffman树,编码结果的存储方式采用书上的结构。 ③ Huffman树的构造约定如下: l       根的权值较小的子树作为左子树,当权值相等时,先生成的作为左子树; l
哈夫曼编码译码器 数据结构与算法 课程设计
设计一个利用哈夫曼算法的编码和译码系统,重复地显示并处理“要求”中项目,直到选择退出为止。 要求: (1)将权值数据存放在数据文件(文件名为data.txt,位于执行程序的当前目录中) (2)分别采用动态和静态存储结构 (3)从键盘输入字符集大小n、n个字符和n个权值,建立哈夫曼树; (4)利用建好的哈夫曼树生成哈夫曼编码; (5)输出编码; 用户可以执行的的功能有: (1)---选择读取某个源文件由系统解析建立哈夫曼树 (2)---手动输入字符集及其权值信息建立哈夫曼树 (3)---打印字符集的哈夫曼编码到屏幕 (4)---选择某个文本文件进行编码 (5)---选择某个代码文件进行译码
哈夫曼编码/译码系统(树应用)
哈夫曼编码/译码系统(树应用) [问题描述] 利用哈夫曼编码进行通信,可以压缩通信的数据量,提高传输效率,缩短信息的传输时间,还有一定的保密性。现在要求编写一程序模拟传输过程,实现在发送前将要发送的字符信息进行编码,然后进行发送,接收后将传来的数据进行译码,即将信息还原成发送前的字符信息。 [实现提示] 在本例中设置发送者和接受者两个功能, 发送者的功能包括: ①输入待传送的字符信息;
哈夫曼编码/译码器数据结构课程设计
设计一个哈夫曼编码/译码系统,对一个文本文件中的字符进行哈夫曼编码,生成编码文件(后缀名.cod);反过来,可将一个编码文件还原为一个文本文件(.txt)。 要求: (1)输入一个待编码的文本文件名,统计文本文件中各字符的个数作为权值,生成哈夫曼树; (2)将文本文件利用哈夫曼树进行编码,生成编码文件(后缀名cod); (3)输入一个待解码的编码文件名称,并利用相应的哈夫曼树将编码文件译码; (4)显示指定的编码文件和文本文件; (5)把哈夫曼编码用二进制位紧缩到一个变量中,利用位运算进行真正的数据压缩,并求压缩比。(此选项选作)
南邮数据结构实验二---二叉树的基本操作及哈夫曼编码译码系统的实现
目的:创建一棵二叉树,实现先序、中序和后序遍历一棵二叉树, 计算二叉树结点个数等操作。 哈夫曼编码/译码系统。 要求: 能成功演示二叉树的有关运算, 运算完毕后能成功释放二叉树所有结点占用的系统内存。 程序一:二叉树的创建以及基本运算 main.cpp #include"BTree.h" #include int main() { BTree d,e,f,b,c,a