赫夫曼树.cpp

自己做的赫夫曼树

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

typedef struct{
	unsigned int weight;
	unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;

typedef char **HuffmanCode;

void Main();
void Coding();
void Decoding();

HuffmanTree HT;
HuffmanCode HC;
int w[100],n;
char c[100];

void Select(HuffmanTree HT,int n,int &s1,int &s2){
	//在HT[1..i-1]中选择parent为0且weight最小的两个结点，其序号分别为s1和s2。
	int i;
	unsigned int min;
	s1=s2=1;
    min=10000;
    for(i=1;i<=n;i++)
		if(HT[i].parent==0){
			if(HT[i].weight<min){
				min=HT[i].weight;
				s1=i;
			}
		}//求s1
    min=10000;
	for(i=1;i<=n;i++)
		if(i!=s1){
			if(HT[i].parent==0){
				if(HT[i].weight<min){
					min=HT[i].weight;
				    s2=i;
				}
			}
		}//求s2
}

void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n) {
  // w存放n个字符的权值(均>0)，构造哈夫曼树HT，
  // 并求出n个字符的哈夫曼编码HC
  int i,  m, s1, s2, start;
  char *cd;
  unsigned int c, f;

  if (n<=1) return;
  m = 2 * n - 1;
  HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode));  // 0号单元未用
  for (i=1; i<=n; i++) { //初始化
    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].weight=0;
    HT[i].parent=0;
    HT[i].lchild=0;
    HT[i].rchild=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 = i;  HT[s2].parent = i;
    HT[i].lchild = s1;  HT[i].rchild = s2;
    HT[i].weight = HT[s1].weight + HT[s2].weight;
  }
  //--- 从叶子到根逆向求每个字符的哈夫曼编码 ---
  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)); 
         // 为第i个字符编码分配空间
    strcpy(HC[i], &cd[start]);    // 从cd复制编码(串)到HC
  }
  free(cd);   // 释放工作空间
} // HuffmanCoding

void creat(){
	int i;
	system("cls");
    printf("********************************************************************************");
	printf("\n\t\t\t\t     初始化\n\n");
	printf("********************************************************************************");
	printf("\n请输入要进行初始化编码的字符个数：");
	scanf("%d",&n);
	for(i=0;i<n;i++){
		printf("\n请输入第%d个字符：",i+1);
		getchar();
		scanf("%c",&c[i]);
		printf("该字符的权值为：");
		scanf("%d",&w[i]);
	}
    HuffmanCoding(HT,HC,w,n);
    printf("\n赫夫曼编码为：\n\n");
    for(i=1;i<=n;++i)
		printf("%c     %-10s\n",c[i-1],HC[i]);
	printf("\n\n返回主菜单：Y     结束程序：N\n选择：");
	getchar();
	char ch;
	scanf("%c",&ch);
    if(toupper(ch)=='Y'){
        system("cls");
		Main();
	}
	else
		exit(0);
}

void coding(){
	Coding();
}

void Coding(){
	char code[1000];
	int i=0,j,k[1000]={0},l=1,ncode;
	system("cls");
    printf("********************************************************************************");
	printf("\n\t\t\t\t     编码\n\n");
	printf("********************************************************************************");
	printf("\n请输入需要编码的字符串：");
	scanf("%s",code);
	printf("\n输入要进行编码的字符是：");
	printf("%s\n",code);
	while(code[i]!='\0'){
		for(j=0;j<n;j++){
			if(code[i]==c[j]){
				k[i]=1;
				break;
			}
		}
		i++;
	}
	ncode=i;
	for(i=0;i<ncode;i++){
		if(k[i]==0){
			l=0;
			break;
		}
	}
	if(l==1){
		i=0;
        printf("\n该字符串的二进制赫夫曼编码是：");
		while(code[i]!='\0'){
		    for(j=0;j<n;j++)
				if(code[i]==c[j]) 
				   printf("%s",HC[j+1]);
		    i++;
		}
	}
	else{
		printf("输入有误，以下字符错误：\n\n");
		for(i=0;i<ncode;i++){
			if(k[i]==0){
				printf("第%d个字符：%c\n",i+1,code[i]);
			}
		}
		printf("\n\n重新输入：Y    结束程序：N\n选择：");
		getchar();
		char c;
		scanf("%c",&c);
        if(toupper(c)=='Y'){
            system("cls");
		    Coding();
		}
	    else
		    exit(0);
	}
    printf("\n\n返回主菜单：Y     结束程序：N\n选择：");
	getchar();
	char ch;
	scanf("%c",&ch);
    if(toupper(ch)=='Y'){
        system("cls");
		Main();
	}
	else
		exit(0);
}

void decoding(){
	Decoding();
}

void Decoding(){
	char decode[1000];
	int i=0,j=2*n-1,k=1;
	system("cls");
    printf("********************************************************************************");
	printf("\n\t\t\t\t     译码\n\n");
	printf("********************************************************************************");
	printf("\n请输入要进行译码的字符：");
	scanf("%s",decode);
	printf("\n输入要进行译码的字符是：");
	printf("%s",decode);
	while(decode[i]!='\0'){
		if(decode[i]!='0'&&decode[i]!='1'){
			k=0;
			break;
		}
		i++;
	}
	if(k==0){
		printf("\n输入的字符有错！\n");
		printf("\n重新输入：Y    结束程序：N\n选择：");
		getchar();
		char c;
		scanf("%c",&c);
        if(toupper(c)=='Y'){
			system("cls");
		    Decoding();
		}
	    else
		    exit(0);
	}
	else{
        printf("\n\n该字符串的原码是：");
		i=0;
		while(decode[i]!='\0'){
			if(decode[i]=='0')
			   j=HT[j].lchild;
		    else if(decode[i]=='1')
			   j=HT[j].rchild;
		    if(HT[j].rchild==0&&HT[j].lchild==0){
			   printf("%c",c[j-1]);
			   j=2*n-1;
			}
		    i++;
		}
	}
	printf("\n\n返回主菜单：Y     结束程序：N\n选择：");
	getchar();
	char ch;
	scanf("%c",&ch);
    if(toupper(ch)=='Y'){
		system("cls");
		Main();
	}
	else
		exit(0);
}
void print(){
	int j;
    system("cls");
    printf("********************************************************************************");
	printf("\n\t\t\t\t     打印\n\n");
	printf("********************************************************************************");
	printf("\n");
    printf("  结点  weight  parent  lchild  rchild");
    for (j=1; j<=2*n-1; j++)
      printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,HT[j].parent,HT[j].lchild, HT[j].rchild);
    printf("\n\n返回主菜单：Y     结束程序：N\n选择：");
	getchar();
	char ch;
	scanf("%c",&ch);
    if(toupper(ch)=='Y'){
		system("cls");
		Main();
	}
	else
		exit(0);
}

void main(){
	Main();
}

void Main(){
	int mainchoose;
	printf("\n\t\t\t\t赫夫曼编码器\n");
	printf("\n\t\t\t****************************\n");
    printf("\n\t\t\t\t  1.初始化\n");
    printf("\n\t\t\t\t  2.编码\n");
    printf("\n\t\t\t\t  3.译码\n");
    printf("\n\t\t\t\t  4.打印\n");
    printf("\n\t\t\t\t  5.退出\n");
    printf("\n\t\t\t****************************\n");
	printf("\n\t\t  请输入要执行的操作（输入1~5之间的数）：");
	scanf("%d",&mainchoose);
    switch(mainchoose){
    case 1:creat();break;
    case 2:coding();break;
    case 3:decoding();break;
    case 4:print();break;
	case 5:exit(0);
	default:{
		printf("\n\n\t\t对不起，输入的字符无效！按任意键后重新输入。");
        getchar();
		getchar();
		system("cls");
		Main();
	}
	}
}