Структура данных: различия между версиями
Материал из Поле цифровой дидактики
Patarakin (обсуждение | вклад) м (1 версия импортирована) |
Patarakin (обсуждение | вклад) |
||
| (не показаны 4 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
{{Понятие | |||
'''Структура данных''' | |Description=Структура данных (data structure) — это способ хранения и организации данных, облегчающий доступ к этим данным и их модификацию. Структура данных — программная единица, позволяющая хранить и обрабатывать однотипные и/или логически связанные данные. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс. | ||
|Field_of_knowledge=Информатика | |||
|similar_concepts=Данные, Датасет | |||
|Environment=Snap!, Perl, Лого | |||
}} | |||
'''Структура данных'''— [[программная единица]], позволяющая хранить и обрабатывать однотипные и/или логически связанные [[данные (вычислительная техника)|данные]]. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс. | |||
Термин «структура данных» может иметь несколько близких, но тем не менее различных значений | Термин «структура данных» может иметь несколько близких, но тем не менее различных значений: | ||
* [[Абстрактный тип данных]]; | * [[Абстрактный тип данных]]; | ||
* Реализация какого-либо абстрактного типа данных; | * Реализация какого-либо абстрактного типа данных; | ||
* Экземпляр типа данных, например, конкретный [[список (структура данных)|список]]; | * Экземпляр типа данных, например, конкретный [[список (структура данных)|список]]; | ||
* В контексте функционального программирования — уникальная единица | * В контексте функционального программирования — уникальная единица, сохраняющаяся при изменениях. О ней неформально говорят как об одной структуре данных, несмотря на возможное наличие различных версий. | ||
Структуры данных формируются с помощью [[Тип данных|типов данных]], [[Ссылка (программирование)|ссылок]] и операций над ними в выбранном [[язык программирования|языке программирования]]. | Структуры данных формируются с помощью [[Тип данных|типов данных]], [[Ссылка (программирование)|ссылок]] и операций над ними в выбранном [[язык программирования|языке программирования]]. | ||
| Строка 14: | Строка 19: | ||
При разработке программного обеспечения сложность реализации и качество работы программ существенно зависят от правильного выбора структур данных. Это понимание дало начало формальным методам разработки и языкам программирования, в которых именно структуры данных, а не алгоритмы, ставятся во главу архитектуры программного средства. Большая часть таких языков обладает определённым типом [[Модульность (программирование)|модульности]], позволяющим структурам данных безопасно [[повторное использование кода|переиспользоваться]] в различных приложениях. [[Объектно-ориентированный язык программирования|Объектно-ориентированные языки]], такие как [[Java]], [[C Sharp|C#]] и [[C++]], являются примерами такого подхода. | При разработке программного обеспечения сложность реализации и качество работы программ существенно зависят от правильного выбора структур данных. Это понимание дало начало формальным методам разработки и языкам программирования, в которых именно структуры данных, а не алгоритмы, ставятся во главу архитектуры программного средства. Большая часть таких языков обладает определённым типом [[Модульность (программирование)|модульности]], позволяющим структурам данных безопасно [[повторное использование кода|переиспользоваться]] в различных приложениях. [[Объектно-ориентированный язык программирования|Объектно-ориентированные языки]], такие как [[Java]], [[C Sharp|C#]] и [[C++]], являются примерами такого подхода. | ||
https://upload.wikimedia.org/wikipedia/commons/1/10/Python_3._The_standard_type_hierarchy.png | |||
Многие классические структуры данных представлены в стандартных библиотеках языков программирования или непосредственно встроены в языки программирования. Например, структура данных хеш-таблица встроена в языки программирования [[Lua]], [[Perl]], [[Python]], [[Ruby]], [[Tcl]] и др. Широко используется [[стандартная библиотека шаблонов]] (STL) языка C++. | Многие классические структуры данных представлены в стандартных библиотеках языков программирования или непосредственно встроены в языки программирования. Например, структура данных хеш-таблица встроена в языки программирования [[Lua]], [[Perl]], [[Python]], [[Ruby]], [[Tcl]] и др. Широко используется [[стандартная библиотека шаблонов]] (STL) языка C++. | ||
| Строка 20: | Строка 26: | ||
== Сравнение структур данных в функциональном и императивном программировании == | == Сравнение структур данных в функциональном и императивном программировании == | ||
Проектировать структуры данных для функциональных языков более сложно, чем для императивных, как минимум по двум причинам | Проектировать структуры данных для функциональных языков более сложно, чем для императивных, как минимум по двум причинам: | ||
# Почти все структуры данных интенсивно используют [[присваивание]], которое в чисто функциональном стиле не используется; | # Почти все структуры данных интенсивно используют [[присваивание]], которое в чисто функциональном стиле не используется; | ||
# Функциональные структуры данных являются более гибкими, и поэтому там, где в императивном программировании старая версия теряется, просто заменяясь новой, в функциональном она автоматически продолжает существовать. Другими словами, в императивном программировании (если не принять особых мер, которые могут серьёзно усложнить программу) структуры данных являются '''''эфемерными''''' | # Функциональные структуры данных являются более гибкими, и поэтому там, где в императивном программировании старая версия теряется, просто заменяясь новой, в функциональном она автоматически продолжает существовать. Другими словами, в императивном программировании (если не принять особых мер, которые могут серьёзно усложнить программу) структуры данных являются '''''эфемерными''''', а в функциональных программах они как правило '''''постоянные'''''. | ||
[[Категория:Структуры данных| ]] | [[Категория:Структуры данных| ]] | ||
[[Категория: | [[Категория:Понятие]] | ||
Текущая версия на 19:00, 9 января 2023
| Описание | Структура данных (data structure) — это способ хранения и организации данных, облегчающий доступ к этим данным и их модификацию. Структура данных — программная единица, позволяющая хранить и обрабатывать однотипные и/или логически связанные данные. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс. |
|---|---|
| Область знаний | Информатика |
| Авторы | |
| Поясняющее видео | |
| Близкие понятия | Данные, Датасет |
| Среды и средства для освоения понятия | Snap!, Perl, Лого |
Структура данных— программная единица, позволяющая хранить и обрабатывать однотипные и/или логически связанные данные. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс.
Термин «структура данных» может иметь несколько близких, но тем не менее различных значений:
- Абстрактный тип данных;
- Реализация какого-либо абстрактного типа данных;
- Экземпляр типа данных, например, конкретный список;
- В контексте функционального программирования — уникальная единица, сохраняющаяся при изменениях. О ней неформально говорят как об одной структуре данных, несмотря на возможное наличие различных версий.
Структуры данных формируются с помощью типов данных, ссылок и операций над ними в выбранном языке программирования.
Различные виды структур данных подходят для различных приложений; некоторые из них имеют узкую специализацию для определённых задач. Например, B-деревья обычно подходят для создания баз данных, в то время как хеш-таблицы используются повсеместно для создания различного рода словарей, например, для отображения доменных имён в интернет-адресах компьютеров.
При разработке программного обеспечения сложность реализации и качество работы программ существенно зависят от правильного выбора структур данных. Это понимание дало начало формальным методам разработки и языкам программирования, в которых именно структуры данных, а не алгоритмы, ставятся во главу архитектуры программного средства. Большая часть таких языков обладает определённым типом модульности, позволяющим структурам данных безопасно переиспользоваться в различных приложениях. Объектно-ориентированные языки, такие как Java, C# и C++, являются примерами такого подхода.
Многие классические структуры данных представлены в стандартных библиотеках языков программирования или непосредственно встроены в языки программирования. Например, структура данных хеш-таблица встроена в языки программирования Lua, Perl, Python, Ruby, Tcl и др. Широко используется стандартная библиотека шаблонов (STL) языка C++.
Фундаментальными строительными блоками для большей части структур данных являются массивы, записи (struct в Си и record в Паскале), размеченные объединения (union в Си) и ссылки. Например, двусвязный список может быть построен с помощью записей и ссылок, где каждая запись (узел) будет хранить данные и ссылки на «левый» и «правый» узлы.
Сравнение структур данных в функциональном и императивном программировании
Проектировать структуры данных для функциональных языков более сложно, чем для императивных, как минимум по двум причинам:
- Почти все структуры данных интенсивно используют присваивание, которое в чисто функциональном стиле не используется;
- Функциональные структуры данных являются более гибкими, и поэтому там, где в императивном программировании старая версия теряется, просто заменяясь новой, в функциональном она автоматически продолжает существовать. Другими словами, в императивном программировании (если не принять особых мер, которые могут серьёзно усложнить программу) структуры данных являются эфемерными, а в функциональных программах они как правило постоянные.
