Huffman树编码解码代码,C代码库,德仔网

代码语言
代码分类
【C】 Huffman树编码解码
作者:ackHD / 发布于2014/12/29/ 480

	#include "string.h"
	#include "stdlib.h"
	#include "stdio.h"
	struct Number
	{
	 int n;
	 Number *next;
	};
	struct Word
	{
	 char word;
	 int count;
	 Word *next,*lchild,*rchild,*parent;
	 int way;//0是左分支，1是右
	 int flag;//是否为子叶
	 int flag2;//是否已经被合并了
	};
	bool SearchWord(Word *words,char word)//找到这个字符就返回true
	{
	 Word t;
	 while(words!=NULL)
	 {
	 if(word==words->word)
	 {
	 words->count++;
	 return true;
	 }
	 words=words->next;
	 }
	 return false;
	}
	Word* SearchWord2(Word *words,char word)//找到这个字符在树上的节点
	{
	 Word t;
	 while(words!=NULL)
	 {
	 if(word==words->word)
	 {
	 return words;
	 }
	 words=words->next;
	 }
	 return NULL;
	}
	void AddWord(char s[],Word *words)
	{
	 int i=1;
	 Word *t;
	 while(s[i]!='\0')
	 {
	 if(SearchWord(words,s[i]))//如果树中已经有这个字符
	 {
	 i++;
	 }
	 else//创建一个新的叶子
	 {
	 t=(Word *)malloc(sizeof(Word));
	 t->word=s[i];
	 t->count=1;
	 t->flag=0;
	 t->flag2=0;
	 t->next=words->next;
	 words->next=t;
	 i++;
	 }
	 }
	}
	void PrintCode(char s[],Word *words,Word *HEAD)
	{
	 int i=0;
	 Word *t;
	 Number *Head,*x;
	 Head=NULL;
	 while(s[i]!='\0')
	 {
	 t=NULL;
	 t=SearchWord2(words,s[i]);
	 if(t!=NULL)
	 {
	 i++;//建一个栈存放每个字符的Huffman编码，实现倒序输出
	 Head=NULL;
	 while(t!=NULL)
	 {
	 Number *next=(Number*)malloc(sizeof(Number));
	 next->n=t->way;
	 next->next=Head;
	 Head=next;
	 t=t->parent;
	 if(t->parent==NULL)
	 {
	 break;
	 }
	 }
	 while(Head!=NULL)
	 {
	 printf("%d",Head->n);
	 x=Head;
	 Head=Head->next;
	 free(x);
	 }
	 }
	
	 }
	}
	bool FindFlag(Word *words)//判断树的所有节点是否全部都并起来了
	{
	 while(words!=NULL)
	 {
	 if(words->flag2==0)
	 {return true;}
	 words=words->next;
	 }
	 return false;
	}
	Word* FindSmall(Word *words)//找树中剩下的没有被并起来的最小节点
	{
	 Word *w=words;
	 Word *last;
	 Word *t=NULL;
	 while(w!=NULL)
	 {
	 if(w->flag2==0)
	 {
	 t=w;
	 break;
	 }
	 w=w->next;
	 }
	 if(t!=NULL)
	 {
	 while(words!=NULL)
	 {
	 if((words->count<t->count)&&words->flag2==0)
	 {
	 t=words;
	 }
	 words=words->next;
	 }
	 }
	 if(t!=NULL)
	 {
	 t->flag2=1;
	 }
	 return t;
	}
	Word* BulidTree(Word *words)//建立树
	{
	 Word *a,*b;
	 Word *t=NULL;
	 while(FindFlag(words))
	 {
	 a=FindSmall(words);
	 b=FindSmall(words);
	 if(a==NULL||b==NULL)
	 {break;}
	 t=(Word*)malloc(sizeof(Word));
	 a->parent=t;
	 b->parent=t;
	 a->way=0;
	 b->way=1;
	 t->parent=NULL;
	 t->lchild=a;
	 t->rchild=b;
	 t->count=a->count+b->count;
	 t->flag=1;
	 t->flag2=0;
	 t->next=words->next;
	 words->next=t;
	 }
	 return t;
	}
	void PrintWords(Word *Head)//根据输入的Huffman编码输出字符
	{
	 Word *p=Head;
	 char t;
	 getchar();
	 scanf("%c",&t);
	 while(t!='\n')
	 {
	 while(p->flag!=0&&t!='/n')
	 {
	 if(t==48)
	 {
	 p=p->lchild;
	 }
	 else if(t==49)
	 {
	 p=p->rchild;
	 }
	 else{break;}
	 scanf("%c",&t);
	 }
	 if(p->flag==0)
	 {printf("%c",p->word);}
	 p=Head;
	
	 }
	}
	void PrintCode2(Word *words,Word *Head)
	{
	 char t[2];t[1]='\0';
	 while(words!=NULL)
	 {
	 if(words->word<=127&&words->word>=0)
	 {
	 t[0]=words->word;
	 printf("%c : ",t[0]);
	 PrintCode(t,words,Head);
	 printf("\n");
	 }
	 words=words->next;
	 }
	}
	void main()
	{
	 char sentense[99999];//例句长度不超过99999字节
	 Word t;
	 t.flag=0;//初始化首节点
	 t.flag2=0;
	 t.next=NULL;
	 printf("请输入例句，不能超过99999个字符\n");//长度可以适当加长一点，99999测试值
	 gets(sentense);
	 Word *words=&t;
	 t.word=sentense[0];t.count=1;
	 AddWord(sentense,words);
	 Word *Head=BulidTree(words);
	 printf("Have built the HuffmanTree\n");
	 PrintCode2(words,Head);
	 printf("Enter what you want to change hahahahaha^,^\n");
	 getchar();
	 scanf("%s",sentense);
	 PrintCode(sentense,words,Head);
	 printf("\nEnter Huffman Code\n");
	 PrintWords(Head);
	 printf("\nEND\n");
	}
试试其它关键字
　Huffman　
同语言下
可能有用的
ackHD贡献的其它代码(1)
.Huffman树编码解码