Рекурсивные функции. Библиотечные функции обработки символьных строк

Лекция 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 ). Пример драйвера для функции сцепления строк strcat(): #include #include /*****************************/ /* Тестирование ф-ции 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 . Имя же своей функции нужно изменить, чтобы оно не совпадало с библиотечным. Библиотечные функции обработки строк 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. Оформите и сдайте отчет.