Всё для Учёбы — студенческий файлообменник
1 монета
pdf

Студенческий документ № 043122 из НИТУ МИСиС

Объектно-ориентированное программирование

с использованием C++

Полевой Дмитрий Валерьевич

к.т.н., доцент КиК e-mail: oop.misis@gmail.com

АТД и структуры данных

• АТД определяет набор допустимых операций

• структура данных определяет способ хранения информации и совершения операций (физическое размещение в памяти, реализация)

• АТД может реализовываться различными структурами данных

• часто называются одинаково

Связный список

• список - структура данных, состоящая из узлов

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

• узел содержит как собственно данные, так и связи с другими узлами

Односвязный список

• однонаправленный список pHead

Односвязный список (узел)

struct SList; struct SList

{ SList* m_pNext;

T m_data; }; Двусвязный список

• двунаправленный список pHead

Двусвязный список (узел)

struct DList;

struct DList { DList* m_pPrev;

DList* m_pNext; T m_data;

}; Операции над линейным списком

• создание (создание первого узла)

• уничтожение (удаление всех узлов)

• вставка списка (узла)

• удаление списка (узла)

• навигация по узлам (следующий, предыдущий)

• доступ к данным узла

Навигация по линейному списку

Навигация по линейному списку

pHead

pD0 while (0 != pHead)

{ pD = pHead; pHead = pHead->m_pNext; delete pD;

} pHead pD0 while (0 != pHead)

{ pD = pHead; pHead = pHead->m_pNext; delete pD;

} pHead pD0 while (0 != pHead)

{ pD = pHead; pHead = pHead->m_pNext; delete pD;

} pHead pD0 while (0 != pHead)

{ pD = pHead; pHead = pHead->m_pNext; delete pD;

} Кольцевой список

• циклический (замкнутый) список pHead

Плюсы списков

• простое динамическое добавление и удаление элементов

• размер ограничен только объёмом памяти и разрядностью указателей

• элементы не перемещаются в памяти

Минусы списков

• накладные расходы памяти на связи

• "долгое" обращение к элементу по индексу

• "долгое" выделение узла

• элементы списка могут быть расположены в памяти разреженно (фрагментация памяти, плохо кэшируется)

АТД "cтек"

• динамическая структура данных

• упорядоченный набор элементов

• LIFO (Last In First Out) - добавление и удаление элементов с одного конца, называемого вершиной стека

Стек (схема работы)

Стек - операции

• создание

• уничтожение

• добавление элемента

• удаление элемента

• получение значение верхнего элемента

Стек (интерфейс класса)

Stack() Stack(const Stack& obj) ~Stack()

Stack& operator=(const Stack& rhs) void push(const T& obj) void pop() bool isEmpty() const T& getTop() const T& getTop() const или

T getTop()

Стек - реализация

• динамически массив

• линейный список

Стек (динамический массив)

вершина

T& getTop() { size_t i(size(s.arr) - 1); assert(i >= 0); return m_data.at(i);

} Стек (линейный список массив)

вершина

T& getTop() { assert(0 != m_pHead); return m_pHead->m_data;

} АТД "очередь"

• динамическая структура данных

• упорядоченный набор элементов

• FIFO (First In First Out) - добавление элементов с одного конца (хвост) и удаление с другого конца (голова)

Очередь - операции

• создание

• уничтожение

• добавление элемента

• удаление элемента

• получение значение верхнего элемента

Очередь (схема работы)

Очередь (интерфейс класса)

Queue() Queue(const Queue& obj) ~Queue()

Queue& operator=(const Queue& rhs) void push(const T& obj) void pop() bool isEmpty() const T& getTop() const T& getTop() const или

T getTop()

Очередь - реализация

• динамический массив

(вставка и извлечение с концов)

• динамический массив

(подвижные концы)

• список

Очередь (подвижные концы)

iTail = (iTail + 1) % size; // push iHead = (iHead + 1) % size; // pop

size - размер буфера

iTail Очередь с приоритетом

• • порядок извлечения элементов определяется ключом, а не порядком добавления элементов в очередь

Дэк (двусвязная очередь)

• добавление и извлечение элементов возможна с обоих концов

push_back pop_back push_front pop_front

Матрица (в математике)

Матрица - математический объект, записываемый в виде прямоугольной таблицы чисел и допускающий алгебраические операции (сложение, вычитание, умножение) между ним и другими подобными объектами. Обычно матрицы представляются двумерными (прямоугольными) таблицами.

(0,0) (1,0) (1,1) (2,0) АТД "матрица"

• создание

• уничтожение

• получение доступа к элементу по индексу (i, j)

• получение размера по измерению

• изменение размера по измерению

Матрица (интерфейс класса)

Matrix(const int nRow, const int nCol);

Matrix(const Matrix& matr); ~Matrix();

Matrix& operator=(const Matrix& rhs); int nRow() const; int nCol() const;

T& at(const int iRow, const int iCol); const T& at(const int iRow, const int iCol)

const; ostream& writeAsTxt(ostream& ostr) const;

Алгебраические операции

• умножение на число

• сложение двух матриц

• умножение двух матриц

Дополнительные операции

• транспонирование (для квадратной)

• вставка/удаление столбца/строки

• перестановка двух строк/столбцов

• умножение на число строки/столбца

Способ представления

• приведенный индекс

- размеры

- массив элементов

или • массив строк/столбцов

АТД "полином"

F(x)=a0·x0 + a1·x1 +...+ aN·xN

ai - коэффициент i - показатель степени

(неотрицательное целое) x - переменная

степень многочлена - максимальный

показатель степени (для 0 не определен)

Операции с полиномом

• создание (одночлен)

• уничтожение

• сложение полиномов

• умножение полиномов

(в т.ч. умножение на число)

• вычисление значения

Дополнительные операции

• получение коэффициента при заданном показателе степени

Представление полинома

• массив an, n=0,N

• массив пар {n,an}

• список пар {n,an}

Оптимизация

• выбор способа хранения в зависимости от разреженности и размерности

• для разреженных - хранение в упорядоченном виде (поддержание упорядоченности при вставке членов)

Дерево (иллюстрация)

Дерево (доп. определения)

• корень - выделенная вершина дерева

• поддерево - любое дерево, корень которого не совпадает с корнем исходного дерева

Узел дерева (доп. определения)

• степень - количество поддеревьев узла

• уровень - длина пути от корня до узла рекурсивное определение:

- уровень корня дерева T равен 0

- уровень любого другого узла на единицу больше, чем уровень корня ближайшего поддерева дерева T, содержащего данный узел

"Родственные отношения"

• родитель, родительский узел

• ребенок, потомок

- подчиненный по отношению к родителю узел

• предок

• брат - братья имеют общего родителя

"Родственные отношения" (иллюстрация)

N-арное дерево

• степень внутреннего узла не превышает N

• степень внутреннего узла N

N-арное дерево

• бинарное (двоичное) дерево (N=2)

• тернарное дерево (N=3)

• квадро-дерево (N=4)

Радиальное подчинение (иллюстрация)

Представление дерева в памяти

• список указателей на детей

• список индексов (в массиве) детей

• "послойно"

• список ребер

• матрица отношений

Список указателей

Послойно

Список ребер

• узлы храним в массиве

• ребро - пара индексов

• ребра храним упорядоченно (по родителю)

Дерево (операции)

• создание

• уничтожение

• добавление поддерева

• удаление поддерева

• навигация

• изменение корня

Навигация по дереву

• проверить наличие родителя

• перейти к родителю

• проверить наличие детей

• перейти к ребенку

• перейти к брату

• перейти к корню дерева

Обход дерева

• поиск заданного узла в дереве

• получение списка всех узлов

• "в ширину"

- послойно, начиная от корня

• "в глубину"

- все потомки текущей вершины (для каждой)

Сбалансированное дерево

• Высота двоичного дерева - максимальный уровень его листьев (-1 для пустого дерева).

• Баланс узла - разность высот левого и правого поддерева.

• Сбалансированным бинарным деревом

является такое бинарное дерево, у которого абсолютное значение баланса каждого узла меньше или равно 1.

Баланс в дереве (иллюстрация)

3 3 Узел дерева (послойно)

struct STNode {

STNode* m_pNext; STNode* m_pChild;

T m_data;

}; Вставка поддерева (послойно)

Вставка поддерева (список детей)

21.04.2012 cppNewb.ru 2

21.04.2012 cppNewb.ru 3

Вставка узла

Вставка узла

21.04.2012 cppNewb.ru 2

21.04.2012 cppNewb.ru 2

Вставка узла

21.04.2012 cppNewb.ru 2

Удаление узла

Удаление узла

21.04.2012 cppNewb.ru 2

21.04.2012 cppNewb.ru 2

Удаление узла

21.04.2012 cppNewb.ru 2

Уничтожение списка

Уничтожение списка

21.04.2012 cppNewb.ru 2

21.04.2012 cppNewb.ru 2

Уничтожение списка

21.04.2012 cppNewb.ru 2

21.04.2012 cppNewb.ru 2

21.04.2012 cppNewb.ru 2

21.04.2012 cppNewb.ru 2

Показать полностью…
200 Кб, 21 апреля 2012 в 11:17 - Россия, Москва, НИТУ МИСиС, 2012 г., pdf
Рекомендуемые документы в приложении