我在做课程设计的时候选择了一道哈夫曼编码的题目。这道哈夫曼编码的题目与其他哈夫曼编码的不同之处在于--它涉及到了一些文件操作相关内容。题目如下在介绍哈夫曼编码之前我们先来介绍一下哈夫曼树。哈夫曼树是一种用于数据压缩的树。在n个带权叶子结点构造的所有二叉树中哈夫曼树的带权路径长度最小(带权路径长度是从根节点到该节点的路径长度与该节点上权的乘积)。我们可以通过贪心的算法思想来构造一颗哈夫曼树其过程如下(1)根据给定的n个权值对应的节点构成n颗二叉树的森林。(2)在森林中选取两颗结点的权值最小的子树作为左右子树构成一个新的二叉树并且置新二叉树的根节点的权值为其左右子树上根的权值之和。(3)在森林F中用新得到的二叉树代替这两棵树。(4)重复(2)和(3)两个过程直至只剩下一棵树这棵树就是哈夫曼树。根据以上算法思想我们可以得到如下的C语言代码#include stdbool.h #include stdio.h #include stdlib.h //结构体定义如下 #define N 30 typedef struct { char data; double weight; int parent; int lchild; int rchild; } HTNode; typedef struct { char cd[N]; int start; // 从start到N-1存储字符的哈夫曼编码 } HCode; // 建立哈夫曼树 void CreateHT(HTNode ht[], int n0) { int i, k, lnode, rnode; double min1, min2; for (i 0; i 2 * n0 - 1; i) { ht[i].parent ht[i].rchild ht[i].lchild -1; // 所有指针域置-1以便后续遍历数组不重复 } for (i n0; i 2 * n0 - 1; i) { min1 min2 32767; lnode rnode -1; // 在ht[0,i-1]寻找两个权值最小的节点 for (k 0; k i; k) { // 只在双亲为-1还没构造二叉树的节点找 if (ht[k].parent -1) { if (ht[k].weight min1) { min2 min1; // min2固定为次最小该哈夫曼树中左孩子权值一定比右孩子小 rnode lnode; min1 ht[k].weight; lnode k; } // 处理min1权值min2的情况 else if (ht[k].weight min2) { min2 ht[k].weight; rnode k; } } } ht[i].weight ht[lnode].weight ht[rnode].weight; ht[i].lchild lnode; ht[i].rchild rnode; ht[lnode].parent ht[rnode].parent i; } }接下来我们讲讲哈夫曼编码。哈夫曼编码是一种前缀码即任一字符的哈夫曼编码不可能是另一个字符的哈夫曼编码的前缀(说实话我觉得叫非前缀码会更好记一点)。它建立在哈夫曼树的基础上规定哈夫曼树左分支为0右分支为1则从根节点到每个叶子结点所经过的分支对应的0和1的序列就是该节点对应字符的编码。哈夫曼编码的结构体类型在上述代码中已经给出就是HCode。进行哈夫曼编码的算法思路如下对于当前的叶子结点ht[i]现将对应的hcd[i]的start置初值0找其双亲节点ht[f]若当前节点是双亲节点的左孩子节点则在hcd[i]的cd数组中添加0若为右孩子节点则添加1添加完成后将start域减1。再对双亲节点进行同样的操作直至达到根节点。对应代码如下void CreateHCode(HTNode ht[], HCode hcd[], int n0) { int i, f, c; HCode hc; for (i 0; i n0; i) { hc.start n0, c i; f ht[i].parent; while (f ! -1) { if (ht[f].lchild c) { hc.cd[hc.start--] 0; // 左分支编0 } else { hc.cd[hc.start--] 1; // 右分支编1 } c f; f ht[f].parent; } hc.start; // 在执行完最后一次操作后需要把start1,指向数组第一个元素 hcd[i] hc; // hc临时存放i的哈夫曼编码最后用hcd来保存所有叶子结点的编码 } }其实到这哈夫曼编码的核心思想就已经完成了但为了完成题目要求我们还需要添加文件操作相关的代码。// 使用全局变量 HTNode *ht NULL; // 动态分配的哈夫曼树数组 HCode *hcd NULL; // 叶子结点编码表 int n0 0; // 叶子结点个数字符集大小 int treeLoaded 0; // 标记哈夫曼树是否已在内存中// 初始化 void InitSystem() { int i; printf(请输入字符集大小n0:\n); scanf(%d, n0); getchar(); // 缓冲回车键 ht (HTNode *)malloc((2 * n0 - 1) * sizeof(HTNode)); hcd (HCode *)malloc(n0 * sizeof(HCode)); printf(请输入%d个字符和它的权值(出现的频率)\n); printf(输出样例:a 10\n); for (i 0; i n0; i) { printf(第 %d 个字符和权值: \n, i 1); scanf(%c %lf, ht[i].data, ht[i].weight); getchar(); // 吸收回车 } CreateHT(ht, n0); CreateHCode(ht, hcd, n0); SaveTreeToFile(hfmTree); treeLoaded 1; // 哈夫曼树在内存中了 printf(初始化完成哈夫曼树已存入文件 hfmTree\n); } // 保存哈夫曼树到文件 该功能由deepseek生成 void SaveTreeToFile(const char *filename) { FILE *fp fopen(filename, wb); // 二进制写入,若存在原有文件就会把原内容清空不存在就会创建该名的文件 if (!fp) { printf(无法打开文件 %s 进行写入\n, filename); return; } // 打开失败 // 保存叶子结点个数 fwrite(n0, sizeof(int), 1, fp); // 文件中必须存n0否则下次打开该文件时程序不知道读取几个HTNode。下一次运行程序的时候n00所以需要存n0 // 保存整棵树 (2*n0-1 个结点) fwrite(ht, sizeof(HTNode), 2 * n0 - 1, fp); fclose(fp); } // 从文件加载哈夫曼树 该功能由deepseek生成 int LoadTreeFromFile(const char *filename) { FILE *fp fopen(filename, rb); if (!fp) { printf(文件 %s 不存在请先执行初始化 (I)\n, filename); return 0; } // 读入叶子结点个数 fread(n0, sizeof(int), 1, fp); // 重新分配内存 if (ht ! NULL) free(ht); if (hcd ! NULL) free(hcd); ht (HTNode *)malloc((2 * n0 - 1) * sizeof(HTNode)); hcd (HCode *)malloc(n0 * sizeof(HCode)); // 读入整棵树 fread(ht, sizeof(HTNode), 2 * n0 - 1, fp); fclose(fp); // 根据树重新生成编码表 CreateHCode(ht, hcd, n0); treeLoaded 1; printf(从文件 %s 加载哈夫曼树成功\n, filename); return 1; } // 编码并存入文件夹中 void Encoding() { // 哈夫曼树不在内存中就从文件中打开 if (!treeLoaded) { if (!LoadTreeFromFile(hfmTree)) return; // 打开失败,直接返回 } FILE *fToBeTran fopen(ToBeTran, r); if (!fToBeTran) { printf(无法打开文件 ToBeTran,请确保该文件存在\n); return; } FILE *fCodeFile fopen(CodeFile, w); if (!fCodeFile) { printf(无法创建文件 CodeFile\n); fclose(fToBeTran); return; } char ch; int i, j, found; // 逐字符读取待编码文件 while ((ch fgetc(fToBeTran)) ! EOF) // EOF是读到了文件末尾 { found 0; // 标记该字符是否在字符集哈夫曼树种 // 查找字符对应的编码 for (i 0; i n0; i) { if (ht[i].data ch) { // 输出编码到 CodeFile for (j hcd[i].start; j n0; j) { fputc(hcd[i].cd[j], fCodeFile); } found 1; break; } } if (!found) { printf(警告字符 %c 不在字符集中已忽略\n, ch); } } fclose(fToBeTran); fclose(fCodeFile); printf(编码完成结果已存入文件 CodeFile\n\n); } // 译码功能 void Decoding() { if (!treeLoaded) { if (!LoadTreeFromFile(hfmTree)) return; } FILE *fCodeFile fopen(CodeFile, r); if (!fCodeFile) { printf(无法打开文件 CodeFile请先进行编码 (E)\n); return; } FILE *fTextFile fopen(TextFile, w); if (!fTextFile) { printf(无法创建文件 TextFile\n); fclose(fCodeFile); return; } // 从根节点开始走0走左1走右直到走到叶子结点读取叶子结点的信息 int root 2 * n0 - 2; // 根结点下标 int cur root; int bit; // fgetc返回int类型 while ((bit fgetc(fCodeFile)) ! EOF) { if (bit 0) cur ht[cur].lchild; else if (bit 1) cur ht[cur].rchild; else { // 忽略空白字符 continue; } // 如果到达叶子结点输出字符并回到根 if (ht[cur].lchild -1 ht[cur].rchild -1) { fputc(ht[cur].data, fTextFile); cur root; // 从root开始重新遍历 } } fclose(fCodeFile); fclose(fTextFile); printf(译码完成结果已存入文件 TextFile\n\n); } // 打印代码文件 void PrintCodeFile() { FILE *fCodeFile fopen(CodeFile, r); if (fCodeFile NULL) { printf(打开文件失败,请先编码); return; } FILE *fCodePrin fopen(CodePrin, w); if (!fCodePrin) { printf(创建文件失败); fclose(fCodeFile); return; } int bit; // fgetc的返回值是int类型的 int count 0; while ((bit fgetc(fCodeFile)) ! EOF) { count; putchar(bit); // 按照ASCII码表输出 fputc(bit, fCodePrin); // 会按照ASCII码表转化成字符后存入文件 if (count % 50 0) { printf(\n); fputc(\n, fCodePrin); } } if (count % 50 ! 0) { printf(\n); fputc(\n, fCodePrin); } printf(打印完毕,并且已存入文件CodePrin); fclose(fCodeFile); fclose(fCodePrin); }接下来我再讲一下用凹入表示法打印一棵二叉树。对于一颗二叉树我们要用凹入表示法打印出来可以采用递归的方式。先打印右子树再打印根在打印左子树然后根据层级来进行缩进。// 用凹入表示法打印哈夫曼树(递归) 两个函数 void PrintTreeRecursive(HTNode ht[], int root, int level, FILE *fp) { if (root -1) { return; } // 打印顺序右子树-根-左子树所以右孩子都在双亲节点的上方 PrintTreeRecursive(ht, ht[root].rchild, level 1, fp); // 打印本节点 for (int i 0; i level; i) { printf( ); fprintf(fp, ); // 打印入文件中 } // 叶子结点打印权值和字符数据非叶子结点打印权值 if (ht[root].lchild -1 ht[root].rchild -1) { printf(%c(%.2f)\n, ht[root].data, ht[root].weight); fprintf(fp, %c(%.2f)\n, ht[root].data, ht[root].weight); } else { printf(%.2f\n, ht[root].weight); fprintf(fp, %.2f\n, ht[root].weight); } PrintTreeRecursive(ht, ht[root].lchild, level 1, fp); } void PrintTree() { if (!treeLoaded) { if (!LoadTreeFromFile(hfmTree)) { return; } } FILE *fTreePrint fopen(TreePrint, w); if (!fTreePrint) { printf(无法创建文件 TreePrint\n); return; } int root 2 * n0 - 2; printf(凹入表示法打印哈夫曼树); PrintTreeRecursive(ht, root, 0, fTreePrint); printf(树形显示结束同时已写入文件 TreePrint\n); fclose(fTreePrint); }写一个主菜单和main函数调用以上代码// 主菜单 void ShowMenu() { printf(\n 哈夫曼编/译码器 \n); printf( I - 初始化建立哈夫曼树\n); printf( E - 编码将 ToBeTran 编码为 CodeFile\n); printf( D - 译码将 CodeFile 译码为 TextFile\n); printf( P - 印代码文件显示 CodeFile 内容\n); printf( T - 印哈夫曼树\n); printf( Q - 退出程序\n); printf(\n); printf(请选择功能: ); } int main() { char choice; while (1) { ShowMenu(); choice getchar(); getchar(); // 吸收回车 switch (choice) { case I: case i: InitSystem(); break; case E: case e: Encoding(); break; case D: case d: Decoding(); break; case P: case p: PrintCodeFile(); break; case T: case t: PrintTree(); break; case Q: case q: // 释放动态内存 if (ht) free(ht); if (hcd) free(hcd); printf(程序退出。\n); return 0; default: printf(无效选择请重新输入\n); } } return 0; }