Информатика и технология программирования


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


Контекстная замена -поиск и замена в строке фрагментов, заданных одной строкой (контекста) на фрагмент, заданный другой, например:


Исходная строка Заменяемая Заменяющая Результат
строка строка
"abc234pe4234e" "234" "_00_" "abc_00_pe4_00_e"

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

Шаг 1: Исходные данные и результат. Строки заданы массивами символов s,s1,s2. Результирующая строка размещается в том же массиве, что и исходная. Контроль размерности не производится:


void Context(char s[], char s1[], char s2[]) {...}

Шаг 2: Основной цикл программы состоит в посимвольной проверке строки на вхождение в нее подстроки, начиная с текущего символа. В случае вхождения производится замена:


void Context(char s[], char s1[], char s2[])
{
int n;
for (n=0; s[n] !='\0'; n++)
{
// Если начиная с n-го символа расположена


// подстрока s1, заменить ее на s2 в строке


}
}

Шаг 3: Проверка утверждения, что начиная с n-го символа в строке s расположена подстрока s2:


int i;
for (i=0; s[n+i] !='\0' &#38&#38 s1[i] !='\0'; i++)
if (s[n+i] != s1[i]) break;
if (s1[n+i]=='\0')
{
// заменить s1 на s2 в строке, начиная с s[n]


}

Шаг 4: Замена подстроки s1 на s2, начиная с n-го символа строки s, заключается перемещении "хвоста" строки s вправо или влево в зависимости от знака разности длин строк и в переписывании строки s2 на место строки s1. Для получения длины строки воспользуемся стандартной функцией strlen:


int l2,dd,k;
l2 = strlen(s2)
dd = l2 - strlen(s1);
if (dd != 0)
{
// сдвинуть "хвост" строки s на dd символов


}
for (k = 0; k &#60 l2; k++)
s[n+k] = s2[k];

Шаг 5: Для сдвига всего "хвоста" (для простоты, начиная с n-го символа) влево (dd &#60 0) необходимо все символы, начиная с n+dd перенести на dd позиций влево. Для перемещения вправо нужно сначала найти конец строки, чтобы от него производить перемещения символов с убывающим индексом


if (dd &#60 0)
{
for (k=n; s[k+dd]!='\0'; k++)
s[k] = s[k+dd];
s[k]='\0';
}
else
{
for (k=n; s[k]!='\0'; k++);
for (; k != n; k--)
s[k+dd] = s[k];
}

Примечание: в случае удачной замены проверка возможности последующей замены производится, начиная со следующего символа. Тогда при наличии замен вида "nnn" на "nnnn..." программа будет расширять строку до бесконечности.




Начало  Назад  Вперед



Книжный магазин