0

我写了一个小字符串压缩算法作为练习的一部分（基本上采用字符串“aaaabbbccc”并返回“a4b3c3”）。代码如下：

char *compress(char string[])
{
    char buffer[256];
    char *pBuffer = buffer;

    char* pStr = (string - 1);
    char currentCharacter = 0;
    int length = 0;

    while (*++pStr != 0)
    {
        currentCharacter = *pStr;
        int currentCharacterLength = 1;

        while ((*(pStr + 1) == currentCharacter) && (*pStr != 0))
        {
            currentCharacterLength++;
            ++pStr;
        }

        *pBuffer++ = currentCharacter;
        *pBuffer++ = (char)currentCharacterLength;
    }

    (*pBuffer) = 0;
    return buffer;
}

但是看着它，我想知道我是否不应该创建另一个实际上适合返回字符串的正确大小的缓冲区。显然，这样做将需要更多的处理时间，但会导致更紧凑的解决方案。所以我想知道，这样的事情的一般做法是什么。牺牲速度来换取内存是更好（通常），还是保持原样更好？

或者更好的是，有没有更好的方法来编写我什至不知道的解决方案？

4

4 回答 4

3

如果是 c++，更好的方法实际上是使用 std::string 类型。

当然，如果您想了解指针/数组/字符串的行为方式或处理 C 库的方式，则有时需要使用字符。

从函数返回 (char *) 和任何其他类型的指针时，最大的问题是如何处理该指针的所有权。你什么时候摆脱这个指针指向的内容？它可以在代码的多个范围内使用，它可以给你各种内存泄漏和未处理的异常。

如果您使用 c++，从函数返回指针的最佳方法是使用 std::shared_ptr，因为您不需要直接处理该指针的内存释放。

哦，当然，返回一个指向在堆栈中分配的内存的指针：

char buffer[256];
char *pBuffer = buffer;

是你代码的最大错误。

正确的方法是在堆上分配它：

char *pBuffer = new char[256];
于 2013-05-16T18:53:13.307 回答
3

返回buffer是未定义的行为：只要您的函数存在，该缓冲区的内容就可以是任何东西。您应该动态分配内存 - 至少， return strdup(buffer)。

由于这是 C++，std::string因此首选使用：它将为您正确管理内存，因此即使您没有正确猜测字符串的大小，也不会出现缓冲区溢出。如果压缩字符串恰好超过 256 个字符，您当前的解决方案将失败；基于std::string的解决方案将没有这个缺点。

于 2013-05-16T18:53:43.503 回答
1

根据您的回答，像往常一样，这取决于...

你最有限的资源是什么？什么是托管您的应用程序？如果这是一个嵌入式项目，您的应用程序内存是否足以容纳一个 char[256] 缓冲区？

如果您在 Xcode 或 Eclipse 中的完整计算机设置上运行此程序，那么这些 IDE 将在此级别上管理您几乎所有的内存问题，但如果您有一个大文件（例如尝试使用此模式压缩小说），那么速度是要优化的情况。

如果是这种情况，我会小心你的代码，因为你有一个嵌套循环，它可能会将整个压缩算法减慢到 O(string.length()^2) ，这对于大字符串来说很糟糕（再次，就像压缩一本书） .

因此，在回答您的问题时，如果您想使用这种特定方法而不是霍夫曼编码或其他更有效的算法（在时间和空间上），那么我会保留您当前的设置，但删除双同时，使用递归代替找到类似字母序列的流。

于 2013-05-16T19:04:05.543 回答
1

如果你想使用指针，你可以这样做：

 bool compress(char string[], char* encodedOut, int &encodedSize);

这样您就会知道编码数组的大小和范围问题将得到处理。

于 2013-05-16T19:05:03.847 回答