ЛЕКЦИЯ 3. СПИСКИ. СПЕЦИФИКАЦИЯ И ПРЕДСТАВЛЕНИЕ В ПАМЯТИ
Цели и задачи лекции: изучить организацию и представление списков в памяти ЭВМ.
Основные вопросы: односвязные линейные списки, двухвязные списки, кольцевые списки.
Динамические структуры по определению характеризуются отсутствием физической смежности элементов структуры в памяти непостоянством структуры в процессе ее обработки. Поскольку элементы динамической структуры располагаются по непредсказуемым адресам памяти, адрес элемента такой структуры не может быть вычислен из адреса начального или предыдущего элемента. Для установления связи между элементами динамической структуры используются указатели, через которые устанавливаются явные связи между элементами. Такое представление данных в памяти называется связным. Элемент динамической структуры состоит из двух полей:
· информационного поля или поля данных, в котором содержатся те данные, ради которых и создается структура; в общем случае информационное поле само является интегрированной структурой - вектором, массивом, записью и т.п.;
· поле связок, в котором содержатся один или несколько указателей, связывающий данный элемент с другими элементами структуры;
Достоинства связного представления данных - в возможности обеспечения значительной изменчивости структур;
· размер структуры ограничивается только доступным объемом машинной памяти;
· при изменении логической последовательности элементов структуры требуется не перемещение данных в памяти, а только коррекция указателей.
|
|
|
Вместе с тем связное представление не лишено и недостатков, основные из которых:
· работа с указателями требует, как правило, более высокой квалификации от программиста;
· на поля связок расходуется дополнительная память;
· доступ к элементам связной структуры может быть менее эффективным по времени.
Связные линейные списки
Списком называется упорядоченное множество, состоящее из переменного числа элементов, к которым применимы операции включения, исключения. Список, отражающий отношения соседства между элементами, называется линейным. Если ограничения на длину списка не допускаются, то список представляется в памяти в виде связной структуры. Линейные связные списки являются простейшими динамическими структурами данных.
Графически связи в списках удобно изображать с помощью стрелок. Если компонента не связана ни с какой другой, то в поле указателя записывают значение, не указывающее ни на какой элемент. Такая ссылка обозначается специальным именем - nil.
Машинное представление связных линейных списков
На рис. 1 приведена структура односвязного списка. На нем поле INF - информационное поле, данные, NEXT - указатель на следующий элемент списка. Каждый список должен иметь особый элемент, называемый указателем начала списка или головой списка, который обычно по формату отличен от остальных элементов. В поле указателя последнего элемента списка находится специальный признак nil, свидетельствующий о конце списка.
|
|
|
Рис. 1. Структура односвязного списка
Однако, обработка односвязного списка не всегда удобна, так как отсутствует возможность продвижения в противоположную сторону. Такую возможность обеспечивает двухсвязный список, каждый элемент которого содержит два указателя: на следующий и предыдущий элементы списка. Структура линейного двухсвязного списка приведена на рис.2, где поле NEXT - указатель на следующий элемент, поле PREV - указатель на предыдущий элемент. Для удобства обработки списка добавляют еще один особый элемент - указатель конца списка. Наличие двух указателей в каждом элементе усложняет список и приводит к дополнительным затратам памяти, но в то же время обеспечивает более эффективное выполнение некоторых операций над списком.
Рис. 2. Структура двухсвязного списка
Разновидностью рассмотренных видов линейных списков является кольцевой список, который может быть организован на основе как односвязного, так и двухсвязного списков. При этом в односвязном списке указатель последнего элемента должен указывать на первый элемент; в двухсвязном списке в первом и последнем элементах соответствующие указатели переопределяются ( рис.3).
|
|
|
При работе с такими списками несколько упрощаются некоторые процедуры, выполняемые над списком. Однако, при просмотре такого списка следует принять некоторых мер предосторожности, чтобы не попасть в бесконечный цикл.
Рис. 3. Структура кольцевого двухсвязного списка
В памяти список представляет собой совокупность дескриптора и одинаковых по размеру и формату записей, размещенных произвольно в некоторой области памяти и связанных друг с другом в линейно упорядоченную цепочку с помощью указателей. Запись содержит информационные поля и поля указателей на соседние элементы списка, причем некоторыми полями информационной части могут быть указатели на блоки памяти с дополнительной информацией, относящейся к элементу списка. Дескриптор списка реализуется в виде особой записи и содержит такую информацию о списке, как адрес начала списка, код структуры, имя списка, текущее число элементов в списке, описание элемента и т.д., и т.п. Дескриптор может находиться в той же области памяти, в которой располагаются элементы списка, или для него выделяется какое-нибудь другое место.
|
|
|
Структуры элементов списков:
· элемент односвязного списка:
· type
· sllptr = ^slltype; { указатель в односвязном списке }
· slltype = record { элемент односвязного списка }
· inf : data; { информационная часть }
· next : sllptr; { указатель на следующий элемент }
end;
· элемент двухсвязного списка:
· type
· dllptr = ^dlltype; { указатель в двухсвязном списке }
· dlltype = record { элемент односвязного списка }
· inf : data; { информационная часть }
· next : sllptr; { указатель на следующий элемент (вперед) }
· prev : sllptr; { указатель на предыдущий элемент (назад) }
end;
Обратить внимание на опережающее описание.
Дата добавления: 2018-05-02; просмотров: 575; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!