迭代和遍历有什么区别?

2024-05-22

过去几周我一直在学习迭代器。我仍然不明白迭代链接列表和遍历链接列表之间的主要区别。我知道遍历意味着遍历(访问每个元素)链接列表,并且在迭代时基本上做同样的事情,但是有什么不同,为什么不能遍历所有内容(标准库数据结构)?


“遍历”只是意味着遍历数据结构的(全部或部分)元素。

Historically, “iteration” in computer science is a special form of recursion for which no additional stack space is needed1 – in other words, tail recursion http://en.wikipedia.org/wiki/Tail_recursion. This form is computationally exactly equivalent to what we now colloquially know as “iteration”, namely a finite loop (such as a for loop with a fixed lower and upper bound).

Now this makes iteration especially well suited (compared to general recursion) for traversing linear data structures2. Note that it does not work for all containers (e.g. general graphs) because here you need to remember the already visited nodes (e.g. using depth-first search http://en.wikipedia.org/wiki/Depth-first_search, which is defined recursively in terms of adjacent nodes, rather than via the C++ concept of iterators).

正是在这种情况下,术语“迭代”在应用于容器的 C++ 中使用。

总之:并非每次遍历都是迭代,但每次迭代(在数据结构上)都是遍历。然而,值得注意的是,许多人没有做出这样的区分,而是互换使用这些术语。


1 In particular this is the usage of Gerald Sussman of SICP http://en.wikipedia.org/wiki/Structure_and_Interpretation_of_Computer_Programs fame.

2 But seemingly non-linear data structures such as trees can be linearised for the purpose of iteration by applying the right-hand rule (wall-following algorithm) http://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_follower and can thus be traversed without a stack.

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

迭代和遍历有什么区别? 的相关文章

随机推荐