Практикум по теме. Дополнить программу, составленную по теме «Хеш-таблицы» или «Деревья двоичного поиска» операциями над последовательностями

Дополнить программу, составленную по теме «Хеш-таблицы» или «Деревья двоичного поиска» операциями над последовательностями, указанными в следующей ниже таблице в соответствии с номером индивидуального задания. Выбрать наиболее подходящий способ доработки структуры данных для получения эффективного алгоритма.

3.2. Индивидуальные задания к теме «Последовательности»

3.3. Требования к отчёту

В отчёте по этой теме должно быть обоснование выбора способа дополнения базовой структуры данных для обеспечения возможности выполнения операций с последовательностями. В выводах можно дать заключение, насколько выбор оказался удачным.

Контрольные вопросы

1. Почему для хранения произвольной последовательности структуру данных для множества (хеш-таблицу или ДДП) приходится дорабатывать?

2. Какие доработки возможны?

3. Можно ли предложить оптимальный вариант доработки?

4. Влияет ли доработка структур данных для множеств для поддержки последовательностей на временную сложность операций над множествами?

5. Какую структуру данных проще дорабатывать — хеш-таблицу или ДДП?

6. Какова оптимальная доработка структуры данных и временная сложность для операции исключения части последовательности между указанными позициями?

7. То же — для операции вставки с указанной позиции?

8. То же — для замены?

4. РАБОТА С ИЕРАРХИЕЙ ОБЪЕКТОВ:
НАСЛЕДОВАНИЕ И ИЗОМОРФИЗМ

Производные классы — это простое, гибкое и эффективное средство определения класса. Новые возможности добавляются к уже существующему классу, не требуя его перепрограммирования или перетрансляции. С помощью производных классов можно организовать общий интерфейс с несколькими различными классами так, что в других частях программы можно будет единообразно работать с объектами этих классов. Понятие виртуальной функции позволяет использовать объекты надлежащим образом даже в тех случаях, когда их тип на стадии трансляции неизвестен. Основное назначение производных классов — упростить программисту задачу выражения общности классов.

Любое понятие не существует изолированно, оно существует во взаимосвязи с другими понятиями, и мощность данного понятия во многом определяется наличием таких связей. Раз класс служит для представления понятий, встаёт вопрос, как представить взаимосвязь понятий. Понятие производного класса и поддерживающие его языковые средства служат для представления иерархических связей, иными словами, для выражения общности между классами. Например, понятия окружности и треугольника связаны между собой, так как оба они представляют ещё понятие фигуры, т. е. содержат более общее понятие. Чтобы представлять в программе окружности и треугольники и при этом не упускать из вида, что они являются фигурами, надо явно определять классы окружность и треугольник так, чтобы было видно, что у них есть общий класс — фигура. Эта простая идея по сути является основой того, что обычно называется объектно-ориентированным программированием.

Подробнее см. [6], с. 149–180, [7], с. 200–210.

Рассмотрим учебную программу, использующую некоторые из этих идей, прототип которой взят из работы [6]. Программа предназначена для вывода на экран картинок, составленных из набора заготовок — «фигур».

В программе объявлен абстрактный класс «фигура» (shape). Все конкретные фигуры — линия, прямоугольник и т. п. — являются производными от этого класса. Класс «фигура» поддерживает действия, необходимые для всех фигур: он создаёт из всех объявляемых фигур общий список, который может быть обработан программой рисования при выдаче фигур на экран. Кроме того, в классе «фигура» объявлен набор функций-членов, которые должны поддерживать все фигуры, чтобы из них можно было создавать картинки. Это функции, возвращающие координаты всех крайних точек фигуры, по которым их можно будет стыковать. Эти функции — виртуальные, они должны быть обязательно определены затем отдельно в каждой фигуре. Имеются также два дополнительных класса, уточняющих свойства фигур. Некоторые фигуры можно поворачивать. Для таких фигур имеется базовый класс rotatable, производный от shape. Для других фигур возможна операция отражения относительно горизонтальной или вертикальной оси. Эти фигуры можно строить на базе класса reflectable. Если фигура имеет оба этих свойства, то она должна быть производной от обоих классов.

Класс «фигура» является ядром библиотеки фигур snape.h. Имеется также библиотека поддержки работы с экраном screen.h, в которой определены размеры экрана, введено понятие точки и перечислены утилиты работы с экраном, конкретизированные затем в shape.h. Для простоты и универсальности работа с экраном реализована как формирование и построчный вывод матрицы символов.

Предполагается, что файлы screen.h и shape.h — покупные, а разработчик создаёт только третий файл — с самой прикладной программой.

4.1. Учебная программа «Библиотека фигур»

//Прикладная программа для работы с библиотекой фигур

//Файл screen.h - поддержка работы с экраном

const int XMAX=80; //Размер экрана

const int YMAX=40;

struct point { //Точка на экране

int x, y;

point() { };

point(int a, int b): x(a), y(b){ }

};

// Набор утилит для работы с экраном

extern void put_point(int a, int b); // Вывод точки

inline void put_point(point p) { put_point(p.x, p.y); }

extern void put_line(int, int, int, int); // Вывод линии

extern void put_line(point a, point b)

{ put_line(a.x, a.y, b.x, b.y); }

extern void screen_init(); // Создание экрана

extern void screen_destroy(); // Удаление экрана

extern void screen_refresh(); // Обновление

extern void screen_clear(); // Очистка

//————————————————————————————————

// Файл shape.h -- библиотека фигур

//==1. Поддержка экрана в форме матрицы символов ==

char screen[XMAX] [YMAX];

enum color { black='*', white='.' };

void screen_init()

{

for (int y=0; y< YMAX; y++)

for (int x=0; x< XMAX; x++)

screen[x] [y] = white;

}

inline int on_screen(int a, int b) // проверка попадания

{ return 0 < = a & & a < XMAX & & 0 < = b & & b < YMAX; }

void put_point(int a, int b)

{ if (on_screen(a, b)) screen[a] [b] = black; }

void put_line(int x0, int y0, int x1, int y1)

/*

Рисование отрезка прямой (x0, y0) - (x1, y1).

Уравнение прямой: b(x-x0) + a(y-y0) = 0.

Минимизируется величина abs(eps),

где eps = 2*(b(x-x0)) + a(y-y0).

*/

{

register int dx = 1;

int a = x1 - x0;

if (a < 0) dx = -1, a = -a;

register int dy = 1;

int b = y1 - y0;

if (b < 0) dy = -1, b = -b;

int two_a = 2*a;

int two_b = 2*b;

int xcrit = -b + two_a;

register int eps = 0;

for (;;) {

put_point(x0, y0);

if (x0 == x1 & & y0 == y1) break;

if (eps < = xcrit) x0 += dx, eps += two_b;

if (eps > = a || a < b) y0 += dy, eps -= two_a;

}

}

void screen_clear() { screen_init(); } //Очистка экрана

void screen_refresh() // Обновление экрана

{

for (int y = YMAX-1; 0 < = y; y--) { // с верхней строки до нижней

for (int x = 0; x < XMAX; x++) // от левого столбца до правого

cout < < screen[x] [y];

cout < < '\n';

}

}

//==2. Библиотека фигур ==

struct shape { //Виртуальный базовый класс " фигура"

static shape* list;

shape* next;

shape() { next = list; list = this; }

virtual point north() const = 0;

virtual point south() const = 0;

virtual point east() const = 0;

virtual point west() const = 0;

virtual point neast() const = 0;

virtual point seast() const = 0;

virtual point nwest() const = 0;

virtual point swest() const = 0;

virtual void draw() = 0;

virtual void move(int, int) = 0;

};

shape * shape:: list = 0; //Инициализация списка фигур

class rotatable: public shape { //Фигуры, пригодные к повороту

public:

virtual void rotate_left() = 0; //Повернуть влево

virtual void rotate_right() = 0; //Повернуть вправо

};

class reflectable: public shape { // Фигуры, пригодные

// к зеркальному отражению

public:

virtual void flip_horisontally() = 0; // Отразить горизонтально

virtual void flip_vertically() = 0; // Отразить вертикально

};

class line: public shape {

/* отрезок прямой [" w", " e" ]

north() определяет точку " выше центра отрезка и так далеко

на север, как самая его северная точка"

*/

point w, e;

public:

point north() const { return point((w.x+e.x)/2, e.y< w.y? w.y: e.y); }

point south() const { return point((w.x+e.x)/2, e.y< w.y? e.y: w.y); }

point east() const { return point((w.x+e.x)/2, e.y< w.y? e.y: w.y); }

point west() const { return point((w.x+e.x)/2, e.y< w.y? e.y: w.y); }

point neast() const { return point((w.x+e.x)/2, e.y< w.y? e.y: w.y); }

point seast() const { return point((w.x+e.x)/2, e.y< w.y? e.y: w.y); }

point nwest() const { return point((w.x+e.x)/2, e.y< w.y? e.y: w.y); }

point swest() const { return point((w.x+e.x)/2, e.y< w.y? e.y: w.y); }

void move(int a, int b)

{ w.x += a; w.y += b; e.x += a; e.y += b; }

void draw() { put_line(w, e); }

line(point a, point b) { w = a; e = b; }

line(point a, int l) { w = point(a.x + l - 1, a.y); e = a; }

};

// Прямоугольник

class rectangle: public rotatable {

/* nw ------ n ------ ne

| |

| |

w c e

| |

| |

sw ------ s ------ se

*/

point sw, ne;

public:

point north() const { return point((sw.x + ne.x) / 2, ne.y); }

point south() const { return point((sw.x + ne.x) / 2, sw.y); }

point east() const { return point(sw.x, (sw.y + ne.y) / 2); }

point west() const { return point(ne.x, (sw.y + ne.y) / 2); }

point neast() const { return ne; }

point seast() const { return point(sw.x, ne.y); }

point nwest() const { return point(ne.x, sw.y); }

point swest() const { return sw; }

void rotate_right() // Поворот вправо относительно se

{ int w = ne.x - sw.x, h = ne.y - sw.y;

sw.x = ne.x – h * 2; ne.y = sw.y + w / 2; }

void rotate_left() //Поворот влево относительно sw

{ int w = ne.x - sw.x, h = ne.y - sw.y;

ne.x = sw.x + h * 2; ne.y = sw.y + w / 2; }

void move(int a, int b)

{ sw.x += a; sw.y += b; ne.x += a; ne.y += b; }

void draw();

rectangle(point, point);

};

rectangle:: rectangle(point a, point b)

{

if (a.x < = b.x) {

if (a.y < = b.y) {

sw = a;

ne = b;

}

else {

sw = point(a.x, b.y);

ne = point(b.x, a.y);

}

}

else {

if (a.y < = b.y) {

sw = point(b.x, a.y);

ne = point(a.x, b.y);

}

else {

sw = b;

ne = a;

}

}

}

void rectangle:: draw()

{

point nw(sw.x, ne.y);

point se(ne.x, sw.y);

put_line(nw, ne);

put_line(ne, se);

put_line(se, sw);

put_line(sw, nw);

}

void shape_refresh() // Перерисовка всех фигур

{

screen_clear();

for (shape* p = shape:: list; p; p = p-> next) p-> draw();

screen_refresh();

}

void stack(shape* p, const shape* q) // поместить p над q

{

point n = q-> north();

point s = p-> south();

p-> move(n.x - s.x, n.y - s.y + 1);

}

//========================================================

// Прикладная программа:

// пополнение и использование библиотеки фигур

#include " stdafx.h"

#include < conio.h>

#include < iostream>

using namespace std;

#include " screen.h"

#include " shape.h"

// Дополнительная " сборная" фигура

class myshape: public rectangle {

line* l_eye; // левый глаз

line* r_eye; // правый глаз

line* mouth; // рот

public:

myshape(point, point);

void draw();

void move(int, int);

};

myshape:: myshape(point a, point b): rectangle(a, b)

{

int ll = neast().x - swest().x + 1;

int hh = neast().y - swest().y + 1;

l_eye = new line(point(swest().x + 2, swest().y + hh * 3 / 4), 2);

r_eye = new line(point(swest().x + ll - 4, swest().y + hh * 3 / 4), 2);

mouth = new line(point(swest().x + 2, swest().y + hh / 4), ll - 4);

}

void myshape:: draw()

{

rectangle:: draw();

int a = (swest().x + neast().x) / 2;

int b = (swest().y + neast().y) / 2;

put_point(point(a, b));

}

void myshape:: move(int a, int b)

{

rectangle:: move(a, b);

l_eye-> move(a, b);

r_eye-> move(a, b);

mouth-> move(a, b);

}

int _tmain()

{

screen_init();

//== 1.Объявление набора фигур ==

rotatable* p1 = new rectangle(point(0, 0), point(14, 5));

shape* p2 = new line(point(0, 15), 17);

shape* p3 = new myshape(point(15, 10), point(27, 18));

shape_refresh();

_getch();

//== 2.Ориентация ==

Результат работы программы

shape_refresh();

_getch();

//== 3.Сборка изображения ==

p3-> move(-10, -10);

stack(p2, p3);

stack(p1, p2);

shape_refresh();

_getch();

// screen_destroy();

return 0;

}

При запуске программы на экран сначала выводится объявленная коллекция фигур. Затем демонстрируется результат поворота/отражения некоторых фигур как подготовка к их использованию. Далее фигуры перемещаются и образуют заданную картинку: физиономия в шляпе. Для рисования использованы прямоугольники, линии и точки. Физиономия является пользовательской фигурой.