数据结构C语言编程—二叉树哈弗曼编码

- 日理万妓 2023-03-13 02:57 12阅读 0赞

\#include<stdio.h>  
\#include<malloc.h>  
\#include<string.h>  
\#include<windows.h>  
\#define M 8  
\#define MAX 200

typedef struct  
\{  
int data;  
int pa,lc,rc;  
\}JD;

typedef struct HuffmanCode  
\{  
char data1;  
struct HuffmanCode \*next;  
\}\*code;

code temp,top;

void huffman(int n,int w\[\],JD t\[\])  
\{  
int i,j,k,x1,x2,m1,m2;  
int start,c,f;  
for(i=1;i<(2\*n);i++)  
\{  
t\[i\].pa=t\[i\].lc=t\[i\].rc=0;  
if(i<=n)  
t\[i\].data=w\[i\];  
else  
t\[i\].data=0;  
\}  
for(i=1;i<n;i++)  
\{  
m1=m2=MAX;  
x1=x2=0;  
for(j=1;j<(n+i);j++)  
\{  
if((t\[j\].data<m1)&&(t\[j\].pa0))  
\{  
m2=m1;  
x2=x1;  
m1=t\[j\].data;  
x1=j;  
\}  
else if((t\[j\].data<m2)&&(t\[j\].pa0))  
\{  
m2=t\[j\].data;  
x2=j;  
\}  
\}  
k=n+i;  
t\[x1\].pa=t\[x2\].pa=k;  
t\[k\].data=m1+m2;  
t\[k\].lc=x1;  
t\[k\].rc=x2;  
\}  
printf(“The huffman tree:\\n”);  
for(i=1;i<M;i++)  
\{  
printf("\\t\\t%d “,t\[i\].lc);  
printf(”\\t\\t%d “,t\[i\].data);  
printf(”\\t\\t%d “,t\[i\].rc);  
printf(”\\t\\t%d “,t\[i\].pa);  
printf(”\\n");  
\}  
printf(“The Huffman Coding is :\\n”);  
for(i=1;i<=n;++i)  
\{  
top=(code)malloc(sizeof(struct HuffmanCode));  
top->next=NULL;  
for(c=i,f=t\[i\].pa;f!=0;c=f,f=t\[f\].pa)  
\{  
temp=(code)malloc(sizeof(struct HuffmanCode));  
if(t\[f\].lc==c)  
\{  
temp->data1=‘0’;  
temp->next=top->next;  
top->next=temp;  
\}  
else  
\{  
temp->data1=‘1’;  
temp->next=top->next;  
top->next=temp;  
\}  
\}  
printf("\\t\\t%d “,t\[i\].data);  
while(top->next!=NULL)  
\{  
top->next=temp->next;  
printf(”%c",temp->data1);  
temp=temp->next;  
\}  
printf("\\n");  
\}  
\}

void main()  
\{  
int w\[M\],i,n=0;  
JD t\[M\];  
printf(“please input the information of character:”);  
for(i=1;i<M;i++)  
\{  
printf("\\nthe number:");  
scanf("%d",&w\[i\]);  
\}  
system(“cls”);  
printf(“The elements are:”);  
for(i=1;(i<M)&&(w\[i\]!=0);i++)  
\{  
printf("%d “,w\[i\]);  
if(w\[i\]!=0)  
n++;  
\}  
printf(”\\nThe quantity of elements is %d",n);  
printf("\\n");  
huffman(n,&w,&t);  
getch();  
\}