主题:救命呀!!请问谁会编写哈夫曼编解码
匆匆过客
[专家分:0] 发布于 2003-10-30 14:47:00
谁会哈夫曼编码解码,请赐教,多谢,多谢。
回复列表 (共8个回复)
沙发
new2999 [专家分:240] 发布于 2003-10-30 15:32:00
我可以编写。你做什么用?
板凳
甲乙丙丁 [专家分:500] 发布于 2003-10-30 20:18:00
#include<stdio.h>
#include<stdlib.h>
#define MAXLEN 100
/*///////////////////////////////////////////////////////////////////////////////*/
typedef struct Huffmantree {
char ch;
int weight,mark;
struct Huffmantree *parent,*lchild,*rchild,*next;
}Hftree,*linktree;
/*///////////////////////////////////////////////////////////////////////////////*/
/*整理输入的字符串,合并相同的项,并求出每个字符在数组中出现的次数 */
linktree tidycharacter(char character[])
{
int i=0;
linktree tree,ptr,beforeptr,node;
tree=(linktree)malloc(sizeof(Hftree));/*创建单链表的头结点*/
if(!tree)return NULL;
tree->next=NULL;
for(i=0;character[i]!='\0'&&character[i]!='\n';i++) {
ptr=tree;
beforeptr=tree;
node=(linktree)malloc(sizeof(Hftree));
if(!node)return NULL;
node->next=NULL;
node->parent=NULL;
node->lchild=NULL;
node->rchild=NULL;
node->mark=0;
node->ch=character[i];
node->weight=1;
if(tree->next==NULL)
tree->next=node;
else {
ptr=tree->next;
while(ptr&&ptr->ch!=node->ch) {/*将指针移至链表尾*/
ptr=ptr->next;
beforeptr=beforeptr->next;
}
if(ptr&&ptr->ch==node->ch) {/*如果链表中某结点的字符与新结点的字符相同*/
/*将该结点的权加一*/
ptr->weight=ptr->weight+1;
free(node);
}
else {/*将新结点插入链表后*/
node->next=beforeptr->next;
beforeptr->next=node;
}
}
}
return tree;
}
/*///////////////////////////////////////////////////////////////////////////////*/
/*将整理完的字符串按出现次数从小到大的顺序排列 */
linktree taxisnode(linktree tree)
{
linktree head,ph,pt,beforeph;
head=(linktree)malloc(sizeof(Hftree));/*创建新链表的头结点*/
if(!head)return NULL;
head->next=NULL;
ph=head;
beforeph=head;
while(tree->next) {
pt=tree->next;/*取被操作链表的首元结点*/
tree->next=pt->next;
pt->next=NULL;
ph=head->next;
beforeph=head;
if(head->next==NULL)
head->next=pt;/*创建当前操作链表首元结点*/
else {
while(ph&&ph->weight<pt->weight) {/*将被操作结点插入相应位置*/
ph=ph->next;
beforeph=beforeph->next;
}
pt->next=beforeph->next;
beforeph->next=pt;
}
}
free(tree);
return head;
}
/*///////////////////////////////////////////////////////////////////////////////*/
/*用排完序的字符串建立霍夫曼树 */
linktree createHftree(linktree tree)
{
linktree p,q,newnode,beforep;
for(p=tree->next,q=p->next;p!=NULL&&q!=NULL;p=tree->next,q=p->next) {
tree->next=q->next;
q->next=NULL;
p->next=NULL;
newnode=(linktree)malloc(sizeof(Hftree));/*申请新结点作为霍夫曼树的中间结点*/
if(!newnode)return NULL;
newnode->next=NULL;
newnode->mark=0;
newnode->lchild=p;/*取链表头结点后的两个结点作为新结点的左、右儿子*/
newnode->rchild=q;
p->parent=newnode;
q->parent=newnode;
newnode->weight=p->weight+q->weight;
p=tree->next;
beforep=tree;
if(p!=NULL&&p->weight>=newnode->weight) {/*将新结点插入原链表的相应位置*/
newnode->next=beforep->next;
beforep->next=newnode;
}
else {
while(p!=NULL&&p->weight<newnode->weight) {
p=p->next;
beforep=beforep->next;
}
newnode->next=beforep->next;
beforep->next=newnode;
}
}
return (tree->next);
}
/*///////////////////////////////////////////////////////////////////////////////*/
/*对霍夫曼树进行编码 */
void Huffmancoding(linktree tree)
{
int index=0;
char *code;
linktree ptr=tree;
code=(char *)malloc(10*sizeof(char));/*此数组用于统计霍夫曼编码*/
printf("字符以及它的相应权数---------霍夫曼编码\n\n");
if(ptr==NULL) {
printf("霍夫曼树是空的!\n");
exit(0);
}
else {
while(ptr->lchild&&ptr->rchild&&ptr->mark==0) {
while(ptr->lchild&&ptr->lchild->mark==0) {
code[index++]='0';
ptr=ptr->lchild;
if(!ptr->lchild&&!ptr->rchild) {
ptr->mark=1;
code[index]='\0';
printf("\tw[%c]=%d\t\t\t",ptr->ch,ptr->weight);
for(index=0;code[index]!='\0';index++)
printf("%c",code[index]);
printf("\n");
ptr=tree;
index=0;
}
}
if(ptr->rchild&&ptr->rchild->mark==0) {
ptr=ptr->rchild;
code[index++]='1';
}
if(!ptr->lchild&&!ptr->rchild) {
ptr->mark=1;
code[index++]='\0';
printf("\tw[%c]=%d\t\t\t",ptr->ch,ptr->weight);
for(index=0;code[index]!='\0';index++)
printf("%c",code[index]);
printf("\n");
ptr=tree;
index=0;
}
if(ptr->lchild->mark==1&&ptr->rchild->mark==1)
{
ptr->mark=1;
ptr=tree;
index=0;
}
}
}
printf("\n");
free(code);
}
/*///////////////////////////////////////////////////////////////////////////////*/
/*解码 */
void decode(linktree tree,char code[])
{
int i=0,j=0;
char *char0_1;
linktree ptr=tree;
char0_1=(char *)malloc(10*sizeof(char));/*此数组用于统计输入的0、1序列*/
printf("霍夫曼编码-----相应字符\n\n");
for(j=0,ptr=tree;code[i]!='\0'&&ptr->lchild&&ptr->rchild;j=0,ptr=tree) {
for(j=0;code[i]!='\0'&&ptr->lchild&&ptr->rchild;j++,i++) {
if(code[i]=='0') {
ptr=ptr->lchild;
char0_1[j]='0';
}
if(code[i]=='1') {
ptr=ptr->rchild;
char0_1[j]='1';
}
}
if(!ptr->lchild&&!ptr->rchild) {
char0_1[j]='\0';
for(j=0;char0_1[j]!='\0';j++)
printf("%c",char0_1[j]);
printf("\t\t%c\n",ptr->ch);
}
if(code[i]=='\0'&&ptr->lchild&&ptr->rchild) {
char0_1[j]='\0';
printf("没有与最后的几个0、1序列:%s相匹配的字符!\n",char0_1);
return;
}
}
free(char0_1);
}
/*///////////////////////////////////////////////////////////////////////////////*/
/*释放霍夫曼树所占用的空间*/
void deletenode(linktree tree)
{
linktree ptr=tree;
if(ptr) {
deletenode(ptr->lchild);
deletenode(ptr->rchild);
free(ptr);
}
}
/*///////////////////////////////////////////////////////////////////////////////*/
void main()
{
char character[MAXLEN],code[MAXLEN];
linktree temp,ht,htree,ptr=NULL;
printf("一、编码:\n请输入要测试的字符串:\n\n");
scanf("%s",character);
printf("\n");
temp=tidycharacter(character);
ht=taxisnode(temp);
htree=createHftree(ht);
Huffmancoding(htree);
printf("二、解码:\n请输入用于解码的0、1序列:\n\n");
scanf("%s",code);
printf("\n");
decode(htree,code);
deletenode(htree);
}
霍夫曼编解码全在里面了:)
3 楼
new2999 [专家分:240] 发布于 2003-10-31 10:26:00
给你看一个简单的版本,用数组实现的。
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>
#define N 10 //要编码的字符个数
typedef char KeyType; // 被编码字符的类型,假定为字符
typedef enum{ NONE, LEFT_CHILD, RIGHT_CHILD } WHICH ; //定义节点是双亲的左孩子还是右孩子。
// NONE表示未知
typedef struct node
{
KeyType key;
int weight; //权重或者出现的概率
int parent; //我们用数组存储树,这里用下标标是双亲。-1表示没有双亲。
WHICH sign; //说明该节点使是左孩子还是右孩子
char *code; //对编码采用01串存储,以便输出;也可以在设定一个int,来存储编码
//这样解码要快,解码程序比较简单,这里就不写了。
} HuffmanNode;
//定义一个HUFFMAN树类型,数组表示,长度是N+N-1 = 2N-1
typedef HuffmanNode HuffmanTree[N+N-1];
//为了测试方便,这里用随机数的方法初始化一个HUFFMAN树。
void init( HuffmanTree T)
{
int i;
char j='A';
//初始化存储关键字的部分。
for(i=0; i<N; i++)
{
T[i].key = j++;
T[i].parent = -1 ; //-1表示没有双亲。
T[i].sign=NONE;
T[i].weight = (rand() % 100); //暂不考虑总的概率和为1,用权值代之
}
for(;i<N+N-1; i++)
{
T[i].parent = -1;
T[i].sign=NONE;
T[i].weight=0;
}
}
//从HT[0]..HT[N+i-1]中找出最小,次小
void SelectMin(HuffmanTree T, int start, int end, int *pmin1, int *pmin2)
{
int i;
int min1=INT_MAX;//最小
int min2; //次小。
//找出最小
for(i=start; i<=end; i++)
{
if( T[i].sign == NONE && T[i].weight < min1)
{
*pmin1 = i;
min1 = T[i].weight;
}
}
//找次小
min2=INT_MAX;
for(i=start; i<=end; i++)
{
if( (*pmin1 != i) && (T[i].sign == NONE) && (T[i].weight < min2) )
{
*pmin2 = i;
min2 = T[i].weight;
}
}
}
// 进行HUFFMAN树构造
void CreateHuffmanTree(HuffmanTree T)
{
int i;
int min1, min2; //记录权值最小,次小的两个节点下标
for(i=N; i<2*N-1; i++)
{
SelectMin(T, 0, i-1, &min1, &min2); //从HT[0]..HT[i-1]中找出最小,次小
T[i].weight = T[min1].weight + T[min2].weight;
T[min1].parent = i;
T[min1].sign = LEFT_CHILD;
T[min2].parent = i;
T[min2].sign = RIGHT_CHILD;
}
}
//生成将每个节点的编码,按01字符串的方式生成。
void EncodeHuffman( HuffmanTree T)
{
char temp[N]; //临时串,树高会大于N。
int s;
int i, p;
temp[N-1]='\0';
//左孩子0,右孩子1
for(i=0; i<N; i++)
{
p = i;
s = N-1;
while(T[p].parent != -1)
{
if( T[p].sign == LEFT_CHILD )
temp[--s] = '0';
else if(T[p].sign == RIGHT_CHILD)
temp[--s] = '1';
p = T[p].parent;
}
T[i].code = (char*)malloc((N-s)*sizeof(char));
strcpy(T[i].code, temp+s); //把编码复制道接点域中。
}
}
//输出每个节点的编码情况。
void ShowCode( HuffmanTree T)
{
int i;
printf(" Key Code weight\n---------------\n");
for(i=0; i<N; i++)
printf("%3c%8s%8d\n",T[i].key,T[i].code,T[i].weight);
}
int main()
{
HuffmanTree T;
init(T); //初始化
CreateHuffmanTree(T);
EncodeHuffman(T);
ShowCode(T);
return 0;
}
4 楼
匆匆过客 [专家分:0] 发布于 2003-11-04 10:11:00
多谢各位帮忙,多谢,多谢!
5 楼
l83910 [专家分:0] 发布于 2004-11-08 15:56:00
请问如何将txt文件内的数据输入再编写哈夫曼编码啊?
例如txt文件是这样的
7
1
0.2 0.19 0.18 0.17 0.15 0.10 0.01
7是信源符号数,1是编码序列长度
求求各位大侠帮帮忙
6 楼
l83910 [专家分:0] 发布于 2004-11-08 16:57:00
请问怎样输入txt文件入面的数据再编哈夫曼编码啊?
例如一个txt文件
7
1
0.20 0.19 0.18 0.17 0.15 0.10 0.01
7是信源符号数,1是编码序列长度
求求各位大侠帮帮忙啦
7 楼
pikeweike [专家分:0] 发布于 2006-06-12 19:29:00
谢谢!!
8 楼
救世猪猪 [专家分:560] 发布于 2006-11-09 23:03:00
现在都忘了……
我来回复