c - 在c中使用链表排序

Question

我正在实现排序。该程序从一个带有 ASCII 字符的文本文件中读取。每行有两个元素，用空格分隔。假设输入是“a b”。这定义了 a 和 b 之间的优先关系，即“a 必须出现在 b 之前”。

如果文件是

a bd cb d

输出是

abdc

我创建了两个链表

• bigList:存储唯一元素(count 跟踪前面的元素)
• smallList:存放前面的元素
• 列表项

我的代码所做的总结

• 逐行读取文件
• 每行抓取两个元素
• 检查它们是否已经存在，如果不存在则插入它们
• 根据计数打印出结果

它实际上打印出文件中的所有元素，就像上面的输入一样，我的输出是

abbddc

我是 C 编程的新手，请让我知道我做错了什么。

Answer 1

我对拓扑排序知之甚少，但我想我知道的足以留下一个聪明的评论。任何人都可以随意编辑此回复。

我发现此实现存在几个问题。有些与 C 相关，有些与算法相关，所以让我一次一个地过一遍。

---

问题定义。 Topological sort确实被定义为有向图中元素的优先级。但是，仅仅这句话并不能完全定义问题。具体来说，拓扑排序是从指定源顶点开始的图元素的优先级。作为示例，假设您有以下有向图:

a -> b
b -> c
c -> a

如果您从顶点 a 开始，您的拓扑顺序应该是 {a, b, c}。如果您从顶点 c 开始，您的拓扑顺序应该是 {c, a, b}。因此，如果没有源顶点，问题定义就没有意义。这种顶点的一种选择可能是图中的某个顶点没有边指向它，即每条入射边都是出边。

要记住的另一件事是图表 connectedness .从任何其他顶点到达任何顶点并不总是可能的。因此，在实现此类算法时值得牢记这一点。

---

好的数据结构是好的算法的关键。如果你想在有向图中对事物进行排序，最好的办法是创建一个有向图数据结构，它本身将涉及创建一个 Node 数据结构和一个 Edge 数据结构体。我建议查找 adjacency lists .一旦你有了这样的数据结构，就可以运行breadth first search了。在图表上，您将得到拓扑优先级作为一个简洁的结果。

在实现邻接表时，您仍然需要将所有元素存储在一个地方。链表通常不是这样做的最佳方式，因为插入一个链表需要恒定的时间(假设对数据进行排序)，搜索一个链表需要线性时间。那是次优的方式。作为@David RF建议，Red-Black trees和 AVL trees将是要走的路。但是，我不会从这个优化开始。只要你有一个完善的工作算法，你总是可以改进你的存储数据结构。毕竟，链表和搜索树的接口(interface)是一样的。

---

如果您使用正确的算法，该算法可以很快。我在实践中没有处理过拓扑排序，所以我不知道每一个复杂的问题和每一个边缘情况。但!如果您使用传统的节点-边缘数据结构(请注意，边缘可以在节点内隐式定义)通过广度优先搜索来执行此操作，则您的搜索本身应该使用广度优先搜索花费线性时间。

我已经通读了您的算法，但我不得不承认我不太理解您关于大列表和小列表的概念。模棱两可的名字并没有真正的帮助。也许它用一个隐藏在某处的小错误来完成工作，但它不太可读。也许其他人可以对您当前的实现发表评论。