Структура данных

Материал из Поле цифровой дидактики
Версия от 16:30, 10 августа 2022; ru_wikipedia>Gretanit (переделал ошибочные части.)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Файл:Binary tree.svg
Бинарное дерево, простой пример ветвящейся связной структуры данных.

Структура данных (Шаблон:Lang-en) — программная единица, позволяющая хранить и обрабатывать однотипные и/или логически связанные данные. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс.

Термин «структура данных» может иметь несколько близких, но тем не менее различных значений{{#if: | }}<ref name="{{#if: | | _13887dce17e184c5 }}" group="{{#if: | }}">Шаблон:Sfn-текст.</ref>{{#if: | }}:

  • Абстрактный тип данных;
  • Реализация какого-либо абстрактного типа данных;
  • Экземпляр типа данных, например, конкретный список;
  • В контексте функционального программирования — уникальная единица (Шаблон:Lang-en), сохраняющаяся при изменениях. О ней неформально говорят как об одной структуре данных, несмотря на возможное наличие различных версий.

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

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

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

Файл:Python 3. The standard type hierarchy.png

Многие классические структуры данных представлены в стандартных библиотеках языков программирования или непосредственно встроены в языки программирования. Например, структура данных хеш-таблица встроена в языки программирования Lua, Perl, Python, Ruby, Tcl и др. Широко используется стандартная библиотека шаблонов (STL) языка C++.

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

Сравнение структур данных в функциональном и императивном программировании

Проектировать структуры данных для функциональных языков более сложно, чем для императивных, как минимум по двум причинам{{#if: | }}<ref name="{{#if: | | _13887dce17e184c5 }}" group="{{#if: | }}">Шаблон:Sfn-текст.</ref>{{#if: | }}:

  1. Почти все структуры данных интенсивно используют присваивание, которое в чисто функциональном стиле не используется;
  2. Функциональные структуры данных являются более гибкими, и поэтому там, где в императивном программировании старая версия теряется, просто заменяясь новой, в функциональном она автоматически продолжает существовать. Другими словами, в императивном программировании (если не принять особых мер, которые могут серьёзно усложнить программу) структуры данных являются эфемерными (Шаблон:Lang-en), а в функциональных программах они как правило постоянные (Шаблон:Lang-en).

Примечания

1 }} 
       | {{#switch: {{{1}}}
         | узкие = columns reflist-narrow
         | широкие = columns reflist-wide
         | #default = columns
         }}
       | {{#switch: {{{1}}}
         | 1 = 
         | 2 | 3 = columns
         | #default = columns reflist-narrow
         }}
       }}
     | columns
     }}
   }}" style="{{#if: 
   | column-width:{{{colwidth}}};
   | {{#if: 
     | {{#iferror: {{#ifexpr: {{{1}}} > 1 }}
       | {{#switch: {{{1}}}
         | узкие | широкие = 
         | #default = column-width:{{{1}}};
         }}
       }}
     }}
   }} list-style-type: {{#switch: 
   | upper-alpha
   | upper-roman
   | lower-alpha
   | lower-greek
   | lower-roman = {{{group}}}
   | #default = decimal
   }};">

<references group="" responsive="{{#if: 

 | 0
 | {{#if: 
   | {{#iferror: {{#expr: {{{1}}} > 1 }}
     | {{#switch: {{{1}}}
       | узкие | широкие = 1
       | #default = 0
       }}
     | {{#switch: {{{1}}}
       | 1 = 0
       | #default = 1
       }}
     }}
   | 1
   }}
}}"></references>

Ошибка скрипта: Модуля «Check for unknown parameters» не существует.

Литература

  • {{#if:Альфред В. Ахо, Джон Хопкрофт, Джеффри Д. Ульман.|Альфред В. Ахо, Джон Хопкрофт, Джеффри Д. Ульман. }}{{#if: |{{#if: |[{{{ссылка часть}}} {{{часть}}}]| {{{часть}}}}} // }}{{#if:|[[:s:{{{викитека}}}|Структуры данных и алгоритмы]]|{{#if:|[{{{ссылка}}} Структуры данных и алгоритмы]|Структуры данных и алгоритмы}}}}{{#if:Data Structures and Algorithms| = Data Structures and Algorithms }}{{#if:| / {{{ответственный}}}.|{{#if:||.}}}}{{#if:Структуры данных и алгоритмы|{{#if:| {{#if:| = {{{оригинал2}}} }}{{#if:| / {{{ответственный2}}}.|{{#if:||.}}}}}}}}{{#if:| — {{{издание}}}.}}{{#switch:{{#if:М.|м}}{{#if:Вильямс|и}}{{#if:2000|г}}
 |миг= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:М.|М.}} }}: Вильямс, 2000.
 |ми= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:М.|М.}} }}: Вильямс.
 |мг= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:М.|М.}} }}, 2000.
 |иг= — Вильямс, 2000.
 |м= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:М.|М..}} }}
 |и= — Вильямс.
 |г= — 2000.

}}{{#if:| — {{{том как есть}}}.}}{{#if:| — Т. {{{том}}}.}}{{#if:| — Vol. {{{volume}}}.}}{{#if:| — B. {{{band}}}.}}{{#if:| — {{{страницы как есть}}}.}}{{#if:| — С. {{{страницы}}}.}}{{#if:| — {{{страниц как есть}}}.}}{{#if:384| — 384 с.}}{{#if:| — P. {{{pages}}}.}}{{#if:| — S. {{{seite}}}.}}{{#if:| —  p.}}{{#if:| —  s.}}{{#if:| — ({{{серия}}}).}}{{#if:| — Шаблон:Nobr}}{{#if:0-201-00023-7| — ISBN 0-201-00023-7}}

  • {{#if:Майкл Мейн, Уолтер Савитч.|Майкл Мейн, Уолтер Савитч. }}{{#if: |{{#if: |[{{{ссылка часть}}} {{{часть}}}]| {{{часть}}}}} // }}{{#if:|[[:s:{{{викитека}}}|Структуры данных и другие объекты в C++]]|{{#if:|[{{{ссылка}}} Структуры данных и другие объекты в C++]|Структуры данных и другие объекты в C++}}}}{{#if:Data Structures and Other Objects Using C++| = Data Structures and Other Objects Using C++ }}{{#if:| / {{{ответственный}}}.|{{#if:||.}}}}{{#if:Структуры данных и другие объекты в C++|{{#if:| {{#if:| = {{{оригинал2}}} }}{{#if:| / {{{ответственный2}}}.|{{#if:||.}}}}}}}}{{#if:2-е изд| — 2-е изд.}}{{#switch:{{#if:М.|м}}{{#if:Вильямс|и}}{{#if:2002|г}}
 |миг= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:М.|М.}} }}: Вильямс, 2002.
 |ми= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:М.|М.}} }}: Вильямс.
 |мг= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:М.|М.}} }}, 2002.
 |иг= — Вильямс, 2002.
 |м= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:М.|М..}} }}
 |и= — Вильямс.
 |г= — 2002.

}}{{#if:| — {{{том как есть}}}.}}{{#if:| — Т. {{{том}}}.}}{{#if:| — Vol. {{{volume}}}.}}{{#if:| — B. {{{band}}}.}}{{#if:| — {{{страницы как есть}}}.}}{{#if:| — С. {{{страницы}}}.}}{{#if:| — {{{страниц как есть}}}.}}{{#if:832| — 832 с.}}{{#if:| — P. {{{pages}}}.}}{{#if:| — S. {{{seite}}}.}}{{#if:| —  p.}}{{#if:| —  s.}}{{#if:| — ({{{серия}}}).}}{{#if:| — Шаблон:Nobr}}{{#if:0-201-70297-5| — ISBN 0-201-70297-5}}

  • {{#if:Chris Okasaki|Chris Okasaki }}{{#if: |{{#if: |[{{{ссылка часть}}} {{{часть}}}]| {{{часть}}}}} // }}{{#if:|[[:s:{{{викитека}}}|Purely Functional Data Structures]]|{{#if:|[{{{ссылка}}} Purely Functional Data Structures]|Purely Functional Data Structures}}}}{{#if:| = {{{оригинал}}} }}{{#if:| / {{{ответственный}}}.|{{#if:||.}}}}{{#if:Purely Functional Data Structures|{{#if:| {{#if:| = {{{оригинал2}}} }}{{#if:| / {{{ответственный2}}}.|{{#if:||.}}}}}}}}{{#if:| — {{{издание}}}.}}{{#switch:{{#if:|м}}{{#if:Cambridge University Press|и}}{{#if:1998|г}}
 |миг= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}: Cambridge University Press, 1998.
 |ми= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}: Cambridge University Press.
 |мг= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}, 1998.
 |иг= — Cambridge University Press, 1998.
 |м= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}.}} }}
 |и= — Cambridge University Press.
 |г= — 1998.

}}{{#if:| — {{{том как есть}}}.}}{{#if:| — Т. {{{том}}}.}}{{#if:| — Vol. {{{volume}}}.}}{{#if:| — B. {{{band}}}.}}{{#if:| — {{{страницы как есть}}}.}}{{#if:| — С. {{{страницы}}}.}}{{#if:| — {{{страниц как есть}}}.}}{{#if:232| — 232 с.}}{{#if:| — P. {{{pages}}}.}}{{#if:| — S. {{{seite}}}.}}{{#if:| —  p.}}{{#if:| —  s.}}{{#if:| — ({{{серия}}}).}}{{#if:| — Шаблон:Nobr}}{{#if:978-0521663502| — ISBN 978-0521663502}}

Ссылки

Шаблон:Rq

Шаблон:Структуры данных Шаблон:Типы данных

Источник — http://digida.mgpu.ru/index.php?title=Структура_данных&oldid=4538