字符串反转递归
好的，我写了这个程序的2个版本。 但我正在寻找最好的解决方案 – 最简单快速的解决方案。
这是我的解决方案，但我被告知这个解决方案是O（n * n）慢，我不知道究竟是什么意思。 我还被告知我可以通过将它分成2个function来固定它，任何人都可以帮我这样做吗？
void reverse3(char s[]) { int l; int i; l = strlen(s); if(l > 1) { reverse3(s + 1); for(i = 1; i < l; i++) { int temp = s[i-1]; s[i-1] = s[i]; s[i] = temp; } } } 你应该交换最外面的字节，即i = 1和j =（l-1），然后i = 2，j =（l-2）等，直到i <=（j-1）（换句话说，直到i = j，对于偶数个字符，或i = j-1，对于奇数）。
那将在O（n）中执行。
递归是没有必要的，并且“将它分成两个函数”似乎没有必要恕我直言。
好的，阅读你的编辑，这是作业的一部分。
在这种情况下，您需要两个函数，如Jimmy所说，保留“main”函数的参数列表。
第二个function是：
void swapRecursive(char[s], i, l) { if(i >= (l-1) { return; } // no more swapping needed char t = s[i]; s[i] = (li); s[li] = t; swapRecurse(s, i+1, l); }
请原谅我生锈的C，我现在住在C＃，VB.NET和JavaScript中，一些细节让我感到厌烦。
此外，我可能会或可能不会在那里留下一个错误，因为这是家庭作业。 ;）
void swapRecursive(char s[], int i, int len) { if(i >= len/2+1) return; char t = s[i]; s[i] = s[len-i]; s[len-i] = t; swapRecursive(s, i+1, len); } void reverse3(char s[]) { int i = 0; swapRecursive(s, i, strlen(s) - 1); }
谢谢理查德，这很有帮助！
这是你的想法吗？
你当然可以更好地在另一端用元素交换元素，然后前进到下一个元素。 然后，您将需要两个参数：指向当前元素的指针和到另一端的距离。 基本情况是距离<= 2的情况。这将使您的算法工作在线性时间（O（n））
假设您的代码对n长度字符串执行F（n）运算。 然后，从您编写的递归中我们可以看到：
F（2）= 2
F（n）= n + F（n-1）+（n-1）* 5 = F（n-1）+ 6n – 5
第一个’n’是strlen，F（n-1）是递归调用，（n-1）* 5来自for循环（3个操作，和“i 如果我们打开公式，我们得到： F（n）= 6n-5 + 6（n-1）-5 + 6（n-2）-5 + … + 6 *（2）-5 = 6（2 + 3 + 4 + … + n） – 5 * n = 6（n（n + 1）/ 2 -1） – 5n F（n）= 3n ^ 2 + 3n -6 -5n = 3n ^ 2 -2n -6 最后一个公式显然是O（n ^ 2）。 您不需要递归来反转文本。 使用（li）-char简单地切换每个i-char。
void switch_chars(char *a, char *b) { char temp = *a; *a = *b; *b = temp; } void reverse(char s[]) { int l = strlen(s); for (int i=0; i
实际上将问题分解为函数（和内联函数）可能是个好主意。
该算法非常简单，给定一个n个字符的字符串，您将第一个字符与最后一个字符交换，第二个字符与最后一个字符交换，依此类推，直到您交换每个字符为止。
这可以用伪代码表示：
str: string of length n i <- 0 j <- n - 1 reverse (i, j): if i < j: swap str[i] and str[j] increment i decrement j reverse(i, j)
这是一个可能的C实现与指针：
static inline void swapCharacters (char* a, char* b) { *a += *b; *b = *a - *b; *a -= *b; } static void recursiveReverse (char* left, char* right) { if (left < right) { swapCharacters(left, right); recursiveReverse(++left, --right); } } void reverseString (char* string) { char* last = strchr(string, '\0') - 1; // Finds the first character before the terminator recursiveReverse(string, last); }
无论如何，如果您的字符串是只读缓冲区，这将无法工作，例如，如果您尝试这样做
char* string = "My string"; reverseString(string);
它会给你一个分段错误。
因此，最佳解决方案实际上是动态分配一个缓冲区，在该缓冲区中复制反向字符串，然后返回缓冲区并在不再需要时释放缓冲区。
外箱思考。
#include #define REVERSE(STRING) r(*(STRING),(STRING),(STRING)+1) char *r(char v, char *s, char *n) { if (*n && *s) s = r(*n, s, n+1); *s = v; return s+1; } int main(int argc, char *argv[]) { if (argc < 2) printf("Usage: RSIP \n"); else { printf("String to reverse: %s\n", argv[1]); REVERSE(argv[1]); printf("Reversed string: %s\n", argv[1]); } return 0; }