C语言—哈夫曼编码译码器

1.介绍

设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下业务，直到选择退出为止。

（说明：在代码中使用 while 循环，并设置一个跳出循环即退出的字符，例如： e ，当输入 ’e’ 时，跳

出循环，重复结束）

(1) 初始化：键盘输入 n 个字符和 n 个权值，建立哈夫曼树 (n>=5) ；

（说明：哈夫曼树使用静态三叉链表结构，有权重， parent, ， lchild, ， rchild ；哈夫曼编码用指向叶子的指针，叶子结点的数目，和一个存储编码的结构 HuffmanCode 组成）

(2) 能够将数据存放在数据文件 ( 文件名为 data.txt ，位于当前目录中 ) ；

(3) 编码：利用建好的哈夫曼树生成哈夫曼编码，输出编码；

(4) 输入编码，完成译码。

设计要求：

(1) 符合课题要求，实现相应功能；

(2) 要求界面友好美观，操作方便易行；

(3) 注意程序的实用性、安全性。

2.代码

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

#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define MAX_NUM 10086
#define MAX 60

//1.哈夫曼树的三叉链表结点的结构
typedef struct
{   
     int weight;//权重
     int parent, lchild, rchild;
     
}HTNode, *HuffmanTree;

//2.数组用来存储哈夫曼编码表
typedef char **HuffmanCode;

//3.哈夫曼树存储结点结构体
typedef struct
{
     char *c;//指向字符数组的指针
     int  longth;//权重
     HuffmanTree TREE;//它代表了哈夫曼树的另一个结点。
     HuffmanCode BM;
     //用于存储与当前结点关联的哈夫曼编码
}Huffman;

//4.作用是在一组哈夫曼树结点中找到两个具有最小权值的结点
void Select(HuffmanTree HT, int end, int *s1, int *s2) 

{
     int i;
     int min1 = MAX_NUM;
	 //用于表示初始时最大的权值。这个变量将用于存储找到的第一个最小权值的结点的索引。
     int min2;
     
     //找到的第二个最小权值的结点的索引。由于我们首先寻找两个权值最小的结点，
	 //所以这个变量一开始没有被初始化，但是在函数中它会被更新。
	 
     for (i = 1;i <= end;i++)
	 {
         if((HT[i].parent == 0)&&(HT[i].weight < min1))
		 {
             *s1 = i;
             min1 = HT[i].weight;
         }
     }
     min2 = MAX_NUM;
     for(i = 1;i <= end;i++)
	 {
         if(HT[i].parent == 0&&(*s1 != i)&&min2 > HT[i].weight)
		 {
             *s2 = i;
             min2 = HT[i].weight;
         }
     }
     //*s1和*s2分别包含了两个权值最小且父结点为零的哈夫曼树结点的索引。
}

//5.输入哈夫曼树的叶子数目及字符和权重,为建立哈夫曼树做准备
Huffman InputHuffman(Huffman Hfm)
{
     int i,n;
	 //i将用作循环变量，而n用于存储用户输入的字符数。
     printf("\n*****新建初始化哈夫曼树*****\n");
     printf("#请输入要输入的字符数（>=5）: ");
     scanf("%d",&n);
	 //从键盘读取用户输入的字符数量，并将其赋值给变量n。
     
     Hfm.TREE = (HuffmanTree)malloc((2*n)*sizeof(HTNode));
     // 使用malloc函数为哈夫曼树的结点分配足够大的连续内存空间。
     Hfm.c = (char *)malloc((n+1)*sizeof(char));
     //以容纳n个输入字符及一个额外的字符用于数组的终止符
     
     for(i = 1;i <= n;i++)//遍历
	 {
         printf("#请分别输入第%d个字符:", i);
         scanf("%s",&Hfm.c[i]);
         printf("#其权重为：");
         scanf("%d", &Hfm.TREE[i].weight);
         Hfm.TREE[i].parent = 0;
         Hfm.TREE[i].lchild = 0;
         Hfm.TREE[i].rchild = 0;
     }
     /*将字符数组Hfm.c[i]设置为用户输入的字符。每个结点的
	 rent、lchild和rchild域都被设置为0，表示它们还没有被连接到树的其他部分。*/
     for(;i <= 2*n - 1;++i)
	 {
         Hfm.TREE[i].weight = 0;
         Hfm.TREE[i].parent = 0;
         Hfm.TREE[i].lchild = 0;
         Hfm.TREE[i].rchild=0;
     }
     //循环结束后，再执行一次赋值操作以填充剩余的哈夫曼树结点。将它们的权重、父节点、左子节点和右子节点都设置为0。
     Hfm.longth = n;
     //表示哈夫曼树中实际使用的结点数量。
     return Hfm;
}

//*（重要）6.创建哈夫曼树并进行哈夫曼编码
Huffman HuffmanCoding(Huffman Hfm)
{
     int i,n,m,s1,s2,start;
     /*i将用作循环变量
	 n表示哈夫曼树中叶子结点的数量
	 m表示哈夫曼树中总的结点数量
	 s1和s2用于暂时存储找到的两个最小权值结点的索引
	 start用于记录当前结点在编码字符串中的起始位置*/
     int c,f;
     char *cd;
     n = Hfm.longth;
	 //n赋值为哈夫曼树结构体中存储的叶子结点数量。
     
     if(n <= 1)   
     {
     	return Hfm;
	 }
	 	
    m = 2*n-1;//计算哈夫曼树中总的结点数量
     
     for(i = n + 1;i <= m;++i)

	 {
         Select(Hfm.TREE,i - 1,&s1,&s2);
         Hfm.TREE[s1].parent = i;
         Hfm.TREE[s2].parent = i;
         Hfm.TREE[i].lchild = s1;
         Hfm.TREE[i].rchild = s2;
         Hfm.TREE[i].weight = Hfm.TREE[s1].weight + Hfm.TREE[s2].weight;
     }
    //从i = n + 1到i <= m进行遍历。
	//每次循环调用Select函数找到两个权值最小的结点s1和s2。
	//然后将这两个结点的索引赋值给哈夫曼树结点i的左右子节点域lchild和rchild。
	//将哈夫曼树结点i的权重设置为它的左右子节点的权重之和。
	//将i赋值给这两个子节点的父节点域parent。
     
     Hfm.BM = (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 = Hfm.TREE[i].parent; f != 0;c = f,f = Hfm.TREE[f].parent)
		 {
             if(c == Hfm.TREE[f].lchild)  
             {
             	cd[--start] = '0';
			 }
            
             else cd[--start] = '1';
         }
         Hfm.BM[i] = (char *)malloc((n - start)*sizeof(char));
         strcpy(Hfm.BM[i],&cd[start]);
     }
    //从i = 1到i <= n进行遍历。
	//对于每个叶子结点，从根结点开始向下遍历哈夫曼树，直到到达该叶子结点。
	//在遍历过程中，将遇到的每一个分支标记为'0'或'1'，并将其存入数组cd中。
	//start变量用于追踪当前结点在编码字符串中的起始位置。
     
     free(cd);
     return Hfm;
     //返回经过哈夫曼编码处理后的哈夫曼树结构体。
}


//7.将哈夫曼存入文件中
Huffman InitbuildHuffman(Huffman Hfm)
{
     int i;
     FILE *fp;
	 //定义了一个指向FILE类型的指针fp，用于表示文件的引用。
     
     fp = fopen("data.txt","wt");
     //使用fopen函数打开一个名为"data.txt"的文件进行写入操作。如果该文件不存在，它将被创建。
     
     Hfm = InputHuffman(Hfm);
     //调用InputHuffman函数来初始化哈夫曼树。用户将在此过程中输入字符和权重的值。
     
     Hfm = HuffmanCoding(Hfm);
     //调用HuffmanCoding函数来创建哈夫曼树并生成哈夫曼编码。
     
     fprintf(fp,"%d\n",Hfm.longth);
     //将哈夫曼树中叶子结点的数量写入文件中，并在末尾添加一个换行符。
     
     for(i = 1;i <= Hfm.longth;i++)
     {
     	fprintf(fp,"%c %d %s ", Hfm.c[i], Hfm.TREE[i].weight, Hfm.BM[i]); 	
	 }
    
     rewind(fp);
     //使用rewind函数将文件指针移动到文件的开头。
     
     fclose(fp);
     //使用fclose函数关闭文件句柄。
     
     printf("#初始化创建已完毕\n#已保存到文件'data.txt'中\n");
     return Hfm;
     //返回初始化并构建完成的哈夫曼树结构体的引用。
}

//8.译码
void Decoding(Huffman Hfm)
{
     HuffmanTree p;
     //用于指向哈夫曼树中的某个结点。
     
     int i,n;
     //i将用作临时变量，用于存储正在处理的结点的索引。
	 //n表示哈夫曼树中叶子结点的数量。
     
     int j = 0;
     char d[50];
     // 定义了一个字符数组d，用于存储输入的哈夫曼编码字符串。
     
     n = Hfm.longth;
     //将变量n赋值为哈夫曼树结构体中存储的叶子结点数量。
     
     printf("\n**********译码**********\n");
     printf("#请输入码文\n");
     scanf("%s",&d);
     printf("#译码为 : ");
     while(d[j])
      {
         p = &Hfm.TREE[2*n - 1];
         
         while(p->lchild||p->rchild)
         {
             if(d[j] == '0')
             { 
				 i = p->lchild;  
                  p = &Hfm.TREE[i]; 
			 }
             else
             { 
				 i = p->rchild;  
                 p = &Hfm.TREE[i]; 
			 }
             j++;
         }
         printf("%c",Hfm.c[i]);
     }
     //while（1）
     //当d[j]不为空（即d[j]表示的字符不是字符串的结束标记\0）时，继续执行循环。
	 //j变量用于追踪当前正在处理的字符在输入编码字符串中的位置。
	 
	 //while（2）
	 //在哈夫曼树中按照输入的哈夫曼编码进行搜索。
	 //如果当前编码为'0'，则将p指向其左子结点；如果当前编码为'1'，则将p指向其右子结点。
	 //j变量在每次比较后递增，以便处理编码字符串中的下一个字符。
} 

//9.将所有的叶子的哈夫曼编码输出
void Output(Huffman Hfm)
{
     int i,n;
     //i将用作循环变量，从1到n遍历哈夫曼树的所有叶子结点。n表示哈夫曼树中叶子结点的数量。
     
     n = Hfm.longth;
     printf("\n*****所有编码输出******\n");
     for(i = 1;i <= n;i++)
	 {
         printf("\n");
         printf("#字符: %c  ",Hfm.c[i]);
         printf("#编码: ");
         puts(Hfm.BM[i]);
         //将当前叶子结点的哈夫曼编码打印出来。puts函数会自动在编码字符串末尾添加一个换行符。
     }
}

//10.主函数
int main()
{ 
     printf("\n*——欢迎使用哈夫曼编码译码器!——*\n");
     printf("*在此系统中可以进行以下操作:\n"); 
     Huffman Hfm;
     char choice = 'a';
     while(choice != 'd')
     {
         printf("***************************\n");
         printf("*a. 新建初始化哈夫曼树    *\n");
         printf("*b. 进行译码              *\n");
         printf("*c. 输出所有编码          *\n");
         printf("*d. 退出哈夫曼编码译码器  *\n");
         printf("***************************\n");
         printf("\n请选择(选项对应的字母)： ");
         scanf(" %c",&choice);
         switch(choice)
         {
             case 'a':
             Hfm = InitbuildHuffman(Hfm);
             printf("\n***请继续选择操作（回车）***\n");
             getch(); break;
      
			 case 'b':
             Decoding(Hfm);
             printf("\n***请继续选择操作（回车）***\n");
             getch(); break;
      
             case 'c':
             Output(Hfm);
             printf("\n***请继续选择操作（回车）***\n");
             getch(); break;
           
             case 'd':
             printf("\n|==欢迎下次使用（回车后退出程序）==|\n");
             getch(); break;
      
             default:
             printf("$$$输入信息错误!请重新输入!$$$（回车）\n\n");
             getch(); break;
         }
     }
     return 0;
}