Методические рекомендации и указания (стр. 20 )

создания структур данных различной конфигурации. Это достигается

благодаря возможности выделять и освобождать память под элементы в

любой момент времени работы программы и возможности установить

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

Для организации связей между элементами динамической структуры данных

требуется, чтобы каждый элемент содержал кроме информационных значений

как минимум один указатель. Отсюда следует, что в качестве элементов таких

структур необходимо использовать записи, которые могут объединять в единое

целое разнородные элементы.

В простейшем случае элемент динамической структуры данных должен

состоять из двух полей: информационного и указательного.

Схематично такую структуру данных можно показать следующим

образом:

Соответствующие ей объявления будут иметь такой вид:

Type

TPtr = ^ TElem;

TElem = Record

Inf : real;

Link: TPtr

End;

Правило последовательности описаний в Турбо Паскаль требует, чтобы

каждый идентификатор был описан, прежде чем он будет использоваться для

других объявлений. Для описания типов элементов динамических структур

данных сделано исключение.

Тип указателя на элемент динамической структуры данных может и должен

быть описан перед описанием типа этого элемента.

ОПЕРАЦИИ НАД СПИСКАМИ.

Основными операциями над списками являются:

1. переход от элемента к следующему элементу;

2. включение нового элемента в список;

3. исключение элемента из списка.

Пусть значением переменной q типа TPtr является ссылка на некоторый

элемент списка целых чисел. Тогда после присваивания q:= q^.link ее

inf

link

inf

link

inf

link

204

значением будет или ссылка на следующий элемент этого списка (если такой

элемент имеется ) или NIL. Пользуясь таким способом перехода от одного

элемента к другому, можно просматривать весь список или его часть.

Пусть имеются переменные p, q, r типа TPtr и значением переменной q

является ссылка на некоторый элемент списка целых чисел? А значением p -

ссылка на первый элемент этого списка, пусть требуется включить в данный

список после элемента? Ссылка на который является значением переменной q,

новый элемент, содержащий число 17. Для этого нужно выполнить

последовательность операторов

New( r ); r^.inf:= 17; r^.link:= q^.link; q^.link:=r;

Пусть теперь значением переменной q является ссылка на некоторый (не

последний) элемент списка целых чисел и требуется исключить из списка

элемент, следующий за тем, ссылка на который является значением

переменной q. Для этого нужно выполнить последовательность операторов

R:= q^.link; q^.link:= q^.link^.link; r^.link:= nil

Второе из этих присваиваний – это исключение элемента из списка, а первое

выполняется для того, чтобы сохранить ссылку на исключенный элемент, т. е.

чтобы после исключения из списка он оставался доступным и с ним можно

было бы выполнять некоторые действия (например, вставить его на другое

место в списке или освободить занимаемую им память с помощью dispose).

Третье присваивание выполняется для того, чтобы сделать исключение

окончательным, т. е. чтобы из исключенного элемента по ссылке нельзя было

попасть в список, из которого этот элемент исключен.

Таким образом, операции включения и исключения элементов представляют

собой изменение значений полей ссылочного типа некоторых элементов

списка. Однако рассмотренные методы включения и исключения не подходят

для включения нового элемента в начало списка и для исключения первого

элемента списка, так как у первого элемента нет предшествующего. Пусть по-

прежнему значением переменной p типа TPtr является _______ссылка на первый

элемент списка целых чисел. Для того чтобы включить в начало списка новый

элемент, содержащий число 17, нужно выполнить действия:

New( r ); r^.inf:= 17; r^.link:= p; p:=r;

Для исключения первого элемента из списка нужно выполнить:

R:=p; p:=p^.link; r^.link:= nil;

То, что включение (или исключение) в зависимости от местоположения

элемента в списке выполняется по разному, доставляет неудобства при

программировании. В программах приходится предусматривать

дополнительные проверки для того, чтобы выполнить включение или

исключение одним из двух способов. Чтобы сделать действия, выполняемые

при включении элемента в список (исключение элемента из списка),

единообразным, применяется следующий прием. В начало каждого списка

добавляется заглавный элемент. Он никогда не исключается из списка и перед

ним в список никогда не включается новые элементы. Информационная часть

заглавного элемента или не используется вообще, или используется для

205

специальных целей. Например, в случае списка целых чисел она может

содержать число, равное количеству элементов списка. Добавление заглавного

элемента в список приводит к тому, что теперь у всех элементов, в том числе и

у первого элемента, имеется предшественник, и действия по включению новых

элементов в список (или исключению элементов из списка) проводятся одним

способом.

2. Разобрать пример задачи:

Создать список, информационная часть которого содержит фамилии студентов.

Распечатать созданный список.

Построение выполняется до нажатия клавиши <enter> вместо ввода фамилии.

ПРОГРАММА:

Type

p_stud = ^ student;

student = record

name : string[20];

next : p_stud;

end;

var

head: p_stud; {начало списка}

curr : p_stud;

buf : string[20];

Begin

Repeat

Write(‘Фамилия? ‘);

Readln(buf);

If length(buf) <> 0 then

Begin

New(curr);

curr^.name := buf;

curr^.next := head;

head := curr;

end;

until length(buf) = 0;

writeln(‘***введенный списоr***');

curr := head;

while curr<> nil do

begin

writeln(curr^.name);

curr:= curr^.next

end;

readln

end.

3. Внимательно прочитать условие задачи согласно варианта.

4. Составить алгоритм решения задачи.

5. Реализовать алгоритм на языке Turbo Pascal.

206

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО ВЫПОЛНЕНИЯ

1.Дан однонаправленный список. Информационная часть списка содержит

целые числа. Вычислить среднее арифметическое элементов списка.

2.Дан однонаправленный список. Информационная часть списка состоит из

символов. Заменить в списке символ «а» на «д».

3.Дан однонаправленный список. Поменять местами первый и последний

элементы непустого списка L.

4.Описать процедуру или функцию, которая переносит в конец непустого

списка L его первый элемент.

5.Описать процедуру или функцию, которая вставляет в список L новый

элемент E1 за каждым вхождением элемента E.

6.Описать процедуру или функцию, которая вставляет в непустой список L

пару элементов E1, E2 перед его последним элементом.

7.Описать процедуру или функцию, которая удаляет из списка L за каждым

вхождением элемента E один элемент, если такой есть и он отличен от E.

8.Описать процедуру или функцию, которая удаляет из списка L все

отрицательные элементы (инф. часть = real).

9.Описать процедуру или функцию, которая проверяет есть ли в списке L

хотя бы два одинаковых элемента.

10. Описать процедуру или функцию, которая которая переносит в начало

непустого списка L его последний элемент.

11. Описать процедуру или функцию, которая добавляет в конец списка L1

все элементы списка L2.

12. Описать процедуру или функцию, которая вставляет в список L за

первым вхождением элемента E все элементы списка L1, если E входит в L.

13. Описать процедуру или функцию, которая в списке L из каждой группы

подряд идущих равных элементов оставляет только один.

14. Описать процедуру или функцию, которая находит максимальный

элемент непустого списка L ( инф. часть = Real).

15. Описать процедуру или функцию, которая формирует список L,

включив в него по одному разу элементы, которые входят в список L1, но не

входят в список L2.

Форма отчета о выполнении лабораторной работы.

Отчет должен содержать:

1. Алгоритм решения задачи;

2. Программу реализации алгоритма;

3. Результат выполнения программы.

Блиц-тест.

1. Стек - это частный случай однонаправленного списка, в котором:

A) разрешается добавлять элемент в начало, а удалять любой элемент с конца;

B) разрешено добавлять и удалять элементы с одного конца, который называется

вершиной;

C) определена связь между последним и первым элементом;

D) разрешается добавлять элемент в конец, а удалять с начала;

E) любой из перечисленных вариантов;

2. Очередь - это частный случай однонаправленного списка, в котором:

A) разрешается добавлять элемент в начало, а удалять любой элемент с конца;

207

B) определена связь между последним и первым элементом;

C) разрешено добавлять и удалять элементы с одного конца, который называется

вершиной;

D) любой из перечисленных вариантов;

E) разрешается добавлять элемент в конец, а удалять с начала;

3. К нелинейным связанным структурам относятся:

A) Стеки, очереди, списки

B) Деревья, сети

C) Стеки, деревья

D) Списки, очереди, сети

E) Списки, сети

Контрольные вопросы.

1. Укажите принципиальное отличие статических переменных от динамических.

2. Поясните роль базового типа при работе с указателями.

3. Укажите причины использования динамических переменных.

4. Можно ли в качестве базового типа использовать тип, определяемый пользователем?

5. Ограничена ли динамическая память?

Глоссарий.

Адрес – это совокупность двух шестнадцатиразрядных слов, называемых сегментом и

смещением.

Сегмент – участок памяти, имеющий длину 64 кбайт и начинающийся с физического адреса,

кратного 16.

Смещение указывает, сколько байт от начала сегмента необходимо пропустить, чтобы

обратиться к нужному адресу.

Указатель – это переменная, которая в качестве своего значения содержит адрес байта

памяти. Указатели различают типизированные и нетипизированные.

Динамические структуры данных – это структуры данных с переменным числом

однотипных элементов. Каждый элемент имеет две части: информационную и ссылочную.

Линейные списки – это данные динамической структуры, которые представляют собой

совокупность линейно связанных однородных элементов, и для которых разрешается

добавлять элементы между любыми двумя другими, и удалять любой элемент.

Кольцевые списки – это такие же данные, как и линейные списки, но имеющие

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

Очередь – частный случай линейного односвязного списка, для которого разрешены только

два действия: добавление элемента в конец очереди и удаление элемента из начала очереди.

Стек - частный случай линейного односвязного списка, для которого разрешено добавлять

или удалять элементы только с одного конца списка, который называется вершиной стека.

Деревья – это динамические данные иерархической структуры произвольной конфигурации.

Элементы дерева называются вершинами (узлами).

Пирамидой (упорядоченным деревом) называется дерево, в котором значения вершин (узлов)

всегда возрастают или убывают при переходе на следующий уровень.