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

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

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

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

Строка – особый род массива

С первого взгляда строка похожа на массив символов. Так ли это? – проверим. Известно, что строка может вместить до 255 символов. Объявим массив из 255 символов и сравним его размер с размером строки. Напомню, что функция SizeOf возвращает размер памяти, занимаемой переменной.

var S1 : array [1..255] of CHAR; { это массив из 255 символов }

      S2 : String;       { это строка длиной 255 символов }

begin

      Writeln (SizeOf(S1)); { печатает 255 }

      Writeln (SizeOf(S2)); { печатает 256 }

      Readln;

end.

Запустили программку? И что? Странно, но размер строки S2 оказался равным 256 байтам, что на единицу больше размера массива. Почему? Где прячется ещё один байтик? Ответ представлен на рис. 98.

Рис.98 – Размещение слова «PASCAL» в строковой переменной

Здесь показана внутренность строковой переменной со словом «PASCAL». Байты с 1-го по 6-й содержат буквы этого слова, а остальные байты не заняты. Но в начале массива обнаружен ещё один байт – с нулевым индексом. Он содержит число 6 – это длина слова «PASCAL». Значит, строковый тип – это массив со скрытым нулевым байтом, хранящим фактическую длину строки (эту длину возвращает функция Length).

Укороченные строки

Память – жилище переменных – всегда чем-нибудь занята. Даже пустая строка (нулевой длины) занимает 256 байтов памяти, и содержит что либо. Это «что либо» программисты называют мусором, а мусор никому не интересен. Так разумно ли отводить 256 байтов для строки, если большая её часть забита всяким вздором? Ведь память – ценный ресурс, и профессионал бережет её. К примеру, для строки, хранящей фамилию, вполне хватило бы и 20 байтов.

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

type TStrA = string[11]; { строка для 11 символов }

      TStrB = string[31]; { строка для 31 символа }

var A : TStrA;       B : TStrB;

Здесь объявлены два строковых типа данных; первый из них вмещает до 11 символов, а второй – до 31. Соответственно переменная A будет занимать в памяти 12 байтов, а переменная B – 32 байта (с учетом нулевого байта). Согласитесь, – экономия солидная, особенно для массива из таких строк. Во всем остальном, кроме размера, короткие строки ничем не отличаются от переменных типа STRING.

А что случится при копировании длинной строки в короткую? А ничего, – не вместившиеся символы будут «отрублены». Следующая ниже программа «P_44_1» подтверждает это, испытайте её.

{ P_44_1 – укороченные строки }

var S1 : string;       { размер строки по умолчанию = 255 }

      S2 : string[5]; { размер укороченной строки = 5 символов }

begin

S1:='abc';       S2:='abcdefgh';

Writeln('Строка S1: Размер =', SizeOf(S1):4,' Длина = ', Length(S1):4,' Значение= '+S1);

Writeln('Строка S2: Размер =', SizeOf(S2):4,' Длина = ', Length(S2):4,' Значение= '+S2);

Writeln('Нулевой байт строки S1 = ', Byte(S1[0]));

Writeln('Нулевой байт строки S2 = ', Byte(S2[0]));

Readln;

end.

Операции со строками

Итак, уяснив внутреннее устройство строк, обратимся к связанным с ними операциям. Что мы умеем делать со строками сейчас? А вот что:

• вводить и выводить строки процедурами ввода и вывода;

• объединять несколько строк в одну (складывать);

• определять длину строки функцией Length;

• проверять строки на равенство и неравенство;

• обращаться к отдельным символам строки (доступ по индексу).

Учитывая важность строкового типа, разработчики Паскаля предусмотрели для строк ещё несколько процедур и функций, позволяющих:

• искать одну строку внутри другой;

• копировать часть строки в другую строку;

• вставлять одну строку внутрь другой;

• удалять часть символов из строки;

• сравнивать две строки в смысле алфавитного порядка.

Рассмотрим всё это подробней. Представленные далее объявления процедур и функций даны мною лишь для пояснений, их не надо вставлять в программы.

Поиск в строке (Pos)

Функция Pos ищет одну строку внутри другой, её объявление выглядит так:

      function Pos(SubS: string; S: string): Integer;

Функция принимает два параметра:

• SubS – подстрока, которую ищут (то есть фрагмент строки);

• S – строка, в которой ищут.

Если искомый фрагмент SubS найден, функция возвращает его позицию – индекс первого символа SubS внутри строки S, а иначе возвращает ноль. Если строка S содержит несколько искомых фрагментов, возвращается индекс первого из них. Вот примеры.

      S:= 'BORLAND PASCAL';

      p:= Pos('LA', S);       { 4 }

      p:= Pos('PAS', S);       { 9 }

      p:= Pos('pas', S);       { 0 – подстрока не найдена }

      p:= Pos('A', S);       { 5 – первая из трех букв "A" }

Искомым фрагментом может быть и отдельный символ. Поиск ведется с учетом регистра; это значит, что заглавная и строчная буквы «P» считаются разными буквами.

Копирование части строки (Copy)

Функция Copy возвращает часть заданной строки.

      function Copy(S: string; Index, Count: Integer): string;

Входных параметров три:

• S – строка, из которой копируются символы;

• Index – индекс первого копируемого символа;

• Count – количество копируемых символов.

А вот примеры её применения.

      S:= ’Free Pascal forever!’;

      T:= Copy(S, 6, 6);       { ’Pascal’ }

      T:= Copy(S, 6, 255); { ’Pascal forever!’ }

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

Вставка в строку (Insert)

Объединять строки сложением просто. А если надо вставить строку в середину другой? Тогда обратитесь к процедуре Insert.

      procedure Insert(S1: string; var S2: string; Index: Integer);

Входные параметры:

• S1 – вставляемая строка;

• S2 – ссылка на принимающую строку;

• Index – позиция вставки.

Вот один пример.

      S:='Спартакчемпион!';

      { В позицию 8 вставляются три символа: тире и два пробела }

      Insert(' – ', S, 8);       { Спартак – чемпион! }

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

Удаление символов из строки (Delete)

Говорят: ломать – не строить. Попытайтесь, однако, удалить часть символов из строки. Слабо? А процедура Delete справляется с этим играючи.

      procedure Delete(var S: string; Index, Count : Integer);

Параметры таковы:

• S – ссылка на строку;

• Index – индекс первого удаляемого символа;

• Count – количество удаляемых символов.

Вот пример её применения.

      S:= ’Free Pascal forever!’;

      Delete(S, 6, 7);       { ’Free forever!’ }

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

Мы уже сравнивали строки на равенство (вспомните проверку пароля). Но строки сравнивают и на больше–меньше – лексикографически. При этом сравниваются слева направо коды символов двух строк в смысле их алфавитного порядка. Если длины строк разные и короткая совпадает с началом длинной, то большей считается длинная строка. Вот примеры:

      Writeln (’Borland’ > ’Pascal’); { false }

      Writeln (’ABC’ > ’AB’);   { true }

      Writeln (’ABC’ > ’abc’);  { false }

      Writeln (’45’ > ’1000’);  { true, поскольку ’4’ > ’1’ }

В первом примере код буквы «B» меньше кода буквы «P», поэтому левая строка меньше правой. Во втором случае первые символы совпадают, но левая строка длиннее, а значит больше. В третьем примере левая строка меньше, – тоже в соответствии с таблицей кодировки. Обратите внимание на неожиданный результат сравнения строк, составленных из цифр, – это вам не числа!

Сравнивая строки, можно отсортировать их в лексикографическом порядке (как если бы они располагались в словаре). К сожалению, такое сравнение работает только для латинских букв, для русских оно не всегда верно, приходится изобретать свою функцию сравнения (в DELPHI этой проблемы нет).

Перевод символов в верхний регистр (UpСase)

Функция UpСase меняет код латинской буквы, переводя её из нижнего в верхний регистр. Иными словами, она превращает строчную (маленькую) латинскую букву в заглавную (большую). Объявление функции таково.

      function UpCase(Ch: Char): Char;

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

      c:= UpCase(’r’);       { ’R’ }

      c:= ’n’;

      c:= UpCase( c );       { ’N’ }

Подсунув этой функции большую латинскую букву, цифру или знак препинания, вы получите назад свой символ неизменным. То же будет и с русскими буквами – они не обрабатываются функцией UpСase.

      c:= UpCase(’R’);       { ’R’ }

      c:= UpCase(’8’);       { ’8’ }

      c:= UpCase(’ы’);       { ’ы’ }

Функцией UpСase обычно приводят введенные строки к определенному виду. Ведь пользователь может ввести данные как заглавными, так и строчными буквами, а это иногда мешает правильной обработке строки.

Ознакомившись со строковой теорией, применим её, что называется, «в бою».

Подсчет слов в строке

Вот вам строка, посчитайте в ней количество слов «Pascal». Чуть подумав, вы остановитесь на функции Pos, – ведь она возвращает позицию искомого слова. Но функция обнаруживает лишь первое вхождение фрагмента, а как быть с остальными? Я предлагаю постепенно разрушать исходную строку. То есть, найдя искомый фрагмент, будем удалять его из строки и снова повторять поиск. На этом и построена программа «P_44_2».

{ P_44_2 – Подсчет слов «PASCAL» в строке }

var S : string; { исходная строка }

      p : integer; { позиция в строке }

      c : integer; { счетчик слов }

begin

S:='Лучший язык программирования – это PASCAL!'+

      'Изучите PASCAL! PASCAL не подведет!';

c:=0;

repeat

      p:= Pos('PASCAL', S); { ищем слово «PASCAL» }

      if p>0 then begin       { если нашли }

      Inc(c);       { то наращиваем счетчик }

      { и удаляем это слово из строки }

      Delete(S, p, Length('PASCAL'));

      end

until p=0;       { выход, если слов «PASCAL» больше нет }

Writeln('Найдено слов PASCAL: ',c); Readln;

end.

Контекстная замена

Любой текстовый редактор умеет заменять одну подстроку на другую, – это называется контекстной заменой. Устроим такую замену в строковой переменной. Итак, дана строка, содержащая несколько слов «Pascal». Заменим все вхождения слова «Pascal» словом «Паскаль» (чем не англо-русский переводчик?).

Разобравшись с предыдущей задачей, вы легко одолеете и эту. Для проверки вашего решения сравните его с моим («P_44_3»).

{ P_44_3 – Замена слов «Pascal» на «Паскаль» }

var S : string; { исходная строка }

      p : integer; { позиция в строке }

begin

S:='Лучший язык программирования – Pascal! '+

      'Изучите Pascal! Pascal не подведет!';

Writeln(S); { исходная строка }

repeat

      p:= Pos('Pascal', S);       { ищем слово 'Pascal' }

      if p>0 then begin       { если нашли }

      { удаляем это слово из строки }

      Delete(S, p, Length('Pascal'));

      { и вставляем в этом месте слово 'Паскаль'}

      Insert('Паскаль', S, p);

      end

until p=0; { выход, если слов 'Pascal' больше нет }

Writeln(S); { строка результата }

Readln;

end.

Итоги

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

• Строка, объявленная без указания размера, по умолчанию занимает 256 байтов памяти и может содержать до 255 символов.

• Для экономии памяти используют строки меньшего размера. При объявлении таких строк размер указывают внутри квадратных скобок после слова STRING.

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

А слабо?

А) Напишите процедуру, переводящую все символы строки (латинские буквы) к верхнему регистру.

Б) Напишите функцию для приведения любой буквы к верхнему регистру (включая и русские). Подсказка: вспомните о таблице кодировки.

В) Напишите функцию для приведения любой буквы к нижнему регистру.

Г) Напишите собственные процедуры и функции обработки строк, повторяющие те, что встроены в Паскаль. Дайте им названия, похожие на стандартные, например: MyCopy, MyDelete и так далее.

Д) Вращение строки вправо. Напишите процедуру, перемещающую 1-й символ строки на место 2-го, 2-й – на место 3-го и т.д. Последний символ должен занять 1-е место. Примените средства обработки строк.

Е) Вращение строки влево. Напишите процедуру для перемещения 2-го символа на место 1-го, 3-го – на место 2-го и т.д. Первый символ должен стать последним.

Ж) Строка содержит несколько слов – предложение. Напишите программы для решения следующих задач.

• Напечатать в столбик отдельные слова введённого предложения.

• Определить количество слов в строке.

• Равномерно расставить пробелы между словами так, чтобы удлинить строку до 80 символов (исходная строка короче 80).

З) Напишите булеву функцию, определяющую, является ли строка (параметр) палиндромом. Палиндром читается одинаково в обоих направлениях.

И) Напишите булеву функцию, определяющую, можно ли из букв первого слова составить второе (например, «клавиша» и «вилка» – TRUE). Учитывается только набор букв, а не их количество. Подсказка: примените множества.

К) Дана строка, содержащая не менее трёх символов. Найти в ней три стоящих подряд символа, дающих максимальную сумму своих кодов.

Л) В строке найти возрастающую последовательность символов наибольшей длины (сравнивайте коды символов).

М) Напишите булеву функцию, проверяющую, следуют ли символы строки по неубыванию своих кодов.

Н) Напишите функцию для шифрования строки путём перестановки её символов, расположенных на нечётных позициях: первый символ обменивается с последним, третий – с третьим от конца и т.д.

Глава 45

Очереди и стеки

Хорошей вещи найдется уйма применений. Взять хотя бы строки, из которых мы построим сейчас инструменты системных программистов – очереди и стеки.

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

Вовочка в потоке событий

Переживайте неприятности по мере их поступления – эта житейская мудрость касается любого из нас. Жизнь – это поток событий, барахтаясь в котором, мы поминутно решаем: прервать ли начатое дело и хвататься за другую проблему? Или отложить эту новую проблему «на потом»?

Смотрите: вот компьютер и Вовочка, мирно играющий в «звездные войны». Входит мама: «Вова, ты уроки сделал?». Вова неохотно откладывает игру и приступает к урокам. Через полчаса мама снова беспокоит его: «Вовочка, я не могу отойти от плиты. Сгоняй-ка быстро за луком». Уроки откладываются, и Вова отправляется в магазин. По пути он видит гоняющих мяч приятелей, – им не хватает вратаря. Как не помочь друзьям? Поход в магазин откладывается, и Вовочка на страже ворот. Делу время, а потехе час. Закончилась игра, и можно выполнить мамино поручение. Купив луку, Вова доделывает отложенные уроки и возвращается к первому занятию – «звездным войнам».

Вовочка обрабатывал события по принципу стека, – скажет об этом системный программист. Другое название стека – дисциплина обслуживания LIFO, что значит «Last-In, First-Out», или по-русски: «последним пришел – первым ушел». Мы соприкоснулись со стеком, разбирая рекурсивную процедуру быстрой сортировки. Помните пример с укладкой рюкзака? А вот ещё пример: магазин для патронов. Патрон, вставленный в магазин последним, выстрелит первым, и наоборот.

Итак, пример с Вовочкой показал, что важные события мы обслуживаем по принципу стека.

А очередь? Какое отношение к нам имеет этот символ потерянного времени? Заметив, как «тормозит» порой ваш компьютер, вспомните о ней. Иногда компьютер реагирует на мышку и клавиатуру с заметным опозданием, но не забывает о нажатиях и щелчках. Они накапливаются в очереди, а затем извлекаются оттуда и обрабатываются.

Или другой пример – печатание документов на сетевом принтере. Когда принтер занят, операционная система ставит запросы на печать в очередь. А затем – по мере готовности принтера – выбирает файлы из этой очереди и отправляет принтеру.

За очередью тоже закрепилось свое сокращение – FIFO, что значит «First-In, First-Out» – «первым пришел, первым ушел». В отличие от стека, в очередь попадают маловажные события.

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

Танцевальный кружок

В городе набирали детей в кружок бального танца. Запись в кружок вела преподающая в нём дама. Приходящих мальчишек и девчонок она стремилась объединять в пары при первой возможности с тем, чтобы они сразу приступали к занятиям. Однако на запись дети приходили поодиночке в разное время и в случайном порядке, – то несколько мальчиков подряд, то несколько девочек. Дама не слыхала о системном программировании, а потому прибегла к здравому смыслу. Взяв пару записных книжек, она поступала так.

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

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

Рис. 99 – Запись в танцевальный кружок

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

      ZHJKqwertASDyuiopQWERTYUIOPasdf

означает, что первым явится мальчик по имени Z, а последней – девочка по имени f. Первая пара составится из мальчика Z и девочки q. Это упрощение не меняет сути нашей модели, но избавляет её от второстепенных деталей.

Итак, с учетом всех договоренностей, явим задачу в окончательном виде. Дана строка, состоящая из больших и маленьких букв латинского алфавита – «мальчиков» и «девочек». Мы должны сформировать другую строку, состоящую из тех же символов, но следующих попарно: сначала большая буква – «мальчик», затем маленькая – «девочка». Пары разделяются пробелом. Например, для указанной выше строки, пары должны быть составлены так:

      Zq Hw Je Kr At Sy Du Qi Wo Ep Ra Ts Yd Uf

А напоследок программа должна напечатать имена тех, кто временно остался без пары. Здесь это будут пришедшие в числе последних мальчики I, O и P.

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

Сделаем так. Элементы очереди – символы – будем хранить в строковых переменных. К ним добавим ещё две процедуры: одну – для установки элемента в очередь, другую (это будет функция) – для извлечения из очереди первого элемента. Назовем их соответственно PutInQue – «поставить в очередь» и GetFromQue – «извлечь из очереди» (Queue – «очередь» или «хвост»). Всё это представлено в программе «P_45_1».

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

{ Постановка символа arg в очередь Que }

procedure PutInQue(var Que: string; arg: char);

begin

Que:= Que + arg; { добавляем в конец строки }

end;

{ Выбор из очереди Que элемента в параметр arg }

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

begin

if Length(Que) = 0       { если очередь пуста }

      then GetFromQue:= false

      else begin

      GetFromQue:= true;       { если не пуста }

      arg:= Que[1];       { запоминаем первый элемент }

      Delete (Que, 1, 1); { и удаляем его из очереди }

      end

end;

      { Глобальные переменные }

var S_IN : string; { входной поток – символы }

      S_OUT : string; { выходной поток (пары) }

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

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

      c1,c2 : char; { очередная пара – символы строки }

      i : integer;       { индекс во входном потоке }

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

{ задаем (вводим) входной поток: A..Z – мальчики, a..z – девочки }

S_IN:='ZHJKqwertASDyuiopQWERTYUIOPasdf';

S_OUT:='';       { выходной поток пока пуст }

Boys:=''; Girls:=''; { Очищаем очереди мальчиков и девочек }

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

for i:=1 to Length(S_IN) do begin

      c1:= S_IN[i]; { выбираем из входного потока }

      if c1 in ['A'..'Z']

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

      { если в очереди есть девочка }

      if GetFromQue(Girls, c2)

      { добавляем пару в выходной поток }

      then S_OUT:= S_OUT+c1+c2+’ ’

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

      else PutInQue(Boys, c1);

      end

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

      { если в очереди есть мальчик }

      if GetFromQue(Boys, c2)

      { добавляем пару в выходной поток }

      then S_OUT:= S_OUT+c2+c1+’ ’

      { а иначе помещаем девочку в очередь }

      else PutInQue(Girls, c1);

      end

end;

Writeln('Входной поток:' );

Writeln(S_IN);

Writeln('Выходной поток:' );

Writeln(S_OUT);

if Length(Boys)>0 then begin

      Writeln('В очереди мальчиков остались:' );

      Writeln(Boys);

end;

if Length(Girls)>0 then begin

      Writeln('В очереди девочек остались:' );

      Writeln(Girls);

end;

Readln;

end.

Процедура PutInQue просто добавляет символ в конец строки. Строго говоря, если длина строки достигнет 255, то новый символ не попадет в очередь. Но мы не станем усложнять программу дополнительными проверками, – считаем, что емкости очереди нам достаточно.

Но для функции GetFromQue, выбирающей из очереди первый символ, контроль строки на пустоту необходим, иначе работа модели нарушится. Функция возвращает состояние очереди, бывшее до извлечения символа (TRUE, если очередь не была пуста). А сам извлекаемый символ возвращается через параметр arg, – это ссылка на символьную переменную. Вот, пожалуй, и вся премудрость. Испытайте эту программу. Добавьте операторы печати для наблюдения за очередями.

Скитания товарного вагона

Прежде, чем углубиться в стек, вникнем в работу железной дороги. Вы знаете, как железнодорожники доставляют товарный вагон из пункта «А» в пункт «Б»? «Очень просто, – скажете, – цепляют к составу и тащат!» Тогда взгляните на рис. 100.

Рис.100 – Доставка вагонов между несколькими станциями

Здесь показаны пять железнодорожных станций, четыре из которых обозначены цифрами, а пятая – узловая станция – буквой «У». Предположим, что со станции «1» надо доставить несколько десятков вагонов на другие станции (по направлению стрелок). С этих станций тоже везут вагоны, но соответствующие стрелки я не показал. Тащить вагоны поодиночке разорительно! Поэтому их собирают в составы по нескольку десятков вагонов. Накопив такой состав на станции «1», железнодорожники доставляют его на узловую станцию; сюда же стекаются составы с других направлений. На узловой творится самое интересное, – здесь из одних составов формируют другие с тем, чтобы тащить их далее в нужном направлении. Эта работа называется сортировкой состава. В нашей стране сотни товарных станций, многие из которых узловые. Прежде чем попасть по назначению, вагон кочует между узловыми станциями, проходя через несколько сортировок. А вы говорите: просто, просто!

Но это ещё присказка, – сказка впереди.

Сортировочная горка

Итак, на узловых станциях формируют новые составы с тем, чтобы каждый вагон следовал далее в нужном направлении. Для сортировки устроены так называемые сортировочные горки. Горка – это слегка наклоненный участок пути; если отцепить от стоящего на нём состава вагон, последний покатится под горку. Но укатится недалеко, – под горкой устроено несколько тупиков. Тупик – это обычное состояние программиста, но здесь я говорю о других тупиках, железнодорожных. Это участки пути, ограниченные с одной стороны земляным валом. Уткнувшись в этот вал, вагон остановится. Горка соединяется с тупиками железнодорожными стрелками, переключая которые можно направить катящийся с горки вагон в тот или иной тупик (рис. 101).

Рис.101 – Схема сортировочной горки

Как сортируют состав? Основную работу выполняют двое: сцепщик и стрелочник (который всегда виноват!). От стоящего на горке состава сцепщик отсоединяет по очереди вагон за вагоном и сообщает стрелочнику по рации, в который из тупиков направить очередной вагон, – тому остается лишь переводить свои стрелки. Вкатившись в тупик, вагон тормозится земляным валом или слегка соударяется с уже стоящим там вагоном и автоматически сцепляется с ним. «Разбросав» по тупикам один состав, на горку выкатывают другой и продолжают сортировку, пока в тупиках не сформируются новые составы, готовые к дальнейшему пути.

Наша цель: смоделировать сортировочную горку, то есть создать программу, ведущую себя подобно такой горке. Вагоны заменим символами; следовательно, и состав и стоящие в тупиках вагоны мы представим строками. Будем считать первый символ строки первым вагоном состава, – он прицеплен к локомотиву. В тупике первым будет вагон, стоящий у земляного вала. Легко догадаться, что обрабатывать вагоны будем по принципу стека, поскольку сцепщику всегда доступен только последний вагон.

Договорившись об этом, сформулируем задачу окончательно. Дана строка символов (состав), из которой надо сформировать три других. Вагоны, обозначенные большими буквами ’A’…’Z’, отправим на станцию «A»; другие, обозначенные маленькими буквами ’a’…’z’, – поедут к станции «B», а третьи, обозначенные цифрами ’0’…’9’, – к станции «C». Программа должна сформировать три строки – это вновь собранные составы. Первый символ в них, – это вагон, прицепленный непосредственно к локомотиву.

Для решения задачи надо всего лишь в точности повторить действия сцепщика и стрелочника. Будем «отцеплять» символы от строки и «заталкивать» их в стеки – это наши тупики. Значит, надо построить механизм для стеков. Он будет похож на механизм для очереди: элементы храним в строковых переменных, а для занесения и извлечения элементов из стека учредим две процедуры. По традиции программисты называют эти процедуры так: Push – затолкнуть в стек, и Pop – вытолкнуть из стека.

Процедура заталкивания в стек Push присоединяет символ к концу строки. Она точь-в-точь повторяет процедуру установки в очередь, только называется иначе.

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

Теперь вам не составит труда разобраться в показанной ниже программе «P_45_2». Обратите внимание на отцепку вагонов от исходного состава: она тоже выполняется функцией выталкивания Pop, поскольку исходный состав трактуется как непустой стек.

{ P_45_2 – Сортировочная станция }

{ Помещение элемента в стек }

procedure Push(var aStack: string; arg: char);

begin

      aStack:= aStack + arg; { добавляем в конец строки }

end;

{ Извлечение элемента из стека }

function Pop(var aStack: string; var arg: char): boolean;

begin

if Length(aStack) = 0 { если стек пуст }

      then Pop:= false       { сообщаем об этом }

      else begin

      { возвращаем последний элемент }

      arg:= aStack[Length(aStack)];

      { и удаляем его из стека }

      Delete(aStack, Length(aStack), 1);

      Pop:= true; { признак того, что стек не был пуст }

      end;

end;

var S : string;       { исходный состав }

      SA, SB, SC : string; { три сортировочных тупика A,B,C}

      c : char;       { очередной вагон }

begin

S:= 'HEjd31kDJK62px912se3BKdwL9'; { Исходный состав }

Writeln('Исходный состав: '+S);

SA:=’’; SB:=’’; SC:=’’; { очистка тупиков }

{ Отцепляем вагоны от исходного состава и заталкиваем в тупики }

while Pop(S, c) do begin

      if c in ['A'..'Z'] then Push(SA, c);

      if c in ['a'..'z'] then Push(SB, c);

      if c in ['0'..'9'] then Push(SC, c);

end;

{ Теперь исходный состав пуст, то есть S='' }

{ Выкатываем вагоны из тупика A и цепляем к первому составу }

while Pop(SA, c) do Push(S, c);

Writeln('На станцию A : '+S);

S:=''; { Освобождаем пути }

{ Выкатываем вагоны из тупика B и цепляем ко второму составу }

while Pop(SB, c) do Push(S, c);

Writeln('На станцию B : '+S);

S:=''; { Освобождаем пути }

{ Выкатываем вагоны из тупика C и цепляем к третьему составу }

while Pop(SC, c) do Push(S, c);

Writeln('На станцию C : '+S);

Readln;

end.

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

Итоги

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

• Очередь обслуживает элементы по принципу «первый пришел – первый ушел» или сокращенно FIFO (First-In, First-Out).

• Стек обслуживает элементы по принципу «последний пришел – первый ушел» или сокращенно LIFO (Last-In, First-Out).

А слабо?

А) Исследуя модель танцевального кружка, можно заметить, что в любой момент одна из двух очередей обязательно пуста. В самом деле, если приходит больше мальчиков, то будет пуста девчоночья очередь и наоборот. Можно ли обойтись одной очередью? Придумайте, как это сделать.

Подсказка: добавьте функцию для тестирования очереди с тем, чтобы выяснить, не пуста ли она. И, если не пуста, то кто томится в ней – мальчик или девочка? Эта функция не должна изменять состояние очереди.

Б) На реальных станциях на горку последовательно загоняют несколько составов, а уж потом освобождают тупики. Добавьте в модель сортировочной горки возможность такой обработки. Исходные составы (строки) должны вводиться с клавиатуры, признак окончания ввода – пустая строка. Совет: выделите действия по сортировке одного состава в отдельную процедуру.