《数据结构C语言版 第2版》第五章课后习题我前前后后刷了三遍。第一遍是本科期末考前突击第二遍是准备考研数据结构第三遍是工作后带实习生重新梳理。每次刷都会发现新问题——有些题看起来简单但对答案的时候才发现自己的推导过程是错的。严蔚敏老师这本教材的第五章“数组和广义表”在期末考试和考研里都属于“性价比极高”的一章题不难套路固定但细节极多稍不注意就丢分。这篇文章我不打算把课后习题答案机械抄一遍因为直接抄答案对你没有任何帮助。真正的做法是把第五章课后题里反复出现的几类题目全部拆开讲清楚每个答案是怎么推出来的推导过程中有哪些隐含前提以及大家最容易踩的坑在哪。不管你是期末突击、考研复习还是自学教材卡在这一章按这个思路去刷题效率会高很多。1. 第五章到底在考什么先把“数组和广义表”的主线捋清楚1.1 这章在全书中的位置与考点分布严蔚敏版《数据结构C语言版 第2版》的逻辑顺序是先讲线性表、栈、队列这些“线性结构”再到串、数组、广义表然后才进入树和图。第五章非常特殊它本质上是一个“转折章”前面的线性结构强调数据元素之间的“一对一”关系从这一章开始你会发现数据组织方式开始变得多样——数组是“多维”的广义表是“嵌套”的稀疏矩阵又涉及“压缩存储”。这些概念看上去割裂实际上都在回答同一个问题怎么在内存里高效地组织和访问数据。从考点分布来看第五章的课后题主要集中在这几个方向二维数组的元素地址计算行优先、列优先两种存储方式的区分特殊矩阵的压缩存储最典型的是对称矩阵、三角矩阵、对角矩阵稀疏矩阵的三元组表示和转置算法简单转置与快速转置广义表的表头、表尾、长度、深度计算这四类题基本就是期末和考研的“题库大头”。你会发现这一章几乎没有特别复杂的算法设计题更多是“计算 推导 理解”。所以刷题的核心不是背公式而是理解公式是怎么来的理解了之后不管题目怎么变你都能应对。1.2 数组、矩阵压缩存储、广义表之间的逻辑关系很多同学刷这章课后题时会觉得“这章怎么这么碎”——一会儿算地址一会儿写广义表一会儿搞三元组好像没有主线。我的理解是这一章的隐藏主线就是“如何用一维空间表达多维结构”。数组本身是随机存取结构你把一个二维数组存成一维数组本质上是在做“多维下标到一维下标的映射”。这和你用行优先还是列优先存储有关也是地址计算题的理论基础。矩阵压缩存储属于数组应用的进阶如果一个矩阵有很多重复元素或者零元素你没必要全存只需要存“有效信息”但压缩之后原来的二维下标就没办法直接用数组下标访问了于是又得建立一个“映射关系”。广义表就更进一步它允许元素本身还是一个表结构上变成了“嵌套的线性结构”。所以你看这三块内容并不是孤立的它们都在讲同一件事当数据结构的逻辑结构不能直接用物理存储表达时怎么设计映射规则。抓住这条主线再去看课后题你会发现题目之间的相似性非常高。2. 课后习题逐类拆解答案和推导过程一次讲透2.1 数组元素地址计算套公式前先做一件事数组地址计算是第五章最容易拿分也最容易失分的题。题目通常长这样已知一个二维数组A[m][n]每个元素占L个字节起始地址是LOC按行优先存储求A[i][j]的地址。先给结论。按行优先存储时A[i][j]前面一共有i个完整行每行有n个元素再加上当前行前面有j个元素所以偏移量为(i * n j) * L地址就是LOC(A[i][j]) LOC(A[0][0]) (i * n j) * L按列优先存储时A[i][j]前面一共有j个完整列每列有m个元素再加上当前列前面有i个元素所以偏移量为(j * m i) * L地址就是LOC(A[i][j]) LOC(A[0][0]) (j * m i) * L这两个公式看起来不难但我见过太多同学把行列搞反。关键在理解行优先时每一行有多少个元素是n列数所以i要乘以n列优先时每一列有多少个元素是m行数所以j要乘以m。花一分钟把这个道理想明白比背十遍公式都管用。举一个完整例子。设二维数组A[5][8]按行优先存储每个元素占3个字节已知A[0][0]的地址为1000求A[3][4]的地址。代入行优先公式LOC(A[3][4]) 1000 (3 * 8 4) * 3 1000 28 * 3 1084如果同样的数组改成按列优先存储LOC(A[3][4]) 1000 (4 * 5 3) * 3 1000 23 * 3 1069同一个元素两种存储方式算出来的地址不一样差在哪里差在三维数组的“行”中有多少个元素。如果一个题目让你分别按行优先和列优先计算你就能很清楚看到存储方式对地址的影响。这里还有一个容易忽略的细节题目说的数组下标是从0开始还是从1开始。很多教材在讲地址计算时默认下标从0开始因为C语言数组就是这样但也有习题会写成A[1..m][1..n]这种下标从1开始的情况公式要改成LOC(A[i][j]) LOC(A[1][1]) ((i - 1) * n (j - 1)) * L为什么是(i - 1)和(j - 1)因为A[1][1]是起始元素它前面没有任何元素实际偏移要从第2行第2列开始算。做题前先花三秒钟确认下标起点能帮你避开一堆低级错误。2.2 对称矩阵和三角矩阵的压缩存储看清下三角还是上三角特殊矩阵压缩存储的课后题里出现频率最高的是对称矩阵。对称矩阵的特点是A[i][j] A[j][i]所以只需要存储下三角包括对角线或者上三角的一部分就能还原整个矩阵。教材里最经典的做法是把n阶对称矩阵的下三角部分按行优先存储到一维数组B中。这里要分清楚题目用的是“下标从1开始”还是“下标从0开始”因为公式不一样。如果矩阵下标从1开始即A[1..n][1..n]下三角元素A[i][j]i j在一维数组B[1..n(n1)/2]中的位置k为k i * (i - 1) / 2 j这个公式怎么来的因为第1行有1个元素第2行有2个元素……第i-1行有i-1个元素前i-1行一共1 2 ... (i - 1) i*(i-1)/2个元素。第i行的下三角元素按列号从小到大排A[i][j]是第i行第j列它的前面还有j个元素不对这里要注意A[i][1]是第i行第一个下三角元素A[i][j]是第i行第j个下三角元素所以它前面有j - 1个元素等等让我们仔细推导。下三角按行存储时第i行只存A[i][1]到A[i][i]这i个元素。A[i][j]在第i行内部排第j个位置所以它前面在同一行内有j - 1个元素。于是总偏移从1开始计数的位置应该是k 前i-1行元素总数 第i行内部偏移 1前i-1行元素总数为i*(i-1)/2第i行内部偏移为j - 1加1是因为位置计数从1开始k i * (i - 1) / 2 (j - 1) 1 i * (i - 1) / 2 j验证一下3阶对称矩阵A[2][1]i2, j1代入公式得k 2*1/2 1 2。一维数组B[1]存A[1][1]B[2]存A[2][1]正确。但如果题目用C语言习惯矩阵下标从0开始即A[0..n-1][0..n-1]存储到B[0..n(n1)/2-1]那么当i j时位置k为k i * (i 1) / 2 j怎么理解下标从0开始前i行一共有1 2 ... i i*(i1)/2个元素第0行1个第1行2个……第i-1行i个第i行内部A[i][j]前面有j个元素所以k i*(i1)/2 j。注意如果题目要求求A[i][j]时给了i j因为对称矩阵A[i][j] A[j][i]你要先交换i和j再用下三角公式。三角矩阵比对称矩阵多了一个“常数元素”的处理。下三角矩阵中上三角部分的元素全部是同一个常数c压缩存储时只需要在整个一维数组末尾多存一个c即可。所以元素个数从n(n1)/2变成n(n1)/2 1。如果是下标从0开始i j时k i * (i 1) / 2 j当i j时也就是上三角部分所有元素都存到最后一个位置k n * (n 1) / 2这个“上三角元素都指向同一个常数位置”的点特别容易被忽略。很多人算三角矩阵时只记得下三角公式忘了还有那个常数项。课后题里只要出现三角矩阵基本都会考这个。2.3 稀疏矩阵的三元组表与快速转置逻辑比代码重要稀疏矩阵是第五章课后题里算法含量最高的一块。所谓稀疏矩阵就是非零元很少的矩阵。如果非零元个数远小于矩阵元素总数用二维数组存储就太浪费了所以用三元组表来存储。一个三元组是(row, col, value)表示第row行第col列有一个值为value的非零元矩阵的行数、列数、非零元个数单独记录。课后题里最常见的是转置算法。普通转置的思路很简单把每个三元组的row和col互换然后重新排序。但这个做法效率低因为你需要反复扫描查找。快速转置算法是课后题的重点也是很多同学觉得难的地方。快速转置的核心不是“转置”本身而是“提前算好每一列第一个非零元在转置后三元组表中的位置”。整个过程分三步第一步统计原矩阵每一列有多少个非零元存到数组num[col]中。第二步计算每一列第一个非零元在转置结果表中的起始位置position[col]。因为转置后原矩阵第col列的元素会变成新矩阵第col行的元素它们在新三元组表中是连续存放的所以可以用累加的方式算起始位置position[1] 1 position[col] position[col - 1] num[col - 1]这里position[col]表示原矩阵第col列的第一个非零元在转置后的三元组表b.data中应该存放的起始位置。第三步扫描原三元组表a.data对每个三元组(r, c, v)它转置后应该放到b.data的哪个位置答案是position[c]。放完之后注意position[c]要自增1因为同一列的下一个非零元应该放到紧挨着的位置。用一个实际例子走一遍。假设有一个3行4列的稀疏矩阵0 0 1 0 2 0 0 0 0 3 0 0非零元按行序排列为(1, 3, 1)(2, 1, 2)(3, 2, 3)这里行、列下标都从1开始。先统计每列非零元个数num[1] 1num[2] 1num[3] 1num[4] 0然后算起始位置position[1] 1position[2] position[1] num[1] 2position[3] position[2] num[2] 3position[4] position[3] num[3] 4接着遍历原三元组表。第一个三元组(1, 3, 1)它的列号是3所以放到b.data[position[3]]也就是b.data[3]然后position[3]变成4。第二个三元组(2, 1, 2)列号是1放到b.data[position[1]]也就是b.data[1]然后position[1]变成2。第三个三元组(3, 2, 3)列号是2放到b.data[position[2]]也就是b.data[2]然后position[2]变成3。最后转置结果是(2, 1, 2), (3, 2, 3), (1, 3, 1)。验证一下原矩阵的列1有一个非零元在(2,1,2)转置后变成新矩阵行1的(2,1,2)原矩阵的列2有一个非零元在(3,2,3)转置后变成新矩阵行2的(3,2,3)原矩阵的列3有一个非零元在(1,3,1)转置后变成新矩阵行3的(1,3,1)。顺序正确这正好是按行序排列的结果。如果用C语言写快速转置的核心代码大概是这样的for (col 1; col n; col) { num[col] 0; // n是原矩阵的列数 } for (i 1; i t; i) { num[a.data[i].col]; } position[1] 1; for (col 2; col n; col) { position[col] position[col - 1] num[col - 1]; } for (i 1; i t; i) { col a.data[i].col; q position[col]; b.data[q].row a.data[i].col; b.data[q].col a.data[i].row; b.data[q].value a.data[i].value; }这道题在考研数据结构里经常以“填空手写代码片段”的形式出现。你可以发现快速转置算法本质上是用空间换时间额外开了两个数组num和position避免了普通转置中反复查找排序的O(n*t)复杂度。理解了这个优化动机代码也就不难记了。2.4 广义表的表头表尾、长度与深度每一步都写清楚过程广义表课后题的核心操作是求表头、表尾、长度和深度。很多人看到广义表就头晕是因为它“嵌套”的结构让括号特别多。实际上掌握规则后这类题就是最简单的送分题。先记住几个基本定义广义表是n个元素的有限序列元素可以是原子也可以是子表。表头GetHead(L)广义表的第一个元素可以是原子也可以是子表。表尾GetTail(L)广义表去掉第一个元素后剩余元素组成的表。注意表尾一定是一个表所以如果结果是“一堆元素”一定要在最外面加一层括号。广义表的长度最外层包含的元素个数。广义表的深度括号嵌套的最大层数。原子的深度是0空表的深度是1一个广义表的深度等于所有元素深度的最大值加1。拿一个例子完整走一遍。设广义表A (a, (b, c), ((d), e))先看长度。最外层有3个元素原子a、子表(b, c)、子表((d), e)所以长度为3。再看表头和表尾GetHead(A) a GetTail(A) ((b, c), ((d), e))注意表尾不是(b, c)和((d), e)分开而是它们俩组成的一个新表必须加一对括号所以GetTail(A)是((b, c), ((d), e))。这里非常容易写错我经常看到有人写成(b, c), ((d), e)少了一层括号就错了。再看深度。递归计算每个元素的深度原子a的深度为0子表(b, c)的深度b和c都是原子深度0子表本身深度为0 1 1子表((d), e)的深度(d)的深度为0 1 1e的深度为0所以这个子表深度为1 1 2整个广义表A的深度等于元素深度的最大值2再加1结果为3。课后题里还有一种变体会问你GetHead(GetTail(A))之类的复合操作。这种题不用慌从内往外一层一层拆。比如上面这个例子GetTail(A) ((b, c), ((d), e)) GetHead(GetTail(A)) (b, c)因为表尾的结果是一个表这个表的第一个元素是(b, c)取表头就是(b, c)。注意这里结果本身是子表所以保留括号。如果题目继续让你取GetHead(GetHead(GetTail(A)))那就是b因为它是一个原子。广义表这块的核心经验只有一句话写每一步操作时都先想清楚当前对象是一个表还是一个原子。表头可以是原子也可以是表但表尾必须是表。所有错误几乎都出在这两个“必须”上。3. 解答过程里最容易翻车的几个细节全是实战踩过的坑3.1 下标从0还是从1开始决定整个公式这一章几乎所有计算题都受“下标起点”影响。C语言教材里数组下标天然从0开始所以严蔚敏教材很多地方也默认0下标。但课后习题里为了体现通用性有时候会写成“矩阵的行列下标均从1开始”有时候又不写默认为0。我的建议是拿到题先做标记。如果题目没有明说看它给的矩阵元素是怎么标识的。比如题目写A[2][3]通常默认下标从0开始如果写A[2..5][1..4]那明显下标不全是0。你可以在草稿纸上先把公式写出来然后标清楚“本题i从几开始j从几开始”再代入数值。这个习惯能帮你避免一半以上的低级失分。3.2 快速转置的position数组别把“起始位置”和“当前可用位置”搞混快速转置的代码里有一个经典细节遍历三元组表时每处理完一个元素position[col]要自增1。很多同学不理解为什么或者理解但写代码时忘了。其实position[col]在初始时存储的是“这一列第一个非零元应该放的位置”放完第一个之后这个位置就失效了下一个同列元素应该放到紧挨着的位置所以position[col]就是在更新“下一个元素可用的位置”。把position数组理解成“当前可用的下一个位置”代码就好写多了。另外要特别提醒统计num数组时如果你用的是从1开始的下标那么num和position数组都从1开始用第0位空着。如果你从0开始整个计算都要跟着偏移。这其实又是“下标起点”的问题但这里坑人于无形因为代码看起来逻辑完全正确错就错在数组下标。3.3 广义表深度的“括号数”别数错有些参考书的速记口诀是“深度等于括号层数”这个说法不严谨但实战中确实好用。不过要注意原子的深度是0一个原子外面套一层括号深度才是1套两层是2。所以“数括号”的时候要数的是这个元素自身被多少层括号包裹而不是整个广义表最外层括号的数量。我习惯的做法是先画一条竖线把每一层括号在竖线上的位置标出来然后看最深的嵌套层数。比如((a, b), (c, (d, e)))最内层(d, e)外面套了两层括号所以整体深度是3我们来验证元素(d, e)深度1(c, (d,e))深度2整个表((a,b), (c, (d,e)))最外层再加1深度3。用“数括号”法就是看(d, e)外面有几层括号这里有两层分别来自(c, (...))和整个表加本身一层共3。这个“本身一层”千万别漏。3.4 行优先、列优先与“m行n列”的对应关系还有一个高频易错点题目说“A是m行n列数组”按行优先存储。有人会下意识认为“一行有m个元素”这是错的。一行有n个元素因为n是列数。列优先时一列有m个元素。说白了行优先看列数列优先看行数。你可以在草稿纸上画一个小的2行3列矩阵行优先和列优先各标一次编号马上就能明白。4. 复习节奏参考课后题怎么刷性价比最高4.1 第一轮按题型分组重推导轻死记我不建议拿着课后题从第1题做到最后一道题。第五章的题目类型很固定更好的做法是按题型分组比如“地址计算题”放一天集中做“对称矩阵压缩”放一天“稀疏矩阵转置”放一天“广义表操作”放一天。同一类题连做几道之后你会自然总结出套路而不是做一道忘一道。第一轮做题时哪怕做错了也不要急着翻答案。地址算错了先看看是不是下标起点看错了广义表表尾写错了先检查少没少括号。自己找到错误原因比直接看正确答案印象深得多。我当年复习考研数据结构时这一章第一轮花了两天每天两小时但之后基本不需要再回头死磕。4.2 第二轮盖住答案写完整过程很多同学刷题时“眼高手低”看一眼题觉得自己会了就跳过。结果考试时一写就错。第二轮复习时我建议拿一张白纸把每道题的完整推导过程写出来包括公式、代入、结果甚至算法题的数组变化过程。写完再对答案。这一步特别适合地址计算和快速转置这类题。地址计算你把公式写完整能明确看到自己用的是行优先还是列优先快速转置你把num、position数组的值一个个列出来基本不会错。把过程写出来暴露的问题远比你想的多。4.3 第三轮把算法题改成C语言程序跑一遍IDE如果只是应付期末考试前两轮就够了。但如果准备考研或者想真正理解数据结构我强烈建议把稀疏矩阵快速转置、对称矩阵压缩存储这些算法的课后题用C语言在IDE里实现一遍然后自己构造几组测试数据验证结果。比如对称矩阵压缩你可以写一个小程序随机生成一个5阶对称矩阵压缩到一维数组再根据下标映射读回检查读回的元素是否等于原矩阵的元素。这个过程能帮你彻底理解i*(i1)/2j这个公式为什么成立而不是只会套用。快速转置也是一样自己写一个打印函数把num和position数组每个阶段的值打出来代码里哪里理解错了结果立刻现形。这里顺带提醒一句实现这些算法时C语言的数组下标从0开始和教材里很多公式的下标从1开始并不一致。写代码时你要么把公式改成0下标版本要么在代码里用偏移量处理。这是很好的练习因为它逼着你真正理解公式而不是死记硬背。5. 常见问题与避坑清单一张表帮你考前自检最后把这章最常出现的错误整理成一张速查表考前看一遍能救回不少分。常见问题出错原因应对策略地址计算差一个字节或多个字节下标从0还是1没搞清楚做题前先标出下标起点再写公式行优先和列优先搞混没理解“每行有n个元素”还是“每列有m个元素”画一个2行3列的小矩阵手动标号对称矩阵公式记错下标0和1对应不同公式把两个公式都写出来对比记忆三角矩阵忘了常数元素只记下三角忽略上三角统一存常数的位置做题时问自己这个矩阵有没有重复或固定元素快速转置忘记position[col]没理解position是“下一个可用位置”写代码时注释放一个元素后更新可用位置广义表表尾少一层括号忽略了“表尾一定是表”写完检查GetTail结果最外层有没有括号广义表深度算错数括号时忘了内层子表可能嵌套从最内层元素出发数它被几层括号包裹再加1对称矩阵A[i][j]中ij没交换忘了对称矩阵A[i][j]A[j][i]见了ij先交换再代入下三角公式这里每一个坑我都在不同场合见过真实案例。最离谱的一次是有人考试时把对称矩阵的公式背成i*(i-1)/2j但题目下标是0开始结果整道题全错。公式本身没错但用错了场景这是最可惜的失分方式。第五章整体难度不高但它是一个“细节放大器”你觉得自己会了考完对答案才发现丢了一堆不该丢的分。把这篇文章里提到的推导过程自己动手写一遍再做一遍课后题你会发现这套知识真的没那么难。我个人刷完三遍的感受是这章不值得花大量时间死磕难题但非常值得花时间把每一个“为什么”彻底搞明白。搞清楚这些细节之后你不仅期末不怕考研遇到类似题目也能拿得稳。