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

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

Термин «структура данных» может иметь несколько близких, но тем не менее различных значений:

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

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

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

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

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

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

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

Проектировать структуры данных для функциональных языков более сложно, чем для императивных, как минимум по двум причинам:

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

Литература

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

Ссылки

• [algolist.manual.ru/ds/ Структуры данных и хеширование]
• [kvodo.ru/data-structures-introduction.html Основные структуры данных]

Отрывок, характеризующий Структура данных

– Отец, ангел, батюшка! – приговаривала она, отирая пальцем слезы.
– Ура! – кричали со всех сторон. С минуту толпа простояла на одном месте; но потом опять бросилась вперед.
Петя, сам себя не помня, стиснув зубы и зверски выкатив глаза, бросился вперед, работая локтями и крича «ура!», как будто он готов был и себя и всех убить в эту минуту, но с боков его лезли точно такие же зверские лица с такими же криками «ура!».
«Так вот что такое государь! – думал Петя. – Нет, нельзя мне самому подать ему прошение, это слишком смело!Несмотря на то, он все так же отчаянно пробивался вперед, и из за спин передних ему мелькнуло пустое пространство с устланным красным сукном ходом; но в это время толпа заколебалась назад (спереди полицейские отталкивали надвинувшихся слишком близко к шествию; государь проходил из дворца в Успенский собор), и Петя неожиданно получил в бок такой удар по ребрам и так был придавлен, что вдруг в глазах его все помутилось и он потерял сознание. Когда он пришел в себя, какое то духовное лицо, с пучком седевших волос назади, в потертой синей рясе, вероятно, дьячок, одной рукой держал его под мышку, другой охранял от напиравшей толпы.
– Барчонка задавили! – говорил дьячок. – Что ж так!.. легче… задавили, задавили!
Государь прошел в Успенский собор. Толпа опять разровнялась, и дьячок вывел Петю, бледного и не дышащего, к царь пушке. Несколько лиц пожалели Петю, и вдруг вся толпа обратилась к нему, и уже вокруг него произошла давка. Те, которые стояли ближе, услуживали ему, расстегивали его сюртучок, усаживали на возвышение пушки и укоряли кого то, – тех, кто раздавил его.
– Этак до смерти раздавить можно. Что же это! Душегубство делать! Вишь, сердечный, как скатерть белый стал, – говорили голоса.
Петя скоро опомнился, краска вернулась ему в лицо, боль прошла, и за эту временную неприятность он получил место на пушке, с которой он надеялся увидать долженствующего пройти назад государя. Петя уже не думал теперь о подаче прошения. Уже только ему бы увидать его – и то он бы считал себя счастливым!
Во время службы в Успенском соборе – соединенного молебствия по случаю приезда государя и благодарственной молитвы за заключение мира с турками – толпа пораспространилась; появились покрикивающие продавцы квасу, пряников, мака, до которого был особенно охотник Петя, и послышались обыкновенные разговоры. Одна купчиха показывала свою разорванную шаль и сообщала, как дорого она была куплена; другая говорила, что нынче все шелковые материи дороги стали. Дьячок, спаситель Пети, разговаривал с чиновником о том, кто и кто служит нынче с преосвященным. Дьячок несколько раз повторял слово соборне, которого не понимал Петя. Два молодые мещанина шутили с дворовыми девушками, грызущими орехи. Все эти разговоры, в особенности шуточки с девушками, для Пети в его возрасте имевшие особенную привлекательность, все эти разговоры теперь не занимали Петю; ou сидел на своем возвышении пушки, все так же волнуясь при мысли о государе и о своей любви к нему. Совпадение чувства боли и страха, когда его сдавили, с чувством восторга еще более усилило в нем сознание важности этой минуты.
Вдруг с набережной послышались пушечные выстрелы (это стреляли в ознаменование мира с турками), и толпа стремительно бросилась к набережной – смотреть, как стреляют. Петя тоже хотел бежать туда, но дьячок, взявший под свое покровительство барчонка, не пустил его. Еще продолжались выстрелы, когда из Успенского собора выбежали офицеры, генералы, камергеры, потом уже не так поспешно вышли еще другие, опять снялись шапки с голов, и те, которые убежали смотреть пушки, бежали назад. Наконец вышли еще четверо мужчин в мундирах и лентах из дверей собора. «Ура! Ура! – опять закричала толпа.
– Который? Который? – плачущим голосом спрашивал вокруг себя Петя, но никто не отвечал ему; все были слишком увлечены, и Петя, выбрав одного из этих четырех лиц, которого он из за слез, выступивших ему от радости на глаза, не мог ясно разглядеть, сосредоточил на него весь свой восторг, хотя это был не государь, закричал «ура!неистовым голосом и решил, что завтра же, чего бы это ему ни стоило, он будет военным.
Толпа побежала за государем, проводила его до дворца и стала расходиться. Было уже поздно, и Петя ничего не ел, и пот лил с него градом; но он не уходил домой и вместе с уменьшившейся, но еще довольно большой толпой стоял перед дворцом, во время обеда государя, глядя в окна дворца, ожидая еще чего то и завидуя одинаково и сановникам, подъезжавшим к крыльцу – к обеду государя, и камер лакеям, служившим за столом и мелькавшим в окнах.