#include <stdio.h> #include <fstream>//文件读写 #include <string.h>//字符串操作（strcpy,strlen) #define MaxSize 1024//读取文件最大长度 #define OK 1 #define ERROR 0 typedef int Status;//用 Status代表函数返回状态（成功/失败） typedef struct wordcnt{ char ch;//统计字符 int cnt = 0;//统计这个字符出现了多少次 }Count; typedef struct NumCount{ //封装上面所有的字符和长度 Count count[MaxSize];//存所有的字符和长度 int length = 0;//实际有多少种不同字符 }NumCount; typrdef struct HTree{//哈夫曼树结构 int data; int weight;//权重（出现次数） int parent,lchild,rchile;//下标 }HTNode,*HuffmanTree; typedef struct HCode{//编码结构 char data;//对应字符 char* str;//编码字符串 }*HuffmanCode; //函数声明 Status ReadData(char *source); // 读入文件 Status WordCount(char *data,NumCount *paraCnt); // 统计次数 Status Show(NumCount *paraCnt); // 展示次数 Status CreateHuffmanTree(HuffmanTree &HT,int length,NumCount cntarray); // 创建哈夫曼树 Status select(HuffmanTree HT,int top,int *s1,int *s2); // 选择权重最小的两个节点 Status CreateHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int length); // 创建哈夫曼编码 Status Encode(char *data,HuffmanCode HC,int length); // 将读入的文件编码，写到txt文件 Status Decode(HuffmanTree HT,int length); //读入编码文件，解码 //主函数 int main() { char data[MaxSize];//存读入的文本 NumCount Cntarray;//存字符统计结果 ReadData(data);// 1.读 in.txt WordCount(data,&Cntarray); // 2.统计字符次数 HuffmanTree tree; CreateHuffmanTree(tree,Cntarray.length,Cntarray); //3.建树 HuffmanCode code; CreateHuffmanCode(tree,code,Cntarray.length);//4.生成编码 Encode(data,code,Cntarray.length); //5.编码写入code.txt Decode(tree,Cntarray.length);//6.解码写入out.txt cout<<"完成！查看文件即可"<<endl; return 0; } Status ReadData(char *source){//读取文本文件 ifstream infile;// 输入文件流 infile.open("in.txt");//打开in.txt cout<<"Reading..."<<endl; infile.getline(source,MaxSize); //读取一行到source数组 cout<<source<<endl; infile.close(); return OK; } Status WordCount(char *data,NumCount *paraCnt){//统计每个字符出现多少次 int len = strlen(data); // 文本总长度 for(int i=0;i<len;i++){ int flag=0; // 看看这个字符之前有没有统计过 for(int j=0;j<paraCnt->length;j++){ if(paraCnt->count[j].ch == data[i]){ paraCnt->count[j].cnt++; // 次数+1 flag=1; break; } } if(!flag){ // 没统计过，新增 paraCnt->count[paraCnt->length].ch = data[i]; paraCnt->count[paraCnt->length].cnt++; paraCnt->length++; } } return OK; } Status CreateHuffmanTree(HuffmanTree &HT,int length,NumCount cntarray){//构建哈夫曼树 int m = length*2-1; //总节点数 = 2*叶子数-1//两个孩子构成一个新节点 HT = new HTNode[m+1]; //开辟数组空间 // 1. 初始化所有节点 for(int i=1;i<=m;i++){ HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; } // 2. 填入叶子节点（字符和权重） for(int i=1;i<=length;i++){ HT[i].data = cntarray.count[i-1].ch; HT[i].weight = cntarray.count[i-1].cnt; } // 3. 循环合并最小两个节点 for(int i=length+1;i<=m;i++){ int s1,s2; select(HT,i-1,&s1,&s2); // 选最小两个 HT[s1].parent = i; HT[s2].parent = i; HT[i].lchild = s1; HT[i].rchild = s2; HT[i].weight = HT[s1].weight + HT[s2].weight;//得到新节点 } return OK; } Status select(HuffmanTree HT,int top,int *s1,int *s2){//选出权重最小的两个节点 int min = INT_MAX; // 找最小 for(int i=1;i<=top;i++){ if(HT[i].weight < min && HT[i].parent == 0){ min = HT[i].weight; *s1 = i; } } // 找次小 min = INT_MAX; for(int i=1;i<=top;i++){ if(HT[i].weight < min && i!=*s1 && HT[i].parent==0){ min = HT[i].weight; *s2 = i; } } return OK; } Status CreateHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int length){//生成编码 HC = new HCode[length+1]; char *cd = new char[length]; // 存储编码的临时空间 cd[length-1] = '\0'; // 方便之后调用strcpy函数 int c,f,start; for(int i = 1;i <= length;++i) { start = length-1; // start表示编码在临时空间内的起始下标，由于是从叶子节点回溯，所以是从最后开始 c = i; f = HT[c].parent; while(f != 0) { --start; //由于是回溯，所以从临时空间的最后往回计 if(HT[f].lchild == c) cd[start] = '0'; else cd[start] = '1'; c = f; f = HT[c].parent; } HC[i].str = new char[length-start]; // 最后，实际使用的编码空间大小是length-start HC[i].data = HT[i].data; strcpy(HC[i].str,&cd[start]); // 从实际起始地址开始，拷贝到编码结构中 } delete cd; } Status Encode(char *data,HuffmanCode HC,int length) { ofstream outfile; outfile.open("code.txt"); for(int i = 0;i < strlen(data);++i) // 依次读入数据，查找对应的编码，写入编码文件 { for(int j = 1;j <= length;++j) { if(data[i] == HC[j].data) { outfile<<HC[j].str; } } } outfile.close(); cout<<"the code txt has been written"<<endl; cout<<endl; return OK; } Status Decode(HuffmanTree HT,int length) { char codetxt[MaxSize*length]; ifstream infile; infile.open("code.txt"); infile.getline(codetxt,MaxSize*length); infile.close(); ofstream outfile; outfile.open("out.txt"); int root = 2*length-1; // 从根节点开始遍历 for(int i = 0;i < strlen(codetxt);++i) { if(codetxt[i] == '0') root = HT[root].lchild; //为0表示向左遍历 else if(codetxt[i] == '1') root = HT[root].rchild; //为1表示向右遍历 if(HT[root].lchild == 0 && HT[root].rchild == 0) // 如果已经是叶子节点，输出到输出文件中，然后重新回到根节点 { outfile<<HT[root].data; root = 2*length-1; } } outfile.close(); cout<<"the output txt has been written"<<endl; cout<<endl; return OK; }
