Алгоритмы обработки символьной информации на языке Си
Базовая структура и сущность программирования
жүктеу/скачать 89,27 Kb.
|
| 1.2 Базовая структура и сущность программирования
Существует ряд кодов, называемых символами, которые не соответствуют определенным действиям во время ввода-вывода. Например, символ с кодом 1310 (0x0D) - «возврат автомобиля» соответствует перемещению курсора в начало строки. Символьные константы, начинающиеся с косой черты, используются для их представления в программе. Действие с постоянным именем \ звуковой сигнал \ b bs Курсор на одну позицию назад \ f Перейти в начало FF (формат перевода) \ N lf Перейти на одну строку вниз (обратная строка) \ r cr Вернуться к первой позиции строки \ t ht Перейти на позицию умноженную на 8 (таблица) \ v vt Вертикальная табуляция по строкам \\ \ '\ »\? Просмотр символов \, ', ",? \ NN Символ с восьмеричным кодом NN. \ xnn Символ с шестнадцатеричным кодом NN Символ с кодом \ 0 0 Некоторые программы обработки символов и строк и стандартные функции (isdigit, isalpha) используют числа, прописные и строчные (строчные и прописные) латинские буквы для увеличения значений кода: Дорога. Строка - это последовательность символов, ограниченная символом с кодом 0, то есть '\ 0'. Его определение показывает, что это переменный объект измерения. Место хранения строки - это массив символов. Связь между строкой и массивом символов - суть отношения - строка - это структура данных, а массив - переменная: * строка хранится в массиве символов, массив символов может быть настроен строкой или заполнен программно: * строка - это последовательность, ограниченная символом '\ 0', поэтому вы должны работать с ней в цикле, ограниченном размером массива, а не символом в конце строки: for (i = 0; B [i]! = '\ 0'; i ++) ... * размер массива и длина строки не соответствуют транслятору, за который отвечает программа (программист, который ее написал): chak C [20], B [] = "путь слишком длинный для C"; // контролируем переполнение массива // и ограничиваем путь его размером для (я = 0; я <19 && B [я]! = '\ 0'; я ++) C [я] = B [я]; C [i] = '\ 0'; Строковая константа - это последовательность символов, заключенная в двойные кавычки. Допускается использование неизменяемых символов. Строковая константа автоматически дополняется символом '\ 0', который может быть задан массивом, размер которого определяется размером строки: char A [80] = "123456 \ r \ n"; char B [] = "ааааа \ 033bbbb"; ... "Сюда" ... Отправить текст. Текст - это строка, и наш уровень обработки данных не позволяет нам предложить ничего, кроме массива двумерных символов для ее хранения: char A [20] [80]; char B [] [40] = {"строка", "дополнительная строка", "0000", "ABCDEF"}; Первый индекс двумерного массива соответствует номеру строки, второй - номеру символа в нем: для (int я = 0; я <20; я ++) for (int k = 0; A [i] [k]! = '\ 0'; k ++) {...} // Работа 1-й строки c Текстовые файлы. Формат строки, ограниченный до '\ 0', используется для отображения в памяти программы. При чтении строки или последовательности символов из внешнего потока (клавиатуры, экрана, файла) разделителем строки является другой символ - '\ n' («перевести строку», строка (LF)). При вызове функций, работающих со строками, возможны разные «тонкости». Например, функция чтения из потока клавиатуры возвращает строку с одним ограниченным символом '\ 0', а функция чтения из файла потока дополнительно помещает символ '\ P', если строка соответствует выделенному буферу (массиву символов). Функции стандартной библиотеки ввода-вывода необходимы для «сглаживания» несоответствий из-за исторически сложившихся форм и анахронизмов в представлении о различных устройствах ввода-вывода и операционных системах (текстовый файл, клавиатура, экран) и приведения их в единый внутренний формат. Стандартные методы дорожной обработки Большинство программ обработки строк используют символ после символа - строку после символа строки. Если вам нужно изменить содержимое строки во время редактирования, есть два варианта: * редактировать строку «на месте», вставляя и удаляя символы или фрагменты; * Организовать символьную перезапись входной строки в выходную (это несложно) путем копирования необходимых и измененных фрагментов. Обработка символов с учетом особенностей кодирования. Некоторые программы используют свойства последовательности значений кодов латинских букв и цифр. Такое программирование в основном машинно-зависимое, но может быть отнесено к языку из-за «нерушимости» стандарта представления символов. Вычтите десятичную цифру из значения целочисленной переменной в диапазоне 0. int H; char с типом; с = н + '0'; Вычтите шестнадцатеричную цифру из значения целочисленной переменной в диапазоне 0..15: Если (N <= 9) C = N + '0'; в противном случае c = N-10 + 'A'; Возьмите значение целочисленной переменной с десятичного знака: если (c> = '0' && C <= '9') N = c - '0'; Вычтите значение целочисленной переменной из шестнадцатеричного числа: если (c> = '0' && C <= '9') N = c - '0'; если (c> = 'A' & c <= 'F') C = C - 'A' + 10; Преобразование строчных латинских букв в прописные если (c> = 'A' && c <= 'i') c = c - 'a' + 'a'; Подсчитайте количество слов. Следует отметить, что программа не может просто «увидеть слово», ей нужно формальное условие, чтобы найти его. Это может быть конец слова или его начало. Начало слова определяется комбинацией пар символов: текущий - символ слова (не пробел), которому предшествует пробел или начало строки. Устраните лишние пробелы. Стоит запомнить одно правило: количество индексов определяет количество независимых перемещений (степеней свободы) на массивах. Если индекс для входной строки может быть изменен в заголовке цикла просмотра пост-символа (равномерное «движение» в строке), то для выходной строки он изменяется только при добавлении следующего символа. Кроме того, не забудьте закрыть линию выхода символом в конце строки. C1 context [J ++] = имеет особое значение: добавить следующий символ к выходной строке и перейти к следующему. Поскольку размер «сжатой» части строки при перезаписи всегда меньше оригинала, вы можете объединить строки ввода и вывода в один массив (новое содержимое будет поверх старого). Сравнение путей. При работе со строками часто необходимо сравнивать их в алфавитном порядке. Самый простой способ - сравнить коды символов (числа, латинские буквы, строчные латинские буквы), гарантирующие их алфавитную последовательность при наличии последовательного кодирования латинских букв и цифр. STR, STR, STR strcmp. Обратите внимание, что массивы символов отображаются без знака. В противном случае коды весом более 0x80 (кириллические символы) будут иметь отрицательные значения и будут помещены «раньше» в латинский алфавит с положительными значениями кодов. Чтобы определить порядок символов в алфавите, символы располагаются в порядке убывания их «шкалы», а порядковый номер символа используется как описание его «веса». Выберите встроенные фрагменты. Этот пример охватывает все вышеперечисленные методы работы с путем: поиск символов путем запоминания их позиций, удаление фрагментов, преобразование числа из внутренней формы во внешнюю. Сложность задачи требует применения принципа модульной конструкции. Фрагменты, расположенные один над другим, следует переписывать один за другим, оставляя уникальный номер, когда фрагмент не на месте. Пример: A {B {c} B} A {D {e {g} e} D} a => {C} {b1b} {g} {e3e} {d4d} a2a5a Решим проблему отдельно. Конечно, нам понадобится функция, которая ищет открывающиеся скобки для вставленного внутри фрагмента. С его помощью можно организовать уже знакомую нам перезапись и «перекус». Основная идея алгоритма поиска заключается в использовании счетчика переменных, который умножается на 1 для каждой открывающейся круглой скобки и уменьшается на 1 для каждой закрывающей скобки. В этом случае фиксируется максимальное значение счетчика и расположение элемента, в котором он находится. // ------------------------------------------------- ------ 44-05.cpp // - - - - Для пары с максимальной глубиной возвращается индекс круглых скобок "{" int find (char c []) { int i; // Индексировать строку int k; // / счетчик слотов int max; // строим максимальное гнездо int b; // Максимальный индекс "{" for (i = 0, max = 0, b = -1; c [i]! = 0; i ++) { если (c [i] == '}') k--; if (c [i] == '{') { k ++; если (k> max) {max = k; б = я; }} }} если (k! = 0) вернуть 0; // "Дурацкая" защита, без скобок return b; }} Другой вариант: функция ищет первую внутреннюю пару круглых скобок. Расположение скобок сохраняется, и когда скобки найдены, возвращается индекс последних скобок. Учтите, что его тоже можно использовать, только порядок получения фрагментов будет другим. // ------------------------------------------------- ------ 44-06.cpp // - - - - Для первой подпары возвращается индекс скобки "{" int find (char c []) { int i; // Индексировать строку int b; // Максимальный индекс "{" for (i = 0, b = -1; c [i]! = 0; i ++) { if (c [i] == '}') return b; если (c [i] == '{') b = i; }} return b;} Идея базового алгоритма состоит в том, чтобы последовательно пронумеровать фрагменты, «откусанные» от входной строки, а на место каждого ставится его номер - значение счетчика, которое переводится в форму внешнего вида. // ------------------------------------------------- ------ 44-07.cpp // - - - - - «Прикусить» скопировать вставленные фрагменты » недействительная копия (char c1 [], char c2 []) { int я = 0; // Индекс на восточной линии int k; // индекс найденного фрагмента int n; // Запоминаем начало фрагмента int m; // Счетчик фрагментов for (m = 1; (k = find (c1))! = - 1; m ++) {// когда есть фрагменты для (n = k; c1 [k]! = '}'; k ++, i ++) c2 [i] = c1 [k]; // фрагмент и его "}" c2 [i ++] = c1 [k ++]; // если (m / 10! = 0) c1 [N ++] = m / 10 + '0'; // Вместо двух чисел c1 [N ++] = m% 10 + '0'; // числа во внешней форме для (; c1 [k]! = 0; k ++, n ++) c1 [n] = c1 [k]; C1 [n] = 0;} // Перемещаем "хвостик" наверх для (k = 0; c1 [k]! = 0; k ++, i ++) c2 [i] = c1 [k]; // заменяем отходы C2 [i] = 0;} // вводная строка Практический совет - избегать сложных расчетов индексов. Рекомендуется начать индексацию для каждого сегмента дорожки и перемещать их независимо при необходимости. Например, что происходит при «уплотнении» строки - после перезаписи фрагмента, в котором находится индекс k, она «останавливается» в начале «хвоста» строки, который заменяется индексом N - началом удаляемого фрагмента. Кроме того, написанные числа заменяют начальную букву на один или два символа. Таким образом, фрагмент заменяется его номером в строке ввода. жүктеу/скачать 89,27 Kb. Достарыңызбен бөлісу:
|