Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Лекция 11. Рекурсивные функции. Библиотечные функции обработки символьных строк
Рекурсивные функции
Рекурсивная функция – это функция, в определении которой есть обращение к себе самой.
Пример 11.1. Допустим, нужно вычислить n! (факториал числа n). Значение n! можно представить как произведение n на факториал (n-1) :
n! = n*(n-1)!
(n-1)! = (n-1)*(n-2)!
…
Если описать функцию вычисления n! , то для вычисления (n-1)! функция может вызвать саму себя. При вычислении (n-1)! функция должна вызывать себя, чтобы вычислить (n-2)! , и т.д. Чтобы процесс не был бесконечным, нужно учесть, что 1!=1 и 0!=1.
/* Рекурсивная функция вычисления n! */
float fact (int n)
{ if (n<0)
{ puts (“Недопустимый аргумент функции fact”);
exit (1); /* завершение выполнения программы */
}
if (n==1 || n==0) return 1;
return n*fact(n-1);
}
Пример вызова этой функции:
int k;
scanf (“%d”, &k);
printf (“%d! = %.0f”, k, fact(k));
Посмотрим, как происходит выполнение функции при k=4.
Последовательность рекурсивных
обращений:
fact (4) 24 Результат
4 * fact (3) 4 * 6
3 * fact (2) 3 * 2
2 * fact (1) 2 * 1
1 1
Хотя для этой задачи можно использовать рекурсию, но предпочтительнее нерекурсивный вариант (когда значение факториала числа вычисляется в цикле), т.к. не тратится время на многократные вызовы функции и передачу параметров. Достоинством рекурсивных функций является компактная запись.
Символьные строки и функции обработки строк
Символьная строка представляет собой последовательность символов, заканчивающуюся нуль-символом (‘\0’ c кодом 0).
Строковые константы заключаются в кавычки. При компиляции программы они автоматически дополняются нуль-символом. Строковые переменные объявляются как массивы символов, например:
char str[81];
char error[] = “Ошибка”; /* массив из 7 символов, включая ‘\0’ */
При работе со строками можно использовать указатели, например:
char *s = “Привет”;
…
s = error;
При объявлении указателя s ему присваивается адрес 1-го символа строки “Привет”, которая будет размещена в памяти отдельно от указателя. Последний оператор указателю s присваивает адрес массива error. Обратное присваивание error=s; будет неверным, т.к. имя массива – это константный указатель, его нельзя изменять.
Для ввода с клавиатуры строки символов служит библиотечная функция gets(), а для вывода – функция puts().
Пример:
char s1[81], s2[81];
char *s3 = “Привет!”;
puts (s3);
puts (“Введите две строки”);
gets (s1);
gets (s2);
В библиотеках Turbo C, Borland C++ имеется ряд функций обработки строк:
- определения длины строки (strlen),
- сравнения строк (strcmp, strncmp),
- копирования строк (strcpy, strncpy),
- сцепления строк (strcat, strncat),
- поиска символа в строке (strchr, strrchr, strpbrk),
- поиска подстроки в строке (strstr).
При их использовании в программу необходимо включить заголовочный файл string.h, содержащий объявления этих функций.
Рассмотрим одну из библиотечных функций - функцию сцепления двух заданных строк strcat(). Определение функции:
char *strcat (char *s1, char *s2);
Функция копирует строку s2 (на которую ссылается указатель s2) в конец строки s1 и возвращает значение s1 - ссылку на сцепленную строку.
Работу функции можно описать так:
char *strcat (char *s1, char *s2)
{ char *rs; /* ссылка на результирующую строку */
rs=s1; /* запоминание адреса начала строки s1 */
while (*s1!='\0') s1++; /* поиск конца строки s1 */
/* копирование строки s2 в конец s1 */
while (*s2!='\0')
{ *s1=*s2; s1++; s2++; }
*s1='\0';
return rs;
}
Как видите, функция не проверяет, достаточно ли памяти для результирующей строки. Вызывающая программа должна позаботиться об этом.
А теперь посмотрите на более компактную (но менее понятную) запись этой функции:
char *strcat (char *s1, char *s2)
{ char *rs;
rs=s1; /* запоминание адреса начала строки s1 */
while (*s1!='\0') s1++; /* поиск конца строки s1 */
while ((*s1++ = *s2++) !='\0'); /* копирование s2 в конец s1,
включая нуль-символ */
return rs;
}
Даже еще можно сократить текст функции, записав второй оператор while короче:
while (*s1++ = *s2++);
Непонятно? Каждый раз очередной символ из второй строки копируется в первую, затем значения указателей s1 и s2 увеличиваются на 1, т.e. происходит продвижение указателей к следующим символам строк. Этот процесс повторяется до тех пор , пока не скопируется нуль-символ (т.к. выход из цикла происходит при нулевом значении выражения в скобках).
С символьными строками можно работать как с массивами: обращаться к отдельным символам строки с помощью индекса. Ту же функцию сцепления строк можно написать иначе:
char *strcat (char *s1, char *s2)
{
int i=0, j=0; /* индексы символов строк s1 * и s2 */
while (s1[i]) i++; /* поиск конца строки s1 */
while ((s1[i++] = s2[j++])); /* копирование строки s2 в конец s1,
включая нуль-символ */
return s1;
}
Теперь вам предлагается самим написать одну из функций обработки строк из списка библиотечных, указанную преподавателем. Для проверки работы вашей функции напишите драйвер (программу отладки) в виде функции main(). Чтобы понять, какой должен быть результат работы своей функции, протестируйте сначала библиотечную функцию с помощью вашего драйвера (не забудьте включить директиву #include <string.h>).
Пример драйвера для функции сцепления строк strcat():
#include <stdio.h>
#include <conio.h>
/*****************************/
/* Тестирование ф-ции strcat */
/* Программа-драйвер */
/*****************************/
void main()
{ char str1[81],str2[81];
puts ("Введите две строки");
gets (str1);
gets (str2);
if (strlen(str1)+strlen(str2) < 81)
{ puts ("Результат:");
puts (strcat(str1,str2));
printf ("Строки после вызова функции сцепления:\n%s\n%s\n",
str1,str2);
}
else puts ("Не хватает памяти для результирующей строки");
getch();
}
Примечание. Если вы выполняете программы в среде Borland C++, при использовании библиотечных функций обработки строк (например, strlen(), как в данной программе) включите в программу директиву #include <string.h>. Имя же своей функции нужно изменить, чтобы оно не совпадало с библиотечным.
1. strlen - определить длину строки (число символов без завершающего
нуль-символа).
Объявление функции: int strlen(char *s);
Пример ее вызова:
char s[81];
gets(s);
printf ("Длина строки = %d\n", strlen(s));
2. strcmp - сравнить две строки.
Объявление: int strcmp (char *s1, char *s2);
0, если строки одинаковые;
Значение функции = разность кодов двух первых несовпадающих
символов, если строки разные.
Например, если s1="abcde", s2= "abca12", функция вернет число 3 (‘d’ – ‘a’=100 - 97).
3. strncmp - сравнить первые n символов двух строк.
Объявление: int strncmp (char *s1, char *s2, int n);
0, если первые n символов строк совпадают;
Значение функции = разность кодов двух первых несовпавших
символов в противном случае.
Например, если s1="123456", s2= "12789", n=4, функция вернет
число -4 (‘3’ – ‘7’ =51 -55). Если же n=2, то результатом будет 0.
4. strcpy - копировать строку s2 в s1.
Объявление: char *strcpy (char *s1, char *s2);
Значением функции является s1 - ссылка на первую строку.
Пример ее вызова:
char a[20], b[20];
strcpy (a, “Группа 4251”);
strcpy (b, a); /* копирование строки из массива a в b */
5. strncpy - копировать не более n символов строки s2 в s1.
Объявление: char *strncpy (char *s1, char *s2, int n);
Значением функции является s1 - ссылка на первую строку.
Например, если s1="1234567", s2= "abcde", n=4, функция вернет адрес строки s1="abcd567". Если задать n > длины строки s2, то в s1 скопируется вся строка s2 (включая нуль-символ) и строки получатся одинаковыми. Так при n=8, s2="abcde", результатом будет s1="abcde".
6. strcat - сцепить две строки s1 и s2 ( копировать вторую строку в конец первой).
Объявление: char *strcat (char *s1, char *s2);
Значением функции является s1 - ссылка на результирующую строку.
Например, если s1="abc", s2="defgh", то после сцепления строк s1="abcdefgh".
7. strncat - сцепить две строки s1 и s2, причем из второй строки копировать не более n символов.
Объявление: char *strncat (char *s1, char *s2, int n);
Значением функции является s1 - ссылка на результирующую строку (n символов строки s2 копируется в конец строки s1. Если n > длины s2, то копируется вся строка).
Например, если s1="abc", s2="12345", n=3, то после сцепления строк s1="abc123".
8. strchr - найти в строке s первое вхождение символа c.
Объявление: char *strchr (char *s, char c);
Значение функции - ссылка на первый символ c в строке s или NULL (пустая ссылка), если символа нет в строке.
Пример вызова функции:
char str[81], *p;
gets (str);
p = strchr(str, ‘a’);
if (p == NULL) puts (“В строке нет буквы ‘a’ ”);
else *p= ‘b’; /* замена в строке 1-й буквы a на b */
9. strrchr - найти в строке s последнее вхождение символа c.
Объявление: char *strrchr (char *s, char c);
Значение функции - ссылка на последний символ c в строке s или NULL (пустая ссылка), если символа нет в строке.
Пример вызова функции:
/* удаление всех пробелов в строке */
char str[81], *p;
. . .
while((p=strrchr(str, ‘ ’))!=NULL)
strcpy (p, p+1);
10. strpbrk - найти в строке s1 любой из множества символов, входящих
в строку s2.
Объявление: char *strpbrk (char *s1, char *s2);
Значение функции - ссылка на любой символ в строке s1, имеющийся в s2, или NULL (пустая ссылка), если символов из s2 нет в s1.
Пример вызова функции:
char str1[81], str2[81], *p;
. . .
p = strpbrk(str1, str2);
Например, если str1=”a1d2”, str2=”4321”, то указателю p будет присвоен адрес символа ‘1’ в строке str1 (функция просматривает поочередно символы первой строки и ищет их во второй строке, пока не найдет или не кончится 1-я строка).
11. strstr - найти в строке s1 первое вхождение строки s2.
Объявление: char *strstr (char *s1, char *s2);
Значение функции - ссылка на первое вхождение s2 в s1 или NULL (пустая ссылка), если подстроки s2 нет в s1.
Например, если s1="ab1111234cd1123", s2= "1123", функция вернет адрес третьего символа ‘1’ в строке s1, с которого начинается подстрока "1123".
Пример вызова функции:
char text []= "Группа 4172", *p;
if ((p = strstr(text, "4172" ))!=NULL)
strcpy(p, "4272"); /* В результате text = "Группа 4272" */
Выполнение контрольных заданий
1. Получите у преподавателя индивидуальное задание (номер функции из перечня библиотечных функций).
2. Напишите программу-драйвер для проверки своей функции.
3. Подберите тесты для проверки функции и протестируйте на компьютере сначала библиотечную функцию, а затем свою. Результаты должны совпадать.
Указание. Если функция возвращает адрес строки или какого-то символа строки, выводите не адрес, а саму строку или ее часть, начиная с найденного адреса.
4. Оформите и сдайте отчет.
PAGE 113