 |
Задачи для самостоятельного решения
|
|
|
|
...оставляю читателю для самостоятельного обдумывания, основанного на его собственных познаниях и наблюдениях.
Ф.Клейн. Лекции об икосаэдре и решение уравнений пятой степени
11.1. Пусть L обозначает кольцевой двунаправленный список с удаленным заглавным звеном. Определить, является ли кольцо пустым.
11.2. Разработать функцию для подсчета количества звеньев в заданном кольцевом двунаправленном списке с удаленным заглавным звеном.
11.3. Пусть L обозначает кольцевой двунаправленный список с удаленным заглавным звеном. Написать функцию, которая подсчитывает количество элементов списка L, у которых равные "соседи".
11.4. Пусть L обозначает кольцевой двунаправленный список с удаленным заглавным звеном. Написать функцию, выводящую на экран дисплея элементы списка L в обратном порядке.
11.5. Пусть L обозначает кольцевой двунаправленный список с удаленным заглавным звеном. Написать функцию удаления из списка L первого звена, содержащего отрицательный элемент (если такое звено найдется).
11.6. Пусть L обозначает кольцевой двунаправленный список с удаленным заглавным звеном. Написать функцию, которая в "конец" кольца добавляла бы все его звенья, располагая их в обратном порядке (например, по кольцу, содержащему целые числа 1,2,3 требуется построить кольцо, содержащее числа 1,2,3,3,2,1).
11.7. Пусть L обозначает кольцевой двунаправленный список с удаленным заглавным звеном. Определить, есть ли в списке L хотя бы одно звено, содержащее элемент, равный элементу следующего за ним звена.
11.8. Предположим, что уже построен кольцевой двунаправленный список с удаленным заглавным звеном, элементами которого являются стpоки. Написать программу, подсчитывающую количество строк в кольце, которые начинаются и оканчиваются одним и тем же символом.
|
|
|
11.9. Предположим, что уже построен и задан указателем P кольцевой двунаправленный список с удаленным заглавным звеном, элементами которого являются целые числа. Написать программу, которая находит минимальное значение элементов кольца и номер первого звена, содержащего элемент с этим значением.
11.10. "Считалка". N ребят располагаются по кругу. Начав отсчет от первого, удаляют каждого k-го, смыкая круг после каждого удаления. Определить порядок удаления ребят из круга. Решение этой задачи описать в виде программы, которая должна вывести на экран номера ребят в том порядке, в каком они удаляются из круга.
11.11. Предположим, что уже построены два двунаправленных кольца с удаленным заглавным звеном, элементами которых являются целые числа. Написать функцию, которая определяет, является ли содержимое данного кольца "перевертышем" содержимого другого кольца.
11.12. Пусть L обозначает кольцевой двунаправленный список с включенным заглавным звеном. Определить, является ли кольцо пустым.
11.13. Разработать функцию для подсчета количества звеньев в заданном двунаправленном кольцевом списке с включенным заглавным звеном.
11.14. Пусть L обозначает кольцевой двунаправленный список с включенным заглавным звеном. Написать функцию, которая подсчитывает количество элементов списка L, у которых равные "соседи".
11.15. Пусть L обозначает кольцевой двунаправленный список с включенным заглавным звеном. Написать функцию, выводящую на экран дисплея элементы кольца в обратном порядке.
11.16. Пусть L обозначает кольцевой двунаправленный список с включенным заглавным звеном. Написать функцию удаления из списка L первого звена, содержащего отрицательный элемент (если такое звено найдется).
11.17. Пусть L обозначает кольцевой двунаправленный список с включенным заглавным звеном. Написать функцию, которая в "конец" кольца добавляла бы все его звенья, располагая их в обратном порядке (например, по кольцу, содержащему целые числа 1,2,3 требуется построить кольцо, содержащее числа 1,2,3,3,2,1).
|
|
|
11.18. Пусть L обозначает кольцевой двунаправленный список с включенным заглавным звеном. Определить, есть ли в списке L хотя бы одно звено, содержащее элемент, равный элементу следующего за ним звена.
11.19. Предположим, что уже построен кольцевой двунаправленный список с включенным заглавным звеном, элементами которого являются строки. Написать программу, подсчитывающую количество строк в кольце, которые начинаются и оканчиваются одним и тем же символом.
11.20. Предположим, что уже построен и задан указателем P кольцевой двунаправленный список с включенным заглавным звеном, элементами которого являются целые числа. Написать программу, которая находит минимальное значение элементов кольца и номер первого звена, содержащего элемент с этим значением.
11.21. Предположим, что уже построены два двунаправленных кольца с включенным заглавным звеном, элементами которых являются целые числа. Написать функцию, которая определяет, является ли содержимое данного кольца "перевертышем" содержимого другого кольца.
Бинарные деревья поиска
Фрагмент теории
Какой он этот Слонопотам?
Неужели очень злой?
Идет ли он на свист? И если идет, то зачем?
Любит ли он поросят или нет?
И как он их любит?
А.А.Милн. Винни-Пух и все-все-все
Определение 1 (неформальное). Определим бинарное дерево как конечное множество элементов (называемых вершинами или узлами), которое:
q либо пусто,
q либо состоит из корня (некоторая выделенная нами вершина), связанного с двумя различными бинарными деревьями, называемыми левым и правым поддеревом корня.
Изобразим несколько бинарных деревьев:
 |
Для представления вершин бинарного дерева в памяти компьютера воспользуемся структурой языка C++, состоящей из четырех полей. Содержимым этих полей будут соответственно:
q информационное поле (ключ вершины),
q служебное поле (их может быть несколько!),
q указатель на левое поддерево,
|
|
|
q указатель на правое поддерево.
Таким образом, каждая вершина бинарного дерева описывается на языке C++ следующим образом:
struct node
{
int Key; // Ключ вершины.
int Count; // Счетчик количества вершин с одинаковыми ключами.
node *Left; // Указатель на "левого" сына.
node *Right; // Указатель на "правого" сына.
};
Определение 2 (неформальное). Бинарным (двоичным) деревом поиска называется бинарное (двоичное) дерево, в котором "слева" от любой вершины находятся вершины с элементами, меньшими элемента из этой вершины, а "справа" - вершины с большими элементами (предполагается, что все элементы вершин дерева попарно различны (что, впрочем, необязательно), и что их тип допускает применение операций сравнения).
|
|
|
