§ 21. Структуры данных
21.1. Понятие о структурах данных
|
В информатике структура данных — программная единица, позволяющая хранить и обрабатывать данные, а также обеспечивающая их эффективное использование. Данные при этом должны быть однотипными или логически связанными. Различные виды структур данных подходят для различных задач; некоторые из них имеют узкую специализацию, другие являются универсальными (пример 21.1). При разработке программного обеспечения сложность реализации и качество работы программ существенно зависят не только от выбора алгоритма, но и от правильного выбора структур данных. Одни и те же данные можно сохранить в структурах, требующих различного объема памяти, а алгоритмы работы с разными структурами данных могут иметь различную эффективность. Структура данных, наиболее подходящая для решения конкретной задачи, позволяет выполнять большое количество различных операций, используя как можно меньший объем ресурсов. Ни одна профессиональная программа сегодня не пишется без использования структур данных, поэтому многие из них содержатся в стандартных библиотеках современных языков программирования (например, STL для С++). Структура данных представляет собой набор значений данных, отношения между ними, а также функции и (или) операции, которые могут быть применены к данным. Структуры данных классифицируют по разным признакам. В примере 21.2 приведена классификация структур данных по организации взаимосвязей между элементами. Далее будут рассмотрены некоторые линейные структуры данных. |
Пример 21.1. Примеры некоторых структур данных: 1. Массив (вектор в C++) — самая простая и широко используемая структура данных. 2. Запись (структура в С++) — совокупность элементов данных разного типа. Содержит постоянное количество элементов, которые называют полями. 3. Связный список (Linked List) представляет набор связанных узлов, каждый из которых хранит собственно данные и ссылку на следующий узел. В реальной жизни связный список можно представить в виде поезда, каждый вагон которого может содержать некоторый груз или пассажиров и при этом может быть связан с другим вагоном. 4. Граф — совокупность вершин (узлов) и связей между ними (ребер). В реальной жизни по такому принципу устроены социальные сети: узлы — это люди, а ребра — их отношения. 5. Множество — совокупность данных, значения которых не повторяются, реализация математического объекта множество, за исключением того, что множество в программировании конечно. Пример 21.2. Классификация структур данных. Линейные:
Иерархические:
Сетевые:
Табличные:
|