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