Примеры

 

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

Сначала рассмотрим программу подготовки списков подписчиков на какие-либо издания. Такие списки обычно печатаются на специально предназначенной для этого бумаге. Бумага эта разбита на заготовки для будущих этикеток, покрытые с обратной стороны клеем. На каждой этикетке печатается определенный адрес, этикетки снимаются с бумаги и наклеиваются на конверты для последующей посылки. Мы будем предполагать, что бумага с заготовками для этикеток выглядит так, как это показано на рис. 10.4. Заготовки обычно располагаются на листе столбцами, причем каждые два соседних столбца разделены четырьмя пробелами. На каждой этикетке могут быть напечатаны три строки по тридцать символов в каждой, этикетки в каждом столбце отделяются друг от друга одной пустой строкой. Итак, мы должны напечатать по одному адресу на этикетке, всего четыре в ряду, пропустить строку и т. д.

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

столбцы 1—30: имя

столбцы 31—55: улица и адрес

столбцы 56—80: город, штат и почтовый индекс

Программа должна считать информацию с каждой карты и должна организовать такую выдачу содержимого каждого из трех полей, чтобы нужный адрес был напечатан в трех строках соответствующей этикетки. Исходная колода карт должна быть разбита на группы почетыре карты в каждой, поскольку в каждом ряду печатного листа должны быть расположены четыре адреса. Предположим, что количество адресных карт кратно 4. Если это не так, то в конец колоды должно быть добавлено соответствующее количество пустых карт. Для обеспечения остановки программы колода завершается ограничителем, картой, содержащей коды символа * в первых пяти колонках.

Рис. 10.4. Структура поля этикеток для машинной обработки адресов.

На рис. 10.5 приведен пример исходной колоды и получаемого в этом случае окончательного списка. На рис. 10.6 представлена блок-схема программы, и, наконец, на рис. 10.7— сама программа. На блок-схеме перемещение символьной информации указано с помощью индексов, соответствующих перемещаемым байтам, у имен областей, из которых производится перемещение. Например, факт пересылки содержимого первых тридцати байтов области NAME в байты с J по (Л+29)-й области LINE1 отмечается так:

LINEI-J +29NAME0-29

При составлении подобных программ целесообразно начинать с определения размеров требуемого сегмента памяти и формата записи вводимой и выводимой информации. Исходная колода сформирована по уже описанным правилам. Для облегчения процессов составления и чтения программы разобьем 80-байтовую область памяти, предназначенную для хранения образов считываемых карт, на три части соответствующей длины: NAME, STADDR и CITSTATE. Печать производится по 3 строки в каждом ряду этикеток. Строка состоит из 132 печатных символов и символа управления кареткой. Пропуск одной строки после каждого ряда достигается указанием контрольного символа С'0' в первой строке вывода. Отметим, что управляющий символ хранится отдельно от каждой строки. Это сделано с целью упрощения адресации.

Теперь мы напишем ту часть программы, которая выполняет реальную работу, в данном случае команды МУС. Учитывая то обстоятельство, что адрес первого операнда может быть различным в зависимости от номера изготовляемой этикетки, для хранения этих адресов используется регистр 6. Теперь осталось лишь организовать выполнение различного рода вспомогательных работ, таких, например, как управление циклом, проверка на появление карты-ограничителя, вычисление адресов операндов MVC, внеся в нужные места скелета программы соответствующие команды. В программу также должны быть включены команды резервирования памяти.

Рис. 10.5. Входная и выходная информация для программы печати адресов.

Рис. 10.6. Блок-схема программы печати адресов.

Рис. 10.7.

В качестве второго примера рассмотрим программу, предназначенную для составления связанного списка. Такой список является способом хранения логически упорядоченной информации, физический порядок расположения которой, вообще говоря, не совпадает слогическим. Для нахождения следующего по порядку за данным элемента информации используется специальный указатель, размещенный в данном элементе. Обычно в качестве указателя используется адрес памяти, по которому хранится следующий в списке элемент.

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

Рис. 10.8. Список.

Представленный на рис. 10.8 список содержит четыре записи, имеющие соответственно ключи С, A, R и F. Пусть мы хотим определить местонахождение следующего за записью С элемента списка. При этом предполагается, что адрес записи С нам известен. Для этого необходимо лишь обратиться к полю указателя элемента С, в котором мы и найдем адрес следующего элемента, 4000. По адресу 4000 записан ключ следующей записи F, в поле соответствующего ей указателя — новый адрес 3000 и т. д.

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

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

При пополнении списка каким-либо новым элементом последний может быть записан на произвольное свободное место памяти. Предположим, что мы хотим внести в список, изображенный на рис. 10.8, новую запись, с ключом D. Пусть, кроме того, адрес, по которому эта запись хранится в памяти, равен 7000. Нужно начать поиск с начала списка и продолжать его до тех пор, пока не будет встречен элемент с ключом, превосходящим D. Теперь указатель, соответствующий D, мы должны установить равным адресу найденного элемента и, кроме того, указатель предыдущей записи — равным адресу D. Результирующий список изображен на рис. 10.9.

Рис. 10.9. Список, представленный на рис. 10.8, с добавлением записи, имеющей ключ D.

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

На рис. 10.10 приведена блок-схема программы, считывающей информацию с колоды 80-колонных перфокарт и записывающей ее в память в виде списка в алфавитном порядке ключей, в качестве которых используются первые десять байтов записи. Завершают каждый элемент списка 4-байтовые указатели. По окончании процесса записи элемента в список указатель содержит информацию об адресе следующего элемента. В блок-схеме использовано сокращение A(NAME) /тля обозначения начала поля NAME. REC(J) обозначает 80-байтовый сегмент памяти, имеющий адрес J.KEY(J) — это первые 10 бантов записи с адресом J, a POINT(REC(J)) — обозначает 4-байтовое поле указателя, непосредственно следующее за REC(J).

Рис. 10.10. Блок-схема программы сортировки группы записей путем внесения в список и печати упорядоченных записей.

Блоку 1 блок-схемы соответствует процесс предварительной организации пустого списка. J представляет собой адрес начала очередной записи, предназначенной для внесения в список. Считывание записи производится в блоке 4, затем ее ключ сравнивается с ключом из 10 девяток. Такой ключ в нашем случае является ограничителем вводимой последовательное™. После того как список составлен, блоки 16—19 организуют распечатку его элементов в логической последовательности. Поиск места, соответствующего данной записи, начинается с начала списка блоком 6. Указатель последнего элемента содержит адрес шапки, проверка на выполнение условия равенства выполняется блоком 7. Ключ считанной записи сравнивается с ключом очередной записи списка, хранящейся по адресу PTNEW. Блоки 9 и 10 меняют содержимое указателей PTOLD (адреса предыдущего элемента) и PTNEW (адреса следующего).

 

Как только найден ключ, превосходящий ключ новой записи, управление передается блокам 11—14, которые изменяют значения указателей в соответствии с вновь определенным порядком записей в списке, вызванным включением новой записи. Затем производится считывание нового элемента в 80-байтовую область памяти, отстоящую от начала области расположения предыдущей на 84 байта. Отметим, что в процессе сортировки нам не пришлось ни разу прибегнуть к перемещению записей (исключая, конечно, начальный их ввод).

На рис. 10.11 приведена программа, соответствующая схеме рис. 10.10. Преобразование блок-схемы в программу достаточно очевидно. Отметим, что блок 1 реализуется следующей командой ассемблера:

NAME DC A(NAME)

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

A (PLACE)

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

Расскажи друзьям