Более сложные связанные динамические структуры данных
Выполнить задания с использованием подходящих связанных динамических структур данных.
1.Написать программу, которая по заданному алгебраическому выражению (операнды – целые числа; операции – + * / % ++ --) вычисляет результат. Воспользоваться логикой построения обратной польской записи.
2.Написать программу, которая по заданному алгебраическому выражению (операнды – вещественные числа; операции – + * / ) вычисляет результат. Воспользоваться логикой построения обратной польской записи.
3.Написать программу, которая по заданному логическому выражению (операнды – булевские константы; логические операции – && || !) вычисляет результат. Воспользоваться логикой построения обратной польской записи.
4.Написать программу, которая по заданному логическому выражению (операнды – целые числа и булевские константы; операции отношения > < == != >= <=, логические операции – && || !) вычисляет результат. Воспользоваться логикой построения обратной польской записи.
5.Написать программу, которая по заданному выражению : (операнды – целые числа; поразрядные операции – & | ^ ~ >> <<) вычисляет результат. Воспользоваться логикой построения обратной польской записи.
Дана программа на С++.
6.Записать в выходной файл построчно все ключевые слова, встречающиеся в этой программе, указав количество появлений для каждого ключевого слова и номера строк программы, в которых они встречаются.
7.Записать в выходной файл в алфавитном порядке построчно все идентификаторы, встречающиеся в этой программе, указав количество появлений для каждого идентификатора и номера строк программы, в которых они встречаются.
8.Записать в выходной файл построчно все константы, встречающиеся в этой программе, указав количество появлений для каждой константы и номера строк программы, в которых они встречаются.
9.Записать в выходной файл построчно все циклические конструкции, встречающиеся в этой программе с указанием номеров строк начала и конца каждого цикла и его типа.
10.Записать в выходной файл построчно все операторы ветвления, встречающиеся в этой программе с указанием номеров строк начала и конца каждого оператора ветвления.
Классы
8.1. Класс «Многоразрядное число»
Объявить класс для решения задачи и определить его методы.
Реализовать:
· три вида конструктора (без аргументов, инициализации, копирования),
· деструктор,
· ввод данных с клавиатуры,
· вывод данных на экран,
· указанные в задании операции реализовать посредством перегрузки операций (операции реализовать и как методы класса, и как внешние дружественные функции).
Объявление класса разместить в заголовочном файле, определения методов – во втором файле, определение главной функций программы – в третьем файле. Выполнить задание, используя объекты этого класса.
Дополнительно к требуемым в заданиях операциям перегрузить операцию индексирования []. Максимально возможный размер массива задать константой. Если количество элементов массива изменяется во время работы, определить в классе поле count. Обеспечить работу с безопасным массивом, т.е. контролировать выход индекса элемента массива за допустимый описанием объекта диапазон.
1.Объявить класс «32-разрядное целое положительное десятичное число». Реализовать операции: сложения, умножения этих чисел.
2.Объявить класс «32-разрядное целое положительное десятичное число. Реализовать операции: сравнения, сдвигов на n разрядов (десятичных).
3.Объявить класс «56-разрядное целое положительное десятичное число. Реализовать операции: сложения, умножения этих чисел.
4.Объявить класс «56-разрядное целое положительное десятичное число». Реализовать операции: сравнения, сдвигов на n разрядов (десятичных).
5.Объявить класс «32-разрядное целое двоичное число со знаком». Реализовать операции: сложения, умножения. Создать метод для перевода десятичного числа в «32-разрядное целое двоичное число со знаком».
6.Объявить класс «32-разрядное целое положительное двоичное число». Реализовать операции: сравнения, сдвигов на n разрядов. Создать метод для перевода десятичного числа в «32-разрядное целое положительное двоичное число».
7.Объявить класс «64-разрядное целое двоичное число со знаком». Реализовать операции: сложения, умножения. Создать метод для перевода десятичного числа в «64-разрядное целое двоичное число со знаком».
8.Объявить класс «64-разрядное целое положительное двоичное число». Реализовать операции: сравнения, сдвигов на n разрядов. Создать метод для перевода десятичного числа в «64-разрядное целое положительное двоичное число».
9.Объявить класс «16-разрядное целое шестнадцатиричное положительное число». Реализовать операции: сложения, умножения. Создать метод для перевода десятичного числа в «16-разрядное целое шестнадцатиричное положительное число».
10.Объявить класс «32-разрядное целое шестнадцатиричное положительное число». Объявить класс «128-разрядное целое положительное двоичное число». Реализовать операцию сложения для тех и других чисел. Создать методы для перевода «128-разрядное целое положительное двоичное число» в «32-разрядное целое шестнадцатиричное положительное число» и наоборот.
11.Объявить класс «16-разрядное целое положительное число в p-ричной с/с (2≤p≤16)». Реализовать операции: сложения, умножения. Создать метод для перевода десятичного числа в р-ричное.
12.Объявить класс «16-разрядное целое положительное число в p-ричной с/с (2≤p≤16)». Реализовать операции: сравнения, сдвигов на n разрядов. Создать методы для перевода десятичного числа в р-ричное.
8.2. Перегрузка операций
Объявить класс для решения задачи и определить его методы.
Реализовать:
· три вида конструктора (без аргументов, инициализации, копирования),
· деструктор,
· ввод данных с клавиатуры,
· вывод данных на экран,
· указанные в задании операции реализовать посредством перегрузки операций (операции реализовать и как методы класса, и как внешние дружественные функции).
Объявление класса разместить в заголовочном файле, определения методов – во втором файле, определение главной функций программы – в третьем файле. Выполнить задание, используя объекты этого класса.
1.Определить класс для работы с объектом «комплексное число», которое задается вещественной и мнимой частями. Реализовать: сложение, вычитание, произведение, деление двух чисел, возведение в целочисленную степень, извлечение квадратного корня.
2.Определить класс для работы с объектом «рациональная дробь» (вида m/n). Реализовать: сложение, вычитание, умножение, деление двух дробей, приведение дроби к несократимому виду, вывод дроби в виде m/n, сравнение двух дробей.
3.Определить класс для работы с объектом «полином». Ввод осуществить по возрастанию степеней членов полинома. Реализовать: сложение, вычитание, умножение, деление двух полиномов, умножение полинома на число, вычисление значения полинома в заданной точке, интегрирование полинома.
4.Определить класс для работы с объектом «строка символов». Реализовать: вставку в строку указанного символа в заданную позицию, удаление ведущих пробелов. Добавить в заданную строку отсутствующие символы из второй заданной строки, на позиции с такими же номерами.
5.Определить класс для работы с объектом «множество целых чисел». Реализовать: объединение двух множеств, пересечение двух множеств, разность двух множеств, добавление элемента во множество, удаление элемента из множества.
6.Определить класс для работы с объектом «строка символов». Реализовать: сравнение строк, удаление из строки указанного символа. Удалить из заданной строки все символы, встречающиеся во второй заданной строке.
7.Определить класс для работы с объектом «комплексное число», которое задается своим модулем и углом. Реализовать: сложение, вычитание, произведение, деление двух чисел, возведение в целочисленную степень, извлечение квадратного корня.
8.Определить класс для работы с объектом «время», которое задается в формате час.минута.секунда. Реализовать (учесть переход через 24 ч.): добавления ко времени заданного количества секунд, вычитания из времени заданного количества секунд, сложения двух моментов времени, вычитание из одного момента времени другого, подсчет числа секунд между двумя моментами времени, лежащими в пределах одних суток.
9.Определить класс для работы с объектом «строка символов». Реализовать: замену подстроки на подстроку, конкатенацию строк. Заменить в заданной строке заданную подстроку на другую заданную подстроку (столько раз, сколько она встречается в тексте).
10.Определить класс для работы с объектом «множество действительных чисел». Реализовать: объединение двух множеств, пересечение двух множеств, разность двух множеств, добавление элемента во множество, удаление элемента из множества.
11.Определить класс для работы с объектом «дата», которое задается в формате число.месяц.год. Реализовать (учесть високосные года): сложение даты с заданным количеством дней, вычитания из даты заданного количества дней, вычисление числа дней, прошедших между двумя датами.
12.Определить класс для работы с объектом «строка символов». Реализовать: удаление подстроки из строки, проверку, является ли строка палиндромом. Удалить из заданной строки заданную подстроку (столько раз, сколько она встречается в тексте).
8.3 Класс «Матрица»
Объявить класс «Матрица» и определить его методы.
Обеспечить представление матрицы произвольного размера с возможностью изменения числа строк и столбцов.
Обеспечить в конструкторе автоматическое генерирование имени матрицы («матрица 1», «матрица 2» и т.д.), используя для этого статическое поле – счетчик объектов класса.
Реализовать в классе метод вывода матрицы на экран с одновременным выводом ее имени. Алгоритм обработки, реализующий условие задачи, определить как функцию-член класса или как дружественную функцию класса.
Класс может реализовывать следующие операции над матрицами (в зависимости от условия задания):
· сложение, вычитание, умножение, деление ) на число
· сложение, вычитание, умножение на другую матрицу
· комбинированные операции присваивания (+=, -=, *=, /=);
· операции сравнения на равенство/неравенство;
· операции вычисления транспонированной матрицы;
· операцию возведения в степень;
· методы, реализующие проверку типа матрицы (квадратная, диагональная, нулевая, единичная, симметричная, верхняя треугольная, нижняя треугольная);
· методы доступа к элементам матрицы с контролем выхода за пределы размерностей;
· методы, обеспечивающие: замену значений элементов i-й строки матрицы значениями элементов вектора;
· операции ввода/вывода в стандартные потоки подматрицы любого размера и всей матрицы.
Алгоритм обработки, реализующий условие задачи, определить как функцию-член класса или как дружественную функцию класса.
В основной программе определить массив указателей (проинициализировав его адресами объявленных матриц-объектов, требуемых по условию задания) и функцию, которой передаются данный массив и количество матриц (для вывода на экран перечня всех матриц с их значениями).
Используя объекты описанного класса «Матрица», реализовать алгоритм своего варианта задания 7.1.2.
8.4 Класс «Линейный список»
Объявить шаблон класса «Линейный список». Определить структуру класса и его методы. В классе должен быть конструктор по умолчанию, конструктор с формальными параметрами, конструктор копирования и деструктор.
Определить методы:
· инициализация первого элемента структуры;
· добавления в структуру нового элемента;
· удаление элемента;
· поиск элемента по заданному ключу поиска (значению информационного поля);
· вывод элементов списка на экран;
· удаления списка.
Используя объекты класса «Линейный список», реализовать алгоритмы своих вариантов заданий 7.3.
Класс «Двусвязный список»
Объявить шаблон класса «Двусвязный линейный список». Определить структуру класса и его методы. В классе должен быть конструктор по умолчанию, конструктор с формальными параметрами, конструктор копирования и деструктор.
Определить методы:
· инициализация первого элемента структуры;
· запись в структуру нового элемента;
· удаление элемента;
· поиск элемента по заданному ключу поиска (значению информационного поля);
· вывод структуры на экран;
· удаления структуры..
Используя объекты класса «Двусвязный линейный список», реализовать алгоритм своего варианта задания 7.4.
.
8.6. Класс «Бинарное дерево»
Объявить шаблон класса «Бинарное дерево». Определить структуру класса и его методы. В классе должен быть конструктор по умолчанию, конструктор с формальными параметрами, конструктор копирования и деструктор.
Определить методы:
· инициализация первого элемента структуры;
· запись в структуру нового элемента;
· удаление элемента (листа);
· поиск элемента по заданному ключу поиска (значению информационного поля);
· вывод структуры на экран;
· удаления структуры.
Используя объекты класса «Бинарное дерево», реализовать алгоритм своего варианта задания 7.5.
8.7. Класс «Граф»
Объявить шаблон класса «Граф». Определить структуру класса и его методы. В классе должен быть конструктор по умолчанию, конструктор с формальными параметрами, конструктор копирования и деструктор.
Определить методы:
· инициализация первого элемента структуры;
· запись в структуру нового элемента;
· удаление элемента;
· вывод структуры на экран;
· удаления структуры.
.
Используя объекты класса «Граф», реализовать алгоритм своего варианта задания 7.6.
8.8. Библиотека шаблонов STL. Векторы
8.7.1. Реализовать задание из 7.1.1, используя объявление и методы соответствующего параметризированного класса из стандартной библиотеки шаблонов STL.
8.7.2. Реализовать задание 7.1.2, используя объявление и методы соответствующего параметризированного класса из стандартной библиотеки шаблонов STL.
8.9. Библиотека шаблонов STL . Списки
8.8.1. Реализовать варианты заданий 7.2, используя объявление и методы соответствующего параметризированного класса из стандартной библиотеки шаблонов STL.
8.8.2. Реализовать вариант заданий 7.3, используя объявление и методы соответствующего параметризированного класса из стандартной библиотеки шаблонов STL.
8.10. Библиотека шаблонов STL . Ассоциативные Списки
Реализовать варианты заданий 4.4, используя объявление и методы соответствующего параметризированного класса из стандартной библиотеки шаблонов STL.
9. Наследование. Полиморфизм
9.1. Наследование
Для каждого класса описать поля, характеризующие объект, и методы, позволяющие заполнять и получать значения каждого из полей. выводить значения полей на экран, а также необходимые конструкторы. Конструкторы и методы должны проверять параметры на допустимость.
Определить и описать иерархию классов в следующих заданиях.
Реализовать функцию, получающую и возвращающую объекты базового типа.
1.студент, преподаватель, персона, лаборант;
2.журнал, газета, книга, печатное издание, учебник;
3.подразделение университета, аудитория, библиотека, учебная лаборатория, вычислительный центр;
4.тест, экзамен, зачет, испытание;
5.устройства вывода, выводящие звук, выводящие изображение, колонки, монитор, наушники.
6.компьютер, персональный компьютер, сеть компьютеров, мэйнфрейм (большой универсальный компьютер), сервер;
7.университет, лицей, школа, колледж, учебное заведение, институт, академия;
8.математика, физика, программирование, линейная алгебра, математический анализ, теоретическая механика, предмет;
9.подразделение университета, факультет, кафедра, библиотека, деканат;
10.накопители данных, внешние НД, жесткий диск, CD, карта памяти.
11.Pascal, С, С++, ассемблер, язык программирования;
12.список, односвязный список, многосвязный список, стек, очередь, бинарное дерево, граф.
9.2. Полиморфизм. Виртуальные методы
Cоздать класс «одномерный динамический массив из потомков-объектов, описанных в 9.1». Реализовать следующие методы:
· создание массива;
· занесение элемента в массив;
· удаление элемента из массива;
· вывод на экран элементов массива с соответствующими полями для каждого объекта;
· удаление массива.
Определить: конструктор, деструктор, виртуальные методы. Выполнить тестирование написанных методов.
9.3. Полиморфизм. Виртуальные методы
Воспользоваться шаблоном задания 8.4, создать класс «односвязный список из потомков-объектов, описанных в 9.1». Для данного списка реализовать следующие методы:
· инициализация списка;
· добавление объекта в список;
· удаление объекта из списка;
· просмотр элементов списка и вывод на экран элементов списка с соответствующими полями для каждого объекта;
· удаление списка.
Определить: конструктор, деструктор, виртуальные методы. Выполнить тестирование написанных методов.