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

Лекция 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)); Выполнение контрольных заданий 1. Получите у преподавателя индивидуальное задание (номер функции из перечня библиотечных функций). 2. Напишите программу-драйвер для проверки своей функции. 3. Подберите тесты для проверки функции и протестируйте на компьютере сначала библиотечную функцию, а затем свою. Результаты должны совпадать. Указание. Если функция возвращает адрес строки или какого-то символа строки, выводите не адрес, а саму строку или ее часть, начиная с найденного адреса. 4. Оформите и сдайте отчет.