Алгоритмы и анализ сложности. Введение в структуры и классы С++

1.

Алгоритмы и анализ
сложности
Введение в структуры и классы
С++
1

2.

Структуры С
Описание составного типа для отрезка линии:
struct Segm
{
double x1, y1, x2, y2;
char type;
int color;
};
Описание переменных, выделение памяти:
Segm а, b, *pa, arr[100]; pa = new Segm;
Доступ к полям структуры, присваивание:
a.x1 = 0; a.y1 = 20;
pa->color = 10; pa->type = ’s’;
arr[1] = a; arr[2].x2 = arr[2].y2 = 1;
b = arr[5]; arr[4] = *pa;
2

3.

Пример структуры
struct SLine
{
double x[100], y[100];
char type;
int color;
};
SLine а, b, *pa, lin[20]; pa = new SLine;
for (i = 0; i < 100; i++)
a.x[i] = a.y[i] = 0;
pa->color = 10; pa->type = ’s’;
lin[1] = a;
lin[2].x[0] = lin[2].y[0] = 1.0;
b = lin[5]; lin[4] = *pa;
3

4.

Пример структуры
struct DLine
{
double *x, *y;
int length;
char type;
int color;
};
void main()
{
DLine a; cin >> a.length;
a.x = new double[a.length];
a.y = new double[a.length];
…
delete [] a.x; delete [] a.y;
}
4

5.

Пример структуры с методами
struct DLine
{
double *x, *y;
int length;
char type;
int color;
void setlength(int len);
void free();
void setp(int n,double vx,double vy);
int getcolor() { return color; }
};
5

6.

Реализация методов
void DLine::setlength(int len)
{
x = new double [len];
y = new double [len];
length = len;
}
void DLine::free()
{
delete [] x;
delete [] y;
}
void DLine::setp(int n,double vx,double vy)
{
if (n < length) { x[n] = vx; y[n] = vy; }
}
6

7.

Вызов методов
#define N 200
void main()
{
DLine a, *pa;
pa = &a;
a.setlength(N);
for (int i = 0; i < N; i++)
a.setp(i, i, rand()%100);
pa->color = 7; a.type = ’s’;
cout << pa->getcolor();
a.free();
}
7

8.

Стек
Стек (контейнер) хранит набор объектов одного
типа, обеспечивая в любой момент доступ только
к одному из них по правилу LIFO (last in – first out,
последний пришел – первый ушел). Таким
образом, для стека определены 2 операции:
• push – добавить элемент в вершину (в конец)
стека
• pop – извлечь последний элемент из стека.
В простейшем случае стек организуется на основе
массива с текущим указателем индекса
последнего элемента.
Стек – динамическая структура данных.
8

9.

Пример стека
Переменные для стека, хранящего целые числа
(статический массив, struct не используется):
int stack[200], curpos;
Инициализация стека:
curpos = -1;
Добавление целого числа val в вершину стека:
stack[++curpos] = val;
Извлечение последнего числа из стека:
val = stack[curpos--];
9

10.

Разработчик и пользователь
Разработчик:
• определяет формат хранения данных
• задает набор полей (переменных)
• реализует все методы
• определяет, какие методы будут доступны
пользователю.
Пользователь:
• может создавать объекты нового типа
• не должен иметь доступа к полям (лишняя
информация + возможность неправильного
обращения)
• может использовать для работы с данными
только доступные ему методы.
10

11.

Общий формат описания простого класса
class class_name
{
private:
// скрытые поля и методы
public:
// открытые методы
};
Поля и методы из раздела private доступны
только в методах данного класса (модификатор
private можно опускать).
Методы из раздела public доступны в любом
месте программы.
11

12.

Пример класса для стека
class IStack
{
int arr[100], curpos;
public:
void init() { curpos = -1; }
void push(int val)
{ arr[++curpos] = val; }
int pop() { return arr[curpos--]; }
};
…
IStack a; a.init();
for (int i = 0; i < 10; i++) a.push(i);
for (int i = 0; i < 10; i++)
cout << a.pop() << endl;
12

13.

Проверки при доступе к данным
class IStack
{
int arr[100], curpos;
public:
void init() { curpos = -1; }
void push(int val);
int pop();
};
void IStack::push(int val)
{ if (curpos < 99) arr[++curpos] = val; }
int IStack::pop()
{
if (curpos >= 0) return arr[curpos--];
return -1;
}
13

14.

Конструктор по умолчанию
class IStack
{
int arr[100], curpos;
public:
IStack() { curpos = -1; }
void push(int val);
int pop();
};
…
IStack a;
for (int i = 0; i <= 100; i++) a.push(i);
14

15.

Класс с динамическим массивом,
конструктором с параметрами и деструктором
class IStack
{
int *arr, length, curpos;
public:
IStack(int len);
~IStack();
void push(int val);
int pop();
};
15

16.

Реализация методов класса IStack
IStack::IStack(int len)
{
arr = new int [len];
length = len; curpos = -1;
}
IStack::~IStack() { delete [] arr; }
void IStack::push(int val)
{
if (curpos < length-1)
arr[++curpos] = val;
}
int IStack::pop()
{
if (curpos < 0) return -1;
return arr[curpos--];
}
16

17.

Использование стеков
void main()
{
int i;
IStack a(10), *pb;
for (i = 0; i < 10; i++)
a.push(i*2);
pb = new IStack(20);
for (i = 0; i < 20; i++)
pb->push(i+10);
for (i = 0; i < 20; i++)
cout << pb->pop() << endl;
delete pb;
}
17

18.

Очередь как динамическая структура
Контейнер «очередь» хранит набор объектов
одного типа, обеспечивая в любой момент доступ
только к одному из них по правилу FIFO (first in –
first out, первый пришел – первый ушел). Как и
для стека, для очереди определены 2 операции:
• push – добавить элемент в конец очереди
• pop – извлечь начальный элемент очереди.
18

19.

Очередь на основе массива
В простейшем случае очередь организуется на основе
массива с двумя указателям (индексами) – на
начальный (first) и конечный (last) элемент. Оба
индекса увеличиваются на 1 – last при добавлении
элемента, first – при извлечении.
0
first
last
n-1
Очередь станет пустой, когда first = last+1. Это условие
нужно проверять при извлечении элемента.
Начальные значения: first = 0, last = -1.
Добавление элемента возможно, если last < n-1.
19

20.

Класс для очереди целых чисел на основе
динамического массива
class IQueue
{
int *arr, length, first, last;
public:
IQueue(int len);
~IQueue();
void push(int val);
int pop();
};
20

21.

Реализация методов класса IQueue
IQueue::IQueue(int len)
{
arr = new int [len];
length = len; first = 0; last = -1;
}
IQueue::~IQueue() { delete [] arr; }
void IQueue::push(int val)
{
if (last < length-1)
arr[++last] = val;
}
int IQueue::pop()
{
if (first == last+1) return -1;
return arr[first++];
}
21

22.

Использование объектов-очередей
void main()
{
int i;
IQueue a(10), *pb;
for (i = 0; i < 10; i++)
a.push(i*2);
pb = new IQueue(20);
for (i = 0; i < 20; i++)
pb->push(i+10);
for (i = 0; i < 20; i++)
cout << pb->pop() << endl;
delete pb;
}
22

23.

Недостатки использованного подхода
Очередь – это динамическая структура: в разные
моменты времени элементы могут добавляться или
извлекаться. Но в приведенном выше классе в
очередь нельзя добавить более length элементов,
даже если часть элементов уже извлечена.
0
first
last
В примере с предыдущего слайда после двух циклов
очередь pb будет выглядеть следующим образом:
0
last first
Элементы нельзя добавить, хотя массив пустой!
23

24.

Циклическое заполнение массива
Если last = length-1, но начальный элемент массива
свободен, то запишем новый элемент туда. Для
этого нужно вычислять новую позицию last подругому: last = (last+1) % length. Аналогично должен
изменяться и индекс first.
last
first
Для упрощения проверок, является ли очередь пустой
или заполненной, введем в классе дополнительное
поле count – счетчик текущего числа элементов в
очереди.
24

25.

Класс с циклической организацией очереди
class IQueue
{
int *arr, length, first, last, count;
public:
IQueue(int len);
~IQueue() { delete [] arr; }
void push(int val);
int pop();
};
Открытый интерфейс класса IQueue не изменяется!
Пользователю не нужно изменять свою программу.
25

26.

Реализация методов класса IQueue
IQueue::IQueue(int len) {
arr = new int [len]; length = len;
count = first = 0; last = -1;
}
void IQueue::push(int val) {
if (count < length)
{ last = (last+1) % length;
arr[last] = val; count++;
}
}
int IQueue::pop() {
if (!count) return -1;
int i = first; first = (first+1)%length;
count--; return arr[i];
26
}