Список (информатика) - История изменений

Patarakin: /* Списки в языках программирования */

2022-10-21T09:59:26Z

Списки в языках программирования

← Предыдущая версия		Версия от 12:59, 21 октября 2022
Строка 45:		Строка 45:
	Списки в функциональных языках являются фундаментальной структурой. Большинство функциональных языков имеет встроенные средства для работы со списками вроде получения длины списка, головы (первый элемент списка), хвоста (часть списка, идущая за первым элементом), применения функции к каждому элементу списка ([[Map (программирование)\|Map]]), [[свертка списка\|свертки списка]] и пр.		Списки в функциональных языках являются фундаментальной структурой. Большинство функциональных языков имеет встроенные средства для работы со списками вроде получения длины списка, головы (первый элемент списка), хвоста (часть списка, идущая за первым элементом), применения функции к каждому элементу списка ([[Map (программирование)\|Map]]), [[свертка списка\|свертки списка]] и пр.


			==== Lists in [[Snap!]] ====

			[[Файл:List commands eng.png\|400px]] [[Файл:List commands.png\|400px]]

			----
	[[Категория:Структуры данных]]		[[Категория:Структуры данных]]
	[[Категория:Понятие]]		[[Категория:Понятие]]

Patarakin в 08:38, 21 октября 2022

2022-10-21T08:38:09Z

← Предыдущая версия		Версия от 11:38, 21 октября 2022
Строка 4:		Строка 4:
	\|Clarifying_video=https://www.youtube.com/watch?v=KTemYEzAQZQ		\|Clarifying_video=https://www.youtube.com/watch?v=KTemYEzAQZQ
	\|similar_concepts=Список		\|similar_concepts=Список
			\|Environment=Snap!
	}}		}}
	Это [[абстрактный тип данных]], представляющий собой упорядоченный набор [[Значение переменной\|значений]], в котором некоторое значение может встречаться более одного раза.		Это [[абстрактный тип данных]], представляющий собой упорядоченный набор [[Значение переменной\|значений]], в котором некоторое значение может встречаться более одного раза.

Patarakin в 08:36, 21 октября 2022

2022-10-21T08:36:13Z

← Предыдущая версия		Версия от 11:36, 21 октября 2022
Строка 1:		Строка 1:
			{{Понятие
			\|Description=Абстрактный тип данных, представляющий собой упорядоченный набор значений, в котором некоторое значение может встречаться более одного раза.
			\|Field_of_knowledge=Информатика
			\|Clarifying_video=https://www.youtube.com/watch?v=KTemYEzAQZQ
			\|similar_concepts=Список
			}}
	Это [[абстрактный тип данных]], представляющий собой упорядоченный набор [[Значение переменной\|значений]], в котором некоторое значение может встречаться более одного раза.		Это [[абстрактный тип данных]], представляющий собой упорядоченный набор [[Значение переменной\|значений]], в котором некоторое значение может встречаться более одного раза.
	Экземпляры значений, находящихся в списке, называются '''элементами''' списка либо; если значение встречается несколько раз, каждое вхождение считается отдельным элементом.		Экземпляры значений, находящихся в списке, называются '''элементами''' списка либо; если значение встречается несколько раз, каждое вхождение считается отдельным элементом.

Patarakin в 08:33, 21 октября 2022

2022-10-21T08:33:42Z

← Предыдущая версия		Версия от 11:33, 21 октября 2022
Строка 39:		Строка 39:

	[[Категория:Структуры данных]]		[[Категория:Структуры данных]]
			[[Категория:Понятие]]

Patarakin в 09:07, 19 октября 2022

2022-10-19T09:07:52Z

@@ Строка 1: / Строка 1: @@
-{{Значения|Список}}
+Это [[абстрактный тип данных]], представляющий собой упорядоченный набор [[Значение переменной|значений]], в котором некоторое значение может встречаться более одного раза.
-В [[информатика|информатике]], '''спи́сок''' ({{lang-en|list}}) — это [[абстрактный тип данных]], представляющий собой упорядоченный набор [[Значение переменной|значений]], в котором некоторое значение может встречаться более одного раза. Экземпляр списка является компьютерной реализацией [[Математика|математического]] понятия конечной [[Последовательность|последовательности]].
+Экземпляры значений, находящихся в списке, называются '''элементами''' списка  либо; если значение встречается несколько раз, каждое вхождение считается отдельным элементом.
-Экземпляры значений, находящихся в списке, называются '''элементами''' списка ({{lang-en|item, entry}} либо {{lang-en2|element}}); если значение встречается несколько раз, каждое вхождение считается отдельным элементом.
 Термином ''список'' также называется несколько конкретных [[Структура данных|структур данных]], применяющихся при реализации абстрактных списков, особенно [[Связный список|связных списков]].
@@ Строка 39: / Строка 38: @@
 Списки в функциональных языках являются фундаментальной структурой. Большинство функциональных языков имеет встроенные средства для работы со списками вроде получения длины списка, головы (первый элемент списка), хвоста (часть списка, идущая за первым элементом), применения функции к каждому элементу списка ([[Map (программирование)|Map]]), [[свертка списка|свертки списка]] и пр.
 [[Категория:Структуры данных]]

Patarakin: 1 версия импортирована

2022-10-19T07:30:53Z

1 версия импортирована

← Предыдущая версия	Версия от 10:30, 19 октября 2022
(нет различий)

ru_wikipedia>Alhadis: PNG -> SVG

2022-03-04T15:56:00Z

PNG -> SVG

Новая страница

{{Значения|Список}}
В [[информатика|информатике]], '''спи́сок''' ({{lang-en|list}}) — это [[абстрактный тип данных]], представляющий собой упорядоченный набор [[Значение переменной|значений]], в котором некоторое значение может встречаться более одного раза. Экземпляр списка является компьютерной реализацией [[Математика|математического]] понятия конечной [[Последовательность|последовательности]].
Экземпляры значений, находящихся в списке, называются '''элементами''' списка ({{lang-en|item, entry}} либо {{lang-en2|element}}); если значение встречается несколько раз, каждое вхождение считается отдельным элементом.
[[Файл:Singly-linked-list.svg|thumb|right|Структура односвязного списка из трёх элементов]]

Термином ''список'' также называется несколько конкретных [[Структура данных|структур данных]], применяющихся при реализации абстрактных списков, особенно [[Связный список|связных списков]].

== Определение ==
При помощи нотации метода [[синтаксически-ориентированное конструирование|синтаксически-ориентированного конструирования]] [[Хоар, Чарльз Энтони Ричард|Ч. Хоара]] определение списка можно записать следующим образом:

: <math>List(A) = NIL + (A \times List(A))</math>
: <math>prefix = \text{constructor}</math> <math>List(A)</math>
: <math>head, tail = \text{selectors}</math> <math>List(A)</math>
: <math>null, nonnull = \text{predicates}</math> <math>List(A)</math>
: <math>NIL, nonNIL = \text{parts}</math> <math>List(A)</math>

Первая строка данного определения обозначает, что список элементов типа <math>A</math> (говорят: «список над <math>A</math>») представляет собой [[размеченное объединение]] пустого списка и [[декартово произведение|декартова произведения]] атома типа <math>A</math> со списком над <math>A</math>. Для создания списков используются два [[конструктор данных|конструктора]] (вторая строка определения), первый из которых создаёт пустой список, а второй — непустой соответственно. Вполне понятно, что второй конструктор получает на вход в качестве параметров некоторый атом и список, а возвращает список, первым элементом которого является исходный атом, а остальными — элементы исходного списка. То есть получается префиксация атома к списку, с чем и связано такое наименование конструктора. Пустой список <math>[]</math> не является атомом, а потому не может префиксироваться. С другой стороны, пустой список является нулевым элементом для конструирования списков, поэтому любой список содержит в самом своём конце пустой список — с него начинается конструирование.

Третья строка определяет [[селектор]]ы для списка, то есть операции для доступа к элементам внутри списка. Селектор <math>head</math> получает на вход список и возвращает первый элемент этого списка, то есть типом результата является тип <math>A</math>. Этот селектор не может получить на вход пустой список — в этом случае результат операции неопределён. Селектор <math>tail</math> возвращает список, полученный из входного в результате отсечения его головы (первого элемента). Этот селектор также не может принимать на вход пустой список, так как в этом случае результат операции неопределён. При помощи этих двух операций можно достать из списка любой элемент. Например, чтобы получить третий элемент списка (если он имеется),
необходимо последовательно два раза применить селектор <math>tail</math>, после чего применить селектор <math>head</math>. Другими словами, для получения элемента списка, который находится на позиции <math>n</math> (начиная с <math>0</math> для первого элемента, как это принято в программировании), необходимо <math>n</math> раз применить селектор <math>tail</math>,
после чего применить селектор <math>head</math>.

Четвёртая строка определения описывает [[предикат]]ы для списка, то есть функции, возвращающие булевское значение в зависимости от некоторых условий. Первый предикат возвращает значение <math>true</math> в случае, если заданный список пуст. Второй предикат действует наоборот. Наконец, пятая строка описывает части списка, которые, как уже сказано, представляют собой пустой и непустой списки.

== Свойства ==
У определённой таким образом структуры данных имеются некоторые свойства:

* '''Размер списка''' — количество элементов в нём, исключая последний «нулевой» элемент, являющийся по определению пустым списком.
* '''Тип элементов''' — тот самый тип <math>A</math>, над которым строится список; все элементы в списке должны быть этого типа.
* '''Отсортированность''' — список может быть отсортирован в соответствии с некоторыми критериями сортировки (например, по возрастанию целочисленных значений, если список состоит из целых чисел).
* '''Возможности доступа''' — некоторые списки в зависимости от реализации могут обеспечивать программиста селекторами для доступа непосредственно к заданному по номеру элементу.
* '''Сравниваемость''' — списки можно сравнивать друг с другом на соответствие, причём в зависимости от реализации операция сравнения списков может использовать разные технологии.

Списки используются для хранения наборов однотипных элементов. Такие элементы могут быть отсортированы для использования в функциях поиска или функциях для быстрой вставки новых элементов в список.

== Списки в языках программирования ==

=== [[Функциональное программирование|Функциональные языки]] ===
Списки в функциональных языках являются фундаментальной структурой. Большинство функциональных языков имеет встроенные средства для работы со списками вроде получения длины списка, головы (первый элемент списка), хвоста (часть списка, идущая за первым элементом), применения функции к каждому элементу списка ([[Map (программирование)|Map]]), [[свертка списка|свертки списка]] и пр.

==== Язык [[Haskell]] ====

==== Язык [[Lisp]] ====

=== [[Императивное программирование|Императивные языки]] ===

== См. также ==
* [[XOR-связный список]]
* [[Линейный список]]
* [[Развёрнутый связный список]]
* [[Связный список]]
* [[Список с пропусками]]

{{rq|sources|refless}}
{{Типы данных}}
{{Структуры данных}}

[[Категория:Информатика]]
[[Категория:Структуры данных]]
[[Категория:Статьи о списках]]
[[Категория:Типы данных]]
[[Категория:Составные типы данных]]