Динамические информационные структуры

Упражнение № 26. Линейные списки (основные операции).

Создание и просмотр списка

Пример. Сформировать список, содержащий целые числа 3, 5, 1, 9.

Решение. Определим запись типа 5 с полями, содержащими характеристики дан­ных — значения очередного элемента и адреса следующего за ним элемента.

Туре ЕХЗ = ^А3; 3=Кесог< 1 Эа1: а: 1п1: едег; Ыех1:: ЕХЗ;

Еп< 1;

Чтобы список существовал, надо определить указатель на его начало. Опишем переменные: Уаг и, х: ЕХЗ;

Таким образом, мы описали ссылочный тип, с помощью которого можно со­здать наш связанный однонаправленный список:

 

Создадим первый элемент:

Ыем(и); {выделим место в памяти для переменной типа 5}. ЫехЪ: =пл.1; {указатель пуст}

. Ба1: а: =3; {информационное поле первого элемента}

" 1 *	N11
^ *

иА.Ыех1: иА. 0а1; а

 

Продолжим формирование списка, для этого надо добавить элемент в конец списка.

х: =и; {введем вспомогательную переменную указательного типа, которая будет хранить адрес последнего элемента списка. Сейчас последний элемент списка совпадает с его началом}

 

	N11

Таким образом, к области памяти (закрашена на рисунке) можно обратиться через два указателя

иА.Ые'хЪ хА.Ыех1: иА. 0а1; а хА.Ыех1:

 

Ыем (х^л.ЫехЪ);

о-

{выделим область памяти для следующего элемента списка}

х: =х^л. Ыех1:; {переменная х принимает значение адреса выделенной области па'мяти}

\	/
У	ч

 

х^л. Ба1: а: =5; {определим значение этого элемента списка}

		N11

 

х^л.Ыех1:: =Ы11;

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

Ргосейиге 1пл_1: (Уаг и: Ехз); {создание списка и} Уаг х, у: Ехз;

01дИ:: Гп'Ьедег; {значение информационной части элемента списка} Вед1п

ДОгл_1: е1п (' Введите список '); и: =N11; {список пуст}

^г11: еЪп (¹ Введите элементы списка. Конец ввода О¹); Кеа< 3 (В1дл_1:); МЪИе О1д1'Ь< > 0 Во Вед1п

Ыем(у); {формирование элемента списка} у^А у^А. ВаЬа: =01д1^:;

и=пИ ТЬеп и: =у {вставляем первый элемент списка} Е1зе х^А.Ыех1:: =у; {вставляем элемент в конец списка} х: =у;

{переносим значение указателя на последний элемент списка} Кеас1 (01дИ:); Епй;

Югл.1: 'е1п; Епй.

Выполним следующие действия: Ыем(х); {создание новой динамической переменной}

хА. с1а" Ьа: =7; {информационное поле созданного элемента} хА. пех-Ь: =и; {присоединим элементы списка и к созданному элементу}

и: =х; {изменим значение указателя начала списка}

Нам необходимо получить список, изображенный на рисунке:

 

 

 

 

 

 

 

Просмотр списка. Просмотр элементов списка осуществляется последовательно, начиная с его начала. Указатель р последовательно ссылается на первый, второй и т.д. элементы списка до тех пор, пока весь список не будет пройден. При этом с каждым элементом списка выполняется операция Ор. Начальное значение р — ад­рес первого элемента списка /? ^А.

ШНе р указывает не на конец списка Во

Вед±п

выполнить с элементом р^А операцию Ор; перейти к следующему элементу

Епс1;

Пусть Ор(р^) — это вывод элемента /? ^А на экран.

Если р указывает на конец списка, то его значение равно №Ь, то есть:

ШНе р< > ЫИ Во

Ведхп

ОДгл_1: е (р^А, ' '); р: =р^А. Ыех1:;

Епс1;

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

Решение. После ввода очередного числа с клавиатуры определяем его место в списке. Заметим, что при этом элемент может быть вставлен либо в начало списка, либо в конец его, либо во внутрь. Первый и второй случаи рассмотрены выше. Остановимся на третьем случае.

Для того чтобы вставить в список элемент со значением э^дИ: между двумя элементами, надо найти эти элементы и запомнить их адреса (первый адрес — в переменной йх, второй — 6 рх), после чего установить новые связи с перемен­ной, в которой хранится значение.

Графически это можно представить так:

Приведем процедуру 1пзл_п1: о, вставляющую в список элемент, переданный ей как параметр. (Адрес первого элемента списка хранится в глобальной переменной и.) Ргосес1иге 1пзл.п1: о (01дл-1:: 1п1: едег; Уаг и: Ехз); {вставка заданного элемента в список} Уаг с1х, рх, х: Ехз; Ведхп Ыем(х); хА.с! а1: а: =01д11:; хА. пех1:: =N11,; {если список пуст, то вставляется первый элемент} И (и=М1) ТЪеп и: =х Е1зе {если список не пуст, то просматриваем его до тех пор, пока

 

не отыщется подходящее место для х^А или не закончится список} Вед±п

с1х: =и; рх: =и;

ГОЪИе (рхОЫИ) Апс1 (рх^А. с! а1: а< =01д11:) Оо Вед±п с1х: =рх; рх: =рх^А. пех-Ь; Епс!; 15 рх=Мл_1 {пройден весь список}

ТЬеп с1х^А. пех*:: =х {элемент добавляется в конец списка}

Е1зе {пройден не весь список}

Вед±п

х^А. пех'Ь: =рх;

рх=и ТЬеп и: =х {вставляем в начало списка} Е1зе с! а^А. пех'Ь: =х; {вставляем внутрь списка} Епс!; Епс!; Епс!;

Вед±п {основная программа} и: =М1Ь; {список пуст}

Шгл_1: е1п (¹ Введите элемент. Окончание ввода О')/

Кеас! (01дИ:);

№Ы1е р1д1'Ь< > 0 Во Вед±п

1п5л_пТо (01дл_1:, и); Кеас! (01дИ:); Епс!;

ДОгл_1: е1п;

Мг11: е1п (¹ список: '); Ргл_п1: (и); {вывод списка} Епс!.

Пример. Удалить из заданного списка все вхождения элемента с заданным зна­чением информационной части.

Решение. Обозначим и — исходный список, 01дл_1: — значение информацион­ной части удаляемого элемента. Удалить элемент можно из любого места списка. Опишем процедуру удаления элементов из списка:

Ргосейиге 0е1(01дл_1:: 1п1: едег; Уаг и: Ехз); Уаг х, с1х: Ехз; Вед±п х: =и;

ИЪИе хОЫл.1 Во

15 х^А. 0а^а=< Ид1^ ТЬеп

Вед±п

15 х=и ТЪеп Вед±п и: =и^А.Ыех1:; 01зрозе (х); х: =и Епс! Е1зе

Вед±п с! х^А.Ыех1:: =х^А.Ыех1:; 01зрозе (х); х: =с! х^А. Ыех1:; Епс!; Епс!;

Е1зе Вед±п с1х: =х; х: =х^А.Ыех1:; Епс!; Епс!;

Основная программа может иметь следующий вид: Вед±п

1пл_1: (и); {формирование списка} Ргл_п1: (и); {вывод списка}

Югл.'Ье (¹ Введи число: '); Кеас11п (01дИ:); Ве1 (В±д±Ъ, и); Ргл_п1: (и) Епс!.

Ргодгат Ехатр1е_56; Туре С1111с1геп=^АС1111с1; СМ1с! =Кесог< 1

ВаЬа: 1п" Ьедег; ЫехЪ: СЪлПйгеп; Епс1;

Уаг сл_гс1: СЫ1с1геп; п, к: 1п" Ьедег;

Ргосейиге 1пл_1: (Уаг и: СЫ1с1геп; Уаг к: 1п" Ьедег); Уаг х, у: СЪИйгеп; 1: 1п" Ьедег; Ведхп

Югл_" Ье (¹ Введите число детей: ')/ КеасИп (п);

Юг Не (¹ Введите число слов в считалочке: ');

КеайЬп(к);

Еог л_: =1 То N с! о

Ведхп

Ыем(х); х^А. с! а" Ьа: =1;

Щ и=ЫИ ТЬеп и: =х Е1зе у^А.пех1:: =х; у: =х; Епс1;

х^А. пех-Ь: =и; Епс1;

Ргосейиге Ргл_п1: (и: СМ1с1геп); Уаг х: СЪлПйгеп; Ведхп х: =и; КереаЪ

Ш±Ье (х^А. Оа" Ьа, "); х: =х^А. Ыех" Ь; 0п" Ы1 х=и; КеасИп; Епс1;

Ргосес1иге Оаше(и: СМ1с1геп); Уаг х: СМ1с1геп;

1: 1п" Ьедег; Ведхп х: =и; КереаЪ

Пример 56. N детей располагаются по кругу. Начав отсчет от первого, удаляют каждого к-го, смыкая при этом круг. Определить порядок удаления детей из круга. Решение. Для хранения данных об участниках игры используется список.

Еог л_: =1 Ьо к-1 с! о Ведхп х: =и; и: =и^А.пех1:; Епс1;

(и^А. Оа*: а, ¹: '); х^А. пех*:: =и^А.пех*:; сИзрозе (и); и: =х; Рг1п1: (и); Ш-ЬИ и=и^А.пех*:; Епс1; Вед1п

1п11: (с1гс1); Рг1п1: (сл.гс1); Саше (с: 1гс1); КеасИп; Епс1.

Упражнение № 27. Стек

Стек — упорядоченный набор элементов, в котором добавление новых эле­ментов и удаление существующих производится с одного конца, называемого вер­шиной стека.

Туре ЕХ5Т=^А5Т; 5Т=Кесог< 1

Ба-Ьа: 1п*: едег; ЫехЪ: ЕХ5Т;

Еп< 1;

Уаг ЗЪаск: ЕХ5Т;

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

Ргосейиге Югл_1: е51: аск (Уаг и: ЕХ5Т; сИдИ:: 1п*: едег); {запись в стек}

Уаг х: ЕХ5Т;

Вед1п

Ыем(х); {создание нового элемента стека} х^А. Ва^а: =6.±д±Ь;

х^А.Ыех1:: =и {созданный элемент определить как вершину стека} и: =х; Епс1;

Основная программа формирования стека будет иметь вид:

Уаг ЗЪаск: ЕХ5Т; {текущая переменная} сИдл-Ъ: 1п1: едег; Вед1п

5" Ьаск: =N11;

^г1" ЬеЪп (¹ Введите элементы стека. Окончание ввода - О¹); Кеас! (МдИ:); •ШгИе В±д±^< > 0 Во Ведл.п

Мг11: е51: аск (5*: аск, сИдИ:); Кеас! (сИд'И:); Еп< 1;

Епс!.

Извлечение элемента из стека. В результате выполнения этой операции некото­рой переменной / должно быть присвоено значение первого элемента стека и из­менено значение указателя на начало списка.

Ргосейиге КеайЗЪаск (Уаг и: ЕХЗТ; Уаг л.: 1п1: едег);

Уаг х: ЕХЗТ;

Вед1п

1: =и^А. Ба1: а; х: =и; и: =и^А.Ыех*:; Бхзрозе (х); Еп< 1;

Пример 57. Написать программу, проверяющую своевременность закрытия скобок в строке символов.

Для решения задачи определим стек, элементами которого являются символы:

Туре ЕХ5Т: ^А5Т; 5Т=Кесогс1

ВаЬа: СЬаг; Ыех!:: ЕХЗТ;

Епс1;

Будем двигаться по строке а: до ее конца. Если в процессе просмотра

встретится одна из открывающих скобок — {, (> [ — занесем ее в стек. При обнару­жении закрывающейся скобки, соответствующей скобке, находящейся в вершине стека, последняя удаляется. При несоответствии скобок выдается сообщение об ошибке.

Ргодгат Ехатр1е_57; Туре Ехз1: =^Аз1:; 31: =Кесогс1

Ыех!:: ехз!:; Ба!: а: СЬаг; Епс1; Уаг а: 31: гз_пд; Г: Воо1еап; 1: 1п!: едег;

Ргосейиге ЭДгИ: е51: аск (Уаг х1: ехз!:; сгСЬаг); {Процедура занесения элемента в стек} Уаг и: ехз!:; Ведхп

Ыем(и); и^А.Ба1: а: =с; и^А. пех!:: =х1; х1: =и Епс1;

Ргосейиге Йе1з1: аск (Уаг х1: ехз1:); {Процедура удаления верхнего элемента стека} Уаг и: ехз!:; Ведхп

и: =х1; х1: =х1^А. пех!:; Б1зрозе(и); Епс1;

Ргосейиге Зо1Vе (а: 5!: гз_пд); {Процедура проверки правильности рас­становки скобок} Уаг зЪаск: Ехз!:; Ведхп

з!: аск: =N3.1; л_: =1;

ШНе (±< =1епдЪЪ. (а)) Апй ± Во

Ведхп

1Г (а[1] = ' (')Ог (а[1] = '{')0г(а[1] = ' [') ТЬеп Югл.!: ез!: аск (зЪаск, а [л.])

Е1зе И (а[^]=^, )^, ) Ог (а[1]='}') Ог (а[±]]') ТЪеп Огй (з1: аск^А.йа1: а) -Огй (а [з_]) < =2 ТЪеп йе1з!: аск (зЪаск) Е1зе ±: =Еа1зе; 1пс (1);

Еп< 1; Епс1;

Вед±п {Основная программа}

ДОгл_1е1п (¹ введите строку¹); КеасИп (а); ^: =Тгие;

15 а< > ¹¹ ТЬеп

Вед±п

Зо1Vе(а);

15 5 ТЪеп ДОгл_-Ье1п (¹ все скобки расставлены верно¹) Е1зе ДОгл_1: е1п (¹ скобка закрыта преждевременно¹);

Епс!;

Е1зе ^Г11е1п(¹ строка пуста¹); КеасИп; Епс1.

Пример 58. Написать программу вычисления значения выражения, представленно­го в обратной польской записи.

Обычная запись: Обратная польская запись:

(, Ь+с)*сI Ъс+с! *

а+(Ъ+с)*с1 аЪс+с! *+

Решение. Логика решения этой задачи не вызывает трудностей. Просматривая строку, анализируем очередной символ, если это:

• число, то записываем его в стек;

• знак, то достаем два элемента из стека, выполняем математическую опера­цию, определяемую этим знаком, и заносим результат в стек.

Ргодгат Ехатр1е_58; Туре Ехз1: =^лз1:; 51: =Кесогс1

Эа-Ьа: Кеа1; N6x1:: ехз-Ь; Епс1;

Уаг аа: 3-Ьгл_пд; з" Ьаск: ехз1:; л_, к: 1п1едег; х, у: Кеа1;

Ргосейиге ДОгл_1ез*: аск (Уаг х1: ехз!:; с: Кеа1); {запись нового элемента в стек} Уаг и: ехз1:; Вед±п

Ыем(и); и^А.Оа" Ьа: =с;. пех!: =х1; х1: =и Епс1;

Ргосейиге Кеас1з1: аск (Уаг х1: ехз1:; Уаг с!: Кеа1); {извлечение элемента из стека} Уаг и: ехз1:; Ведл.п

с1: =х1^А. с! а1а; и: =х1; х1: =х1^А. пех1:; 01зрозе(х1); Епс1;

Ргосес1иге Орега-Ыоп (а, Ъ: Кеа1; с: СЪаг);

{выполнение действия и занесение результата в стек}

Уаг с!: Кеа1;

Вед±п

Сазе с 05

' + ': с!: =а+Ъ; й: =Ъ-а; '*': й: =а*Ъ; '/': с!: =Ь/а;

Е1зе Югл." Ье1п (¹ ошибка в записи¹); Епс!;

Югл.!: ез!: аск (з" Ьаск, с!); Епс!;

Ведхп {основная программа}

Югл." Ье1п (¹ введите выражение в обратной польской записи¹); КеасИп(аа); ЗЪаск: =N11;. Еог 1: =1 То 1епд" Ы1 (аа) Бо Ведхп

Уа1(аа[л_], х, к);

1Г к=0 ТЪеп ДОгНез^аск (зЪаск, х);

Е1зе

Ведхп

КеайзЪаск(зЪаск, х);

Кеас1з" Ьаск (зЪаск, у); Орега-Ыоп (х, у, аа [л.]); Епс!; Епс!;

Югх-Ье (¹ ответ: ¹); Югл." Ье1п (з!: аск^А. йаЪа); КеасИп; Епс!.

Упражнение № 28. Очереди

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

Туре ЕХ0=^А0; 0 =Кесогс!

0а1: а: 1п" Ьедег; N6x1:: ЕХО; Епс!;

Над очередью определены две операции: занесение элемента в очередь и извле­чение элемента из очереди. Поскольку очередь представлена списком, занесение элемента в очередь соответствует занесению элемента в конец списка. Ргосейиге ТОгхЪеО (Уаг х1, х2: ЕХО; с: 1п1: едег); Уаг и: ЕХО; Ведхп

^м(и); и^А. с1а" Ьа: =с; и^А. пех!:: =ШЪ; 1Г х1=ШЪ ТЬеп х1: =и {если очередь пуста} Е1зе х2^А. пех!:: =и; {заносим элемент в конец списка} х2: =и; Епс!;

Основная программа, создающая очередь, может быть такой:

Ведхп

х1: =К1Ъ; х2: =ШЪ;

Шг11: е1п ('Введите элементы очереди. Конец ввода - 0'); Кеас! (01дИ:);

ШИе Б1д: И: < > 0 Бо

Ведхп

МгНеО (х1, х2, Бхдх!:); Кеас! (Бхдх!:); Епс!; Епс!.

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

Ргосейиге Кеас1о (Уаг х1, х2: ЕХО; Уаг с: 1пЪедег); Уаг и: ЕХО;

Гипс^л-оп Ыи1 (х1: ЕХО): Воо1еап; Ведл.п

Ыи1: = (х1=ЫИ); Епс1; Ведл.п

15 Ыи1(х1) ТЬеп (^ЛОчередь пуста¹)

Е1зе

Вед1п

с: =х1^А. Оа" Ьа; и: =х1; х1: =х1^А.Ыех" Ь; 01зрозе(и);