ПРЕОБРАЗОВАНИЯ СТРУКТУР
5.5.1. ЗАДАЧИ ПРЕОБРАЗОВАНИЯ
Рассмотрим ряд программ, реализующих процедуры простого преобразования структур данных. Эти преобразования касаются только количественных характеристик структур и формы представления элементов.
Данные программы осуществляют перевод содержимого элементов некоторой структуры из одной системы кодирования в другую, удаление элемента из структуры и вставку его в структуру.Необходимость перекодировки возникает в том случае, когда различные программы, входящие в один программный комплекс, по-разному интерпретируют данные одного содержания. Чаще всего такая потребность возникает при обработке символьной информации в операциях ввода-вывода, когда внутрисистемное представление символов определяется одними правилами, а некоторое внешнее устройство интерпретирует те же символы по другим правилам. Например, программы внутренней об-
работки символов требуют их представления в коде КОИ-7, а вывод этих символов на индикаторное табло необходимо осуществлять в сегментном коде. Аналогичная ситуация может возникнуть и при вводе информации с внешнего устройства. Процедуры вставки и удаления элементов рассматриваются не только для динамических структур (списков), но и для статических (массивов). К простому преобразованию массивов приходится чаще всего прибегать в том случае, когда в массиве содержится символьная информация, подлежащая редактированию.
5.5.2. ПРЯМАЯ ПЕРЕКОДИРОВКА СТРОКИ
Пусть имеется некоторая строка, представляющая собой массив символов, закодированный в системе кодов А (входная система кодирования). Необходимо получить строку, содержащую такую же последовательность символов, но закодированную в системе кодов В (выходная система кодирования). Если входная и выходная системы кодирования различаются незначительно (небольшим количеством символов), перекодировку можно осуществить путем последовательного просмотра входной строки и селекции различающихся массивов с их последующей заменой.
В более общем случае перекодировка производится с помощью специальной таблицы. Таблица составляется следующим образом: в і-й элемент таблицы помещается код символа в выходной системе кодирования, соответствующий символу, который кодируется кодом і во входной системе кодирования. Таким образом, код символа во входной системе кодирования можно использовать как индекс для нахождения соответствующего кода выходной системы кодирования в таблице (схема перекодировки приведена на рис. 5.6). Программа перекодировки имеет вид:
Таблица перекодировки
Рис. 5.6. Схема перекодировки символов входной и выходной строк
Программа представляет итеративный цикл, на каждой итерации которого перекодируется один байт. Используются два указателя — для входной и выходной строк, а также счетчик текущей длины для контроля окончания цикла. Значение очередного байта выходной строки определяется следующим образом: содержимое очередного байта входной строки добавляется к адресу начала таблицы, затем содержимое ячейки памяти с полученным адресом переписывается в текущий байт выходной строки.
5.5.3. ОБРАТНАЯ ПЕРЕКОДИРОВКА СТРОКИ
Эта задача отличается от предыдущей тем, что таблица перекодировки содержит коды символов не в выходной, а во входной системе кодирования. Обратную перекодировку можно свести к прямой, если составить новую таблицу. Как правило, в МП системах перекодировку
символов приходится проводить как в прямом, так и в обратном направлениях, и наличие двух таблиц, содержащих одну и ту же информацию, является избыточным. При обратной перекодировке значение каждого кода входной строки отыскивается в таблице, а в соответствующее место выходной строки записывается индекс найденного элемента таблицы. Программа перекодировки представлена ниже:
Как и в предыдущей программе, для организации итеративного цикла используются два указателя —
для входной и выходной строк, а также счетчик текущей длины массива.
Поиск элемента таблицы, содержащего очередной код входной строки, осуществляется с помощью подпрограммы ПСК1, которая находит заданный код в определенной области памяти и возвращает его абсолютный адрес в регистровую пару (Н, L). Для получения индекса из этого абсолютного адреса вычитается адрес начала таблицы, затем значение индекса записывается в выходную строку.5.5.4. УДАЛЕНИЕ ФРАГМЕНТА МАССИВА
Под удалением фрагмента массива понимается удаление содержимого некоторой области памяти, входящей в данный массив, при этом длина массива уменьшается на длину удаляемого фрагмента. Пусть имеется массив с начальным адресом А и конечным адресом D, из которого необходимо удалить фрагмент, начинающийся с адреса В и оканчивающийся адресом С (Aконца массива-приемника будет больше адреса начала массива-источника.
5.5.5. ВСТЛВКЛ ФРАГМЕНТА В МАССИВ
Пусть в некоторый массив, ограниченный адресами А и С, необходимо, начиная с адреса В, вставить содержимое области памяти, не принадлежащей этому массиву, при этом вся информация исходного массива сохраняется. Решение задачи осуществляется в два этапа. Сначала необходимо освободить в массиве место под вставляемый фрагмент. Для этого часть массива, ограниченная адресами В и С, сдвигается в памяти в сторону возрастания адресов на количество байтов, равное длине вставки, затем в освобожденную область копируется содержимое вставляемого фрагмента (рис. 5.8). Программа вставки имеет вид:
Первый фрагмент программы обеспечивает «раздвижку» массива путем перемещения содержимого области памяти, ограниченной адресом вставки и адресом последнего байта массива, в область памяти, начинающуюся с адреса, значение которого равно сумме адреса вставки и длины вставляемого фрагмента. Перемещение выполняется подпрограммой КОП1. Во втором фрагменте обеспечивается заполнение освобожденной области содержимым вставляемого фрагмента. Здесь вторично вызывается подпрограмма КОП1, для которой массивом- источником является вставляемый фрагмент, а адресом начала массива-приемника—адрес вставки.
В данной программе в отличие от предыдущей перемещение информации выполняется с помощью подпрограммы КОПІ, а не КОП2. Это объясняется тем, что если длина вставляемого фрагмента меньше длины остатка
Рис. 5.8. Схема вставки фрагмента массива
массива (области памяти, ограниченной адресами В и С), то при выполнении «раздвижки» адрес начала массива- приемника оказывается меньше адреса конца массива- источника, и пересылку надо производить со старших адресов. Во втором фрагменте безразлично, какую подпрограмму применять: КОШ или КОП2. Подпрограмма КОП1 используется только с целью унификации, хотя для уменьшения времени выполнения более целесообразно использовать подпрограмму КОП2.
5.5.6. ВСТАВКА ЭЛЕМЕНТА В СПИСОК
Модификация списка в отличие от модификации массива не требует физического перемещения информации; достаточно только изменить значение полей связи соответствующих элементов списка. Для выполнения вставки, элемента в список необходимо указать точку входа в него, т. е. адрес начала списка и место вставки в список, идентифицируемое по заданному значению ключа того элемента, после которого необходимо произвести вставку.
Алгоритм решения этой задачи состоит в следующем. Последовательно просматривается весь список для нахождения элемента, значение поля ключа которого равно заданному, затем содержимое поля связи найденного элемента копируется в поле связи вставляемого элемента, а туда записывается адрес вставляемого элемента (рис. 5.9). Программа вставки имеет вид:
Поиск элемента по заданному значению ключа выполняется с помощью подпрограммы ПСКСП. После возврата из этой подпрограммы проверяется содержимое регистровой пары (Н, L). Если оно равно 0FFH (элемента с заданным ключом в списке не существует), в выходной параметр записывается признак неудачного выполнения и осуществляется возврат из программы.
Проверка производится путем логического умножения содержимого регистров (Н) и (L) и последующего их инкрементирования. Очевидно, что результат будет нулевой только в том случае, если в регистрах (Н) и (L) содержался код 0FFH. Если элемент найден, в его поле связи записывается адрес вставляемого элемента, причем старое содержимое поля связи сохраняется в регистровой паре (В, С).
Рис. 5.9. Схема вставки элемента в список:
А, В, С, D — адреса элементов списка; Е — адрес вставляемого элемента; К — значение ключа
В последнем фрагменте программы это сохраненное значение записывается в поле связи вставляемого элемента.
5.5.7. УДАЛЕНИЕ ЭЛЕМЕНТА ИЗ СПИСКА
Удаление элемента из списка заключается в том, что в поле' связи элемента, стоящего перед удаляемым, записывается адрес элемента, стоящего в списке после удаляемого. Идентификацию удаляемого элемента списка можно произвести точно так же, как и ранее. Программа удаления имеет вид:
В первом фрагменте программы выполняется поиск удаляемого элемента. Структура этого фрагмента аналогична структуре первого фрагмента программы ВСТСП, рассмотренной на с. 241).Если элемент, подлежащий удалению, найден в списке, то содержимое его поля связи переписывается в поле связи предыдущего элемента. Адрес предыдущего элемента определяется подпрограммой ПСКСП и помещается ею в регистровую пару (В, С).
При удалении элемента из списка может возникнуть особая ситуация. Она заключается в том, что в качестве удаляемого элемента может быть задан первый элемент списка. При этом подпрограмма ПСКСП возвращает в регистровую пару (В, С) нулевое значение. В рассматри
94.4
ваемой программе обработка этой ситуации сводится к тому, что изменяется адрес начала списка, который является входным параметром. Это выполняется путем записи содержимого поля связи удаляемого элемента в регистровую пару. (В, С). Таким образом, изменение значения входного параметра, расположенного в регистровой паре (В, С), информирует вызывающую программу, что было произведено удаление первого элемента и дальнейшее обращение к списку должно производиться по новому адресу.