字符串压缩(面试准备)

Question

我需要压缩一根绳子。可以假设字符串中的每个字符不超过255次。我需要返回压缩字符串及其长度。在过去的两年里，我和C#一起工作，忘记了C++。我将很高兴听到您对代码、算法和c++编程实践的评论。

// StringCompressor.h
class StringCompressor
{
public:
    StringCompressor();
    ~StringCompressor();
    unsigned long Compress(string str, string* strCompressedPtr);
    string DeCompress(string strCompressed);
private:
    string m_StrCompressed;
    static const char c_MaxLen;
};
// StringCompressor.cpp
#include "StringCompressor.h"
const char StringCompressor::c_MaxLen = 255;

StringCompressor::StringCompressor()
{
}


StringCompressor::~StringCompressor()
{
}

unsigned long StringCompressor::Compress(string str, string* strCompressedPtr)
{
    if (str.empty())
    {
        return 0;
    }

    char currentChar = str[0];
    char count = 1;
    for (string::iterator it = str.begin() + 1; it != str.end(); ++it)
    {
        if (*it == currentChar)
        {
            count++;
            if (count == c_MaxLen)
            {
                return -1;
            }
        }
        else
        {
            m_StrCompressed+=currentChar;
            m_StrCompressed+=count;
            currentChar = *it;
            count = 1;
        }
    }
    m_StrCompressed += currentChar;
    m_StrCompressed += count;
    *strCompressedPtr = m_StrCompressed;
    return m_StrCompressed.length();
}

string StringCompressor::DeCompress(string strCompressed)
{
    string res;
    if (strCompressed.length() % 2 != 0)
    {
        return res;
    }
    for (string::iterator it = strCompressed.begin(); it != strCompressed.end(); it+=2)
    {
        char dup = *(it + 1);
        res += string(dup, *it);
    }
    return res;
}

Answer 1

可以有许多改进：

1. 不要为unsigned long函数返回-1。
2. 考虑使用size_t或ssize_t来表示大小。
3. 学习const
4. 如果重复调用m_StrCompressed，则Compress具有假状态。由于这些成员不能被重用，所以您最好使函数是静态的。
5. 压缩的内容一般不应视为字符串，而应视为字节缓冲区。重新设计你的界面。
6. 评论！没人知道你在这里做什么。
7. 奖励:如果你的压缩产生更大的效果，你的回退机制。例如，表示未压缩缓冲区或返回失败的标志。
8. 我想效率不是这里的主要问题。

Answer 2

有几件事：

• 我完全赞成使用类，也许您可以在这里以一种更有意义的方式这样做。但是，考虑到您要做的事情的范围，这里作为两个函数更好。一个用于压缩，一个用于解压。例如，为什么要将字符串作为对象存储在类中，而从不使用它？如何将其分组为一个类来实际增强功能或使其更可重用？
• 您应该将压缩的字符串返回作为引用而不是指针传递。
• 看起来，您正在尝试计算字符在一行中重复的次数，并保存它。对于大多数普通字符串，这将使压缩字符串的大小大于未压缩字符串，因为存储每个非重复字符需要两个字节。
• 有很多字符，有两种位。如果您这样做，尝试分组重复位，您将更成功(这实际上是一种简单的无损压缩方法)。
• 如果允许，只需使用像zlib这样的库对任意数据类型进行压缩。