c++ - 需要一些关于 C++ 中简单无损压缩算法的想法

Question

我正在学习编程入门类(class)，我们的作业之一是用 C++ 编写无损压缩程序。唯一的限制是我们不能使用 STL、静态变量或全局变量。我发现的很多压缩算法都需要使用我不允许使用的 map/multimap，所以霍夫曼编码和 LZW 几乎是不可能的，除非我可以编写自己的 map 类并让它工作。

我发现很多算法也使用 std::string，但我完全可以使用 cstring(我们被允许使用)。我还可以访问我的教授创建的一些我们可以使用的库。我们可以访问以下内容:

• Red-Black、AVL、Splay 等各种树
• 二叉堆
• 各种哈希表，例如几个开放寻址实现，以及单独的链
• vector 、链表和队列

所以除上述之外的任何事情我都必须自己编写代码。

有没有人推荐任何非常简单的无损压缩算法？ Huffman 和我在网上找到的其他压缩算法似乎非常复杂，更不用说我不能在 STL 中使用 map/multimap :(。我不是在这里寻找绝对最快的算法，只是作为起点的东西，我们会根据需要调整它以使其运行得更快。

Answer 1

A lot of the compression algorithms I have found require use of map/multimap which I am not allowed to use so Huffman encoding and LZW are pretty much out of the question

嗯？当然不是。映射是一种非常薄的抽象，可在您的树或哈希表实现之一上实现。

unless I can write my own map class and get it to work

这可能就是练习的重点。

继续吧。你可以在汇编中做面向对象的。您可以在没有(现成的)数据结构的情况下编写算法。这只是更多的工作。而且更容易出错。并且更有教育意义(我希望 :) 显然也需要好的学费)