列表，元组和数组作为数据结构之间有什么区别? [英] What is the difference between a list, a tuple and an array as data structures?

问题描述

在这里，我不是在谈论一种特定的编程语言.我想知道这些东西之间以及不同的数据结构之间有什么区别.我认为列表基本上应该是可调整大小的，而数组则不能，但是我不确定.

Here I'm not talking about a particular programming language. I would like to know what is the difference between these things as between different data structures. I assume lists are basically supposed to be resizable whereas arrays are not, but I'm not sure.

推荐答案

谈论数组"和列表"由于抽象数据类型没有引用任何特定的实现，可能会造成一些混乱，因为这两种定义不是很好.

Talking about "arrays" and "lists" as abstract data types without referring to any particular implementation can be a bit confusing, because those two are not very well defined.

两个Wikipedia页面列表(抽象数据类型)和数组数据类型使得这种歧义有些明显，带有不确定的陈述，例如列表数据结构的实现可以提供以下一些操作:.

The two Wikipedia pages List (abstract data type) and Array data type make this ambiguity somewhat evident, with uncertain statements such as "Implementation of the list data structure may provide some of the following operations:".

在许多语言中，有一个名为 list 的类型和一个名为 array 的类型，它们具有更好的定义含义.

In many languages, there is a type called list and a type called array and they have some better defined meaning.

这是一个非常笼统的摘要.

Here is a very general summary.

列表:

• 一个列表是线性的，它是元素的有序序列；
• 您可以访问列表的第一个元素；
• 您可以向列表中添加新元素；
• 您可以从第一个元素开始一个接一个地访问列表的所有元素.最后的操作或者通过任意访问"完成.(访问元素为 l [0]，l [1]，l [2] 等)或使用两个称为"head"的操作来访问和"tail"，其中 head(l)返回 l 的第一个元素，而 tail(l)返回通过丢弃第一个元素.

• a list is linear, it is an ordered sequence of elements;
• you can access the first element of a list;
• you can add a new element to a list;
• you can access all elements of the list one after the other, starting from the first element. That last operation is done either with "arbitrary access" (accessing elements as l[0], l[1], l[2], etc.) or with two operations called "head" and "tail", where head(l) returns the first element of l and tail(l) returns the sublist obtained by discarding the first element.

在我看来，四个元素的列表如下所示:

In my mind, a list of four elements looks like this:

-> 3 -> 7 -> 12 -> 9

数组:

数组提供了任意访问"功能.使用索引(将元素作为 a [something] 访问)；
• 有时索引限制为0到数组长度之间的整数；有时索引可以是任何东西；
• 您可以轻松地修改要访问的元素，但是不必添加新元素.

• an array provides "arbitrary access" using indices (accessing elements as a[something]);
• sometimes the index is restricted to integers between 0 and the length of the array; sometimes the index can be anything and everything;
• you can easily modify elements that you access, but you cannot necessarily add new elements.

在大多数语言中，允许将任何内容用作索引的数组通常称为 map 或 dict ，其中 array 严格指代到由整数索引的线性结构；但是在某些语言中(例如PHP)，它仍然称为数组.

An array which allows anything to be used as index is usually called a map or a dict in most languages, where array refers strictly to linear structures indexed by integers; but in a few languages, for instance PHP, it is still called an array.

在我看来，由四个元素组成的数组如下所示:

In my mind, an array of four elements looks like this:

+--+--+--+--+
| 0| 1| 2| 3|
+--+--+--+--+
| 3| 7|12| 9|
+--+--+--+--+

故事:

• 线性，有序的元素序列；
• 通常可以包含不同类型的元素，而在大多数语言中，列表中的所有元素必须具有相同的类型；
• 通常无法添加/删除元素
在强类型语言(例如Haskell或OCaml)中，
• 元组的类型由其长度和其中使用的类型的枚举给出，例如，元组(3，7，12.0，"; 9)具有类型(int，int，float，string)，并且返回特定类型的元组的函数不能突然返回其他类型的元组.

• a linear, ordered sequence of elements;
• usually can contain elements of different types, whereas in most languages, all the elements in a list must have the same type;
• usually cannot add/remove elements
• in strongly-typed languages, such as Haskell or OCaml, the type of a tuple is given by its length and the enumeration of the types used in it, for instance the tuple (3, 7, 12.0, "9") has type (int, int, float, string), and a function returning a specific type of tuple cannot suddenly return a tuple of a different type.

强类型语言中的词组有时被称为产品类型".类似于数学中的笛卡尔积，并且与C中的 struct 非常接近.弱类型语言的元组与列表非常接近.

Tuples in strongly-typed languages are sometimes called "product types" by analogy with the Cartesian product in mathematics, and are very close to struct in C. Tuples in weakly-typed languages are very close to lists.

这篇关于列表，元组和数组作为数据结构之间有什么区别?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！