3

我正在尝试编写一个接受三个 c 样式字符串并返回一个 c 样式字符串的函数。此函数在 c 字符串中搜索所有出现的子字符串，并用不同的字符串替换它们。
这个程序有效，但看起来很不优雅。我情不自禁地感觉它本来可以用不那么笨重的方式完成。

char* replaceSubstring(char *original, char *from, char *to)
{
     int origlen = strlen(original);
     int i = 0;
     int count = 0;
     char *ptr;

     //figure out how many times the sub-string occurs in a string.
     //i couldn't figure out a way to avoid this loop
     while (i<origlen)
     {
           ptr = strstr(original+i, from);
           if (!ptr)
               break;
           else
           {
               i = ptr - original + 1;
               count++;
           }
     }
     //figure out what the size of the output string has to be
     int newsize = origlen + (strlen(to) - strlen(from)) * count;

     char *newstring = new char[newsize];  
     newstring[0] = '\0';  
     i = 0;
     while (i < origlen)
     {
          ptr = strstr(original+i, from);
          if (!ptr)
          {
               strcat(newstring,original+i);
               break;
          }
          else
          {
               //this looks extremely ugly and bulky...
               strncat(newstring, original+i, ptr-(original+i));
               strcat(newstring, to);
               i = i + ptr - (original + i) + strlen(from);
          }
     }
     strcat(newstring,"\0");
     return newstring;
}

有人对如何使这段代码更清晰和/或更高效有任何建议吗？欢迎任何意见。请不要建议改用类字符串。这不是一个选择。该函数必须与 c 字符串一起使用

4

4 回答 4

3

我会做的一项改进可能会同时提高优雅和效率，那就是

  1. 分配一个整数数组，该数组将保存与给定字符串匹配的子字符串的索引。
  2. 遍历字符串并找到所有匹配的子字符串，并将每个子字符串添加到数组中，根据需要重新分配更大的数组（因为您不想使用我认为的 STL；如果可以，请使用）。std::vector std::list std::deque
  3. 根据原始字符串的长度和找到的子字符串的数量为修改后的字符串分配新内存。
  4. 同时迭代旧字符串和数组，将旧字符串中不匹配的部分复制到新字符串中。
  5. 用替换字符串填充您留下的孔。

此外，我不会在函数内部动态分配内存，而是将其更改为接受调用者分配的缓冲区和最大缓冲区大小。这样，调用者可以完全负责内存的生命周期（如果他们愿意/可以使用自动内存），您不必担心计算缓冲区大小（您依赖调用者）。

编辑：

这是我创建的一个示例实现。如果有人发现任何错误，请告诉我，这很可能。（如果您想自己弄清楚，您可能不想阅读此内容。）

char* strreplace(const char* haystack, const char* needle, const char* replacement) {
    // using deque for pop_front
    std::deque<const char*> positions;
    unsigned int haystacklen    = strlen(haystack),
                 needlelen      = strlen(needle),
                 replacementlen = strlen(replacement);

    for (const char* cur = haystack, *pos = strstr(cur, needle); pos; cur = pos + 1, pos = strstr(cur, needle))
        positions.push_back(pos);

    char* newstr    = new char[haystacklen + replacementlen * positions.size() + 1],
          dst       = newstr;
    const char* src = haystack;

    while (src <= haystack + haystacklen)
        if (!positions.empty() && src == positions.front()) {
            strcpy(dst, replacement);
            dst += replacementlen;
            src += needlelen;
            positions.pop_front();
        } else
            *dst++ = *src++;

    return newstr;
}

并且不要忘记delete[]该函数的返回值。

我追求效率而没有做最大的优化。例如，您可以有一个while循环执行，而positions.empty()当它为假时，然后当它变为真时，只需退出循环并直接strcpy执行其余部分，因为不再需要进行替换，这将让您避免不必要地positions.empty()调用每个字符，即使没有替换，或者根本没有。但我认为这是一个小问题，代码传达了这一点。

此外，我曾经删除所有阵列管理代码，但如果您想自己做，那应该是直截了当的。std::list std::deque

正如 ildjarn 在评论中提到的那样，我从 更改list为deque因为我使用了该size成员，并且根据他的评论，它不是O(1)（通常是O(n)）在所有 C++11 之前的实现中，所以deque使用它的恒定时间size会更有效.

于 2012-04-25T01:21:26.283 回答
0

如果您只需将 newstring 的大小设置为解决方案后的最大可能大小，您就可以摆脱代码的第一部分来计算计数。

尤其是：

int newsize = origlen + (strlen(to) - strlen(from)) * origlen/strlen(from);

此外，不要多次调用 strlen(from)，只需将其分配给一个变量（例如 srtlen_from）并使用它。

于 2012-04-25T01:43:50.143 回答
0

这是我制作的一个版本，它几乎只使用指针（省略了错误检查等）（我还注意到它在某些情况下会失败）：

#include <cstring>
#include <cstdlib>
#include <iostream>

char* replaceSubstring(char *original, char *from, char *to)
{
// This could be improved (I was lazy and made an array twice the size)
    char* retstring = new char[std::strlen(original) * 2];

    int pos = 0;
    for (int i = 0; *(original + i); ++i)
    {   
        if (*(original + i) == *(from)) 
        {
            // Got a match now check if the two are the same
            bool same = true; // Assume they are the same
            for (int j = 1, k = i + 1; *(from + j) && *(original + k); ++j, ++k)
            {
                if (*(from + j) != *(original + k))
                {
                    same = false;
                    break;
                }
            }
            if (same)
            {
                // They are the same now copy to new array
                for (int j = 0; *(to + j); ++j)
                {
                    retstring[pos++] = *(to + j);
                }
                i += std::strlen(from) - 1;
                continue;
            }
        }
        retstring[pos++] = *(original + i);
    }
    retstring[pos] = '\0';
    return retstring;
}

int main()
{
    char orig1[] = "Replace all the places that say all";
    char* r1 = replaceSubstring(orig1, "all", "Replacement");
    std::cout << r1 << std::endl;
    delete [] r1;

    char orig2[] = "XXXXXX with something else XXXXXX";
    char* r2 = replaceSubstring(orig2, "XXXXXX", "hello");
    std::cout << r2 << std::endl;
    delete [] r2;
}
于 2012-04-25T02:25:33.413 回答
0

不言自明： http ://ideone.com/ew5pL

这就是丑陋和笨重的样子——除了最后的 strlen 和 memcpy 之外，没有 C 函数。

我觉得你的看起来又漂亮又紧凑。

于 2012-04-25T20:41:12.210 回答