哈夫曼编码

计算哈夫曼编码~

/* algo6-1.c 求哈夫曼编码。实现算法6.12的程序 */
//------------------- 公用的常量和类型 ----------------------------
#include<stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
//函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define UINT_MAX 1000
typedef int Status;

/* c6-7.h 哈夫曼树和哈夫曼编码的存储表示 */
typedef struct HTNode
{
char leaf;
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; /* 动态分配数组存储哈夫曼编码表 */

typedef char **HuffmanCode; /* 动态分配数组存储哈夫曼编码表 */
typedef struct Node
{
char leaf;
unsigned int weight;
struct Node * next;
}LeafNode,*LeafLink;

typedef struct
{
LeafLink head;
unsigned len;
}LeafLinkList;

int min1(HuffmanTree t,int i)
{ /* 函数void select()调用 */
int j,flag;
unsigned int k=UINT_MAX; /* 取k为不小于可能的值 */
for(j=1;j<=i;j++)
if(t[j].weight<k&&t[j].parent==0)
k=t[j].weight,flag=j;
t[flag].parent=1;
return flag;
}

void select(HuffmanTree t,int i,int *s1,int *s2)
{ /* s1为最小的两个值中序号小的那个 */
int j;
*s1=min1(t,i);
*s2=min1(t,i);
if(*s1>*s2)
{
j=*s1;
*s1=*s2;
*s2=j;
}
}

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC, LeafLinkList L) /* 算法6.12 */
{ /* w存放n个字符的权值(权值均需大于0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC*/
int m,i,s1,s2,start;
int n=L.len;
unsigned c,f;
LeafLink ptr;
HuffmanTree p;
char *cd;
if(n<=1)
return;
m=2*n-1;
printf("表长为%d\t哈夫曼树含节点数为%d\n",n,m);
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /* 0号单元未用 */
ptr=L.head->next;
for(p=HT+1,i=1;i<=n;++i,++p,ptr=ptr->next)
{
(*p).leaf=ptr->leaf;
printf("%d\t",(*p).leaf);
(*p).weight=ptr->weight;
printf("%d\n",(*p).weight);
(*p).parent=0;
(*p).lchild=0;
(*p).rchild=0;
}
for(;i<=m;++i,++p)
{
(*p).parent=0;
(*p).leaf=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=HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
/* 从叶子到根逆向求每个字符的哈夫曼编码 */
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
/* 分配n个字符编码的头指针向量([0]不用) */
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));
/* 为第i个字符编码分配空间 */
strcpy(HC[i],&cd[start]); /* 从cd复制编码(串)到HC */
}
free(cd); /* 释放工作空间 */
for(i=1;i<=n;i++)
{
printf("%c编码为%s:\n",HT[i].leaf,HC[i]);
}
}

void InitLeafList(LeafLinkList &L)
{
L.head=(LeafLink)malloc(sizeof(LeafLink));
L.head->next=NULL;
L.len=0;
}
void PrintList(LeafLinkList L)
{
LeafLink p;
p=L.head->next;
printf("打印链表\n");
printf("表长为%d\n",L.len);
while(p!=NULL)
{
printf("%c or %d,%u\t",p->leaf,p->leaf,p->weight);
printf("打印一个节点\n");
p=p->next;
}
printf("打印结束\n");
printf("\n");
}

void EnLeafList(LeafLinkList &L,char ch)
{
LeafLink p,pre,temp;
int flag=0;
pre=p=L.head;
printf("%d即为%c******\n\n",ch,ch);
if(p->next==NULL) //p->next=NULL则为第一次插入操作
{
printf("第一次插入\n");
temp=(LeafLink)malloc(sizeof(LeafNode));
temp->leaf=ch;
temp->weight=1;
temp->next=NULL;
p->next=temp;
L.len++;
}

else
{

p=p->next;
while(p!=NULL)
{

if(ch==p->leaf)
{
p->weight++;
printf("加权\n");
p=NULL;
flag=1;
} //权重加一
else if(ch<p->leaf) //插入
{
printf("插入A\n");
temp=(LeafLink)malloc(sizeof(LeafNode));
temp->leaf=ch;
temp->weight=1;
temp->next=p;
pre->next=temp;
L.len++;
flag=1;
p=NULL;
}
else //继续寻找插入点
{
pre=p;
p=p->next;
}
}

if(p==NULL&&flag!=1) //若p=NULL则插到链尾
{
printf("插入B\n");
temp=(LeafLink)malloc(sizeof(LeafNode));
temp->leaf=ch;
temp->weight=1;
temp->next=NULL;
pre->next=temp;
L.len++;
}
}

}
void EnCoding()
{
FILE *fp,*fr,*fc;
HuffmanTree HT;
HuffmanCode HC;
int i,n;
LeafLinkList L;
InitLeafList(L);
char filename[15];
char ch;
printf("请输入文件名:\n ");
scanf("%s",filename);
if( !(fp=fopen(filename,"r")) )
{
printf("打开文件失败，请输入正确的文件名!! ");
exit(0);
}
ch=getchar(); //接收执行scanf语句时最后输入的回车符
printf("文件已经打开\n");
while(!feof(fp))
{

ch=fgetc(fp);
if(ch==-1)
{
printf("结束统计\n");
}
else
{
EnLeafList(L,ch);
}
}
PrintList(L);
HuffmanCoding(HT,HC, L);
n=L.len;
for(i=1;i<=n;i++)
{
puts(HC[i]);
}
char TreeName[15];
printf("把哈夫曼树存入文件，请输入文件名:\n ");
scanf("%s",TreeName);
if( !(fr=fopen(TreeName,"wb")) )
{
printf("打开文件失败，请输入正确的文件名!! ");
exit(0);
}
ch=getchar(); //接收执行scanf语句时最后输入的回车符
printf("文件已经打开\n");
//把哈夫曼树存入文件
printf("%d\n",n);
printf("把树的长度先存入\n");
putw(n,fr); //把树的长度先存入
for(i=1;i<=2*n-1;i++)
if(fwrite(&HT[i],sizeof(struct HTNode),1,fr)!=1)
printf("文件写入出错\n");
fclose(fr);

printf("打印原来的树\n");
for(i=1;i<=2*n-1;i++)
printf("%c %u %u %u %u\n",HT[i].leaf ,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild );
fclose(fr);

printf("把编码结果存入文件，请输入文件名:\n ");
char CodeFileName[15];
scanf("%s",CodeFileName);
if( !(fc=fopen(CodeFileName,"wb")) )
{
printf("打开文件失败，请输入正确的文件名!! ");
exit(0);
}
ch=getchar(); //接收执行scanf语句时最后输入的回车符

printf("待编码的文件位置指针重新指向开始位置\n");
printf("对待编码文件进行编码，编码同步显示，并将结果存入指定的文件\n");
rewind(fp);
while(!feof(fp))
{

ch=fgetc(fp);
printf("%c\n",ch);
if(ch==-1)
{
printf("结束编码\n");
}
else
{
for(int tap=0,i=1;tap==0&&i<=n;) //查找，该叶子对应的编码串
{
if(ch==HT[i].leaf) //找到，打印出对应的编码，并存入文件
{
printf("%s\n",HC[i]);
fputs(HC[i],fc); //将编码字符串存入文件

tap=1;
}
else
{
i++;
}
}
}
}
fclose(fp); //关闭文件
fclose(fc); //关闭文件
}
int decode(FILE *fc,HuffmanTree HT,int n)
{
while(!feof(fc))
{
char ch=fgetc(fc);
if(ch=='0')
{
n=HT[n].lchild;
if(HT[n].leaf!=0)
{
printf("%c",HT[n].leaf);
return OK;
}
else
{
decode(fc,HT,n);
return OK;
}
}
else if(ch=='1')
{

n=HT[n].rchild;
if(HT[n].leaf!=0)
{
printf("%c",HT[n].leaf);
return OK;
}
else
{
decode(fc,HT,n);
return OK;
}
}
else return OK;
}
return ERROR;
}

void Decoding() //解码文件，并将结果显示出来
{
FILE *fc,*fr;
char CodeFileName[15],ch,TreeName[15];
int i;
printf("解码文件，请输入文件名(如*.dat):\n ");
scanf("%s",CodeFileName);
if( !(fc=fopen(CodeFileName,"r")) )
{
printf("打开文件失败，请输入正确的文件名!! ");
exit(0);
}
ch=getchar(); //接收执行scanf语句时最后输入的回车符
printf("存放编码结果文件已经打开\n");

//读入哈夫曼树

HuffmanTree HT;
printf("取出对应的哈夫曼树文件，请输入文件名,\n");
scanf("%s",TreeName);
if( !(fr=fopen(TreeName,"rb")) ) //打开存放哈夫曼树的文件
{
printf("打开文件失败，请输入正确的文件名!! ");
exit(0);
}
int n=getw(fr); //将叶子数目取出
printf("叶子数目%d\n",n);
HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode)); /* 然后分配空间，0号单元未用 */

for(i=1;i<=2*n-1;i++)
if(fread(&HT[i],sizeof(struct HTNode),1,fr)!=1)
printf("文件读出出错\n");
int length=2*n-1; //总长度
printf("总结点数目为：%d\n",n);
printf("该文件译码后得到的源文件为：\n");
printf("**************************************\n");
while(!feof(fc))
{
decode(fc,HT,length);
}
printf("**************************************\n");
printf("\n\n");
}

int PreOrderPrint(HuffmanTree HT,int n,int count)
{
if(HT[n].lchild)
{
for(int i=0;i<count;i++)
printf(" ");
printf("%u\n",HT[n].weight);
if( PreOrderPrint(HT,HT[n].lchild, ++count) )
if (PreOrderPrint(HT,HT[n].rchild, ++count))
return OK;
return ERROR;
}
else return OK;
}
void PrintTree()
{
//读入哈夫曼树
FILE *fr;
char TreeName[15];
HuffmanTree HT;
printf("取出对应的哈夫曼树文件(如*.dat)，请输入文件名,\n");
scanf("%s",TreeName);
if( !(fr=fopen(TreeName,"rb")) ) //打开存放哈夫曼树的文件
{
printf("打开文件失败，请输入正确的文件名!! ");
exit(0);
}
int n=getw(fr); //将叶子数目取出
printf("含叶子数%d\n",n);
HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode)); /* 然后分配空间，0号单元未用 */

for(int i=1;i<=2*n-1;i++)
if(fread(&HT[i],sizeof(struct HTNode),1,fr)!=1)
printf("文件读出出错\n");
int count=0;
n=2*n-1;
printf("总结点数目为；%d\n",n);
printf("哈夫曼树的存储形式为：\n");
for(i=1;i<=n;i++)
{
printf("%c,%u,%u,%u,%u\n",HT[i].leaf,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
}
printf("哈夫曼树的凹入表形式为：\n");
PreOrderPrint(HT,n,count);
}
void PrintCodeFile()
{
FILE *fc;
printf("打印编码后的文件，请输入文件名(如*.dat):\n ");
char CodeFileName[15];
scanf("%s",CodeFileName);

if( !(fc=fopen(CodeFileName,"r")) )
{
printf("打开文件失败，请输入正确的文件名!! ");
exit(0);
}

char ch=getchar(); //接收执行scanf语句时最后输入的回车符
printf("打印编码后的文件，打印方法一\n");
int flag=1;
while(!feof(fc))
{

ch=fgetc(fc);
if(ch==-1)
{
printf("结束打印\n");
}
else
{
printf("%c",ch);
if(flag<=49)
flag++;
else
{
flag=1;
printf("\n");
}
}
}
printf("打印编码后的文件，打印方法二\n");
rewind(fc);
char str[50];
while(!feof(fc))
{
fgets(str,51,fc);
puts(str);
}
fclose(fc); //关闭文件
}

void Initialization() //系统初始化
{
printf("**************************************\n");
printf("*编码文件请输入e\n*译码文件请输入d\n*打印编码后的文件请输入p\n*打印哈夫曼树请输入t\n*结束请输入q \n");
printf("**************************************\n");
printf("\n\n\t\t字符:\n\n\n");
printf("**************************************\n");
printf("* 输入一个字符:e,d,p,t or q *\n");
printf("**************************************\n");
}

int read(char cmd)
{
int i,flag=0;
char choice[10]={'e','E','d','D','p','P','T','t','Q','q'};
for(i=0;i<10;i++)
{
if(cmd==choice[i]) flag++;
}
if(flag==1) return FALSE;
else return TRUE;
}
void ReadCommand(char &cmd) // 读入操作命令符
{
do
{
cmd=getchar();
}
while(read(cmd));
}
void Interpret(char cmd) //解释执行操作命令
{
switch(cmd)
{
case 'e':case'E':
EnCoding();
Initialization();
break;
case 'd':case'D':
Decoding();
Initialization();
break;
case 'p':case'P':
PrintCodeFile();
Initialization();
break;
case't':case'T':
PrintTree(); // Print();
Initialization();
break;
case 'q': case'Q': exit(0);
break;
default: printf("Error\n");break;
}
}
void main() //用户驱式
{
char cmd;
Initialization(); //初始化
do
{
ReadCommand(cmd); //读入一个操作命令符
Interpret(cmd); //解释执行操作命令符
}
while(cmd!='q'&&cmd!='Q');
EnCoding();
Decoding();

}

---

六枝特区13433579736： 哈夫曼编码 - 搜狗百科？
藩溥齐斯： 哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种.Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就叫做Huffman编码(有时也称为霍夫曼编码).

六枝特区13433579736： 哈夫曼编码的编码方法怎样? ？
藩溥齐斯： 哈夫曼编码是一种编码方式,是可变字长编码(VLC)的一种.以哈夫曼树-即最优二叉树,带权路径长度最小的二叉树,经常应用于数据压缩. 在计算机信息处理中,“...

六枝特区13433579736： 如何叙述哈夫曼编码 - ？
藩溥齐斯： 哈夫曼编码 哈夫曼树可用于构造最短的不等长编码方案,具体做法如下:设需要编码的字符集合为{d1,d2,…,d¬n},它们在字符串中出现的频率为{w1, w2,…, wn},以d1,d2,…,d¬n作为叶子结点, w1, w2,…, wn¬作为叶子结点的权值,构造一颗...

六枝特区13433579736： 哈夫曼编码原理 - ？
藩溥齐斯： 霍夫曼(Huffman)编码属于码词长度可变的编码类,是霍夫曼在1952年提出的一种编码方法,即从下到上的编码方法.同其他码词长度可变的编码一样,可区别的不同码词的生成是基于不同符号出现的不同概率.生成霍夫曼编码算法基于一种称...

六枝特区13433579736： 哈夫曼编码 - ？
藩溥齐斯： //HC是一个字符串数组,HC[i]中保存的是第i字符的编码;n是haffman树的树高 HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//cd是一个临时变量,临时保存编码 cd=(char*)malloc(n*sizeof(char));cd[n-1]='\0'; // 字符串的结束符为0 (0) for(i=1;i<=...

六枝特区13433579736： 哈夫曼树编码？
藩溥齐斯： #include&lt;iostream&gt; #include&lt;string&gt;//存放输入的字符串 using namespace std; int num[27];//统计字符的个数 int main() { freopen(＂input.txt＂,＂r＂,stdin); freopen(＂output.txt＂,＂w＂,stdout); memset(num,0,sizeof(num)); string st; cin...

六枝特区13433579736： 哈夫曼编码码长怎么算 - ？
藩溥齐斯：[答案] 假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成,这8个字母在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}.(1)为这8个字母设计哈夫曼编码.(2)若用这三位二进制数(0…7)对这8个字母进行等长编码,则哈夫曼编...

六枝特区13433579736： 求哈夫曼编码,谢谢! - ？
藩溥齐斯： 完整的程序 #include #include #include #define NULL 0 typedef struct huff_code_node //存储编码的链表 { char ch; //编码对应的字符 char code[100]; //字符对应的哈夫曼码 struct huff_code_node *next; }hnode,*huff; typedef struct tree_Node //二叉...

六枝特区13433579736： 哈夫曼树 3位固定长度编码是什么? - ？
藩溥齐斯：[答案] 主可以去看看最优二叉树的编码问题.1、哈夫曼编码在数据通信中,需要将传送的文字转换成二进制的字符串,用0,1码的不同排列来表示字符.例如,需传送的报文为“AFTER DATA EAR ARE ART AREA”,这里用到的字符集为“A,E,R...