代码之家 › 专栏 › 技术社区 › Tool

字符串递归反转

string c

Tool · 技术社区 · 15 年前

好的,我写了这个程序的两个版本。但我在寻找最好的解决方案——最简单、最快速的解决方案。

这是我的解决方案,但我被告知这个解决方案慢了O(N*N),我不知道这到底意味着什么。我还被告知我可以把它分成两个功能来固定它,有人能帮我吗?

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;
          }
     }
}

6 回复 | 直到 9 年前

richardtallent 15 年前

您应该交换最外层的字节,即i=1和j=(l-1),然后i=2,j=(l-2)等,直到i<=(j-1)(换句话说,直到i=j,表示偶数个字符,或者i=j-1,表示奇数)。

在O(N)中执行。

递归不是必需的,而且“将它分成两个函数”似乎也不是必需的。

好的,阅读你的编辑关于这是任务的一部分。

在这种情况下,你做如吉米所说,需要两个函数来保存“main”函数的参数列表。

第二个函数是:

void swapRecursive(char[s], i, l) {      
   if(i >= (l-1) { return; } // no more swapping needed
   char t = s[i];
   s[i] = (l-i);
   s[l-i] = t;
   swapRecurse(s, i+1, l);
   }

请原谅我生锈的C,我现在住在C,vb.net和javascript中,一些细节让我无法理解。

此外,我可能会或可能不会在那里留下一个bug,因为这是作业。;)

Tool 15 年前

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);
}

谢谢理查德,那很有帮助!

这就是你想的吗?

pau.estalella 15 年前

您当然可以更好地交换一端的元素和另一端的元素,并前进到下一个元素。然后需要两个参数:指向当前元素的指针和到另一端的距离。基本情况是距离<=2的情况。这将使您的算法在线性时间内工作(o(n))。

Oren 15 年前

假设您的代码对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<l”、“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)。

您不需要递归来反转文本。用(l-i)字符简单地切换每个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<l/2; i++) {
    switch_chars(&s[i], &s[l-1-i]);
  }
}

Davide Valdo 15 年前

实际上,将问题分解为函数(和内联函数)可能是一个好主意。

算法非常简单,给定一个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);

它会给你一个分割错误。

因此,最好的解决方案实际上是动态分配一个缓冲区,在这个缓冲区中复制反向字符串,然后在不再需要缓冲区时返回并释放缓冲区。

Simon Peverett 11 年前

跳出框框思考。

#include <stdio.h>
#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 <string to reverse>\n");
    else {
        printf("String to reverse: %s\n", argv[1]);
        REVERSE(argv[1]);
        printf("Reversed string:   %s\n", argv[1]);
    }
    return 0;
}