Структуры и алгоритмы обработки данных

Partse.ru предлагает: запчасти на Toyota Town Ace Noah в Екатеринбурге!

Краткая теория


 

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

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

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

В языке ПАСКАЛЬ для работы с динамическими объектами предусматривается специальный тип данных - так называемый ссылочный тип. Значением этого типа является ссылка на какой - либо программный объект, по которой осуществляется непосредственный доступ к этому объекту. На машинном языке такая ссылка как раз и представляется указанием места в памяти соответствующего объекта.

В этом случае для описания действий над динамическими объектами каждому такому объекту в программе сопоставляется статическая переменная ссылочного типа - в терминах этих ссылочных переменных и описываются действия над соответствующими динамическими объектами.

Итак, динамические структуры данных имеют две особенности :

 1. Заранее не определимо количество элементов в структуре;

 2. Элементы динамической структуры не имеют жесткой линейной упорядоченности. Они могут быть разбросаны по памяти.

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

 

 

p1, p2 - указатели, содержащие адреса элементов, с которыми данный элемент связан.

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

К линейным спискам относятся односвязные и двусвязные списки.

К нелинейным - многосвязные списки.

Элемент списка в общем случае представляет собой комбинацию поля записи (информационного поля) и одного или нескольких указателей.




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



Книжный магазин