C语言实现Z字形输出：详解算法与代码优化61

在程序设计中，字符的特殊输出方式往往能够体现算法设计的巧妙之处。 “Z字形输出”就是一个经典的例子，它要求程序将输入的字符串按照Z字形的路径输出。本文将深入探讨C语言实现Z字形输出的多种方法，分析其算法原理，并给出相应的代码实现及优化策略，力求让读者能够透彻理解并灵活运用。

一、问题描述

给定一个字符串，将其按照Z字形路径输出。例如，输入字符串为"PAYPALISHIRING"，行数为3，则输出应为"PAHNAPLSIIGYIR"。

假设输入字符串为 `s`，行数为 `numRows`。输出的Z字形路径可以形象地理解为一个锯齿形的路径。当 `numRows` 为 3 时，路径如下：```
P A H N
A P L S I I G
Y I R
```

当 `numRows` 为 4 时，路径如下：```
P I N
A L S I G
Y A H R
P I
```

二、算法设计与实现

我们可以通过分析Z字形路径的规律来设计算法。观察可以发现，Z字形路径中的字符的索引与行号之间存在一定的对应关系。我们可以使用一个二维数组来模拟Z字形路径，然后将字符串中的字符逐个放入相应的数组元素中。最后，按照数组的行优先顺序输出即可。

以下提供两种C语言实现方法：

方法一：模拟Z字形路径

这种方法直接模拟Z字形路径，使用一个二维数组存储字符。代码如下：```c
#include
#include
void printZ(char *s, int numRows) {
int len = strlen(s);
char matrix = (char )malloc(numRows * sizeof(char *));
for (int i = 0; i < numRows; i++) {
matrix[i] = (char *)malloc(len * sizeof(char));
memset(matrix[i], '\0', len * sizeof(char)); // 初始化数组
}
int row = 0, col = 0;
int down = 1; // 方向标志，1表示向下，-1表示向上
for (int i = 0; i < len; i++) {
matrix[row][col] = s[i];
row += down;
col++;
if (row == numRows - 1 || row == 0) {
down *= -1; // 改变方向
}
}
for (int i = 0; i < numRows; i++) {
for (int j = 0; j < len; j++) {
if (matrix[i][j] != '\0') {
printf("%c", matrix[i][j]);
}
}
}
printf("");
// 释放内存
for (int i = 0; i < numRows; i++) {
free(matrix[i]);
}
free(matrix);
}
int main() {
char str[] = "PAYPALISHIRING";
int numRows = 3;
printZ(str, numRows); // 输出PAHNAPLSIIGYIR
numRows = 4;
printZ(str, numRows); // 输出PINALSIGYAHRPI
return 0;
}
```

方法二：直接访问索引

这种方法更加高效，它直接计算每个字符在最终结果中的索引位置，无需使用额外的二维数组。代码如下：```c
#include
#include
void printZOptimized(char *s, int numRows) {
int len = strlen(s);
if (numRows == 1) {
printf("%s", s);
return;
}
char result[len + 1];
result[len] = '\0';
int cycleLen = 2 * numRows - 2;
for (int i = 0; i < numRows; i++) {
for (int j = 0; j < len; j++) {
int index = j;
if (i == 0 || i == numRows - 1) {
if (j % cycleLen == i) {
result[i + (j/cycleLen) * (numRows -1 + numRows -2)] = s[index];
}
} else {
if (j % cycleLen == i || j % cycleLen == cycleLen - i) {
if (j % cycleLen == i)
result[i + (j/cycleLen) * (numRows -1 + numRows -2)] = s[index];
else
result[i + (j/cycleLen) * (numRows -1 + numRows -2) + (j / cycleLen) * (numRows-1)] = s[index];
}
}
}
}
printf("%s", result);
}

int main() {
char str[] = "PAYPALISHIRING";
int numRows = 3;
printZOptimized(str, numRows); // 输出PAHNAPLSIIGYIR
numRows = 4;
printZOptimized(str, numRows); // 输出PINALSIGYAHRPI
return 0;
}
```