树：链表VS阵列（效率） [英] Trees: Linked Lists vs Arrays (Efficiency)

问题描述

这是我遇到了麻烦措辞的答案赋值问题。

This is an assignment question that I am having trouble wording an answer to.

假设一个树可以具有多至k每个节点的孩子。令v为每个节点的孩子的平均数。对于诉什么值（s）是更有效的（在使用的空间术语）来存储子在阵列中的一个链表与存储节点？为什么？

"Suppose a tree may have up to k children per node. Let v be the average number of children per node. For what value(s) of v is it more efficient (in terms of space used) to store the child nodes in a linked list versus storage in an array? Why?"

我相信我能回答为什么？或多或少地用简单的英语 - 这将是更有效地使用链表，因为而不是一堆空节点（数组中，即空的索引，如果你的平均比最大更低）占用内存只ALLOC空间在链表的一个节点时，你实际上填补的值。

I believe I can answer the "why?" more or less in plain English -- it will be more efficient to use the linked list because rather than having a bunch of empty nodes (ie empty indexes in the array if your average is lower than the max) taking up memory you only alloc space for a node in a linked list when you're actually filling in a value.

所以，如果你有一个平均，当你最大200 6个孩子，当树被创建，但阵列将创建为所有200名儿童的每个节点空间的链接列表将只用于节点ALLOC空间如所须。所以，用链表，使用的空间将是大约的平均值（？）;与阵列，隔开使用将是最大

So if you've got an average of 6 children when your maximum is 200, the array will be creating space for all 200 children of each node when the tree is created, but the linked list will only alloc space for the nodes as needed. So, with the linked list, space used will be approximately(?) the average; with the array, spaced used will be the max.

...我不认为它何时会永远是更有效地使用数组。这是一个很难回答的问题？我必须考虑到的阵列需要它的创建时，对节点的总数量限制的事实？

...I don't see when it would ever be more efficient to use the array. Is this a trick question? Do I have to take into account the fact that the array needs to have a limit on total number of nodes when it's created?

推荐答案

对于许多常用的语言，阵列将需要分配存储空间的 K 的内存地址（数据）。一个单向链表将要求每个节点（数据＆安培;下一个）2个地址。一个双向链表将要求每个节点3的位置。

For many commonly used languages, the array will require allocating storage k memory addresses (of the data). A singly-linked list will require 2 addresses per node (data & next). A doubly-linked list would require 3 addresses per node.

让的 N 的是一个特定节点的子节点的实际数量的 A 的：

Let n be the actual number of children of a particular node A:

• 的阵列使用的 K 的内存地址


• 的单链表使用2 N 地址


• 的双向链表使用3 N 地址

• The array uses k memory addresses
• The singly-linked list uses 2n addresses
• The doubly-linked list uses 3n addresses

该值的 K 的允许你以确定是否2 名词或3 名词的地址将平均收益或损失相比，简单地贮存在阵列中的地址。

The value k allows you to determine if 2n or 3n addresses will average to a gain or loss compared to simply storing the addresses in an array.

这篇关于树：链表VS阵列（效率）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！