Рекурсивный алгоритм. Определение рекурсивной функцию int Lat, возвращающую количество латинских букв в текстовом файле, страница 9

// стек организуется с помощью макрокоманд

#define pop() stk[deep++]

#define push(a) stk[--deep]=a

int stk[200], deep=200;  // стек целых чисел

char *s = "[a(b)]cabb{}"; // строка без ошибок

main()

{

int i, t, err = 0;

for (i=0; i<strlen(s);i++)

switch(s[i])

{

case '(': case '[': case '{':

push(s[i]); break;

case ')': if ( pop() != '(') {printf("\n error()"); err = 1;} break;

case ']': if ( pop() != '[') {printf("\n error[]"); err = 1;} break;

case '}': if ( pop() != '{') {printf("\n error{}"); err = 1;} break;

default:;

}

if (!err) printf(“\n No errors”);

getch();  // задержка

}

Пример 2

Текстовый файл содержит записанные через пробелы целые числа. Определить, сколько раз повторится в файле каждое из этих чисел.

Решение

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

Текст программы:

// нахождение частоты повторения целых чисел

#include <stdio.h>

#include <string.h>

#include <alloc.h>

#include <conio.h>

#define TNULL ( struct node* ) 0

typedef struct nd

{

int info, freq;

struct nd *left;

struct nd *right;

} NODE;

NODE *tree = TNULL;

NODE *add( NODE *root, int x )

{

if( root == TNULL )

{

root = (NODE*) malloc(sizeof(NODE));

root->info = x;

root->left = root->right = TNULL;

root->freq = 1;

return root;

}

else

{

if( root->info == x )

{

root->freq++;

return root;

}

if( x < root->info )

{

root->left = add( root->left, x );

return root;

}

else

{

root->right = add( root->right, x );

return root;

}

}

}

void display( NODE *p )

{

if( p != TNULL )

{

display( p->left );

printf(“\n число %d повторяется %d раз”, p->info, p->freq);

display( p->right );

}

}

main( )

{

int x;

FILE *fp = fopen(“integer.txt”, “r”); clrscr();

while(fscanf(fp, “%d”, &x) != EOF) tree = add( tree, x);

display( tree );

getch( );

}

Если файл integer.txt состоит из чисел

10     20    –2    0     10    –12   34, то программа выведет число -12 повторяется 1 раз число -2 повторяется 1 раз число 0 повторяется 1 раз число 10 повторяется 2 раз число 20 повторяется 1 раз число 34 повторяется 1 раз

Пример 3

Написать подпрограммы обращения и конкатенации линейных списков.

Решение

Организуем линейный список, у которого подпрограмма добавления элемента определяется рекурсивно.

Для того чтобы произвести конкатенацию списков, нужно сначала установить указатель на конец первого списка, а затем в конечном элементе первого списка заменить нулевой указатель указателем на начало второго списка.

Напишем подпрограмму обращения списка, используя рекурсию. В этой подпрограмме указатель устанавливается на следующий элемент, затем список, начинающийся со следующего элемента, рекурсивно обращается, и начальный элемент ставится в конец полученного списка.

// обращение и объединение списков

#include <stdio.h>

#include <string.h>

#include <alloc.h>

#include <conio.h>

typedef struct nd

{

int info;

struct nd *next;

} NODE;

NODE *s1 = 0, *s2 = 0, *s3 = 0;

NODE *insert( NODE *root, int x )

{

if( root == 0 )

{

root = (NODE*) malloc(sizeof(NODE));

root->info = x;

root->next = 0;

}

else root->next = insert( root->next, x );

return root;

}

void display( NODE *p )

{

if( p != 0 )

{

printf(“%-7d”, p->info);

display( p->next );

}

}

NODE *concat( NODE *s, NODE *t)

{

NODE *prev, *cur = s;

if( s == 0 ) return t;

if( t == 0 ) return s;

while(cur != 0)

{

prev = cur;

cur = cur->next;

}

prev->next = t;

return s;

}

NODE *reverse( NODE *s )

{

NODE *res = 0; int x;

if( s == 0 ) return 0;

else

{

x = s->info;

res = reverse( s->next );