在R中滚动您自己的链接列表/树？ [英] Roll Your Own Linked List/Tree in R?

问题描述

我正试图围绕R编程语言的基本概念，发现难以理解，因为R面向统计学而不是通用编程。我找不到类似于指针/引用的东西。您如何在R语言中实现链表，搜索树等？

注意：我明白，如果您实际滚动自己的参考数据R中的结构，可能有更好的方法来完成你想要完成的任务。然而，我相信一个答案将有助于我更好地理解语言的整体结构和概念。

编辑：关于Matt Shotwell的评论，这个问题的意义是我正在寻找在 R中干净地编写链表和树，而不是以C或其他语言编写的扩展名。作为一个扩展名，或者用解释器的奥秘细节进行破坏，就会破坏目的。

解决方案

R中的链表可以是表示为向量，通常为列表。您不需要编写特殊代码来引用下一个和前一个项目，因为R通过索引为您提供。

要向列表中添加一个新项目，只需跟踪其长度并分配给下一行。

  lst < -  list（）＃创建一个空（长度零）列表
 lst [[1]]<  -  1＃自动扩展lst 
 lst [[2]]<  -  2＃同上
 由于R处理内存的方式，对于长列表来说，这可能是无效的。如果可能，提前创建列表，并在其可用时分配其内容。
  lst < -  list（1， 2，3，4，5）＃5项目列表
 
 lst < -  vector（list，10000）＃10000 NULLs 
 lst [[1]] < 1 
 lst [[10000]]<  -  10000＃lst现在包含1，NULL，...，NULL，10000 
  
从列表中删除项目可以用负指标来完成。
  lst <列表（1，2，3，4，5）
 lst < -  lst [-2]＃现包含1，3，4，5 
  
树只是一个包含其他列表的列表。
  tree< ;列表（list（1，2），list（3，list（4，5）））
 
＃left child：list（1,2）
 tree [[1] ] 
 
＃right child 
 tree [[2]] 
 
＃右边孩子的右边孩子：list（4,5）
 tree [[ 2]] [[2]] 
  
默认情况下，没有内置的强制执行结构，例如，对于二进制t，每个节点只有两个孩子ree。通过S4课程可以获得更多结构化的方法，但这样做可以帮助您。
 
I'm trying to wrap my head around the basic concepts of the R programming language and am finding it difficult since R is geared towards statistics instead of general-purpose programming.  I can't find anything similar to pointers/references.  How would you implement a linked list, search tree, etc. within the R language?

Note:  I understand that if you're actually rolling your own self-referential data structures in R, there's probably a better way to accomplish what you're trying to accomplish.  However, I believe an answer will help me understand the overall structure and concepts of the language better.

Edit:  With regard to Matt Shotwell's comment, the point of this question is that I'm looking to write linked lists and trees cleanly, within R, not as an extension written in C or some other language.  Doing it as an extension or by mucking with arcane details of the interpreter defeats the purpose.
解决方案
A linked list in R can be represented as a vector, typically a list. You don't need to write special code to reference the next and previous items, because R does it for you via indexing.

To add a new item to the list, just keep track of its length and assign to the next in line.
lst <- list() # creates an empty (length zero) list
lst[[1]] <- 1 # automagically extends the lst
lst[[2]] <- 2 # ditto
This can be inefficient for long lists because of the way R handles memory. If possible, create the list in advance, and assign their contents as they become available.
lst <- list(1, 2, 3, 4, 5)    # a list of 5 items

lst <- vector("list", 10000)  # 10000 NULLs
lst[[1]] <- 1
lst[[10000]] <- 10000  # lst now contains 1, NULL, ..., NULL, 10000
Deleting an item from the list can be accomplished with negative indexes.
lst <- list(1, 2, 3, 4, 5)
lst <- lst[-2]  # now contains 1, 3, 4, 5
A tree is just a list containing other lists.
tree <- list(list(1, 2), list(3, list(4, 5)))

# left child: list(1, 2)
tree[[1]]

# right child
tree[[2]]

# right child of right child:list(4, 5)
tree[[2]][[2]]
By default there is no built-in enforcing of the structure, eg only two children per node for a binary tree. More structured approaches are available via S4 classes, but this will do the job in a pinch.

                        
这篇关于在R中滚动您自己的链接列表/树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！