简介这份文档面向数据结构课程设计学习者围绕基于Huffman编码的文件压缩与解压缩项目给出可参考的课程设计报告与实现思路。正文覆盖总体设计、详细数据结构与算法设计、主要函数说明、程序测试报告、结论及源程序附录串联字符频率统计、Huffman树构建、编码表存储、按位读写、压缩比输出与解压还原等环节并对HTNode、Huffmancode结构体、命令行输入输出流程和代码注释规范作了说明。包内共1个docx文件约1.41MB以报告文档为主便于查阅、打印和整理。已有1061人学习适合需要完成同类课设、理解Huffman编码应用或补充C语言文件处理实践的学习者参考。1. 从一个 117% 的压缩比说起这套 Huffman 课设真正要交付的东西一份测试记录里躺着这样一行数据JPG 文件压缩后是原文件的 117.76%Mp4 是 99.99%而纯文本 txt 只有 33.02%。只看「压缩」两个字前两行像是翻车实际上这是 Huffman 编码在真实文件上的正常表现也是数据结构课程设计里最值得讲清楚的一件事。这套基于 Huffman 编码的文件压缩与解压缩课设要交付的不是一个能打赢 zip 的工具而是两个能用命令行跑起来的 C 程序一个读源文件吐出压缩文件一个读压缩文件还原出与源文件逐字节一致的目标文件外加一份能把数据结构、算法、T(n) 和测试数据都讲圆的设计报告。适合正在做数据结构课设、需要一个能直接照着搭骨架的人。2. 需求拆解与技术选型字节符号表 两遍扫描 位流输出2.1 把任务书上的四句话翻译成可勾选的验收项任务书上的文字往往写得很客气落到验收现场就变成一条条能不能当场跑出来的动作。我习惯先把原始要求逐条翻译成功能点再倒推需要哪些函数和哪些文件格式字段这样报告里的「总体设计」一节基本就是翻译表扩写不会写着写着跑偏。原始要求翻译成功能点现场验收动作完成两个 C 语言程序压缩端与解压端各自独立编译不共享可执行文件只保留解压程序源码也能单独构建成功命令行参数输入源文件与目标文件入口判断 argc取 argv[1]、argv[2]源文件不存在则退出目标文件不存在则创建故意传一个不存在的源文件名看是否打印提示并退出压缩时两遍扫描源文件第一遍只统计符号种类与频次第二遍才编码输出在第一遍结束后打印符号种类数与手算结果比对符号表与 Huffman 树存进压缩文件压缩文件头部自带符号种类数与每组的字符、权重解压端不依赖源文件压完把源文件删掉再解压看是否能还原第二行和第四行是很多方案里最容易含糊过去的地方。命令行参数这块常见做法是用argc ! 3直接拒绝打印一行用法提示返回非 0 退出码「目标文件不存在则创建」不需要额外写creatfopen(..., wb)本身就会创建写wb而不是w这件事后面还会单独说。第四行决定了整个压缩文件的格式设计方向。把码表写进压缩文件解压端才能独立工作如果不写解压时必须回头读原文件重建树那就不叫解压了叫「对照还原」。这一条也顺带解释了为什么结构体里用int存左右孩子下标而不是指针——下标是可以序列化的指针不行。2.2 符号集取 0 到 255而不是可见字符题目里给了一个很小的例子19 字节的文件aaBBaaaaccBBB符号种类数是 5五个符号分别是 97、66、99、13、10频率分别是 6/19、5/19、2/19、3/19、3/19。13 和 10 这一对值得多看两眼它们就是回车和换行在文本文件里几乎必然出现。如果符号集只取可见 ASCII32 到 126这两个符号就会被漏掉统计总数对不上文件长度编码表里查不到它们压缩到那一字节时直接崩或者写出垃圾。所以符号集老老实实取unsigned char的 0 到 255覆盖所有可能的字节值。这里有个血泪教训如果用char声明字符变量在多数编译器上它是有符号的读到 0x80 以上的字节会变成负数拿它当下标去访问charnum[ch]就直接越界而且越界得毫无声息可能跑十次才崩一次。全程用unsigned char只在fgetc的返回值上留一个int中转。数组长度取N 257而不是 256是因为这套实现里所有树节点下标从 1 开始。0 号下标空着不用parent 0就成了「这个节点还没有父节点」的天然标记lchild 0 rchild 0就成了「这是叶子」的判断依据。省掉一个额外的布尔数组代价是浪费一个HTNode的空间这笔账很划算。#define N 257 /* 0 号下标不用parent0 表示尚未合并lchildrchild0 表示叶子 */ unsigned char buf[256]; /* 实际用得上的只有 0..255 */统计频次的那一趟用一个double charnum[257]或者unsigned long count[257]全局数组就够每读一字节charnum[ch]同时累加总长度。总长度也可以直接用fseek(fp, 0, SEEK_END)加ftell拿到比边读边数少一次累加但两种都要rewind回到文件开头才能开始第二遍。2.3 两遍扫描与一次读全的取舍题目明确建议两遍扫描第一遍统计第二遍编码。也有人图省事fread把整个文件读进内存统计和编码都在内存里做最后一次性写盘。两种都能跑出正确结果区别在于报告里怎么写 T(n) 和空间复杂度。两遍扫描的代价是 2n 次字节读空间是常数级一个 257 项的计数数组加一棵最多 513 个节点的树。一次读全的代价是 n 次读加 O(n) 的堆内存对几十 MB 的文件还能接受对上百 MB 的文件就要小心了。我一般会按题目原意走两遍扫描因为fseek、ftell、rewind这一套文件定位操作本身就是这个课设想让人练熟的东西答辩时被问到「你怎么知道文件多大」也答得干脆。建树部分的复杂度更值得写进报告。每合并一次要在剩下的节点里找权值最小的两个线性扫描是 O(k)一共合并 k-1 次整体 O(k²)。k 最大 256k² 大约六万五千次比较实际耗时可以忽略。用最小堆可以把这一段压到 O(k log k)但代码量差不多翻倍报告页码有限收益不明显。写报告的时候把这个权衡写出来比单纯贴一句「时间复杂度 O(n log n)」要有说服力得多。整个压缩流程的 T(n) 可以这样拆第一遍扫描 O(n)建树 O(k²)求码表 O(k·L)L 是最长码长不超过 k-1第二遍扫描 O(n·L̄)L̄ 是平均码长。因为 k ≤ 256 是常数上界整体可以写成 O(n)但报告里把 k 保留着写阅卷的人一眼就能看出你是真推过而不是抄的。3. 数据结构与压缩文件格式树、码表、位缓冲区三件套的落盘约定3.1 HuffmanTree 与 Huffmancode 的结构定义与下标约定树和码表的结构定义直接决定了后面所有函数的签名。#define N 257 typedef struct Node { unsigned char ch; /* 叶子代表的字节值 0-255内部节点此字段无意义 */ double weight; /* 频次或归一化后的概率 */ int parent, lchild, rchild; /* 存下标不存指针0 表示空 */ } HTNode, HuffmanTree[2 * N - 1]; typedef struct { unsigned char ch; /* 该编码对应的字节 */ char *code; /* 变长 01 串需 malloc结尾 \0 */ } Huffmancode[N];2 * N - 1这个长度不是拍脑袋来的。n 个叶子的严格二叉树必有 n-1 个内部节点总共 2n-1 个下标 1 到 2n-1。前 n 个位置放叶子后 n-1 个位置放合并出来的内部节点这样内部节点的下标永远大于它两个孩子的下标select在1..i-1范围里找最小值时不会误选到还没生成的节点。用下标不用指针有三个实际好处。写入文件时可以直接序列化解压端重建树时下标关系天然保持调试时打印HT[i].parent得到的是一个 3 位以内的整数比打印一个地址直观太多。weight用double是为了跟题目给的概率口径一致6/19 这种如果改成unsigned long存原始计数比较时不会有浮点误差文件里每个符号也省 4 字节。两种都行关键是压缩端和解压端必须一致报告里也要前后一致。Huffmancode里的code是指针意味着每个符号的码字要单独malloc。这一步别忘了配对释放压完一个文件如果不释放连续压十个文件就漏十份内存虽然课设通常只压一个文件就退出但报告里「代码规范」那一栏是会给分的。3.2 压缩文件的二进制布局压缩文件不是一个黑匣子它的每一段都要能说清楚。这套方案的实际布局是这样偏移长度内容写入方式04 字节int n符号种类数fwrite(n, sizeof(int), 1, fp)4n × 9 字节n 组1 字节字符 8 字节权重循环fwrite两次4 9n2m 字节m 个short位流字整块或逐个fwrite文件末尾4 字节int dy最后一字补零的个数fwrite(dy, sizeof(int), 1, fp)解压端的读取顺序必须和写入严格对齐先fseek(fp, -4, SEEK_END)读末尾的dyrewind回去读n再读 n 组字符与权重剩下(文件长度 - 8 - 9n) / 2就是位流字的个数 m。这个推导要写进报告的详细设计里因为它解释了为什么解压端不需要知道原始文件多大。注意把double直接二进制写盘跨平台会遇到端序和sizeof(double)的差异。同一台机器上压、同一台机器上解没有问题这也是课程设计的默认假设但报告里最好补一句「码表以二进制形式存储要求压缩端与解压端平台一致」这句话能挡掉答辩时一半的追问。还有一种更省事的变体权重不存double存unsigned int计数每个符号从 9 字节降到 5 字节码表开销直接砍掉将近一半。对 19 字节的样例文件来说头部的 49 字节码表比数据本身还大压缩比会难看到没法看对小文件来说这是必然的报告里要主动说明「压缩比在小文件上不具参考性」别等老师来问。3.3 位缓冲区15 位装进 short还是 16 位装进 unsigned shortC 语言没有位类型的数组写文件最小单位是字节。所以必须自己攒一个缓冲区把变长的 01 串按位填进去填满一个字就写盘。原文报告里写的是「short int 有一位符号位故将 15 个 0/1 转化为一个数据存入 short int」代码里却是按pow(2.0, 15 - j)从 j0 算到 15实际上是 16 位。两处口径不一致答辩时很容易被揪住。我一般会统一成 16 位加unsigned short理由很简单无符号类型没有符号位干扰移位不会产生实现定义的行为容量还多一位。unsigned short bucket 0; /* 位桶攒满 16 位就写盘 */ int filled 0; /* 当前已填位数 0..15 */ /* 往桶里塞一个比特先左移腾位置再把新比特放到最低位 */ static void push_bit(unsigned short *bucket, int *filled, int bit, FILE *fp) { *bucket (unsigned short)((*bucket 1) | (bit 1)); if ((*filled) 16) { fwrite(bucket, sizeof(unsigned short), 1, fp); *bucket 0; *filled 0; } }bit 1是防御性写法保证传进来的即使是0 - 0之外的脏值也只影响最低位。filled用一个指针传进去是因为压缩主循环要跨很多次调用共享它。最后收尾时必须处理不满 16 位的情况把桶左移16 - filled位让有效比特对齐到高位低位补零然后把补零个数写进文件末尾那 4 字节。if (filled 0) { bucket (unsigned short)(bucket (16 - filled)); /* 有效位左对齐 */ fwrite(bucket, sizeof(unsigned short), 1, fp2); int pad 16 - filled; /* 补了几个零 */ fwrite(pad, sizeof(int), 1, fp2); } else { int pad 0; fwrite(pad, sizeof(int), 1, fp2); /* 末尾一定要写解压端靠它定位 */ }pad这个字段看着不起眼却是解压端最容易出错的地方。有效总位数 m × 16 - pad多解一位就会在还原文件末尾多出一个字符。所以这里有个原则不管有没有补零末尾这 4 字节必须写写 0 也要写让解压端的读取路径只有一条不要出现「某些文件有尾字段、某些没有」的分支。4. 四段核心算法落地建树、求码、压缩、解压的代码与参数说明4.1 建树与 select找最小两个节点的那点讲究建树的过程本身就是 Huffman 算法的四条步骤初始 n 棵单节点树、取最小两棵合并、删旧添新、重复到只剩一棵。void creattree(HuffmanTree HT, int n) { int m 2 * n - 1; /* 先把内部节点区间的字段清零避免上一轮残留的 parent 干扰 select */ for (int i n 1; i m; i) { HT[i].parent HT[i].lchild HT[i].rchild 0; HT[i].weight 0; } for (int i n 1; i m; i) { int min1, min2; select(HT, i - 1, min1, min2); /* 在 1..i-1 中找两个 parent0 且权值最小的 */ HT[min1].parent i; HT[min2].parent i; HT[i].lchild min1; HT[i].rchild min2; HT[i].weight HT[min1].weight HT[min2].weight; } }select的写法有个小技巧值得讲连续调用两次「找最小」第一次找到的节点必须被打上标记否则第二次还会找到它自己。原文的做法是在min()里把选中节点的parent临时置成 1这样第二轮扫描时它就不满足parent 0的条件了。/* 在 1..i 范围内找 parent0 且权值最小的节点找到后把它的 parent 置 1 当墓碑 */ int min(HuffmanTree HT, int i) { int j 1, best 0; double bestw 0; while (j i HT[j].parent ! 0) j; /* 跳过已有父节点的 */ if (j i) return 0; /* 没有可用节点 */ best j; bestw HT[j].weight; for (; j i; j) { if (HT[j].parent 0 HT[j].weight bestw) { best j; bestw HT[j].weight; } } HT[best].parent 1; /* 墓碑标记防止第二次 select 重复选中 */ return best; }这个技巧的好处是省一个visited数组坏处是把parent字段当成了两种语义用0 表示未合并1 表示临时占用大于 1 才是真正的父节点下标。所以creattree结束之后第 1 到 n 号叶子节点的parent一定大于等于 n1不会有残留的 1。但如果同一份HuffmanTree要在进程里复用比如连续压多个文件下一轮进来之前必须把 1 到 2n-1 的parent全部清回 0包括叶子区。这一点后面避坑章还会提。select只要写两行void select(HuffmanTree HT, int i, int *min1, int *min2) { *min1 min(HT, i); *min2 min(HT, i); }i这个参数的含义是「当前已存在的节点上界」。第一次合并时 i n之后每合并一次 i 加一所以在creattree里传的是i - 1。还有一个细节weight是double两个不同符号的频次完全相等是可能的比如样例文件里 13 和 10 的频次都是 3。浮点相等时谁先谁后会影响树的形状但不会影响编码的正确性——前缀无歧义这个性质不依赖于具体的合并顺序。如果报告里要求「同一输入必须得到同一输出」比如测试用例要做文件哈希比对那就得补一个平局规则让下标小的优先或者干脆把weight改成整数计数从根上避开浮点比较。4.2 自底向上回溯求码表树建好之后每个叶子的编码就是「从根走到它」的路径左 0 右 1。但从叶子往上走比从根往下走更方便因为每个节点只存了parent没存「我是父节点的左孩子还是右孩子」——不过这个信息可以现推HT[f].lchild c就说明是左边。void HuffmanCoding(HuffmanTree HT, Huffmancode HC, int n) { char *lcode (char *)malloc(n * sizeof(char)); /* 最长码长不超过 n-1 */ lcode[n - 1] \0; for (int i 1; i n; i) { int start n - 1; int c i, f HT[i].parent; while (f ! 0) { lcode[--start] (HT[f].lchild c) ? 0 : 1; /* 倒着填 */ c f; f HT[c].parent; } HC[i].ch HT[i].ch; HC[i].code (char *)malloc(n - start); /* 含结尾 \0 */ strcpy(HC[i].code, lcode[start]); } free(lcode); }从n - 1这个位置往前倒填是关键。如果正着填每次都要先知道码长或者填完再memmove挪一次代码更啰嗦。倒填之后start停在真实起点的位置lcode[start]直接就是一个完整的 C 字符串strcpy一步到位。malloc的长度n - start里已经含了\0的位置因为lcode的长度是 n从start到n-1有n - start个字节其中最后一个位置是被初始化的\0。这段代码有一个隐含假设n个叶子的树最长路径不超过 n-1。这是对的因为每次合并至少让路径上的节点数加一而合并总次数是 n-1。所以给lcode分配 n 字节足够不需要按2n分。free(lcode)之后HC[i].code仍然指向各自malloc的堆块这些块要么在压缩结束后统一释放要么跟着进程退出一起回收。课设场景下泄漏一次问题不大但既然写了malloc配对写一个free循环也就三行的事。4.3 压缩主循环查表、拼位、写盘有了码表第二遍扫描就变成「读一字节、查出码串、逐位塞进位桶」。rewind(fp1); int idx[256]; /* 从字节值直接映射到 HC 下标O(1) 查表 */ memset(idx, 0, sizeof(idx)); for (int i 1; i n; i) idx[HC[i].ch] i; int a; while ((a fgetc(fp1)) ! EOF) { /* 用返回值判断结束不要用 feof */ int i idx[(unsigned char)a]; if (i 0) continue; /* 理论上不会发生防御性跳过 */ for (const char *p HC[i].code; *p ! \0; p) { push_bit(bucket, filled, *p - 0, fp2); } }idx这个数组是性能上的小优化也是代码可读性上的分水岭。原文用的是一个for (i 1; i n; i) if (HC[i].ch a)的线性查找n 最大 256三百多字节的文件感受不到差别。但写成idx之后主循环里少一层嵌套答辩时讲起来也清楚这就是一个 256 项的直接寻址表本质上是把「符号集有限」这个前提用足了。fgetc的返回值必须用int接收这一点不能省。fgetc返回的取值域是 0 到 255 加上 EOF(-1)如果用char接读到字节 0xFF 时会被截成 -1跟 EOF 撞车循环就提前结束了。这个 bug 在纯文本文件上永远不出现一换成 jpg 或者压缩包就露馅属于典型的「测试用例选得太温柔」型翻车。参数说明push_bit的四个参数分别是位桶指针、已填位数指针、待写入比特、目标文件指针。之所以用指针传位桶是因为 C 语言没有引用而位桶的状态必须跨调用保留。4.4 解压从根节点往下走树解压端拿到的是「码表 位流 补零个数」要做的正好反过来按位读0 往左走1 往右走走到叶子就吐一个字节然后回根重新开始。int root 2 * n - 1; long total_bits (long)m * 16 - pad; /* 有效比特总数 */ int f root; for (long b 0; b total_bits; b) { int word bits[b 4]; /* 第几个 16 位字 */ int bit (word (15 - (b 15))) 1; /* 字内第几位从高位开始 */ f bit ? HT[f].rchild : HT[f].lchild; if (HT[f].lchild 0 HT[f].rchild 0) { /* 走到叶子 */ fputc(HT[f].ch, fp2); f root; /* 回根准备解下一个符号 */ } }这段和原文的写法有一处明显差别原文是先把所有short展开成一个int数组decode[k * 16]再在展开后的数组上循环。展开的好处是下标计算简单坏处是内存占用翻 32 倍int四字节、short两字节再乘以 16 倍展开系数一个 1 MB 的压缩文件要额外吃 32 MB 内存。按位即时取不需要额外数组代价是每次多两次移位一次与运算。循环的终止条件必须是「有效位数用完」不能写成「走到叶子就结束」。因为最后一个符号的码字可能正好在补零区之前结束如果按叶子判断补的那些零会在树上走出一些奇怪的路径运气好走到某个叶子多吐一个字符运气不好走到内部节点然后数组越界。原文用的是while (i k - dy)其中dy是补零个数思路一致只是变量命名不够直白。fputc每写一个字节就刷一次缓冲区对 1 MB 的文件来说系统调用次数太多。想快一点可以用一个 4 KB 的输出缓冲数组攒满再fwrite但课设规模下没必要保持代码短比跑得快重要。5. 避坑与排查最容易让程序在验收现场翻车的五个点先澄清一个不算 bug 的现象压缩比超过 100%。测试数据里 JPG 是 117.76%Mp4 是 99.99%docx 是 106.11%。原因不复杂——这些格式本身已经做过熵编码或者本身就是压缩容器字节分布接近均匀Huffman 给每个符号的平均码长接近 8 位压不动再叠上 9n 字节的码表开销和 8 字节的头尾字段净增就这么来了。文本文件能压到 33.02%是因为字符分布极不均匀空格、换行、常用字母的码长只有三四位。报告里把这张表原样放上去再补一句「压缩效果取决于符号分布的偏斜程度」比强行解释成「程序有问题」强。下面五条是真正会让程序在验收现场跑不出结果的。5.1 用 feof 判断文件结束最后一个字节被处理两次现象压缩出来的文件比预期多几个码字解压还原后末尾多出半个字符或者程序在最后一步突然崩溃。原因feof(fp)不是「文件到头了」的预测而是「上一次读操作撞到文件尾」的事后标记。写成while (!feof(fp1)) { a fgetc(fp1); ... }最后一次循环里fgetc返回 EOFfeof此时才置位但循环体已经拿着a -1执行了一轮把-1转成unsigned char就是 255凭空多统计了一个符号。解决直接用读函数的返回值做循环条件。fgetc返回int与EOF比较fread返回实际读到的元素个数与期望个数比较。feof只适合在读完之后判断「是正常结束还是出错」不适合当循环条件。5.2 fgetc 的返回值塞进 char遇到 0xFF 就提前收工现象txt 文件压得好好的一换成 jpg、png 或者 exe压缩过程在中途无声无息地结束还原出来的文件只有原文件的一小段。原因char在多数编译器上是有符号的把fgetc返回的 255 存进char就变成 -1和EOF相等循环条件直接判负退出。图片和可执行文件里 0xFF 出现的概率很高文本文件里几乎为零所以这个 bug 有极强的欺骗性。解决接收变量声明成int比较完EOF之后立刻转成unsigned char再用。同理fwrite写单个字节时用fputc((unsigned char)c, fp)或者fwrite(c, 1, 1, fp)别让符号位掺和进来。5.3 用 w 或 r 打开文件换行符被悄悄改写现象压缩再解压之后文件字节数变了用十六进制对比发现每一处0D 0A变成了0A或者反过来多出了0D。原因文本模式在部分平台上会做换行翻译。写的时候\n变成\r\n读的时候反过来。对于只处理文本的程序这是便利对于按字节压缩的程序这是灾难压缩时统计到的 10 和 13 的频次跟解压时实际要写的字节对不上还原文件自然不一致。解决所有fopen一律带brb、wb。题目给的那个 19 字节样例里正好同时有 13 和 10拿它当第一个测试用例这个坑一测就现形。5.4 select 里的 parent 标记没清干净第二次建树直接歪掉现象单次压缩解压完全正常改成循环处理多个文件后第二个文件的压缩比明显异常或者解压直接得到乱码。原因min()里把选中节点的parent置 1 当墓碑用这个 1 是临时状态。如果HuffmanTree是全局变量或者循环外声明的第二次进creattree时上一轮留下的parent值还在select会认为这些节点已经有父节点了跳过它们结果要么选错节点要么在while里死循环找不到可用的。解决每次建树前把1..2n-1的parent、lchild、rchild全部清零不要只清内部节点区间。更稳妥的做法是把HuffmanTree定义在压缩函数内部当局部变量靠作用域强制隔离代价是栈上多占几 KB——513 个节点每个 24 字节左右也就 12 KB撑得住。5.5 空文件和单符号文件没有特判直接除零或者死循环现象压一个空文件程序在小数点后第几位崩掉压一个内容全是同一个字符的文件解压出来是空的或者程序卡住不动。原因空文件第一遍扫描结束n 02*n-1是负数建树那层循环一次不进后面算概率时除以总长度 0浮点异常。单符号文件n 1树只有一个节点它既是根又是叶子HuffmanCoding里while (f ! 0)一次不进码串是空串压缩时一个比特都写不进去解压时root指向的那个节点既没有左孩子也没有右孩子按位走第一步就落到空指针上。解决入口处两个特判。n 0时压缩文件只写头部长度为 0就返回解压端读到n 0直接创建一个空目标文件。n 1时给这唯一的符号定义一个位固定为0或者干脆在位流里存字符重复次数解压端读到n 1就走专用分支不建树、不走树直接按位数值写字符。提示这两个用例在验收表上一定要列出来而且要放在前面。老师看到你主动考虑退化情况对「测试」那一栏的评分帮助比多压十个 txt 文件大得多。6. 验收与答辩用一张测试表和一份 T(n) 分析把分数拿稳验收现场的时间通常只有五到十分钟能不能过很大程度上取决于你打开电脑之前有没有把测试用例排好序。我一般会准备这样一张表按复杂度递增排第一条就是能背下来的序号输入期望结果判据119 字节的 aaBBaaaaccBBB还原后与原文件逐字节相同符号种类数 5符号为 97、66、99、13、102空文件0 字节生成合法压缩文件解压得到 0 字节文件程序不崩溃退出码为 03单字符重复 1 MB 的文件还原一致压缩比接近 0验证 n1 分支4一个 txt、一个 docx、一个 jpg全部还原一致压缩比分别为小于 100%、可能大于 100%5不存在的源文件名打印提示并退出退出码非 0不产生目标文件第一条是老师给的例子符号种类数 5 这个数字能直接手算你先跑它等于告诉对方「我知道正确结果长什么样」。第四条里 jpg 压完变大这件事要主动说别等被问。第五条是命令行参数处理的分很多人只写正常路径一传错文件名就段错误。T(n) 分析别写成一串大 O 符号了事。按「扫描 O(n) → 建树 O(k²) → 求码 O(k·L) → 编码 O(n·L̄) → 解压 O(m·16)」分段列每一段说明 n、k、L 各是什么k 是符号种类数、上界 256L 是最长码长、上界 k-1。最后给一句结论由于 k 是常数整体随文件长度线性增长。这句话比空写一个 O(n) 有内容得多。答辩最常被问的三个问题答案都在前面的章节里为什么压缩文件要存码表因为解压端不能依赖源文件为什么用下标不用指针因为要序列化且跨进程地址无意义压缩比为什么有的大于 100%因为源文件已被压缩过符号分布均匀叠加码表开销。把这三条各准备两句话剩下就是现场演示别手抖。我第一版做这个课设的时候测试只用了自己随手写的一个 txt验收时老师从桌面拖了一张照片进来程序跑了三秒就停还原出来的文件只有前半截。那天回去之后我把 0xFF 那个坑记了很多年从那以后我每次写文件处理相关的代码第一件事就是拿一个全 0xFF 的二进制文件跑一遍不管需求里有没有提。希望帮到你。本文还有配套的精品资源点击获取