涛涛改.cpp

数据结构的一次作业

#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#include<malloc.h>

int m,s1,s2;//定义全局变量，n为叶结点个数，m=2n-1，s1和s2表示weight最小的两个结点。

/*定义赫夫曼树的结点*/
typedef struct 
{
	unsigned int weight;
	unsigned char letter;
	unsigned int parent,lchild,rchild;
}  HTNode,*HuffmanTree;     //动态分配数组存储赫夫曼树                                
typedef char *HuffmanCode; //动态分配数组存储赫夫曼编码表

/*函数声明*/
void CreatHuffman(HuffmanTree &HT, HuffmanCode HC[], int *w, int n);
void Select(HuffmanTree HT,int n);
void DecodeHuffman(HuffmanTree &HT,char *a,int n);

/*主函数*/
void main()                                                       
{
	 //欢迎词
	
		printf("\n\n");
		printf("*************************************************************\n");
		printf("\t\t\tWELCOME TO HAFFMAN\n");
		printf("*************************************************************\n");
		printf("\n");

	HuffmanTree HT;//建树
	HuffmanCode *HC;
	int *w,n,j;
	char *c;
	printf("请输入你想要编码的结点个数: ");
	scanf("%d",&n);
	HC=(HuffmanCode *)malloc(n*sizeof(HuffmanCode));
	w=(int *)malloc(n*sizeof(int));
	c=(char *)malloc(n*sizeof(char));

	printf("请依次输入这%d个结点的字符和它的权值(注意是整数哦)：\n\n",n);//录入信息
	for(j=0;j<n;j++)
	{
		printf("输入结点<%d>的字符:\t",j+1);
		getchar();
		scanf("%c",&c[j]);
	}
	
	printf("\n");
	for(j=0;j<n;j++)
	{
		printf("输入结点<%c>的权值:\t",c[j]);
		scanf("%d",&w[j]);
	}
	

	int i;
	char *cd;
	int p;
	int len;
    
	if (n<=1) return;
	m =2*n-1;
	HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); //为赫夫曼结点分配空间
	for (i=1;i<=n;i++)  //初始化用户输入的n个有权值待编码的结点
	{ 
		HT[i].letter=c[i-1];
		HT[i].weight=w[i-1];
		HT[i].parent=0;
		HT[i].lchild=0;
		HT[i].rchild=0;
	}
	for (i=n+1;i<=m;i++)//初始化其它结点
	{ 
		HT[i].letter=0;
		HT[i].weight=0;
		HT[i].parent=0;
		HT[i].lchild=0;
		HT[i].rchild=0;
	}

	for (i=n+1;i<=m;i++) //将找到的两个最小权值结点结合
	{ 
		Select(HT,i-1);
		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;
	}

	cd = (char *)malloc(n*sizeof(char));//分配赫夫曼编码表空间
	/*下面是无栈非递归遍历赫夫曼树，求赫夫曼编码*/
	p=m;
	len=0;
	for(i=1;i<=m;++i) 
	HT[i].weight=0;
	while (p)
	{
		if (HT[p].weight==0) 
		{ 
			HT[p].weight=1;
			if (HT[p].lchild!= 0) 
			{ 
				p=HT[p].lchild; 
				cd[len++]='0'; 
			}
			else if (HT[p].rchild==0) 
			{ 
				HC[p]=(char *)malloc((len+1)*sizeof(char));
				cd[len]='\0'; 
				strcpy(HC[p],cd); 
			}
		} 
		else if (HT[p].weight==1) 
		{ 
			HT[p].weight=2;
			if (HT[p].rchild!= 0) 
			{ 
				p=HT[p].rchild;
				cd[len++] ='1'; 
			}
		} 
		else 
		{ 
			HT[p].weight=0; 
			p=HT[p].parent; 
			--len;
		}
	}
	printf("\n现在输出各结点的赫夫曼编码:  ");//输出编码
	printf("\n");
	for(i=1;i<= n;i++)
	printf("结点为<%c>，权值为 <%d> 的编码为: %s\n",c[i-1],w[i-1],HC[i]);
	printf("\n");
    printf("请输入想要解码的01编码：\n");//解码
	char a[200];
	scanf("%s",a);
	DecodeHuffman(HT,a,n);
	printf("\n");
	
}


/*选择函数，用于在构建赫夫曼树时选出两个权值最小的结点*/
void Select(HuffmanTree HT,int n)  
{
	int i,j;
	for(i=1;i<=n;i++)
	if(!HT[i].parent)	{s1=i;break;}
	for(j=i+1;j<=n;j++)
	if(!HT[j].parent)	{s2=j;break;}
	for(i=1;i<=n;i++)
	if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i))	s1=i;
	for(j=1;j<=n;j++)
	if((HT[s2].weight>HT[j].weight)&&(!HT[j].parent)&&(s1!=j))	s2=j;

}

/*用户输入自定义的01代码，实现解码功能*/
void DecodeHuffman(HuffmanTree &HT,char a[],int n)
{
	int p,k=0,q;
	p=2*n-1;
	q=p;
    while(a[k]=='0'||a[k]=='1')
	{
		       if(a[k]=='0')
			   {
			    q=HT[q].lchild; 
			    if(HT[q].lchild==0&&HT[q].rchild==0)
				{
				printf("%c",HT[q].letter);
				q=p;
				k=k+1;
				}
			    else k=k+1;
			   }
		       else if(a[k]=='1')
			   {
			      q=HT[q].rchild;
			        if(HT[q].lchild==0&&HT[q].rchild==0)
					{
			     	  printf("%c",HT[q].letter);
				      q=p;
				      k=k+1;
					}
			        else k=k+1;
			   }
			   
		   };
}