求:《数据结构》关于“哈夫曼树”这类的文章资料
发布网友
发布时间：2022-04-29 13:14
共2个回答
热心网友
时间：2023-10-08 19:58
我写过一个对文件进行霍夫曼编码的程序……当然很原始，压缩率不咋地，但是是霍夫曼的一个重要应用，你看看对你有帮助没：
//Power by S.J.Qin
#include <stdio.h>
#include <malloc.h>
#include <string.h>
typedef struct{
double weight;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef struct HCode{
unsigned char bit;
struct HCode *next;
}HCode,*PHCode;
typedef struct{
short int lchild,rchild;
}eHTNode,*eHuffmanTree;
double PublicWeight[256]={
239992,14802,7962,5872,10297,6583,6881,3248,18791,2181,2550,1661,8444,3982,1332,4298,5862,2369,1544,1092,3440,3417,987,925,3470,3893,1013,1049,2255,5863,962,916,6840,831,872,1034,7798,1865,1353,760,2040,837,1064,1128,1867,820,1032,761,2240,1096,1039,4307,2393,1115,845,711,2093,2268,1070,5163,1762,1005,697,1139,5566,2682,1443,2893,3713,22268,7277,2444,3475,2105,1314,1067,6580,33249,11341,4426,19675,15209,9331,6461,2921,4988,8061,6265,2590,3570,1063,1880,1641,4540,4863,3325,1752,2960,1093,1986,6101,9089,3720,1630,9855,2956,7908,899,3140,1771,3507,3087,4394,897,4453,3296,12108,12604,1815,1769,2168,1499,900,660,2555,2808,1873,599,4387,1644,640,12128,3334,6452,1684,612,4489,15748,2809,47055,1829,24611,1860,646,1949,668,624,3060,1847,534,806,546,1382,619,544,517,1293,485,957,532,1432,707,931,807,1172,1305,748,531,1582,467,643,676,1606,540,666,588,2008,792,639,696,1636,894,1106,895,7711,663,860,892,1731,878,1563,1126,7122,2755,3900,5405,3290,589,8669,3741,2532,5624,910,1426,8038,677,5958,1556,2282,699,1237,861,2106,570,1206,1065,3003,703,614,1424,2567,526,794,641,3740,600,654,583,3392,457,624,514,29214,11342,624,2947,9741,592,682,635,11846,2626,1810,1906,3940,710,2517,1831,3613,5935,3563,2794,17246,1641,5126,74420
};//For Public use
unsigned char status;
double *Use;
double need;
void WeightUse(eHuffmanTree HTW,HuffmanTree HT,PHCode HC){
void Huffman(HuffmanTree,PHCode);
Huffman(HT,HC);
for(int j=0;j<256;j++){
HTW[j].lchild=HT[j+255].lchild;
HTW[j].rchild=HT[j+255].rchild;
}
}//WeightUse(in WeightBuild)
void WeightBuild(FILE *input,double *PrivateWeight,eHuffmanTree HTW,HuffmanTree HT,PHCode HC){
void Huffman(HuffmanTree,PHCode);
unsigned char ch;
double words=0;
while(!feof(input)){
fread(&ch,sizeof(unsigned char),1,input);
PrivateWeight[ch]++;
words++;
}
if((need=words)>1024){
status=1;
Use=PrivateWeight; //Use PrivateWeight
WeightUse(HTW,HT,HC);
}
else{
Use=PublicWeight;
Huffman(HT,HC);
status=0;
}
}//WeightBuild
void Select(HuffmanTree HT,int n,int &s1,int &s2){
int i;double m;
for(i=0;i<n&&HT[i].parent;i++);
for(m=HT[i].weight;i<n;i++)
if(!HT[i].parent&&m>=HT[i].weight){
s1=i;
m=HT[i].weight;
}
HT[s1].parent=-1;
for(i=0;i<n&&HT[i].parent;i++);
for(m=HT[i].weight;i<n;i++){
if(!HT[i].parent&&m>=HT[i].weight){
s2=i;
m=HT[i].weight;
}
}
HT[s1].parent=0;
}//Select
void Huffman(HuffmanTree HT,PHCode HC){
int s1,s2,i,p;
PHCode z;
for(int t=0;t<256;t++) HT[t].weight=Use[t];
for(i=256;i<511;i++){
Select(HT,i,s1,s2);
HT[s2].parent=HT[s1].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
for(i=0;i<256;i++){
p=i;z=NULL;
do{
if(p==510) break;
HC[i].next=(PHCode)malloc(sizeof(HCode));
if(p==HT[HT[p].parent].lchild) (HC[i].next)->bit=0;
else (HC[i].next)->bit=1;
HC[i].next->next=z;
z=HC[i].next;
}while(p=HT[p].parent);
}
}//Huffman
void Pack(FILE *input,FILE *output,PHCode HC,eHuffmanTree HTW){
rewind(input);
unsigned char ch,wr=0,i=0;
PHCode p;
fwrite(&status,sizeof(unsigned char),1,output);
if(status)
fwrite(HTW,sizeof(eHTNode),256,output);
while(!feof(input)){
fread(&ch,sizeof(unsigned char),1,input);
for(p=HC[ch].next;p;p=p->next){
if(p->bit) wr=((wr<<=1)|1);
else wr<<=1;
i++;
if(i==8){
fwrite(&wr,sizeof(unsigned char),1,output);
wr=i=0;
}
}
}
if(i){
wr<<=(8-i);
fwrite(&wr,sizeof(unsigned char),1,output);
}
fclose(output);
}//Pack
void Translate(FILE *input,FILE *output,PHCode HC,HuffmanTree HT,eHuffmanTree HTW){
unsigned char ch,bit,wr;
int i,q=510;
fread(&ch,sizeof(unsigned char),1,input);
if(ch){
fread(HTW,sizeof(eHTNode),256,input);
for(int j=0;j<256;j++){
HT[j+255].lchild=HTW[j].lchild;
HT[j+255].rchild=HTW[j].rchild;
}
}
else{
Use=PublicWeight;
Huffman(HT,HC);
}
while(!feof(input)){
i=0;
fread(&ch,sizeof(unsigned char),1,input);
while(i<8){
bit=ch&128;
if(bit) q=HT[q].rchild;
else q=HT[q].lchild;
ch<<=1;
i++;
if(q<256){
wr=q;
fwrite(&wr,sizeof(unsigned char),1,output);
q=510;
}
}
}
}//Translate
int main(int argc,char **argv){
double PrivateWeight[256]={0};
eHTNode HTW[256]={0,0};
FILE *input,*output;
HTNode HT[511]={0,0,0,0};
PHCode HC=(PHCode)malloc(256*sizeof(HCode));
int namecount,mode;
char Trans[255]="Trans-",filename[255];
if(argc!=3){
printf("======HuffmanPack======\n");
printf("Please Choose Mode:\n1.Pack\n2.Translate\nYour Choise:");
scanf("%d",&mode);getchar();
if(mode!=1&&mode!=2) {printf("Enter Error!!!Please Try Again!!!");return 0;}
mode--;
printf("Please enter the file name:");
scanf("%s",filename);
}
else{
strcpy(filename,*(argv+2));
if(!strcmp(*(argv+1),"/p")) mode=0;
else if(!strcmp(*(argv+1),"/t")) mode=1;
else printf("Please refer to the FORMAT!\n");
}
if(!(input=fopen(filename,"rb"))) {printf("File Not Found/Cannot Open the File\n");return 0;}
if(mode){
for(namecount=0;filename[namecount];namecount++);
filename[namecount-4]=0;
if(!(output=fopen(strcat(Trans,filename),"wb"))) {printf("Error");return 0;}
printf("Translating...\n");
Translate(input,output,HC,HT,HTW);
}
else{
if(!(output=fopen(strcat(filename,".pac"),"wb"))) {printf("Error");return 0;}
WeightBuild(input,PrivateWeight,HTW,HT,HC);
if(need<512){
printf("Packing no needed!!!");
return 1;
}
printf("Packing...\n");
Pack(input,output,HC,HTW);
}
printf("Mission Completed!");
return 1;
}//main
热心网友
时间：2023-10-08 19:59
#include <string.h>
#include <stdlib.h>
#include <malloc.h>
#include <conio.h>
typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
} HTNode,*HuffmanTree;
typedef char **HuffmanCode;
typedef struct {
unsigned int s1;
unsigned int s2;
} MinCode;
void Error(char *message);
HuffmanCode HuffmanCoding(HuffmanTree HT,HuffmanCode HC,unsigned int *w,unsigned int n);
MinCode Select(HuffmanTree HT,unsigned int n);
void Error(char *message)
{
fprintf(stderr,"Error:%s\n",message);
exit(1);
}
HuffmanCode HuffmanCoding(HuffmanTree HT,HuffmanCode HC,unsigned int *w,unsigned int n)
{
unsigned int i,s1=0,s2=0;
HuffmanTree p;
char *cd;
unsigned int f,c,start,m;
MinCode min;
if(n<=1) Error("Code too small!");
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(p=HT,i=0;i<=n;i++,p++,w++)
{
p->weight=*w;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(;i<=m;i++,p++)
{
p->weight=0;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(i=n+1;i<=m;i++)
{
min=Select(HT,i-1);
s1=min.s1;
s2=min.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;
}
printf("HT List:\n");
printf("Number\t\tweight\t\tparent\t\tlchild\t\trchild\n");
for(i=1;i<=m;i++)
printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\n",
i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
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=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]);
}
free(cd);
return HC;
}
MinCode Select(HuffmanTree HT,unsigned int n)
{
unsigned int min,secmin;
unsigned int temp;
unsigned int i,s1,s2,tempi;
MinCode code;
s1=1;s2=1;
for(i=1;i<=n;i++)
if(HT[i].parent==0)
{
min=HT[i].weight;
s1=i;
break;
}
tempi=i++;
for(;i<=n;i++)
if(HT[i].weight<min&&HT[i].parent==0)
{
min=HT[i].weight;
s1=i;
}
for(i=tempi;i<=n;i++)
if(HT[i].parent==0&&i!=s1)
{
secmin=HT[i].weight;
s2=i;
break;
}
for(i=1;i<=n;i++)
if(HT[i].weight<secmin&&i!=s1&&HT[i].parent==0)
{
secmin=HT[i].weight;
s2=i;
}
if(s1>s2)
{
temp=s1;
s1=s2;
s2=temp;
}
code.s1=s1;
code.s2=s2;
return code;
}
void main()
{
HuffmanTree HT=NULL;
HuffmanCode HC=NULL;
unsigned int *w=NULL;
unsigned int i,n;
printf("Input n:\n");
scanf("%d",&n);
w=(unsigned int *)malloc((n+1)*sizeof(unsigned int *));
w[0]=0;
printf("Enter weight:\n");
for(i=1;i<=n;i++)
{
printf("w[%d]=",i);
scanf("%d",&w[i]);
}
HC=HuffmanCoding(HT,HC,w,n);
printf("HuffmanCode:\n");
printf("Number\t\tWeight\t\tCode\n");
for(i=1;i<=n;i++)
printf("%d\t\t%d\t\t%s\n",i,w[i],HC[i]);
}
