当前位置：文江博客话题详情

算法与设计模式有何不同？

发布于 2024-11-08 06:03:29 字数 283 浏览 0 评论 0原文

我是 C 编程新手；来自 OOP PHP 背景。

我发现 C 是（难怪）一种更难的语言。起初，我在弄清楚数组上的一些事情时遇到了很多问题：就像没有本机关联数组一样。

现在，我想我正在一点一点地弄清楚这一部分，但是现在我有一个关于我昨天与 C 开发人员进行的对话的问题。她正在向我解释二分搜索算法，因为我问她是否有库可以用 C 语言做数组相关的事情，因为这似乎是一个比总是重新发明轮子更聪明的解决方案。

我真的很想了解更多关于 C 语言的算法，特别是算法和我习惯在 PHP 中使用的设计模式之间有什么区别？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

So尛奶瓶 2024-11-15 06:03:29

按顺序排列：C 对关联数组之类的内容的支持范围是 qsort，用于根据键对结构数组进行排序，以及 bsearch 来查找基于键的结构数组在一把钥匙上。当然，还有很多替代方案——其他各种库都有哈希表、平衡树等。但很难猜测到底哪个适合您的目的。

顺便说一句，我不知道有多少好书涵盖了使用 C 作为主要演示工具的算法。关于一般算法（大部分与语言无关）的书籍的一些明显推荐是：

Donald Knuth 所著的
计算机编程艺术。这几乎是类算法书籍。现在（终于）达到了四卷。高德纳最初于 1967 年开始写作，计划写 7 卷。很长一段时间内只有三卷可用。第四个是最近添加的。按照他目前的速度，如果 Knuth 能活到 100 岁以上，他的寿命只能到 7 岁。尽管如此，其中的部分非常好——但是（警告！）他对算法进行了相当详细的分析；如果您至少不懂一点微积分，那么相当多的微积分可能很难理解。
算法简介，作者：Cormen、Leiserson、Rivest 和 Stein。 IIRC，现在有一个比我的版本更新的版本，其中又添加了另一位作者。这是一本大书（把它掉到脚趾上会很痛苦）。它自始至终使用了大量的数学符号等，但如果您愿意花点时间查找符号，那么它确实很容易理解。它涵盖了相当多的重要领域（例如，图算法），这些内容计划在 Knuth 的后面几卷中介绍，但（至少目前）还没有。
算法和数据结构，作者：Aho、Hopcraft 和 Ullman。这是（相当公平地）最小、最轻的，至少对于大多数人来说可能是其中最容易遵循的。
虽然它已经不再可用，但如果您能找到 Niklaus Wirth 的算法 + 数据结构 = 程序，这就是我真正建议的。它使用 Pascal（毫不奇怪——Niklaus Wirth 发明了 Pascal），但这已经足够像 C 了，不会造成真正的问题。它没有像 Knuth 那样深入探讨每种算法，但仍然足以让人很好地了解一种算法何时可能是另一种算法的不错选择。对于像你这样的职位的人（有一些编程背景，但在这个领域很少），这是我的首要推荐。

尽管我之前已经说过，但我认为值得重复：在我看来，罗伯特·塞奇威克（Robert Sedgewick）关于算法的所有书籍都应该避免。 C++ 中的算法可能是其中最差的，但其他算法也只是稍微好一些。它们包含的代码（特别是 C++ 版本）确实很糟糕，并且算法的描述通常不完整和/或具有误导性。最新版本已经解决了一些问题，但是（IMO）还不足以成为值得推荐的东西。如果没有其他选择，您可能可以通过这些，但考虑到许多明显优越的替代方案，阅读这些内容的唯一原因是如果有人将它们提供给您，并且您绝对买不起其他任何东西。

就算法与设计模式而言，界限可能在某些地方变得模糊，但通常算法的定义要严格得多。算法通常具有特定的、严格定义的输入，它以特定的方式处理该输入以产生同样特定的结果/输出。设计模式的定义往往更加松散、更加通用。算法也可以是通用的（例如，排序算法可能需要定义严格的弱排序的类型），但对该类型仍然有特定要求。

设计模式的定义往往比较宽松。例如，访问者模式涉及处理对象组——但是当我们决定需要以新的不同方式处理这些对象时，我们不想修改这些对象的类型。为此，我们将进程与要处理的对象分开定义，以及如何遍历对象组，并允许一个进程处理每个对象。

从一个相当不同的方向来看，您通常可以使用一个函数或一小组函数来实现算法。设计模式往往更倾向于您编写代码的风格，而不仅仅是“这里有一个函数，使用它”。

Taking things in order: the extent of C's support for anything like an associative array would be qsort to sort an array of structures based on a key, and bsearch to find one based on a key. There are, of course, quite a few alternatives -- various other libraries have hash tables, balanced trees, etc. Exactly which will suit your purposes is hard to guess though.

Offhand, I don't know of many good books covering algorithms that use C as their primary vehicle for demonstration. A few obvious recommendations for books on algorithms in general (mostly language independent) would be:

The Art of Computer Programming by Donald Knuth. This is pretty much the class algorithms book. It's now (finally) up to four volumes. Knuth originally started on it in 1967, planning to write 7 volumes. Only three volumes were available for a long time. A fourth was added quite recently. At the rate he's going, it's only going to make it to 7 if Knuth lives to be well past 100 years old. Nonetheless, the parts that are there are extremely good -- but (warning!) he analyzes the algorithms in considerable detail; if you don't know at least a little calculus, a fair amount will probably be hard to follow.
Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein. IIRC, there's now a newer edition than I have, which adds yet another author. This is a large book (dropping it on your toes would be quite painful). It uses a fair amount of mathematical notation and such throughout, but if you're willing to work a little at looking up the notation, it's really pretty understandable. It covers quite a bit of important ground (e.g., graph algorithms) that are scheduled for later volumes of Knuth, but not (at least yet) available there.
Algorithms and Data Structures by Aho, Hopcraft and Ullman. This is (by a pretty fair margin) the smallest, lightest, and at least for most people probably the easiest of these to follow.
Though it's only available used anymore, if you can find a copy of Algorithms + Data Structures = Programs by Niklaus Wirth, that's what I'd really suggest. It uses Pascal (no surprise -- Niklaus Wirth invented Pascal), but that's enough like C that it doesn't cause a real problem. It doesn't go into as much depth as Knuth about each algorithm, but still enough to give a good feel for when one is likely to be a good choice versus another. For somebody in your position (some background in programming, but little in this area) it's my top recommendation.

Though I've said it before, I think it bears repeating: IMO, all of Robert Sedgewick's books on algorithms should be avoided. Algorithms in C++ is probably the worst of them, but the others are only marginally better. The code they include (again, especially the C++ version) is truly execrable, and the descriptions of algorithms are often incomplete and/or misleading. The most recent editions have fixed some of the problems, but (IMO) not nearly enough to qualify as something that should ever be recommended. If there was no alternative, you could probably get by with these, but given the number of alternatives that are dramatically superior, the only reason to read these at all is if somebody gives them to you, and you absolutely can't afford anything else.

As far as algorithms versus design patterns goes, the line can get blurry in places, but generally an algorithm is much more tightly defined. An algorithm will normally have a specific, tightly defined input which it processes in a specific way to produce an equally specific result/output. A design pattern tends to be more loosely defined, more generic. An algorithm can be generic as well (e.g., a sorting algorithms might require a type that defines a strict, weak ordering) but still has specific requirements on the type.

A design pattern tends to be somewhat more loosely defined. For example, the visitor pattern involves processing groups of objects -- but we don't want to modify the types of those objects when we decide we need to process them in a new and different way. We do that by defining the processes separately from the objects to be processed, along with how we'll traverse the groups of objects, and allow a process to work with each.

To look at it from a rather different direction, you can usually implement an algorithm with a function or a small group of functions. A design pattern tends to be oriented more toward the style in which you write your code, rather than just "here's a function, use it."

回复收藏 0 原文