Примеры алгоритмов работы со строками

Пример 1. Добавить одну строку (s) к концу другой (t).

int main()

{

char t[20]="ABCDEF", s[]="uvxyz", *tp=t, *sp=s;

// Первый вариант

// Сначала находим конец строки- приёмника t.

while (*tp!='\0') tp++;

/* После выполнения этого цикла в tp будет адрес символа, следующего после последнего символа строки (буквы F), то есть адрес символа конца строки. */

while ((*tp=*sp)!='\0')

{tp++; sp++; }

puts(t);

// t и tp — адреса начала одной и той же области памяти со строкой

// "ABCDEF"

getch(); return 0;

}

В последнем цикле порядок выполнения операций следующий:

1) *sp — взять символ, на который указывает sp.

2) *tp=*sp занести этот символ в ячейку по адресу tp.

3) (*tp=*sp)!='\0') сравнить его с символом конца строки.

4) Если это был не символ конца строки, то в теле цикла увеличиваем на один байт значения обоих указателей, то есть переходим к следующим символам. Арифметические операции над указателями при работе со строками выполняются обычным образом, так как один символ занимает один байт. Поэтому tp++; увеличивает значение адреса на единицу, а не на 1*4, как это было, например, для целочисленного массива.В противном случае после копирования символа '\0' осуществляется выход из цикла.

Зачем внутренние скобки в заголовке оператора while? Без скобок

while (*tp=*sp!='\0') // ошибка

сначала выполнялась бы операция сравнения, так как она имеет более высокий приоритет, чем операция присваивания. И результат сравнения (0 или 1) запомнился бы в *tp. Но так как символьный и целый типы в языке С совместимы (см. первый семестр), то ни ошибки компиляции, ни ошибки этапа выполнения не будет, но программа будет выполняться неправильно.

Второй вариант реализации алгоритма соединения двух строк.

Если вышеприведённую программу продолжать, то сначала надо выполнить

tp=t; sp=s;.

Во-первых, получить адрес символа конца строки можно и так:

tp+=strlen(t);

где встроенная функция strlen(t) находит длину строки, то есть количество символов до символа '\0'.

Соединение двух строк можно выполнить компактнее и “красивее”:

while (*tp++=*sp++); // обязательно в конце заголовка символ “;”.

puts(t); puts(s);

Обратим внимание, что в цикле операция ++ постфиксная и она относится не к символу, а к указателю. Увеличивается на единицу не код символа, а значение указателя, то есть мы “перемещаемся” к следующему символу.

Упражнения.

1) Записать короче, более компактно первый цикл для поиска конца строки-приёмника t.

2) Наоборот, записать более простой, понятный (в стиле языка Pascal) вариант второго цикла, в котором в заголовке оператора while нельзя использовать присваивание.

3) Составить и проверить функцию для реализации аналогичного алгоритма копирования одной строки в другую.

Пример2. Составить и проверить функции для выделения подстроки и для удаления подстроки.

/* Выделение подстроки: s1 – адрес начала исходной строки, s2 – адрес выделенной подстроки, n_start – номер символа, начиная с которого выделяем подстроку, size_sub – количество выделяемых символов */

void mysub(char *s1, char *s2, int n_start, int size_sub)

{ char *p=s1;

p+=n_start;

strncpy (s2, p, size_sub);

}

/* strncpy — стандартная функция для копирования size_sub символов, начиная с адреса p, в строку по адресу s2 */

/* Из строки s, начиная с символа с номером n_start, удаляем n_del символов */

void mydelete (char *s, int n_start, int n_del)

{ char *p=s,*q;

p+=n_start;

q=p+n_del;

strcpy(p,q);

/* стандартная функция для копирования всей строки, начиная с адреса q, в строку с адресом p */

}

int main(int argc, char* argv[])

{

char S2[]="Variant: Testing of function";

char *Sub=new char[20]; mysub(S2,Sub,20,8);

/*С помощью “своей” функции из S2, начиная с символа с номером 20, выделили 8 символов, т. е. слово “ function ” */

puts(Sub); getch();

mydelete(S2,9,7);

/*С помощью “своей” функции из S2, начиная с символа с номером 9, удалили 7 символов, т. е. удалили “ Testing ” */

puts(S2); getch();

return 0;

}

Пример 3. Функция считает, сколько раз подстрока sub встречается в строке s

int count_of_sub(char *s, char *sub)

{ unsigned k=0;

char *p=s, *q;

while(1)

{ q=strstr(p,sub);

/* Стандартная функция находит адрес первого появления подстроки sub. При этом поиск осуществляется, начиная с адреса p. Если подстрока не найдена, то q=NULL, что равносильно false */

if (!q) return k; // Если подстрока не найдена, выход из функции

k++;

p=q+strlen(sub);

/* В p помещаем адрес символа, следующего после найденной подстроки. Дальше поиск будет осуществляться, начиная с этого символа */

}

}

int main()

{ char S[]="Text abcdetexttextxyztext";

cout<<count_of_sub(S,"text");

getch(); return 0;

}

В функции main() нашли, сколько раз в строке S встречается подстрока “text”. Программа выведет число 3, а не 4, так как первый раз “Text” начинается с большой буквы.

Рассматривается более сложный вариант этого же примера. Ввести последовательность строк, не формируя из них массива строк. Ввод не менее трёх подряд идущих символов “@” – конец ввода. Для каждой строки найти, сколько раз подстрока “ for ” встречается в ней. Найти наибольшее такое количество. Заданную подстроку вывести другим цветом в разреженном виде, т. е. с пробелами между символами. После последнего for текст в строке не выводится

int main()

{ clrscr(); char t[80], *p=t, *q;

int m, n, nmax=0; // nmax – наибольшее количество повторений “for”

gets(t); // ввод первой строки

do // цикл для анализа всех строк

{ p=t; n=0; // n – количество “for” в одной строке

do { // цикл для анализа одной строки

char *u;

textcolor(2); // зелёный цвет для вывода текста

q=strstr(p,"for");

for(u=p;u<q;u++) // вывод текста, отличного от “for”

cprintf("%c",*u);

if(!q) break;

// выход из внутреннего цикла, если не нашли подстроку

n++;

p=q+3; // 3 – длина строки “for”

textcolor(11); // голубой цвет для вывода “for”

for(;q<p;q++) cprintf("%c ",*q);

// вывод “for” c пробелами между символами

}

while(*p);

cout<<" Number of \“for\”"<<n<<endl;

if(n>nmax) nmax=n;

gets(t); // ввод следующей строки

}

while(!strstr(t,"@@@"));

cout<< " MAX "<<nmax<<endl;

getch(); return 0;

}

Выход из внешнего цикла выполнится, если введём три и более подряд расположенные указанные символы “@”.

Вариант а. В случае, если введём в самом начале, или после набранной строки три и более подряд идущих символа ‘@’, например, “@@@@@”, то функция strstr(t,"@@@") найдёт адрес первого появления трёх символов в строке. Так как такие символы, а, точнее, последовательность из трёх символов ‘@’, есть в строке, то будет найден не пустой адрес. Это равносильно true, и, так как используется операция отрицания, выполняется выход из внешнего цикла.

Вариант b. Введём текст, подлежащий обработке, без указанной последовательности из трёх подряд идущих символов ‘@’. Тогда функция strstr(t,"@@@") возвращает нулевой указатель NULL, так как подстроки "@@@" нет. Это равносильно false. Поэтому с учётом операции “отрицание” выражение в скобках внешнего оператора do … while примет значение true и цикл будет продолжен. Такой же результат будет и в случае, если введём в строке "@@" или "@"

Пример 4.

Под словом будем понимать последовательность символов, отличных от специальных знаков, используемых в качестве разделителей слов. Некоторые из этих символов перечислены в тексте программы в строке pat. При тестировании будем использовать только указанные здесь символы для разделения слов. Другие разделители, не указанные в строке, будут восприниматься как символы слова. Между словами может быть любое количество таких не обязательно одинаковых символов (например, три подряд идущих точки, скобка и пробел и т.п.). В строке найти количество слов, у которых первый и последний символы одинаковые.

int main()

{ char t[80], pat[]=",.;:-()", *p=t, c1, c2; int k=0;

gets(t);

do

{ p+=strspn(p,pat); // в ячейке p – адрес начала слова

c1=*p; // первый символ слова

p+=strcspn(p,pat); /* адрес символа, следующего после последнего символа слова, т.е. адрес первого разделителя */

c2=*(p-1); // последний символ слова

if (c1 = = c2)k++; //сравниваем первый и последний символы слова

}

while (*p); /* пока не найден символ конца строки, который играет роль false при сравнении

или while (*p!='\0'); */

cout<<"\nResult "<<k<<endl;

getch(); return 0;

}

Функция strspn возвращает количество подряд идущих символов, которые есть в строке pat, начиная с адреса p. Поэтому оператор

p+=strspn(p,pat)

изменяет адрес на найденное количество. Другими словами, мы c помощью переменной указателя p “перемещаемся” в начало слова. Функция strcspn возвращает количество подряд идущих символов, которых нет в строке pat, начиная с адреса p. Поэтому таким образом “перемещаемся” за последний символ слова.

Заметим, что если надо проанализировать длину слова и (или) выполнить посимвольный анализ самого слова, то вместо одного оператора

p+=strcspn(p,pat);

необходимо записать два. Сначала отдельно находим длину слова, например,

Len= strcspn(p,pat);,

где Len — переменная целого типа. Затем анализируем полученную длину и (или) слово, то есть Len символов, начиная с адреса p. Выполняем требуемые действия, и изменяем значение указателя p:

p+=Len;