人们会想到简单的代码
llist1.Last.Next = llist2.First;
llist2.First.Previous = llist1.Last;
可行,但显然在C#的LinkedList,First,Last中,它们的属性只有Get.
我能想到的另一种方法是
llist1.AddLast(llist2.First);
但是,这也不起作用 - 它失败了,因为llist2的第一个节点已经在链表中.
这是否意味着我必须有一个循环,手动AddLast的llist2的每个节点到llist1？这不是打败链表的效率????
C++中是否有链接列表,我可以#include？或者如果我想使用它,我是否需要创建自己的？
这似乎正在回答正确的答案,但我不确定这是否真的是最好的方法.好像我正在访问前n个节点太多次了.有什么建议？请注意,我必须使用单链表进行此操作.
Node *findNodeFromLast( Node *head, int n )
{
Node *currentNode;
Node *behindCurrent;
currentNode = head;
for( int i = 0; i < n; i++ ) {
if( currentNode->next ) {
currentNode = currentNode->next;
} else {
return NULL;
}
}
behindCurrent = head;
while( currentNode->next ) {
currentNode = currentNode->next;
behindCurrent = behindCurrent->next;
}
return behindCurrent;
}
如何获取LinkedList实例的第n个元素？是否有内置方式或者我可能需要介绍我自己的实现？例如扩展方法？
谢谢
数组上的Mergesort的空间复杂度为O(n),而链表上的mergesort的空间复杂度为O(log(n)),此处记录
我相信我了解数组的情况,因为在合并两个子数组时我们需要辅助存储.但是链接列表合并排序不会合并两个子链接列表到位吗？我认为这会产生空间复杂度O(1)来创建一个新头.
合并(无辅助存储):
public Node merge(Node a, Node b) {
Node dummyHead, curr; dummyHead = new Node(); curr = dummyHead;
while(a !=null && b!= null) {
if(a.info <= b.info) { curr.next = a; a = a.next; }
else { curr.next = b; b = b.next; }
curr = curr.next;
}
curr.next = (a == null) ? b : a;
return dummyHead.next;
}
解释会很棒.
我很好奇,首先,为什么std::list并将std::forward_list排序函数作为成员函数包含在内,与其他标准库容器不同.但对我来说更有趣的是,CPPReference和CPlusPlus都声称这种排序是在O(n log n)时间内完成的.
我甚至无法想象如何在没有随机访问元素的情况下对容器进行排序.所以我把测试组合起来,forward_list尽可能地使它变得困难.
#include <chrono>
#include <cstdint>
#include <deque>
#include <forward_list>
#include <iostream>
#include <random>
using std::endl;
using namespace std::chrono;
typedef nanoseconds::rep length_of_time;
constexpr int TEST_SIZE = 25000;
class Stopwatch
{
public:
void start_timing();
void end_timing();
length_of_time get_elapsed_time() const;
private:
time_point<high_resolution_clock> start;
time_point<high_resolution_clock> end;
length_of_time elapsed_time = 0;
};
void Stopwatch::start_timing()
{
start = high_resolution_clock::now();
}
void Stopwatch::end_timing()
{
end = high_resolution_clock::now();
auto elapsed = end - …我的问题很简单,可以使用C++,实现链接列表数据结构而不使用指针(下一个节点)吗？为了进一步限定我的问题,我的意思是可以只使用类实例创建一个Linked-List数据结构.
常见的节点定义可能如下:
template<typename T>
struct node
{
T t;
node<T>* next;
node<T>* prev;
};
我知道std::list等等,我只是想知道它是否可能 - 如果是这样的话怎么样？代码示例将不胜感激.
更多说明:
Haskell的默认String实现在速度和内存方面都不高效这一事实是众所周知的.据我所知[] lists,通常在Haskell中实现单链接列表和大多数小/简单数据类型(例如Int)它似乎不是一个非常好的主意,但因为String它似乎完全矫枉过正.关于此事的一些意见包括:
在像这样的简单基准测试中,即使用Python等解释语言编写的程序也可以胜过使用String一个数量级的Haskell代码.
由于String只是[Char],这是Char的链接列表,这意味着字符串的引用局部性较差,并且再次意味着字符串在内存中相当大,至少它是N*(21bits + Mbits)其中N是字符串的长度,M是指针的大小(...).字符串不太可能被编译器优化为循环等.
我知道Haskell的ByteStrings(和Arrays)有几种不同的风格,并且它们可以很好地完成工作,但我希望默认实现是最有效的.
TL; DR:为什么Haskell的默认String实现是单链表,即使它非常低效并且很少用于真实世界的应用程序(除了非常简单的应用程序)？有历史原因吗？实施起来更容易吗？
Idris在矢量引擎下做了什么样的优化吗？因为从它的外观来看,Idris向量只是一个已知大小的链表(在编译时已知).事实上,一般来说,你似乎可以表达以下等价(我在语法上有点猜测):
Vector : Nat -> Type -> Type
Vector n t = (l: List t ** length l = n)
因此,虽然这在防止范围误差方面很好,但是矢量的真正优势(在该术语的传统用法中)是在性能方面; 特别是O(1)随机访问.似乎idris向量不支持这个(你如何编写索引函数来获得这种性能？).
Nat在重新配置Vectors 之下没有任何巫术(如果发生的那样),Idris中是否存在随机访问数据类型？