|
|
转贴1
标题：huffman编码代码
出处：Wirlfly's Blog
时间：Tue, 05 Dec 2006 16:46:41 +0000
作者：wirlfly
地址：http://wf.xplore.cn/read.php/62.htm
内容：
huffman树和编码实现,由于偷懒，整个程序分为两部分，先读取待编码的文档，按字符出现的频率大小保存字符和频率值，然后在另一个程序里构造huffman树，再遍历的树的同时进行huffman编码，其中第一次是以1,0字符串形式保存的编码，第二次是以1,0整形保存的。在此非常感谢mlsx的指点，他的指导使我顿时思路霍然。呵呵。只有一个多月就要考研了，给位考研的朋友加油啊，坚持到最后,就胜利了一半！
引用
/* 下面的程序是整个HUFFMAN编码里读取待编码文件的一段 */
/* 其操作格式为：./huffmanreader 文件名 */
/* 采用链式表存储文档出现的字符和字符频率，输出在文件file_data.txt中 */
#include
#include
#define DEBUG 1 /* 宏定义调试参数 */
typedef struct node /* 定义一个存放文档里出现的元素的结构 */
{ int value; /* 存放元素的值，如c，A，数字，符号等等 */
int weight; /* 文档中该元素出现的次数 */
struct node *next; /* 采用链式结构，存放下一个节点的指针 */
struct node *lchild; /* 指向左孩子的指针 */
struct node *rchild; /* 指向右孩子的指针 */
struct node *parent; /* 指向双亲的指针 */
}Node,*NodePtr; /* Node，和NodePtr两个自定义的数据类型 */
void print(NodePtr); /* 打印函数，用于调试 */
int main(int argc,char *argv[]) /* 接受参数 */
{ int count=0; /* 统计元素个数 */
int count_list=0; /* 控制循环 */
int ctrl=0; /* 控制字符出现的先后 */
int char_tmp; /* 暂存字符 */
FILE *file_inPtr,*file_outPtr; /* 文档的FILE指针 */
NodePtr base,Ptr_next,Ptr_tmp; /* 定义的一系列指向结构的指针 */
if (argc!=2) /* 参数控制操作 */
{ perror("\nUsage:./** yourpathname!");
exit(1);
}
if ((file_inPtr=fopen(argv[1],"rb"))==NULL) /* 打开文件出错操作 */
{ perror("\nFile open error!");
exit(2);
}
rewind(file_inPtr); /* 反绕文档，把指针指向文档的起始地址 */
while ( getc(file_inPtr)!= EOF ) /* 统计元素个数 */
count++;
#ifdef DEBUG
printf("%d",count+1); /* 打印元素个数，用来调试 */
#endif
base=(NodePtr)malloc(sizeof(Node)); /* 分配地址给base，链表的头地址 */
base->next=NULL; /* 头地址的定义 */
rewind(file_inPtr); /* 反绕文档，把指针指向文档的起始地址 */
while(count_listnext; /* 初始化Ptr_tmp */
while(Ptr_tmp!=NULL) /* 寻找已出现的字符 */
{ if(Ptr_tmp->value==char_tmp)
{ Ptr_tmp->weight++;
ctrl=1; /* 字符已出现过，置位标志 */
break;
}
Ptr_tmp=Ptr_tmp->next; /* 循环 */
}
if (ctrl!=1) /* 字符为新出现的字符 */
{ Ptr_next=(NodePtr)malloc(sizeof(Node)); /* 新出现的则要分配地址 */
Ptr_next->value=char_tmp; /* 赋值 */
Ptr_next->next=base->next; /* 插入链表 */
Ptr_next->weight=1;
Ptr_next->lchild=NULL;
Ptr_next->rchild=NULL;
Ptr_next->parent=NULL;
base->next=Ptr_next;
}
}
fclose(file_inPtr); /* 关闭打开的文件 */
#ifdef DEBUG
print(base); /* 打印链表成员 */
#endif
if ((file_outPtr=fopen("file_data.txt","w"))==NULL) /* 打开文件出错操作 */
{ perror("\nFile open error!");
exit(3);
}
Ptr_tmp=base->next; /* 初始化以控制循环 */
while(Ptr_tmp!=NULL)
{ if (fwrite(Ptr_tmp,sizeof(Node),1,file_outPtr)==0) /* 写出错操作 */
{ perror("\nfwrite error!");
exit(4);
}
Ptr_tmp=Ptr_tmp->next; /* 逐个写进文件 */
}
fclose(file_outPtr); /* 关闭打开的文件 */
return 0;
}
void print(NodePtr base) /* 打印链表成员，调试之用，这里不详细说明了 */
{ NodePtr p_tmp;
int sum=0,total=0;
p_tmp=base->next;
while(p_tmp!=NULL)
{ sum+=p_tmp->weight;
total++;
printf("\n");
printf("value=%d,weight=%d",p_tmp-> value,p_tmp-> weight);
p_tmp=p_tmp->next;
}
printf("\n%d,%d",sum,total);
return;
}
引用
/* 下面的程序是整个HUFFMAN编码里进行编码的一段,它在huffmanreader程序运行后运行 */
/* 程序先读取file_data.txt中的内容，然后进行从大到小的排序 */
/* 将排序好的构造出huffman树，然后进行huffman编码，运行格式同上：./huffmancode 文件名 */
#include
#include
#include
#include
#include /* 以下都是UNIX-LIKE OS里的头文件，不是ANSI C里定义的 */
#include
#include
#include
//#define DEBUG 1 /* 定义DEBUG，把前面的//去掉可以看到调试的整个过程 */
#define SCALE 4 /* 定义字符的多少规模，一般取4或5足够了 */
typedef struct node /* 定义一个存放文档里出现的元素的结构 */
{ int value; /* 存放元素的值，如c，A，数字，符号等等 */
int weight; /* 文档中该元素出现的次数 */
struct node *next; /* 采用链式结构，存放下一个节点的指针 */
struct node *lchild; /* 指向左孩子的指针 */
struct node *rchild; /* 指向右孩子的指针 */
struct node *parent; /* 指向双亲的指针 */
}Node,*NodePtr; /* Node，和NodePtr两个自定义的数据类型 */
typedef struct code /* 存储第一次编码的结果的结构 */
{ int value; /* 待编码的字符值 */
char *huffmancodes; /* 用指针字符串的形式存储的huffman编码，这就是要进行二次编码的原因 */
struct code *next; /* 采用动态链表的方式存储 */
}Code,*CodePtr;
typedef struct real /* 存储二次编码的结果的结构 */
{ int value; /* 待编码的字符值 */
int realcode[SCALE*8]; /* 这里用的数组存储为int形式的huffman编码 */
struct real *next; /* 也是采用的动态链表存储 */
}Real,*RealPtr;
void print(NodePtr); /* 打印函数，用于调试 */
void printcode(CodePtr); /* 打印函数，用于调试 */
void printreal(RealPtr); /* 打印函数，用于调试 */
NodePtr sort(); /* 排序程序，由于字符的个数不会很多，所以采用插入排序 */
NodePtr hufftree(NodePtr); /* 构造huffman树 */
CodePtr huffcode(NodePtr); /* 第一次huffman编码 */
int PreOrderTrave(NodePtr,CodePtr,char *,void (*setchar)(char *)); /* 前序遍历整个huffman树 */
void delchar(char *); /* 在遍历回溯的时候删除最尾的一个字符 */
void putout(CodePtr); /* 开始想存储到文件中去，后来想想没必要，这里存储到文件中去 */
RealPtr compresscode(CodePtr); /* 压缩，思想方法是将编码以后的码位代替文件中的字符，以达到压缩效果 */
int replacecode(RealPtr,char *); /* 替代函数 */
int main(int argc,char *argv[]) /* 带参数，参数为待替代的原文件，不要紧张，不会覆盖原文件，呵呵 */
{ NodePtr base,Ptr_next;
NodePtr treebase;
CodePtr codebase;
RealPtr realbase;
if (argc!=2) /* 参数控制操作 */
{ perror("\nUsage:./** yourpathname!");
exit(1);
}
base=sort(); /* 有关函数声明，前面已经很详细的说明了，这是排序函数 */
#ifdef DEBUG
print(base); /* 打印排序后的字符频率表 */
printf("\n");
#endif
treebase=hufftree(base); /* 构造huffman树 */
Ptr_next=base->next; /* 释放前面的空间 */
while(Ptr_next!=NULL)
{ free(Ptr_next);
Ptr_next=Ptr_next->next;
}
free(base);
codebase=huffcode(treebase); /* huffman编码 */
realbase=compresscode(codebase); /* 二次编码 */
#ifdef DEBUG
printreal(realbase); /* 打印出二次编码后的结果 */
printf("\n");
#endif
#ifdef DEBUG
printcode(codebase); /* 打印一次编码后的结果，和二次编码后的看不出有什么变化，但是编码存储方式不同 */
printf("\n");
#endif
replacecode(realbase,argv[1]); /* 用编码(可惜我不会用位写进文件)替代文件中的字符 */
/* nodePtr_next=treebase->next;
while(nodePtr_next!=NULL)
{ free(nodePtr_next);
nodePtr_next=nodePtr_next->next;
}
free(treebase);
codePtr_next=codebase->next;
while(codePtr_next!=NULL)
{ free(codePtr_next);
codePtr_next=codePtr_next->next;
}
free(codebase);
realPtr_next=realbase->next;
while(realPtr_next!=NULL)
{ free(realPtr_next);
realPtr_next=realPtr_next->next;
}
free(realbase);*/
// putout(codebase);
return 0;
}
NodePtr sort()
{ FILE *file_inPtr; /* 文档的FILE指针 */
NodePtr base,Ptr_next,Ptr_tmp;
NodePtr nodePtr_tmp;
int size;
if ((file_inPtr=fopen("file_data.txt","r"))==NULL) /* 打开文件出错操作 */
{ perror("\nFile open error!");
exit(2);
}
base=(NodePtr)malloc(sizeof(Node)); /* 分配地址给base，链表的头地址 */
base->next=NULL; /* 头地址的定义 */
rewind(file_inPtr); /* 反绕文档，把指针指向文档的起始地址 */
Ptr_tmp=(NodePtr)malloc(sizeof(Node)); /* 注意要分配地址啊 */
if ((size=fread(Ptr_tmp,sizeof(Node),1,file_inPtr))!=1) /* 读文件 */
{ perror("fread error!");
exit(3);
}
Ptr_next=(NodePtr)malloc(sizeof(Node)); /* 对基址后第一个节点的操作 */
base->next=Ptr_next;
Ptr_next->value=Ptr_tmp->value;
Ptr_next->weight=Ptr_tmp->weight;
Ptr_next->next=NULL;
Ptr_next->lchild=NULL;
Ptr_next->rchild=NULL;
Ptr_next->parent=NULL;
while(Ptr_tmp->next!=NULL) /* 循环操作以后的节点，直到结束 */
{ if ((size=fread(Ptr_tmp,sizeof(Node),1,file_inPtr))!=1)
{ perror("fread error!");
exit(3);
}
nodePtr_tmp=(NodePtr)malloc(sizeof(Node));
nodePtr_tmp->value=Ptr_tmp->value;
nodePtr_tmp->weight=Ptr_tmp->weight;
nodePtr_tmp->lchild=NULL;
nodePtr_tmp->rchild=NULL;
nodePtr_tmp->parent=NULL;
Ptr_next=base; /* 进行插入排序 */
while(Ptr_next->next!=NULL) /* 很关键，确定插入点 */
{ if (nodePtr_tmp->weight next->weight)
break;
else
Ptr_next=Ptr_next->next;
}
nodePtr_tmp->next=Ptr_next->next; /* 排序后插入节点 */
Ptr_next->next=nodePtr_tmp;
}
fclose(file_inPtr); /* 关闭文件 */
return (base);
}
void print(NodePtr base) /* 打印 */
{ NodePtr p_tmp;
int sum=0,total=0;
p_tmp=base->next;
while(p_tmp!=NULL)
{ total++;
sum+=p_tmp->weight;
printf("\n");
printf("value=%d,weight=%d",p_tmp-> value,p_tmp-> weight);
p_tmp=p_tmp->next;
}
printf("\nsum=%d,total=%d",sum,total);
return;
}
void printcode(CodePtr base)
{ CodePtr p_tmp;
int total=0;
p_tmp=base->next;
while(p_tmp!=NULL)
{ total++;
printf("\n");
printf("value=%d,codes=%s",p_tmp->value,p_tmp->huffmancodes);
p_tmp=p_tmp->next;
}
printf("\ntotal=%d",total);
return;
}
void printreal(RealPtr base)
{ RealPtr p_tmp;
int i,total=0;
p_tmp=base->next;
while(p_tmp!=NULL)
{ total++;
printf("\n");
printf("value=%d,codes=",p_tmp->value);
for (i=0;irealcode>=0)
printf("%d",p_tmp->realcode);
p_tmp=p_tmp->next;
}
printf("\ntotal=%d",total);
return;
}
NodePtr hufftree(NodePtr base) /* 构造huffman tree */
{ NodePtr nodePtr_tmp1,nodePtr_tmp2;
NodePtr treebase,treefirst,treesecond;
treebase=NULL; /* 初始化基址 */
nodePtr_tmp1=base->next; /* 待造树的数据存储在base后的链表里 */
while(nodePtr_tmp1->next!=NULL) /* 造树 */
{ treebase=(NodePtr)malloc(sizeof(Node)); /* 不停的构造parent和lchild，rchild */
treefirst=(NodePtr)malloc(sizeof(Node));
treesecond=(NodePtr)malloc(sizeof(Node));
treefirst->value=nodePtr_tmp1->value; /* 对两者中的小者存放在lchild */
treefirst->weight=nodePtr_tmp1->weight;
treefirst->next=NULL;
treefirst->lchild=nodePtr_tmp1->lchild;
treefirst->rchild=nodePtr_tmp1->rchild;
treefirst->parent=treebase;
treesecond->value=nodePtr_tmp1->next->value; /* 对两者中的大者存放在rchild */
treesecond->weight=nodePtr_tmp1->next->weight;
treesecond->next=NULL;
treesecond->lchild=nodePtr_tmp1->next->lchild;
treesecond->rchild=nodePtr_tmp1->next->rchild;
treesecond->parent=treebase;
treebase->value=-33; /* treebase存放parent，并且要排序插入到前面的列表中以待重构树 */
treebase->weight=treefirst->weight+treesecond->weight;
treebase->lchild=treefirst;
treebase->rchild=treesecond;
treebase->parent=NULL;
nodePtr_tmp2=base; /* 排序插入parent */
while(nodePtr_tmp2->next!=NULL)
{ if (treebase->weight next->weight)
break;
else
nodePtr_tmp2=nodePtr_tmp2->next;
}
treebase->next=nodePtr_tmp2->next;
nodePtr_tmp2->next=treebase;
nodePtr_tmp1=nodePtr_tmp1->next->next;
}
#ifdef DEBUG
print(base); /* 打印出与前面不同的base链表，因为在构树过程中插入了parent */
printf("\n");
#endif
return (treebase);
}
CodePtr huffcode(NodePtr treebase) /* huffman一次编码 */
{ CodePtr codebase;
char *code_tmp; /* 存放临时的编码值，这里很关键，也很容易出错 */
code_tmp=(char *)malloc(SCALE*sizeof(char));
codebase=(CodePtr)malloc(sizeof(Code));
codebase->next=NULL;
PreOrderTrave(treebase,codebase,code_tmp,NULL); /* 实际上就是先序遍历huffman tree */
free(code_tmp);
return (codebase);
}
void setchar_l(char *code_tmp) /* 左走函数 */
{ strcat(code_tmp,"0");
#ifdef DEBUG
printf("\nturn left!");
#endif
return;
}
void setchar_r(char *code_tmp) /* 右走函数 */
{ strcat(code_tmp,"1");
#ifdef DEBUG
printf("\nturn right!");
#endif
return;
}
int PreOrderTrave(NodePtr treebase,CodePtr codebase,char *code_tmp,void (*setchar)(char *))
{ CodePtr codePtr_next; /* 先序遍历huffman tree */
int i;
if (treebase!=NULL) /* 先判断root */
{/* printf("\n@@value=%d,@@weight=%d",treebase->value,treebase->weight);*/
if (treebase->parent!=NULL) /* 左右走分别调用相应的函数 */
setchar(code_tmp);
if (treebase->value < 1000 && treebase->value >= -1) /* 找到叶子节点的操作 */
{ codePtr_next=(CodePtr)malloc(sizeof(Code));
codePtr_next->huffmancodes=(char *)malloc(SCALE*sizeof(char));
codePtr_next->value=treebase->value;
for(i=0;ihuffmancodes=*(code_tmp+i);
codePtr_next->next=codebase->next;
codebase->next=codePtr_next;
/* printf ("\n%c(%d) turns to %s",codePtr_next->value,codePtr_next->value,codePtr_next->huffmancodes);*/
}
if(PreOrderTrave(treebase->lchild,codebase,code_tmp,setchar_l)==1) /* 左走 */
if(PreOrderTrave(treebase->rchild,codebase,code_tmp,setchar_r)==1) /* 右走 */
{/* printf("\ngo back!");*/
delchar(code_tmp); /* 回溯时删除字符串最后的一个字符 */
return 1;
}
perror("\nPreordertaver error!"); /* 出错控制 */
exit(1);
}
else /* 左右都不能走了，也就是从叶子节点回溯 */
{/* printf("\non the end and go back!");*/
return 1;
}
}
void delchar(char *code_tmp) /* 删除最后字符，有两种方法，下面都给出 */
{/* while(*(code_tmp)!='\0')
code_tmp++;*/
int i;
i=strlen(code_tmp);
*(code_tmp+i-1)=*(code_tmp+i);
/* printf("\n%s",code_tmp);*/
return;
}
void putout(CodePtr codebase) /* 写出到文件 */
{ FILE *file_outPtr;
CodePtr Ptr_tmp;
if ((file_outPtr=fopen("code_data.txt","w"))==NULL) /* 打开文件出错操作 */
{ perror("\nFile open error!");
exit(4);
}
Ptr_tmp=codebase->next; /* 初始化以控制循环 */
while(Ptr_tmp!=NULL)
{
if (fwrite(Ptr_tmp,sizeof(Code),1,file_outPtr)==0) /* 写出错操作 */
{ perror("\nfwrite error!");
exit(5);
}
Ptr_tmp=Ptr_tmp->next; /* 逐个写进文件 */
}
// fclose(file_outPtr);
printf("\nWrite ok!");
return;
}
RealPtr compresscode(CodePtr codebase)
{ RealPtr realbase,real_next;
CodePtr code_tmp;
int i;
realbase=(RealPtr)malloc(sizeof(Real)); /* 这个构造链表和前面相似 */
realbase->next=NULL;
code_tmp=codebase->next;
while (code_tmp!=NULL)
{ real_next=(RealPtr)malloc(sizeof(Real));
real_next->value=code_tmp->value;
for(i=0;irealcode=-1;
for(i=0;ihuffmancodes);i++) /* 存储%d的1,0,而不是字符 */
real_next->realcode=*(code_tmp->huffmancodes+i)-48; /* 就是减48 */
real_next->next=realbase->next;
realbase->next=real_next;
code_tmp=code_tmp->next;
}
return (realbase);
}
int replacecode(RealPtr realbase,char *pathname) /* 采用unbufferI/O写，我以为是写的位流，结果怎么还是字符流啊？ */
{ RealPtr real_next; /* 这里有谁指明道路，请联系wirlfly@xplore.cn */
FILE *file_inPtr;
char code_tmp;
int filedes;
int i=0;
char buf[0];
if ((file_inPtr=fopen(pathname,"r"))==NULL) /* 这里是非ANSI C部分的内容，在WIN机器下请注释掉这个函数 */
{ perror("\nFile open error!");
exit(6);
}
if ((filedes=open("test_replace.txt",O_WRONLY|O_CREAT|O_TRUNC|O_APPEND,S_IRUSR|S_IWUSR|S_IRGRP|S_IWGRP|S_IROTH))next;
while (real_next!=NULL)
{ if (code_tmp==real_next->value)
{ for (i=0;irealcode >= 0)
{ buf[0]=real_next->realcode;
if (write(filedes,buf,1)!=1)
{ perror("\nFile unbuffered write error!");
exit(8);
}
break;
}
break;
}
else
real_next=real_next->next;
}
}
return 1; /* 总算完了，呵呵，谢谢看完啦，GOOD LUCK！ */
}
初步瞄了一眼,存在很多的内存泄漏.呵呵,以前写的代码只知道把自己想的写下来,没有顾虑其他非常重要的东西.呵呵,幼稚.如果需要看代码实现的结果,可以查看原帖.
Generated by Bo-blog 2.0.3 sp1 |
评分
-
1
查看全部评分
-
|
发表于 2007-6-8 01:05
提升卡
变色卡
显身卡
发表于 2007-6-8 10:45
楼主