Лабораторная работа № 1.
СПИСКОВЫЕ СТРУКТУРЫДАННЫХ
Цель работы: исследовать и изучить списковые структуры данных, научиться писать программы по исследованию списковых структур на языке программирования.
Краткая теория
Статические программные объекты – это объекты, которые порождаются непосредственно перед выполнением программы, существуют в течение всего времени ее выполнения и размер значений которых не изменяется по ходу выполнения программы.
Программные объекты, которые создаются в процессе выполнения программы, называют динамическими объектами.
Для работы с динамическими объектами предусматривается специальный тип данных - так называемый ссылочный тип. Значением этого типа является ссылка на какой - либо программный объект, по которой осуществляется непосредственный доступ к этому объекту. Для описания действий над динамическими объектами каждому такому объекту в программе сопоставляется статическая переменная ссылочного типа - в терминах этих ссылочных переменных и описываются действия над соответствующими динамическими объектами.
Чтобы связать элементы динамической структуры между собой, в состав элемента помимо информационного поля входят поля указателей (связок с другими элементами структуры).
p1, p2 - указатели, содержащие адреса элементов, с которыми данный элемент связан.
Наиболее распространенными динамическими структурами являются связанные списки. С точки зрения логического представления различают линейные и нелинейные списки. В линейных списках связи строго упорядочены. Указатель предыдущего элемента дает адрес последующего элемента или наоборот.
К линейным спискам относятся односвязные и двусвязные списки.
К нелинейным - многосвязные списки.
Элемент списка в общем случае представляет собой комбинацию поля записи (информационного поля) и одного или нескольких указателей.
Линейные однонаправленные списки
Под односвязными списками понимают упорядоченную последовательность элементов, каждый из которых имеет 2 поля: информационное поле info и поле указателя ptr.
Особенностью указателя является то, что он дает только адрес последующего элемента списка. У однонаправленных списков поле указателя последнего элемента в списке является пустым null.
Lst - указатель начала списка. Он представляет список как единое целое. Иногда список может быть пустым, т.е. в данном списке нет ни одного элемента. В этом случае lst = null.
Алгоритм
Операции с односвязными списками.
1. Вставка элемента в начало односвязного списка.
Вставим в начало данного списка элемент, информационное поле которого содержит переменную D. Чтобы это осуществить, необходимо произвести следующие действия:
а) Создать пустой элемент, на который указывает указатель p.
b) Информационному полю созданного элемента присвоить значение D.
с) Связать новый элемент со списком.
Ptr(p)=lst (lst - уже не указывает на начало списка)
d) Перенести указатель lst на начало списка.
Удаление элемента из начала односвязного списка
Удалим 1-й элемент списка, но при этом запомним информацию содержащиеся в поле info этого элемента.
Чтобы это осуществить, необходимо произвести следующие действия:
a) Ввести указатель р, который будет указывать на удаляемый элемент.
P=lst
b) Запомнить поле info элемента, на который ссылается указатель р, в некоторую переменную (х).
X=info(P)
c) Перенести указатель lst на новое начало списка.
lst=ptr(P)
d) Удалить элемент на который указывает указатель р.
Freenode(P)
