Программа поиска имеет следующий вид. Б программе просмотр элементов списка выполняется с помощью итеративного цикла. Для полного определения местоположения элемента в однонаправленном списке необходимо знать адрес не только данного элемента, но и предыдущего, так как в однонаправленных списках отсутствуют адресные ссылки назад. С этой целью в программу вводятся два указателя. Первоначально значение первого указателя равно адресу начала списка, а второго — нулю. На каждой итерации анализируется поле ключа одного элемента. После этого указатели меняются местами, и если обнаруживается, что поле ключа текущего элемента равно заданному, осуществляется возврат из программы. В противном случае в первый указатель загружается значение поля связи текущего элемента. Если новое значение первого указателя равно нулю . ЗАДАЧИ ПРЕОБРАЗОВАНИЯ Рассмотрим ряд программ, реализующих процедуры простого преобразования структур данных. Эти преобразования касаются только количественных характеристик структур и формы представления элементов. Данные программы осуществляют перевод содержимого элементов некоторой структуры из одной системы кодирования в другую, удаление элемента из структуры и вставку его в структуру. Необходимость перекодировки возникает в том случае, когда различные программы, входящие в один программный комплекс, по. Чаще всего такая потребность возникает при обработке символьной информации в операциях ввода. Например, программы внутренней об . Аналогичная ситуация может возникнуть и при вводе информации с внешнего устройства. Процедуры вставки и удаления элементов рассматриваются не только для динамических структур . К простому преобразованию массивов. ПРЯМАЯ ПЕРЕКОДИРОВКА СТРОКИ Пусть имеется некоторая строка, представляющая собой массив символов, закодированный в системе кодов А . Необходимо получить строку, содержащую такую же последовательность символов, но закодированную в системе кодов В . Если входная и выходная системы кодирования различаются незначительно . В более общем случае перекодировка производится с помощью специальной таблицы. Таблица составляется следующим образом. Таким образом, код символа во входной системе кодирования можно использовать как индекс для нахождения соответствующего кода выходной системы кодирования в таблице . Программа перекодировки имеет вид. Схема перекодировки символов входной и выходной строк Программа представляет итеративный цикл, на каждой итерации которого перекодируется один байт. Используются два указателя — для входной и выходной строк, а также счетчик текущей длины для контроля окончания цикла. Значение очередного байта выходной строки определяется следующим образом. ОБРАТНАЯ ПЕРЕКОДИРОВКА СТРОКИ Эта. Обратную перекодировку можно свести к прямой, если составить новую таблицу. Как правило, в МП системах перекодировку . Поиск элемента таблицы, содержащего очередной код входной строки, осуществляется с помощью подпрограммы ПСК. Для получения индекса из этого абсолютного адреса вычитается адрес начала таблицы, затем значение индекса записывается в выходную строку. УДАЛЕНИЕ ФРАГМЕНТА МАССИВА Под удалением фрагмента массива понимается удаление содержимого некоторой области памяти, входящей в данный массив, при этом длина массива уменьшается на длину удаляемого фрагмента. Пусть имеется массив с начальным адресом А и конечным адресом В, из которого необходимо удалить фрагмент, начинающийся с адреса В и оканчивающийся адресом С . Как видно из рис. Программа удаления имеет вид. Команды, предшествующие обращению к этой подпрограмме, формируют необходимые значения входных параметров. При обратной перекодировке значение каждого кода входной строки отыскивается в таблице, а в соответствующее место выходной строки записывается индекс найденного элемента таблицы. Программа перекодировки представлена ниже. ГДЕ М ДЛИНА ВЫХОДНОЙ ; СТРОКИ. И . с . Схема удаления фрагмента массива Адресом начала массива. Длина перемещаемой области определяется как разность между адресами последнего байта массива и последнего удаляемого байта. При этом адрес конца массива. ВСТАВКА ФРАГМЕНТА В МАССИВ Пусть в некоторый массив, ограниченный адресами А и С, необходимо, начиная с адреса В, вставить содержимое области памяти, не принадлежащей этому массиву, при этом вся информация исходного массива сохраняется. Решение задачи осуществляется в два этапа. Сначала необходимо освободить в массиве место под вставляемый фрагмент. Для этого часть массива, ограниченная адресами В и С, сдвигается в памяти в сторону возрастания адресов на количество байтов, равное длине вставки, затем в освобожденную область копируется содержимое вставляемого фрагмента . Перемещение выполняется подпрограммой КОШ. Во втором фрагменте обеспечивается заполнение освобожденной области содержимым вставляемого фрагмента. Здесь вторично вызывается подпрограмма КОШ, для которой массивом. В данной программе в отличие от предыдущей перемещение информации выполняется с помощью подпрограммы КОП. Это объясняется тем, что если длина вставляемого фрагмента меньше длины остатка . Схема вставки фрагмента массива массива . Во втором фрагменте безразлично, какую подпрограмму применять. Подпрограмма КОШ используется только с целью унификации, хотя для уменьшения времени выполнения более целесообразно использовать подпрограмму КОП. ВСТАВКА ЭЛЕМЕНТА В СПИСОК Модификация списка в отличие от модификации массива не требует физического перемещения информации. Для выполнения вставки, элемента в список необходимо указать точку входа в него, т. адрес начала списка и место вставки в список, идентифицируемое по заданному значению ключа того элемента, после которого необходимо произвести вставку. Алгоритм решения этой задачи состоит в следующем. Последовательно просматривается весь список для нахождения элемента, значение поля ключа которого равно заданному, затем содержимое поля связи найденного элемента копируется в поле связи вставляемого элемента, а туда записывается адрес вставляемого элемента .