当前位置：首页 » 编程语言 » 哈夫曼编码c语言实现

哈夫曼编码c语言实现

发布时间: 2021-03-30 01:00:09

㈠哈夫曼树及哈夫曼编码，c语言算法实现

#include<stdio.h>
#define MAX 30
#define inf 100000000
typedef char valType;
typedef int wghType;
struct HFMnode
{
valType data;
wghType weight;
int parent;
int lchild;
int rchild;
};
struct HFMcode
{
char code[MAX];
int start;
};
void createHFMtree(HFMnode *node,int n)
{
int i,m1,m2,l,r;
for(i=n+1;i<=2*n-1;i++)
{
m1=m2=inf;
l=r=0;
int k;
for(k=1;k<=i-1;k++)
if(node[k].parent==0)
{
if(node[k].weight<m1)
{
m2=m1;
r=l;
m1=node[k].weight;
l=k;
}
else if(node[k].weight<m2)
{
m2=node[k].weight;
r=k;
}
}
node[i].weight=node[l].weight+node[r].weight;
node[i].lchild=l;
node[i].rchild=r;
node[l].parent=i;
node[r].parent=i;
}
}
void createHFMcode(HFMnode *node, HFMcode *hcode,int n)
{
int i;
for(i=1;i<=n;i++)
{
HFMcode d;
d.start=n;
int num=i;
int father=node[num].parent;
while(father!=0)
{
if(node[father].lchild==num)
d.code[d.start--]='0';
else d.code[d.start--]='1';
num=father;
father=node[num].parent;
}
hcode[i]=d;
}
}
void printHFMcode(HFMnode * node,HFMcode * hcode,int n)
{
int i;
for(i=1;i<=n;i++)
{
printf("%c: ",node[i].data);
for(int k=hcode[i].start+1;k<=n;k++)
putchar(hcode[i].code[k]);
puts("");
}
}
void main()
{
HFMnode node[2*MAX];HFMcode hcd[MAX];
int n;
scanf("%d\n",&n);
for(int i=1;i<=n;i++){
printf("输入第%d个节点的值\n",i);
scanf("%c",&node[i].data);
printf("输入它的权重\n");
scanf("%d\n",&node[i].weight);
}
for(int i=1;i<=2*n-1;i++)
node[i].parent=node[i].lchild=node[i].rchild=0;
createHFMtree(node,n);
createHFMcode(node,hcd,n);
printHFMcode(node,hcd,n);
}

参考资料:http://blog.csdn.net/heyongluoyao8/article/details/6925209
输入文件格式例：
26
A 7
B 2
C 2
D 3
E 11
F 2
G 2
H 6
I 6
J 1
K 1
L 4
M 3
N 7
O 9
P 2
Q 1
R 6
S 6
T 8
U 4
V 1
W 2
X 1
Y 2
Z 1

㈡哈夫曼树及哈夫曼编码的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();
}

㈢霍夫曼编码用c语言实现

以前写的，证明最优子结构，随便一本算法书上就有. #include<stdio.h>
#include<stdlib.h>
#define NIL -2
#define Size_Max_bm 30
#define left(i) (2*(i)+1)
#define right(i) (2*(i)+2)
#define swap(a,b) {cjys t;t=(a);(a)=(b);(b)=t;}
#define parent(i) ((i)%2?((i)-1)/2:((i)-2)/2)typedef struct cjys
{
char sj;
int pl;
struct cjys *left;
struct cjys *right;
}cjys;typedef struct cjdl
{
int size;
int leapsize;
cjys *p;
}cjdl;
cjys *fpnn(void);
void input(cjdl *p);
cjys *fpnn(void);
void zxdwh(cjys *p, int i, int leapsize);
void rd(cjdl *p, cjys tp);
cjys cd(cjdl *p);
void hbs(cjdl *p);
cjys *cjs(cjdl *p);
void bls(cjys *p,int *jl, int i);
void disp(char *tp, cjys *p);int main()
{
cjdl p;
char x[255];
cjys *re=NULL;
int jl[Size_Max_bm];
input(&p);
re=cjs(&p);
printf("对照编码图为:\n");
bls(re,jl,0);
freopen("CON","r",stdin);
printf("输入Huffman码(VLC):");
scanf("%s",x);
disp(x,re);
system("pause");
}
void input(cjdl *p)
{
int i;
cjys *tp;
tp=fpnn();
printf("输入字母个数:");
scanf("%d", &p->size);
p->p=malloc(sizeof(cjys)*p->size);
p->leapsize=0;
for(i = 0; i < p->size;i++)
{
printf("输入第%d字母:",i+1),scanf(" %c",&tp->sj);
printf("输入出现次数(频率整数):"),scanf("%d",&tp->pl);
rd(p,*tp);
}
free(tp);
}
cjys *fpnn(void)
{
cjys *p=NULL;
p=malloc(sizeof(cjys));
p->left=NULL;
p->right=NULL;
return p;
} void zxdwh(cjys *p, int i, int leapsize)
{
int l=left(i), r=right(i), mini=i;
if(l<leapsize && p[l].pl<p[mini].pl)
mini=l;
if(r<leapsize && p[r].pl<p[mini].pl)
mini=r;
if(mini != i)
{
swap(p[i],p[mini]);
zxdwh(p,mini,leapsize);
}
}
void rd(cjdl *p, cjys tp)
{
if(p->leapsize == p->size)
{
printf("队列已满!");
exit(0);
}
p->p[p->leapsize]=tp;
int j=p->leapsize,k=parent(j);
while(k>=0 && p->p[j].pl < p->p[k].pl)
{
swap(p->p[j],p->p[k]);
j=k;
k=parent(j);
}
p->leapsize++;
}
cjys cd(cjdl *p)
{
if(p->leapsize == 0)
{
printf("队列已空!");
exit(0);
}
cjys tp=p->p[0];
p->leapsize--;
p->p[0]=p->p[p->leapsize];
zxdwh(p->p,0,p->leapsize);
return tp;
}
void hbs(cjdl *p)
{
cjys *p1=NULL, *p2=NULL;
cjys tp;
p1=fpnn();
p2=fpnn();
*p1=cd(p);
*p2=cd(p);
tp.left=p1;
tp.right=p2;
tp.pl=p1->pl+p2->pl;
tp.sj=NIL;
rd(p,tp);
}cjys *cjs(cjdl *p)
{
int i, n=p->leapsize;
cjys *tp=NULL;
tp=fpnn();
for(i = 0; i < n-1; i++)
hbs(p);
*tp=p->p[0];
return tp;
}
void bls(cjys *p, int *jl, int i)
{
if(p == NULL)
return;
if(p->sj!=NIL)
{
int i2;
printf("%c:",p->sj);
for(i2 = 0; i2 < i; i2++)
printf("%d",jl[i2]);
printf("\n");
}
jl[i]=0;
bls(p->left,jl,i+1);
jl[i]=1;
bls(p->right,jl,i+1);
}
void disp(char *tp, cjys *p)
{
cjys *ttp=NULL;
int pd=0;
while(1)
{
ttp=p;
while(1)
{
if(ttp->sj != NIL)
{
printf("%c",ttp->sj);
break;
}
if(*tp == '\0')
{
pd=1;
break;
}

if(*tp++ == '0' )
ttp=ttp->left;
else
ttp=ttp->right;
}
if(pd)
break;
}
}

㈣ Huffman编码C语言实现

说明：本程序是依据严蔚敏的数据结构（C语言版）上的代码实现的。
#pragmaonce
#include<stdio.h>
#include<tchar.h>
#include<stdlib.h>
#define MAX 100

typedefstruct{ //节点
int weight;
int parent, lchild, rchild;
}HTNode, *HuffmanTree;

typedefchar **HuffmanCode; //字符串数组，用于存储叶子节点的编码

void SelectMinNode(HuffmanTree &HT, int m, int &i1, int &i2) //找出权值最小的两个节点对应的数组下标
{
HuffmanTree p = HT;
int s1, s2;
s1 = s2 = MAX;
i1 = i2 = 1;
for(int i=1; i<=m; i++)
{
if(!(p+i)->parent)
{
if((p+i)->weight < s1)
{
i2 = i;
s1 = (p+i)->weight ;
}
}
}
for(int i=1; i<=m; i++)
{
if(!(p+i)->parent && i!=i2)
{
if((p+i)->weight < s2)
{
i1 = i;
s2 = (p+i)->weight ;
}
}
}
}
void StrCopy(char *p, char *q, int start) //从字符数组中第start个字符开始复制
{
char *c1, *c2;
c1 = p;
while(q[start] != '\0')
{
*c1 = q[start];
c1++;
start++;
}
*c1 = q[start];//别忘了将‘\n’复制过来
}
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)
{ //HT赫夫曼树节点数组，HC存储赫夫曼编码，*w 节点权值数组的首地址，n节点个数
int i, i1, i2, m;
HuffmanTree p;
if(n<=1) return;
m = 2 * n -1; //n个叶子节点的赫夫曼树的节点总数为2n-1，可以结合树的度为n-1自己证明。
HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode)); //数组首元素不使用，故多分配一个空间
p = HT + 1;
for(i=1;i<=n;++i,++p,++w) //n个叶子节点初始化
{
p->weight = *w;
p->lchild = 0;
p->rchild = 0;
p->parent = 0;
}
for(;i<=m;++i,++p) //非叶子节点初始化
{
p->weight = 0;
p->lchild = 0;
p->rchild = 0;
p->parent = 0;
}
for(i=n+1;i<=m;++i) //对非叶子节点重新计算
{
SelectMinNode(HT, i-1, i1, i2);
HT[i1].parent = i;
HT[i2].parent = i;
HT[i].lchild = i1;
HT[i].rchild = i2;
HT[i].weight = HT[i1].weight + HT[i2].weight ;
}

///从叶子节点到根节点求赫夫曼编码
char* cd;
int start, c, f;
HC = (HuffmanCode)malloc((n+1)*sizeof(char*));//分配字符指针数组，同样多分配一个
cd = (char*)malloc(n*sizeof(char)); //零时变量，用于存储当前叶子节点的赫夫曼编码
cd[n-1] = '\0';
for(int 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));
StrCopy(HC[i], cd, start); //将存储的编码给HC的第i个数组
}
free(cd);
}
void PrintHuffmanCode(HuffmanTree HT, HuffmanCode HC, int n) //打印各节点的赫夫曼编码
{
HuffmanCode p;
for(int i=1; i<=n; i++)
{
p = HC;
printf("The weight %d HuffmanCode is: ", HT[i]);
while(*p[i]!='\0')
{
printf("%c",*p[i]);
p[i]++;
}
printf("\n");
}
}
void main()
{
int n = 8;
HuffmanTree HT;
HuffmanCode HC;
int a[8] = {5, 29, 7, 8, 14, 23, 3, 11};//信号源的概率分布，即P={p0, p1,…, pK-1}
HuffmanCoding(HT, HC, a, n);
PrintHuffmanCode(HT, HC, n);
system("pause");}

㈤哈夫曼编码的C语言源代码

/*文件名:exp7-6.cpp*/
#include <stdio.h>
#include <string.h>
#define N 50 /*叶子结点数*/
#define M 2*N-1 /*树中结点总数*/
typedef struct
{
char data[5]; /*结点值*/
int weight; /*权重*/
int parent; /*双亲结点*/
int lchild; /*左孩子结点*/
int rchild; /*右孩子结点*/
} HTNode;
typedef struct
{
char cd[N]; /*存放哈夫曼码*/
int start;
} HCode;
void CreateHT(HTNode ht[],int n)
{
int i,k,lnode,rnode;
int min1,min2;
for (i=0;i<2*n-1;i++) /*所有结点的相关域置初值-1*/
ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
for (i=n;i<2*n-1;i++) /*构造哈夫曼树*/
{
min1=min2=32767; /*lnode和rnode为最小权重的两个结点位置*/
lnode=rnode=-1;
for (k=0;k<=i-1;k++)
if (ht[k].parent==-1) /*只在尚未构造二叉树的结点中查找*/
{
if (ht[k].weight<min1)
{
min2=min1;rnode=lnode;
min1=ht[k].weight;lnode=k;
}
else if (ht[k].weight<min2)
{
min2=ht[k].weight;rnode=k;
}
}
ht[lnode].parent=i;ht[rnode].parent=i;
ht[i].weight=ht[lnode].weight+ht[rnode].weight;
ht[i].lchild=lnode;ht[i].rchild=rnode;
}
}
void CreateHCode(HTNode ht[],HCode hcd[],int n)
{
int i,f,c;
HCode hc;
for (i=0;i<n;i++) /*根据哈夫曼树求哈夫曼编码*/
{
hc.start=n;c=i;
f=ht[i].parent;
while (f!=-1) /*循序直到树根结点*/
{
if (ht[f].lchild==c) /*处理左孩子结点*/
hc.cd[hc.start--]='0';
else /*处理右孩子结点*/
hc.cd[hc.start--]='1';
c=f;f=ht[f].parent;
}
hc.start++; /*start指向哈夫曼编码最开始字符*/
hcd[i]=hc;
}
}
void DispHCode(HTNode ht[],HCode hcd[],int n)
{
int i,k;
int sum=0,m=0,j;
printf(" 输出哈夫曼编码:\n"); /*输出哈夫曼编码*/
for (i=0;i<n;i++)
{
j=0;
printf(" %s:\t",ht[i].data);
for (k=hcd[i].start;k<=n;k++)
{
printf("%c",hcd[i].cd[k]);
j++;
}
m+=ht[i].weight;
sum+=ht[i].weight*j;
printf("\n");
}
printf("\n 平均长度=%g\n",1.0*sum/m);
}
void main()
{
int n=15,i;
char *str[]={"The","of","a","to","and","in","that","he","is","at","on","for","His","are","be"};
int fnum[]={1192,677,541,518,462,450,242,195,190,181,174,157,138,124,123};
HTNode ht[M];
HCode hcd[N];
for (i=0;i<n;i++)
{
strcpy(ht[i].data,str[i]);
ht[i].weight=fnum[i];
}
printf("\n");
CreateHT(ht,n);
CreateHCode(ht,hcd,n);
DispHCode(ht,hcd,n);
printf("\n");
}

以前写的，你照着改下就行的.

㈥哈夫曼编码和译码c语言的源程序

|#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <malloc.h>
#define NULL 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAX_NUM 10000
#define MAX 60
typedef int Status;
typedef char **HuffmanCode;
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef struct{
HuffmanTree HT;
char *c;
int longth;
HuffmanCode HC;
}Huffman;
void Select(HuffmanTree HT,int end,int *s1,int *s2)
{
int i;
int min1=MAX_NUM;
int min2;
for (i=1;i<=end;i++)
{
if (HT[i].parent==0&&HT[i].weight<min1)
{
*s1=i;
min1=HT[i].weight;
}
}
min2=MAX_NUM;
for(i=1;i<=end;i++)
{
if(HT[i].parent==0&&(*s1!=i)&&min2>HT[i].weight)
{
*s2=i;
min2=HT[i].weight;
}
}
}
Huffman HuffmanCoding(Huffman Hfm)
{
/*---------------------------------*/
int i,n,m,s1,s2,start;
int c,f;
char *cd;
n=Hfm.longth;
if(n<=1) return Hfm;
m=2*n-1;

for(i=n+1;i<=m;++i)
{
Select(Hfm.HT,i-1,&s1,&s2);
Hfm.HT[s1].parent=i;
Hfm.HT[s2].parent=i;
Hfm.HT[i].lchild=s1;
Hfm.HT[i].rchild=s2;
Hfm.HT[i].weight=Hfm.HT[s1].weight+Hfm.HT[s2].weight;
}
/*------------------------------------------*/
Hfm.HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=1;i<=n;++i)
{
start=n-1;
for(c=i,f=Hfm.HT[i].parent;f!=0;c=f,f=Hfm.HT[f].parent)
{
if(c==Hfm.HT[f].lchild) cd[--start]='0';
else cd[--start]='1';
}
Hfm.HC[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(Hfm.HC[i],&cd[start]);
}
free(cd);
return Hfm;
}
Huffman InputHuffman(Huffman Hfm)
{
int i,n;
clrscr();
printf("\n\n\t\t********************Initial*********************\n");
printf("\tThe chars and weights will be saved in the file \"hfmTree\"\n");
printf("Please input the number of the chars: ");
scanf("%d",&n);
Hfm.HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode));
Hfm.c=(char *)malloc((n+1)*sizeof(char));
for(i=1;i<=n;i++)
{
printf("Please input the char: ");
scanf("%s",&Hfm.c[i]);
printf("Please input the weight of the char: ");
scanf("%d",&Hfm.HT[i].weight);
Hfm.HT[i].parent=0;
Hfm.HT[i].lchild=0;
Hfm.HT[i].rchild=0;
}
for(;i<=2*n-1;++i)
{
Hfm.HT[i].weight=0;
Hfm.HT[i].parent=0;
Hfm.HT[i].lchild=0;
Hfm.HT[i].rchild=0;
}
Hfm.longth=n;
return Hfm;
}
Huffman InitHuffman(Huffman Hfm)
{
int n,i;
FILE *fp;
fp=fopen("hfmTree","rt");
if(fp==NULL)
{
Hfm=InputHuffman(Hfm);
fp=fopen("hfmTree","wt");
fprintf(fp,"%d\n",Hfm.longth);
for(i=1;i<=Hfm.longth;i++)
fprintf(fp,"%c %d",Hfm.c[i],Hfm.HT[i].weight);
rewind(fp);
}
else
{
fscanf(fp,"%d\n",&n);
Hfm.c=(char *)malloc((n+1)*sizeof(char));
Hfm.HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode));
for(i=1;i<=n;i++)
fscanf(fp,"%s %d",&Hfm.c[i],&Hfm.HT[i].weight);
for(i=1;i<=n;i++)
{
Hfm.HT[i].parent=0;
Hfm.HT[i].lchild=0;
Hfm.HT[i].rchild=0;
}
for(;i<=2*n-1;++i)
{
Hfm.HT[i].weight=0;
Hfm.HT[i].parent=0;
Hfm.HT[i].lchild=0;
Hfm.HT[i].rchild=0;
}
Hfm.longth=n;
}
fclose(fp);
Hfm=HuffmanCoding(Hfm);
return Hfm;
}

void Output(Huffman Hfm)
{
int i,n;
n=Hfm.longth;
printf("\n\n******************Output the code of the chars****************\n\n");
for(i=1;i<=n;i++)
{
printf("\n");
printf("Char: %c\t",Hfm.c[i]);
printf("Weight: %d\t",Hfm.HT[i].weight);
printf("Code: ");
puts(Hfm.HC[i]);
}
}
void Encoding(Huffman Hfm)
{
int i=0,j=0,n;
char ch[MAX];
FILE *fp,*ffp;
n=Hfm.longth;
printf("\n\n*******************Encoding**************************\n\n");
if((ffp=fopen("ToBeTran","rt"))==NULL)
{
printf("\nPlease input the sentence: ");
scanf("%s",&ch);
printf("\n");
fp=fopen("CodeFile","wt+");
}
else
{
fscanf(ffp,"%s",ch);
fclose(ffp);
}
while(ch[j])
{
for(i=1;i<=n;i++)
if(ch[j]==Hfm.c[i])
{
printf("%s",Hfm.HC[i]);
fprintf(fp,"%s",Hfm.HC[i]);
break;
}
j++;
}
rewind(fp);
fclose(fp);
}
void Decoding(Huffman Hfm)
{
HuffmanTree p;
int i,n;
int j=0;
char d[50];
FILE *fp;
n=Hfm.longth;
printf("\n\n******************Decoding************************\n\n");
if((fp=fopen("CodeFile","rt"))==NULL)
{
printf("Please input the code:");
scanf("%s",&d);
}
else
{
fscanf(fp,"%s",d);
fclose(fp);
}
printf("\nThe file is : ");
fp=fopen("TextFile","wt+");
while(d[j])
{
p=&Hfm.HT[2*n-1];
while(p->lchild||p->rchild)
{
if(d[j]=='0')
{ i=p->lchild; p=&Hfm.HT[i]; }
else
{ i=p->rchild; p=&Hfm.HT[i]; }
j++;
}
printf("%c",Hfm.c[i]);
fprintf(fp,"%c",Hfm.c[i]);
}
fclose(fp);
}
Huffman RebuildHuffman(Huffman Hfm)
{
int n,i;
FILE *fp;
fp=fopen("hfmTree","wt");
Hfm=InputHuffman(Hfm);
fprintf(fp,"%d\n",Hfm.longth);
for(i=1;i<=Hfm.longth;i++)
fprintf(fp,"%c %d",Hfm.c[i],Hfm.HT[i].weight);
rewind(fp);
fclose(fp);
Hfm=HuffmanCoding(Hfm);
return Hfm;
}
int main()
{
Huffman Hfm;
char choice='a';
Hfm=InitHuffman(Hfm);
while(choice!='q')
{
clrscr();
printf("\n\n\n\t\t*************************************\n\n");
printf("\t\t\ta. Encoding:\n\n");
printf("\t\t\tb. Decoding:\n\n");
printf("\t\t\tc. Print all codes:\n\n");
printf("\t\t\td. Rebuild the huffmantree:\n\n");
printf("\t\t\tq. Quit...\n\n");
printf("\n\t\t************************************\n\n");
printf("Please enter your choice: ");
scanf("%s",&choice);
switch(choice)
{
case 'a':
clrscr();
Encoding(Hfm);
printf("\n\n*******Please enter anykey to continue*******\n");
getch(); break;
case 'b':
clrscr();
Decoding(Hfm);
printf("\n\n*******Please enter anykey to continue********\n");
getch(); break;
case 'c':
clrscr();
Output(Hfm);
printf("\n\n*******Please enter anykey to continue********\n");
getch(); break;
case 'd':
clrscr();
Hfm=RebuildHuffman(Hfm);
printf("\n\n********************Initial*********************\n");
getch(); break;
case 'q':
break;
default:
printf(" Your choice is wrong!\n Please enter anykey to choice again!\n");
getch(); break;
}
}
return 0;
}

㈦ huffman编码译码的c语言实现

留个脚印，晚上回去看看

#include <iostream.h>
#include <iomanip.h>
#include <string.h>
#include <malloc.h>
#include <stdio.h>

//typedef int TElemType;
const int UINT_MAX=1000;
char str[50];

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

typedef char **HuffmanCode;

//-----------全局变量-----------------------
HuffmanTree HT;
HuffmanCode HC;
int w[50],i,j,n;
char z[50];
int flag=0;
int numb=0;

// -----------------求赫夫曼编码-----------------------
struct cou{
char data;
int count;
}cou[50];

int min(HuffmanTree t,int i)
{ // 函数void select()调用
int j,flag;
int k=UINT_MAX; // 取k为不小于可能的值,即k为最大的权值1000
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;
}

//--------------------slect函数----------------------
void select(HuffmanTree t,int i,int &s1,int &s2)
{ // s1为最小的两个值中序号小的那个
int j;
s1=min(t,i);
s2=min(t,i);
if(s1>s2)
{
j=s1;
s1=s2;
s2=j;
}
}
// --------------算法6.12--------------------------
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{ // w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC
int m,i,s1,s2,start;
//unsigned c,f;
int c,f;
HuffmanTree p;
char *cd;
if(n<=1)
return;//检测结点数是否可以构成树
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0号单元未用
for(p=HT+1,i=1;i<=n;++i,++p,++w)
{
p->weight=*w;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(;i<=m;++i,++p)
p->parent=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); // 释放工作空间
}
//---------------------获取报文并写入文件---------------------------------
int InputCode()
{
//cout<<"请输入你想要编码的字符"<<endl;
FILE *tobetran;

if((tobetran=fopen("tobetran.txt","w"))==NULL)
{
cout<<"不能打开文件"<<endl;
return 0;
}
cout<<"请输入你想要编码的字符"<<endl;
gets(str);
fputs(str,tobetran);
cout<<"获取报文成功"<<endl;
fclose(tobetran);
return strlen(str);
}

//--------------初始化赫夫曼链表---------------------------------
void Initialization()
{ int a,k,flag,len;
a=0;
len=InputCode();
for(i=0;i<len;i++)
{k=0;flag=1;
cou[i-a].data=str[i];
cou[i-a].count=1;
while(i>k)
{
if(str[i]==str[k])
{
a++;
flag=0;
}
k++;
if(flag==0)
break;

}

if(flag)
{
for(j=i+1;j<len;j++)
{if(str[i]==str[j])
++cou[i-a].count;}
}

}
n=len-a;
for(i=0;i<n;i++)
{ cout<<cou[i].data<<" ";
cout<<cou[i].count<<endl;
}
for(i=0;i<=n;i++)
{*(z+i)=cou[i].data;
*(w+i)=cou[i].count;
}

/* 原来未修改的初始化程序段:
flag=1;
int num;
int num2;
cout<<"下面初始化赫夫曼链表"<<endl<<"请输入结点的个数n：";
cin>>num;
n=num;
w=(int*)malloc(n*sizeof(int));
z=(char*)malloc(n*sizeof(char));
cout<<"\n请依次输入"<<n<<"个字符(字符型)："<<endl;
char base[2];
for(i=0;i<n;i++)
{
cout<<"第"<<i+1<<"个字符:"<<endl;
gets(base);
*(z+i)=*base;
}
for(i=0;i<=n-1;i++)
{
cout<<setw(6)<<*(z+i);
}
cout<<"\n请依次输入"<<n<<"个权值："<<endl;
for(i=0;i<=n-1;i++)
{
cout<<endl<<"第"<<i+1<<"个字符的权值:";
cin>>num2;
*(w+i)=num2;
}*/
HuffmanCoding(HT,HC,w,n);
//------------------------打印编码-------------------------------------------
cout<<"字符对应的编码为:"<<endl;
for(i=1;i<=n;i++)
{
puts(HC[i]);
}
//--------------------------将赫夫曼编码写入文件------------------------
cout<<"下面将赫夫曼编码写入文件"<<endl<<"...................."<<endl;
FILE *htmTree;
char r[]={' ','\0'};
if((htmTree=fopen("htmTree.txt","w"))==NULL)
{
cout<<"can not open file"<<endl;
return;
}

fputs(z,htmTree);
for(i=0;i<n+1;i++)
{
fprintf(htmTree,"%6d",*(w+i));
fputs(r,htmTree);
}
for(i=1;i<=n;i++)
{
fputs(HC[i],htmTree);
fputs(r,htmTree);
}
fclose(htmTree);
cout<<"已将字符与对应编码写入根目录下文件htmTree.txt中"<<endl<<endl;
}
//---------------------编码函数---------------------------------
void Encoding()
{
cout<<"下面对目录下文件tobetran.txt中的字符进行编码"<<endl;

FILE *tobetran,*codefile;

if((tobetran=fopen("tobetran.txt","rb"))==NULL)
{
cout<<"不能打开文件"<<endl;
}
if((codefile=fopen("codefile.txt","wb"))==NULL)
{
cout<<"不能打开文件"<<endl;
}
char *tran;
i=99;
tran=(char*)malloc(100*sizeof(char));
while(i==99)
{
if(fgets(tran,100,tobetran)==NULL)
{
cout<<"不能打开文件"<<endl;
break;
}
for(i=0;*(tran+i)!='\0';i++)
{
for(j=0;j<=n;j++)
{
if(*(z+j-1)==*(tran+i))
{
fputs(HC[j],codefile);
if(j>n)
{
cout<<"字符错误，无法编码!"<<endl;
break;
}
}
}
}
}
cout<<"编码工作完成"<<endl<<"编码写入目录下的codefile.txt中"<<endl<<endl;
fclose(tobetran);
fclose(codefile);
free(tran);
}
//-----------------译码函数---------------------------------
void Decoding()
{
cout<<"下面对根目录下文件codefile.txt中的字符进行译码"<<endl;
FILE *codef,*txtfile;
if((txtfile=fopen("txtfile.txt","w"))==NULL)
{
cout<<"不能打开文件"<<endl;
}
if ((codef=fopen("codefile.txt","r"))==NULL)
{
cout<<"不能打开文件"<<endl;
}
char *work,*work2,i2;
int i4=0,i,i3;
unsigned long length=10000;
work=(char*)malloc(length*sizeof(char));
fgets(work,length,codef);
work2=(char*)malloc(length*sizeof(char));
i3=2*n-1;
for(i=0;*(work+i-1)!='\0';i++)
{
i2=*(work+i);
if(HT[i3].lchild==0)
{
*(work2+i4)=*(z+i3-1);
i4++;
i3=2*n-1;
i--;
}
else if(i2=='0') i3=HT[i3].lchild;
else if(i2=='1') i3=HT[i3].rchild;
}
*(work2+i4)='\0';
fputs(work2,txtfile);
cout<<"译码完成"<<endl<<"内容写入根目录下的文件txtfile.txt中"<<endl<<endl;
free(work);
free(work2);
fclose(txtfile);
fclose(codef);
}
//-----------------------打印编码的函数----------------------
void Code_printing()
{
cout<<"下面打印根目录下文件CodePrin.txt中编码字符"<<endl;
FILE * CodePrin,* codefile;
if((CodePrin=fopen("CodePrin.txt","w"))==NULL)
{
cout<<"不能打开文件"<<endl;
return;
}
if((codefile=fopen("codefile.txt","r"))==NULL)
{
cout<<"不能打开文件"<<endl;
return;
}

char *work3;
work3=(char*)malloc(51*sizeof(char));
do
{
if(fgets(work3,51,codefile)==NULL)
{
cout<<"不能读取文件"<<endl;
break;
}
fputs(work3,CodePrin);
puts(work3);
}while(strlen(work3)==50);
free(work3);
cout<<"打印工作结束"<<endl<<endl;
fclose(CodePrin);
fclose(codefile);
}
//-------------------------------打印译码函数---------------------------------------------
void Code_printing1()
{
cout<<"下面打印根目录下文件txtfile.txt中译码字符"<<endl;
FILE * CodePrin1,* txtfile;
if((CodePrin1=fopen("CodePrin1.txt","w"))==NULL)
{
cout<<"不能打开文件"<<endl;
return;
}
if((txtfile=fopen("txtfile.txt","r"))==NULL)
{
cout<<"不能打开文件"<<endl;
return;
}
char *work5;
work5=(char*)malloc(51*sizeof(char));
do
{
if(fgets(work5,51,txtfile)==NULL)
{
cout<<"不能读取文件"<<endl;
break;
}
fputs(work5,CodePrin1);
puts(work5);
}while(strlen(work5)==50);
free(work5);
cout<<"打印工作结束"<<endl<<endl;
fclose(CodePrin1);
fclose(txtfile);
}
//------------------------打印赫夫曼树的函数-----------------------
void coprint(HuffmanTree start,HuffmanTree HT)
{
if(start!=HT)
{
FILE * TreePrint;

if((TreePrint=fopen("TreePrint.txt","a"))==NULL)
{cout<<"创建文件失败"<<endl;
return;
}
numb++;//该变量为已被声明为全局变量
coprint(HT+start->rchild,HT);
cout<<setw(5*numb)<<start->weight<<endl;

fprintf(TreePrint,"%d\n",start->weight);
coprint(HT+start->lchild,HT);
numb--;
fclose(TreePrint);
}
}
void Tree_printing(HuffmanTree HT,int w)
{
HuffmanTree p;
p=HT+w;
cout<<"下面打印赫夫曼树"<<endl;
coprint(p,HT);
cout<<"打印工作结束"<<endl;
}
//------------------------主函数------------------------------------
void main()
{
char choice;
while(choice!='q')
{ cout<<"\n******************************"<<endl;
cout<<" 欢迎使用赫夫曼编码解码系统"<<endl;
cout<<"******************************"<<endl;
cout<<"(1)要初始化赫夫曼链表请输入'i'"<<endl;
cout<<"(2)要编码请输入'e'"<<endl;
cout<<"(3)要译码请输入'd'"<<endl;
cout<<"(4)要打印编码请输入'p'"<<endl;
cout<<"(5)要打印赫夫曼树请输入't'"<<endl;
cout<<"(6)要打印译码请输入'y'"<<endl;
if(flag==0)cout<<"\n请先初始化赫夫曼链表,输入'i'"<<endl;
cin>>choice;
switch(choice)
{
case 'i':
Initialization();
break;
case 'e':
Encoding();
break;
case 'd':
Decoding();
break;
case 'p':
Code_printing();
break;
case 't':
Tree_printing(HT,2*n-1);
break;
case 'y':
Code_printing1();
break;
default:
cout<<"input error"<<endl;
}

}
free(z);
free(w);
free(HT);
}

阅读全文

哈夫曼编码c语言实现

与哈夫曼编码c语言实现相关的阅读推荐