哈夫曼树 shishikan.cpp

一些数据结构源代码

#include"stdio.h"
#include"malloc.h"
struct Huf{
unsigned int weight;
char date;
unsigned int parent,lchild,rchild;
};
void Select(struct Huf *HuffmanTree,int i,int *s1,int *s2)
{
int j;
for(j=1;j<=i;j++) if(HuffmanTree[j].parent==0) *s1=j;
for(j=1;j<=i;j++)
if(HuffmanTree[j].weight<HuffmanTree[*s1].weight)
if(HuffmanTree[j].parent==0)
*s1=j;
for(j=1;j<=i;j++) if(HuffmanTree[j].parent==0)
if(j!=*s1) *s2=j;
for(j=1;j<=i;j++)
if(HuffmanTree[j].weight<HuffmanTree[*s2].weight)
if(HuffmanTree[j].parent==0)
if(j!=*s1)
*s2=j;
}
void HuffmanCoding(struct Huf *HuffmanTree,char **HuffmanCode,int n,int m)
{
int i,e,s1,s2,start,j,f;
char c,*cd;
for(i=0;i<=m;i++) HuffmanTree[i].weight=0;
for(i=0;i<=m;i++) HuffmanTree[i].parent=0;
for(i=0;i<=m;i++) HuffmanTree[i].lchild=0;
for(i=0;i<=m;i++) HuffmanTree[i].rchild=0;
for(i=0;i<=m;i++) HuffmanTree[i].date='+';
for(i=1;i<=n;i++)
{
scanf("%d%c",&e,&c);
HuffmanTree[i].date=c;
HuffmanTree[i].weight=e;
}
for(i=n+1;i<=m;i++)
{
Select(HuffmanTree,i-1,&s1,&s2);
HuffmanTree[s1].parent=i;
HuffmanTree[s2].parent=i;
HuffmanTree[i].lchild=s1;
HuffmanTree[i].rchild=s2;
HuffmanTree[i].weight=HuffmanTree[s1].weight+HuffmanTree[s2].weight;
}
cd=(char*)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=1;i<=n;i++)
{
start=n-1;
for(j=i,f=HuffmanTree[i].parent;f!=0;j=f,f=HuffmanTree[f].parent)
if(HuffmanTree[f].lchild=j) cd[--start]='0';
else cd[--start]='1';
HuffmanCode[i]=(char*)malloc((n-start)*sizeof(char));
strcpy(HuffmanCode[i],&cd[start]);
}
free(cd);
}
void myprint(struct Huf *T,char **C,int mark,int num,int n)
{
int i,r,l;
for(i=0;i<=num;i++) printf(" ");
printf("%c:",T[mark].date);
if(mark<=n) printf("%s",C[mark]);
printf("\n");
r=T[mark].rchild;
l=T[mark].lchild;
if(l) myprint(T,C,l,num+1,n);
if(r) myprint(T,C,r,num+1,n);
}
void mychange(struct Huf *T,char **C,int n)
{
int i;
FILE *pf1,*pf2;
char file1[20],file2[20],c;
gets(file1);
puts("\ninput the name of the file that you want to change:\n");
gets(file1);
puts("\ninput the name of the newfile:\n");
gets(file2);
pf1=fopen(file1,"r");
pf2=fopen(file2,"w");
while(!feof(pf1))
{
c=fgetc(pf1);
for(i=1;i<=n;i++)
if(T[i].date==c)
fprintf(pf2,"%s",C[i]);
}
fclose(pf1);
fclose(pf2);
}
void yourchange(struct Huf *T,int m)
{
FILE *p1,*p2;
int i=m;
char c,file1[20],file2[20];
gets(file1);
puts("\ninput the secret filename:\n");
gets(file1);
puts("\ninput the place you want to put:\n");
gets(file2);
p1=fopen(file1,"r");
p2=fopen(file2,"w");
while(!feof(p1))
{
c=fgetc(p1);
if((c=='1')&&(T[i].rchild!=0)) i=T[i].rchild;
else if((c=='0')&&(T[i].lchild!=0)) i=T[i].lchild;
if((T[i].rchild==0)&&(T[i].lchild==0))
{
printf("%c",T[i].date);
fputc(T[i].date,p2);
i=m;
}
}
fclose(p1);
fclose(p2);
}
void main()
{
int n,m;
struct Huf *HuffmanTree;
char **HuffmanCode;
system("cls");
puts("\ninput the number of the huffmantree\n");
scanf("%d",&n);
HuffmanCode=(char**)malloc((n+1)*sizeof(char*));
m=2*n;
HuffmanTree=(struct Huf*)malloc(m*sizeof(struct Huf));
m--;
HuffmanCoding(HuffmanTree,HuffmanCode,n,m);
myprint(HuffmanTree,HuffmanCode,m,1,n);
mychange(HuffmanTree,HuffmanCode,n);
yourchange(HuffmanTree,m);
puts("\n");
system("type rr");
puts("\n");
system("type asd");
}