最近在帮备考GESP四级的学生整理练习题刷题列表里反复出现三道题单词长度统计、删除子串、冒泡K趟。这三道题乍看没什么关联一道是字符串处理、一道是字符串查找、一道是排序但实际练下来会发现它们正好从三个维度考验C语言的基本功——字符串遍历与切分、子串匹配与拼接、排序过程中的循环控制与状态记录。不管你是刚学C语言、准备等级考试还是在网上刷OJ题库这三道题都值得拿出来单独拆一拆。这篇文章就把这三道题串起来讲清楚每道题的核心思路、可参考的实现代码、以及我在实际调试中踩过的坑。文章用的是C语言但思路同样适用于Java和C最后还会顺带聊聊冒泡排序和选择排序到底该选哪个以及GESP四级里“统计交换次数”这类变形题怎么应对。1. 先拆题这三道题到底在考什么1.1 单词长度统计字符串处理的“边界感”单词长度统计这个题题目描述通常是这样输入一行英文句子输出每个单词的长度单词之间用空格分隔。听起来简单但它考的根本不是“你会不会数数”而是你对字符串边界的处理能力。一个句子里有多个空格、开头结尾有空格、最后一个单词后面跟不跟空格这些情况变化一下代码就可能从“能跑”变成“踩内存”。这类题在“GESP四级”的字符串大题里经常作为低难度部分出现但它的变形很多比如让你统计最长单词、最短单词、或者按长度从小到大输出单词本质都是在考同一个状态机逻辑。1.2 删除子串字符串查找与拼接的“组合拳”删除子串的经典问法是输入两个字符串s和t把s中所有出现的t删除输出删除后的结果。字符串长度可能到几千甚至十万级别。这题表面上是“删除”实际考的是子串查找。你得先找到t在s里的位置才能谈删除。最直接的做法是暴力匹配也就是逐个位置去比对效率更高一点的做法是KMP先对t做一次预处理生成next数组然后再去s里扫描。在GESP四级的考试范围里KMP本身不是必须掌握的内容但理解“查找”这一步才是本质。很多学生一上来就想着怎么把字符“抠掉”却不知道C语言里字符串是靠“移动字符”来删除的也就是把后面剩下的字符往前面搬。想清楚这一层代码怎么写都不会歪。1.3 冒泡K趟从“任务题”到“算法优化题”冒泡排序是所有排序算法里最基础的一个几乎每个学C语言的人都写过。但“冒泡K趟”这个问法直接把难度从“实现”拉到了“理解”。所谓冒泡K趟就是只执行K轮冒泡然后输出这K轮之后数组的状态。比如题目说“对数组执行3趟冒泡排序输出结果”你得注意不是让你把数组整个排完而是只做3轮外层循环。这个区别很重要因为冒泡排序的内层循环边界每趟都在变第1趟比较到n-1第2趟比较到n-2执行K趟时最后一趟的比较边界要落在n-K上。这道题在OJ上很常见也是“GESP四级202605冒泡排序交换次数”这类真题的母题。真题会让你在冒泡过程中统计交换次数或者判断某趟之后数组是否已经有序——这些都是在基础冒泡上加了状态记录。1.4 三道题之间的联系都是“循环条件判断”的变奏把三道题放在一起看其实它们有个共同的底层逻辑在遍历过程中维护一个“状态”。统计单词时你要维护“当前是否在一个单词里”删除子串时你要维护“当前位置是否匹配上了目标串”冒泡K趟时你要维护“已经冒了几趟、是否发生过交换”。这个思想看起来简单但绝大多数BUG都出在状态维护上。你忘了重置标记单词长度就多算你没在匹配成功后跳过目标串的长度子串就会被重复删除你没在内层循环前把交换标志清零数组明明已经有序了还会白跑好几趟。所以这篇文章里我每个题都会重点讲“状态怎么记录”而不是只贴一段能过的代码。2. 单词长度统计从逐字符扫描到sscanf偷懒2.1 基础写法逐字符扫描单词边界判定先上最稳的写法。思路是从头到尾遍历字符串用一个变量记录“当前是否处于单词内”如果遇到非空格字符且当前不在单词内说明一个新单词开始了如果遇到空格且当前在单词内说明单词结束了。#include stdio.h #include string.h int main() { char s[1005]; fgets(s, sizeof(s), stdin); int len strlen(s); int inWord 0; // 是否在单词内 int curLen 0; // 当前单词长度 // 去掉fgets可能读入的换行符 if (len 0 s[len - 1] \n) { s[len - 1] \0; len--; } for (int i 0; s[i] ! \0; i) { if (s[i] ! ) { if (!inWord) { inWord 1; curLen 0; } curLen; } else { if (inWord) { printf(%d , curLen); inWord 0; } } } // 处理最后一个单词 if (inWord) { printf(%d\n, curLen); } return 0; }这段代码的关键在最后那个if (inWord)。因为句子末尾不一定有空格如果你不在循环结束后补一次输出最后一个单词的会被漏掉。很多初学者就是栽在这里中间的所有单词都输出了偏偏最后一个单词没有输出。2.2 用sscanf提取单词什么时候可以偷懒如果题目里明确说了“单词之间用单个空格分隔没有多余空格”那你可以用sscanf来偷懒。它的机制类似于正则匹配分词每次调用会跳过空白、读取下一个单词。#include stdio.h int main() { char s[1005]; fgets(s, sizeof(s), stdin); char word[1005]; char *p s; int first 1; while (sscanf(p, %s, word) 1) { if (!first) printf( ); printf(%d, (int)strlen(word)); first 0; // 指针移动到当前单词之后 while (*p ! *p ! \0) p; while (*p ) p; } printf(\n); return 0; }注意这里有个细节sscanf每次从p开始解析解析完一个单词后你得手动把指针挪到单词后面的空格之后否则下一次循环又会从同一个单词开始读。指针操作不熟的话这个写法很容易死循环所以我建议初学者用2.1的状态机写法遇到多空格的情况也不慌。2.3 多空格和行首行尾空格的处理真实题目往往不会老老实实给“单空格分隔”OJ上的测试数据经常带着行首空格、行尾空格、连续多个空格。这时候用sscanf反而更稳因为它天然忽略所有空白字符。但如果你坚持用逐字符状态机写也完全没问题——状态机的优点就是不依赖输入格式。不管有多少空格、空格在哪个位置逻辑都一样非空格字符进入单词空格字符结束单词。这也是为什么我更推荐状态机写法它一次写对后面怎么变题都不怕。还有个小细节用fgets读一整行时字符串末尾会带上\n。如果你不处理它\n在isspace函数看来也算空白但如果你用if (s[i] ! )判断空格\n会被当成单词的一部分导致最后一个单词长度多1。这是个非常典型的错误我在帮人debug的时候几乎每周都能见到一次。3. 删除子串先会暴力匹配再谈KMP优化3.1 暴力删除思路直接适合长度1000以内对于字符串长度在1000以内的题目暴力删除完全够用。做法是循环查找t在s中的位置找到就把它后面的字符全部往前移动strlen(t)个位置然后继续从当前位置查找直到找不到为止。#include stdio.h #include string.h void removeSubstr(char s[], const char t[]) { int lens strlen(s); int lent strlen(t); if (lent 0) return; int i 0; while (s[i] ! \0) { // 检查从i开始的子串是否等于t if (strncmp(s[i], t, lent) 0) { // 把后面的字符往前移覆盖掉t for (int j i; j lens - lent; j) { s[j] s[j lent]; } lens - lent; // 注意i不前进因为可能有重叠删除 // 比如saaa, taa删除后还剩a } else { i; } } } int main() { char s[2005], t[1005]; fgets(s, sizeof(s), stdin); fgets(t, sizeof(t), stdin); // 去掉换行符 s[strcspn(s, \n)] \0; t[strcspn(t, \n)] \0; removeSubstr(s, t); printf(%s\n, s); return 0; }这段代码里有个很重要的注释点匹配成功后i不要自增。举个例子s是“aaa”t是“aa”在i0处删除后s变成“a”此时如果i自增到1就直接结束了结果还是“a”没问题但再看另一种重叠情况s是“aaaa”t是“aa”i0删除后变成“aa”这时i如果自增到1就错过了i0处新形成的“aa”导致结果变成“aa”而不是空串。所以删除后保持i不动才能处理连续重叠的情形。这个细节是本题最大的坑。3.2 用KMP优化字符串长度到十万时的选择当s的长度到100000量级暴力删除就会超时最坏情况下每匹配一次要扫一遍子串时间复杂度能到O(n*m)。这时候就该用KMP来做子串查找。KMP的核心思想是当某个位置的字符匹配失败时不把模式串的指针退回开头而是根据next数组跳到前面某个位置继续匹配。这样s的扫描指针永远不会回退整体时间复杂度降到O(nm)。#include stdio.h #include string.h #include stdlib.h void getNext(const char t[], int next[]) { int lent strlen(t); next[0] 0; int j 0; for (int i 1; i lent; i) { while (j 0 t[i] ! t[j]) { j next[j - 1]; } if (t[i] t[j]) { j; } next[i] j; } } void removeSubstrKMP(char s[], const char t[]) { int lens strlen(s); int lent strlen(t); if (lent 0) return; int *next (int*)malloc(lent * sizeof(int)); getNext(t, next); char *res (char*)malloc((lens 1) * sizeof(char)); int cnt 0; // res当前长度 int j 0; // 当前匹配长度 for (int i 0; i lens; i) { while (j 0 s[i] ! t[j]) { j next[j - 1]; } if (s[i] t[j]) { j; } res[cnt] s[i]; if (j lent) { // 匹配到完整子串回溯cnt相当于删除了t cnt - lent; j 0; // 注意这里不能直接从0重新匹配 // 严谨做法是用next数组回退或者用辅助栈记录 } } res[cnt] \0; strcpy(s, res); free(next); free(res); }如果你是初学阶段有个更简单的方法把字符逐个压栈一旦发现栈顶的lent个字符和t相同就弹出lent个。这个思路和KMP殊途同归而且更好理解也不容易把j的回退逻辑写错。不过GESP四级一般考不到这个量级暴力写法正确处理重叠情况就够了。3.3 删除子串的常见坑坑一用strstr循环删除时陷入死循环。有些人觉得既然要查找那就直接用strstr好了。但strstr返回的是char*你没法把“原数组的偏移量”直接拿回来用strcpy往左搬。写了半天发现指针操作乱掉不如一开始就用strncmp检查当前位置。坑二忘了处理换行。fgets读进来的字符串带\n如果t的长度是2s末尾却有个\n原本最后能匹配的子串会因为中间隔了个换行而匹配不上。凡是字符串题目读入后第一件事就是去掉换行。坑三删除后数组长度记录不一致。你用一个变量lens维护字符串长度删除时更新了lens但数组结尾的\0没有及时布置后面再用strlen(s)重新算了这样会导致程序读到旧字符。最好的做法是删除操作里只依赖自己维护的长度循环结束后统一在s[lens] \0处收尾。4. 冒泡K趟排序与交换次数统计4.1 标准冒泡排序的两种写法写冒泡排序有很多人习惯写成“外层循环i从0到n-1内层循环j从0到n-i-1”还有不少人写成“外层循环i从0到n-1内层循环j从i1到n-1每次把最小的往前冒”。后者其实不是冒泡更像是选择排序的交换版。标准冒泡应该是相邻元素两两比较大的往后移。每一趟能把当前未排序部分的最大值“冒”到末尾。我给的推荐写法#include stdio.h void bubbleSortK(int arr[], int n, int k) { // 只执行k趟冒泡 for (int i 0; i k; i) { // 第i趟比较范围是[0, n-i-1] for (int j 0; j n - i - 1; j) { if (arr[j] arr[j 1]) { int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; } } } }“冒泡K趟”的核心就在于第i趟的内层循环边界是n - i - 1。你只跑K趟那么到第K趟时边界就停留在n - K - 1。数组后半部分的K个元素已经是全局最大的K个且有序前半部分则保持“部分有序”的状态。4.2 提前终止优化没有交换就停如果题目问“数组在第几趟已经有序”或者让你输出每趟的交换次数你就需要在冒泡中加入“是否发生过交换”的标记。#include stdio.h int bubbleSortWithFlag(int arr[], int n) { int totalSwaps 0; for (int i 0; i n - 1; i) { int swapped 0; for (int j 0; j n - i - 1; j) { if (arr[j] arr[j 1]) { int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; swapped 1; totalSwaps; } } if (!swapped) { // 这一趟没有发生交换说明已经有序提前退出 break; } } return totalSwaps; }注意swapped这个标记必须在每一趟开始前重置为0。我见过有同学把swapped 0放在外层循环外面结果第一趟发生了交换之后swapped永远是1后面所有趟都没法提前退出优化直接失效。4.3 交换次数统计GESP四级的重点变式从热词“gesp四级 202605 冒泡排序交换次数”能看出来近年GESP四级对冒泡排序的考察点已经从“背代码”转向了“理解过程”。最常见的变形有三种第一种直接统计交换次数。给一个数组跑完整冒泡排序输出交换次数。你只需要在交换代码块里加一个计数器。第二种在K趟内统计交换次数。这个更考细心因为你得先做K趟然后仍需知道这K趟里到底换了多少次。这里的坑是如果数组提前有序即使还没到K趟也要停下来否则后续的交换计数都是0趟、但循环依然跑满结果虽然不会错但“是否提前退出”会影响对排序行为的判断。第三种在K趟之后输出数组。这个就是前面代码里写的逻辑但要注意有一种出题人特别喜欢的情况K大于实际需要的趟数。比如数组本来3趟就排好了但题目让你输出5趟之后的结果。这时候如果没有提前退出的逻辑你的数组不会变因为已经有序交换不再发生如果有提前退出循环直接停。两种做法在这个case上输出相同但效率不同。再看一个容易搞混的点很多人把交换次数等同于“逆序对数量”这个问题不大但严格来说标准冒泡排序每次交换恰好消除一个逆序对所以在不分方向的前提下冒泡排序的交换总数确实等于逆序对数。这个性质在选择题里会出现可以直接用。4.4 冒泡排序和选择排序的区分热词里有“选择排序和冒泡排序”这两个排序初学者最容易搞混。核心区别在于对比点冒泡排序选择排序基本操作相邻元素两两比较不符合顺序就交换每次选择未排序部分的最小值放到最前面交换次数最坏O(n^2)平均也较多最多n-1次交换稳定性稳定不稳定因为可能跳过相等元素的相对位置本轮是否提前终止可以通过swapped标记提前退出无法提前退出每趟都得扫描找最小值如果题目问的是“交换次数”选排和冒泡的答案往往是不同的。比如数组{4, 3, 2, 1}冒泡要交换6次选择排序只交换3次。所以读题时必须看清用的是哪种排序。这也是“GESP四级”喜欢出的区分点。5. 现场实录我调试时踩过的坑5.1 单词统计时漏掉最后一个单词这个是字符串题第一高频bug。学生用状态机统计单词长度循环结束后忘了输出最后一个单词因为循环是碰到空格才输出而句子末尾没有空格。我一般建议的解决策略是把输出动作“延迟一帧”。看见空格时不立即输出而是先把当前单词的状态存下来在读到下一个单词开始时再输出上一个单词的长度。这样不会漏也好改。还有另一个思路就是2.1代码里那样循环后补一次if (inWord)输出。两种都能过但“延迟一帧”的思路对处理更多字符串问题更通用。5.2 scanf读数字后残留的换行在作怪Python写多了转C的人最容易犯的错就是先用scanf(%d, n)读了数字再用fgets读字符串结果fgets把换行符吃掉了字符串什么都没读到。解决方案是在scanf后面加一句getchar()把换行消费掉。但要小心如果输入在数字后面有多个空白符比如有空格再换行getchar只能消费一个。用循环while(getchar() ! \n);更稳或者干脆把所有输入都统一用fgets读再做解析。三种方案里我个人最推荐最后一种因为一旦输入都走fgets格式就统一了不再受缓冲区残留困扰。5.3 删除子串后忘记加字符串结束符删除子串时当把后面字符往前搬后新的末尾位置应该立即赋值为\0否则字符串长度就会出错。很多源码里会看到“搬完字符后把总长度减掉但不理末尾”这样后续一旦用strlen(s)计算长度就又读回到了搬走前留下的残骸。处理这个问题最好的办法是不要在删除过程中频繁调用strlen。自己定义一个lens变量来维护长度每次删完更新它循环结束时在res[lens] \0统一收尾。推荐在纸上模拟一次“aaa删aa”就会明白为什么lens要单独维护。5.4 冒泡排序K趟时数组已经提前有序题目问“执行K趟之后数组状态”其实包含了一个隐藏条件如果实际趟数小于K就只执行实际趟数。这里有个细节值得注意——没有提前退出的标准冒泡在第K趟之后数组已经有序后面虽然还在跑但不会有任何交换输出结果同样正确。所以这个坑主要出在“统计交换次数”的变式题里。如果你不做提前退出优化交换次数不会错但如果你做了那么“执行的趟数”减少了部分同学会把“实际趟数”当成K输出。解决办法是单独用一个变量记录实际进行的趟数或者用swapped标记是否是提前退出。5.5 一个通用调试技巧遇到WA先打印中间过程我做OJ题调试时习惯性地在关键位置加printf看中间结果。单词统计就打印inWord和curLen删除子串就打印每次删除后的字符串和当前位置冒泡就打印每一趟结束后的数组。实际上线提交前记得把调试代码删掉否则输出格式直接乱套。对于字符串题还有一个更高效率的调试法拿笔在纸上把数组画出来用下标标好读入的每个字符和\0的位置。绝大多数“为什么匹配不上”“为什么越界”的问题画一遍图就自己看明白了。这个习惯对新手尤其重要比盲目查资料有用得多。6. 从这三道题看GESP四级的字符串与排序备考回到开头说的GESP四级。四级的字符串考点基本就是单词统计、子串删除、替换、反转、大小写转换这一套数组排序考点就是冒泡、选择、插入以及它们的交换次数、趟数、状态变化。备考时不用刷那种偏怪难的题把这三道题的每一个细节吃透比盲目刷30道类似题都有效。单词统计吃透字符边界删除子串吃透字符串在内存中的真实结构冒泡K趟吃透循环嵌套的状态控制——这三个点正好是四级考试中区分度最高的地方。我个人建议的顺序是先搞定冒泡K趟因为它的代码量最小、逻辑最容易验证然后做单词长度统计训练对字符串边界的感觉最后攻删除子串这题会把字符数组和指针操作暴露得最彻底。三道题全部自己独立写完、跑过至少10组测试数据之后再回头去看考纲里其他内容你会发现整个思路都顺了。