Структура данных - История изменений

Patarakin в 16:00, 9 января 2023

2023-01-09T16:00:25Z

← Предыдущая версия		Версия от 19:00, 9 января 2023
Строка 1:		Строка 1:
	{{Понятие		{{Понятие
	\|Description=Структура ~~данных—~~ программная единица, позволяющая хранить и обрабатывать однотипные и/или логически связанные данные. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс.		\|Description=Структура данных (data structure) — это способ хранения и организации данных, облегчающий доступ к этим данным и их модификацию. Структура данных — программная единица, позволяющая хранить и обрабатывать однотипные и/или логически связанные данные. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс.
	\|Field_of_knowledge=Информатика		\|Field_of_knowledge=Информатика
	\|similar_concepts=Данные, Датасет		\|similar_concepts=Данные, Датасет

Patarakin в 10:51, 19 октября 2022

2022-10-19T10:51:34Z

← Предыдущая версия		Версия от 13:51, 19 октября 2022
Строка 1:		Строка 1:
			{{Понятие
			\|Description=Структура данных— программная единица, позволяющая хранить и обрабатывать однотипные и/или логически связанные данные. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс.
			\|Field_of_knowledge=Информатика
			\|similar_concepts=Данные, Датасет
			\|Environment=Snap!, Perl, Лого
			}}
	'''Структура данных'''— [[программная единица]], позволяющая хранить и обрабатывать однотипные и/или логически связанные [[данные (вычислительная техника)\|данные]]. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс.		'''Структура данных'''— [[программная единица]], позволяющая хранить и обрабатывать однотипные и/или логически связанные [[данные (вычислительная техника)\|данные]]. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс.

Patarakin в 10:50, 19 октября 2022

2022-10-19T10:50:00Z

← Предыдущая версия		Версия от 13:50, 19 октября 2022
Строка 27:		Строка 27:

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

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

2022-10-19T07:41:28Z

← Предыдущая версия		Версия от 10:41, 19 октября 2022
Строка 5:		Строка 5:
	* Реализация какого-либо абстрактного типа данных;		* Реализация какого-либо абстрактного типа данных;
	* Экземпляр типа данных, например, конкретный [[список (структура данных)\|список]];		* Экземпляр типа данных, например, конкретный [[список (структура данных)\|список]];
	* В контексте функционального программирования — уникальная единица ~~({{lang-en\|unique identity}})~~, сохраняющаяся при изменениях. О ней неформально говорят как об одной структуре данных, несмотря на возможное наличие различных версий.		* В контексте функционального программирования — уникальная единица, сохраняющаяся при изменениях. О ней неформально говорят как об одной структуре данных, несмотря на возможное наличие различных версий.

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

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

2022-10-19T07:40:20Z

@@ Строка 1: / Строка 1: @@
-[[Файл:binary tree.svg|thumb|192px|[[Бинарное дерево]], простой пример ветвящейся связной структуры данных.]]
+'''Структура данных'''— [[программная единица]], позволяющая хранить и обрабатывать однотипные и/или логически связанные [[данные (вычислительная техника)|данные]]. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс.
-Термин «структура данных» может иметь несколько близких, но тем не менее различных значений{{sfn|Okasaki|1998|pp=3-4}}:
+Термин «структура данных» может иметь несколько близких, но тем не менее различных значений:
 * [[Абстрактный тип данных]];
 * Реализация какого-либо абстрактного типа данных;
@@ Строка 14: / Строка 13: @@
 При разработке программного обеспечения сложность реализации и качество работы программ существенно зависят от правильного выбора структур данных. Это понимание дало начало формальным методам разработки и языкам программирования, в которых именно структуры данных, а не алгоритмы, ставятся во главу архитектуры программного средства. Большая часть таких языков обладает определённым типом [[Модульность (программирование)|модульности]], позволяющим структурам данных безопасно [[повторное использование кода|переиспользоваться]] в различных приложениях. [[Объектно-ориентированный язык программирования|Объектно-ориентированные языки]], такие как [[Java]], [[C Sharp|C#]] и [[C++]], являются примерами такого подхода.
-[[File:Python 3. The standard type hierarchy.png|thumb]]
+https://upload.wikimedia.org/wikipedia/commons/1/10/Python_3._The_standard_type_hierarchy.png
 Многие классические структуры данных представлены в стандартных библиотеках языков программирования или непосредственно встроены в языки программирования. Например, структура данных хеш-таблица встроена в языки программирования [[Lua]], [[Perl]], [[Python]], [[Ruby]], [[Tcl]] и др. Широко используется [[стандартная библиотека шаблонов]] (STL) языка C++.
@@ Строка 20: / Строка 20: @@
 == Сравнение структур данных в функциональном и императивном программировании ==
-Проектировать структуры данных для функциональных языков более сложно, чем для императивных, как минимум по двум причинам{{sfn|Okasaki|1998|pp=3-4}}:
+Проектировать структуры данных для функциональных языков более сложно, чем для императивных, как минимум по двум причинам:
 # Почти все структуры данных интенсивно используют [[присваивание]], которое в чисто функциональном стиле не используется;
-# Функциональные структуры данных являются более гибкими, и поэтому там, где в императивном программировании старая версия теряется, просто заменяясь новой, в функциональном она автоматически продолжает существовать. Другими словами, в императивном программировании (если не принять особых мер, которые могут серьёзно усложнить программу) структуры данных являются '''''эфемерными''''' ({{lang-en|ephemeral}}), а в функциональных программах они как правило '''''постоянные''''' ({{lang-en|persistent}}).
+# Функциональные структуры данных являются более гибкими, и поэтому там, где в императивном программировании старая версия теряется, просто заменяясь новой, в функциональном она автоматически продолжает существовать. Другими словами, в императивном программировании (если не принять особых мер, которые могут серьёзно усложнить программу) структуры данных являются '''''эфемерными''''', а в функциональных программах они как правило '''''постоянные'''''.
 [[Категория:Структуры данных| ]]

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

2022-10-19T07:30:50Z

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

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

ru_wikipedia>Gretanit: переделал ошибочные части.

2022-08-10T13:30:26Z

переделал ошибочные части.

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

[[Файл:binary tree.svg|thumb|192px|[[Бинарное дерево]], простой пример ветвящейся связной структуры данных.]]
'''Структура данных''' ({{lang-en|data structure}}) — [[программная единица]], позволяющая хранить и обрабатывать однотипные и/или логически связанные [[данные (вычислительная техника)|данные]]. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс.

Термин «структура данных» может иметь несколько близких, но тем не менее различных значений{{sfn|Okasaki|1998|pp=3-4}}:
* [[Абстрактный тип данных]];
* Реализация какого-либо абстрактного типа данных;
* Экземпляр типа данных, например, конкретный [[список (структура данных)|список]];
* В контексте функционального программирования — уникальная единица ({{lang-en|unique identity}}), сохраняющаяся при изменениях. О ней неформально говорят как об одной структуре данных, несмотря на возможное наличие различных версий.

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

Различные виды структур данных подходят для различных приложений; некоторые из них имеют узкую специализацию для определённых задач. Например, [[B-дерево|B-деревья]] обычно подходят для создания [[база данных|баз данных]], в то время как [[Хеш-таблица|хеш-таблицы]] используются повсеместно для создания различного рода словарей, например, для отображения доменных имён в [[IP-адрес|интернет-адресах компьютеров]].

При разработке программного обеспечения сложность реализации и качество работы программ существенно зависят от правильного выбора структур данных. Это понимание дало начало формальным методам разработки и языкам программирования, в которых именно структуры данных, а не алгоритмы, ставятся во главу архитектуры программного средства. Большая часть таких языков обладает определённым типом [[Модульность (программирование)|модульности]], позволяющим структурам данных безопасно [[повторное использование кода|переиспользоваться]] в различных приложениях. [[Объектно-ориентированный язык программирования|Объектно-ориентированные языки]], такие как [[Java]], [[C Sharp|C#]] и [[C++]], являются примерами такого подхода.

[[File:Python 3. The standard type hierarchy.png|thumb]]
Многие классические структуры данных представлены в стандартных библиотеках языков программирования или непосредственно встроены в языки программирования. Например, структура данных хеш-таблица встроена в языки программирования [[Lua]], [[Perl]], [[Python]], [[Ruby]], [[Tcl]] и др. Широко используется [[стандартная библиотека шаблонов]] (STL) языка C++.

Фундаментальными строительными блоками для большей части структур данных являются [[Массив (программирование)|массивы]], [[Запись (тип данных)|записи]] (<code>struct</code> в [[Си (язык программирования)|Си]] и <code>record</code> в [[Паскаль (язык программирования)|Паскале]]), [[размеченное объединение|размеченные объединения]] (<code>union</code> в Си) и [[Ссылка (программирование)|ссылки]]. Например, [[двусвязный список]] может быть построен с помощью записей и ссылок, где каждая запись (узел) будет хранить данные и ссылки на «левый» и «правый» узлы.

== Сравнение структур данных в функциональном и императивном программировании ==
Проектировать структуры данных для функциональных языков более сложно, чем для императивных, как минимум по двум причинам{{sfn|Okasaki|1998|pp=3-4}}:
# Почти все структуры данных интенсивно используют [[присваивание]], которое в чисто функциональном стиле не используется;
# Функциональные структуры данных являются более гибкими, и поэтому там, где в императивном программировании старая версия теряется, просто заменяясь новой, в функциональном она автоматически продолжает существовать. Другими словами, в императивном программировании (если не принять особых мер, которые могут серьёзно усложнить программу) структуры данных являются '''''эфемерными''''' ({{lang-en|ephemeral}}), а в функциональных программах они как правило '''''постоянные''''' ({{lang-en|persistent}}).

== Примечания ==
{{примечания}}

== Литература ==
* {{книга
|автор = Альфред В. Ахо, [[Джон Хопкрофт]], Джеффри Д. Ульман.
|заглавие = Структуры данных и алгоритмы
|оригинал = Data Structures and Algorithms
|место = М. |издательство = [[Вильямс (издательство)|Вильямс]]
|год = 2000
|страниц = 384
|isbn = 0-201-00023-7
|ref=Ахо, Ульман
}}
* {{книга
|автор = Майкл Мейн, Уолтер Савитч.
|заглавие = Структуры данных и другие объекты в C++
|оригинал = Data Structures and Other Objects Using C++
|издание = 2-е изд
|место = М. |издательство = [[Вильямс (издательство)|Вильямс]]
|год = 2002
|страниц = 832
|isbn = 0-201-70297-5
|ref = Мейн, Савитч
}}
* {{книга
|автор = Chris Okasaki
|заглавие = Purely Functional Data Structures
|издательство = Cambridge University Press
|год = 1998
|страниц = 232
|isbn = 978-0521663502
|ref=Okasaki
}}

== Ссылки ==
* [http://algolist.manual.ru/ds/ Структуры данных и хеширование]
{{rq|refless|topic=ИТ}}

{{Структуры данных}}
{{Типы данных}}

__NOTOC__

[[Категория:Структуры данных| ]]
[[Категория:Вычислительная техника]]