Темы заданий аналогичны заданиям из раздела 3.9.2.
Объявите заданную динамическую структуру данных как класс и разработайте методы класса для обработки значений данных. «Главная» программа (main) осуществляет тестирование разработанных программных средств.
1) Для хранения целых чисел используется следующая структура данных:
Класс
Данные:
· Массив указателей
Методы:
· добавить значение (в зависимости от первой цифры число попадает в конец одного из списков)
· вывести текущее состояние структуры данных (вывести все значения в виде двумерного массива)
· найти значение в структуре данных (функция возвращает 1, если значение найдено, и 0 – в противном случае)
2) Множество целых чисел представляется как однонаправленный линейный список.
Класс
Данные:
· Указатель на начало списка (список – множество)
Методы:
· найти значение в множестве (функция возвращает 1, если значение найдено, и 0 – в противном случае)
· добавить значение в множество (если значение уже есть в множестве, то оно в множество не добавляется. Для проверки используйте функцию «найти значение в множестве»)
· вывести текущее состояние множества (вывести все значения)
· определить мощность множества (подсчитать количество чисел в множестве)
3) Многочлен представляется как однонаправленный линейный список, элемент которого имеет следующую структуру:
Например, многочлену будет соответствоватьсписок:
Класс
Данные:
· Указатель на начало списка (список – элементы многочлена)
Методы:
· добавить элемент многочлена в список
· сформировать многочлен (используется функция «добавить элемент многочлена в список»)
· вывести многочлен (вывести общий вид многочлена; для возведения в степень использовать символ «^», например, х^3)
· вычислить многочлен (функция возвращает значение многочлена при заданном х)
4) «Длинное» целое число представляется как однонаправленный линейный список, где каждая цифра – элемент списка.
Класс
Данные:
· Указатель на начало списка (список – целое число)
Методы:
· сформировать «длинное» целое число (функция формирует список из цифр числа)
· вывести список (функция выводит «длинное» целое число)
· сложить два «длинных» целых числа (функция получает на вход два списка и возвращает третий список, каждый элемент которого содержит цифру, равную сумме, соответствующих цифр исходных списков. Фактически, результат функции – сумма двух чисел)
5) Циклический однонаправленный список целых чисел имеет следующуюструктуру:
Класс
Данные:
· Указатель на начало списка
Методы:
· добавить в список (функция добавляет элемент в конец списка)
· вывести список (функция выводит все значения, которые хранятся в списке)
· выбрать элемент из списка по номеру (функция удаляет элемент, отсчитывая его в соответствии с заданным номером от начала списка. Номер может быть больше количества элементов списка)
6) Динамический массив из N комплексных чисел.
Класс
Данные:
· Массив комплексных чисел
Методы:
· сформировать массив
· вывести массив (функция выводит все комплексные числа)
· определить комплексное число как сумму всех комплексных чисел массива
· найти комплексное число с максимальным модулем (модуль: , где re – действительная часть, im – мнимая часть комплексного числа)
7) Стек как динамический массив из N целых чисел.
Класс
Данные:
· Массив целых чисел
· Значение номера «верхушки» стека
Методы:
· поместить значение в стек;
· извлечь значение из стека (функция возвращает значение из вершины стека и удаляет его из стека)
· стек заполнен (функция возвращает значение «истина», если стек заполнен)
· стек пуст (функция возвращает значение «истина», если в стеке нет значений)
· вывести стек (не изменяя содержимое стека функция, выводит все значения, которые хранятся в стеке)
8) Стек как однонаправленный линейный список целых чисел.
Класс
Данные:
· Указатель на начало списка (список – стек)
Методы:
· поместить значение в стек (функция добавляет значение в начало списка);
· извлечь значение из стека (функция возвращает значение из начала списка и удаляет его из списка)
· стек пуст (функция возвращает значение «истина», если в списке нет значений)
· вывести стек (не изменяя содержимого списка, функция выводит все значения, которые хранятся в списке)
9) Очередь как однонаправленный линейный список целых чисел. Задана максимальная длина очереди – N.
Класс
Данные:
· Указатель на начало списка (список – очередь)
· Текущая длина очереди
· Максимальная длина очереди
Методы:
Функции:
· поместить значение в очередь (функция добавляет значение в конец списка);
· выбрать значение из очереди (функция возвращает значение из начала списка и удаляет его из списка)
· длина очереди (функция возвращает количество элементов в списке)
· очередь заполнена (функция возвращает значение «истина», если количество элементов списка равно N)
· вывести очередь (не изменяя содержимого списка, функция выводит все значения, которые хранятся в списке)
10) Двунаправленный линейный список целых чисел. Каждый элемент списка имеет указатель на следующий элемент списка и указатель на предыдущий элемент.
Класс
Данные:
· Указатель на начало списка (список – стек)
Методы:
· поместить значение в список (функция добавляет значение в конец списка);
· удалить значение из списка (функция удаляет значение из конца списка)
· вставить значение в список после элемента с порядковым номером M (функция добавляет новый элемент в список после элемента с указанным номером. Если в списке меньше элементов, чем M, функция выводит предупредительное сообщение и не изменяет структуру списка)
· вывести список в прямом порядке (не изменяя содержимого списка, функция выводит все значения, которые хранятся в списке, от начала до конца списка)
· вывести список в обратном порядке (не изменяя содержимого списка, функция выводит все значения, которые хранятся в списке, от конца списка к началу)
ЛИТЕРАТУРА
1. Павловская Т.А. С/C++.Программирование на языке высокого уровня. – СПб.: Питер, 2006.
2. Давыдов В.Г. Технология программирования. С++ - СПб.: БХВ-Петербург, 2005.
3. Дейтел Х., Дейтел П. Как программировать на С++. – М.:ЗАО «Издательство БИНОМ», 2001.
4. Керниган Б., Пайк Р. Практика программирования – СПб.: Невский диалект, 2001.
5. Пол А. Объектно-ориентированное программирование на С++. – СПб.: Невский диалект, 1999
6. Джамса К. Учимся программировать на языке С++. – М.: Мир, 1999.