利用哈夫曼树压缩文本

#include "HuffmanCompress.h" #include <stdio.h> #include <stdlib.h> #include <string.h> #include <malloc.h> HuffmanNodeTypeDef HuffmanHead; HuffmanNodeTypeDef *RootTreeNode; StringDataTypeDef StringData; FileBitQueue_TypeDef FileBitQueue; //输入字符串操作 void GetString(StringDataTypeDef *string_data); uint8_t BuildHuffmanTree(StringDataTypeDef *string_data,HuffmanNodeTypeDef *head); uint8_t GetHuffmanCode(StringDataTypeDef string_data,HuffmanNodeTypeDef *head); void OutPutTreeCode(StringDataTypeDef string_data,HuffmanNodeTypeDef head); void OutPutStringCode(StringDataTypeDef string_data); uint8_t GetHufmanRootNode(HuffmanNodeTypeDef head);//获取霍夫曼树的根节点 void AnalyseTreeCode(HuffmanNodeTypeDef *root); uint8_t FreeTreeCode(HuffmanNodeTypeDef *head); //文件读取操作 uint8_t OpenFile(FILE *fp,StringDataTypeDef *string_data); //压缩操作 uint8_t StartCompression(FILE *source,FILE *object,StringDataTypeDef string_data,FileBitQueue_TypeDef *queue); //解压操作 uint8_t StartDecompression(FILE *source,FILE *object,HuffmanNodeTypeDef *root); FILE *fp1,*fp2,*fp3,*fp4; int main() { //输入字符串的压缩操作 //GetString(&StringData); //BuildHuffmanTree(&StringData,&HuffmanHead); //建立哈夫曼树 //GetHuffmanCode(StringData,&HuffmanHead); //OutPutTreeCode(StringData,HuffmanHead); //OutPutStringCode(StringData); //GetHufmanRootNode(HuffmanHead); //AnalyseTreeCode(RootTreeNode); //FreeTreeCode(HuffmanHead.NextNode); //文件的压缩操作 fp1 = fopen("C:/Users/baozi/Desktop/test1.txt","rt"); if(fp1 == NULL) { printf("open file is fail!\n"); return 0; } fp2 = fopen("C:/Users/baozi/Desktop/test2.txt","wb+"); if(fp2 == NULL) { printf("open file is fail!\n"); return 0; } fp3 = fopen("C:/Users/baozi/Desktop/test3.txt","wb+"); if(fp3 == NULL) { printf("open file is fail!\n"); return 0; } OpenFile(fp1,&StringData); BuildHuffmanTree(&StringData,&HuffmanHead); //建立哈夫曼树 GetHuffmanCode(StringData,&HuffmanHead); OutPutTreeCode(StringData,HuffmanHead); GetHufmanRootNode(HuffmanHead); StartCompression(fp1,fp2,StringData,&FileBitQueue); StartDecompression(fp2,fp3,RootTreeNode); FreeTreeCode(HuffmanHead.NextNode); fclose(fp1); fclose(fp2); fclose(fp3); system("pause"); return 0; } uint8_t FreeTreeCode(HuffmanNodeTypeDef *node) { if(node == NULL)//该指针为空，则直接返回完成 { return 1; } if(FreeTreeCode(node->NextNode)) { free(node); return 1; } else { return 0; } } //获取改霍夫曼树的根节点 uint8_t GetHufmanRootNode(HuffmanNodeTypeDef head) { HuffmanNodeTypeDef *node = head.NextNode; while(node->Parent != NULL) { node = node->NextNode; } RootTreeNode = node; if(RootTreeNode != NULL) { return 1; } else { return 0; } } //查找该字符是否已经存在 uint8_t CharType_is_Exist(StringDataTypeDef *string_data,unsigned char char_data,unsigned char *char_id) { int i = 0; for(i = 0; i < string_data->CharTypeNum; i++) { if(string_data->ObjectString[i] == char_data) { *char_id = i; return 1; } } return 0; } //输出字符串数据（字符和频率） void OutPutStirngConstitute(StringDataTypeDef *string_data) { int i; for(i = 0;i < string_data->CharTypeNum; i++) { printf("字符%d为%c,次数为%d\t\n",i,string_data->ObjectString[i],string_data->StringCharTime[i]); } } //输出霍夫曼编码,全部编码，测试用 void OutPutTreeCode(StringDataTypeDef string_data,HuffmanNodeTypeDef head) { int i,j; HuffmanNodeTypeDef *tree_node = head.NextNode; for(i = 0;i < string_data.CharTypeNum; i++) { printf("字符%c的霍夫曼编码为:\t",tree_node->ch); for(j = tree_node->EndPlace;j > 0;j--) { printf("%d",tree_node->bit[j - 1]); } tree_node = tree_node->NextNode; printf("\n"); } } //输出单个树节点的霍夫曼编码 void OutPutPointTreeCode(HuffmanNodeTypeDef tree_node) { int j; for(j = tree_node.EndPlace;j > 0;j--) { printf("%d",tree_node.bit[j - 1]); } } //输出单个字符的霍夫曼编码 uint8_t OutPutPointHufmanCode(StringDataTypeDef string_data,char ch) { int i; for(i = 0;i < string_data.CharTypeNum;i++) { if(string_data.ObjectString[i] == ch)//找到相同的字符 { OutPutPointTreeCode(*string_data.CharPlace[i]); return 1; } } return 0;//失败 } //输出字符串的霍夫曼编码 void OutPutStringCode(StringDataTypeDef string_data) { int i; char ch; printf("编码为："); for(i = 0;i < (int)strlen(string_data.SurceString);i++) { ch = string_data.SurceString[i]; OutPutPointHufmanCode(string_data,ch); } printf("\n"); } //获取输入的字符串，并解析字符出现的次数 void GetString(StringDataTypeDef *string_data) { int i = 0; unsigned char char_id; printf("please input string!\n"); gets(string_data->SurceString); string_data->CharTypeNum = 0; for(i = 0;i < (int)strlen(string_data->SurceString);i++) { //若存在 if(CharType_is_Exist(string_data,string_data->SurceString[i],&char_id)) { string_data->StringCharTime[char_id] += 1; } else//不存在 { string_data->ObjectString[string_data->CharTypeNum] = string_data->SurceString[i]; string_data->StringCharTime[string_data->CharTypeNum] = 1; string_data->CharTypeNum += 1; } } OutPutStirngConstitute(string_data); } //根据权值，构建哈夫曼树 uint8_t BuildHuffmanTree(StringDataTypeDef *string_data,HuffmanNodeTypeDef *head) { int tree_node = (string_data->CharTypeNum * 2) - 1 ;//计算树的节点数 HuffmanNodeTypeDef *last_tree_node = head; HuffmanNodeTypeDef *star_new_tree ; int i,j,k; if(string_data->CharTypeNum <= 0)//数量错误，创建树失败 { printf("input string data is erro!\n"); FreeTreeCode(HuffmanHead.NextNode);//清空树 return 0; } //建立树的各个节点 （初始化树的链表） for(i = 0; i < tree_node; i++) { if(i < string_data->CharTypeNum ) { last_tree_node->NextNode = (HuffmanNodeTypeDef *)malloc(sizeof(HuffmanNodeTypeDef));//创建一个节点 if(last_tree_node->NextNode == NULL)//创建未成功 { //printf("create tree node is faile!\n");//创建树节点失败 //清空链表 FreeTreeCode(HuffmanHead.NextNode); return 0; } string_data->CharPlace[i] = last_tree_node->NextNode; //将树中字符位置保存在字符串结构体中，方面后面将字符串使用霍夫曼编码输出 last_tree_node->NextNode->ch = string_data->ObjectString[i]; last_tree_node->NextNode->Weight = string_data->StringCharTime[i];//赋值频率 last_tree_node->NextNode->L_Child = NULL; last_tree_node->NextNode->R_Child = NULL ; last_tree_node->NextNode->Parent = NULL; last_tree_node->NextNode->NextNode = NULL; last_tree_node->NextNode->EndPlace = 0; last_tree_node = last_tree_node->NextNode;//保存为上一次节点 // } } else { last_tree_node->NextNode = (HuffmanNodeTypeDef *)malloc(sizeof(HuffmanNodeTypeDef));//创建一个节点 if(last_tree_node->NextNode == NULL)//创建未成功 { printf("create tree node is faile!\n");//创建树节点失败 //清空链表 FreeTreeCode(HuffmanHead.NextNode); return 0; } last_tree_node = last_tree_node->NextNode; last_tree_node->ch = 0; last_tree_node->Weight = 0;//赋值频率 last_tree_node->L_Child = NULL; last_tree_node->R_Child = NULL ; last_tree_node->Parent = NULL; last_tree_node->NextNode = NULL; last_tree_node->EndPlace = 0; } } star_new_tree = head->NextNode; //对剩余的n = 总节点 - 叶子节点的节点,进行n次合并，形成新节点 for(k =0;k < string_data->CharTypeNum;k++) { star_new_tree = star_new_tree->NextNode; } for(i = string_data->CharTypeNum;i < tree_node;i++) { HuffmanNodeTypeDef *p1 = head->NextNode,*p2 = head->NextNode; int small_1 = 65535,samll_2 = 65535; last_tree_node = head->NextNode;//每次都从头节点进行轮询 for(j = 0;j < i;j++)//轮循到最后一个节点 { if(last_tree_node == NULL) { printf("read tree