哈夫曼编码与译码
发布网友
发布时间：2022-04-22 01:22
共1个回答
热心网友
时间：2023-07-18 06:19
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <stdlib.h>
#include <conio.h>
#define NN 10000
#define M 2*NN-1
#define IN 0
#define OUT 1
#define MAX_INT 32767
#define PRINTLN printf("\n\n\n\n\n\n\n\n");
typedef struct
{
int wi;
char c;
int tag;
int parent, lchild, rchild;
}huffmtype;
typedef char* encodetype[NN+1];
typedef struct
{
char c;
int times;
}codetype;
void PRINT()
{
PRINTLN;
printf("\t\t\t Huffman编/译码器\n");
printf("\t\t\t ====================\n");
printf("\t\t\t 1.编码 2.译码 3.退出\n\n");
printf("\t\t\t >>选择:");
}
FILE* OpenFile(char filename[20], char type[3])
{
FILE *fp = NULL;
if((fp = fopen(filename, type)) == NULL) exit(1);
return fp;
}
int ReadCode(codetype* code, FILE* fp)
{
char c;//保存某次从文件中读入字符-
int n = 1;//记录首次出现字符在数组中的下标-
int i;//循环变量-
int cnt = 1;
int tag;//标志某次读入字符是否为首次出现字符，tag=1表示是首次出现;tag=0表示本次读入字符为已有字符
while((c = fgetc(fp)) != EOF)//当文件没有结束时读入字符-
{
//从fp指向文件中读取字符，存入字符变量c中-
tag = 1;//假设本次读取字符为首次出现字符-
for(i = 1; i < n; i++)
{
if(c == code[i].c)//如果本次读入字符为存储在下标为i已有字符-
{
code[i].times++;//权值加1-
tag = 0;//标记本字符为已有字符-
break;//在已有数组元素中找到本次读入字符，结束for(;;)循环-
}
}
if(tag)//当本字符为首次出现字符时-
{
code[n].c = c;//把改字符存入n指向的数组单元中-
code[n].times = 1;//记字符出现次数为1-
n++;//n指向下一个数组地址-
}
}
return n - 1;//返回文件中字符集合的元素个数-
}
void InitHuffmanTree(huffmtype* huffmtree, int real_n, int real_m)//初始化-
{
int i;
for(i = real_n; i <= real_m; i++)
{
huffmtree[i].wi = 0;
huffmtree[i].c = 0;
huffmtree[i].tag = IN;
huffmtree[i].lchild = huffmtree[i].rchild = huffmtree[i].parent = 0;
}
}
void ReadDataWeight_Init(huffmtype* huffmtree, codetype* code, int real_n)//获取权值及数值域值-
{
int i;
for(i = 1; i <= real_n; i++)//-
{
huffmtree[i].wi = code[i].times;
huffmtree[i].c = code[i].c;
huffmtree[i].tag = IN;
huffmtree[i].lchild = huffmtree[i].rchild = huffmtree[i].parent = 0;
}
}
int LeastNode(huffmtype *huffmtree, int max_i)//找到最小权值节点地址-
{
int i;
int least_i;
int max = MAX_INT;
for(i = 1; i <= max_i; i++)//遍历1到max_i节点-
{
if(huffmtree[i].wi < max && huffmtree[i].tag == IN)//若节点权值比max小并且在森林中-
{
max = huffmtree[i].wi;//刷新max值-
least_i = i;//保存当前节点地址-
}
}
huffmtree[least_i].tag = OUT;//将最小权值节点从森林中移除-
return least_i;//返回最小节点地址
}
void Slect(huffmtype *huffmtree, int max_i, int *x1, int *x2)//找到权值最小的两个节点，并将其下标值保存在x1，x2中-
{
*x1 = LeastNode(huffmtree, max_i);//计算合法最下权值下标-
*x2 = LeastNode(huffmtree, max_i);//
}
void CreatHuffmanTree(huffmtype* huffmtree, int real_n, int real_m)//创建哈弗曼树-
{
int i;
int x1, x2;
for(i = real_n + 1; i <= real_m; i++)
{
Slect(huffmtree, i-1, &x1, &x2);//找到权值最小的两个节点，并将其下标值保存在x1，x2中-
huffmtree[i].wi = huffmtree[x1].wi + huffmtree[x2].wi;//计算双气节点权值-
huffmtree[x1].parent = huffmtree[x2].parent = i;//计算双亲节点地址-
huffmtree[i].lchild = x1; huffmtree[i].rchild = x2;//计算双亲节点左右孩子地址-
}
}
void Encode(huffmtype *huffmtree, encodetype encode, int real_n)//依据已创建的HuffmanTree对字符进行编码-
{
char *cd;
int i;
int start;
int c, p;
cd = (char*)malloc(real_n*sizeof(char));//cd用来存放某次运行时当前字符编码-
cd[real_n - 1] = '\0';//作为字符结束符-
for(i = 1; i <= real_n; i++)//对real_n个节点进行遍历-
{
start = real_n-1;
c = i;//c保存当前节点地址（下标）-
p = huffmtree[i].parent;//p保存当前节点双亲地址-
while(p)
{
start--;//计算编码的起始地址-
if(huffmtree[p].lchild == c)//若当前节点为其双亲的左孩子-
{
cd[start] = '0';//编码为0-
}
else//若为右孩子-
{
cd[start] = '1';//编码为1-
}
c = p;//节点前进-
p = huffmtree[p].parent;//计算前进后节点双亲节点地址-
}
encode[i] =(char*)malloc((real_n - start)*sizeof(char));//申请空间用于存放编码-
strcpy(encode[i], &cd[start]);//将本次编码存入encode数组中-
}
free(cd);//释放闲置存储空间-
}
void WriteToFile(FILE *fp, encodetype encode, codetype *code, int real_n, char *readfile)//将编码输出到文件
{
int i;
char cod[NN];
FILE *fp2;
char c;
int cnt = 1, j;
fp2 = fopen(readfile, "rt");
while((c = fgetc(fp2)) != EOF)
{
cod[cnt++] = c;
}
fclose(fp2);
for(i = 1; i < cnt; i++)
{
for(j = 1; j <=real_n; j++)
{
if(cod[i] == code[j].c)
{
break;
}
}
fprintf(fp, "%s", encode[j]);
}
fclose(fp);
}
int IsError(FILE *fp)//对打开文件进行出错判断-
{
if(!fp)
{
printf("\t\t\t ×打开文件错误\n");
printf("\t\t\t 任意键返回主菜单");
getch();
return 1;//文件打开失败-
}
return 0;//文件打开成功-
}
void GetFilename(char *filename, char type[13])//得到用户输入相关文件名
{
system("cls");
PRINTLN;
printf("\t\t\t %s:", type);
fflush(stdin);
gets(filename);
}
int PutIntoCode(codetype code[], huffmtype huffmtree[])//编码函数
{
encodetype encode;
FILE* fp;//文件类型指针-
int real_n;//用来存放字符集长度-
char readfile[20];//从readfile文件中读取字符，写入到writefile文件中-
GetFilename(readfile, "读取源文件");//从键盘读取文件名-
fp=OpenFile(readfile, "rt");//打开待编码文件-
if(IsError(fp))//判断是否正确打开文件-
{
return 0;//打开文件失败，返回主菜单-
}
real_n=ReadCode(code, fp);//从readfile文件读取字符，将字符集合元素存入code数组，将集合元素个数存入real_n-
fclose(fp);//关闭文件-
ReadDataWeight_Init(huffmtree, code, real_n);//初始化HuffmanTree中从1到real_n的元素-
InitHuffmanTree(huffmtree, real_n, 2*real_n-1);//初始化HuffmanTree中real_n到2*real_n的元素-
CreatHuffmanTree(huffmtree, real_n, 2 * real_n - 1);//创建HuffmanTree-
Encode(huffmtree, encode, real_n);//根据HuffmanTree对字符进行编码，编码结果保存到encode数组中-
fp = OpenFile("CodeFile.txt", "wb");//打开待写入文件-
WriteToFile(fp, encode, code, real_n, readfile);//将encode数组中元素写入到文件中-
fclose(fp);//关闭文件-
printf("\t\t\t 完成编码并保存至CodeFile.txt文件中");//打印完成编码信息-
getch();//等待用户输入任意键返回主菜单-
return real_n;
}
void Translate(codetype code[], huffmtype huffmtree[], int real_n)//译码函数
{
FILE *fp,*fp2;
int i, real_m;
char c;
char writefile[20];
GetFilename(writefile, "保存解码文件到");
fp = OpenFile("CodeFile.txt", "rb");
fp2 = OpenFile(writefile, "wt");
if(IsError(fp))
{
return;
}
i = real_m = 2*real_n - 1;
while((c = fgetc(fp)) != EOF)
{
if(c == '0')
{
i = huffmtree[i].lchild;
}
else
{
i = huffmtree[i].rchild;
}
if(huffmtree[i].lchild == 0)
{
fputc(code[i].c, fp2);
i = real_m;
}
}
fclose(fp);
fclose(fp2);
printf("\t\t\t 完成译码任务");
getch();
}
int main(void)
{
int choice;
int real_n = 0;
codetype code[NN];
huffmtype huffmtree[NN];
while(1)
{
system("cls");
PRINT();
scanf("%d",&choice);
switch(choice)
{
case 1 :
real_n = PutIntoCode(code, huffmtree);
break;//编码函数
case 2 :
if(real_n) Translate(code, huffmtree, real_n);break;//译码函数
case 3 :
exit(1);//退出程序
default :
printf("\t\t\t ★无效输入");
getch();
break;
}
}
return 0;
}
