Деревья

Пусть задано двоичное дерево a

Используя очередь или стек описать функцию, / \

которая: b c

1) присваивает параметру Е элемент / \ \

из самого левого листа непустого дерева Т d e f

(лист - вершина, из которой не выходит ни /

одной ветви); g

2) определяет число вхождений элемента Е в дерево Т.

3) вычисляет среднее арифметическое значение всех элементов не­пустого дерева Т;

4) заменяет в дереве Т все отрицательные элементы на их абсолют­ные величины;

5) меняет местами максимальный и минимальный элементы непустого дерева Т, все элементы которого различны;

6) печатает элементы из всех листьев дерева Т;

7) находит в непустом дереве Т длину (число ветвей) пути от корня до ближайшей вершины с элементом Е; если Е не входит в Т, за ответ принять -1;

8) подсчитывает число вершин на n-ом уровне непустого дерева Т (корень считать вершиной 0-го уровня);

9) определяет максимальную глубину непустого дерева Т, т.е. число ветвей в самом длинном из путей от корня до листьев;

10) вычисляет сумму элементов непустого дерева Т вещ. чисел;

11) строит Т1 - копию дерева Т;

12) строит Т - бинарное "сбалансированное" дерево с n уровнями (n

- целое положительное число);

13) добавляет к дереву поиска Т новый элемент Е, если его не было в Т;

14) по файлу f, все элементы которого различны, строит соответс­твующее дерево поиска Т; подсчитать число уровней;

15) записывает в файл f элементы дерева поиска Т в порядке их возрастания;

16. Написать логическую функцию, проверяющую на равенство деревья Т1 и Т2.

17. Создать два бинарных дерева целых чисел, затем поэлементно их сложить.

18. Отсортируйте бинарное дерево целых чисел так чтобы левый по­томок числа n был меньше его правого потока.

19. Из бинарного дерева вещественных чисел создать два, где ко­рень первого - левый потомок корня, а корень второго - правый потомок.

20. Написать программу для задачи 18 при условии, что максималь­ная длина идентификаторов заранее не известна.

21. Создать бинарное дерево целых чисел и подсчитать число вхож­дений элемента к.

22. Создать бинарное дерево вещественных чисел и вывести значения всех узлов дерева.

24. Написать программу для задачи 17 при условии, что максималь­ная длина идентификаторов заранее не известна.

25. Во внешнем текстовом файле записана некоторая программа на языке Паскаль (Си). Известно, что в этой программе каждый идентифика­тор содержит не более 9 латинских букв и/или цифр. Напечатать в алфа­витном порядке все различные идентификаторы этой программы, указав для каждого из них число его вхождений в текст программы. (Учесть, что внутри литерных) значений, строк-констант и комментариев последова­тельности из букв и цифр не являются идентификаторами и что в записи вещественных чисел может встретиться буква Е или е.)

Для хранения идентификатором использовать дерево поиска, элемен­тами которого являются пары - идентификатор и число его вхождений в текст программы.

26. Решить предыдущую задачу, но вместе с каждым идентификатором печатать в возрастающем порядке номера всех строк текста программы, в которых он встречается.

27. Создать бинарное дерево целых чисел и вывести его в файл. Формат ввода: в каждой строке файла - одно число, перед которым могут стоять символы табуляции. Пусть в какой-то строке стоит число n в по­зиции k. Тогда потомки числа n стоят в последующих строках в позиции (k+1).

Лабораторная работа 7

ПОЛИМОРФИЗМ. ПЕРЕГРУЗКА ОПЕРАЦИЙ И ФУНКЦИЙ В С++

Одним из базовых принципов ООП стиля программирования является полимор­физм. Это свойство, которое позволяет одно и то же имя использовать для ре­шения двух или более задач, но технически разных. Целью полиморфизма, при­менительно к ООП, является использование одного имени для задания общих для класса действий. Выполнение каждого конкретного действия будет опреде­ляться типом данных.

В С++ операции (из списка уже существующих) могут быть определены и для объектов, введенных пользователем . Это очень удобно, потому что, например, описав класс"вектор в трехмерном пространстве" , не нужно придумывать имя функции для выполнения операции сложения над векторами, а можно переопре­делить смысл имеющийся операции + таким образом, что сложение двух векторов будет записываться в привычной форме : А + В.

Важным новшеством в С++ является то, что транслятор различает функции не только по именам ,но и по типам аргументов(см. выше).Поэтому вполне допус­тимым является наличие, например, двух таких функций :

int sqr (int x)

return (x*x)

float sqr (float x)

return (x*x)

Код какой конкретно функции будет использован при вызове зависит от типа фактического аргумента. Перегруженные функции хорошо использовать при вве­дении новых данных. Описав тип COMPLEX для работы с комплексными числами, можно составить функцию pow() для возведения в степень комплексного числа, а назвать ее так же, как и функцию, работающую с вещественными числами.

Вот формат перегрузки операторов :

[<класс>] operator <оператор>( <параметры> )

<выражения>;

return(<выражения>);

Пример решения задачи :

Переопределим некоторые операции ("+","-","^","%","*") для нахождения суммы, разности, скалярного произведения, векторного произведения двух задан­ных векторов, а также произведение каждого из них на скаляр. */

#define g goto

#define o odin

#define d dva

#define t tri

#include <stdlib.h>

#include <string.h>

#include <stdio.h>

#include <conio.h>

struct St //структура вектор

int s[4];;

St operator + (St a,St b) //перегрузка операции +

static St sum;int i;

for (i=1;i<=3;i++)sum.s[i]=a.s[i]+b.s[i];

return sum;

St operator - (St a,St b) //перегрузка операции -

static St sum;int i;

for (i=1;i<=3;i++)sum.s[i]=a.s[i]-b.s[i];

return sum;

int operator ^ (St a,St b) //перегрузка операции ^

int i,sum=0;

for (i=1;i<=3;i++)sum+=a.s[i]*b.s[i];

return sum;

St operator % (St a,St b) //перегрузка операции %

static St sum;int i;

sum.s[1]=a.s[2]*b.s[3]-a.s[3]*b.s[2];

sum.s[2]=-(a.s[1]*b.s[3]-a.s[3]*b.s[1]);

sum.s[3]=a.s[1]*b.s[2]-a.s[2]*b.s[1];

return sum;

St operator * (St a,int b) //перегрузка операции *

static St sum;int i;

for (i=1;i<=3;i++)sum.s[i]=a.s[i]*b;

return sum;

void main() //основная программа

static St a,b,c;int j,res,con;char vibor;

clrscr();

randomize();

printf("ВВЕДИТЕ КООРДИНАТЫ ВЕКТОРА a ");

scanf("%d %d %d",&a.s[1],&a.s[2],&a.s[3]);

printf("ВВЕДИТЕ КООРДИНАТЫ ВЕКТОРА b ");

scanf("%d %d %d",&b.s[1],&b.s[2],&b.s[3]);

ddd:printf("a=(%d,%d,%d)\n",a.s[1],a.s[2],a.s[3]);

printf("b=(%d,%d,%d)\n",b.s[1],b.s[2],b.s[3]);

printf("ОПЕРАЦИЯ");

printf("=>1: a+b; 2: a-b; 3:(a,b); 4:[axb]; 5:const*a; 6:const*b; 0:EXIT\n");

vibor=getch();

switch (vibor) case '1' : c=a+b;g o;

case '2' : c=a-b;g o;

case '3' : res=a^b;g d;

case '4' : c=a%b;g o;

case '5' : printf("ВВЕДИТЕ сonst ");scanf("%d",&con);

c=a*con;g o;

case '6' : printf("ВВЕДИТЕ сonst ");scanf("%d",&con);

c=b*con;g o;

case '0' : g t;

odin:printf("результат с=(%d,%d,%d) \n",c.s[1],c.s[2],c.s[3]);g ddd;

dva:printf("результат %d\n",res);

g ddd;

tri:

/*

АРГУМЕНТЫ ПО УМОЛЧАНИЮ.

При объявлении функции в языке С++ для нее можно задать аргументы по умолчанию. Например, объявление

void fun(int,int=5);

позволяет вызвать функцию fun двумя способами, например fun(10) и fun(10,20). Когда у функции задан только один аргумент, второй аргумент получит значение, заданное по умолчанию. Поэтому вызов fun(10) назначит первому аргументу значе­ние 10, а второму - 5. Второй вызов fun(10,20) назначит аргументам значения 10 и 20.

Рассмотрим пример 1: */

#include <iostream.h>

void fun(int,char='%',float=1.25); // Объявление функции

void fun(int=1,char,float); // Переобъявление функции

void fun(char *); // Объявление функции

void main()

int ii=10; char cc='*'; float ff=22.33;

fun(ii); // Результат 10 % 1.25

fun(ii,cc); // Результат 10 * 1.25

fun(ii,cc,ff); // Результат 10 * 22.33

fun("HELLO\n"); // Результат HELLO

fun(); // Результат 1 % 1.25

void fun (int i,char c,float f) // Описание функции

cout<<i<<'\t'<<c<<'\t'<<f<<'\t'<<endl;

void fun (char *s)

cout<<s;

/*Два следующих друг за другом объявления :

void fun(int,char='%',float=1.25);

void fun(int=1,char,float);

являются правильными. Второе из них добавляет в первую функцию значение перво­го аргумента, заданного по умолчанию. Для обоих объявлений достаточно одного описания. Новую функцию fun, заданную в виде void fun(char *), можно отличить по числу аргументов, поэтому здесь не возникает неоднозначности.

Еще очень важно знать, если функция имеет аргумент, заданный по умолчанию, то после него могут идти только аргументы, тоже заданные по умолчанию. Пример :

int f1(int a,char b='#',float f); // Ошибка

int f2(int a,char b='#',float f=5.28); // Нет ошибки

Рассмотрим пример 2: */

#include <iostream.h>

class my_class

int x,y,z;

public :

my_class() x=y=0;

float add_mul(int a=0,int b=0,int c=0,char ch='+');

void display() cout<<x<<'\t'<<y<<endl;

;

float my_class::add_mul(int a,int b,int c,char ch)

if (ch=='+') return x=a+b+c;

if (ch=='*') return y=a*b*c;

cout<<"ERROR \n"; return NULL;

void main(void)

my_class A;

cout<<A.add_mul(5,10)<<endl; // Результат 15

cout<<A.add_mul(2,5,10)<<endl; // Результат 17

cout<<A.add_mul(2,5,10,'*')<<endl; // Результат 100

A.display(); // Результат 17 100

В задании на программирование требуется реализовать классы и операции (функции) для работы с объектами этих классов. Записать полученную программу

в файл:имя4_N.

Задания к лабораторной работе:

1. Для строки символов реализовать операции:

а) сравнение строк (операция ==);

б) удаление из строки заданного символа (операция -).

Кроме того, членом класса сделать функцию с именем strset() для удаления из первой строки всех символов, встречающихся во второй строке.

2. Для строки символов реализовать операции:

а) проверка в строке наличия заданного символа (операция !);

б) перевод указанного символа строки в код ASCII(операция %).

Членом класса сделать функцию с именем strlen() для нахождения суммы кодов ASCII всех символов данной строки.

3. В британском формате дата задается как число/месяц/дата. Реализовать с учетом високосных годов:

а) сложение даты и заданного количества дней (операция +);

б) вычитание из даты заданного количества дней (операция -).

Кроме того, членом класса сделать функцию с именем printf() для вывода конечной даты.

4. В британском формате дата задается как число/месяц/дата. Реализовать с учетом високосных годов:

а) определение числа дней, прошедших между двумя датами (операция %);

б) нахождение порядкового номера даты в заданном году (опера­ция /).

Членом класса сделать функцию с именем printf() для вывода конечной даты.

5. Ввести класс для работы с прямоугольной матрицей. Реализовать операции:

а) сложение двух матриц (операция +);

б) умножение двух матриц (операция *).

Членом класса сделать функцию printf() для вывода конечной матрицы и ее модуля.

6. Ввести класс для работы с прямоугольной матрицей. Реализовать операции:

а) проверка наличия заданного числа в заданной матрице (операция !);

б) вычитание двух матриц (операция -).

Членом класса сделать функцию с именем printf() для вывода конечной матрицы и ее модуля.

7. Время задается в формате час/минута/секунда. Реализовать следующие опера­ции(учесть переход через 24 часа):

а) сложение времени и заданного количества секунд (операция +);

б) вычитание из времени заданного количества секунд (операция -).

Членом класса сделать функцию с именем printf() для вывода конечного времени.

8. Время задается в формате час/минута/секунда. Реализовать следующие операции (учесть переход через 24 часа):

а) вычитание из одного момента времени другого (операция -);

б) подсчет числа секунд между двумя моментами времени в пределах одних суток (операция %).

Членом класса сделать функцию printf() для вывода конечного времени.

9. Время задается в формате час/минута/секунда. Реализовать следующие опера­ции (учесть переход через 24 часа):

а) сложение двух моментов времени(операция +);

б) определение времени дня по заданному количеству пройденных секунд(опера­ция /).

Членом класса сделать функцию printf() для вывода конечного времени.

10. Ввести класс для работы с объектом " полином ". Реализовать операции:

а) сложение двух полиномов(операция +);

б) умножение двух полиномов(операция *).

Членом класса сделать функцию printf() для вывода конечного полинома.

11. Ввести класс для работы с объектом " полином ". Реализовать операции:

а) вычитание двух полиномов (операция -);

б) деление двух полиномов (операция /).

Членом класса сделать функцию printf() для вывода конечного полинома.

12. Ввести класс для работы с объектом " полином ". Реализовать операции:

а) умножение полинома на число (операция &);

б) вычисление значения полинома в заданной точке Х (операция |).

Членом класса сделать функцию printf() для вывода конечного полинома.

13. Ввести класс для работы с объектом "множество целых чисел". Реализовать следующие операции:

а) объединение двух множеств (операция +);

б) пересечение двух множеств (операция &).

Членом класса сделать функцию printf() для вывода конечного множества.

14. Ввести класс для работы с объектом "множество целых чисел". Реализовать следующие операции:

а) разность двух множеств (операция -);

б) добавление элемента во множество (операция +).

Членом класса сделать функцию printf() для вывода конечного множества.

15. Ввести класс для работы с объектом "множество целых чисел". Реализовать следующие операции:

а) удаление элемента из множества(операция -);

б) проверка наличия заданного элемента в заданном множестве(операция /). Членом класса сделать функцию printf() для вывода конечного множества.

16. Ввести класс работы с объектом "рациональная дробь" вида m/n. Реализовать:

а) сложение дробей (операция +);

б) умножение двух дробей(операция *).

Членом класса сделать функцию printf() для вывода конечной дроби в виде m/n.

17. Ввести класс работы с объектом "рациональная дробь" вида m/n. Реализовать:

а) вычитание дробей(операция -);

б) деление двух дробей(операция /).

Членом класса сделать функцию с именем abs() для приведениея дроби к несократимому виду.

18. Ввести класс работы с объектом "рациональная дробь" вида m/n. Реализовать:

а) сравнение двух дробей(операция ||);

б) возведение в целую положительную степень(операция ^);

Членом класса сделать функцию с именем printf() для вывода конечной дроби в несократимом виде m/n.

19. Комплексное число задается своей вещественной и мнимой частями (например, 5+3i задается парой 5,3). Реализовать:

а) сложение чисел (операция +);

б) произведение двух чисел (операция *).

Членом класса сделать функцию printf() для вывода конечного числа в виде U+iV.

20. Комплексное число задается своей вещественной и мнимой частями(например,

5+3i задается парой 5,3). Реализовать:

а) вычитание чисел (операция -).

б) возведение числа в целую положительную степень (операция ^).

Членом класса сделать функцию printf() для вывода конечного числа в виде U+iV.

Лабораторная работа 8

Программирование на Вuilder C++

См. Отделную папку