Лабораторная работа № 2. "СПИСКОВЫЕ СТРУКТУРЫ ДАННЫХ"

Привет, сегодня поговорим про списковые структуры данных, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое списковые структуры данных , настоятельно рекомендую прочитать все из категории Структуры данных.

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

Алгоритм

Операции с односвязными списками.

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 )

Окончательно:

Вставка элемента в список

Вставим в данный список перед элементом на который указывает указатель р, элемент с информационным полем х.





Чтобы это осуществить необходимо произвести следующие действия :

a) Создать пустой элемент на который указывает указатель q. 

Q=getnode 

b) Внести х в информационное поле созданного элемента.

Info(Q)=x

c) Связать элемент х с элементом В.

Ptr(Q)=Ptr(P) - это значит, что указателю созданного элемента присваивается значение указателя элемента р.

d) Связать элемент А с элементом х.

Ptr(p)=Q - это значит, что следующим за элементом А будет элемент на который указывает указатель Q.

Окончательно :

Удаление элемента из односвязного списка

Удалим из списка элемент, который следует за элементом с рабочим указателем р.





Чтобы это осуществить необходимо произвести следующие действия :

a) Ввести указатель Q, который будет указывать на удаляемый элемент.

Q=ptr(p)

b) Поставить за элементом А элемент В.

Ptr(p)=Ptr(Q)

с) Запомнить информацию, которая содержится в поле info удаляемого элемента.

K=info(Q) 

d) Удалим элемент с указателем Q.

Freenode(Q)

Окончательно :

Задания

Варианты :

1. Написать программу передвижения элемента на n позиций.

2. Создать копию списка.

3. Добавить элемент в начало списка.

4. Склеить два списка.

5. Удалить n-ый элемент из списка.

6. Вставить элемент после n-го элемента списка.

7. Создать список содержащий элементы общие для двух списков.

8. Упорядочить элементы в списке по возрастанию.

9. Удалить каждый второй элемент списка.

10. Удалить каждый третий элемент списка.

11. Упорядочить элементы списка по убыванию.

12. Очистить список.

На этом все! Теперь вы знаете все про списковые структуры данных, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое списковые структуры данных и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Структуры данных

Из статьи мы узнали кратко, но содержательно про списковые структуры данных