高校工会网站建设,郑州公司网页,深圳建设营销型网站,微信小程序开发工具怎么用数据结构-----哈夫曼编译码器 题目题目描述基本要求算法分析 代码实现初始化编码解码打印代码打印哈夫曼树 总结 题目
题目描述
利用哈夫曼编码进行信息通信可大大提高信道利用率#xff0c;缩短信息传输时间#xff0c;降低传输成本。 要求#xff1a;在发送端通过一个编… 数据结构-----哈夫曼编译码器 题目题目描述基本要求算法分析 代码实现初始化编码解码打印代码打印哈夫曼树 总结 题目
题目描述
利用哈夫曼编码进行信息通信可大大提高信道利用率缩短信息传输时间降低传输成本。 要求在发送端通过一个编码系统对待传数据预先编码在接收端将传入的数据进行译码复原。对于双工信道(即可以双向传输信息的信道)每端都需要个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼的编/译码系统。
基本要求
基本要求 系统应具有以下功能 ① I:初始化.从终端读入字符集大小n及n个字符和n个权值建立哈夫曼树井将它存于文件HuffmanTree中。 ② C:编码。利用已建立好的哈夫曼树如不在内存则从文件HuffmanTree中读入。对文件tobetrans中的正文进行编码然后将结果存入文件codefile中。 ③ D:解码。利用已建立好的哈夫曼树将文件codefile中的代码进行译码结果存入testfile中。 ④ P打印代码文件。将文件codefile以紧凑格式显示在终端上每行50个代码。同时将此字符形式的编码文件写入文件codeprint中。 ⑤ T打印哈夫曼树。将已在内存中的哈夫曼树直观的方式树或凹入表形式显示在终端上同时将此字符形式的哈夫曼树写入文件treeprint中。
算法分析
本题例主要用到3个算法如下 ① 哈夫曼编码。在初始化(I)的过程中要用输入的字符和权值建立哈夫曼树并求得哈夫曼编码。先将输入的字符和权值放到一个结构体数据中建立哈夫曼树将计算所得的哈夫曼编码存储到另一个结构体数组中。 ② 串的匹配。在解码(D)的过程中要对已经编码过的代码进行译码可利用循环将代码中与哈夫曼编码长度相同的串与这个哈夫曼编码进行比较如果相等就回显并存入文件。 ③二叉树的遍历。在打印哈夫曼树(T)的过程中因为哈夫曼树也是二叉树所以就要利用二叉树的前序遍历将哈夫曼树输出。
代码实现
代码部分参考了《数据结构-C语言版第2版》这本书中代码以及C风格进行书写测试文件tobetrans中的内容为ABCABC
初始化
题目要求从终端读入字符集大小n及n个字符和n个权值建立哈夫曼树并将它存于文件HuffmanTree中可以先将哈夫曼树构建起来得到哈夫曼树及其对应叶子节点的编码再通过文件的输入输出将这些编码写入文件HuffmanTree中即可
构造哈夫曼树
/*找出森林集合中根权值最小的两个*/
void Select(HuffmanTree HT,int len,int s1,int s2)
{int i,min10x3f3f3f3f,min20x3f3f3f3f;//先赋予最大值for(i1;ilen;i){if(HT[i].weightmin1HT[i].parent0){min1HT[i].weight;s1i;} }int tempHT[s1].weight;//将原值存放起来然后先赋予最大值防止s1被重复选择HT[s1].weight0x3f3f3f3f;for(i1;ilen;i){if(HT[i].weightmin2HT[i].parent0){min2HT[i].weight;s2i;}}HT[s1].weighttemp;//恢复原来的值
}/*构建哈夫曼树*/
void CreatHuffmanTree(HuffmanTree HT,int n)
{//构造赫夫曼树HTint m,s1,s2,i;if(n1) return;m2*n-1;HTnew HTNode[m1]; //0号单元未用所以需要动态分配m1个单元HT[m]表示根结点 for(i1;im;i) //将1~m号单元中的双亲、左孩子右孩子的下标都初始化为0 { HT[i].parent0; HT[i].lchild0; HT[i].rchild0; }cout请输入叶子结点的字符和权值\n;for(i1;in;i) //输入前n个单元中叶子结点的权值 cinHT[i].sHT[i].weight; /*――――――――――初始化工作结束下面开始创建赫夫曼树――――――――――*/ for(in1;im;i) { //通过n-1次的选择、删除、合并来创建赫夫曼树Select(HT,i-1,s1,s2);//在HT[k](1≤k≤i-1)中选择两个其双亲域为0且权值最小的结点,// 并返回它们在HT中的序号s1和s2HT[s1].parenti; HT[s2].parenti; //得到新结点i从森林中删除s1s2将s1和s2的双亲域由0改为iHT[i].lchilds1; HT[i].rchilds2; //s1,s2分别作为i的左右孩子HT[i].weightHT[s1].weightHT[s2].weight; //i 的权值为左右孩子权值之和}
}哈夫曼编码
/*哈夫曼树编码*/
void CreatHuffmanCode(HuffmanTree HT,HuffmanCode HC,int n)
{//从叶子到根逆向求每个字符的赫夫曼编码存储在编码表HC中int i,start,c,f;HCnew char*[n1]; //分配n个字符编码的头指针矢量char *cdnew char[n]; //分配临时存放编码的动态数组空间cd[n-1]\0; //编码结束符for(i1;in;i){ //逐个字符求赫夫曼编码startn-1; //start开始时指向最后即编码结束符位置ci; fHT[i].parent; //f指向结点c的双亲结点while(f!0){ //从叶子结点开始向上回溯直到根结点--start; //回溯一次start向前指一个位置if(HT[f].lchildc) cd[start]0; //结点c是f的左孩子则生成代码0else cd[start]1; //结点c是f的右孩子则生成代码1cf; fHT[f].parent; //继续向上回溯} //求出第i个字符的编码 HC[i]new char[n-start]; // 为第i 个字符编码分配空间strcpy(HC[i], cd[start]); //将求得的编码从临时空间cd复制到HC的当前行中}delete cd; //释放临时空间
}将编码写入到文件HuffmanTree 这里通过循环将构造好的哈夫曼编码直接写入到文件
//编码写入文件HuffmanTree.txt
void printCreatHuffmanCode(HuffmanTree HT, HuffmanCode HC,int n)
{ofstream hFile(HuffmanTree.txt);if (!hFile.is_open()) {cout 文件HuffmanTree.txt打开失败. endl;exit(1);} cout各字符对应的编码如下endl; for (int i 1; i n; i){cout HT[i].s HC[i] endl;hFile HT[i].s HC[i]endl; }hFile.close();cout 成功写入文件HuffmanTree.txt endl;
}初始化部分运行截图如下
编码
思路通过文件逐行读出字符并将其存放到数组通过遍历该数组以及哈夫曼树从而将对应的编码写入到文件codefile.txt中
//编码部分
void Huffmancode(HuffmanTree HT,HuffmanCode HC,int n) {// 函数用于对 tobetrans.txt 文件中的内容进行编码并将结果存储在 codefile.txt 文件中// 假设 tobetrans.txt 包含要编码的内容每一行表示一个要编码的字符串。ifstream tFile(tobetrans.txt);//读 ofstream cFile(codefile.txt);//写 if (!tFile.is_open()) {cout 文件tobetrans.txt打开失败.\nendl;exit(1);}if (!cFile.is_open()) {cout 文件codefile.txt打开失败.\nendl;exit(1);}char tobetrans[100];//临时存放文件中每一行的字符 // 逐行读取内容while (tFile.getline(tobetrans, sizeof(tobetrans))) {//行不空 int m strlen(tobetrans);//数组长度即每一行字符个数couttobetrans内容tobetrans; coutendl; for (int i 0; i m; i) {//遍历数组 for(int j1;jn;j) //遍历树节点0号单元为根节点未启用 {if (HT[j].s tobetrans[i]) {//相等则将其对应的编码写入文件 cFile HC[j];}}}}tFile.close();cFile.close();cout成功写入文件codefile.txtendl;}编码部分运行截图如下
解码
思路和编码部分一样先从文件逐行读出存入数组接着再遍历该数组和树的节点从而将对应的字符写入到testfile.txt中
//译码部分
void HuffmanDecode(HuffmanTree HT, int n) {//函数用于利用已建立好的哈夫曼树将文件codefile.txt中的代码进行译码结果存入testfile.txt中ifstream codeFile(codefile.txt);//读 ofstream testFile(testfile.txt);//写 if (!codeFile.is_open()) {cout 文件codefile.txt打开失败.\nendl;exit(1);}if (!testFile.is_open()) {cout 文件testfile.txt打开失败.\nendl;exit(1);}char pwd[100];codeFile.getline(pwd, sizeof(pwd));//每次读取一行放入数组pwd中进行译码 int len strlen(pwd);int i 0;int node 2 * n - 1;//从根节点开始 while (i len) { // 循环遍历读取数组中的每个字符while (HT[node].lchild ! 0 HT[node].rchild ! 0) { // 当当前节点不是叶子节点时循环if (pwd[i] 0) { // 如果当前读取的字符是 0node HT[node].lchild; // 移动到当前节点的左孩子节点} else if (pwd[i] 1) { // 如果当前读取的字符是 1node HT[node].rchild; // 移动到当前节点的右孩子节点}i; // 移动到下一个字符}testFile HT[node].s; // 将叶子节点对应的字符写入到输出文件中node 2 * n - 1; // 将节点移动回到根节点}codeFile.close();testFile.close();cout 成功写入文件testfile.txt endl;}解码部分运行截图如下
打印代码
思路通过文件逐行读出二进制码在根据题目要求将对应的格式输出到终端输入到文件我这里以每5行为例
//打印代码文件
void Print()
{//函数用于将文件codefile.txt以紧凑格式显示在终端上每行5个代码。//同时将此字符形式的编码文件写入文件codeprint.txt中。 char str[1000];//存储codefile.txt的0-1编码 int num 0;ifstream file1(codefile.txt);//读出 ofstream file2(codeprint.txt);//写入 if(file1.fail()){cout文件codefile.txt打开失败endl;exit(0);}if(file2.fail()){cout文件codeprint.txt打开失败endl;exit(0);}file1.getline(str, 10000);//读取每一行coutstr内容str; coutendl;cout文件codefile.txt内容显示如下endl; while(str[num]){if(num%50num!0)//每输出5个字符换行由于数组下标从0开始所以要忽略num0这个情况 {coutendl; file2endl;//文件里也是每5个字符换行 }coutstr[num];file2str[num];//写入文件 num; }coutendl;file1.close();file2.close();cout成功写入文件codeprint.txtendl; }打印代码部分运行截图如下
打印哈夫曼树
这里结合树的前序遍历并以凹入表的形式进行输出
void PrintHuffmanTree(HuffmanTree HT, int root, int level) {// 递归打印哈夫曼树的结构凹入表形式if (root ! 0) {// 打开文件 treeprint.txtofstream treeFile(treeprint.txt, ios::app); // 使用 ios::app 追加模式if (treeFile.fail()) {cout 文件 treeprint.txt 打开失败 endl;exit(0);}// 输出当前节点信息以凹入表形式cout string(4 * level, ); // 控制缩进cout HT[root].weight;//输出节点权值 if (HT[root].s) {cout ( HT[root].s );//节点字符 }cout endl;treeFile string(4 * level, );treeFile HT[root].weight;if (HT[root].s) {treeFile ( HT[root].s );}treeFile endl;// 递归打印左右子树PrintHuffmanTree(HT, HT[root].lchild, level 1);PrintHuffmanTree(HT, HT[root].rchild, level 1);}
}打印哈夫曼树运行截图如下
总结
关于如何书写一个哈夫曼编译码器以上代码大家可以参考仅供参考毕竟我写的也不是很优秀只能做到题目的要求代码中还有许多可以优化的地方介于自己能力有限就先分享这么多大家如果在参考以上代码存在问题时需要我自己书写的完整代码可以私信我哦在此感谢各位大佬的支持
