C语言实现哈夫曼压缩与解压缩

矫情吗；* 2022-10-02 11:57 133阅读 0赞

#include <unistd.h>
    #include <assert.h>
    #include <stdio.h>
    #include <stdlib.h>
    
    #include <stdio.h>
    #include <math.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define N 256
    #define Maxsize 80
    #define SOME 1
    #define Empty 0
    #define FULL -1
    
    typedef unsigned long int WeightType;
    typedef unsigned char MyType;
    typedef struct {   //哈夫曼树
    	MyType ch;    //存字符
    	WeightType weight;    /* 用来存放各个结点的权值 */
    	int parent, LChild, RChild;    /*指向双亲、孩子结点的指针 */
    } HTNode;
    
    typedef struct {   //队列
    	int tag;
    	int front;
    	int rear;
    	MyType length;
    	char elem[Maxsize];
    } SeqQueue;
    
    int InitQueue(SeqQueue * Q){
    	if (!Q)
    	return 1;
    	Q->tag = Empty;
    	Q->front = Q->rear = 0;
    	Q->length = 0;
    
    	return 0;
    }
    
    int In_seqQueue(SeqQueue * Q, char x){
    	if (Q->front == Q->rear && Q->tag == SOME)
    	return FULL;
    
    	Q->elem[Q->rear] = x;
    	Q->rear = (Q->rear + 1) % Maxsize;
    	Q->length++;
    	Q->tag = SOME;
    	return SOME;
    }
    
    int Out_Queue(SeqQueue * Q, char *x){
    	if (Q->tag == Empty)
    	return Empty;
    
    	*x = Q->elem[Q->front];
    	Q->length--;
    	Q->front = (Q->front + 1) % Maxsize;
    
    	if (Q->front == Q->rear)
    	Q->tag = Empty;
    
    	return SOME;
    }
    
    /* ------以上是队列的操作--------- */
    
    void SelectMinTree(HTNode * ht, int n, int *k){
    	int i, temp;
    	WeightType min;
    
    	for (i = 0; i <= n; i++) {
    		if (0 == ht[i].parent) {
    			min = ht[i].weight;    //init min
    			temp = i;
    			break;
    		}
    	}
    	for (i++; i <= n; i++) {
    		if (0 == ht[i].parent && ht[i].weight < min) {
    			min = ht[i].weight;
    			temp = i;
    		}
    	}
    	*k = temp;
    }
    
    // 对哈夫曼树排序，并统计叶子数量
    int SortTree(HTNode * ht){
    	short i, j;
    	HTNode tmp;
    
    	for (i = N - 1; i >= 0; i--) {
    		for (j = 0; j < i; j++)
    			if (ht[j].weight < ht[j + 1].weight) {
    				tmp = ht[j];
    				ht[j] = ht[j + 1];
    				ht[j + 1] = tmp;
    			}
    	}
    	for (i = 0; i < N; i++)
    		if (0 == ht[i].weight)
    			return i;
    	return i;    //返回叶子个数
    }
    
    //求哈夫曼0-1字符编码表
    char **CrtHuffmanCode(HTNode * ht, short LeafNum){
    /*从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码*/
    	char *cd, **hc;    //容器
    	int i, start, p, last;
    
    	hc = (char **)malloc((LeafNum) * sizeof(char *));    /*分配n个编码的头指针 */
    
    	if (1 == LeafNum) {   //只有一个叶子节点时 
    		hc[0] = (char *)malloc((LeafNum + 1) * sizeof(char));
    		strcpy(hc[0], "0");
    		return hc;
    	}
    
    	cd = (char *)malloc((LeafNum + 1) * sizeof(char));    /*分配求当前编码的工作空间 */
    	cd[LeafNum] = '\0';    /*从右向左逐位存放编码，首先存放编码结束符 */
    	for (i = 0; i < LeafNum; i++) {    /*求n个叶子结点对应的哈夫曼编码 */
    		start = LeafNum;    /*初始化编码起始指针 */
    		last = i;
    		for (p = ht[i].parent; p != 0; p = ht[p].parent) {    /*从叶子到根结点求编码 */
    			if (ht[p].LChild == last)
    				cd[--start] = '0';    /*左分支标0 */
    			else
    				cd[--start] = '1';    /*右分支标1 */
    			last = p;
    		}
    		hc[i] = (char *)malloc((LeafNum - start) * sizeof(char));    /*为第i个编码分配空间 */
    		strcpy(hc[i], &cd[start]);
    
    		//printf("%3d号 %3c 码长:%2d;编码:%s\n", ht[i].ch, ht[i].ch, LeafNum - start, &cd[start]);
    	}
    	free(cd);
    	return hc;
    }
    
    HTNode *CreatHFM(FILE * fp, short *n, WeightType * FileLength){
    	HTNode *ht = NULL;
    	int i, m, s1, s2;
    	MyType ch;
    
    	ht = (HTNode *)malloc(2 * N * sizeof(HTNode));
    	if (!ht)
    		return NULL;
    
    	for (i = 0; i < N; i++) {
    		ht[i].weight = 0;
    		ht[i].ch = (MyType)i;    /*1-n号ch 为字符，初始化 */
    	}
    
    	for (*FileLength = 0; !feof(fp); ++(*FileLength)) {
    		ch = fgetc(fp);
    		ht[ch].weight++;
    	}
    	--(*FileLength);    //去掉文件结束后的长度
    	*n = SortTree(ht);
    	m = *n * 2 - 1; 
    
    	if (1 == *n) {
    		ht[0].parent = 1;
    		return ht;
    	}
    	else if (0 > *n)
    		return NULL;
    
    	for (i = m - 1; i >= 0; i--) {
    		ht[i].LChild = 0;
    		ht[i].parent = 0;
    		ht[i].RChild = 0;
    	}
    	/* ------初始化完毕！对应算法步骤1----- */
    	for (i = *n; i < m; i++) {    //创建非叶子结点,建哈夫曼树
    	    //在ht[0]~ht[i-1]的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给s1、s2返回
    		SelectMinTree(ht, i - 1, &s1);
    		ht[s1].parent = i;
    		ht[i].LChild = s1;
    
    		SelectMinTree(ht, i - 1, &s2);
    		ht[s2].parent = i;
    		ht[i].RChild = s2;
    
    		ht[i].weight = ht[s1].weight + ht[s2].weight;
    	}    /*哈夫曼树建立完毕 */// puts(" over^_^");
    
    	return ht;
    }
    
    //从队列里取8个字符（0、1），转换成一个字节
    MyType GetBits(SeqQueue * Q){
    	MyType i, bits = 0;
    	char x;
    
    	for (i = 0; i < 8; i++) {
    		if (Out_Queue(Q, &x) != Empty) {
    			if ('0' == x)
    				bits = bits << 1;
    			else
    				bits = (bits << 1) | 1;
    		}
    		else
    			break;
    	}
    
    	return bits;
    }
    
    //求最长（最短）编码长度
    void MaxMinLength(FILE * File, HTNode * ht, char **hc, short NLeaf, MyType * Max,MyType * Min){
    	int i;
    	MyType length;
    
    	*Max = *Min = strlen(hc[0]);
    	for (i = 0; i < NLeaf; i++) {
    		length = strlen(hc[i]);
    		fwrite(&ht[i].ch, sizeof(MyType), 1, File);    //字符和对应的
    		fwrite(&length, sizeof(MyType), 1, File);    //编码长度写进文件
    		if (length > *Max)
    			*Max = length;
    		if (length < *Min)
    			*Min = length;
    	}
    }
    
    //把出现过的字符编码表经过压缩写进文件
    short CodeToFile(FILE * fp, char **hc, short n, SeqQueue * Q, MyType * length){
    	int i;
    	char *p;
    	MyType j, bits;
    	short count = 0;
    
    	for (i = 0; i < n; i++) {   // 将n个叶子压缩并写入文件
    		for (p = hc[i]; '\0' != *p; p++)
    			In_seqQueue(Q, *p);
    
    		while (Q->length > 8) {
    			bits = GetBits(Q);    //出队8个元素
    			fputc(bits, fp); 
    			count++;
    		}
    	}
    
    	*length = Q->length;
    	i = 8 - *length;
    	bits = GetBits(Q);    //取8个如果队不空
    	for (j = 0; j < i; j++)
    		bits = bits << 1; 
    	fputc(bits, fp);
    	count++; 
    
    	InitQueue(Q);
    	return count;
    }
    
    //压缩
    void Compress(char* srcFile, char* desFile){
    	MyType maxLen, minLen, ch, bits, n, finalLength;
    	int i;
    	short LeafNum, codeNum;
    	WeightType count = 0, Length = 0, FileLength;
    	FILE *srcFp, *desFp;
    	SeqQueue *Q;
    	HTNode *ht = NULL;
    	char **hc = NULL, **Map = NULL, *p;
    
    	desFp = fopen(desFile, "wb");
    	srcFp = fopen(srcFile, "rb"); 
    
    	if (!srcFp || !desFp) {
    		return;
    	}
    
    	ht = CreatHFM(srcFp, &LeafNum, &FileLength);    //创建哈夫曼树,统计叶子个数和原文件长度
    	if (!FileLength) {
    		fclose(srcFp);
    		fclose(desFp);
    		free(ht);
    		return;
    	}
    	Q = (SeqQueue *)malloc(sizeof(SeqQueue));
    	InitQueue(Q);    //SEEK_SET:文件开头 SEEK_CUR:当前位置 SEEK_END:文件结尾
    	hc = CrtHuffmanCode(ht, LeafNum);    //取得哈夫曼0、1编码,hc的长度为LeafNum
    	//Map为了取编码好定位，再建立全部(256个)//
    	Map = (char **)malloc(N * sizeof(char *));    //字符编码表
    	if (!Map) {
    		return;
    	}
    
    	for (i = 0; i < N; i++)    //初始化
    		Map[i] = NULL;
    
    	for (i = 0; i < LeafNum; i++)    // 定位，编码指针数组Map[256]
    		Map[(int)(ht[i].ch)] = hc[i];
    
    	fseek(desFp, sizeof(WeightType) + sizeof(short) + 6 * sizeof(MyType), SEEK_SET);    //先占个位置 
    	//先占个位置,等下填压缩叶子编码剩几个和最长编码长
    
    	MaxMinLength(desFp, ht, hc, LeafNum, &maxLen, &minLen);    //获得最长码串长度,顺便填写字符对应编码长
    
    	free(ht); 
    	codeNum = CodeToFile(desFp, hc, LeafNum, Q, &finalLength);    //把字符转成其二进制编码写入文件,返回压成多少个
    
    	rewind(desFp);    //使文件指针移到开始
    	fseek(desFp, sizeof(WeightType) + sizeof(MyType), SEEK_SET);
    	fwrite(&LeafNum, sizeof(short), 1, desFp);    //写入叶子个数
    	fwrite(&maxLen, sizeof(MyType), 1, desFp);    //最长码串长度
    	fwrite(&minLen, sizeof(MyType), 1, desFp);    //最短码串长度
    
    	fwrite(&codeNum, sizeof(short), 1, desFp);    //填写叶子编码压多少个
    	fwrite(&finalLength, sizeof(MyType), 1, desFp);    //最后剩
    
    	fseek(desFp, 2 * LeafNum * sizeof(MyType) + codeNum, SEEK_CUR);
    	fseek(srcFp, 0, SEEK_SET);
    	printf("Please wait a minute,compressing...");
    
    	while (count < FileLength) {
    		ch = fgetc(srcFp);
    		++count;
    		for (p = Map[ch]; *p != '\0'; p++)
    			In_seqQueue(Q, *p);
    
    		while (Q->length > 8){
    			bits = GetBits(Q);    //出队8个元素,合成一个字节
    			fputc(bits, desFp); 
    			Length++; 
    		}
    	} 
    	//最后一个bits ;
    	finalLength = Q->length; 
    	n = 8 - finalLength;
    	bits = GetBits(Q);
    
    	for (i = 0; i < n; i++)
    		bits = bits << 1;    //以‘0’补
    
    	fwrite(&bits, sizeof(MyType), 1, desFp); 
    	Length++;
    
    	rewind(desFp); 
    	fwrite(&Length, sizeof(WeightType), 1, desFp);    //压缩后的长
    	fwrite(&finalLength, sizeof(char), 1, desFp);    //最后的串长
    
    	Length = Length + 12 + codeNum;
    
    	if (Length >= FileLength)
    		puts("\nCompression rate: 0.0%");
    	else
    		printf("\nCompression rate: %.2lf%c\n",
    		(double)((FileLength -
    		Length) / (double)FileLength) * 100.0, '%');
    
    	fclose(srcFp);
    	fclose(desFp);
    	free(Q);
    	free(hc);
    	free(Map);
    }
    
    //把读出的字符，转换成8个0、1字符串并入队
    void ToQueue(SeqQueue * Q, MyType ch){
    	int i;
    	MyType temp;
    
    	for (i = 0; i < 8; i++) {
    		temp = ch << i;
    		temp = temp >> 7;
    		if (1 == temp)
    			In_seqQueue(Q, '1');
    		else
    			In_seqQueue(Q, '0');
    	}
    }
    
    //解压缩
    void UnCompress(char* srcFile, char* desFile){
    	MyType *str, MaxLength, MinLength, ch, *num, finalLength = 0, final = 0;
    	FILE *srcFp, *desFp;
    	short NLeaf, Ncom;
    	char **hc, *p, x, *buf;
    	SeqQueue *Q = NULL;
    	int i, j;
    	WeightType srcLen = 0, thisFile = 0;
    
    	srcFp = fopen(srcFile, "rb");
    	desFp = fopen(desFile, "wb");
    	if (!srcFp || !desFp) {
    		puts("Cannot open files.");
    		return;
    	}
    
    	fread(&srcLen, sizeof(WeightType), 1, srcFp); 
    	fread(&finalLength, 1, 1, srcFp); 
    	fread(&NLeaf, sizeof(short), 1, srcFp); 
    	fread(&MaxLength, sizeof(MyType), 1, srcFp);
    	fread(&MinLength, sizeof(MyType), 1, srcFp);
    
    	Q = (SeqQueue *)malloc(sizeof(SeqQueue));
    
    	buf = (char *)malloc((2 + MaxLength * sizeof(char)));
    	str = (MyType *)malloc(NLeaf * sizeof(MyType));
    	num = (MyType *)malloc(NLeaf * sizeof(MyType));
    	//压缩叶子数量x和最后剩长
    	if (!Q || !str || !num || !buf) {
    		puts("Memery error.");
    		return ;
    	}
    	InitQueue(Q);    //初始化
    
    	fread(&Ncom, sizeof(short), 1, srcFp);
    	fread(&final, sizeof(MyType), 1, srcFp);
    
    	for (i = 0; i < NLeaf; i++) {   //读取叶子及其码长
    		fread(&str[i], sizeof(MyType), 1, srcFp);
    		fread(&num[i], sizeof(MyType), 1, srcFp);
    	}
    
    	hc = (char **)malloc((NLeaf) * sizeof(char *));    //hc为编码表的指针数组
    	if (!hc)
    		return ;
    
    	--Ncom; 
    	for (j = i = 0; i < Ncom; i++) {
    		ch = fgetc(srcFp); 
    		ToQueue(Q, ch); 
    		while (Q->length > MaxLength) {
    			hc[j] = p = (char *)malloc(1 + num[j]);
    			for (ch = 0; ch < num[j]; ch++) {
    				Out_Queue(Q, &x);
    				*p++ = x;
    			}
    			*p = '\0'; 
    			j++;
    		}
    	}
    	ch = fgetc(srcFp);
    	ToQueue(Q, ch);
    	final = 8 - final;
    	while (Q->length > final) {
    		p = hc[j] = (char *)malloc(1 + num[j]);
    		for (ch = 0; ch < num[j]; ch++) {
    			Out_Queue(Q, &x);
    			*p++ = x;
    		}
    		*p = '\0'; 
    		j++;
    	}
    
    	InitQueue(Q);
    	--srcLen;
    	--MinLength;
    
    	printf("Please wait a minute,uncompressing...");
    	while (thisFile < srcLen) {
    		ch = fgetc(srcFp); 
    		ToQueue(Q, ch);
    		thisFile++; 
    		//完了后队列长于码串的最大值
    
    		while (Q->length > MaxLength) {
    			for (i = 0; i < MinLength; i++) {
    				Out_Queue(Q, &x);
    				buf[i] = x;
    			}
    			for (; i < MaxLength; i++) {
    				Out_Queue(Q, &x);
    				buf[i] = x;
    				buf[i + 1] = '\0';
    				for (j = 0; j < NLeaf; j++) {
    					if (i + 1 == num[j]
    					&& 0 == strcmp(hc[j], buf)) {
    						ch = str[j]; 
    						fputc(ch, desFp); 
    						break;
    					}
    				}
    				if (j < NLeaf)
    					break;
    			}
    		}    //while MaxLength
    	}
    
    	ch = fgetc(srcFp); 
    	ToQueue(Q, ch);
    
    	finalLength = 8 - finalLength;
    	while (Q->length > finalLength) {
    		for (i = 0; i < MinLength; i++) {
    			Out_Queue(Q, &x);
    			buf[i] = x;
    		}
    		for (; i < MaxLength; i++) {
    			Out_Queue(Q, &x);
    			buf[i] = x;
    			buf[i + 1] = '\0';
    			for (j = 0; j < NLeaf; j++) {
    				if (i + 1 == num[j] && 0 == strcmp(hc[j], buf)) {
    					ch = str[j];  
    					fputc(ch, desFp); 
    					break;
    				}
    			}
    			if (j < NLeaf)
    				break;
    		}
    	}
    
    	free(Q);
    	free(str);
    	free(num);
    	free(hc);
    	fclose(desFp);
    	fclose(srcFp);
    }
    
    int main(int argc, char *argv[]){
    	char choice, blank[] = " ";
    	system("color 8a");
    	while (1) {
    		system("clear");    //清屏
    		puts(" * * * *Welcome use huffman encoder\\decoder* * *");
    		puts(" **********************^_^***********************");
    		puts(" * *");
    		printf(" * %s 1 ]. Compress %s*\n", blank, blank);
    		puts(" * *");
    		printf(" * %s 2 ]. Uncompress%s *\n", blank, blank);
    		puts(" * *");
    		printf(" * %s 3 ]. Exit ^_^ %s *\n", blank, blank);
    		puts(" * *");
    		puts(" ************************************************");
    		printf
    		(" (Apply to text file) Copyright 2011 By Bocai\n");
    		printf(" Choose (1 to 3):");
    		choice = getchar();
    
    		puts("");
    		getchar();
    		fflush(stdin);    //清空输入缓冲区域，否则键入的回车符将作为程序结尾处的scanf输入，此函数在stdio.h中
    		switch (choice) {
    			case '1':
    				Compress("slptt.log", "slptt_en.log");
    				printf("Press Enter to continue...");
    				getchar();
    				break;
    			case '2':
    				UnCompress("slptt_en.log", "slptt_de.log");
    				printf("\nPress Enter to continue...");
    				getchar();
    				break;
    			case '3':
    				return 0;
    		}
    	}
    
    	return 0;
    }