编程实现哈夫曼编码

1. c或c++ 实现 哈夫曼编码 最优字符串编码

#include <iostream>
#include <queue>
#include <vector>
#include <map>
#include <string>
using namespace std;
class Node {
public:
char c; //表示字符
int frequency; //表示该字符出现的次数或频率
Node *left;
Node *right;
Node(char _c, int f, Node *l = NULL, Node *r = NULL)
:c(_c), frequency(f), left(l), right(r) { }
bool operator<(const Node &node) const { //重载<运算法以至于在加入优先队列的时候决定如何处理结点位置
return frequency > node.frequency;
}
};
void initNode(priority_queue<Node> &q, int nodeNum) {
char c;
int frequency;
for (int i = 0; i < nodeNum; i++) {
cout << "输入字符和结点出现的次数: ";
cin >> c >> frequency;
Node node(c, frequency);
q.push(node);
}
}
void showNode(priority_queue<Node> q) {
while (!q.empty()) {
Node node = q.top(); q.pop();
cout << node.c << ", " << node.frequency << endl;
}
}
//构造哈夫曼树
void huffmanTree(priority_queue<Node> &q) {
while (q.size() != 1) {
Node *left = new Node(q.top()); q.pop();
Node *right = new Node(q.top()); q.pop();
Node node('R', left->frequency + right->frequency, left, right);
q.push(node);
}
}

// 打印哈夫曼编码
void huffmanCode(Node *root, string &prefix, map<char, string> &result) {
string m_prefix = prefix;
if (root->left == NULL)
return;
//处理左子树
prefix += "0";
//如果是叶子结点则输出,否则递归打印左子树
if (root->left->left == NULL)
result[root->left->c] = prefix;
//cout << root->left->c << ": " << prefix << endl;
else
huffmanCode(root->left, prefix, result);
//还原原来的路径,回溯
prefix = m_prefix;
//处理右子树
prefix += "1";
//如果是叶子结点，则输出, 否则递归打印右子树
if (root->right->right == NULL)
result[root->right->c] = prefix;
//cout << root->right->c << ": " << prefix << endl;
else
huffmanCode(root->right, prefix, result);
}
void testResult(map<char, string> result) {
//迭代map容器
map<char, string>::const_iterator it = result.begin();
while (it != result.end()) {
cout << it->first << ": " << it->second << endl;
++it;
}
}
int main() {
priority_queue<Node> q;
int nodeNum;
//初始化字符信息
cout << "请输入结点个数: ";
cin >> nodeNum;
initNode(q, nodeNum);
//showNode(q);
//构造哈夫曼树
huffmanTree(q);
//构造哈夫曼编码
Node root = q.top();
string prefix = "";
map<char, string> result;
huffmanCode(&root, prefix, result);
//检验结果是否正确
testResult(result);
return 0;
}

2. 哈夫曼编码的程序实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define M 100
typedef struct Fano_Node
{
char ch;
float weight;
}FanoNode[M];
typedef struct node
{
int start;
int end;
struct node *next;
}LinkQueueNode;
typedef struct
{
LinkQueueNode *front;
LinkQueueNode *rear;
}LinkQueue;
//建立队列
void EnterQueue(LinkQueue *q,int s,int e)
{
LinkQueueNode *NewNode;
//生成新节点
NewNode=(LinkQueueNode*)malloc(sizeof( LinkQueueNode ));
if(NewNode!=NULL)
{
NewNode->start=s;
NewNode->end=e;
NewNode->next=NULL;
q->rear->next=NewNode;
q->rear=NewNode;
}
else
{
printf(Error!);
exit(-1);
}
}
//按权分组
void Divide(FanoNode f,int s,int *m,int e)
{
int i;
float sum,sum1;
sum=0;
for(i=s;i<=e;i++)
sum+=f[i].weight;//
*m=s;
sum1=0;
for(i=s;i<e;i++)
{
sum1+=f[i].weight;
*m=fabs(sum-2*sum1)>fabs(sum-2*sum1-2*f[i+1].weight)?(i+1):*m;
if(*m==i) break;
}
}
void main()
{
int i,j,n,max,m,h[M];
int sta,end;
float w;
char c,fc[M][M];
FanoNode FN;
LinkQueueNode *p;
LinkQueue *Q;
//初始化队Q
Q=(LinkQueue *)malloc(sizeof(LinkQueue));
Q->front=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));
Q->rear=Q->front;
Q->front->next=NULL;
printf( ***FanoCoding*** );
printf(Please input the number of node:);
//输入信息
scanf(%d,&n);
//超过定义M,退出
if(n>=M)
{
printf(>=%d,M);
exit(-1);
}
i=1; //从第二个元素开始录入
while(i<=n)
{
printf(%d weight and node:,i);
scanf(%f %c,&FN[i].weight,&FN[i].ch);
for(j=1;j<i;j++)
{
if(FN[i].ch==FN[j].ch)//查找重复
{
printf(Same node!!! ); break;
}
}
if(i==j)
i++;
}
//排序(降序)
for(i=1;i<=n;i++)
{
max=i+1;
for(j=max;j<=n;j++)
max=FN[max].weight<FN[j].weight?j:max;
if(FN[i].weight<FN[max].weight)
{
w=FN[i].weight;
FN[i].weight=FN[max].weight;
FN[max].weight=w;
c=FN[i].ch;
FN[i].ch=FN[max].ch;
FN[max].ch=c;
}
}
for(i=1;i<=n;i++) //初始化h
h[i]=0;
EnterQueue(Q,1,n); //1和n进队
while(Q->front->next!=NULL)
{
p=Q->front->next; //出队
Q->front->next=p->next;
if(p==Q->rear)
Q->rear=Q->front;
sta=p->start;
end=p->end;
free(p);
Divide(FN,sta,&m,end); /*按权分组*/
for(i=sta;i<=m;i++)
{
fc[i][h[i]]='0';
++h[i];
}
if(sta!=m)
EnterQueue(Q,sta,m);
else
fc[sta][h[sta]]='';
for(i=m+1;i<=end;i++)
{
fc[i][h[i]]='1';
++h[i];
}
if(m==sta&&(m+1)==end)
//如果分组后首元素的下标与中间元素的相等，
//并且和最后元素的下标相差为1，则编码码字字符串结束
{
fc[m][h[m]]='';
fc[end][h[end]]='';
}
else
EnterQueue(Q,m+1,end);
}
for(i=1;i<=n;i++) /*打印编码信息*/
{
printf(%c:,FN[i].ch);
printf(%s ,fc[i]);
}
system(pause);
} #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 100
#define M 2*N-1
typedef char * HuffmanCode[2*M];//haffman编码
typedef struct
{
int weight;//权值
int parent;//父节节点
int LChild;//左子节点
int RChild;//右子节点
}HTNode,Huffman[M+1];//huffman树
typedef struct Node
{
int weight; //叶子结点的权值
char c; //叶子结点
int num; //叶子结点的二进制码的长度
}WNode,WeightNode[N];
/***产生叶子结点的字符和权值***/
void CreateWeight(char ch[],int *s,WeightNode CW,int *p)
{
int i,j,k;
int tag;
*p=0;//叶子节点个数
//统计字符出现个数,放入CW
for(i=0;ch[i]!='';i++)
{
tag=1;
for(j=0;j<i;j++)
if(ch[j]==ch[i])
{
tag=0;
break;
}
if(tag)
{
CW[++*p].c=ch[i];
CW[*p].weight=1;
for(k=i+1;ch[k]!='';k++)
if(ch[i]==ch[k])
CW[*p].weight++;//权值累加
}
}
*s=i;//字符串长度
}
/********创建HuffmanTree********/
void CreateHuffmanTree(Huffman ht,WeightNode w,int n)
{
int i,j;
int s1,s2;
//初始化哈夫曼树
for(i=1;i<=n;i++)
{
ht[i].weight =w[i].weight;
ht[i].parent=0;
ht[i].LChild=0;
ht[i].RChild=0;
}
for(i=n+1;i<=2*n-1;i++)
{
ht[i].weight=0;
ht[i].parent=0;
ht[i].LChild=0;
ht[i].RChild=0;
}
for(i=n+1;i<=2*n-1;i++)
{
for(j=1;j<=i-1;j++)
if(!ht[j].parent)
break;
s1=j; //找到第一个双亲为零的结点
for(;j<=i-1;j++)
if(!ht[j].parent)
s1=ht[s1].weight>ht[j].weight?j:s1;
ht[s1].parent=i;
ht[i].LChild=s1;
for(j=1;j<=i-1;j++)
if(!ht[j].parent)
break;
s2=j; //找到第二个双亲为零的结点
for(;j<=i-1;j++)
if(!ht[j].parent)
s2=ht[s2].weight>ht[j].weight?j:s2;
ht[s2].parent=i;
ht[i].RChild=s2;
ht[i].weight=ht[s1].weight+ht[s2].weight;//权值累加
}
}
/***********叶子结点的编码***********/
void CrtHuffmanNodeCode(Huffman ht,char ch[],HuffmanCode h,WeightNode weight,int m,int n)
{
int i,c,p,start;
char *cd;
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='';//末尾置0
for(i=1;i<=n;i++)
{
start=n-1; //cd串每次从末尾开始
c=i;
p=ht[i].parent;//p在n+1至2n-1
while(p) //沿父亲方向遍历,直到为0
{
start--;//依次向前置值
if(ht[p].LChild==c)//与左子相同,置0
cd[start]='0';
else //否则置1
cd[start]='1';
c=p;
p=ht[p].parent;
}
weight[i].num=n-start; //二进制码的长度(包含末尾0)
h[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(h[i],&cd[start]);//将二进制字符串拷贝到指针数组h中
}
free(cd);//释放cd内存
system(pause);
}
/*********所有字符的编码*********/
void CrtHuffmanCode(char ch[],HuffmanCode h,HuffmanCode hc,WeightNode weight,int n,int m)
{
int i,k;
for(i=0;i<m;i++)
{
for(k=1;k<=n;k++) /*从weight[k].c中查找与ch[i]相等的下标K*/
if(ch[i]==weight[k].c)
break;
hc[i]=(char *)malloc((weight[k].num)*sizeof(char));
strcpy(hc[i],h[k]); //拷贝二进制编码
}
}
/*****解码*****/
void TrsHuffmanTree(Huffman ht,WeightNode w,HuffmanCode hc,int n,int m)
{
int i=0,j,p;
printf(***StringInformation*** );
while(i<m)
{
p=2*n-1;//从父亲节点向下遍历直到叶子节点
for(j=0;hc[i][j]!='';j++)
{
if(hc[i][j]=='0')
p=ht[p].LChild;
else
p=ht[p].RChild;
}
printf(%c,w[p].c); /*打印原信息*/
i++;
}
}
/*****释放huffman编码内存*****/
void FreeHuffmanCode(HuffmanCode h,HuffmanCode hc,int n,int m)
{
int i;
for(i=1;i<=n;i++)//释放叶子结点的编码
free(h[i]);
for(i=0;i<m;i++) //释放所有结点的编码
free(hc[i]);
}
void main()
{
int i,n=0; /*n为叶子结点的个数*/
int m=0; /*m为字符串ch[]的长度*/
char ch[N]; /*ch[N]存放输入的字符串*/
Huffman ht; /*Huffman二叉数*/
HuffmanCode h,hc; /*h存放叶子结点的编码，hc 存放所有结点的编码*/
WeightNode weight; /*存放叶子结点的信息*/
printf( ***HuffmanCoding*** );
printf(please input information :);
gets(ch); /*输入字符串*/
CreateWeight(ch,&m,weight,&n); /*产生叶子结点信息，m为字符串ch[]的长度*/
printf(***WeightInformation*** Node );
for(i=1;i<=n;i++) /*输出叶子结点的字符与权值*/
printf(%c ,weight[i].c);
printf( Weight );
for(i=1;i<=n;i++)
printf(%d ,weight[i].weight);
CreateHuffmanTree(ht,weight,n); /*产生Huffman树*/
printf( ***HuffamnTreeInformation*** );
printf( i weight parent LChild RChild );
for(i=1;i<=2*n-1;i++) /*打印Huffman树的信息*/
printf( %d %d %d %d %d ,i,ht[i].weight,ht[i].parent,ht[i].LChild,ht[i].RChild);
CrtHuffmanNodeCode(ht,ch,h,weight,m,n); /*叶子结点的编码*/
printf( ***NodeCode*** ); /*打印叶子结点的编码*/
for(i=1;i<=n;i++)
{
printf( %c:,weight[i].c);
printf(%s ,h[i]);
}
CrtHuffmanCode(ch,h,hc,weight,n,m); /*所有字符的编码*/
printf(***StringCode*** ); /*打印字符串的编码*/
for(i=0;i<m;i++)
printf(%s,hc[i]);
system(pause);
TrsHuffmanTree(ht,weight,hc,n,m); /*解码*/
FreeHuffmanCode(h,hc,n,m);
system(pause);
} Matlab 中简易实现Huffman编译码：
n=input('Please input the total number: ');
hf=zeros(2*n-1,5);
hq=[];
for ki=1:n
hf(ki,1)=ki;
hf(ki,2)=input('Please input the frequency: ');
hq=[hq,hf(ki,2)];
end
for ki=n+1:2*n-1
hf(ki,1)=ki;
mhq1=min(hq);
m=size(hq);
m=m(:,2);
k=1;
while k<=m%del min1
if hq(:,k)==mhq1
hq=[hq(:,1:(k-1)) hq(:,(k+1):m)];
m=m-1;
break
else
k=k+1;
end
end
k=1;
while hf(k,2)~=mhq1|hf(k,5)==1%find min1 location
k=k+1;
end
hf(k,5)=1;
k1=k;
mhq2=min(hq);
k=1;
while k<=m%del min2
if hq(:,k)==mhq2
hq=[hq(:,1:(k-1)) hq(:,(k+1):m)];
m=m-1;
break
else
k=k+1;
end
end
k=1;
while hf(k,2)~=mhq2|hf(k,5)==1%find min2 location
k=k+1;
end
hf(k,5)=1;
k2=k;
hf(ki,2)=mhq1+mhq2;
hf(ki,3)=k1;
hf(ki,4)=k2;
hq=[hq hf(ki,2)];
end
clc
choose=input('Please choose what you want: 1: Encoding 2: Decoding 3:.Exit ');
while choose==1|choose==2
if choose==1
a=input('Please input the letter you want to Encoding: ');
k=1;
while hf(k,2)~=a
k=k+1;
if k>=n
display('Error! You did not input this number.');
break
end
end
if k>=n
break
end
r=[];
while hf(k,5)==1
kc=n+1;
while hf(kc,3)~=k&hf(kc,4)~=k
kc=kc+1;
end
if hf(kc,3)==k
r=[0 r];
else
r=[1 r];
end
k=kc;
end
r
else
a=input('Please input the metrix you want to Decoding: ');
sa=size(a);
sa=sa(:,2);
k=2*n-1;
while sa~=0
if a(:,1)==0
k=hf(k,3);
else
k=hf(k,4);
end
a=a(:,2:sa);
sa=sa-1;
if k==0
display('Error! The metrix you entered is a wrong one.');
break
end
end
if k==0
break
end
r=hf(k,2);
end
choose=input('Choose what you want: 1: Encoding 2: Decoding 3:.Exit ');
clc;
end
if choose~=1&choose~=2
clc;
end

3. 用C程序实现哈夫曼编码

去年做的课程设计，有什么不合要求的自己改改

#include<string.h>
#include<stdlib.h>
#include<stdio.h>

int m,s1,s2;

typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树
typedef char *HuffmanCode; //动态分配数组存储哈夫曼编码表

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

void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC[], int *w, int n) {
// 算法6.13
// w存放n个字符的权值(均>0)，构造哈夫曼树HT，
// 并求出n个字符的哈夫曼编码HC
int i, j;
char *cd;
int p;
int cdlen;

if (n<=1) return;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0号单元未用
for (i=1; i<=n; i++) { //初始化
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for (i=n+1; i<=m; i++) { //初始化
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
puts("\n哈夫曼树的构造过程如下所示：");
printf("HT初态:\n 结点 weight parent lchild rchild");
for (i=1; i<=m; i++)
printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight,
HT[i].parent,HT[i].lchild, HT[i].rchild);
printf(" 按任意键，继续 ...");
getchar();
for (i=n+1; i<=m; i++) { // 建哈夫曼树
// 在HT[1..i-1]中选择parent为0且weight最小的两个结点，
// 其序号分别为s1和s2。
Select(HT, i-1);
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;
printf("\nselect: s1=%d s2=%d\n", s1, s2);
printf(" 结点 weight parent lchild rchild");
for (j=1; j<=i; j++)
printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,
HT[j].parent,HT[j].lchild, HT[j].rchild);
printf(" 按任意键，继续 ...");
getchar();
}

//------无栈非递归遍历哈夫曼树，求哈夫曼编码
cd = (char *)malloc(n*sizeof(char)); // 分配求编码的工作空间
p = m; cdlen = 0;
for (i=1; i<=m; ++i) // 遍历哈夫曼树时用作结点状态标志
HT[i].weight = 0;
while (p) {
if (HT[p].weight==0) { // 向左
HT[p].weight = 1;
if (HT[p].lchild != 0) { p = HT[p].lchild; cd[cdlen++] ='0'; }
else if (HT[p].rchild == 0) { // 登记叶子结点的字符的编码
HC[p] = (char *)malloc((cdlen+1) * sizeof(char));
cd[cdlen] ='\0'; strcpy(HC[p], cd); // 复制编码(串)
}
} else if (HT[p].weight==1) { // 向右
HT[p].weight = 2;
if (HT[p].rchild != 0) { p = HT[p].rchild; cd[cdlen++] ='1'; }
} else { // HT[p].weight==2，退回退到父结点，编码长度减1
HT[p].weight = 0; p = HT[p].parent; --cdlen;
}
}
} // HuffmanCoding
void main() {
HuffmanTree HT;HuffmanCode *HC;int *w,n,i;
puts("输入结点数:");
scanf("%d",&n);
HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode));
w = (int *)malloc(n*sizeof(int));
printf("输入%d个结点的权值\n",n);
for(i = 0;i < n;i++)
scanf("%d",&w[i]);
HuffmanCoding(HT,HC,w,n);
puts("\n各结点的哈夫曼编码:");
for(i = 1;i <= n;i++)
printf("%2d(%4d):%s\n",i,w[i-1],HC[i]);
getchar();
}

4. 哈夫曼编码/译码器编程

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define M 10000 //定义字符串最大长度
#define N 128 //定义叶子节点个数
typedef struct node //定义哈夫曼树节点结构体
{
int weight;
struct node *LChild,*RChild,*Parent; //分别指向该节点的左孩子，右孩子，和双亲节点
struct node *next; //指向建立的哈夫曼树的下一个节点
}HFMNode,*HFMTree;
typedef struct //定义哈夫曼编码的结构体
{
char ch; //存储对应的字符
char code[N+1]; //存储对应字符的编码
int start; //存储编码的起始位置
}CodeNode;int n; //存储真正叶子节点个数
void clearscreen()
{
system("cls");
}
void Open(char s[]) //打开存放字符或编码的文件，将其存入字符串数组中
{
char name[10];
FILE *fp;
int i=0;
printf("请输入要打开的文件名：");
gets(name); //要打开的文件名
if((fp=fopen(name,"rt"))==NULL)
{
printf("打开失败！\n"); //若打开失败，则直接退出
exit(1);
}
s[i++]=fgetc(fp);
while(s[i-1]!=EOF)
s[i++]=fgetc(fp);
s[i]='\0'; //存取字符串结束
fclose(fp);
}
void Save(char s[]) //保存字符或编码到文件中
{
char name[10];
FILE *fp;
printf("请输入要保存的文件名：");
gets(name);
if((fp=fopen(name,"wt"))==NULL)
{
printf("存储失败！");
exit(1);
}
fputs(s,fp);
printf("\n保存成功，文件名为:%s。\n",name);
printf("\n按回车键继续...");
getchar();
fclose(fp);} void SearchStr(char s[],char str[],int count[])
{
//查找字符串中字符的个数和每个字符出现的次数
int i,j,k=0;
for(i=0;i<N;i++) //初始化每个字符出现的次数
count[i]=0;
for(i=0;s[i];i++)
{
for(j=0;j<k;j++) //在str[]中查找是否有该字符
if(str[j]==s[i])
{
count[j]++;
break;
}
if(j==k) //在str[]中无该字符，将其存入最后一个单元
{
str[k]=s[i];
count[k++]++;
}
}
str[k]='\0'; //将字符串结尾置\0
n=k; //将实际的字符个数作为叶子节点个数存入n
}void SelectMin(HFMTree HT,int k,HFMTree *HT1,HFMTree *HT2)
{
//查找哈夫曼链表中两个权值最小的节点
int i,min;
HFMTree p;
min=32767;
for(i=0,p=HT;i<k;i++,p=p->next)
if(p->weight<min&&p->Parent==0)
{
min=p->weight;
*HT1=p;
}
min=32767;
for(i=0,p=HT;i<k;i++,p=p->next)
if(p->weight<min&&p->Parent==0&&p!=*HT1) //令第二个最小的节点不等于第一个节点
{
min=p->weight;
*HT2=p;
}}
void CreatHFMTree(HFMTree *HT,int count[])
{
//创建哈夫曼树
int i;
HFMTree p,HT1,HT2; //HT1，HT2分别存放权值最小和次小的节点的位置
p=*HT=(HFMTree)malloc(sizeof(HFMNode));
p->next=p->LChild=p->RChild=p->Parent=NULL; //初始化哈夫曼链表且有2n-1个节点
for(i=1;i<2*n-1;i++)
{
p->next=(HFMTree)malloc(sizeof(HFMNode));
p=p->next;
p->next=p->LChild=p->RChild=p->Parent=NULL;
}for(i=0,p=*HT;i<n;i++) //将各个字符出现的次数作为权值
{ //存入哈夫曼链表的前n个单元中
p->weight=count[i];
p=p->next;
}for(i=n;i<2*n-1;i++) //将后n-1个节点赋权值，建树
{
SelectMin(*HT,i,&HT1,&HT2); //每次从前i个节点中选取权值最小的两个节点
HT1->Parent=HT2->Parent=p;
p->LChild=HT1;
p->RChild=HT2;
p->weight=HT1->weight+HT2->weight; //将两个节点的权值相加存入最后一个节点中
p=p->next; //p指向下一个没有存储权值的节点
}}
void HFMCode(HFMTree HT,CodeNode HC[],char str[])
{
//从每个叶子节点开始，利用哈夫曼树对每个字符进行编码，最终建立一个哈夫曼表
int i;
HFMTree q,p=HT;
for(i=0;i<n;i++) //将字符存入哈夫曼编码结构体数组的字符单元中
{
HC[i].ch=str[i];
HC[i].code[n-1]='\0'; //初始化编码的最后一位
}
for(i=0;i<n;i++)
{
HC[i].start=n-1;
for(q=p;q->Parent;q=q->Parent) //判断q所指向的节点，左孩子置0，右孩子置1
if(q==q->Parent->LChild)
HC[i].code[--HC[i].start]='0';
else HC[i].code[--HC[i].start]='1';
p=p->next; //判断下一个叶子节点
}
}
void TotalCoding(char s[],CodeNode HC[],char code[])
{
//利用哈夫曼编码表对整个字符串进行编码
int i,j;
code[0]='\0'; //编码数组初始化
for(i=0;s[i];i++) //将每个字符在哈夫曼编码表中对应的编码存入存放总编码的数组中
for(j=0;j<n;j++)
if(s[i]==HC[j].ch)
strcpy(code+strlen(code),HC[j].code+HC[j].start);
}void DeCoding(char code[],HFMTree HT,char str[],char s[])
{
//对哈夫曼编码进行解码，放入字符串s中
int i,j,k=0;
HFMTree root,p,q;
for(root=HT;root->Parent;root=root->Parent); //用root指向哈夫曼树的根结点
for(i=0,p=root;code[i];i++) //从根结点开始按编码顺序访问树
{
if(code[i]=='0')
p=p->LChild;
else p=p->RChild;
if(p->LChild==NULL&&p->RChild==NULL) //到根节点时将该节点对应的字符输出
{
for(j=0,q=HT;q!=p;q=q->next,j++);
s[k++]=str[j];
p=root; //回溯到根结点
}
}
s[k]='\0'; //解码完毕，在字符串最后一个单元存入'\0'
}
void Coding(char s[],char str[],char code[],int count[],HFMTree *HT,CodeNode HC[])
{
clearscreen();
printf("\n打开存放字符串的文件...\n\n");
Open(s); //打开源码文件
SearchStr(s,str,count); //查找字符串中不同的字符及其出现的次数
CreatHFMTree(HT,count); //用每个字符出现的次数作为叶子节点的权值建立哈夫曼树
HFMCode(*HT,HC,str); //利用哈夫曼树对每个叶子节点进行编码，存入编码表中
TotalCoding(s,HC,code); //利用编码表对字符串进行最终编码
printf("\n读入的字符串为:\n");
puts(s);
printf("\n最终的哈夫曼编码是:\n");
puts(code);
printf("\n保存编码,");
Save(code); //保存最终的哈夫曼编码
}
void TransCode(char code[],char str[],char ss[],HFMTree *HT,CodeNode HC[])
{
clearscreen();
printf("\n打开编码的文件...\n\n");
Open(code); //打开编码文件
DeCoding(code,*HT,str,ss); //将编码进行解码存入字符串数组ss[]中
printf("\n得到的最终字符串为:\n");
puts(ss);
printf("\n保存译码，");
Save(ss); //保存译码后的字符串
}void main()
{
//主函数
char s[M],ss[M]; //定义字符串数组，s[]存放将要编码的字符串，ss[]存解码后的字符串
char str[N]; //存放输入的字符串中n个不同的字符
int count[N]; //存放n个不同字符对应的在原字符串中出现的次数
char code[M]; //存放最终编码完成后的编码
char choice;
HFMTree HT; //定义一个哈夫曼树的链表
CodeNode HC[N]; //定义一个哈夫曼编码表的数组，存放每个字符对应的哈夫曼编码
do
{
clearscreen();
printf("\n\n");
printf(" ************哈夫曼树************\n");
printf(" ** **\n");
printf(" ** 1.编码。 **\n");
printf(" ** 2.译码。 **\n");
printf(" ** 0.退出。 **\n");
printf(" ** **\n");
printf(" ** **\n");
printf(" ** **\n");
printf(" ** 请输入相应操作的序号(0-2) **\n");
printf(" ********************************\n");
scanf("%c",&choice);
getchar();
switch(choice)
{
case '1': Coding(s,str,code,count,&HT,HC);break; //对字符串进行编码
case '2': TransCode(code,str,ss,&HT,HC);break; //对编码进行解码
case '0': break;
default : printf(" 输入错误！请重新输入！\n");
}
}while(choice!='0');
}

5. 哈夫曼树及哈夫曼编码的C程序实现(数据结构题)

去年做的课程设计，有什么不合要求的自己改改

#include<string.h>
#include<stdlib.h>
#include<stdio.h>

int m,s1,s2;

typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树
typedef char *HuffmanCode; //动态分配数组存储哈夫曼编码表

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

void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC[], int *w, int n) {
// 算法6.13
// w存放n个字符的权值(均>0)，构造哈夫曼树HT，
// 并求出n个字符的哈夫曼编码HC
int i, j;
char *cd;
int p;
int cdlen;

if (n<=1) return;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0号单元未用
for (i=1; i<=n; i++) { //初始化
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for (i=n+1; i<=m; i++) { //初始化
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
puts("\n哈夫曼树的构造过程如下所示：");
printf("HT初态:\n 结点 weight parent lchild rchild");
for (i=1; i<=m; i++)
printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight,
HT[i].parent,HT[i].lchild, HT[i].rchild);
printf(" 按任意键，继续 ...");
getchar();
for (i=n+1; i<=m; i++) { // 建哈夫曼树
// 在HT[1..i-1]中选择parent为0且weight最小的两个结点，
// 其序号分别为s1和s2。
Select(HT, i-1);
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;
printf("\nselect: s1=%d s2=%d\n", s1, s2);
printf(" 结点 weight parent lchild rchild");
for (j=1; j<=i; j++)
printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,
HT[j].parent,HT[j].lchild, HT[j].rchild);
printf(" 按任意键，继续 ...");
getchar();
}

//------无栈非递归遍历哈夫曼树，求哈夫曼编码
cd = (char *)malloc(n*sizeof(char)); // 分配求编码的工作空间
p = m; cdlen = 0;
for (i=1; i<=m; ++i) // 遍历哈夫曼树时用作结点状态标志
HT[i].weight = 0;
while (p) {
if (HT[p].weight==0) { // 向左
HT[p].weight = 1;
if (HT[p].lchild != 0) { p = HT[p].lchild; cd[cdlen++] ='0'; }
else if (HT[p].rchild == 0) { // 登记叶子结点的字符的编码
HC[p] = (char *)malloc((cdlen+1) * sizeof(char));
cd[cdlen] ='\0'; strcpy(HC[p], cd); // 复制编码(串)
}
} else if (HT[p].weight==1) { // 向右
HT[p].weight = 2;
if (HT[p].rchild != 0) { p = HT[p].rchild; cd[cdlen++] ='1'; }
} else { // HT[p].weight==2，退回退到父结点，编码长度减1
HT[p].weight = 0; p = HT[p].parent; --cdlen;
}
}
} // HuffmanCoding
void main() {
HuffmanTree HT;HuffmanCode *HC;int *w,n,i;
puts("输入结点数:");
scanf("%d",&n);
HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode));
w = (int *)malloc(n*sizeof(int));
printf("输入%d个结点的权值\n",n);
for(i = 0;i < n;i++)
scanf("%d",&w[i]);
HuffmanCoding(HT,HC,w,n);
puts("\n各结点的哈夫曼编码:");
for(i = 1;i <= n;i++)
printf("%2d(%4d):%s\n",i,w[i-1],HC[i]);
getchar();
}

6. 用C/C++或Java编程实现： 通过给定字符a,b,c,d,e,f,g,h,i,h的使用频率，编程求出它们的赫夫曼编码。

下面的截图就是你给定的权重对应的haffman编码，见图：

下面的二进制数就是对应的编码

7. 哈夫曼树及哈夫曼编码译码的实现（根据程序画流程图及对每句程序注释）

这是以前写的，可是我不想加注释了，Huffman编码其实原理很简单的，你自己好好学下吧，一句一句注释也太夸张了啊。

#include<string.h>
#include<stdlib.h>
#include<stdio.h>

int m,s1,s2;

typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;

typedef char ** HuffmanCode;

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

void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)
{
int i,j;
char *cd;
int p;
int cdlen;
if (n<=1) return;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode));
for (i=1; i<=n; i++)
{
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for (i=n+1; i<=m; i++)
{
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}

//添加查看，便于调试
printf("构造过程显示：\n");
for(i=1;i<=m;i++)
printf("%4d%4d%4d%4d%4d\n",i,HT[i].weight, HT[i].parent,HT[i].lchild, HT[i].rchild);
system("pause");

for(i=n+1;i<=m;i++)
{
Select(HT,i-1);
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;
//添加查看，便于调试
/*printf("s1=%d,s2=%d\n",s1,s2);
for(j=1;j<=i;j++)
printf("%d%4d%4d%4d",j,HT[j].weight,HT[j].parent,HT[j].lchild, HT[j].rchild);
system("pause");
*/
}
cd = (char *)malloc(n*sizeof(char));
p=m;
cdlen=0;
for(i=1;i<=m;i++)
HT[i].weight=0;
while(p)
{
if(HT[p].weight==0)
{
HT[p].weight=1;
if(HT[p].lchild!=0)
{
p=HT[p].lchild;
cd[cdlen++]='0';
}
else if(HT[p].rchild==0)
{
HC[p]=(char *)malloc((cdlen+1)*sizeof(char));
cd[cdlen]='\0';
strcpy(HC[p],cd);
}
}
else if(HT[p].weight==1)
{
HT[p].weight=2;
if(HT[p].rchild!=0)
{
p=HT[p].rchild;
cd[cdlen++]='1';
}
}
else
{
HT[p].weight=0;
p=HT[p].parent;
--cdlen;
}
}

}

int main()
{
HuffmanTree HT;
HuffmanCode HC;
int *w,n,i;
printf("请输入节点数：\n");
scanf("%d",&n);
HC = (HuffmanCode)malloc(n*sizeof(HuffmanCode));
w=(int *)malloc(n*sizeof(int));
printf("请输入节点的权值：\n");
for(i=0;i<n;i++)
scanf("%d",&w[i]);
HuffmanCoding(HT,HC,w,n);
printf("输出编码：\n");
for(i=1;i<=n;i++)
printf("%2d(%4d):%s\n",i,w[i-1],HC[i]);
return 0;
system("pause");
}

8. 用哈夫曼编码 编程

手打的,你最好编译一下以免我哪里敲错了
(网络不能显示行首空格真是不爽)

//哈夫曼树和~编码的存储表示
typedef struct{
unsigned int weight;//权值
unsigned int parent,lchild,rchild;
}HTNode, *HuffmanTree;//动态分配数组存储哈夫曼树
typedef char * *HuffmanCode;//动态分配数组存储哈夫曼编码表

void HoffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n){
//w存放n个字符的权值(均>0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC
if (n<=1) return;
m=2*n-1;
HT=(HuffmanTree) malloc ((m+1)*sizeof(HTNode));//0号单元未采用
for (p=HT,i=1;i<=n;++i,++p,++w) *p={*w,0,0,0};
for (;i<=m;++i;++p) *p={0,0,0,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=i;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个字符编码的头指针向量
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);//释放工作空间
}//HuffmanCoding

9. 哈夫曼编码码长怎么算

设某信源产生有五种符号u1、u2、u3、u4和u5，对应概率P1=0.4，P2=0.1，P3=P4=0.2，P5=0.1。

霍夫曼编码是变长编码，思路：对概率大的编的码字短，概率小的编的码字长，这样一来所编的总码长就小，这样编码效率就高。上面那样求是不对的，除非你这6个码字是等概率的，各占1/6。应该用对应的概率*其对应得码长，再求和。

实际应用中

除采用定时清洗以消除误差扩散和采用缓冲存储以解决速率匹配以外，主要问题是解决小符号集合的统计匹配，例如黑（1）、白（0）传真信源的统计匹配，采用0和1不同长度游程组成扩大的符号集合信源。游程，指相同码元的长度（如二进码中连续的一串0或一串1的长度或个数）。

按照CCITT标准，需要统计2×1728种游程（长度），这样，实现时的存储量太大。事实上长游程的概率很小，故CCITT还规定：若l表示游程长度，则l=64q+r。