Лабораторная работа № 6. Шаблоны классов

Задание I. Разработать шаблон класса для работы с однонаправленным некольцевым списком. Реализовать следующие действия

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

  1. статья по однонаправленным спискам;
  2. однонаправленные списки в C++

 

Протестировать шаблон класса на следующих типах данных: целые, вещественные, символьные, строки.

Решить задачу

  1. Составить программу, которая удаляет из списка L все элементы E, если такие есть.
  2. Составить программу, которая в списке L заменяет первое вхождение списка L1 (если такое есть) на список L2.
  3. Даны упорядоченные списки L1 и L2. Вставить элементы списка L2 в список L1, не нарушая его упорядоченности.
  4. Составить программу, которая удаляет из списка L за каждым вхождением элемента E один элемент, если такой есть и он отличен от E.
  5. Составить программу, которая удаляет из списка L все элементы с указанным значением.
  6. Составить программу, которая проверяет, есть ли в списке L хотя бы два одинаковых элемента.
  7. Составить программу, которая переносит в конец непустого списка L его первый элемент.
  8. Составить программу, которая вставляет в список L за первым вхождением элемента E все элементы списка L, если E входит в L.
  9. Составить программу, которая переворачивает список L, т.е. изменяет ссылки в этом списке так, чтобы его элементы оказались расположенными в обратном порядке.
  10. Составить программу, которая в списке L из каждой группы подряд идущих одинаковых элементов оставляет только один.
  11. Составить программу, которая формирует список L, включив в него по одному разу элементы, которые входят одновременно в оба списка L1 и L2.
  12. Составить программу, которая формирует список L, включив в него по одному разу элементы, которые входят в список L1, но не входят в список L2.
  13. Составить программу, которая формирует список L включив в него по одному разу элементы, которые входят в один из списков L1 и L2, но в то же время не входит в другой из них.
  14. Оставить в списке только первые вхождения одинаковых элементов.
  15. Определить количество различных элементов списка.
  16. Повторить дважды каждое вхождение элемента Е в список L.

 

 

Задание II. Разработать шаблон класса для работы с двунаправленным некольцевым списком. Реализовать следующие действия

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

  1. статья по двунаправленным спискам;
  2. списки в C++

 

Протестировать шаблон класса на следующих типах данных: целые, вещественные, символьные, строки.

Решить задачу

  1. печатает в обратном порядке элементы непустого списка L;
  2. сортировка элементов списка по возрастанию;
  3. подсчитывает количество элементов списка L, у которых равные «соседи»;
  4. определяет, есть ли в списке L хотя бы один элемент, который равен следующему за ним (по кругу) элементу (первый элемент счиать следующим для последнего);
  5. в списке L переставляет в обратном порядке все элементы между первым и последним вхождениями элемента E, если E входит в L не менее двух раз;
  6. удаляет из списка L первое вхождение заданного элемента, если такой есть;
  7. из списка L, содержащего не менее двух элементов, удаляет все элементы, у которых одинаковые «соседи» (первый и последний элементы считать соседями);
  8. добавляет в начало и конец списка L новый элемент E
  9. в списке L справа и слева от элемента E вставляет элемент F;
  10. строит двунаправленный список L по однонаправленному списку L1;
  11. в конец непустого списка L добавляет все его элементы, располагая их в обратном порядке (например, по списку из элементов 1, 2, 3 требуется построить список из элементов 1, 2, 3, 3, 2, 1);
  12. проверяет симметричность участка списка с i-го по j-й элемент (i < j);
  13. удалить все элементы между минимальным и максимальным элементами;
  14. если у элемента со значением E "соседи" не равны, поменять их местами;
  15. если у элемента со значением E "соседи" не равны, заменить их на элемент F;
  16. поменять местами фрагменты списка между минимальным и максимальным элементами.

 

 

Задание III. Разработать шаблон класса для работы с двоичным деревом поиска. Реализовать следующие действия

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

  1. статья по двоичным деревьям поиска;
  2. двоичные деревья поиска в C++

 

Протестировать шаблон класса на следующих типах данных: целые, вещественные, символьные, строки.

Решить задачу

  1. Реализовать операцию пересечения для двух двоичных деревьев поиска, т.е. построить двоичное дерево поиска из элементов, входящих одновременно в первое и второе деревья.
  2. Написать рекурсивную функцию, которая определяет глубину заданного элемента на дереве и возвращает –1, если такого элемента нет.
    Контроль.
    Тест 1. Для данных -1 -2 9 2 -4 22 -3 0 -9 10 4 -5 14 и заданного элемента 0 получаем 2 (корень находится на уровне с номером 0).
    Тест 2. Для данных -1 -2 9 2 -4 22 -3 0 -9 10 4 -5 14 и заданного элемента 1 получаем -1.
  3. Написать функцию, которая находит наибольший элемент дерева.
    Контроль. Тест. Для данных 4 1 9 0 3 2 -3 получаем 9.
  4. Написать функцию, которая находит наименьший элемент дерева.
    Контроль. Тест. Для данных 4 1 9 0 5 2 3 получаем 0.
  5. Напишите программу, которая удаляет из дерева все заданные элементы.
    Контроль. Тест. Для данных 4 1 9 0 5 2 3 получаем 0 2 4.
  6. Написать программу, которая определяет число вхождений заданного элемента в дерево.
    Контроль.
    Тест 1. Для данных -1 2 2 9 2 2 -4 2 -3 -3 0 9 9 2 9 -1 4 и заданного элемента 2 получаем 5.
    Тест 2. Для данных -1 2 2 9 2 2 -4 2 -3 -3 0 9 9 2 9 -1 4 и заданного элемента -2 получаем 0.
  7. Написать программу, которая по заданному n считает число всех вершин глубины n в заданном дереве.
    Контроль.
    Тест 1. Для данных -1 -2 9 2 -4 22 -3 0 -9 10 4 -5 14 и заданного n=2 получаем 3 (корень находится на уровне с номером 0).
    Тест 2. Для данных -1 -2 9 2 -4 22 -3 0 -9 10 4 -5 114 и заданного n=3 получаем 6 (корень находится на уровне с номером 0).
  8. Написать программу, которая печатает элементы из всех листьев дерева.
  9. Написать программу, которая по заданному дереву T строит дерево, состоящее только из листьев дерева T.
  10. Написать программу, которая удаляет повторяющиеся элементы непустого дерева T.
  11. Написать программу, которая удаляет из непустого бинарного дерева T вершины, содержащие максимальный и минимальный элемент.
  12. Написать программу, которая определяет количество вхождений вершины с заданным элементом E в бинарное дерево.
  13. Написать программу, которая находит в заданном непустом бинарном дереве длину (количество ветвей) пути от корня до ближайшей вершины с заданным элементом E.
  14. Написать программу, которая определяет максимальный элемент из всех листьев непустого бинарного дерева.
  15. Составить программу, которая печатает все элементы дерева по уровням: сначала — из корня дерева, затем (слева направо) — из вершин, дочерних по отношению к корню, затем (также слева направо) — из вершин, дочерних по отношению к этим вершинам, и т.д.
  16. Составить программу, которая формирует дерево L, включив в него по одному разу элементы, которые входят в одно из деревьев L1 и L2, но в то же время не входит в другое из них.

 


Рейтинг ресурсов УралWeb

 

© А.П. Шестаков, 2008-2011
Сайт создан в системе uCoz