Занятия 9-12 (8 часов). Использование классов-коллекций (ArrayList, HashTable, Stack, Queue) (динамические структуры данных).

1. Дан текстовый файл, в котором записана последовательность целых чисел. Сформировать из них два списка – в одном только четные элементы, в другом – нечетные.

2. Использование списка для представления полинома. Написать функции:

· Ввода полинома;

· Печати полинома;

· Вычисления полинома в заданной точке;

· Получения суммы двух полиномов;

· Получения произведения двух полиномов;

· Получения производной полинома;

· Получения первообразной полинома.

3. Использование списка для представления разреженной матрицы (матрицы с большим количеством нулевых элементов). Написать функции:

· Ввода матрицы;

· Печати матрицы;

· Суммирования двух матриц;

· Умножения двух матриц;

· Транспонирования матрицы.

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

5. Написать программу «Адресная книжка». Каждая запись в книжке содержит имя адресата, дату рождения и список номеров телефона (домашнего, мобильного и пр.). Предусмотреть возможность формирования адресной книжки с клавиатуры и из файла, печати адресной книжки, поиска записи по какому-либо признаку (фамилии, дате рождения или номеру телефона), добавления и удаления записей, сохранения в файл.

6. Написать программу «Каталог библиотеки». Каждая запись каталога содержит информацию о книге – название, автор, количество экземпляров, количество экземпляров «на руках». Предусмотреть возможность формирования каталога с клавиатуры и из файла, печати каталога, сохранения в файл, поиска книги по какому-либо признаку (например, автору или названию), добавления книг в библиотеку, удаления книг из нее, фиксации получения или возврата книги читателем.

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

8. Дан односвязный список, содержащий целые числа. Написать функцию, которая за один проход по списку распечатывает эти числа таким образом, что сначала распечатаются все отрицательные числа, затем – все положительные. Элементы, равные нулю, печататься не должны. Для решения задачи использовать очередь.

9. Получить двоичное представление заданного целого числа, используя стек.

10. Лабиринт задан в виде прямоугольной матрицы, в которой используются следующие обозначения: 0 – возможен проход, 1 – стена. Даны координаты позиция путника в лабиринте. С помощью стека распечатать путь, по которому путник может выйти из лабиринта, если выход существует. Считается, что путник вышел из лабиринта, если он находится на первой или последней строке матрицы, или на первом или последнем столбце. Путник может двигаться только по горизонтали или по вертикали.

11. Дана символьная строка, которая содержит правильное скобочное выражение. Для каждой пары скобок (открывающей и соответствующей ей закрывающей) распечатать номера их позиций в строке, упорядочив пары:

· по возрастанию номеров открывающих скобок;

· по возрастанию номеров закрывающих скобок.

12. Дана символьная строка, содержащая правильно записанное математическое выражение следующего вида:

 

<формула>::=<цифра>|M(<формула>,<формула>)

|m(<формула>,<формула>)

 

M – операция вычисления max из двух выражений, m - операция вычисления min из двух выражений. Написать функцию вычисления значения этого выражения.

13. Дана символьная строка, содержащая правильно записанное логическое выражение следующего вида:

 

<формула>::= T | F | And(<формула>, <формула>) |

Or(<формула>, <формула>) | Not (<формула>)

 

And – операция логического И, Or – операция логического ИЛИ, Not - операция логического НЕ.

Написать функцию вычисления этого выражения (функция должна возвращать true, если значение выражения равно T, false – в противном случае).

14. Дана символьная строка, содержащая постфиксную форму правильно записанного арифметического выражения, операндами которого являются цифры. Написать функцию вычисления этого выражения.

15. Можно использовать следующий алгоритм. Выражение просматривается слева направо. Если встречается цифра, то она заносится в стек. Если встречается знак операции, то из стека извлекаются два операнда, над ними выполняется операция и ее результат записывается в стек. Когда выражение заканчивается, в стеке остается одно число – значение выражения.