АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ
Электронный учебный материал для студентов всех специальностей факультета Прикладная информатика Кубанского государственного аграрного университета
1.4. Краткая теория
В лабораторном занятии №1 рассматривались только статические программные объекты. Этим термином обозначаются объекты, которые порождаются непосредственно перед выполнением программы, существуют в течение всего времени ее выполнения и размер значений которых не изменяется по ходу выполнения программы.
Поскольку статические объекты порождаются до выполнения программы и размер их значений можно выделить еще на этапе трансляции исходного текста программы на языке машины.
Однако использование при программировании только статических объектов может вызвать определенные трудности, особенно с точки зрения получения эффективной машинной программы, а такая эффективность бывает чрезвычайно важной при решении ряда задач. Дело в том, что иногда мы заранее не знаем не только размера значения того или иного программного объекта, но даже и того, будет ли существовать этот объект или нет. Такого рода программные объекты, которые возникают уже в процессе выполнения программы, называют динамическими объектами.
Динамические структуры данных имеют две особенности :
1. Заранее не определимо количество элементов в структуре;
2. Элементы динамической структуры не имеют жесткой линейной упорядоченности. Они могут быть разбросаны по памяти.
Чтобы связать элементы динамической структуры между собой, в состав элемента помимо информационного поля входят поля указателей (связок с другими элементами структуры).
p1, p2 - указатели, содержащие адреса элементов, с которыми данный элемент связан.
Наиболее распространенными динамическими структурами являются связанные списки. С точки зрения логического представления различают линейные и нелинейные списки. В линейных списках связи строго упорядочены. Указатель предыдущего элемента дает адрес последующего элемента или наоборот.
К линейным спискам относятся односвязные и двусвязные списки.
К нелинейным - многосвязные списки.
Элемент списка в общем случае представляет собой комбинацию поля записи (информационного поля) и одного или нескольких указателей.
Линейные однонаправленные списки (односвязные списки)
Под односвязными списками понимают упорядоченную последовательность элементов, каждый из которых имеет 2 поля:
- информационное поле info и
- поле указателя ptr .
Особенностью указателя является то, что он дает только адрес последующего элемента списка. У однонаправленных списков поле указателя последнего элемента в списке является пустым nil.
Lst - указатель начала списка. Он представляет список как единое целое. Иногда список может быть пустым, т.е. в данном списке нет ни одного элемента. В этом случае lst = nil.
Кольцевые односвязные списки
Пример кольцевого списка представлен на следующем рисунке.
На этом рисунке, список замыкается в своеобразное "кольцо": двигаясь по ссылкам, можно от последнего элемента списка переходить к заглавному элементу. В связи с этим списки подобного рода называют кольцевыми списками.
ОПЕРАЦИИ НАД ОДНОСВЯЗНЫМИ СПИСКАМИ:
1. Вставка элемента в начало односвязного списка.
2. Удаление элемента из начала односвязного списка
3. Вставка элемента в список
4. Удаление элемента из односвязного списка
ОПЕРАЦИИ НАД КОЛЬЦЕВЫМИ СПИСКАМИ:
1. Вставка элемента в кольцевой список
2. Удаление элемента из кольцевого списка