哈夫曼樹c語言
『壹』 數據結構 c語言版 哈弗曼樹 實驗
#include<iostream>
#include<iomanip>
#include<string>
#include<windows.h>
usingnamespacestd;
typedefstruct{//定義哈夫曼樹個結點
intweight;//權值
intparent,lchild,rchild;//雙親，左右孩子結點下標
chardata;//儲存相關的字元信息
}HTNode,*HuffmanTree;//動態分配數組存儲哈夫曼編碼樹
typedefchar**HuffmanCode;//動態分配數組存儲哈夫曼編碼表
voidstatistics(char*a,int*w,char*d,int&n)//統計字元
{
intj=0;
intk;
for(inti=0;i<100&&a[i]!=' ';i++){
for(k=0;k<j;k++){
if(a[i]==d[k])
{ w[k]++;
break;
}
}
if(k==j){
d[j]=a[i];
w[j]++;
j++;}
}
n=j;
d[j]=' ';
}
voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn,char*d)//w存放n個字元的權值，構造哈夫曼樹HT，並求出n個字元的哈夫曼編碼HC
{if(n<=1)return;
intm=2*n-1;//m為結點數，一棵有n個葉子結點的哈夫曼樹共有2n-1個結點，可以儲存一個大小為2n-1的一維數組中
HT=newHTNode[m+1];
HuffmanTreep;
inti;
for(p=HT+1,i=1;i<=n;i++,++p)//初始化哈夫曼樹
{ p->data=d[i-1];
p->lchild=p->parent=p->rchild=0;
p->weight=w[i-1]; }
for(;i<=m;++i,++p) {
p->lchild=p->parent=p->rchild=0;
p->weight=0; }
for(i=n+1;i<=m;++i){//建立哈夫曼樹
ints1,s2,u,t;
for(u=1;u<=i-1;u++)if(HT[u].parent==0){s1=u;break;}
for(u=u+1;u<=i-1;u++) {
if(HT[s1].weight>HT[u].weight&&HT[u].parent==0)
s1=u; }
for(t=1;t<=i-1;t++)
if(HT[t].parent==0&&t!=s1){s2=t;break;}
for(t=t+1;t<=i-1;t++)
{ if(HT[s2].weight>HT[t].weight&&HT[t].parent==0&&t!=s1)
s2=t; }
HT[s1].parent=i;HT[s2].parent=i;//parent為0且weight最小的的兩個結點，一個為s1,一個為s2
HT[i].lchild=s1;HT[i].rchild=s2;//左孩子權值小，右孩子權值大
HT[i].weight=HT[s1].weight+HT[s2].weight; }
HC=newchar*[n+1]; //分配n個字元編碼指針
char*cd=newchar[n];//分配編碼的工作空間
cd[n-1]=' ';//編碼結束符
intstart,c,f;
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';//判斷是左孩子還是右孩子（左為0右為1）
elsecd[--start]='1';
HC[i]=newchar[n-start];//為第i個字元分配空間
strcpy(HC[i],&cd[start]); }//講cd[]數組的start位置到n-1位置復制給HC[i]
delete(cd);}//釋放空間
voidmain()
{
chara[100];
chard[100];charbc[1000];
intw[100],n=0;
HuffmanTreeHT;
HuffmanCodeHC;
cout<<"請輸入字元： ";
cin>>a;
for(intak=0;ak<100;ak++)w[ak]=0;
statistics(a,w,d,n);//統計
HuffmanCoding(HT,HC,w,n,d);
cout<<"霍夫曼編碼為："<<endl;
cout<<"原碼"<<"權值"<<"二進制碼"<<endl;
system("pause");
}
請採納，謝謝
『貳』 數據結構中哈夫曼樹的應用（C語言）
#include<stdio.h>
#include<stdlib.h>
typedef int DataType;
#define MaxValue 10000
#define MaxBit 10
#define MaxN 100
#define N 100;
int n1=0;
char c[100];
typedef struct Node
{
DataType data;
struct Node *leftChild;
struct Node *rightChild;
}BiTreeNode;
typedef struct
{
int weight;
int flag;
int parent;
int leftChild;
int rightChild;
}HaffNode;
typedef struct
{
int bit[MaxN];
int start;
int weight;
}Code;
struct worder
{
char words; /*字元*/
}word[100];
struct weighted
{
int weighter; /*轉換權值有利於文件的存儲*/
}weight[100] ;
void Initiate(BiTreeNode **root) /*初始化二叉樹*/
{
*root=(BiTreeNode * )malloc(sizeof(BiTreeNode));
(*root)->leftChild=NULL;
(*root)->rightChild=NULL;
}
BiTreeNode *InsertLeftNode(BiTreeNode *curr,DataType x) /*插入左子樹*/
{
BiTreeNode *s,*t;
if(curr==NULL) return NULL;
t=curr->leftChild;
s=(BiTreeNode *)malloc(sizeof(BiTreeNode));
s->data=x;
s->leftChild=t;
s->rightChild=NULL;
curr->leftChild=s;
return curr->leftChild;
}
BiTreeNode *InsertRightNode(BiTreeNode *curr ,DataType x) /*插入右子樹*/
{
BiTreeNode *s,*t;
if(curr==NULL)
return NULL;
t=curr->rightChild;
s=(BiTreeNode *)malloc(sizeof(BiTreeNode));
s->data=x;
s->rightChild=t;
s->leftChild=NULL;
curr->rightChild=s;
return curr->rightChild;
}
void Haffman(int weigh[],int n,HaffNode haffTree[],int a[][3]) /*建立哈夫曼樹*/
{
int i,j,m1,m2,x1,x2;
for(i=0;i<2*n-1;i++)
{
if(i<n)
haffTree[i].weight=weigh[i];
else haffTree[i].weight=0;
haffTree[i].parent=-1;
haffTree[i].flag=0;
haffTree[i].leftChild=-1;
haffTree[i].rightChild=-1;
}
for(i=0;i<n-1;i++)
{
m1=m2=MaxValue;
x1=x2=0;
for(j=0;j<n+i;j++)
{
if(haffTree[j].weight<m1&&haffTree[j].flag==0)
{
m2=m1;
x2=x1;
m1=haffTree[j].weight;
x1=j;
}
else if(haffTree[j].weight<m2&&haffTree[j].flag==0)
{
m2=haffTree[j].weight;
x2=j;
}
}
haffTree[x1].parent=n+i;
haffTree[x2].parent=n+i;
haffTree[x1].flag=1;
haffTree[x2].flag=1;
haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight;
haffTree[n+i].leftChild=x1;
haffTree[n+i].rightChild=x2;
a[i+1][0]=haffTree[x1].weight;
a[i+1][1]=haffTree[x2].weight; /*將每個權值賦值給二維數組a[][],利用這個二維數組可以進行建立二叉樹*/
a[i+1][2]=haffTree[n+i].weight;
}
}
void HaffmanCode(HaffNode haffTree[],int n,Code haffCode[]) /*對已經建立好的哈夫曼樹進行編碼*/
{
Code *cd=(Code *)malloc(sizeof(Code));
int i,j,child,parent;
for(i=0;i<n;i++)
{
cd->start=n-1;
cd->weight=haffTree[i].weight;
child=i;
parent=haffTree[child].parent;
while(parent!=-1)
{
if(haffTree[parent].leftChild==child)
cd->bit[cd->start]=0;
else
cd->bit[cd->start]=1;
cd->start--;
child=parent;
parent=haffTree[child].parent;
}
for(j=cd->start+1;j<n;j++)
haffCode[i].bit[j]=cd->bit[j];
haffCode[i].start=cd->start+1;
haffCode[i].weight=cd->weight;
}
}
void PrintBiTree(BiTreeNode *bt ,int n) /*將哈夫曼樹轉換成的二叉樹進行列印*/
{
int i;
if(bt==NULL)
return;
PrintBiTree(bt->rightChild,n+1);
for(i=0;i<n;i++)
printf(" ");
if(bt->data!=0&&bt->data<100)
{
if(n>0)
{
printf("---");
printf("%d\n\n",bt->data);
}
}
PrintBiTree(bt->leftChild,n+1);
}
int search(int a[][3],int m) /*查找和a[][2]相等的權值*/
{
int i=1;
if(m==1) return 0;
while(a[i][2]!=a[m][0]&&i<m)
i++;
if(i==m) return 0; /*查找失敗返回數字0 查找成功返回和a[][2]相等的數的行數 i*/
else return i;
}
int searcher(int a[][3],int m) /*查找和a[][1]相等的權值*/
{
int i=1;
if(m==1) return 0;
while(a[i][2]!=a[m][1]&&i<m) /*查找失敗返回數字0 查找成功返回和a[][1]相等的數的行數 i*/
i++;
if(i==m) return 0;
else return i;
}
void creat(BiTreeNode *p,int i,int a[][3]) /*建立哈夫曼樹*/（利用遞歸）
{
int m,n;
BiTreeNode *p1,*p2,*p3;
if(i<=0) return;
p1=p;
if(a[i][0]!=a[i][1]) /*如果a[][0]和a[][1]不相等*/
{
p2=InsertLeftNode(p,a[i][0]); /*a[][0]為左子樹*/
n=search(a,i);
if(n)
creat(p2,n,a);
p3=InsertRightNode(p1,a[i][1]); /*a[][1]為右子樹*/
m=searcher(a,i);
if(m)
creat(p3,m,a);
} /*如果a[][0]和a[][1]相等則只要進行一個的查找*/
else
{
p2=InsertLeftNode(p,a[i][1]);
n=searcher(a,i);
if(n)
creat(p2,n,a);
p3=InsertRightNode(p1,a[i][1]);
}
}
void code(Code myHaffCode[],int n ) /*編碼*/
{
FILE *fp,*fp1,*fp2;
int i=0,k,j;
int text_len = strlen(c);
int *p2;
struct worder *p1;
if((fp2=fopen("CodeFile","wb"))==NULL) /*建立存儲編碼的文件*/
{
printf("Error,cannot open file\n" );
exit(0);
}
if((fp1=fopen("hfmTree","rb"))==NULL) /*讀取存儲字元的文件*/
{
printf("\n\n Please,increase records first~!! \n" );
return;
}
for(p1=word;p1<word+n;p1++)
{
fread(p1,sizeof(struct worder),1,fp1) ;
printf("word=%c Weight=%d Code=",p1->words,myHaffCode[i].weight); /*輸出每個權值的編碼*/
for(j=myHaffCode[i].start;j<n;j++)
printf("%d",myHaffCode[i].bit[j]);
printf("\n");
printf("\n");
i++;
}
j=0;
printf("\n\nThe codes :") ;
for(i=0;i< text_len;i++)
{
while(c[i]!=word[j].words) /*查找字元找到對應的編碼*/
{
j++;
}
for(k=myHaffCode[j].start;k<n;k++)
{
printf("%d",myHaffCode[j].bit[k]); /*輸出相應的編碼*/
fprintf(fp2,"%d",myHaffCode[j].bit[k]);
}
j=0;
}
fclose(fp2);
}
void sava(int n) /*建立文件*/
{
FILE *fp,*fp1,*fp2;
int *p2,i,j;
struct worder *p1;
struct weighted *p3;
if((fp2=fopen("NO.","wb"))==NULL) /*建立存儲權值個數的文件*/
{
printf("Error,cannot open file\n" );
exit(0);
}
fprintf(fp2,"%d",n) ;
if((fp=fopen("hfmTree","wb"))==NULL) /*建立存儲字元的文件*/
{
printf("Error,cannot open file\n" );
exit(0);
}
for(p1=word;p1<word+n;p1++)
{
if(fwrite(p1,sizeof(struct worder),1,fp)!=1)
printf("file write error\n");
}
fclose(fp);
if((fp1=fopen("hfmTree-1","wb"))==NULL) /*建立存儲權值的文件*/
{
printf("Error,cannot open file\n" );
exit(0);
}
for(p3=weight;p3<weight+n;p3++)
{
if(fwrite(p3,sizeof(struct weighted),1,fp1)!=1)
printf("file write error\n");
}
fclose(fp1);
printf("Please input any key !\n") ;
printf("Please input any key !\n") ;
if(n>MaxN)
{
printf("error!\n\n");
exit(0);
}
}
void menu() /*界面*/
{
printf("\n\n\n\t\t*************************************\n\n");
printf("\t\t\t1. To Code:\n\n"); /*編碼*/
printf("\t\t\t2. Decoding:\n\n"); /*解碼*/
printf("\t\t\t3. Output the huffman Tree:\n\n"); /*列印哈夫曼樹*/
printf("\t\t\t4. New data\n\n");
printf("\t\t\t5. Quit up...\n\n");
printf("\n\t\t************************************\n\n");
printf("Input you choice :\n");
}
void main()
{ FILE *fp,*fp1,*fp2,*fp3,*fp4;
int i,j;
int b[100][3],m=100,n,w,k=0,weigh[100];
struct worder *d;
struct weighted *p2;
char h;
BiTreeNode *root,*p;
HaffNode *myHaffTree=(HaffNode *)malloc(sizeof(HaffNode)*(2*m+1));
Code *myHaffCode=(Code *)malloc(sizeof(Code)*m);
Initiate(root);
if(((fp1=fopen("hfmTree","rb"))==NULL)&&((fp=fopen("hfmTree-1","rb"))==NULL))
{
loop:
printf("how many number do you want input?\n");
scanf("%d",&n);
if((fp=fopen("hfmTree-1","wb"))==NULL)
{
printf("Error,cannot open file\n" );
exit(0);
}
for(i=0;i<n;i++)
{
printf("\nword[%d]=",i) ;
scanf("%s",&word[i].words) ;
printf("\nweight[%d]=",i);
scanf("%d",&weight[i].weighter);
}
sava(n) ;
}
else
{
if((fp3=fopen("NO.","rb"))==NULL)
{
printf("\n\n Please,increase records first~!! \n" );
return;
}
fscanf(fp3,"%d",&n);
if((fp=fopen("hfmTree-1","rb"))==NULL)
{
printf("\n\n Please,increase records first~!! \n" );
return;
}
for(p2=weight;p2<weight+n;p2++)
{
fread(p2,sizeof(struct weighted),1,fp) ;
weigh[k]=p2->weighter ;
k++;
}
Haffman(weigh,n,myHaffTree,b);
HaffmanCode(myHaffTree,n,myHaffCode);
while(1)
{
do
{
clrscr();
menu();
scanf("%d",&w);
}while(w!=1&&w!=2&&w!=3&&w!=4&&w!=5);
switch(w)
{
case 1: clrscr();
printf("plesase input :\n");
scanf("%s",&c) ;
if((fp2=fopen("ToBeTran","wb"))==NULL)
{
printf("Error,cannot open file\n" );
exit(0);
}
fprintf(fp2,"%s",c) ;
fclose (fp2);
code(myHaffCode,n) ;
getch();
break;
case 2: if((fp2=fopen("ToBeTran","rb"))==NULL)
{
printf("\n\n Please,increase records first~!! \n" );
return;
}
fscanf(fp2,"%s",&c);
printf("The words:");
printf("%s",c);
if((fp4=fopen("TextFile.","wb"))==NULL)
{
printf("Error,cannot open file\n" );
exit(0);
}
fprintf(fp4,"%s",c) ;
fclose (fp4);
getch();
break;
case 3: clrscr();
printf("The huffman Tree:\n\n\n\n\n\n");
p=InsertLeftNode(root,b[n-1][2]);
creat(p,n-1,b);
PrintBiTree(root->leftChild,n);
printf("\n");
getch();
clrscr();
break;
case 4:goto loop;
case 5:exit(0);
}
}
}
getch();
}
『叄』 C語言 編寫哈弗曼樹
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define M 10000
typedef struct {
unsigned int weight;
unsigned int lchild,rchild,parent;
}HTNode,*HuffmanTree;
typedef char* *HuffmanCode;
//找到權值最小的兩個結點
void select(HuffmanTree HT,int k,int &s1,int &s2)
{
int j;
s1=s2=k;
for(j=0;j<k;j++)
if(HT[j].parent==0)
{
if(HT[j].weight<HT[s1].weight)
{
s2=s1;
s1=j;
}
else if(HT[j].weight<HT[s2].weight)
s2=j;
}
}
//構造哈夫曼樹
void CreateHuffmanTree(HuffmanTree &HT,int *w,int n)
{
int m,i,s1,s2;
HuffmanTree p;
m=2*n-1;
HT=(HuffmanTree)malloc(m*sizeof(HTNode));
for(p=HT,i=0;i<n;i++,p++,w++)
{
p->lchild=p->parent=p->rchild=0;
p->weight=*w;
}
for(i=n;i<m;i++,p++)
p->lchild=p->parent=p->rchild=p->weight=0;
for(i=n;i<m;i++)
{
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;
}
}
void print(HuffmanTree HT,char *u,int n)
{
int i;
char a;
printf("No\tchar\tweight\tlchild\trchild\tparent\n");
for(i=0;i<2*n-1;i++)
{
if(i<n)
a=u[i];
else a='-';
printf("%d\t%c\t%d\t%d\t%d\t%d\n",i,a,HT[i].weight,HT[i].lchild,HT[i].rchild,HT[i].parent);
}
}
//編碼哈夫曼樹
void Huffmancoding(HuffmanTree HT,HuffmanCode &HC,int n)
{
int i,c,start;
int f;
char *cd;
HC=(HuffmanCode)malloc(n*sizeof(char *));
cd=(char *)malloc((n-1)*sizeof(char));
cd[n-1]='\0';
for(i=0;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));
strcpy(HC[i],&cd[start]);
}
}
//編碼
void code(HuffmanCode HC,char *u,char *v)
{
int i,j;
for(i=0;i<strlen(v);i++)
for(j=0;j<strlen(u);j++)
if(v[i]==u[j])
{
printf("%s",HC[j]);
break;
}
}
//解碼
void recode(HuffmanCode HC,int n,char *u,char *v)
{
int i,j,k;
char *p;
i=0;
p=v;
while(i<strlen(v))
{
for(j=0;j<n;j++)
{
char temp[M]={0};
strncpy(temp,p,strlen(HC[j]));
if(strcmp(temp,HC[j])==0)
{
printf("%c",u[j]);
break;
}
}
p+=strlen(HC[j]);
i+=strlen(HC[j]);
}
}
main ()
{
HuffmanTree HT;
HuffmanCode HC;
int n,i;
int *w;
char *u,*v;
u=(char *)malloc(M*sizeof(char));
v=(char *)malloc(M*sizeof(char));
w=(int *)malloc(M*sizeof(int));
printf("請輸入字元數:");
scanf("%d",&n);
printf("請輸入字元:\n");
scanf("%s",u);
printf("請輸入對應的權值:\n");
for(i=0;i<n;i++)
scanf("%d",&w[i]);
CreateHuffmanTree(HT,w,n);
Huffmancoding(HT,HC,n);
printf("各字元對應的編碼:\n");
for(i=0;i<n;i++)
printf("%c: %s ",u[i],HC[i]);
printf("\n");
printf("輸出哈夫曼樹:\n");
print(HT,u,n);
free(w);
//編碼
printf("待發送信息:\n");
scanf("%s",v);
printf("編碼:\n");
code(HC,u,v);
//解碼
printf("\n接收到的編碼:\n");
scanf("%s",v);
printf("原文:\n");
recode(HC,n,u,v);
printf("\n");
}
『肆』 怎麼樣用c語言程序編碼哈夫曼樹
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include <ctype.h>
#include<limits.h>
int function1(char ch,char *s)
{
int i;
for(i=0; s[i]!='\0'; i++)
{
if(ch==s[i])return 0;
}
return 1;
}
typedef struct
{
unsigned int weight;
unsigned int parent,lchild,rchild;
} HTNode,*HuffmanTree; // 動態分配數組存儲赫夫曼樹
typedef char **HuffmanCode; // 動態分配數組存儲赫夫曼編碼表
// algo6-1.cpp 求赫夫曼編碼。實現演算法6.12的程序
int min(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為最小的兩個值中序號小的那個
s1=min(t,i);
s2=min(t,i);
/* if(s1>s2)
{
j=s1;
s1=s2;
s2=j;
}*/
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) // 演算法6.12
{
// w存放n個字元的權值(均>0),構造赫夫曼樹HT,並求出n個字元的赫夫曼編碼HC
int m,i,s1,s2,start;
unsigned 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].rchild=s1;
HT[i].lchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
// printf("HT[%d].lchild:%d HT[%d].rchild:%d\n",i,s2,i,s1);
}
// 從葉子到根逆向求每個字元的赫夫曼編碼
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]='1';
else
cd[--start]='0';
HC[i]=(char*)malloc((n-start)*sizeof(char));
// 為第i個字元編碼分配空間
strcpy(HC[i],&cd[start]); // 從cd復制編碼(串)到HC
}
free(cd); // 釋放工作空間
}
void swap1(int *a ,int *b)
{
int t;
t=*a;
*a=*b;
*b=t;
}
void swap2(char *a,char *b)
{
char ch;
ch=*a;
*a=*b;
*b=ch;
}
int main(void)
{
HuffmanTree HT;
HuffmanCode HC;
char *s1,*s2;
int i,j=0,n,count,*m,t,flag=1;
scanf("%d",&n);
getchar();
s1=(char*)malloc((n+n)*sizeof(char));
s2=(char*)malloc(n*sizeof(char));
memset(s2,'\0',n*sizeof(char));
gets(s1);
count=strlen(s1);
for(i=0; i<count; i++)
{
if(!isspace(*(s1+i)))
{
if(function1(*(s1+i),s2))
{
*(s2+j)=*(s1+i);
j++;
}
}
else;
}
m=(int*)malloc(j*sizeof(int));
for(i=0; i<j; i++)
*(m+i)=0;
for(t=0; t<j; t++)
{
for(i=0; i<count; i++)
{
if(*(s2+t)==*(s1+i))
*(m+t)+=1;
}
}
for(i=0;i<j;i++)
while(flag)
{
flag = 0;
for (t=0; t<j-1; t++)
{
if(*(m+t)<*(m+t+1))
{
swap1(m+t,m+t+1);
swap2(s2+t,s2+t+1);
flag=1;
}
}
}
HuffmanCoding(HT,HC,m,j);
for(i=1,t=0; i<=j; i++,t++)
{
printf("%c %d %s\n",*(s2+t),*(m+t),HC[i]);
}
return 0;
}
『伍』 創建一個哈夫曼樹並且進行編碼權重如下w={5，29，7 8，14，13 ，3 ，11}寫出c語言代碼
#include"stdafx.h"
#include"hfm.h"
#include<string.h>
#include<malloc.h>//malloc()等
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<limits.h>
#include<iostream>
#defineTRUE1
#defineFALSE1
#defineOK1
#defineERROR1
#defineINFEASIBLE-1
typedefintStatus;
typedefintBoolean；
/************************************************************************/
/*最優二叉樹簡稱：哈夫曼樹*/
/************************************************************************/
//哈夫曼樹結構
;typedefstruct{
unsignedintweight;//權重
unsignedintparent,lchild,rchild;//樹的雙親節點，和左右孩子
}HTNode,*HuffmanTree;
typedefchar**HuffmanCode;
//返回i個節點中權值最小的樹的根節點的序號，供select()調用
intMin(HuffmanTreeT,inti){
intj,flag;
unsignedintk=UINT_MAX;//%d-->UINT_MAX=-1,%u--->非常大的數
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;//將parent標志為1避免二次查找
returnflag;//返回
}
voidSelect(HuffmanTreeT,inti,int&s1,int&s2){
//在i個節點中選取2個權值最小的樹的根節點序號，s1為序號較小的那個
intj;
s1=Min(T,i);
s2=Min(T,i);
if(s1>s2){
j=s1;
s1=s2;
s2=j;
}
}
//HuffmanCode代表的樹解碼二進制值
voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){
//w存放n個字元的權值(均>0),構造哈夫曼樹HT,並求出n個字元的哈夫曼編碼HC
intm,i,s1,s2,start;
unsignedc,f;
char*cd;
//分配存儲空間
HuffmanTreep;
if(n<=1)
return;
//n個字元(葉子節點)有2n-1個樹節點，所以樹節點m
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).lchild=0;
(*p).rchild=0;
(*p).parent=0;
}
//這一步是給哈夫曼樹的非葉子節點初始化
for(;i<=m;++i,++p){
(*p).parent=0;
}
/************************************************************************/
/*做完准備工作後，開始建立哈夫曼樹
/************************************************************************/
for(i=n+1;i<=m;i++)
{
//在HT[1~i-1]中選擇parent=0且weigh最小的節點，其序號分別為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;
}
/************************************************************************/
/*從葉子到根逆求每個葉子節點的哈夫曼編碼*/
/************************************************************************/
//分配n個字元編碼的頭指針向量，（[0]不用）
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
cd=(char*)malloc(n*sizeof(char));//分配求編碼的工作空間
cd[n-1]=' ';//結束符
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賦值字元串到cd
}
free(cd);//釋放資源
}
//函數聲明
intMin(HuffmanTreeT,inti);//求i個節點中的最小權重的序列號，並返回
voidSelect(HuffmanTreeT,inti,int&s1,int&s2);//從兩個最小權重中選取最小的(左邊)給s1，右邊的給s2
voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn);//哈夫曼編碼與解碼
intmain(){
HuffmanTreeHT;
HuffmanCodeHC;
int*w,n,i;
printf("請輸入權值的個數(>1):");
scanf_s("%d",&n);
w=(int*)malloc(n*sizeof(int));
printf("請依次輸入%d個權值(整形): ",n);
for(i=0;i<=n-1;i++)
{
scanf_s("%d",w+i);
}
HuffmanCoding(HT,HC,w,n);
for(i=1;i<=n;i++)
{
puts(HC[i]);
}
return0;
}
『陸』 求助，哈夫曼樹的C語言編程問題萬分
根據數組 a 中 n 個權值建立一棵哈夫曼樹，返回樹根指針
struct BTreeNode* CreateHuffman(ElemType a[], int n)
{
int i, j;
struct BTreeNode **b, *q;
b = malloc(n*sizeof(struct BTreeNode));
for (i = 0; i < n; i++) //初始化b指針數組，使每個指針元素指向a數組中對應的元素結點
{
b[i] = malloc(sizeof(struct BTreeNode));
b[i]->data = a[i];
b[i]->left = b[i]->right = NULL;
}
for (i = 1; i < n; i++)//進行 n-1 次循環建立哈夫曼樹
{
//k1表示森林中具有最小權值的樹根結點的下標，k2為次最小的下標
int k1 = -1, k2;
for (j = 0; j < n; j++)//讓k1初始指向森林中第一棵樹，k2指向第二棵
{
if (b[j] != NULL && k1 == -1)
{
k1 = j;
continue;
}
if (b[j] != NULL)
{
k2 = j;
break;
}
}
for (j = k2; j < n; j++)//從當前森林中求出最小權值樹和次最小
{
if (b[j] != NULL)
{
if (b[j]->data < b[k1]->data)
{
k2 = k1;
k1 = j;
}
else if (b[j]->data < b[k2]->data)
k2 = j;
}
}
//由最小權值樹和次最小權值樹建立一棵新樹，q指向樹根結點
q = malloc(sizeof(struct BTreeNode));
q->data = b[k1]->data + b[k2]->data;
q->left = b[k1];
q->right = b[k2];
b[k1] = q;//將指向新樹的指針賦給b指針數組中k1位置
b[k2] = NULL;//k2位置為空
}
free(b); //刪除動態建立的數組b
return q; //返回整個哈夫曼樹的樹根指針
}
『柒』 有人可以幫我注釋一段關於用c語言實現哈夫曼樹的代碼嗎
在一般的數據結構的書中，樹的那章後面，著者一般都會介紹一下哈夫曼(HUFFMAN)樹和哈夫曼編碼。哈夫曼編碼是哈夫曼樹的一個應用。哈夫曼編碼應用廣泛，如
JPEG中就應用了哈夫曼編碼。 首先介紹什麼是哈夫曼樹。哈夫曼樹又稱最優二叉樹，是一種帶權路徑長度最短的二叉樹。所謂樹的帶權路徑長度，就是樹中所有的葉結點
的權值乘上其到根結點的 路徑長度（若根結點為0層，葉結點到根結點的路徑長度為葉結點的層數）。
樹的帶權路徑長度記為WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln) ，N個權值Wi(i=1,2,...n)構成一棵有N個葉結點的二叉樹，相應的葉結點的路徑長度為Li(i=1,2,...n)。 可以證明哈夫曼樹的WPL是最小的。
哈夫曼編碼步驟：
一、對給定的n個權值{W1,W2,W3,...,Wi,...,Wn}構成n棵二叉樹的初始集合F= {T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉樹Ti中只有一個權值為Wi的根結點，它的左右子樹均為空。（為方便在計算機上實現算 法，一般還要求以Ti的權值Wi的升序排列。）
二、在F中選取兩棵根結點權值最小的樹作為新構造的二叉樹的左右子樹，新二叉樹的根結點的權值為其左右子樹的根結點的權值之和。
三、從F中刪除這兩棵樹，並把這棵新的二叉樹同樣以升序排列加入到集合F中。
四、重復二和三兩步，直到集合F中只有一棵二叉樹為止。
簡易的理解就是，假如我有A,B,C,D,E五個字元，出現的頻率（即權值）分別為5,4,3,2,1,那麼我們第一步先取兩個最小權值作為左右子樹構造一個新樹，即取1，2構成新樹，其結點為1+2=3，如圖：
所以各字元對應的編碼為：A->11,B->10,C->00,D->011,E->010
霍夫曼編碼是一種無前綴編碼。解碼時不會混淆。其主要應用在數據壓縮，加密解密等場合。
C語言代碼實現：
/*-------------------------------------------------------------------------
* Name: 哈夫曼編碼源代碼。
* Date: 2011.04.16
* Author: Jeffrey Hill+Jezze(解碼部分)
* 在 Win-TC 下測試通過
* 實現過程：著先通過 HuffmanTree() 函數構造哈夫曼樹，然後在主函數 main()中
* 自底向上開始(也就是從數組序號為零的結點開始)向上層層判斷，若在
* 父結點左側，則置碼為 0,若在右側,則置碼為 1。最後輸出生成的編碼。
*------------------------------------------------------------------------*/
#include <stdio.h>
#include<stdlib.h>
#define MAXBIT 100
#define MAXVALUE 10000
#define MAXLEAF 30
#define MAXNODE MAXLEAF*2 -1
typedef struct
{
int bit[MAXBIT];
int start;
} HCodeType; /* 編碼結構體 */
typedef struct
{
int weight;
int parent;
int lchild;
int rchild;
int value;
} HNodeType; /* 結點結構體 */
/* 構造一顆哈夫曼樹 */
void HuffmanTree (HNodeType HuffNode[MAXNODE], int n)
{
/* i、j： 循環變數，m1、m2：構造哈夫曼樹不同過程中兩個最小權值結點的權值，
x1、x2：構造哈夫曼樹不同過程中兩個最小權值結點在數組中的序號。*/
int i, j, m1, m2, x1, x2;
/* 初始化存放哈夫曼樹數組 HuffNode[] 中的結點 */
for (i=0; i<2*n-1; i++)
{
HuffNode[i].weight = 0;//權值
HuffNode[i].parent =-1;
HuffNode[i].lchild =-1;
HuffNode[i].rchild =-1;
HuffNode[i].value=i; //實際值，可根據情況替換為字母
} /* end for */
/* 輸入 n 個葉子結點的權值 */
for (i=0; i<n; i++)
{
printf ("Please input weight of leaf node %d:
", i);
scanf ("%d", &HuffNode[i].weight);
} /* end for */
/* 循環構造 Huffman 樹 */
for (i=0; i<n-1; i++)
{
m1=m2=MAXVALUE; /* m1、m2中存放兩個無父結點且結點權值最小的兩個結點 */
x1=x2=0;
/* 找出所有結點中權值最小、無父結點的兩個結點，並合並之為一顆二叉樹 */
for (j=0; j<n+i; j++)
{
if (HuffNode[j].weight < m1 && HuffNode[j].parent==-1)
{
m2=m1;
x2=x1;
m1=HuffNode[j].weight;
x1=j;
}
else if (HuffNode[j].weight < m2 && HuffNode[j].parent==-1)
{
m2=HuffNode[j].weight;
x2=j;
}
} /* end for */
/* 設置找到的兩個子結點 x1、x2 的父結點信息 */
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;
printf ("x1.weight and x2.weight in round %d: %d, %d
", i+1, HuffNode[x1].weight, HuffNode[x2].weight); /* 用於測試 */
printf ("
");
} /* end for */
/* for(i=0;i<n+2;i++)
{
printf(" Parents:%d,lchild:%d,rchild:%d,value:%d,weight:%d
",HuffNode[i].parent,HuffNode[i].lchild,HuffNode[i].rchild,HuffNode[i].value,HuffNode[i].weight);
}*///測試
} /* end HuffmanTree */
//解碼
void decodeing(char string[],HNodeType Buf[],int Num)
{
int i,tmp=0,code[1024];
int m=2*Num-1;
char *nump;
char num[1024];
for(i=0;i<strlen(string);i++)
{
if(string[i]=='0')
num[i]=0;
else
num[i]=1;
}
i=0;
nump=&num[0];
while(nump<(&num[strlen(string)]))
{tmp=m-1;
while((Buf[tmp].lchild!=-1)&&(Buf[tmp].rchild!=-1))
{
if(*nump==0)
{
tmp=Buf[tmp].lchild ;
}
else tmp=Buf[tmp].rchild;
nump++;
}
printf("%d",Buf[tmp].value);
}
}
int main(void)
{
HNodeType HuffNode[MAXNODE]; /* 定義一個結點結構體數組 */
HCodeType HuffCode[MAXLEAF], cd; /* 定義一個編碼結構體數組， 同時定義一個臨時變數來存放求解編碼時的信息 */
int i, j, c, p, n;
char pp[100];
printf ("Please input n:
");
scanf ("%d", &n);
HuffmanTree (HuffNode, n);
for (i=0; i < n; i++)
{
cd.start = n-1;
c = i;
p = HuffNode[c].parent;
while (p != -1) /* 父結點存在 */
{
if (HuffNode[p].lchild == c)
cd.bit[cd.start] = 0;
else
cd.bit[cd.start] = 1;
cd.start--; /* 求編碼的低一位 */
c=p;
p=HuffNode[c].parent; /* 設置下一循環條件 */
} /* end while */
/* 保存求出的每個葉結點的哈夫曼編碼和編碼的起始位 */
for (j=cd.start+1; j<n; j++)
{ HuffCode[i].bit[j] = cd.bit[j];}
HuffCode[i].start = cd.start;
} /* end for */
/* 輸出已保存好的所有存在編碼的哈夫曼編碼 */
for (i=0; i<n; i++)
{
printf ("%d 's Huffman code is: ", i);
for (j=HuffCode[i].start+1; j < n; j++)
{
printf ("%d", HuffCode[i].bit[j]);
}
printf(" start:%d",HuffCode[i].start);
printf ("
");
}
/* for(i=0;i<n;i++){
for(j=0;j<n;j++)
{
printf ("%d", HuffCode[i].bit[j]);
}
printf("
");
}*/
printf("Decoding?Please Enter code:
");
scanf("%s",&pp);
decodeing(pp,HuffNode,n);
getch();
return 0;
}
『捌』 用C語言編寫Huffman樹
//huffmantree and huffmancode
#include <stdio.h>
#include <malloc.h>
#define MAX 10
typedef struct huffmanTreeNode{
int weight;
int parent,left,right;
}htNode;
void select(htNode *ht,int n,int *s1,int *s2){
int i=0;
*s1=*s2=-1;
while(i<n){
if(ht[i].parent!=-1){i++;continue;}
else{
if(ht[i].weight<ht[*s1].weight||*s1==-1){
*s2=*s1;
*s1=i;
}
else if(ht[i].weight<ht[*s2].weight||*s2==-1)
*s2=i;
i++;
}
}
}
bool createHtree(htNode *ht,int n){
int i=n,m=2*n-1,s1,s2;
for(;i<m;i++){
select(ht,n++,&s1,&s2);
if(s1==-1||s2==-1) return true;
ht[i].left=s1; ht[i].right=s2;
ht[s1].parent=i; ht[s2].parent=i;
ht[i].weight=ht[s1].weight+ht[s2].weight;
}
return true;
}
void printfData(htNode *ht,int m){
int i=0;
printf("location\tparent\tleft\tright\tweight\n");
while(i<m){
printf("%d\t\t%d\t%d\t%d\t%d\n",i,ht[i].parent,ht[i].left,ht[i].right,ht[i].weight);
i++;
}
}
void initHtree(htNode *ht,int n){
int m=2*n-1,i=0;
printf("Please input the weight of node:");
for(;i<n;i++){
scanf("%d",&(ht[i].weight));
getchar();
ht[i].left=-1;
ht[i].right=-1;
ht[i].parent=-1;
}
for(i=n;i<m;i++){
ht[i].left=-1;
ht[i].right=-1;
ht[i].parent=-1;
ht[i].weight=-1;
}
}
void huffmanCode(htNode *ht,int n){
// char *hc=(char *)malloc(n*sizeof(char *));
char *temp=(char *)malloc(n*sizeof(char));
char **code=(char **)malloc(n*sizeof(char));
int i=0,j=0,start=n,parent,t;
for(i=0;i<n;i++)
code[i]=(char *)malloc(n*sizeof(char));
for(i=0;i<n;i++){
start=n;
parent=ht[i].parent; t=i;
while(parent!=-1){
temp[--start]=(ht[parent].left==t?'0':'1');
t=parent;
parent=ht[parent].parent;
}
for(j=0;start<n;j++,start++){
code[i][j]=temp[start];
}
code[i][j]='\0';
}
free(temp);
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(code[i][j]=='\0') break;
else printf("%c",code[i][j]);
}
printf("\t");
}
printf("\n");
}
int main(void){
htNode *ht;
int n,m,i=0;
printf("Please input the number of node:");
scanf("%d",&n); getchar();
m=2*n-1;
ht=(htNode *)malloc(m*sizeof(htNode));
initHtree(ht,n);
createHtree(ht,n);
printfData(ht,m);
printf("\nThe code of huffmanCode is:");
huffmanCode(ht,n);
return 0;
}
哥以前做的