Текст книги "Песни о Паскале (СИ)"

Автор книги: Олег Деревенец

сообщить о нарушении

Текущая страница: 22 (всего у книги 29 страниц)

PrintList;       { Распечатка списка }

repeat       { Цикл попыток поиска в списке }

      Write('Укажите номер авто = '); Readln(N);

      if N>0 then begin

      P:= Find(N);

      if Assigned(P)

            then Writeln(P^.mNumber, '':3, P^.mFam)

      else Writeln ('Не найдено!');

      end;

until N=0

end.

Простенькая функция Find ищет в списке элемент с нужным номером автомобиля, и возвращает указатель на этот элемент списка. При неудачном исходе функция возвращает NIL.

В главной программе список заполняется записями со случайными номерами автомобилей. Так же «случайно» все владельцы оказались однофамильцами (придумайте тут что-нибудь!). Далее организован цикл с запросом искомого номера, поиском и печатью результата.

Сортированные списки

Итак, мы построили список и организовали в нём поиск данных. Довольны ли мы результатом? Для начала – неплохо, но если копнуть глубже…

Войдите в положение полицейского, перед которым мелькают сотни машин. Сколько из них числятся в угоне? Мизер! Но обработка каждого автомобиля вынуждает программу пройти по всему списку, – ведь он не сортирован! А опыт показал, что там, где порядок, все ищется быстрее. Действительно, если расположить записи в порядке возрастания номеров, то просмотр списка можно прекращать при достижении номера больше искомого. При этом среднее число шагов поиска сократится вдвое.

Есть и другая причина для сортировки списка – желание распечатать данные в удобном порядке, например, по алфавиту. Честно говоря, список – это не лучшая структура для поиска и сортировки. Для этого лучше подходят другие динамические структуры – деревья, о которых можно узнать из литературы по алгоритмам. Но сейчас мы заняты списком и будем сортировать его.

Здесь не годятся алгоритмы для массивов. Ведь в списке нет индексов, к его элементам можно добраться лишь по цепочке ссылок. Зато у списка есть другое достоинство: для перестановки элементов не надо перемещать записи в памяти, – достаточно перенацелить указатели. Это легко сделать при вводе данных из файла, – так совмещается ввод списка с его сортировкой.

Вот пример с тремя записями (на рис. 125 и рис. 126 показаны лишь номера автомобилей). Предположим, что список содержит записи с номерами 20, 30 и 40, и мы вставляем запись с номером 35. После создания переменной p^ надо найти предыдущий элемент, чтобы подцепить к нему новый. Обозначим указатель на такой элемент буквой q. Найдя элемент q (об этом чуть позже), вставку делаем на «раз и два» (рис. 125).

      p^.mNext:=q^.mNext; { связываем текущий со следующим }

      q^.mNext:=p;       { связываем предыдущий с текущим }

Рис.125 – Состояние списка перед вставкой записи с номером 35

Состояние списка после вставки элемента показано на рис. 126.

Рис.126 Состояние списка после вставки записи с номером 35

Теперь рассмотрим два особых случая. Первый – когда список ещё пуст, и вставляемая запись будет первой и последней, здесь вставка делается так:

      List:= p; { если список пуст, голова указывает на новую запись }

Второй случай, – когда номер в первой записи окажется больше вставляемого. Тогда новую запись вставим в начало списка.

      p^.mNext:=List; { первый становится вторым }

      List:=p;       { а текущий– первым }

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

      q:= List; { Поиск места вставки начинаем с головы, здесь List<>nil }

      while Assigned(q^.mNext) and (q^.mNext^.mNumber < aNumber)

      do q:=q^.mNext;

Здесь выражение q^.mNext^.mNumber соответствует номеру автомобиля в следующей за q записи.

Разобрав тонкости программы «P_54_3», предъявлю её во всей красе.

{ P_54_3 – Размещение данных в сортированном списке }

type PRec = ^TRec; { Тип указатель на запись }

      TRec = record       { Тип записи для базы данных }

      mNumber : integer;       { Номер авто }

      mFam : string[31]; { Фамилия владельца }

      mNext : PRec;       { Указатель на следующую запись }

      end;

var List : PRec; { Указатель на начало списка (голова) }

      { Размещение нового элемента в сортированном списке }

procedure AddToSortList(aNumber: integer; const aFam : string);

var p, q : PRec;

begin

New(p); { Создаем динамическую переменную-запись }

{ Размещаем данные в полях записи }

p^.mNumber:= aNumber; p^.mFam:= aFam;

p^.mNext:=nil;

{ Если список пуст… }

if not Assigned(List)

      then List:= p { если список пуст, голова указывает на новую запись }

      else begin { если список не пуст… }

      q:= List; { Поиск места вставки начинаем с головы }

      { Двигаемся по списку, пока следующий элемент существует

      и его номер меньше вставляемого }

      while Assigned(q^.mNext) and (q^.mNext^.mNumber < aNumber)

      do q:=q^.mNext;

      if q^.mNumber > aNumber then begin

      { вставка на первое место }

      p^.mNext:=List; { первый становится вторым }

      List:=p;       { а текущий – первым }

      end else begin

      { вставка в середине или в конце списка }

      p^.mNext:=q^.mNext; { связываем текущий со следующим }

      q^.mNext:=p;       { связываем предыдущий с текущим }

      end

      end

end;

{ Распечатка списка }

procedure PrintList;

{– взять из P_54_1 –}

end;

var i: integer;

begin {– Главная программа –}

List:= nil; { инициализация}

{ Заполнение списка }

for i:=1 to 20 do AddToSortList(100+Random(100), 'Деточкин');

{ Распечатка списка }

PrintList;

Readln;

end.

Разумеется, что проверку этой программы я возлагаю на вас.

Поиск в сортированном списке

Создав функцию поиска номера в сортированном списке, поставим победную точку. Будем искать запись, для которой номер в следующей за ней записи больше искомого (если следующая запись существует). Это условие совпадает с условием поиска при вставке в сортированный список. Найдя такую запись и сравнив её номер с искомым, сформируем результат: если номер найден, возвращаем указатель на эту запись, а иначе – NIL. Все это относится к программе «P_54_4».

{ P_54_4 – Поиск данных в сортированном списке }

type PRec = ^TRec; { Тип указатель на запись }

      TRec = record       { Тип записи для базы данных }

      mNumber : integer;       { Номер авто }

      mFam : string[31]; { Фамилия владельца }

      mNext : PRec;       { Указатель на следующую запись }

      end;

var List : PRec; { Указатель на начало списка (голова) }

      { Размещение нового элемента в сортированном списке }

procedure AddToSortList(aNumber: integer; const aFam : string);

{– взять из P_54_1 –}

end;

      { Распечатка списка }

procedure PrintList;

{– взять из P_54_1 –}

end;

      { Поиск в сортированном списке }

function Find(aNumber: integer): PRec;

var p : PRec;

begin

p:= List; { Поиск начинаем с головы }

{ Двигаемся по списку, пока следующий элемент существует

и его номер не больше искомого }

while Assigned(p) and Assigned(p^.mNext) and (p^.mNext^.mNumber <= aNumber)

      do p:=p^.mNext;

{ Если конец списка не достигнут и номер совпадает… }

if Assigned(p) and (p^.mNumber = aNumber)

      then Find:= p { то успешно! }

      else Find:= nil; { а иначе не нашли }

end;

var i, N : integer; P : PRec;

begin {– Главная программа –}

List:= nil;

for i:=1 to 20 do AddToSortList(100+Random(100), 'Фамилия, Имя');

PrintList;       { Просмотр списка }

repeat       { Цикл экспериментов по поиску в списке }

      Write('Укажите номер авто = '); Readln(N);

      if N>0 then begin

      P:= Find(N);

      if Assigned(P)

      then Writeln(P^.mNumber, '':3, P^.mFam)

      else Writeln ('Не найдено!');

      end;

until N=0

end.

Итоги

• Указатель на любой тип данных можно объявлять раньше типа, на который он ссылается.

• Односвязный список – это простейшая динамическая структура, отводящая под данные столько памяти, сколько им требуется.

• Элементы списка – это записи, содержащие в числе прочих данных указатель на следующую запись в списке.

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

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

• Сортировку списка можно совместить с его вводом.

А слабо?

А) Напишите функцию для подсчета элементов списка; она должна принимать указатель на голову списка, а возвращать целое число.

Б) Начертите блок-схему вставки записи в сортированный список.

В) Напишите процедуру для удаления первого элемента списка. Или слабо?

Г) Напишите процедуру сортировки уже готового списка. Подсказка: последовательно извлекайте элементы из несортированного списка и вставляйте в сортированный (потребуется две головы для двух списков).

Задачи на темы предыдущих глав

Д) В задаче 53-Г была представлена модель «глупого» винчестера. «Умный» винчестер отличается организацией внутренней очереди и челночным движением головки, которая следует попеременно то от внутренней дорожки к внешней, то обратно, попутно выполняя все накопившиеся в очереди запросы. Направление движения переключается, когда в текущем направлении не остается запросов, поэтому головка редко достигает крайних дорожек.

Ваша программа должна подсчитать общее время обработки запросов «умным» контроллером для набора данных из входного файла, составленного по правилам для задачи 53-Г. Создайте несколько наборов таких данных и сравните время их обработки двумя типами контроллеров: «умным» и «глупым».

Подсказка: для организации внутренней очереди контроллера здесь можно применить массив чисел (счетчиков). Каждый счетчик будет хранить текущее количество запросов для своей дорожки. При постановке запроса в очередь счетчик наращивается, а при извлечении уменьшается.

Глава 55

Слова, слова, слова…

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

Частотный анализ текста

Однажды разгорелся спор об известном романе «Тихий Дон», – некоторые литераторы усомнились в авторстве Михаила Шолохова. Их сомнения развеяли программисты, вычислившие частотные характеристики нескольких его произведений. Что это за характеристики такие?

Предположим, вы подсчитали, что слово «Паскаль» упомянуто в этой книге 150 раз, а всего в книге 10000 слов. Тогда относительная частота слова «Паскаль» в книге составит 150 / 10000 = 0,015 или 1,5%. Если найти частоту употребления других слов книги, и расположить эти результаты в некотором порядке, то получится картина, подобная отпечатку пальца. У разных авторов эти «отпечатки» разные, зато у одного автора в разных произведениях – очень похожи! Обработав таким частотным анализатором несколько книг Михаила Шолохова, специалисты сравнили результаты и обнаружили на романе «Тихий Дон» «пальчики» донского писателя.

Слово за слово

Итак, мы беремся за разработку слегка упрощенного частотного анализатора. Это опять тот случай, где заранее неизвестен объём обрабатываемых данных. В самом деле, определить приблизительное количество слов в тексте не так уж сложно: посчитаем их на одной странице и умножим на число страниц. Но сколько из этих слов несовпадающих, разных? Не слышу ответа!

Наша программа будет читать не романы, а текстовые файлы, – возьмем файл какой-либо из наших программ, и посчитаем в нём слова, составленные из латинских букв. Для упрощения программы русские слова считать не будем, и пропустим слова, состоящие из одной буквы. Зато примем в расчет слова с цифрами и знаками подчеркивания, например, такие.

Begin, NIL, P1, q2, Words_Count, _1_

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

Структура записи

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

      TRec = record { Тип записи для подсчета слов }

      mWord : string;       { Слово из текста – 256 байт }

      mCount : Longint;       { Счетчик слов – 4 байта }

      mNext : PRec;       { Указатель на следующий – 4 байта }

      end;

Сколько памяти займет один такой элемент? Сейчас посчитаем: 256+4+4=264 байта, – не так уж мало! Полагаю, что для слова достаточно и тридцати символов. Но, прежде, чем окончательно выбрать длину строки, открою небольшой секрет, – он касается выделения динамической памяти. Сколько бы памяти ни запросила программа, операционная система выделит кусочек, кратный восьми байтам. То есть, часть байтов в выделяемой порции может быть лишней. Значит, предпочтительный размер записи для динамических переменных кратен восьми байтам. В нашем случае размер записи можно уменьшить до 40 байтов, если объявить её так:

      TRec = record { Тип записи для подсчета слов }

      mWord : string[31]; { Слово из текста – 32 байта }

      mCount : Longint;       { Счетчик слов – 4 байта }

      mNext : PRec;       { Указатель на следующий – 4 байта }

      end;

С одной стороны, число 40 кратно 8, а с другой стороны, 31-го символа для слова вполне достаточно.

Алгоритм

Теперь обсудим алгоритм обнаружения и обработки слов. В чем состоит эта обработка? Найдя выделенное слово в списке, нарастим его счетчик – поле mCount, а если слова в списке ещё нет, добавим запись с этим словом и счетчиком, равным единице.

Можно придумать много способов выборки слов из файла. Один из них – построчная обработка, когда каждую строку можно обработать так.

1. Перекодировать все символы строки в верхний регистр.

2. Удалить из начала строки все символы, которые не являются латинской буквой или подчеркиванием, и, если строка стала пустой, то завершить процедуру.

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

4. Искать слово в списке.

5. Если слово найдено, нарастить его счетчик, а иначе вставить в список запись со счетчиком, равным единице.

6. Прейти к пункту 2.

В перечисленных действиях нет ничего нового. В самом деле, обработка строк – дело привычное, так же, как поиск в сортированном списке и вставка в него данных. Таким образом, нам остается лишь собрать все это воедино, что и сделано в программе «P_55_1».

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

{ P_55_1 – Частотный анализатор текста }

type

      PRec = ^TRec; { Тип указатель на запись }

      TRec = record { Тип записи для подсчета слов }

      mWord : string[31]; { Слово из текста }

      mCount : Longint;       { Счетчик слов }

      mNext : PRec;       { Указатель на следующий элемент }

      end;

var List : PRec; { Указатель на начало списка (голова) }

      { Поиск в сортированном списке }

function Find(const aWord: string): PRec;

var p: PRec;

begin

p:= List; { Поиск начинаем с головы }

{ Двигаемся по списку, пока следующий элемент существует

и слово в нём меньше искомого }

while Assigned(p) and Assigned(p^.mNext) and (p^.mNext^.mWord <= aWord)

      do p:=p^.mNext;

{ Если конец списка не достигнут и слово совпадает… }

if Assigned(p) and (p^.mWord = aWord)

      then Find:= p { … то успешно! }

      else Find:= nil; { … а иначе не нашли }

end;

      { Размещение нового элемента в сортированном списке слов }

procedure AddToSortList(const aWord : string);

var p, q : PRec;

begin

New(p); { Создаем динамическую переменную-запись }

{ Размещаем данные в полях записи }

p^.mCount:= 1; p^.mWord:= aWord; p^.mNext:=nil;

{ Если список пуст… }

if not Assigned(List)

then List:= p { …голова указывает на первую запись }

else begin

      q:= List; { Поиск места вставки начинаем с головы }

      { Двигаемся по списку, пока следующий элемент существует

      и его номер меньше вставляемого }

      while Assigned(q^.mNext) and (q^.mNext^.mWord < aWord)

      do q:=q^.mNext;

      if q^.mWord > aWord then begin

      { вставка на первое место }

      p^.mNext:=List;       { первый становится вторым }

      List:=p;       { а текущий– первым }

      end else begin

      { вставка в середине или в конце списка }

      p^.mNext:=q^.mNext; { связываем текущий со следующим }

      q^.mNext:=p;       { связываем предыдущий с текущим }

      end

      end

end;

      { Добавление слова либо увеличение его счетчика }

procedure AddWord(const aWord : string);

var P : PRec;

begin

P:= Find(aWord);

if Assigned(p)

      then Inc(P^.mCount)

      else AddToSortList(aWord);

end;

      { Выделение и добавление слов из прочитанной строки }

procedure AddLine(S: string);

const CLetter = ['A'..'Z','_'];

      CDigits = ['0'..'9'];

var W : string; i : integer;

begin

{ переводим все буквы строки в верхний регистр }

for i:=1 to Length(S) do S[i]:= UpCase(S[i]);

while Length(S)>0 do begin

{ удаляем все небуквы в начале строки }

while (Length(S)>0) and not (S[1] in CLetter) do Delete(S,1,1);

if Length(S)>0 then begin

      W:='';

      { копируем все буквы и цифры в слово W и удаляем из строки }

      while (Length(S)>0) and (S[1] in CLetter+CDigits) do begin

      W:= W+S[1];

      Delete(S,1,1);

      end;

      if Length(W)>1 then AddWord(W); { Если не буква, вставляем в список }

end;

end;

end;

      { Распечатка списка }

procedure PrintList(var F: text);

var P : PRec;

begin

Rewrite(F); P:= List;

while Assigned(P) do begin

Writeln(F, P^.mWord, '':(20-Length(P^.mWord)), P^.mCount:5 );

P:= P^.mNext;

end;

Close(F);

end;

var S: string; F: text;

begin {– Главная программа –}

List:= nil;

Assign(F, 'P_55_1.pas');

Reset(F);

while not Eof(F) do begin

Readln(F, S);

AddLine(S);

end;

Close(F); Assign(F, 'P_55_1.OUT');

PrintList(F); { Распечатка списка }

end.

Полагаю, что моих комментариев и вашего опыта хватит для понимания программы. Обязательно проверьте её. Вот результат исследования программой своего собственного текста (приведена только часть слов).

ADDLINE       2

ADDTOSORTLIST       2

ADDWORD       2

AND       6

ASSIGN       2

ASSIGNED       7

AWORD       10

BEGIN       14

CLETTER       3

А слабо?

А) Дополните программу средствами для подсчета:

• общего количества слов в файле;

• общего количества разных слов.

Напишите для этого подобающие функции.

Б) Измените программу так, чтобы при распечатке списка выводилась относительная частота слов в процентах от общего их количества с двумя знаками после точки.

В) Создайте программу для подсчета в файле слов, составленных из одних и тех же символов: цифр и букв, например: «end» и «deen», «121» и «221». Для каждой такой группы слов программа должна напечатать перечень входящих в них символов (каждый символ – по разу) и количество обнаруженных слов этой группы, например, для приведенных выше слов будет напечатано:

1 2 – 2

d e n – 2

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

Глава 56

И снова очереди, и снова стеки…

Новейшая версия полицейской базы данных и частотный анализатор текста укрепили ваш опыт по части динамических переменных. И все-таки, один момент нами упущен. Пока мы лишь добавляли данные в кучу, не утруждая себя её очисткой, – в решаемых задачах этого не требовалось. Но так будет не вечно, когда-то придется освобождать кучу от ненужных переменных. В этой главе мы рассмотрим два таких случая на примере знакомых нам очередей и стеков.

Шутить изволите?

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

end.

Close(F);

while Pop(S) do Writeln(F, S);

{ Пока стек не пуст, извлекаем и печатаем строки }

Assign(F, 'P_56_1.out'); Rewrite(F);

{ Открываем выходной файл }

Close(F);

end;

Приятель умолял Ника найти здесь ошибку.

Приняв во внимание 1-е апреля, Ник заподозрил розыгрыш и всмотрелся в эту абракадабру внимательней. Вскоре он сообразил, что строки в файле следуют в обратном порядке: последняя стоит первой, а первая – последней. Достойным ответом приятелю, – рассудил Ник, – будет правильный текст этой же программы. Но как переставить строки? Вручную, редактором текста? «Не царское это дело! – возмутился его разум, – пусть этим займется компьютер». И Ник написал программу для преобразования файла. Последуем за Ником.

Вы уже знакомы со стеком – временным хранилищем данных, из которого последний вставленный элемент извлекается первым (сообразно с дисциплиной LIFO). Стек – отличное средство для перестановки данных шиворот навыворот и задом наперед. Хранилищем данных в нашем первом стеке была строка, а хранимыми элементами – символы (загляните в главу 45). Скромные возможности того стека не помешали нам решить задачу о сортировочной горке.

Но чаще в стеке надо сохранять не символы, а крупные и сложные элементы данных. Так будет и в программе Ника, где элементом данных является строка. Как организовать стек из строк?

Вспомним порядок элементов при вставке их в список: последний элемент оттесняет соседей, становясь на первое место. А это значит, что, извлекая элементы от головы к хвосту списка, мы получим их в обратном порядке (рис. 127).

Рис.127 – Порядок следования в стеке первых трех строк

После извлечения элемента из стека (в данном случае – строки) отпадет нужда в хранившей его динамической переменной. К чему засорять память? Ведь этот ценный ресурс нам ещё пригодится. Так давайте удалять из кучи ненужные динамические переменные.

Работу начнем, как обычно, с конструирования элемента списка. Этим элементом будет запись, включающая строку и указатель на следующую запись.

type PRec = ^TRec;       { Тип указатель на запись }

      TRec = record       { Тип запись для хранения связанных строк }

      mStr : string; { хранимая строка }

      mNext : PRec; { указатель на следующую запись }

      end;

Напомню, что со стеком выполняются, по меньшей мере, две операции: помещение в стек PUSH, и извлечение из стека POP. В нашем случае процедура записи в стек будет объявлена так:

procedure Push(const arg : string);

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

Теперь об извлечении из стека. Здесь надо получить не только строку, но и сигнал о состоянии стека: пуст он, или в нём ещё валяется что-то. Поэтому операцию извлечения из стека оформим булевой функцией.

function Pop(var arg : string): boolean;

Строка будет возвращаться через параметр arg, – это ссылка на переменную. Но, если функция вернет FALSE, это будет сигналом того, что стек пуст и строка не возвращена.

На этом закончим рассуждения и обратимся к программе «P_56_1».

{ P_56_1 – перестановка строк файла }

type PRec = ^TRec;       { Тип указатель на запись }

      TRec = record       { Тип запись для хранения связанных строк }

      mStr : string; { хранимая строка }

      mNext : PRec; { указатель на следующую запись }

      end;

var Stack : PRec; { Голова (вершина) стека }

      { Процедура размещения строки в стеке }

procedure Push(const arg : string);

var p : PRec;

begin

New(p);       { создаем новую переменную-запись }

p^.mStr:= arg;       { размещаем строку }

{ размещаем в голове стека }

p^.mNext:= Stack; { указатель на предыдущую запись }

Stack:=p;       { текущая запись в голове стека }

end;

      { Процедура извлечения строки из стека }

function Pop(var arg : string): boolean;

var p : PRec;

begin

Pop:= Assigned(Stack); { Если стек не пуст, то TRUE }

if Assigned(Stack) then begin { Если стек не пуст… }

arg:= Stack^.mStr;       { извлекаем данные из головы стека }

p:= Stack;       { временно копируем указатель на голову }

Stack:= Stack^.mNext; { переключаем голову на следующий элемент }

Dispose(p);       { удаляем ненужный элемент }

end

end;

var F : text; S : string;

begin       {– Главная программа –}

Stack:= nil; { Инициализация стека пустым значением }

{ Открываем входной файл }

Assign(F, 'P_56_1.pas'); Reset(F);

{ Пока не конец файла, читаем строки и помещаем в стек }

while not Eof(F) do begin

      Readln(F, S); Push(S);

end;

Close(F);

{ Открываем выходной файл }

Assign(F, 'P_56_1.out'); Rewrite(F);

{ Пока стек не пуст, извлекаем и печатаем строки }

while Pop(S) do Writeln(F, S);

Close(F);

end.

Процедура Push повторяет процедуру вставки элемента в список. А в теле функции Pop гляньте на выделенные операторы. После извлечения строки ненужный теперь элемент стека уничтожается процедурой Dispose(p), – так освобождается память. Но перед этим указатель на следующий элемент надо сохранить в голове списка, иначе мы потеряем ссылку на цепочку оставшихся элементов.

Изваяв программу, Ник испытал её волшебное действие на её собственном тексте. Каково же было его удивление, когда результат совпал с абракадаброй, полученной от приятеля! Вот такое чудесное совпадение!

Танцуют все!

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

Только теперь мы изменим имена мальчиков и девочек. В том варианте, как вы помните, дети носили однобуквенные имена, и мы представили их символами. Теперь же мы дадим им настоящие человеческие имена, но для этого и очередь организуем иначе. Как? Вы уже догадались – посредством односвязного списка (рис. 128).

Рис.128 – Размещение в очереди трех строк

Кажется, что этот рисунок совпадает с рисунком для стека. Так оно и есть. Только элементы теперь извлекаются в ином порядке. Первым элементом в очереди назначим тот, что в хвосте списка. Значит, по сравнению со стеком, в очереди все наоборот: первым элементом очереди является последний элемент списка, и для доступа к нему придется пробежать по всей цепочке ссылок.

Это обстоятельство вынудит нас изменить процедуру удаления первого элемента очереди. Теперь перед удалением надо заполучить указатель на предпоследний элемент списка. В нём надлежит поставить заглушку NIL, чтобы отцепить первый элемент очереди (рис. 129). В этом состоит главная премудрость обращения с очередью строк.

Рис.129 – Отцепление первого элемента очереди

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

Процедуру установки в очередь PutInQue объявим так:

procedure PutInQue(var Que: PRec; const arg: string);

Два её параметра – это ссылка на очередь (на голову списка) и помещаемая в очередь строка.

Для извлечения из очереди потребуется уже не процедура, а функция, назовем её GetFromQue, и объявим так:

function GetFromQue(var Que: PRec; var arg: string): boolean;

Здесь опять заметно сходство со стеком: как только очередь окажется пустой, функция сообщит об этом, вернув значение FALSE. И тогда мы отвергнем возвращаемый через ссылку arg результат.

Осталось обсудить ещё одну мелочь: организацию входных данных с тем, чтобы отличать мальчиков от девочек. Имена детей поместим в файл «P_56_2.IN», а для различения мальчиков и девочек, впечатаем имена девочек с некоторым отступом (с одним или несколькими пробелами в начале строки). Вот пример такого входного файла.

Ваня

Петя

Гриша

Маша

Наташа

Коля

Семен

Света

Теперь вы готовы рассмотреть программу «P_56_2».

{ P_56_2 – Запись в танцевальный кружок, версия 2 }

type PRec = ^TRec;       { Тип указатель на запись }

      TRec = record       { Тип запись для хранения связанных строк }

      mStr : string[31]; { хранимая строка (имя) }

      mNext : PRec;       { указатель на следующую запись }

      end;

{ Процедура размещения строки в очереди }

procedure PutInQue(var Que: PRec; const arg: string);

var p: PRec;

begin

New(p);       { создаем новую переменную-запись }

p^.mStr:= arg;       { размещаем строку }

{ размещаем указатель в голове очереди }

p^.mNext:= Que; { указатель на предыдущую запись }

Que:=p;       { текущая запись в голове очереди }

end;

      { Извлечение строки из начала очереди (из конца списка) }

function GetFromQue(var Que: PRec; var arg: string): boolean;

var p1, p2: PRec;

begin

GetFromQue:= Assigned(Que);

if Assigned(Que) then begin

{ Поиск первого элемента очереди }

p1:= Que; p2:=p1;

{ если в очереди только один элемент, цикл не выполнится ни разу! }

while Assigned(p1^.mNext) do begin

      p2:=p1;       { текущий }

      p1:=p1^.mNext; { следующий }

end;

{ теперь p1 указывает на первый элемент очереди, а p2 – на второй

      (или на тот-же самый, если в очереди всего один элемент) }

arg:= p1^.mStr;       { извлекаем данные }

if p1=p2       { если в очереди был один элемент… }

      then Que:= nil       { очередь стала пустой }

      else p2^.mNext:= nil; { а иначе "отцепляем" первый элемент }

Dispose(p1);       { освобождаем память первого элемента }

end;

end;

var

Boys : PRec; { очередь мальчиков }

Girls : PRec; { очередь девочек }

S1, S2 : String; { строки с именами }

Boy: boolean; { признак чтения имени мальчика }

F_In, F_Out : Text; { входной и выходной файла }

begin       {– Главная программа –}

{ Очищаем очереди мальчиков и девочек }

Boys := nil ; { очередь мальчиков }

Girls := nil; { очередь девочек }

Assign(F_In, 'P_56_2.in'); Reset(F_In);

Assign(F_Out,'P_56_2.out'); Rewrite(F_Out);

{ Цикл обработки входного потока }

while not Eof(F_In) do begin

Readln(F_In, S1); { выбираем имя из входного потока }

Boy:= S1[1]<>' '; { строки с именами девочек начинаются с пробела! }

while S1[1]=' ' do Delete(S1,1,1);

if Boy

      then begin { если это мальчик…}

      if GetFromQue(Girls, S2)       { если в очереди есть девочка }

      then Writeln(F_Out,S1+' + '+S2) { пару -> в выходной поток }

      else PutInQue(Boys, S1); { а иначе мальчика в очередь }

      end

      else begin { а если это девочка…}

      if GetFromQue(Boys, S2)       { если в очереди есть мальчик }

      then Writeln(F_Out,S2+' + '+S1) { пару -> в выходной поток }

      else PutInQue(Girls, S1); { а иначе девочку в очередь }

end

end;

Close(F_In); Close(F_Out);

end.

Вот результат обработки входного файла:

Ваня + Маша

Петя + Наташа

Гриша + Света

Как видите, из 8 детей сформированы лишь три пары, и кто-то ожидает в сторонке.

Итоги

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