Более сложные связанные динамические структуры данных

Выполнить задания с использованием подходящих связанных динамических структур данных.

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». Для данного списка реализовать следующие методы:

· инициализация списка;

· добавление объекта в список;

· удаление объекта из списка;

· просмотр элементов списка и вывод на экран элементов списка с соответствующими полями для каждого объекта;

· удаление списка.

Определить: конструктор, деструктор, виртуальные методы. Выполнить тестирование написанных методов.