数据结构作业-6.2哈夫曼树

#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 coutReading...endl; infile.getline(source,MaxSize); //读取一行到source数组 coutsourceendl; infile.close(); return OK; } Status WordCount(char *data,NumCount *paraCnt){//统计每个字符出现多少次 int len strlen(data); // 文本总长度 for(int i0;ilen;i){ int flag0; // 看看这个字符之前有没有统计过 for(int j0;jparaCnt-length;j){ if(paraCnt-count[j].ch data[i]){ paraCnt-count[j].cnt; // 次数1 flag1; 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[m1]; //开辟数组空间 // 1. 初始化所有节点 for(int i1;im;i){ HT[i].parent0; HT[i].lchild0; HT[i].rchild0; } // 2. 填入叶子节点字符和权重 for(int i1;ilength;i){ HT[i].data cntarray.count[i-1].ch; HT[i].weight cntarray.count[i-1].cnt; } // 3. 循环合并最小两个节点 for(int ilength1;im;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 i1;itop;i){ if(HT[i].weight min HT[i].parent 0){ min HT[i].weight; *s1 i; } } // 找次小 min INT_MAX; for(int i1;itop;i){ if(HT[i].weight min i!*s1 HT[i].parent0){ min HT[i].weight; *s2 i; } } return OK; } Status CreateHuffmanCode(HuffmanTree HT,HuffmanCode HC,int length){//生成编码 HC new HCode[length1]; 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) { outfileHC[j].str; } } } outfile.close(); coutthe code txt has been writtenendl; coutendl; 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) // 如果已经是叶子节点输出到输出文件中然后重新回到根节点 { outfileHT[root].data; root 2*length-1; } } outfile.close(); coutthe output txt has been writtenendl; coutendl; return OK; }