Примеры выполнения задания 2
Пример 1
Задана текстовая строка. Проверить ее на соответствие круглых, квадратных и фигурных скобок.
Решение
Будем читать текстовую строку по одному символу. Если встречается любая из открывающихся скобок, то запомним ее в стек. Если встретится закрывающаяся скобка, то в стеке должна находиться соответствующая ей открывающаяся скобка. В этом случае надо извлечь скобку из стека и перейти к чтению следующего символа. В противном случае вывести сообщение об ошибке.
Текст программы:
// Проверка на соответствие скобок
#include <stdio.h>
#include <string.h> // для определения длины строки
#include <conio.h> // для очистки экрана
// стек организуется с помощью макрокоманд
#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 );
res = insert( res, x );
return res;
}
}
main( )
{
clrscr();
s1 = insert( s1, 1 );
s1 = insert( s1, 2 );
s1 = insert( s1, 3 );
display( s1 );
s2 = insert( s2, 8 );
s2 = insert( s2, 9 );
puts(“\n”);
display( s2 );
puts(“\n”);
display( s3 = concat( s1, s2 ));
getch();
puts(“\n”);
display( reverse( s3 ));
}
Программа выведет:
1 2 3
8 9
1 2 3 8 9
9 8 3 2 1
Пример 4
Написать программу сложения целых чисел, заданных в виде линейных списков цифр. В начале линейного списка находятся младшие разряды, в конце – старшие.
Решение
Будем складывать цифры, соответствующие одинаковым разрядам. Поскольку сумма цифр может быть больше 9, то определим дополнительный бит и сложение будем производить с этим битом.
Вместе с подпрограммой добавления элемента к списку и подпрограммой вывода элементов списка, написанных рекурсивно, наша подпрограмма сложения будет иметь следующий текст:
// сложение длинных целых чисел,
// заданных в виде списков цифр
#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 )
{
display ( p->next );
printf("%-7d", p->info);
}
}
NODE *add( NODE *s, NODE *t )
{
int x, c=0 ; NODE* res=0 ;
while ((s!=0) || (t!=0))
{
if (s == 0) x = t->info + c;
else if (t==0) x = s->info +c ;
else x = s->info+t->info+c ;
if (x > 9){ x-=10; c=1;}
else c=0;
res = insert( res,x );
if(s!=0) s = s->next;
if(t!=0) t = t->next;
}
if (c == 1) res = insert( res, 1 );
return res;
}
main()
{
clrscr() ;
s1 = insert ( s1, 1);
s1 = insert ( s1, 2);
s1 = insert ( s1, 3);
display (s1);
s2 = insert ( s2, 9);
s2 = insert ( s2, 9);
puts("\n");
display (s2);
puts("\n");
display( add(s1,s2));
getch();
}
В главной программе складываются числа 321 и 99. Будет выведено:
3 2 1
9 9
4 2 0