| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 454 人关注过本帖, 1 人收藏
标题:关于哈弗曼的解压
只看楼主 加入收藏
chenloveyou
Rank: 1
来 自:西安
等 级:新手上路
帖 子:16
专家分:0
注 册:2012-12-17
结帖率:20%
收藏(1)
已结贴  问题点数:8 回复次数:8 
关于哈弗曼的解压
程序代码:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct
{   
    int weight;   
    char ch;                 
    int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode; 

void welcome();    
void HuffmanCoding(HuffmanTree &,char *,int *,int);
void select(HuffmanTree HT,int j,int *s1,int *s2); 
void Init(); 
void Coding(); 
void Decoding(); 
void Print_code(); 
int Read_tree(HuffmanTree &); 
void find(HuffmanTree &HT,char *code,char *text,int i,int m);

HuffmanTree HT; 
int n=0; 

int main()
{
    char select;
    while(1)
    {
        welcome();
        scanf("%c",&select);
        switch(select)
        {
        case '1':Init();break;
        case '2':Coding();break;
        case '3':Decoding();break;
        case '4':Print_code();break;
        case '5':exit(1);
        default :printf("Input error!\n");
        }
        getchar();
    }
    return 0;
}

void welcome() 
{
    printf("*_______________________________________________________*\n");
    printf("|                            菜单                       |\n");
    printf("|_______________________________________________________|\n");
    printf("|                                                      |\n");
    printf("|                                                      |\n");
    printf("| 1  --------------------------建立哈夫曼树.           |\n");
    printf("| 2  --------------------------哈夫曼树编码压缩.       |\n");
    printf("| 3  --------------------------哈夫曼树译码.           |\n");
    printf("| 4  --------------------------输出压缩codefile文件.   |\n");
    printf("| 5  --------------------------退出.                   |\n");
    printf("|                                                      |\n");
    printf("|______________________________________________________|\n");
    printf("|______________________________________________________|\n");
}


void Init() 
{
    FILE *fp;
    int i,n,w[50]; 
    char character[50]; 
    printf("\n输入字符个数 n:");
    scanf("%d",&n);       
    printf("输入%d个字符:\n",n);
    for (i=0;i<n;i++)
    {
        char b=getchar();
        scanf("%c",&character[i]);          
    }
    printf("输入%d个对应的权值:\n",n);
    for(i=0;i<n;i++)
    {
        char b=getchar();
        scanf("%d",&w[i]);                  
    }
    HuffmanCoding(HT,character,w,n);    
    if((fp=fopen("hfmtree.txt","w"))==NULL)
        printf("打开文件 hfmtree.txt 错误!\n");
    for (i=1;i<=2*n-1;i++)
    {
        if(fwrite(&HT[i],sizeof(HTNode),1,fp)!=1)   
            printf("文件写入错误!\n");
    }
    printf("\n建立赫夫曼树成功,已将其存于文件hfmtree.txt中\n");
    fclose(fp);
}

void HuffmanCoding(HuffmanTree &HT,char *character,int *w,int n)
{
    int m,i,s1,s2;
    HuffmanTree p;
    if(n<=1) return;
    m=2*n-1;
    HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
    for(p=HT+1,i=1;i<=n;++i,++p,++character,++w)
    {
        p->ch=*character;p->weight=*w;p->parent=0;p->lchild=0;p->rchild=0;
    }
    for(i=n+1;i<=m;++i,++p) 
    {
        p->ch=0;p->weight=0;p->parent=0;p->lchild=0;p->rchild=0;
    }
    for(i=n+1;i<=m;++i)
    {
        select(HT,i-1,&s1,&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;
    }
}

void select(HuffmanTree HT,int j,int *s1,int *s2)
{
    int i;
    for (i=1;i<=j;i++) 
        if (HT[i].parent==0)
        {
            *s1=i;break;
        }
        for (;i<=j;i++)
            if ((HT[i].parent==0)&&(HT[i].weight<HT[*s1].weight))
                *s1=i;
            HT[*s1].parent=1;
            for (i=1;i<=j;i++)
                if (HT[i].parent==0)
                {
                    *s2=i;break;
                }
                for (;i<=j;i++)
                    if ((HT[i].parent==0)&&(i!=*s1)&&(HT[i].weight<HT[*s2].weight))
                        *s2=i;
}

void Coding() 
{
    FILE *fp,*fw;
    int i,f,c,start,t=1,J,l,k=1;
    char *cd;
    HuffmanCode HC;
    if(n==0)
        n=Read_tree(HT);
    
    {
        HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
        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';
                else cd[--start]='1';
                HC[i]=(char *)malloc((n-start)*sizeof(char));
                strcpy(HC[i],&cd[start]);
        }
        free(cd);
    }

    if((fp=fopen("tobetrans.txt","rb"))==NULL)
        printf("打开文件tobetrans.txt 错误!\n");
    if((fw=fopen("codefile.txt","wb"))==NULL)
        printf("打开文件 codefile.txt 错误!\n");
//    fscanf(fp,"%c",&temp); 
//    while(!feof(fp))
//    {
//    
//        for(i=1;i<=n;i++) 
//        if(HT[i].ch==temp) break;              //该部分为直接输出哈夫曼编码
//        for(int r=0;HC[i][r]!='\0';r++) 
//        {
//            fputc(HC[i][r],fw);
//        }
//        fscanf(fp,"%c",&temp);  
        
//    }
    char temp;
    while(!feof(fp))
    {   
        temp=fgetc(fp);
        for(i=1;i<=n;i++)
        {
            if(HT[i].ch==temp)
            {
                l=strlen(HC[i]);
                if(l+k>=32)
                {
                    fwrite(&c,4,1,fw);
                    c=1;                      //该部分为输出压缩文件
                    k=1;
                }
                for(J=0;J<l;J++)
                {
                    if(HC[i][J]=='0')
                        c=c<<1;
                    else
                    {c=c<<1;c=c|1;}
                    k++;
                }
                break;
            } 
        }
    }
    fwrite(&c,4,1,fw);
    fclose(fw);
    fclose(fp);
    printf("\n对文件hfmtree.txt编码,压缩成功,结果存入codefile.txt中。\n\n");
}
     

 
void Decoding() 
{
    FILE *fp,*fw;
    int m,i;
    char *code,*text,*p;
    
    if(n==0)
        n=Read_tree(HT);
    if((fp=fopen("codefile.txt","r"))==NULL)
        printf("打开文件 codefile.txt 错误!\n");
    if((fw=fopen("textfile.txt","w"))==NULL)
        printf("打开文件 textfile.txt 错误!\n");
    code=(char *)malloc(sizeof(char));

    fscanf(fp,"%c",code);       ////////////////////////////////////////////////////////
    for(i=1;!feof(fp);i++)
    {
        code=(char *)realloc(code,(i+1)*sizeof(char)); 
        fscanf(fp,"%c",&code[i]);     
    }
    code[i-1]='\0';
    text=(char *)malloc(100*sizeof(char));
    p=text;                                         //中间这部分要改
    m=2*n-1;
    if(*code=='0')
        find(HT,code,text,HT[m].lchild,m);  
    else
        find(HT,code,text,HT[m].rchild,m);   
    
    for(i=0;p[i]!='\0';i++) 
        fputc(p[i],fw);////////////////////////////////////////////////////////////////
    //fwrite(& ,4,1,fw);
/*    int t=1,J,l,k=1,c;
    char temp;
    HuffmanCode HC;
    while(!feof(fp))
    {   
        temp=fgetc(fp);
        for(i=1;i<=n;i++)
        {
            if(HT[i].ch==temp)
            {
                l=strlen(HC[i]);
                if(l+k>=32)
                {
                    fwrite(&c,4,1,fw);
                    c=1;                      //该部分为输出压缩文件
                    k=1;
                }
                for(J=0;J<l;J++)
                {
                    if(HC[i][J]=='0')
                        c=c>>1;
                    else
                    {c=c>>1;c=c|1;}
                    k++;
                }
                break;
            } 
        }
    }
    fwrite(&c,4,1,fw);*///////////////
    fclose(fp);
    fclose(fw);
    printf("\n对codefile.txt文件译码成功,结果已存入textfile.txt文件。\n\n");
}

void find(HuffmanTree &HT,char *code,char *text,int i,int m)
{
    
    if(*code!='\0') //若译码未结束
    {
        code++;

    if(HT[i].lchild==0&&HT[i].rchild==0)   //若找到叶子节点
        {
            
            *text=HT[i].ch; 
            text++;
            if((*code=='0'))
                find(HT,code,text,HT[m].lchild,m); 
            else
                find(HT,code,text,HT[m].rchild,m); 
        }
        else   //如果不是叶子节点
            if(*code=='0')
                find(HT,code,text,HT[i].lchild,m);   
            else
                find(HT,code,text,HT[i].rchild,m);   
            
            
    }
    else
        *text='\0'; //译码结束
    
}
void Print_code()
{
    FILE *fp,*fw;
    char temp;
    int i;
    if((fp=fopen("codefile.txt","r"))==NULL)
        printf("打开文件codefile.txt 错误!\n");
    if((fw=fopen("codeprint.txt","w"))==NULL)
        printf("打开文件 codeprint.txt 错误!\n");
    printf("\n文件codefi1e以压缩形式如下:\n");
    fscanf(fp,"%c",&temp);        //从文件读入一个字符
    for (i=1;!feof(fp);i++)
    {  
        printf("%c",temp);
        if(i%50==0) printf("\n");
        fputc(temp,fw);   //将该字符存入文件codeprint.txt中
        fscanf(fp,"%c",&temp);        //从文件读入一个字符
    }
    printf("\n\n此字符形式的编码已写入文件codeprint.txt中.\n\n");
    fclose(fp);
    fclose(fw);    
}

int Read_tree(HuffmanTree &HT) 
{
    FILE *fp;
    int i,n;
    HT=(HuffmanTree)malloc(sizeof(HTNode));
    if((fp=fopen("hfmtree.txt","r"))==NULL)
        printf("打开文件 hfmtree.txt 错误!\n");
    for (i=1;!feof(fp);i++)
    {
        HT=(HuffmanTree)realloc(HT,(i+1)*sizeof(HTNode)); 
        fread(&HT[i],sizeof(HTNode),1,fp); 
    }
    fclose(fp);
    n=(i-1)/2;
    return n;//返回叶子
}
搜索更多相关主题的帖子: 哈弗 parent 
2012-12-20 21:18
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:3 
一头雾水,解压?


[fly]存在即是合理[/fly]
2012-12-20 21:25
chenloveyou
Rank: 1
来 自:西安
等 级:新手上路
帖 子:16
专家分:0
注 册:2012-12-17
收藏
得分:0 
回复 2楼 azzbcc
void Decoding() 这个函数
把存在文件中的压缩过的文件解压,并译码存入另一个文件
2012-12-20 21:28
yaobao
Rank: 13Rank: 13Rank: 13Rank: 13
等 级:蒙面侠
威 望:4
帖 子:1854
专家分:4121
注 册:2012-10-25
收藏
得分:3 
第一次接触解压,学习楼主代码

认认真真的学习,踏踏实实的走路:戒骄戒躁!!!
2012-12-20 21:31
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
哦,什么问题?清楚一些


[fly]存在即是合理[/fly]
2012-12-20 21:35
chenloveyou
Rank: 1
来 自:西安
等 级:新手上路
帖 子:16
专家分:0
注 册:2012-12-17
收藏
得分:0 
回复 4楼 yaobao
额……菜……菜菜鸟
2012-12-20 21:36
chenloveyou
Rank: 1
来 自:西安
等 级:新手上路
帖 子:16
专家分:0
注 册:2012-12-17
收藏
得分:0 
回复 5楼 azzbcc
这个代码想实现功能:创建一个哈夫曼树,将其压缩存入txt文件中,然后在经过解压把压缩的txt文件解压存到另一个txt文件中。
原来那个函数只能实现将哈夫曼编码译码,但是现在直接译码就不行了,因为被压缩了。所以先要解码,所以…………、

不知道这样说清了没有
2012-12-20 21:44
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
tobetrans.txt  ??

什么东东?,找不到。。。。


[fly]存在即是合理[/fly]
2012-12-20 22:09
晴娣
Rank: 2
等 级:论坛游民
帖 子:21
专家分:38
注 册:2010-12-29
收藏
得分:3 
解压??copy下代码, 有时间仔细看一下……
2012-12-20 22:20
快速回复:关于哈弗曼的解压
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.056787 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved