[ЗВУК]
[ЗВУК] Рассмотрим задачу
формирования новой очереди из элементов исходного списка, кратных 3.
Здесь мы предполагаем, что список у нас предварительно сформирован и напоминаю
вам, что когда мы работаем со списком, который был предварительно создан,
то решение задач не зависит от того, стек мы создавали или очередь,
потому что стек отличается от очереди только порядком расположения полей данных.
При решении этой задачи мы с вами будем использовать следующие указатели.
first будет указателем на начало исходного списка.
FirstNew будет указателем на начало нового формируемого списка.
current будет указатель на текущую запись в исходном списке.
Далее, LastNew будет указателем на последнюю добавляемую запись в новом
списке.
И currNew будет указатель на текущую запись нового списка,
туда мы будем с вами копировать числовое поле из исходного списка.
Таким образом, все названия переменных, в которых есть слово New, относится к новому
списку, а те, в которых этого слова нет, будут относиться к исходному списку.
Здесь параметрами являются first — это адрес начала
исходного списка, это параметр значения,
потому что он не меняется в процессе выполнения нашей процедуры.
FirstNew, адрес начала нового списка, является параметром переменной,
потому что мы будем здесь его изменять.
Далее объявляем локальные переменные — current, LastNew и currNew.
Затем мы с вами берем указатель
current текущий и ставим его в начало исходного списка.
Далее мы с вами говорим, что изначально новый список является пустым,
то есть адрес его начала инициализируется константой nil.
Пока что там нет никаких записей.
Если ни одна запись не попадет в новый список,
то этот указатель так и останется равным nil.
Далее мы с вами должны пройти по всем записям исходного списка.
Пока текущий указатель отличен от nil, то есть пока мы не дошли до конца списка,
мы с вами будем проделывать следующие действия: если у нас в поле данных
исходного списка находится элемент кратный 3, то есть остаток от деления
этого числа на 3 равен 0, то мы с вами должны поместить элемент в новый список.
При этом мы с вами должны рассмотреть два случая: либо этот элемент помещается на
первое место в этот список, либо это очередной добавляемый элемент.
Если это первая запись, которую мы добавляем в новый элемент,
то есть если указатель FirstNew по-прежнему равен nil,
то тогда мы должны выделить память для первой записи нового списка.
То есть сделать New для FirstNew и LastNew так же присвоит этот адрес, то есть
оба этих указателя будут показывать на эту запись — первая запись и она же текущая.
Все остальные действия,
которые у нас происходят при выполнении условия того, что элемент кратен 3,
будут происходить, как для первой записи, так и для всех остальных.
Далее мы с вами CurrNew должны присвоить LastNew,
то есть запомнить адрес предыдущей записи из нового списка и
затем сделать New LastNew, то есть выделить память для очередной записи.
Далее в переменную CurrNew разадресация поле info мы присвоим currinfo.
То есть скопируем поле данных из исходного списка в новый.
Далее CurrNew next мы должны присвоить LastNew,
то есть связать эти два элемента так, чтобы образовывалась очередь.
И далее мы с вами закрываем условие того,
что у нас происходило добавление.
Теперь в любом случае, когда происходило добавление записи в новый список
и когда оно не происходило, мы в исходном списке перемещаем указатель
на следующую запись, то есть curr присваиваем curr разадресация next,
теперь этот указатель показывает на очередную запись.
И наш цикл завершается тогда,
когда значение когда значение указателя curr станет равным nil, то есть,
когда мы с вами обработали последнюю запись и вышли за пределы списка.
Теперь мы с вами должны посмотреть,
поместились ли какие-нибудь данные в новый список?
Если firstNew отлично от nil, то есть если хотя бы одна запись в наш список была
добавлена, то мы тогда должны завершить формирование списка.
Что мы при этом делаем?
CurrNew в поле next присваивается nil, это признак того,
что в этом месте находится конец нового списка.
Далее мы удаляем лишнюю запись, dispose LastNew освобождает память,
и закрываем соответствующее условие, и на этом наша процедура будет завершена.
Рассмотрим, как работает программа,
которая создает из элементов исходного списка в полях данных,
в которых находятся значения кратные 3, новый список — очередь.
Исходный список у нас так же будет очередью.
Для того чтобы наша программа работала, нам потребуется: объявить тип, который мы
с вами используем при создании связанных списков — линейных и однонаправленных.
Далее у нас есть переменные first и firstNew, которые являются указателями,
соответственно, на начало исходного списка и формируемого списка.
Далее у нас находится процедура создания линейной очереди,
которую мы с вами в одном из предыдущих уроков рассматривали подробно.
И далее мы записываем процедуру NewList,
которая будет создавать новый список.
Процедура print, которая так же нам знакома, будет выводить список на экран и
затем у нас идет главная программа, в которой происходят следующие действия.
Сначала мы формируем исходную очередь, называем процедуру формирование очереди,
затем выводим исходный список на экран, использую процедуру print.
Потом вызываем процедуру NewList,
на входе у которой указатель first, адрес начала исходного списка,
а на выходе указатель FirstNew, адрес начала полученного списка.
И после этого при помощи процедуры print мы выводим новый список.
Теперь давайте посмотрим подробнее, как работает процедура NewList.
Параметр first является параметром значением,
потому что от наших действий этот указатель не будет меняться.
Затем firstNew это параметр-переменная,
потому что этот указатель вычисляется здесь, в этой процедуре.
Вначале curr присваивается first,
то есть текущий указатель поставлен на начало исходного списка.
Далее FirstNew присваивается nil — новый список «пусто».
Теперь, пока curr не равно nil, то есть пока мы не пройдем весь список,
мы на каждом шаге цикла выполняем следующие действия.
Поверяем, нужно ли копировать информационное поле из исходного списка в
новый, если currinfo кратно 3, то есть остаток от деления этого числа
на 3 равен 0, то тогда мы должны поместить элемент в новый список.
Здесь рассматривается два случая — если FirstNew равен nil,
то новый список еще пуст.
В этом случае мы должны выделить память для первой записи этого
списка и настроить указатель LastNew на ту же область памяти.
Далее действия, которые выполняются только на первом шаге, когда мы формируем новый
список, заканчиваются, а остальные действия будут у нас выполняться
на каждом шаге в не зависимости от того, первая запись или не первая,
когда мы с вами будем добавлять новое число во второй список.
CurrNew присваивается LastNew, то есть запоминается адрес предыдущей записи.
Далее New LastNew выделяет память для новой записи и затем
CurrNew next присваивается LastNew,
то есть устанавливается связь между предыдущей и текущей записью.
Далее вне зависимости от того, копировали ли мы данные из исходного списка в новый,
мы переходим к новой записи в исходном списке.
На этом цикл заканчивается и дальше мы должны понять, есть ли у нас новый список?
Если он сформирован, то есть указатель FirstNew не равен nil,
то тогда мы проделываем следующие действия.
CurrNew next присваиваем nil, то есть вносим признак конца списка,
и удаляем запись LastNew последнюю, потому что в данную эту запись мы не записывали.
Теперь запустим программу и попробуем посмотреть различные случаи ее работы.
Попробуем ввести следующие данные.
1, 2, 3, 6, 5, 9 и 12.
Для того чтобы показать, что ввод данных завершен, ввожу ноль.
Мы с вами видим, что сформирован исходный список, он является очередью,
то есть данные в этом списке появляются в том же порядке, в котором они были в
исходном, и затем новый список, который является так же очередью,
содержит те элементы исходного списка, в которых поля данных были кратны 3.
И новый список так же является очередью,
то есть в нем записи появляются в том же порядке, в котором они были в исходном.
То есть 3 — первая, затем 6, 9 и 12.
Запустим программу еще раз и попробуем сформировать список,
в котором нет элементов кратным 3.
Допустим, 1, 2, 4, 8 и 7.
Завершаю ввод данных.
Мы с вами видим, что исходный список у нас сформирован, а новый список пуст.
То есть наша программа работает правильно и в том случае,
когда новый список будет создан, и в том случае, когда он является пустым.
[ЗВУК]
[ЗВУК]
[ЗВУК]