"Информатика (базовый уровень) (в 2 частях)", Под ред. Макаровой Н.В.
Структура данных определяет, как элементы организованы, связаны и обрабатываются в программе. Линейный список выстраивает элементы в последовательность, стек работает по правилу «последним пришёл — первым вышел», очередь — «первым пришёл — первым вышел», а дерево создаёт иерархию уровней. Выбор структуры зависит от того, какие операции нужны чаще: добавление, удаление, поиск или обработка элементов.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Линейный список — последовательность элементов, в которой у каждого внутреннего элемента есть предыдущий и следующий. В отличие от массива, элементы списка могут быть связаны не соседним расположением в памяти, а ссылками или указателями. Такая организация удобна, когда элементы часто вставляют или удаляют, потому что можно изменить связи между соседями.
Стек — структура, где добавление и удаление выполняются с одного конца, называемого вершиной. Она работает по правилу LIFO: «последним пришёл — первым вышел». Стек нужен там, где сначала требуется обработать самое позднее действие, например при отмене команд или разборе вложенных вызовов.
Очередь — структура, в которой элементы добавляются с одного конца, а удаляются с другого. Её правило FIFO означает «первым пришёл — первым вышел». Поэтому очередь подходит для последовательного обслуживания заявок, сообщений или покупателей.
Дерево — иерархическая структура узлов со связями «родитель — потомок», начинающаяся с корня. От корня отходят ветви, а узлы, у которых нет потомков, называют листьями. Дерево позволяет показывать уровни и отношения подчинения, например папки и файлы.
Разные задачи требуют разных способов доступа к данным, поэтому одной универсальной структуры недостаточно. Если нужно быстро обращаться к элементу по номеру, удобен массив, а если важны вставки и удаления внутри последовательности, полезен список. Выбор структуры заранее определяет, какие операции будут простыми, а какие потребуют дополнительных действий.
В линейном списке элементы образуют цепочку связей. При вставке нового узла между вторым и третьим достаточно направить связь от второго к новому, а от нового — к третьему, не сдвигая все последующие элементы. При удалении узла соседние элементы соединяют напрямую, поэтому порядок сохраняется, но связи изменяются.
Стек подходит для вложенных действий, потому что последнее начатое действие обычно должно завершиться раньше предыдущего. Например, при вызове одной процедуры из другой сначала завершается внутренняя процедура, а затем внешняя. По той же причине стек удобен для отмены операций: последнюю команду можно отменить первой.
Очередь упорядочивает обслуживание так, чтобы более ранняя заявка не была вытеснена поздней. Новые элементы помещают в конец, а обработку начинают с начала, поэтому порядок поступления сохраняется. В стеке, наоборот, новая заявка оказывается первой на обработку, если она лежит на вершине.
Дерево организует данные по уровням, потому что каждый узел может иметь родителя и несколько потомков. Корень находится на верхнем уровне, от него отходят ветви, а листья располагаются на концах ветвей. Потомки узла — это все узлы, расположенные ниже него и связанные с ним через иерархию.
| Свойство | Линейный список | Стек | Очередь | Дерево |
|---|---|---|---|---|
| Как расположены элементы | В последовательности, связанной отношениями соседства | В последовательности с доступом через вершину | В последовательности с началом и концом | По уровням и ветвям |
| Как добавляют элементы | В нужное место списка | На вершину | В конец | К выбранному узлу как потомка |
| Как удаляют элементы | Из нужного места | С вершины | Из начала | Выбранный узел или ветвь |
| Порядок доступа к элементам | По связям последовательности | LIFO | FIFO | По уровням или ветвям |
| Пример применения | Список дел | Отмена действий | Очередь заявок | Файловая система |
Таблицу удобно читать по строкам, если нужно сравнить одну характеристику разных структур. По столбцам можно быстро определить, как устроена конкретная структура и где её применять. Особое внимание стоит обратить на порядок доступа: именно он различает стек и очередь.
Дан список из трёх элементов: A, B, C. Требуется вставить элемент X между вторым и третьим элементами. Нужно проследить не только порядок букв, но и изменение связей между соседними узлами.
Ответ: список станет A, B, X, C. Элемент C не исчезает и не перемещается физически обязательно: меняется порядок связей, по которым список просматривают.
В стек последовательно положили числа 4, 7 и 2. Затем дважды извлекли верхний элемент. Поскольку стек работает по принципу LIFO, сначала нужно проверить последний добавленный элемент, а не самое первое число.
Ответ: числа извлекаются в порядке 2, 7, а в стеке остаётся число 4. Каждая операция удаления берёт элемент с той же стороны, с которой выполнялось добавление.
В очередь поступили заявки A, B и C, затем одну заявку обработали, после чего поступила заявка D. В очереди добавление происходит в конец, а обработка — из начала. Поэтому нужно выполнять действия строго в порядке их поступления.
Ответ: первой обработана A, а состояние очереди после добавления D — B, C, D. Заявка D не может обойти B и C, потому что очередь соблюдает принцип FIFO.
Ошибка: считать стек и очередь одинаковыми структурами. Так происходит, если смотреть только на наличие добавления и удаления, не учитывая их стороны. Проверьте себя: в стеке обе операции выполняются с одного конца, а в очереди — с разных.
Ошибка: путать LIFO и FIFO. Названия похожи, поэтому полезно раскрывать сокращение и проверять его на трёх элементах. Если первым извлекается последний добавленный элемент, это LIFO; если первый — FIFO.
Ошибка: считать, что любой узел дерева имеет только одного потомка. Такое представление возникает из-за сходства дерева с цепочкой, но у узла может быть несколько ветвей. Проверьте схему: посчитайте, сколько связей выходит из одного родительского узла.
Ошибка: называть дерево линейной структурой. В дереве элементы не образуют одну последовательность, а располагаются по уровням. Если от одного узла можно перейти к нескольким потомкам, перед вами иерархия, а не линейная цепочка.
Для понимания темы нужны представления о данных, элементах данных и последовательностях, а также умение выполнять алгоритм по шагам. Эти знания помогают точно отслеживать добавление, удаление и изменение связей. Структуры данных применяются при выборе способа хранения информации в программах, в файловых системах и при работе с иерархическими данными.
Чем список отличается от массива?
Массив обычно хранит элементы в соседних ячейках памяти и имеет фиксированный или заранее заданный размер. В линейном списке элементы связаны последовательностью, поэтому вставка и удаление могут выполняться изменением связей между узлами.
Почему стек называют структурой LIFO?
LIFO расшифровывается как «последним пришёл — первым вышел». Новый элемент кладут на вершину стека, и извлекают также с вершины, поэтому последняя добавленная запись обрабатывается первой.
Почему очередь называют структурой FIFO?
FIFO означает «первым пришёл — первым вышел». Элементы добавляются в конец очереди, а извлекаются из начала, поэтому порядок обслуживания совпадает с порядком поступления.
Можно ли добавлять и удалять элементы очереди с одного конца?
В обычной очереди эти операции выполняются с разных концов: добавление — с конца, удаление — с начала. Если обе операции разрешены с одного конца, такая структура уже работает по принципу стека.
Чем дерево отличается от линейной последовательности?
Линейная последовательность образует одну цепочку элементов, где у каждого внутреннего элемента есть один предшественник и один следующий. В дереве связи образуют уровни: у узла может быть несколько потомков, а все ветви начинаются от корня.
Другие виды структур
