//赫夫曼编码程序（严蔚敏数据结构）
#include <iostream>
using namespace std;
typedef struct
{
int weight;
int parent,lchild,rchild;
}HTNode,HuffmanTree;
typedef char HuffmanCode;
typedef char EachHuffcode;
void Select(HuffmanTree HT,int length,int &s1,int &s2)
{
//s1 lowest,s2 lower
unsigned int min = 5000;
HuffmanTree p = HT;
int i;
for(i = 1, ++p; i <= length ; ++i,++p)
{
if(p->weight < min && p->parent == 0)
{
min = p->weight;
s1 = i;
}
}
min = 5000;
p = HT;
//Get the second less weight
for(i = 1, ++p; i <= length ; ++i,++p)
{
if(p->weight < min && p->parent == 0)
{
if( i == s1)//case s1,ignore
continue;
min = p->weight;
s2 = i;
}
}
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC, int w,int n)
{
if(n <= 1)
return;
int m = 2 n - 1;
HT = new HTNode[m + 1];//0 is not used
HuffmanTree p = HT;
int i;
for( i = 1, ++p; i <= n; ++i,++p,++w)
{
p->weight = w;//NOte: never use this p = {w,0,0,0,0},because p has already been declared
p->parent = p->lchild = p->rchild = 0;
}
for(; i <= m; ++i,++p)
p->weight = p->parent = p->lchild = p->rchild = 0;
int s1;
int s2;
for( i = n + 1; i <= m; ++i)
{
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 = new EachHuffcode[n+1];//0 is not used
char cd = new char[n];
cd[n-1] = '\0';//the end of each char
int start;
for(int i = 1; i <= n ; ++i)
{//get each huff code for h[1] to h[n]
start = n -1;
for(int c = i, int f = HT[i]parent; f != 0; c = f ,f = HT[f]parent)
if(c == HT[f]lchild) cd[--start] = '0';
else cd[--start] = '1';
HC[i] = new char[n - start];//allocate memory for each HT
strcpy(HC[i],&cd[start]);
}
delete []cd;//don't forget release memory
}
int main(int argc, char argv[])
{
HuffmanTree hftree = NULL;
HuffmanCode hfcode = NULL;
int weight[4] = {7,5,2,4};//four node's weight
HuffmanCoding(hftree,hfcode,weight,4);
EachHuffcode p = hfcode;
++p;
for (int i = 0; i < 4; ++i,++p)
{
cout<<p<<endl;//show each huffman code by each line
}
for(int i = 1; i <=4; ++i)
delete hfcode[i];//release memory
delete []hfcode;
delete []hftree;
return 0;
}
#include<stdioh>
#include<stringh>
#include<stdlibh>
#include<ctypeh>
int n;
struct node{
int w;
int flag;
char c;
struct node plink,llink,rlink;
char code[50];
}num[100],root;
FILE fp;
char tmpcode[50];
int t=0;
void main(void)
{
int i;
void settree(void); //建立树
void code(void); //对文件编码
void decode(void); // 译码
void disp(void);
root=(struct node)malloc(sizeof(struct node));
puts("哈夫曼编/译码器演示");
while(1){
start:
puts("1 初始化 2 编码 3 译码 4显示编码表 5 退出");
while(scanf("%d",&i)!=1)
{
while(getchar()!='\n')
continue;
puts("输入错误!");
puts("请重新输入！");
puts("1 初始化 2 编码 3 译码 4显示编码表 5 退出");
}
switch (i)
{
case 1:
settree();
break;
case 2:
code();
break;
case 3:
decode();
break;
case 4:
disp();
break;
case 5:
exit(0);
default:
puts("输入错误！");
puts("请重新输入！");
goto start;
}
}
}
void settree(void)
{
int i,j,k;
struct node p1,p2,tmp,p;
void go(struct node );
void setcode(struct node );//建立每一个字符的编码
void printtree(struct node );
puts("输入字符集的大小：");
scanf("%d",&n);
while(getchar()!='\n')
continue;
for(i=0;i<n;i++)
{
p=(struct node )malloc(sizeof(struct node));
puts("请输入一个字符");
scanf("%c",&p->c);
while(getchar()!='\n')
continue;
puts("请输入该字符的权值:");
scanf("%d",&p->w);
while(getchar()!='\n')
continue;
p->plink=NULL;
p->rlink=NULL;
p->llink=NULL;
num[i]=p;
}
for(i=0;i<n-1;i++) //（递增）排序
{
for(j=i+1;j<n;j++)
{
if(num[i]->w>num[j]->w)
{
tmp=num[i];
num[i]=num[j];
num[j]=tmp;
}
}
}
/开始建立树/
num[n]=NULL; //结束标志
k=n;
while(num[1]!=NULL)
{
p=(struct node )malloc(sizeof(struct node));
p1=num[0];
p2=num[1];
p->llink=p1;
p->rlink=p2;
p->plink=NULL;
p1->plink=p;
p2->plink=p;
p->w=p1->w+p2->w;
for(i=1;i<k;i++)
{
num[i]=num[i+1];
}
k--;
num[0]=p;
for(i=0;i<k-1;i++) //排序
{
for(j=i+1;j<k;j++)
{
if(num[i]->w>num[j]->w)
{
tmp=num[i];
num[i]=num[j];
num[j]=tmp;
}
}
}
}
root=num[0];
/建立完毕/
/写入文件，前序/
if((fp=fopen("c:\\hfmtreewxl","wb"))==NULL)
{
puts("文件打开错误！");
getchar();
exit(0);
}
setcode(root);
go(root);
fclose(fp);
}
void setcode(struct node p)
{
if(p->llink==NULL&&p->rlink==NULL)
{
tmpcode[t]='\0';
strcpy(p->code,tmpcode);
}
else
{
tmpcode[t++]='0';
setcode(p->llink);
t--;
tmpcode[t++]='1';
setcode(p->rlink);
t--;
}
}
void go(struct node p)
{
if(p->llink==NULL&&p->rlink==NULL)
{
fputc('(',fp);
fputc(p->c,fp);
fputs(p->code,fp);
fputc(')',fp);
}
else
{
go(p->llink);
go(p->rlink);
}
}
void code(void)
{
FILE fp1,fp2,fp3;
char ch1,ch2,c;
if((fp1=fopen("c:\\hfmtreewxl","rb"))==NULL)
{
puts("文件打开错误！");
getchar();
exit(0);
}
if((fp2=fopen("c:\\tobetranstxt","wb"))==NULL)
{
puts("文件打开错误！");
getchar();
exit(0);
}
if((fp3=fopen("c:\\codefilewxl","wb"))==NULL)
{
puts("文件打开错误！");
getchar();
exit(0);
}
while((ch1=fgetc(fp2))!=EOF)
{
t=0;
while((ch2=fgetc(fp1))!=EOF)
{
if(ch1==ch2)
{
while((c=fgetc(fp1))!=')')
{
tmpcode[t++]=c;
}
tmpcode[t]='\0';
fputs(tmpcode,fp3);
fputc('@',fp3);
rewind(fp1);
break;
}
}
}
fclose(fp1);
fclose(fp2);
fclose(fp3);
}
void decode(void)
{
FILE fp1,fp2,fp3;
char ch1,ch2,ch3;
char temp_3[20];
char temp_1[20];
int t1,t3;
if((fp1=fopen("c:\\hfmtreewxl","rb"))==NULL)
{
puts("文件打开错误！");
getchar();
exit(0);
}
if((fp2=fopen("c:\\textfiletxt","wb"))==NULL)
{
puts("文件打开错误！");
getchar();
exit(0);
}
if((fp3=fopen("c:\\codefilewxl","rb"))==NULL)
{
puts("文件打开错误！");
getchar();
exit(0);
}
while((ch3=fgetc(fp3))!=EOF)
{
t3=0;
while(ch3!='@')
{
temp_3[t3++]=ch3;
ch3=fgetc(fp3);
}
temp_3[t3]='\0';
while((ch1=fgetc(fp1))!=EOF)
{
if(isalpha(ch1))
{
ch2=ch1;
t1=0;
while((ch1=fgetc(fp1))!=')')
{
temp_1[t1++]=ch1;
}
temp_1[t1]='\0';
if(strcmp(temp_1,temp_3)==0)
{
fputc(ch2,fp2);
rewind(fp1);
break;
}
}
}
}
fclose(fp1);
fclose(fp2);
fclose(fp3);
}
void disp(void)
{
FILE fp1,fp2;
char ch1,ch2;
char tmp[20];
int t;
if((fp1=fopen("c:\\hfmtreewxl","rb"))==NULL)
{
puts("文件打开错误！");
getchar();
exit(0);
}
if((fp2=fopen("c:\\hfmcodetxt","wb"))==NULL)
{
puts("文件打开错误！");
getchar();
exit(0);
}
while((ch1=fgetc(fp1))!=EOF)
{
if(ch1=='(')
{
t=0;
ch1=fgetc(fp1);
ch2=ch1;
while((ch1=fgetc(fp1))!=')')
{
tmp[t++]=ch1;
}
tmp[t]='\0';
printf("%c-----%s\n",ch2,tmp);
fputc(ch2,fp2);
fputc('-',fp2);
fputc('-',fp2);
fputc('-',fp2);
fputs(tmp,fp2);
fputc('\n',fp2);
}
}
fclose(fp1);
fclose(fp2);
}
#ifndef Huffman_Tree_h
#define Huffman_Tree_h
#endif
#include <stdioh>
typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode, HuffmanTree; //存储赫夫曼树的结点类型
typedef char HuffmanCode; //用于存储字符集中各个字符相应的赫夫曼编码
void strcpy(char S1,char S2){ //将字符串S2复制到S1
int i = 0;
while( S2[i] != '\0' ){
S1[i] = S2[i];
i++;
}
S1[i] = '\0';
}
void Select(HuffmanTree HT,int t,int &s1,int &s2){ //在HT[1]到HT[t-1]中找出权值最小的两个S1和S2
int i = 1;
s1 = s2 = 0;
HT[0]weight = 65535;
while( i <= t ){ //遍历查找权值最小的结点S1
if( HT[i]parent == 0 && HT[i]weight < HT[s1]weight )
s1 = i;
i++;
}
i = 1;
while( i <= t ){ //遍历查找除S1外权值最小的结点S2
if( i != s1 && HT[i]parent == 0 && HT[i]weight < HT[s2]weight )
s2 = i;
i++;
}
}
int HuffmanCoding( HuffmanTree &HT,HuffmanCode &HC,int w,int n){ //根据各个字符的权值构造赫夫曼树HT，将对应的赫夫曼编码存储在HC中
int s1,s2,m,i,start;
unsigned int c,f;
HTNode p;
char cd;
if( n <= 1 ) return 0;
m = 2 n - 1; //赫夫曼树的总结点树为m
HT = (HuffmanTree)malloc((m + 1) sizeof(HTNode)); //申请存储赫夫曼树的空间
for(p = HT + 1, i = 1; i <= n; ++i, ++p, ++w){ //将各个叶子结点的weight赋以相应的权值，parent,lchild,rchild均赋为0
p->weight = (w+1);
p->parent = p->lchild = p->rchild = 0;
}
for( ; i <= m; ++i, ++p ){ //将各个非叶子结点的weight,parent,lchild,rchild均赋为0
p->weight = p->parent = p->lchild = p->rchild = 0;
}
for( i = n + 1; i <= m; ++i ){ //构造赫夫曼树，给各个非叶子结点赋值
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 )); //申请空间，用于存储指向存储各个字符相应赫夫曼编码的字符数组的指针
cd = (char )malloc(n sizeof(char)); //申请用于求赫夫曼编码
cd[n - 1] = '\0'; //编码结束符
for( i = 1; i <= n; ++i){ //逐个字符求赫夫曼编码
start = n -1; //编码在数组cd[]中的最前位置
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[]数组的start位置到n-1位置复制给HC[i]
}
free(cd); //释放空间
return 1;
}
以上为第一部分
#include <stdioh>
#include <stdlibh>
#include "Huffman_Treeh"
#define Yes 1 //当程序已经调用过初始化赫夫曼树的InitHuff_T()函数，或已从htfTree文件读取过，则将Init_Mode置为Yes，否则为No
#define No 0
void InitHuff_T( HuffmanTree &HT, HuffmanCode &HC, char ch[],int &n ){ //初始化赫夫曼数，要求用户输入字符和相应权值
int i = 1,w[100],tem,j;
char a[20];
FILE save;
printf("请输入编码字符集的大小n:");
scanf("%d",&n); //获取用户输入的字符集个数
while( i <= n ){ //获取用户输入的字符和相应权值，分别存储在ch[]和w[]数组中
printf("请输入第%d个字符和该字符的权值w:",i);
fflush(stdin);
scanf("%c%d",&ch[i],&w[i]);
i++;
}
ch[i] = '\0';
HuffmanCoding(HT,HC,w,n); //根据用户的输入，生成赫夫曼数及各个字符相应的赫夫曼编码，分别存在HT树和HC中
if(( save = fopen("htfTree","w")) == NULL ){ //打开用于存储赫夫曼树的文件
printf("Open file fail\n");
exit(0);
}
tem = n; //接下来的14行是将字符集大小转换成字符形式写入到文件中
j = 0;
while( tem != 0 ){
tem = tem / 10;
j++;
}
tem = n;
a[j] = '\0';
while( tem != 0 ){
a[j - 1] = (char)(tem % 10 + 48);
tem = tem / 10;
j--;
}
fputs(a,save);
printf("%d\n",n); //向屏幕输出字符集大小n
fputc('\n',save);
for( i = 1; i <= n; i++ ){ //分别向文件和屏幕输出各个字符和相应的赫夫曼编码
fputc(ch[i],save); printf("%c\t",ch[i]);
fputc('\t',save);
fputs(HC[i],save); printf("%s\n",HC[i]);
fputc('\n',save);
}
for(i = 1; i <= 2 n - 1; i++ ){ //将赫夫曼树各个结点的parent,lchild,rchild分别写入到文件中
tem = HT[i]parent; //将i结点的parent转换成字符并写入到文件中
if(tem == 0){
fputc(tem + 48,save);
fputc(' ',save);
}
else{
j = 0;
while( tem != 0 ){
tem = tem / 10;
j++;
}
tem = HT[i]parent;
a[j] = '\0';
while( tem != 0 ){
a[j - 1] = (char)(tem % 10 + 48);
tem = tem / 10;
j--;
}
fputs(a,save);
fputc(' ',save);
}
tem = HT[i]lchild; //将i结点的lchild转换成字符并写入到文件中
if(tem == 0){
fputc(tem + 48,save);
fputc(' ',save);
}
else{
j = 0;
while( tem != 0 ){
tem = tem / 10;
j++;
}
tem = HT[i]lchild;
a[j] = '\0';
while( tem != 0 ){
a[j - 1] = (char)(tem % 10 + 48);
tem = tem / 10;
j--;
}
fputs(a,save);
fputc(' ',save);
}
tem = HT[i]rchild; //将i结点的rchild转换成字符并写入到文件中
if(tem == 0){
fputc(tem + 48,save);
fputc('\n',save);
}
else{
j = 0;
while( tem != 0 ){
tem = tem / 10;
j++;
}
tem = HT[i]rchild;
a[j] = '\0';
while( tem != 0 ){
a[j - 1] = (char)(tem % 10 + 48);
tem = tem / 10;
j--;
}
fputs(a,save);
fputc('\n',save);
}
}
fclose(save);
}
void Encoding(HuffmanTree &HT, HuffmanCode &HC, char ch[]){ //根据赫夫曼编码将用户指定的文件中的字符编成相应的编码,并将所得编码存储到用户指定文件
FILE ToBeTran,CodeFile;
char ToBeTran_Name[100],CodeFile_Name[100]; //存储用户指定文件的文件名
int i;
char c;
printf("请输入所要进行编码的文件的文件名:");
scanf("%s",ToBeTran_Name); //获得所要进行编码的文件的文件名
if(( ToBeTran = fopen(ToBeTran_Name,"r")) == NULL ){ //打开文件
printf("Open file fail\n");
exit(0);
}
printf("请输入编码后编码表示的信息所存储到的文件的文件名:");
scanf("%s",CodeFile_Name); //获得编码后编码表示的信息所存储到的文件的文件名
if(( CodeFile = fopen(CodeFile_Name,"w")) == NULL ){ //打开文件
printf("Open file fail\n");
exit(0);
}
c = fgetc(ToBeTran); //从文件读取一个字符
while( c != EOF ){ //对文件中的各个字符进行编码，直至文件结尾
i = 1;
while( c != ch[i] && ch[i] != '\0' ) //在ch[]数组中查找从文件读取的字符
i++;
if(ch[i] == '\0'){ //未找到，c不在ch[]数组中，c无法被识别，程序出错，退出
printf("字符%c无法识别，程序将退出。\n",c);
exit(0);
}
fputs(HC[i],CodeFile); //若找到，则将c相应的赫夫曼编码写入到文件中
printf("%s",HC[i]); //将c相应的赫夫曼编码输出到屏幕
c = fgetc(ToBeTran); //读入文件中的下一个字符
}
printf("\n");
fclose(ToBeTran);
fclose(CodeFile);
}
void Decoding(HuffmanTree HT, char ch[] , int n){ //对指定的存储由赫夫曼编码表示的信息的文件进行译码，翻译成相应的字符表示，并存储到指定文件
int p,i = 1;
char code[1000],c;
char CodeFile_Name[100],TextFile_Name[100]; //存储用户指定文件的文件名
p = 2 n - 1;
FILE CodeFile,TextFile;
printf("请输入所要译的文件名:");
scanf("%s",CodeFile_Name); //获得所要译的文件的文件名
if(( CodeFile = fopen("CodeFile","r")) == NULL ){ //打开文件
printf("Open file fail\n");
exit(0);
}
printf("请输入译后的字符存储到的文件的文件名:");
scanf("%s",TextFile_Name); //获得译后的字符存储到的文件的文件名
if(( TextFile = fopen(TextFile_Name,"w")) == NULL ){ //打开文件
printf("Open file fail\n");
exit(0);
}
c = fgetc(CodeFile);
while( c != EOF ){
code[i] = c;
i++;
c = fgetc(CodeFile);
}
code[i] = '\0'; //从文件读取字符，存储在code[]数组中
i = 1;
while ( code[i] != '\0' && p != 0 ){ //对数组code[]中的赫夫曼编码进行译码
if ( code[i] == '0' )
p=HT[p]lchild; //进入左分支
else
p = HT[p]rchild; //进入右分支
if (!HT[p]lchild&& !HT[p]rchild){ //进入叶子结点
fputc(ch[p], TextFile); //将相应的字符写入到文件中
printf("%c",ch[p]); //将相应的字符输出到屏幕
p = 2 n - 1; //重新从树根出发进行译码
}
i++;
}
printf("\n");
}
void ReadHuff_T( HuffmanTree &HT, HuffmanCode &HC, char ch[], int &n){ //从文件读取赫夫曼树
FILE htfTree;
char c[100],ch1;
int i,j,t;
if(( htfTree = fopen("htfTree","r")) == NULL ){ //打开存有赫夫曼树信息的文件
printf("Open file fail\n");
exit(0);
}
fgets(c,10,htfTree); //获取赫夫曼树叶子结点个数的字符串表示形式
i = 0; //以下6行将字符串形式转换成整数形式
while( c[i] != '\n' )
i++;
n = 0;
for( j = 0; j < i; j++ )
n = 10 n + c[j] - '0'; //求出叶子结点数n
HC = (HuffmanCode)malloc((n + 1) sizeof(char )); //申请HC空间
HT = (HuffmanTree)malloc((2 n) sizeof(HTNode)); //申请赫夫曼树存储空间
i = 1;
while( i <= n ){
ch[i] = fgetc(htfTree); //读取字符集中的一个字符
HC[i] = (char )malloc((10)sizeof(char)); //申请用于存储读取到的字符集中的字符的赫夫曼编码的空间
fgetc(htfTree); //将‘\t’输出
ch1 = fgetc(htfTree); //读取赫夫曼编码，存储在相应的HC[i][]数组里
int j = 0;
while( ch1 != '\n' ){
HC[i][j] = ch1;
j++;
ch1 = fgetc(htfTree);
}
HC[i][j] = '\0';
i++;
}
ch[i] = '\0';
i = 0;
while( i < 2 n - 1 ){ //读取赫夫曼树的各个结点的parent,lchild,rchild并赋值到赫夫曼树HT中
ch1 = fgetc(htfTree); //读取parent的字符串形式,存储在c[]中，并将其转换成整数形式，赋给HT[i]parent
j = 0;
while( ch1 != ' ' ){
c[j] = ch1;
j++;
ch1 = fgetc(htfTree);
}
HT[i+1]parent = 0;
for( t = 0; t < j; t++ )
HT[i+1]parent = 10 HT[i+1]parent + c[t] - '0';
ch1 = fgetc(htfTree); //读取lchild的字符串形式，并将其转换成整数形式，赋给HT[i]lchild
j = 0;
while( ch1 != ' ' ){
c[j] = ch1;
j++;
ch1 = fgetc(htfTree);
}
HT[i+1]lchild = 0;
for( t = 0; t < j; t++ )
HT[i+1]lchild = 10 HT[i+1]lchild + c[t] - '0';
ch1 = fgetc(htfTree); //读取rchild的字符串形式，并将其转换成整数形式，赋给HT[i]rchild
j = 0;
while( ch1 != '\n' ){
c[j] = ch1;
j++;
ch1 = fgetc(htfTree);
}
HT[i+1]rchild = 0;
for( t = 0; t < j; t++ )
HT[i+1]rchild = 10 HT[i+1]rchild + c[t] - '0';
i++;
}
}
int main(){
HuffmanTree HT;
HuffmanCode HC;
char ch[100]; //用于存储字符集
int n,Init_Mode = No; //n为字符集的大小，Init_Mode = No 表示内存中没有赫夫曼树的信息
char mode; //让用户选择不同的 *** 作
printf("请输入你要选择的功能\n");
printf("\t\tI -- 初始化\t\tE -- 编码\n");
printf("\t\tD -- 译码 \t\tQ -- 退出程序\n");
scanf("%c",&mode); //获得用户选择的 *** 作
while( mode != 'Q' && mode != 'q' ){ //当用户输入不为Q或q时，执行相应 *** 作
switch(mode){
case 'I' :
InitHuff_T(HT,HC,ch,n);
Init_Mode = Yes;
break;
case 'i' :
InitHuff_T(HT,HC,ch,n);
Init_Mode = Yes;
break;
case 'E' :
if( No == Init_Mode )
ReadHuff_T(HT,HC,ch,n);
Encoding(HT,HC,ch);
Init_Mode = Yes;
break;
case 'e' :
if( No == Init_Mode )
ReadHuff_T(HT,HC,ch,n);
Encoding(HT,HC,ch);
Init_Mode = Yes;
break;
case 'D' :
if( No == Init_Mode )
ReadHuff_T(HT,HC,ch,n);
Decoding(HT,ch,n);
Init_Mode = Yes;
break;
case 'd' :
if( No == Init_Mode )
ReadHuff_T(HT,HC,ch,n);
Decoding(HT,ch,n);
Init_Mode = Yes;
default :
printf("您的输入有错，请重新选择\n");
}
printf("请输入你要选择的功能\n");
printf("\tI -- 初始化\tE -- 编码\n");
printf("\tD -- 译码 \tQ -- 退出程序\n");
fflush(stdin);
scanf("%c",&mode); //让用户继续选择相应的 *** 作，直至用户选择退出
}
return 0;
}
第二部分
1。进vc++60
2。新建一个新工程 选择Win32 Console application
一个空工程 确认
3。新建一个c++源文件 命名为Huffman_Treeh 记住 命名很重要 然后将第一部分烤贝 粘贴 一定得是这个名字 然后编译保存
4。在新建一个c++源文件命名为 赫夫曼cpp 然后将第二部分拷贝 粘贴 编译保存 然后就大功告成了 可以执行了
需要注意的是 编译后生成的可执行文件保存在 你新建工程是的那个默认文件夹里 当然你也可以在新建工程是选择你想要保存可执行文件的文件夹 方便查找
哈夫曼在上世纪五十年代初就提出这种编码时，根据字符出现的概率来构造平均长度最短的编码。它是一种变长的编码。在编码中，若各码字长度严格按照码字所对应符号出现概率的大小的逆序排列，则编码的平均长度是最小的。（注：码字即为符号经哈夫曼编码后得到的编码，其长度是因符号出现的概率而不同，所以说哈夫曼编码是变长的编码。） 而且哈夫曼编码是按照子树到父亲，而其读码则是完全相反的。 因此，后来有人提出了一种动态的哈夫曼编码方法。动态哈夫曼编码使用一棵动态变化的哈夫曼树，对第t+1个字符的编码是根据原始数据中前t个字符得到的哈夫曼树来进行的，编码和解码使用相同的初始哈夫曼树，每处理完一个字符，编码和解码使用相同的方法修改哈夫曼树，所以没有必要为解码而保存哈夫曼树的信息。编码和解码一个字符所需的时间与该字符的编码长度成正比，所以动态哈夫曼编码可实时进行。动态哈夫曼编码比静态哈夫曼编码复杂的多，有兴趣的读者可参考有关数据结构与算法的书籍。
前面提到的JPEG中用到了哈夫曼编码，并不是说JPEG就只用哈夫曼编码就可以了，而是一幅经过多个步骤后得到它的一列数值，对这些数值进行哈夫曼编码，以便存储或传输。哈夫曼编码方法比较易懂，大家可以根据它的编码方法，自己编写哈夫曼编码和解码的程序。
哈夫曼树的构造算法。
const maxvalue= 10000; {定义最大权值}
maxleat=30; {定义哈夫曼树中叶子结点个数}
maxnode=maxleaf2-1;
type HnodeType=record
weight: integer;
parent: integer;
lchild: integer;
rchild: integer;
end;
HuffArr:array[0maxnode] of HnodeType;
var ……
procedure CreatHaffmanTree(var HuffNode: HuffArr); {哈夫曼树的构造算法}
var i,j,m1,m2,x1,x2,n: integer;
begin
readln(n); {输入叶子结点个数}
for i:=0 to 2n-1 do {数组HuffNode[ ]初始化}
begin
HuffNodeweight=0;
HuffNodeparent=-1;
HuffNodelchild=-1;
HuffNoderchild=-1;
end;
for i:=0 to n-1 do read(HuffNodeweight); {输入n个叶子结点的权值}
for i:=0 to n-1 do {构造哈夫曼树}
begin
m1:=MAXVALUE; m2:=MAXVALUE;
x1:=0; x2:=0;
for j:=0 to n+i-1 do
if (HuffNode[j]weight<m1) and (HuffNode[j]parent=-1) then
begin m2:=m1; x2:=x1;
m1:=HuffNode[j]weight; x1:=j;
end
else if (HuffNode[j]weight<m2) and (HuffNode[j]parent=-1) then
begin m2:=HuffNode[j]weight; x2:=j; end;
{将找出的两棵子树合并为一棵子树}
HuffNode[x1]parent:=n+i; HuffNode[x2]parent:=n+i;
HuffNode[n+i]weight:= HuffNode[x1]weight+HuffNode[x2]weight;
HuffNode[n+i]lchild:=x1; HuffNode[n+i]rchild:=x2;
end;
end;
呵呵，分数太少了啊。代码贴给你了，测试没问题#include "stdafxh"
// Huffmancpp : 定义控制台应用程序的入口点。
//
#include <stdioh>
#include <stringh>
#define N 50 /叶子结点数/
#define M 2N-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<2n-1;i++) /所有结点的相关域置初值-1/
ht[i]parent=ht[i]lchild=ht[i]rchild=-1;
for (i=n;i<2n-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++) /根据哈夫曼树求哈夫曼编码/
{
hcstart=n;c=i;
f=ht[i]parent;
while (f!=-1) /循序直到树根结点/
{
if (ht[f]lchild==c) /处理左孩子结点/
hccd[hcstart--]='0';
else /处理右孩子结点/
hccd[hcstart--]='1';
c=f;f=ht[f]parent;
}
hcstart++; /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]weightj;
printf("\n");
}
printf("\n 平均长度=%g\n",10sum/m);
}
void main()
{
int i, n=4;
char str[]={"A","B","C","D"};
int fnum[]={1,3,4,7}; 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");
system("pause");
}
以上就是关于香农、费诺、哈夫曼、循环码编码全部的内容，包括:香农、费诺、哈夫曼、循环码编码、哈夫曼编码问题，高手帮我、求数据结构哈夫曼编码译码器等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）