作为学习练习,我刚刚尝试实现自己的“归并排序”算法。我在 std::list 上做了这个,它显然已经内置了函数 sort() 和 merge()。但是,我正计划将它移到我自己制作的链表中,所以实现不是特别重要。
问题在于 std::list 没有访问随机节点的功能,只能访问前/后和单步执行。我最初计划以某种方式对该列表执行简单的二进制搜索,并通过几个步骤找到我的答案。
事实上,std::list 中已经内置了用于执行此类排序的函数,这让我相信有一种同样简单的方法可以按照我想要的方式访问列表。
无论如何,提前感谢您的帮助!
最佳答案
链表的工作方式是一次一个地遍历列表中的项目。根据定义,无法访问列表中的“随机”元素。您提到的排序方法实际上通过一次一个地遍历每个节点并将项目放置在正确的位置来创建一个全新的列表。
如果您想随机访问数据,则需要以不同方式存储数据。也许是您要存储的元素的数组。
有关链表的更多信息:http://en.wikipedia.org/wiki/Linked_list
关于algorithm - 排序双链表的搜索算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2452185/