PTA基础编程题目集 7-32 说反话-加强版（C语言实现）

摘要： 本文解析一道经典 PAT 算法题：将英语句子中的所有单词顺序反转。题目要求处理长度不超过 50 万字符的输入，单词间可能有多个空格。文章提供完整的 C 语言代码实现，通过跳过连续空格、记录单词起止位置，最后倒序输出保证单词间仅一个空格。

题目描述：

给定一句英语，要求你编写程序，将句中所有单词的顺序颠倒输出。

解题思路

算法的核心逻辑可以用以下流程图表示：

#mermaid-svg-Q4GHobLOCxPidDOp{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-Q4GHobLOCxPidDOp .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-Q4GHobLOCxPidDOp .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-Q4GHobLOCxPidDOp .error-icon{fill:#552222;}#mermaid-svg-Q4GHobLOCxPidDOp .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-Q4GHobLOCxPidDOp .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-Q4GHobLOCxPidDOp .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-Q4GHobLOCxPidDOp .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-Q4GHobLOCxPidDOp .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-Q4GHobLOCxPidDOp .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-Q4GHobLOCxPidDOp .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-Q4GHobLOCxPidDOp .marker{fill:#333333;stroke:#333333;}#mermaid-svg-Q4GHobLOCxPidDOp .marker.cross{stroke:#333333;}#mermaid-svg-Q4GHobLOCxPidDOp svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-Q4GHobLOCxPidDOp p{margin:0;}#mermaid-svg-Q4GHobLOCxPidDOp .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-Q4GHobLOCxPidDOp .cluster-label text{fill:#333;}#mermaid-svg-Q4GHobLOCxPidDOp .cluster-label span{color:#333;}#mermaid-svg-Q4GHobLOCxPidDOp .cluster-label span p{background-color:transparent;}#mermaid-svg-Q4GHobLOCxPidDOp .label text,#mermaid-svg-Q4GHobLOCxPidDOp span{fill:#333;color:#333;}#mermaid-svg-Q4GHobLOCxPidDOp .node rect,#mermaid-svg-Q4GHobLOCxPidDOp .node circle,#mermaid-svg-Q4GHobLOCxPidDOp .node ellipse,#mermaid-svg-Q4GHobLOCxPidDOp .node polygon,#mermaid-svg-Q4GHobLOCxPidDOp .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-Q4GHobLOCxPidDOp .rough-node .label text,#mermaid-svg-Q4GHobLOCxPidDOp .node .label text,#mermaid-svg-Q4GHobLOCxPidDOp .image-shape .label,#mermaid-svg-Q4GHobLOCxPidDOp .icon-shape .label{text-anchor:middle;}#mermaid-svg-Q4GHobLOCxPidDOp .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-Q4GHobLOCxPidDOp .rough-node .label,#mermaid-svg-Q4GHobLOCxPidDOp .node .label,#mermaid-svg-Q4GHobLOCxPidDOp .image-shape .label,#mermaid-svg-Q4GHobLOCxPidDOp .icon-shape .label{text-align:center;}#mermaid-svg-Q4GHobLOCxPidDOp .node.clickable{cursor:pointer;}#mermaid-svg-Q4GHobLOCxPidDOp .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-Q4GHobLOCxPidDOp .arrowheadPath{fill:#333333;}#mermaid-svg-Q4GHobLOCxPidDOp .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-Q4GHobLOCxPidDOp .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-Q4GHobLOCxPidDOp .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-Q4GHobLOCxPidDOp .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-Q4GHobLOCxPidDOp .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-Q4GHobLOCxPidDOp .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-Q4GHobLOCxPidDOp .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-Q4GHobLOCxPidDOp .cluster text{fill:#333;}#mermaid-svg-Q4GHobLOCxPidDOp .cluster span{color:#333;}#mermaid-svg-Q4GHobLOCxPidDOp div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-Q4GHobLOCxPidDOp .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-Q4GHobLOCxPidDOp rect.text{fill:none;stroke-width:0;}#mermaid-svg-Q4GHobLOCxPidDOp .icon-shape,#mermaid-svg-Q4GHobLOCxPidDOp .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-Q4GHobLOCxPidDOp .icon-shape p,#mermaid-svg-Q4GHobLOCxPidDOp .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-Q4GHobLOCxPidDOp .icon-shape .label rect,#mermaid-svg-Q4GHobLOCxPidDOp .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-Q4GHobLOCxPidDOp .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-Q4GHobLOCxPidDOp .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-Q4GHobLOCxPidDOp :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

是

否

是

否

是

否

是

否

开始

读取字符串 s，去除末尾换行符

初始化 wordCount=0，i=0

i < len ?

跳过连续空格

i < len ?

记录单词起始位置，计算长度

wordCount++

j = wordCount-1 ; j >= 0 ?

j != wordCount-1 ?

输出空格

输出单词

j–

输出换行符

结束

输入格式：

测试输入包含一个测试用例，在一行内给出总长度不超过 500 000 的字符串。字符串由若干单词和若干空格组成，其中单词是由英文字母（大小写有区分）组成的字符串，单词之间用若干个空格分开。

输出格式：

每个测试用例的输出占一行，输出倒序后的句子，并且保证单词间只有 1 个空格。

输入样例：

Hello World Here I Come

输出样例：

Come I Here World Hello

代码部分实现：

#include <stdio.h> // 引入标准输入输出头文件
#include <string.h> // 引入字符串处理头文件

int main() {
char s[500001]; // 定义字符数组存储输入字符串，最大长度500000
fgets(s, 500001, stdin); // 从标准输入读取一行字符串
int len = strlen(s); // 获取字符串实际长度
if (s[len – 1] == '\\n') s[—len] = '\\0'; // 去除末尾换行符

int words[500000]; // 存储每个单词的起始位置
int wordLens[500000]; // 存储每个单词的长度
int wordCount = 0; // 单词计数器，初始化为0

int i = 0; // 遍历字符串的索引
while (i < len) { // 遍历整个字符串
while (i < len && s[i] == ' ') i++; // 跳过连续空格
if (i < len) { // 如果还没到字符串末尾
words[wordCount] = i; // 记录单词起始位置
int start = i; // 保存起始位置
while (i < len && s[i] != ' ') i++; // 找到单词结束位置（空格处）
wordLens[wordCount] = i – start; // 计算单词长度
wordCount++; // 单词数加1
}
}

for (int j = wordCount – 1; j >= 0; j—) { // 从最后一个单词开始倒序输出
if (j != wordCount – 1) printf(" "); // 非首个输出的单词前打印空格分隔
for (int k = words[j]; k < words[j] + wordLens[j]; k++) { // 遍历单词的每个字符
printf("%c", s[k]); // 输出单词的每个字符
}
}
printf("\\n"); // 输出换行符

return 0; // 程序正常结束
}