Информатика и технология программирования


Списки как динамические структуры данных


Наиболее простыми динамическими структурами данных являются списки. Список представляет собой линейную последовательность переменных, каждая из которых связана указателями со своими соседями. Списки бывают следующих видов:



-односвязные -каждый элемент списка имеет указатель на следующий;



-двусвязные -каждая элемент списка имеет указатель на следующий и на предыдущий элементы;



-двусвязный циклический список -первый и последний элементы списка ссылаются друг на друга, таким образом цепочка представляет собой кольцо.







Сразу же необходимо отметить основное свойство списков как структур данных. Последовательность обхода списка, естественно, зависит не от физического размещения элементов списка в памяти, а от последовательности из связывания указателями. Точно так же определяется нумерация элементов списка - ЛОГИЧЕСКИЙ НОМЕР элемента в списке - это номер, получаемывй им в процессе движения по списку.

Односвязные списки являются наиболее простыми. Основным их недостатком является возможность просмотра только в одном направлении -от начала к концу. Без дополнительных "ухищрений" нельзя получить указатель на предыдущий элемент списка, который необходим при удалении текущего. Для односвязного списка наиболее простыми являются операции включения и исключения элементов в начале и конце списка, соответственно они используются для моделирования таких структур данных, как стеки и очереди.

Двусвязные списки дают возможность просмотра элементов в обоих направлениях и являются наиболее универсальными. Операции включения и исключения элементов в различные части такого списка имеют примерно одинаковый уровень сложности. Двусвязные списки используются для создания цепочек элементов, которые допускают частые операции включения, исключения, упорядочения, замены и пр..

В односвязных и двусвязных списках последний элемент содержит указатель NULL для обозначения факта окончания последовательности. Аналогично первый элемент двусвязного списка содержит указатель NULL на предыдущий элемент.


Начало  Назад  Вперед