[数据结构与算法]数据结构——树——通用堆——哈夫曼树解压缩

前文的通用堆作为辅助工具https://blog.csdn.net/fzh1038526545/article/details/119392304?spm=1001.2014.3001.5501注释掉的为调试代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <stdint.h>
#include "heap_tree.h"

typedef struct TreeNode
{
	char code;
	int weight;
	struct TreeNode* left;
	struct TreeNode* right;
}TreeNode;

TreeNode* create_tree_node(char code,int weight)
{
	TreeNode* node = malloc(sizeof(TreeNode));
	node->code = code;
	node->weight = weight;
	node->left = NULL;
	node->right = NULL;
	return node;
}

TreeNode* create_tree(char code[],int weight[],size_t len)
{
	int cmp(const void* p1,const void* p2)
	{
		TreeNode* n1 = (TreeNode*)p1;
		TreeNode* n2 = (TreeNode*)p2;
		if(n1->weight > n2->weight)
			return 1;
		if(n1->weight < n2->weight)
			return -1;
		return 0;
	}

	Heap* heap = create_heap(len);
	setcmp_heap(heap,cmp);
	for(int i=0; i<len; i++)
	{
		push_heap(heap,create_tree_node(code[i],weight[i]));
	}
	
	while(true)
	{
		TreeNode* left = top_heap(heap);
		pop_heap(heap);
		TreeNode* right = top_heap(heap);
		pop_heap(heap);
		TreeNode* root = create_tree_node(0,left->weight+right->weight);
		root->left = left;
		root->right = right;
		if(empty_heap(heap))
			return root;
		push_heap(heap,root);
	}
}

void ldr_show(TreeNode* root)
{
	if(NULL == root)
		return;
	ldr_show(root->left);
	if(root->code)
	{
		printf("%c %d\n",root->code,root->weight);
	}
	ldr_show(root->right);
}

typedef struct HuffmanCode
{
	char code;
	char bits;
	char cnt;
}HuffmanCode;

HuffmanCode* hcode;
size_t _index = 0;
void code_tree(TreeNode* root,char bits,int n)
{
	if(NULL == root)
		return;
	char new_bits = bits << 1;
	code_tree(root->left,new_bits,n+1);
	if(root->code)
	{
		hcode[_index].code = root->code;
		hcode[_index].bits = bits;
		hcode[_index++].cnt = n;
	}
	new_bits += 1;
	code_tree(root->right,new_bits,n+1);
}

typedef struct Data
{
	uint64_t bits;
	int cnt;
}Data;

int main(int argc,const char* argv[])
{
	char str[] = "abcdefg";
	int arr[] = {9,2,1,4,3,6,7};
	hcode = malloc(sizeof(HuffmanCode)*7);
	TreeNode* root = create_tree(str,arr,7);
	code_tree(root,0,0);
	/*
	char* text = "abcabcdeabcdefgfgdefgababcdefgcdefg";
	FILE* fwp = fopen("test.txt","w");
	Data data = {};
	for(int i=0,j; text[i]; i++)
	{
		for(j=0; j<7; j++)
		{
			if(hcode[j].code == text[i])
				break;
		}
		if(data.cnt + hcode[j].cnt > 64)
		{
			fwrite(&data,sizeof(Data),1,fwp);
			printf("%llu %d\n",data.bits,data.cnt);
			data.bits = 0;
			data.cnt = 0;
		}	
	
		data.bits = data.bits << hcode[j].cnt;
		data.bits += hcode[j].bits;
		data.cnt += hcode[j].cnt;
	}
	if(data.cnt>0)
		fwrite(&data,sizeof(Data),1,fwp);
	fclose(fwp);
	*/
		
	FILE* frp = fopen("test.txt","r");
	Data data = {};
	while(0 < fread(&data,sizeof(Data),1,frp))
	{
		TreeNode* node = root;
		for(int i=0; i<data.cnt; i++)
		{
			if((data.bits >> (data.cnt-i-1))&1)
				node = node->right;
			else
				node = node->left;
			if(node->code)
			{
				printf("%c",node->code);
				node = root;
			}
		}
	}
	
	/*
	for(int i=0; i<7; i++)
	{
		printf("%c %hhu %d\n",hcode[i].code,hcode[i].bits,hcode[i].cnt);
	}
	*/

}