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

6.  Решить задачу Джозефуса с помощью двухсвязного циклического списка.

7.  Организовать стек, написать подпрограммы конкатенации (присоединения) одного стека к другому и обращения стека.

8.  Организовать двухсвязный циклический список и написать подпрограмму обращения этого списка.

9.  Применить стек для преобразования рекурсивной подпрограммы обхода дерева поиска в прямом порядке.

10.  Написать программу для вычисления введенного с клавиатуры логического выражения, состоящего из операций & (“и”), | (“или”), > (“больше”), < (“меньше”), = (“равно”), скобок и целых чисел. Приоритет операции “и” равен 3, приоритет “или” – двум, приоритеты остальных операций равны 1. Значения логического выражения равны 1 (“истина”) или 0 (“ложь”).

11.  Число задается в виде стека составляющих его цифр. Написать подпрограмму сложения двух чисел.

12.  Организовать двухсвязный циклический список. Написать подпрограмму объединения двух таких списков.

13.  Применить стек для преобразования рекурсивной подпрограммы обхода дерева в симметричном порядке.

14.  Применить дерево поиска для исключения одинаковых чисел из массива и расположения их в возрастающем порядке.

15.  Написать программу обхода вершин графа в ширину. Граф задан с помощью матрицы смежности.

16.  Вычислить значение заданного с клавиатуры арифметического выражения, состоящего из целых чисел, скобок и операций ‘*’ (“умножение”), ‘:’ (“деление”), ‘%’ (“остаток от деления”), ‘+’ (“сложение”), ‘–’ (“вычитание”). Приоритеты первых трех операций равны 2, остальных – 1.

17.  Написать программу обхода дерева поиска в глубину.

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

19.  Написать программу конкатенации (присоединения) двух деков.

20.  Задан текстовый файл, содержащий записанные через пробелы целые числа. Используя стек, вывести сначала в прямом порядке неотрицательные, а затем в обратном порядке отрицательные числа.

21.  Задан текстовый файл. Проверить его на соответствие угловых и квадратных скобок.

22.  Написать подпрограмму обращения очереди целых чисел.

23.  Написать подпрограмму обращения односвязного циклического списка.

24.  Организовать множество целых чисел как дерево поиска. Написать подпрограмму объединения двух множеств.

25.  Задан текстовый файл. Проверить его на соответствие фигурных и угловых скобок.

26.  Применить очередь для генерации перестановок с помощью преобразования рекурсивной подпрограммы.

27.  С помощью стека решить уравнение f(x) = 0 методом деления отрезка пополам. Предполагается, что функция f непрерывна на отрезке [a, b], и значения f(a) и f(b) имеют противоположные знаки.

28.  Определить многоугольник как циклический однонаправленный список. Написать подпрограмму его вывода на экран.

29.  Применить очередь для преобразования рекурсивной подпрограммы обхода дерева в обратном порядке.

30.  Задан текстовый файл, содержащий записанные через пробелы целые числа. Используя стек, вывести сначала все четные числа, а затем – нечетные.

Примеры выполнения задания 2

Пример 1

Задана текстовая строка. Проверить ее на соответствие круглых, квадратных и фигурных скобок.

Решение

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

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

// Проверка на соответствие скобок

#include <stdio.h>

#include <string.h> // для определения длины строки

#include <conio.h> // для очистки экрана