哈夫曼树运行错误 但调试却正确 一直找不成错误

估计问题是出在HuffmanCoding 但怎么都找不出来

 #include "stdio.h"
#include "stdlib.h"
#include "string.h"
char alphabet[]={'A','B','C','D'};
typedef struct 
{
    int weight;     //权值 
    int parent;     //父节点序号 
    int left ;
    int right;
}HuffmanTree;

typedef char *HuffmanCode;  //Huffman编码指针 
void SelectNode (HuffmanTree *ht,int n,int *bt1,int *bt2)
//从n个节点中选择parent节点为0,权重最小的两个节点 
{
    int i;
    HuffmanTree *ht1,*ht2,*t;
    ht1=ht2=NULL;
    for(i=1;i<=n;i++)
    {
        if(!ht[i].parent)               //父节点为空 
        {
            if(ht1==NULL)   
            {
                ht1=ht+i;               // 
                continue;
            }
            if(ht2==NULL)
            {
                ht2=ht+i;
                if(ht1->weight>ht2->weight)
                {
                    t=ht2;
                    ht2=ht1;
                    ht1=t;          //让ht1指向最小节点 ht2指向第二小 
                }
                continue;
            }
            if(ht1 &&ht2)
            {
                if(ht[i].weight<=ht1->weight)
                {
                    ht2=ht1;                    //如果还有比ht1更小的则把ht1赋给ht2 ,ht1继续等于最小 
                    ht1=ht+i;
                }
                else if(ht[i].weight<ht2->weight){
                    ht2=ht+i;                       //没有比ht1更小的 但有比ht2小的 
                }
            }
        }
    } 
    if(ht1>ht2){                    //按数组最初的位置排序 
        *bt2=ht1-ht;
        *bt1=ht2-ht;
    }
    else
    {
        *bt1=ht1-ht;
        *bt2=ht2-ht;
    }
}
void CreateTree(HuffmanTree *ht,int n,int *w)
{
    int i,m=2*n-1;    //总节点数 
    int bt1,bt2;
    if(n<=1)
        return ;
    for(i=1;i<=n;++i)
    {
        ht[i].weight=w[i-1];
        ht[i].parent=0;
        ht[i].left=0;
        ht[i].right=0;
    } 
    for(;i<=m;++i)
    {
        ht[i].weight=0;
        ht[i].parent=0;
        ht[i].left=0;
        ht[i].right=0;
    }
    for(i=n+1;i<=m;++i)
    {
        SelectNode(ht,i-1,&bt1,&bt2);
        ht[bt1].parent=i;
        ht[bt2].parent=i;
        ht[i].left=bt1;
        ht[i].right=bt2;
        ht[i].weight=ht[bt1].weight+ht[bt2].weight;  
    }
}


void HuffmanCoding(HuffmanTree *ht,int n,HuffmanCode *hc)
{
    char *cd;
    int start,i;
    int current,parent;
    cd=(char*)malloc(sizeof(char)*n);
    cd[n-1]='\0';
    for(i=1;i<=n;i++)
    {
        start=n-1;                      
        current=i;                          //获得当前节点序号 
        parent=ht[current].parent;          //获得当前节点父亲的序号 
        while(parent)           //当父节点不为空 
        {
            if(current==ht[parent].left)    //若当前节点是父亲的左节点 
                cd[--start]='0';            //字符最后编码为0 注意这个编码是逆序的 最后其实根节点 
            else
                cd[--start]='1';
            current=parent;                 //从当前节点向根节点寻找 
            parent=ht[parent].parent;
        }
        hc[i-1]=(char*)malloc(sizeof(char*)*(n-start)); //分配保存编码的内存 
        strcpy(hc[i-1],&cd[start]);                     //复制生成的编码 
    }
    free(cd);
} 

void Encode(HuffmanCode *hc,char *alphabet,char *str,char *code)
{
    int len=0,i=0,j;
    code[0]='\0';
    while(str[i])
    {
        j=0;
        while(alphabet[j]!=str[i])   //搜索字母在编码表的位置 
            j++;
        strcpy(code+len,hc[j]);     //字母在叶节点的编号到根节点的编号全部复制给code 
        len=len+strlen(hc[j]);      // 扩大len的长度(也就是节点深度) 
        i++;                    
    }
    code[len]='\0';
}

void Decode(HuffmanTree *ht,int m,char *code,char *alphabet,char *decode)//解码 
{
    int position=0,i,j=0;
    m=2*m-1;
    while(code[position])
    {
        for(i=m;ht[i].left &&ht[i].right;position++ )   
        {   
            if(code[position]=='0')             
                i=ht[i].left;               
            else
                i=ht[i].right;
        }
        decode[j]=alphabet[i-1];
        j++;
    }   
    decode[j]='\0';
}
int main()
{
    int i,n=4,m;
    char test[]="DBDBDABDCDADBDADBDADACDBDBD";
    char code[100],code1[100];

    int w[]={5,7,2,13};
    HuffmanTree *ht;
    HuffmanCode *hc;
    m=2*n-1;
    ht=(HuffmanTree *)malloc((m+1)*sizeof(HuffmanTree));
    if(!ht)
    {
        printf("分配内存失败\n");
        exit(0);
    }
    CreateTree(ht,n,w);
    HuffmanCoding(ht,n,hc);
    for(i=1;i<=n;i++)
        printf("字母:%c,权重:%d,编码:%s\n",alphabet[i-1],ht[i].weight,hc[i-1]);
    Encode(hc,alphabet,test,code);
    printf("\n字符串:\n%s\n转换后:\n%s\n",test,code);
    Decode(ht,n,code,alphabet,code1);
    printf("\n编码:\n%s\n转换后:\n%s\n",code,code1);

    return 0;
} 

3个回答

我帮你看看~~~~~~~~~~~~·

简单帮你修改了下。请采纳!

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
char alphabet[]={'A','B','C','D'};
typedef struct 
{
    int weight;     //权值 
    int parent;     //父节点序号 
    int left ;
    int right;
}HuffmanTree;

typedef char *HuffmanCode;  //Huffman编码指针 
void SelectNode (HuffmanTree *ht,int n,int *bt1,int *bt2)
//从n个节点中选择parent节点为0,权重最小的两个节点 
{
    int i;
    HuffmanTree *ht1,*ht2,*t;
    ht1=ht2=NULL;
    for(i=1;i<=n;i++)
    {
        if(!ht[i].parent)               //父节点为空 
        {
            if(ht1==NULL)   
            {
                ht1=ht+i;               // 
                continue;
            }
            if(ht2==NULL)
            {
                ht2=ht+i;
                if(ht1->weight>ht2->weight)
                {
                    t=ht2;
                    ht2=ht1;
                    ht1=t;          //让ht1指向最小节点 ht2指向第二小 
                }
                continue;
            }
            if(ht1 &&ht2)
            {
                if(ht[i].weight<=ht1->weight)
                {
                    ht2=ht1;                    //如果还有比ht1更小的则把ht1赋给ht2 ,ht1继续等于最小 
                    ht1=ht+i;
                }
                else if(ht[i].weight<ht2->weight){
                    ht2=ht+i;                       //没有比ht1更小的 但有比ht2小的 
                }
            }
        }
    } 
    if(ht1>ht2){                    //按数组最初的位置排序 
        *bt2=ht1-ht;
        *bt1=ht2-ht;
    }
    else
    {
        *bt1=ht1-ht;
        *bt2=ht2-ht;
    }
}
void CreateTree(HuffmanTree *ht,int n,int *w)
{
    int i,m=2*n-1;    //总节点数 
    int bt1,bt2;
    if(n<=1)
        return ;
    for(i=1;i<=n;++i)
    {
        ht[i].weight=w[i-1];
        ht[i].parent=0;
        ht[i].left=0;
        ht[i].right=0;
    } 
    for(;i<=m;++i)
    {
        ht[i].weight=0;
        ht[i].parent=0;
        ht[i].left=0;
        ht[i].right=0;
    }
    for(i=n+1;i<=m;++i)
    {
        SelectNode(ht,i-1,&bt1,&bt2);
        ht[bt1].parent=i;
        ht[bt2].parent=i;
        ht[i].left=bt1;
        ht[i].right=bt2;
        ht[i].weight=ht[bt1].weight+ht[bt2].weight;  
    }
}


void HuffmanCoding(HuffmanTree *ht,int n,HuffmanCode *hc)
{
    char *cd;
    int start,i;
    int current,parent;
    cd=(char*)malloc(sizeof(char)*n);
    cd[n-1]='\0';
    for(i=1;i<=n;i++)
    {
        start=n-1;                      
        current=i;                          //获得当前节点序号 
        parent=ht[current].parent;          //获得当前节点父亲的序号 
        while(parent)           //当父节点不为空 
        {
            if(current==ht[parent].left)    //若当前节点是父亲的左节点 
                cd[--start]='0';            //字符最后编码为0 注意这个编码是逆序的 最后其实根节点 
            else
                cd[--start]='1';
            current=parent;                 //从当前节点向根节点寻找 
            parent=ht[parent].parent;
        }

        hc[i-1]=(char*)malloc(sizeof(char)*(n-start)); //分配保存编码的内存 
        strcpy(hc[i-1],&cd[start]);                     //复制生成的编码 
    }
    free(cd);
} 

void Encode(HuffmanCode *hc,char *alphabet,char *str,char *code)
{
    int len=0,i=0,j;
    code[0]='\0';
    while(str[i])
    {
        j=0;
        while(alphabet[j]!=str[i])   //搜索字母在编码表的位置 
            j++;
        strcpy(code+len,hc[j]);     //字母在叶节点的编号到根节点的编号全部复制给code 
        len=len+strlen(hc[j]);      // 扩大len的长度(也就是节点深度) 
        i++;                    
    }
    code[len]='\0';
}

void Decode(HuffmanTree *ht,int m,char *code,char *alphabet,char *decode)//解码 
{
    int position=0,i,j=0;
    m=2*m-1;
    while(code[position])
    {
        for(i=m;ht[i].left &&ht[i].right;position++ )   
        {   
            if(code[position]=='0')             
                i=ht[i].left;               
            else
                i=ht[i].right;
        }
        decode[j]=alphabet[i-1];
        j++;
    }   
    decode[j]='\0';
}
int main()
{
    int i,n=4,m;
    char test[]="DBDBDABDCDADBDADBDADACDBDBD";
    char code[100],code1[100];

    int w[]={5,7,2,13};
    HuffmanTree *ht;
    HuffmanCode *hc;
    m=2*n-1;
    ht=(HuffmanTree *)malloc((m+1)*sizeof(HuffmanTree));
    hc=(HuffmanCode *)malloc((n+1)*sizeof(HuffmanCode));
    if(!ht)
    {
        printf("分配内存失败\n");
        exit(0);
    }
    CreateTree(ht,n,w);
    HuffmanCoding(ht,n,hc);
    for(i=1;i<=n;i++)
        printf("字母:%c,权重:%d,编码:%s\n",alphabet[i-1],ht[i].weight,hc[i-1]);
    Encode(hc,alphabet,test,code);
    printf("\n字符串:\n%s\n转换后:\n%s\n",test,code);
    Decode(ht,n,code,alphabet,code1);
    printf("\n编码:\n%s\n转换后:\n%s\n",code,code1);
    free(hc);
    hc = NULL;
    free(ht);
    ht = NULL;
    return 0;
} 
gsky1986
foreach_break 回复bill1829: 请查看http://blog.csdn.net/gsky1986/article/details/45388915
大约 5 年之前 回复
gsky1986
foreach_break 请采纳!随后给你详解。
大约 5 年之前 回复
bill1829
bill1829 就改了最后吗? 为什么要这样?
大约 5 年之前 回复

图片说明

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
怎样打印哈夫曼树,在运行的时候可以看到自己的哈夫曼树?

怎样将自己构建的哈夫曼树打印出来,运行时能够看到自己的树,用横线个竖线形成的树,求高手解答,有代码的话能不能贴出来看看,学习学习,谢谢!

项目开发中哈夫曼树应用

在项目开发过程中碰到一个难点,请教各位高手指点: **应用场景** 由于项目需求,需要设计一个条形码(纯数字字符串),条形码长度小于30Byte. 条形码输入后程序需要解码识别. 个人思路: 1.将相关信息进行哈夫曼树编码,输入条形码数字后进行哈夫曼树解码; 难点: 1.条形码如何携带哈夫曼树动态树信息;

关于写哈夫曼树的思路

哪位能给一个写哈夫曼树的思路啊。我想了好久都不会写,不知道怎么才能把自己输入的东西用哈夫曼树翻译出来。求帮助

横向打印哈夫曼树的问题

已经存储在二维数组中的哈夫曼树。怎么以树的形式横向打印出来,就是有分支的那种。

用c++构建一个哈夫曼树

输入字符个数,权值,打印哈夫曼树,编码和译码,源代码,可以用c-free运行的那种,求各位大神帮忙解答,要完整的代码拜托了

数据结构哈夫曼树代码怎么写

哈夫曼树:输入一串只包含abcdefg8种字符的字符串,统计每种字符出现的次数,并据此创建相应的哈夫曼树。 这怎么写

哈夫曼树带权路径长度简便算法问题

各位大神应该知道一棵 哈夫曼树的带权路径长度=所有叶子节点的带权路径长度和 应该也知道还有另一种算法 哈夫曼树的带权路径长度=所有非叶子结点的权值和 ![图片说明](https://img-ask.csdn.net/upload/201604/04/1459752161_872418.jpg) 有谁能证明一下这个吗? 或者告诉我哪本书上有讲这个证明的?

哈夫曼树的构造技巧以及权值问题

数据结构中树的权值最优问题,还有怎样构造哈夫曼树,求详细的解答,谢谢啦!

求一段可以打印哈夫曼树的代码,能够在执行时看到的,谢谢!!

求一段可以将我写的哈夫曼树打印出来的代码,谢谢!!我正在写一个huffman的编码和译码的程序可是不会写打印的,请大家帮忙

数据结构作业,三叉哈夫曼树的实现

这是我用二叉哈夫曼树代码改的,但是无法实现,首先是叶子节点和节点数没法表示,然后就算自己输入固定节点也无法正确实现,请问怎么实现三叉哈夫曼树呢 #include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> using namespace std; typedef struct { unsigned int weight; //结点权值 unsigned int parent, lchild, rchild; //结点的父指针,左右孩子指针 }HTNode, *HuffmanTree; //动态分配数组存储哈夫曼树 typedef char **HuffmanCode; //动态分配数组存储哈夫曼编码表 HuffmanTree HT; //哈夫曼树HT HuffmanCode HC; //哈夫曼编码表HC unsigned int *w; //w存放叶子结点权值 char * source_code;//source_code 存放原始码 void CreateHuffmanTree(HuffmanTree &, unsigned int*, int); //生成一棵哈夫曼树 void HuffmanCoding(HuffmanTree, HuffmanCode &, int); //对哈夫曼树进行编码 void PrintHuffmanCode(HuffmanCode, unsigned int*, int); //显示哈夫曼编码 void Select(HuffmanTree, int, int&, int&); //在数组中寻找权值最小的两个结点 int main() { int n, i; //n是哈夫曼树叶子结点数 char choose = 'y'; //用于选择程序是否退出 //程序解说 printf("本程序将演示构造哈夫曼树.\n"); printf("首先输入叶子结点数目.\n例如:2\n"); printf("然后输入原始码以及权值.\n"); printf("第1个原始码及其权值 :"); printf("a 5\n"); printf("第2个原始码及其权值 :"); printf("b 3\n"); printf("程序会构造一棵哈夫曼树并显示哈夫曼编码.\n"); cout << "权值" << " " << "原始码" << " " << "哈夫曼编码" << endl; printf(" 5 a 1\n"); printf(" 3 b 0\n"); putchar('\n'); putchar('\n'); while (choose != 'N'&&choose != 'n') { printf("请输入叶子结点数目:"); scanf("%d", &n); //输入叶子结点数 if (n <= 1) { printf("该数不合理!\n"); continue; } w = (unsigned int*)malloc(n * sizeof(unsigned int)); //开辟空间存放权值 source_code = (char *)malloc(n * sizeof(char)); //开辟空间存放原始码 //printf("请输入各原始码以及权值 :\n"); for (i = 0; i < n; i++) { printf("第%d个原始码及其权值 :", i + 1); cin >> source_code[i]; //输入原始码 cin >> w[i]; //输入各叶子结点权值 } CreateHuffmanTree(HT, w, n); //生成哈夫曼树 HuffmanCoding(HT, HC, n); //进行哈夫曼编码 putchar('\n'); PrintHuffmanCode(HC, w, n); //显示哈夫曼编码 printf("哈夫曼树构造完毕,还要继续吗?(Y/N)"); scanf(" %c", &choose); } } void CreateHuffmanTree(HuffmanTree &HT, unsigned int *w, int n) {//w存放n个结点的权值,将构造一棵哈夫曼树HT int i, m; int s1, s2; HuffmanTree p; if (n <= 1) return; m = 2 * n - 1; //n个叶子结点的哈夫曼树,有2*n-1个结点 HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode)); //开辟2*n各结点空间,0号单元不用 for (p = HT + 1, i = 1; i <= n; ++i, ++p, ++w) //进行初始化 { p->weight = *w; p->parent = 0; p->lchild = 0; p->rchild = 0; } for (; i <= m; ++i, ++p) { p->weight = 0; p->parent = 0; p->lchild = 0; p->rchild = 0; } for (i = n + 1; i <= m; ++i) //建哈夫曼树 { //从HT[1...i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2 Select(HT, i - 1, s1, s2); HT[s1].parent = i; HT[s2].parent = i; //修改s1和s2结点的父指针parent HT[i].lchild = s1; HT[i].rchild = s2; //修改i结点的左右孩子指针 HT[i].weight = HT[s1].weight + HT[s2].weight; //修改权值 } } void HuffmanCoding(HuffmanTree HT, HuffmanCode &HC, int n) { //将有n个叶子结点的哈夫曼树HT进行编码, 所编的码存放在HC中 //方法是从叶子到根逆向求每个叶子结点的哈夫曼编码 int i, c, f, start; char *cd; HC = (HuffmanCode)malloc((n + 1) * sizeof(char *)); //分配n个编码的头指针向量 cd = (char *)malloc(n * sizeof(char)); //开辟一个求编码的工作空间 cd[n - 1] = '\0'; //编码结束符 for (i = 1; i <= n; ++i) //逐个地求哈夫曼编码 { start = n - 1; //编码结束位置 for (c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent) //从叶子到根逆向求编码 if (HT[f].lchild == c) cd[--start] = '0'; //若是左孩子编为'0' else cd[--start] = '1'; //若是右孩子编为'1' HC[i] = (char *)malloc((n - start) * sizeof(char)); //为第i个编码分配空间 strcpy(HC[i], &cd[start]); //将编码从cd复制到HC中 } free(cd); //释放工作空间 } void PrintHuffmanCode(HuffmanCode HC, unsigned int *w, int n) { //显示有n个叶子结点的哈夫曼树的编码表 int i; printf("哈夫曼编码如下 :\n"); putchar('\n'); cout << "权值" << " " << "原始码" << " " << "哈夫曼编码" << endl; for (i = 1; i <= n; i++) { printf(" %d", w[i - 1]); printf(" %3c\t ", source_code[i - 1]); puts(HC[i]); } printf("\n"); } void Select(HuffmanTree HT, int t, int&s1, int&s2) { //在HT[1...t]中选择parent不为0且权值最小的两个结点,其序号分别为s1和s2,s1存放最小的,s2存放次小的 int i = 0; int j = 0; int k = 0; int least = 0; int second = 0; for (i = 1; i <= t; i++) { if (HT[i].parent == 0) break; } for (j = i + 1; j <= t; j++) { if (HT[j].parent == 0) break; } if (HT[i].weight < HT[j].weight) { least = i; second = j; } else { least = j; second = i; } for (k = j + 1; k <= t; k++) { if (HT[k].parent == 0) { if (HT[k].weight < HT[least].weight) { second = least; least = k; } else if (HT[k].weight >= HT[least].weight && HT[k].weight < HT[second].weight) second = k; } } s1 = least; s2 = second; }

哈夫曼树与哈夫曼编码

利用哈夫曼编码进行通信可以大大提高信道的利用率,缩短信息传输的时间,降低传输成本。根据哈夫曼编码的原理,编写一个程序,在用户输入结点权值的基础上求哈夫曼编码。 设计要求:从键盘输入若干字符及每个字符出现的频率,将字符出现的频率作为结点的权值,建立哈夫曼树,然后对各个字符进行哈夫曼编码,最后打印输出字符及对应的哈夫曼编码。

哈夫曼树算法设计编码译码

求大神帮忙用C++语言写一个算法设计 1)从键盘上输入要进行哈夫曼编码的字符集和对应的权值。 2)构造哈夫曼树的算法 3)完成哈夫曼编码的算法 4)完成哈夫曼译码算法。 5)利用编译码算法,对给定的文本文件t1.txt的英语内容进行编码,保存到指定文件code1.txt中。然后再编写一个函数对code1.txt中的内容进行译码。 要求输入哈夫曼编码时,能输出对应的字符。跪求了 真的没法写啊 想不到思路发到我哦空间或者是1511437725@qq.com都行啊

求教,哈夫曼树问题,感觉好难

大佬们,哈夫曼编码的问题,编码完毕后,下次不初始化,怎么从文件中读出哈夫曼树?怎么打印哈夫曼树?

C++哈夫曼树压缩的问题

在利用哈夫曼树进行压缩时,建立好哈夫曼树,得到得到每个叶子节点中的字符编码之后,如何使用位运算将编码中的每个位(BIT)设置到一个char类型的位缓冲中,可能多个编码才能填满一个位缓冲,每填满一次,将位缓冲区以单个字节的形式写入文件。这涉及到哪方面的知识,谢谢

哈夫曼树的建立和编码,提交时总是运行时错误

*![图片说明](https://img-ask.csdn.net/upload/201606/14/1465887225_826935.png) ``` #include <iostream> #include <stdlib.h> #include <cstdio> #include <string.h> #define MAX 1000000 using namespace::std; struct huffnode{ int weight;//权值 int lchild,rchild,parent; }typedef huffnode; void select(int len,int weight[],int &s1,int &s2,huffnode* &hufftree){ int min1=MAX; int min2=MAX; s1=-1; s2=-1; for(int i=0;i<len;i++){ if(hufftree[i].parent==-1){//没有父结点 if(hufftree[i].weight<min1){ s2=s1; min2=min1; s1=i; min1=hufftree[i].weight; } else if(hufftree[i].weight<min2){ s2=i; min2=hufftree[i].weight; } } } } void HuffCode(int weight[],int n,huffnode* &hufftree,char** &code){ int m=2*n-1;//霍夫曼树结点总数 int s1,s2;//最小值、此小值 //初始化霍夫曼树 hufftree=(huffnode*)malloc(m*sizeof(huffnode)); for(int i=0;i<n;i++){ hufftree[i].lchild=-1; hufftree[i].rchild=-1; hufftree[i].parent=-1; hufftree[i].weight=weight[i]; } for(int i=n;i<m;i++){ hufftree[i].lchild=-1; hufftree[i].rchild=-1; hufftree[i].parent=-1; hufftree[i].weight=0; } //构建霍夫曼树 for(int i=n;i<m;i++){ select(i,weight,s1,s2,hufftree);//从i的前面选取最小值和次小值 hufftree[s1].parent=i; hufftree[s2].parent=i; hufftree[i].lchild=s1; hufftree[i].rchild=s2; hufftree[i].weight=hufftree[s1].weight+hufftree[s2].weight;//构建新结点 } //霍夫曼编码 code=(char**)malloc(n*sizeof(char*));//n个结点的霍夫曼编码地址 // char temp_code[n];//临时存储霍夫曼编码 char *temp_code=(char*)malloc(n*sizeof(char)); for(int i=0;i<n;i++){//从叶节点访问到根节点 int a,b; int start=n; temp_code[start]='\0';//字符串结尾 for(a=i,b=hufftree[a].parent; b!=-1 ;a=hufftree[a].parent,b=hufftree[b].parent){ if(a==hufftree[b].lchild){ temp_code[--start]='0';//左分支为0 } else{ temp_code[--start]='1';//右分支为1 } } code[i]=(char *)malloc((n-start+1)*sizeof(char));//n个节点霍夫曼代码的值 strcpy(code[i],&temp_code[start]); } } int main(){ int n,i,j,k;//叶子结点总数 char s[200];//存放字符 int weight[200];//存放权值 huffnode *hufftree;//创建结构体数组用来存储霍夫曼树 char **code;//存储霍夫曼编码 char ss[200];//用于转化哈夫曼编码的字符 scanf("%d\n",&n); for(i=0;i<n;i++) scanf("%c ",&s[i]); s[n]='\0';//s是字符数组,不是字符串数组 for(i=0;i<n;i++) scanf("%d",&weight[i]); HuffCode(weight,n,hufftree,code); fflush(stdin);//清空缓存区 gets(ss); for(i=0;ss[i]!='\0';i++){ for(k=0;k<n;k++) if(s[k]==ss[i]) break; for(j=0;code[k][j]!='\0';j++) cout<<code[k][j]; } printf("\n"); puts(ss); return 0; } ```

基于哈夫曼树的数据压缩算法

A 基于哈夫曼树的数据压缩算法 时间限制(C/C++):1000MS/3000MS 运行内存限制:65536KByte 总提交:445 测试通过:131 描述 输入一串字符串,根据给定的字符串中字符出现的频率建立相应哈夫曼树,构造哈夫曼编码表,在此基础上可以对待压缩文件进行压缩(即编码),同时可以对压缩后的二进制编码文件进行解压(即译码)。 输入 多组数据,每组数据一行,为一个字符串(只考虑26个小写字母即可)。当输入字符串为“0”时,输入结束。 输出 每组数据输出2n+4行(n为输入串中字符类别的个数)。第一行为统计出来的字符出现频率(只输出存在的字符,格式为:字符:频度),每两组字符之间用一个空格分隔,字符按照ASCII码从小到大的顺序排列。第二行至第2n行为哈夫曼树的存储结构的终态(形如教材139页表5.2(b),一行当中的数据用空格分隔)。第2n+2行为每个字符的哈夫曼编码(只输出存在的字符,格式为:字符:编码),每两组字符之间用一个空格分隔,字符按照ASCII码从小到大的顺序排列。第2n+3行为编码后的字符串,第2n+4行为解码后的字符串(与输入的字符串相同)。 样例输入 aaaaaaabbbbbccdddd aabccc 0 样例输出 a:7 b:5 c:2 d:4 1 7 7 0 0 2 5 6 0 0 3 2 5 0 0 4 4 5 0 0 5 6 6 3 4 6 11 7 2 5 7 18 0 1 6 a:0 b:10 c:110 d:111 00000001010101010110110111111111111 aaaaaaabbbbbccdddd a:2 b:1 c:3 1 2 4 0 0 2 1 4 0 0 3 3 5 0 0 4 3 5 2 1 5 6 0 3 4 a:11 b:10 c:0 111110000 aabccc

C++哈夫曼编码译码器设计与实现并对哈夫曼树进行先序遍历。

现在就是差一个先序遍历的要求没有做到 ``` #include<stdio.h> #include<string.h> #include<stdlib.h> //树结点定义 typedef struct { int weight; int parent; int lchild; int rchild; }HTNode,*HuffmanTree; static char N[100];//用于保存正文 //哈弗曼编码,char型二级指针 typedef char **HuffmanCode; //封装最小权结点和次小权结点 typedef struct { int s1; int s2; }MinCode; //函数声明 void Error(char *message); HuffmanCode HuffmanCoding(HuffmanTree &HT,HuffmanCode HC,int *w,int n); MinCode Select(HuffmanTree HT,int n); //当输入1个结点时的错误提示 void Error(char *message) { fprintf(stderr,"Error:%s\n",message); //根据指定的格式,向输出流写入数据 exit(1); } //构造哈夫曼树HT,编码存放在HC中,w为权值,n为结点个数 HuffmanCode HuffmanCoding(HuffmanTree &HT,HuffmanCode HC,int *w,int n) { int i,s1=0,s2=0; HuffmanTree p; char *cd; int f,c,start,m; MinCode min; if(n<=1) { Error("Code too small!");//只有一个结点不进行编码,直接exit(1)退出。 } m=2*n-1;//哈弗曼编码需要开辟的结点大小为2n-1 HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//开辟哈夫曼树结点空间 m+1 ,动态内存分配。 //初始化n个叶子结点,w[0] = 0,main函数已赋值 for(p=HT,i=0;i<=n;i++,p++,w++) { p->weight=*w; p->parent=0; p->lchild=0; p->rchild=0; } //将n-1个非叶子结点的初始化 for(;i<=m;i++,p++) { p->weight=0; p->parent=0; p->lchild=0; p->rchild=0; } //构造哈夫曼树 for(i=n+1;i<=m;i++) { min=Select(HT,i-1);//找出最小和次小的两个结点 s1=min.s1 ; //最小结点下标 s2=min.s2;//次小结点下标 HT[s1].parent=i; HT[s2].parent=i; HT[i].lchild=s1; HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight; } //打印哈弗曼树 printf("HT List:\n"); printf("Number\t\tweight\t\tparent\t\tlchild\t\trchild\n"); for(i=1;i<=m;i++) { printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\t\n",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild); } //从叶子结点到根节点求每个字符的哈弗曼编码 HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); cd=(char *)malloc(n*sizeof(char *));//为哈弗曼编码动态分配空间 cd[n-1]='\0';//如:3个结点编码最长为2。cd[3-1] = '\0'; //求叶子结点的哈弗曼编码 for(i=1;i<=n;i++) { start=n-1; //定义左子树为0,右子树为1 /* 从最下面的1号节点开始往顶部编码(逆序存放),然后编码2号节点,3号...... */ for(c=i,f=HT[i].parent; f!=0; c=f,f=HT[f].parent) { if(HT[f].lchild==c) cd[--start]='0'; else cd[--start]='1'; } //为第i个字符分配编码空间 HC[i]=(char *)malloc((n-start)*sizeof(char *)); //将当前求出结点的哈弗曼编码复制到HC strcpy(HC[i],&cd[start]); } free(cd); return HC; } MinCode Select(HuffmanTree HT,int n) { int min,secmin; int temp = 0; int i,s1,s2,tempi = 0; MinCode code ; s1=1; s2=1; min = 9999; //找出权值最小的结点,下标保存在s1中 for(i=1;i<=n;i++) { if(HT[i].weight<min && HT[i].parent==0) { min=HT[i].weight; s1=i; } } secmin = 9999; //找出权值次小的结点,下标保存在s2中 for(i=1;i<=n;i++) { if((HT[i].weight<secmin) && (i!=s1) && HT[i].parent==0) { secmin=HT[i].weight; s2=i; } } //放进封装中 code.s1=s1; code.s2=s2; return code; } void HuffmanTranslateCoding(HuffmanTree HT, int n,char* ch) {//译码过程 int m=2*n-1; int i,j=0; printf("After Translation:"); while(ch[j]!='\0')//ch[]:你输入的要译码的0101010串 { i=m; while(0 != HT[i].lchild && 0 != HT[i].rchild)//从顶部找到最下面 { if('0' == ch[j])//0 往左子树走 { i=HT[i].lchild; } else//1 往右子树走 { i=HT[i].rchild; } ++j;//下一个路径 } printf("%c",N[i-1]);//打印出来 } printf("\n"); } void main() { HuffmanTree HT=NULL; HuffmanCode HC=NULL; int *w=NULL; int i,n; char tran[100]; printf("Input N(char):"); gets(N); fflush(stdin); n = strlen(N); w=(int *)malloc((n+1)*sizeof(int *));//开辟n+1个长度的int指针空间 w[0]=0; printf("Enter weight:\n"); //输入结点权值 for(i=1;i<=n;i++) { printf("w[%d]=",i); scanf("%d",&w[i]); } fflush(stdin); //清空输入缓冲区 //构造哈夫曼树HT,编码存放在HC中,w为权值,n为结点个数 HC=HuffmanCoding(HT,HC,w,n); //输出哈弗曼编码 printf("HuffmanCode:\n"); printf("Number\t\tWeight\t\tCode\n"); for(i=1;i<=n;i++) { printf("%c\t\t%d\t\t%s\n",N[i-1],w[i],HC[i]); } fflush(stdin); //译码过程 printf("Input HuffmanTranslateCoding:"); gets(tran); HuffmanTranslateCoding(HT, n, tran); return; } ```题目要求:九、哈夫曼编码译码器设计与实现 编写程序设计哈夫曼编码译码器。 (1)根据输入的权值建立哈夫曼树。 (2)对建立好的哈夫曼树进行先序遍历。 (3)利用建好的哈夫曼树生成哈夫曼编码,并显示生成的各字符的哈夫曼编码。 (4)根据输入的字符进行译码。 (5)显示功能:以先序遍历的顺序显示建立好的哈夫曼树。显示哈夫曼编码和译码的结果。

哈夫曼树在生活中的实例有哪些,各位大神拜托了,尽可能详细些,非常感谢

哈夫曼树在生活中的实例有哪些,各位大神拜托了,尽可能详细些,非常感谢

C语言文件/哈夫曼树/算法/二叉树

``` 在一个函数中,下面这两行运行无错误 fp=fopen("CodeFile.dat","wb"); fwrite(HC[i],sizeof(char),strlen(HC[i])+1,fp); //其中HC的类型是char ** //然后在另外一个函数中加入 fp=fopen("CodeFile.dat","rb"); for(int i=1;i<=n;i++) fread(HC[i].sizeof(char),strlen(HC[i])+1,fp); //就不行了,老是运行到这三行就出错。!! //补充一些 typedef char ** HuffmanCode; HuffmanCode HC; HC = (HuffmanCode)malloc((n+1)*sizeof(char *)); //求救 ```

在中国程序员是青春饭吗?

今年,我也32了 ,为了不给大家误导,咨询了猎头、圈内好友,以及年过35岁的几位老程序员……舍了老脸去揭人家伤疤……希望能给大家以帮助,记得帮我点赞哦。 目录: 你以为的人生 一次又一次的伤害 猎头界的真相 如何应对互联网行业的「中年危机」 一、你以为的人生 刚入行时,拿着傲人的工资,想着好好干,以为我们的人生是这样的: 等真到了那一天,你会发现,你的人生很可能是这样的: ...

程序员请照顾好自己,周末病魔差点一套带走我。

程序员在一个周末的时间,得了重病,差点当场去世,还好及时挽救回来了。

我以为我学懂了数据结构,直到看了这个导图才发现,我错了

数据结构与算法思维导图

String s = new String(" a ") 到底产生几个对象?

老生常谈的一个梗,到2020了还在争论,你们一天天的,哎哎哎,我不是针对你一个,我是说在座的各位都是人才! 上图红色的这3个箭头,对于通过new产生一个字符串(”宜春”)时,会先去常量池中查找是否已经有了”宜春”对象,如果没有则在常量池中创建一个此字符串对象,然后堆中再创建一个常量池中此”宜春”对象的拷贝对象。 也就是说准确答案是产生了一个或两个对象,如果常量池中原来没有 ”宜春” ,就是两个。...

技术大佬:我去,你写的 switch 语句也太老土了吧

昨天早上通过远程的方式 review 了两名新来同事的代码,大部分代码都写得很漂亮,严谨的同时注释也很到位,这令我非常满意。但当我看到他们当中有一个人写的 switch 语句时,还是忍不住破口大骂:“我擦,小王,你丫写的 switch 语句也太老土了吧!” 来看看小王写的代码吧,看完不要骂我装逼啊。 private static String createPlayer(PlayerTypes p...

Linux面试题(2020最新版)

文章目录Linux 概述什么是LinuxUnix和Linux有什么区别?什么是 Linux 内核?Linux的基本组件是什么?Linux 的体系结构BASH和DOS之间的基本区别是什么?Linux 开机启动过程?Linux系统缺省的运行级别?Linux 使用的进程间通信方式?Linux 有哪些系统日志文件?Linux系统安装多个桌面环境有帮助吗?什么是交换空间?什么是root帐户什么是LILO?什...

将一个接口响应时间从2s优化到 200ms以内的一个案例

一、背景 在开发联调阶段发现一个接口的响应时间特别长,经常超时,囧… 本文讲讲是如何定位到性能瓶颈以及修改的思路,将该接口从 2 s 左右优化到 200ms 以内 。 二、步骤 2.1 定位 定位性能瓶颈有两个思路,一个是通过工具去监控,一个是通过经验去猜想。 2.1.1 工具监控 就工具而言,推荐使用 arthas ,用到的是 trace 命令 具体安装步骤很简单,大家自行研究。 我的使用步骤是...

学历低,无法胜任工作,大佬告诉你应该怎么做

微信上收到一位读者小涛的留言,大致的意思是自己只有高中学历,经过培训后找到了一份工作,但很难胜任,考虑要不要辞职找一份他能力可以胜任的实习工作。下面是他留言的一部分内容: 二哥,我是 2016 年高中毕业的,考上了大学但没去成,主要是因为当时家里经济条件不太允许。 打工了三年后想学一门技术,就去培训了。培训的学校比较垃圾,现在非常后悔没去正规一点的机构培训。 去年 11 月份来北京找到了一份工...

JVM内存结构和Java内存模型别再傻傻分不清了

讲一讲什么是Java内存模型 Java内存模型虽说是一个老生常谈的问题 ,也是大厂面试中绕不过的,甚至初级面试也会问到。但是真正要理解起来,还是相当困难,主要这个东西看不见,摸不着。 这是一个比较开放的题目,面试官主要想考察的是对Java内存模型的了解到了什么程度了,然后根据回答进行进一步的提问 下面,我们就这个问题的回答列一下我们的思路 具体的思路如下: 说一说Java内存模型的缘由 简略辨析...

和黑客斗争的 6 天!

互联网公司工作,很难避免不和黑客们打交道,我呆过的两家互联网公司,几乎每月每天每分钟都有黑客在公司网站上扫描。有的是寻找 Sql 注入的缺口,有的是寻找线上服务器可能存在的漏洞,大部分都...

Google 与微软的浏览器之争

浏览器再现“神仙打架”。整理 | 屠敏头图 | CSDN 下载自东方 IC出品 | CSDN(ID:CSDNnews)从 IE 到 Chrome,再从 Chrome 到 Edge,微软与...

讲一个程序员如何副业月赚三万的真实故事

loonggg读完需要3分钟速读仅需 1 分钟大家好,我是你们的校长。我之前讲过,这年头,只要肯动脑,肯行动,程序员凭借自己的技术,赚钱的方式还是有很多种的。仅仅靠在公司出卖自己的劳动时...

上班一个月,后悔当初着急入职的选择了

最近有个老铁,告诉我说,上班一个月,后悔当初着急入职现在公司了。他之前在美图做手机研发,今年美图那边今年也有一波组织优化调整,他是其中一个,在协商离职后,当时捉急找工作上班,因为有房贷供着,不能没有收入来源。所以匆忙选了一家公司,实际上是一个大型外包公司,主要派遣给其他手机厂商做外包项目。**当时承诺待遇还不错,所以就立马入职去上班了。但是后面入职后,发现薪酬待遇这块并不是HR所说那样,那个HR自...

女程序员,为什么比男程序员少???

昨天看到一档综艺节目,讨论了两个话题:(1)中国学生的数学成绩,平均下来看,会比国外好?为什么?(2)男生的数学成绩,平均下来看,会比女生好?为什么?同时,我又联想到了一个技术圈经常讨...

搜狗输入法也在挑战国人的智商!

故事总是一个接着一个到来...上周写完《鲁大师已经彻底沦为一款垃圾流氓软件!》这篇文章之后,鲁大师的市场工作人员就找到了我,希望把这篇文章删除掉。经过一番沟通我先把这篇文章从公号中删除了...

85后蒋凡:28岁实现财务自由、34岁成为阿里万亿电商帝国双掌门,他的人生底层逻辑是什么?...

蒋凡是何许人也? 2017年12月27日,在入职4年时间里,蒋凡开挂般坐上了淘宝总裁位置。 为此,时任阿里CEO张勇在任命书中力赞: 蒋凡加入阿里,始终保持创业者的冲劲,有敏锐的...

总结了 150 余个神奇网站,你不来瞅瞅吗?

原博客再更新,可能就没了,之后将持续更新本篇博客。

副业收入是我做程序媛的3倍,工作外的B面人生是怎样的?

提到“程序员”,多数人脑海里首先想到的大约是:为人木讷、薪水超高、工作枯燥…… 然而,当离开工作岗位,撕去层层标签,脱下“程序员”这身外套,有的人生动又有趣,马上展现出了完全不同的A/B面人生! 不论是简单的爱好,还是正经的副业,他们都干得同样出色。偶尔,还能和程序员的特质结合,产生奇妙的“化学反应”。 @Charlotte:平日素颜示人,周末美妆博主 大家都以为程序媛也个个不修边幅,但我们也许...

MySQL数据库面试题(2020最新版)

文章目录数据库基础知识为什么要使用数据库什么是SQL?什么是MySQL?数据库三大范式是什么mysql有关权限的表都有哪几个MySQL的binlog有有几种录入格式?分别有什么区别?数据类型mysql有哪些数据类型引擎MySQL存储引擎MyISAM与InnoDB区别MyISAM索引与InnoDB索引的区别?InnoDB引擎的4大特性存储引擎选择索引什么是索引?索引有哪些优缺点?索引使用场景(重点)...

如果你是老板,你会不会踢了这样的员工?

有个好朋友ZS,是技术总监,昨天问我:“有一个老下属,跟了我很多年,做事勤勤恳恳,主动性也很好。但随着公司的发展,他的进步速度,跟不上团队的步伐了,有点...

我入职阿里后,才知道原来简历这么写

私下里,有不少读者问我:“二哥,如何才能写出一份专业的技术简历呢?我总感觉自己写的简历太烂了,所以投了无数份,都石沉大海了。”说实话,我自己好多年没有写过简历了,但我认识的一个同行,他在阿里,给我说了一些他当年写简历的方法论,我感觉太牛逼了,实在是忍不住,就分享了出来,希望能够帮助到你。 01、简历的本质 作为简历的撰写者,你必须要搞清楚一点,简历的本质是什么,它就是为了来销售你的价值主张的。往深...

离职半年了,老东家又发 offer,回不回?

有小伙伴问松哥这个问题,他在上海某公司,在离职了几个月后,前公司的领导联系到他,希望他能够返聘回去,他很纠结要不要回去? 俗话说好马不吃回头草,但是这个小伙伴既然感到纠结了,我觉得至少说明了两个问题:1.曾经的公司还不错;2.现在的日子也不是很如意。否则应该就不会纠结了。 老实说,松哥之前也有过类似的经历,今天就来和小伙伴们聊聊回头草到底吃不吃。 首先一个基本观点,就是离职了也没必要和老东家弄的苦...

男生更看重女生的身材脸蛋,还是思想?

往往,我们看不进去大段大段的逻辑。深刻的哲理,往往短而精悍,一阵见血。问:产品经理挺漂亮的,有点心动,但不知道合不合得来。男生更看重女生的身材脸蛋,还是...

什么时候跳槽,为什么离职,你想好了么?

都是出来打工的,多为自己着想

程序员为什么千万不要瞎努力?

本文作者用对比非常鲜明的两个开发团队的故事,讲解了敏捷开发之道 —— 如果你的团队缺乏统一标准的环境,那么即使勤劳努力,不仅会极其耗时而且成果甚微,使用...

为什么程序员做外包会被瞧不起?

二哥,有个事想询问下您的意见,您觉得应届生值得去外包吗?公司虽然挺大的,中xx,但待遇感觉挺低,马上要报到,挺纠结的。

当HR压你价,说你只值7K,你该怎么回答?

当HR压你价,说你只值7K时,你可以流畅地回答,记住,是流畅,不能犹豫。 礼貌地说:“7K是吗?了解了。嗯~其实我对贵司的面试官印象很好。只不过,现在我的手头上已经有一份11K的offer。来面试,主要也是自己对贵司挺有兴趣的,所以过来看看……”(未完) 这段话主要是陪HR互诈的同时,从公司兴趣,公司职员印象上,都给予对方正面的肯定,既能提升HR的好感度,又能让谈判气氛融洽,为后面的发挥留足空间。...

面试:第十六章:Java中级开发(16k)

HashMap底层实现原理,红黑树,B+树,B树的结构原理 Spring的AOP和IOC是什么?它们常见的使用场景有哪些?Spring事务,事务的属性,传播行为,数据库隔离级别 Spring和SpringMVC,MyBatis以及SpringBoot的注解分别有哪些?SpringMVC的工作原理,SpringBoot框架的优点,MyBatis框架的优点 SpringCould组件有哪些,他们...

面试阿里p7,被按在地上摩擦,鬼知道我经历了什么?

面试阿里p7被问到的问题(当时我只知道第一个):@Conditional是做什么的?@Conditional多个条件是什么逻辑关系?条件判断在什么时候执...

终于懂了TCP和UDP协议区别

终于懂了TCP和UDP协议区别

立即提问
相关内容推荐