close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
15.04.2014
Программирование
с использованием C++11
Полевой Дмитрий Валерьевич
к.т.н., доцент КиК
e-mail: [email protected]
1
15.04.2014
Массив (структура данных)
• «быстрый» доступ к элементу по индексу
• возможность «блочной» обработки
• соответствует низкоуровневым массивам
• тип элемента
• размер
16.04.2014
2
2
15.04.2014
Плюсы массивов
• “быстрое” обращение к элементу
(по индексу)
• отсутствуют накладные расходы памяти
• размер ограничен только объёмом памяти и
разрядностью указателей
• элементы расположены в памяти подряд
(хорошо кэшируется)
16.04.2014
3
3
15.04.2014
Минусы массивов
• «долгое» динамическое добавление и
удаление элементов
• элементы могут перемещаться в памяти
• требуются непрерывные фрагменты памяти
16.04.2014
4
4
15.04.2014
Связный список
• список – структура данных, состоящая из
узлов
• предназначен для хранения данных с
последовательным доступом
• узел содержит как собственно данные, так
и связи с другими узлами
16.04.2014
5
5
15.04.2014
Односвязный список
• однонаправленный список
pHead
0
голова
(первый узел)
16.04.2014
хвост
(последний узел)
6
6
15.04.2014
Односвязный список (узел)
struct SSList;
struct SSList
{
SSList* m_pNext;
T m_data;
};
16.04.2014
7
7
15.04.2014
Двусвязный список
• двунаправленный список
pHead
0
0
16.04.2014
8
8
15.04.2014
Двусвязный список (узел)
struct SDList;
struct SDList
{
SDList* m_pPrev;
SDList* m_pNext;
T m_data;
};
16.04.2014
9
9
15.04.2014
Операции над линейным списком
• создание (создание первого узла)
• уничтожение (удаление всех узлов)
• вставка списка (узла)
• удаление списка (узла)
• навигация по узлам (следующий,
предыдущий)
• доступ к данным узла
16.04.2014
10
10
15.04.2014
Навигация по линейному списку
pNode
pHead
0
if (0 != pNode)
{
pNode = pNode->m_pNext;
}
16.04.2014
11
11
15.04.2014
Навигация по линейному списку
pNode
pHead
0
if (0 != pNode)
{
pNode = pNode->m_pNext;
}
16.04.2014
12
12
15.04.2014
Вставка узла
pPos
pHead
0
pN
16.04.2014
13
13
15.04.2014
Вставка узла
pPos
pHead
0
pN
pN->m_pNext = pPos->m_pNext;
16.04.2014
14
14
15.04.2014
Вставка узла
pPos
pHead
0
pN
pPos->m_pNext = pN;
16.04.2014
15
15
15.04.2014
Удаление узла
pHead
0
16.04.2014
16
16
15.04.2014
Удаление узла
pPos
pHead
0
pD
16.04.2014
17
17
15.04.2014
Удаление узла
pPos
pHead
0
pD
pPos->m_pNext = pD->m_pNext;
16.04.2014
18
18
15.04.2014
Удаление узла
pPos
pHead
0
pD
0
delete pD;
pD = 0;
16.04.2014
19
19
15.04.2014
Уничтожение списка
pHead
pD
0
while (0 != pHead)
{
pD = pHead;
pHead = pHead->m_pNext;
delete pD;
}
16.04.2014
20
20
15.04.2014
Уничтожение списка
pHead
pD
0
while (0 != pHead)
{
pD = pHead;
pHead = pHead->m_pNext;
delete pD;
}
16.04.2014
21
21
15.04.2014
Уничтожение списка
pHead
pD
0
while (0 != pHead)
{
pD = pHead;
pHead = pHead->m_pNext;
delete pD;
}
16.04.2014
22
22
15.04.2014
Уничтожение списка
pHead
pD
0
while (0 != pHead)
{
pD = pHead;
pHead = pHead->m_pNext;
delete pD;
}
16.04.2014
23
23
15.04.2014
Кольцевой список
• циклический (замкнутый) список
pHead
16.04.2014
24
24
15.04.2014
Плюсы списков
• простое динамическое добавление и
удаление элементов
• размер ограничен только объёмом памяти
и разрядностью указателей
• элементы не перемещаются в памяти
16.04.2014
25
25
15.04.2014
Минусы списков
•
•
•
•
накладные расходы памяти на связи
“долгое” обращение к элементу по индексу
“долгое” выделение узла
элементы списка могут быть расположены в
памяти разреженно (фрагментация памяти,
плохо кэшируется)
16.04.2014
26
26
15.04.2014
Кортеж
• последовательность конечного числа
элементов
• пустое множество — кортеж
(с нулевым количеством элементов)
• для каждого кортежа (a1,…,an)=T ,
множество (a, a1,…,an)={a, {a, T}} также
является кортежем
16.04.2014
27
27
15.04.2014
Упорядоченная пара
• кортеж длинны 2
< e1, e2 > = {e1, {e1, e2 }}
• сравнение на равенство
< x1, x2 > = < y1, y2 > ⇔ x1 = y1 ^ x2 = y2
16.04.2014
28
28
15.04.2014
Прямое (декартово) произведение
множеств
• A×B={<a, b>} ∀a∈A, ∀b∈B
• прямое произведение множества A и
множества B есть множество A×B,
элементами которого являются
упорядоченные пары <a, b> для всех
возможных a∈A и b∈B
16.04.2014
29
29
15.04.2014
Бинарное отношение
• подмножество декартова произведения двух
множеств
• R – бинарное отношение на множестве S
R ⊂ S×S
• форма записи
<a, b>∈R
aRb
16.04.2014
30
30
15.04.2014
Отношение строгого порядка
(бинарное, антирефлексивное, транзитивное, антисимметричное
отношение)
• ∀a ¬(aRa)
• ∀a ∀b ∀c aRb ∧ bRc ⇒ aRc
• ∀a ∀b aRb ∧ bRa ⇒ a=b
• обозначение (R<
16.04.2014
или <)
31
31
15.04.2014
Несравнимые элементы
• для множества S с заданным строгим
порядком R< a∈S и b∈S несравнимы, если не
выполняется ни одно из условий
a<b
a=b
b<a
16.04.2014
32
32
15.04.2014
Наименьший элемент
• для множества S с заданным строгим
порядком R< определен наименьший
элемент a∈S, если ∀b∈S a < b
• если определен, то единственный
16.04.2014
33
33
15.04.2014
Максимальный элемент
• для множества S с заданным строгим
порядком R< определен максимальный
элемент a∈S, если !∃b∈S a < b
• может быть несколько
16.04.2014
34
34
15.04.2014
Дерево
(определение через отношение)
• конечное непустое множество T узлов
• отношение R< строгого порядка на T×T
• наименьший элемент (корень)
• максимальные элементы (листья)
• не максимальные элементы (внутренние
узлы)
16.04.2014
35
35
15.04.2014
Дерево
(определение через множества )
• конечное непустое множество T узлов
• существует один корень дерева r∈T
• остальные узлы (за исключением r)
распределены среди непересекающихся
множеств T1,...,Tm, являющихся деревьями
• деревья T1,...,Tm называются поддеревьями
данного корня r
16.04.2014
36
36
15.04.2014
Дерево
(определение через множества )
• листья – корни поддеревьев, которые не
имеют подчиненных деревьев
• внутренние узлы - корни поддеревьев,
которые имеют подчиненные деревья
16.04.2014
37
37
15.04.2014
Дерево
(иллюстрация)
a<b
a<e
a<f
b<c
b<d
листья
c
d
e
f
b
a корень
〈a, {〈b, {〈c〉, 〈d〉}〉, 〈e〉, 〈f〉}}〉
16.04.2014
38
38
15.04.2014
Дерево (доп. определения)
• корень – выделенная вершина дерева
• поддерево – любое дерево, корень
которого не совпадает с корнем исходного
дерева
16.04.2014
39
39
15.04.2014
Узел дерева (доп. определения)
• степень — количество поддеревьев узла
• уровень — длина пути от корня до узла
рекурсивное определение:
– уровень корня дерева T равен 0
– уровень любого другого узла на единицу
больше, чем уровень корня ближайшего
поддерева дерева T, содержащего данный узел
16.04.2014
40
40
15.04.2014
“Родственные отношения”
• родитель, родительский узел
• ребенок, потомок
– подчиненный по отношению к родителю узел
• предок
• брат
– братья имеют общего родителя
16.04.2014
41
41
15.04.2014
“Родственные отношения”
(иллюстрация)
братья
c
d
дети для a
b
e
f
a общий
предок
16.04.2014
42
42
15.04.2014
N-арное дерево
• степень внутреннего узла не превышает N
• степень внутреннего узла N
16.04.2014
43
43
15.04.2014
N-арное дерево
• бинарное (двоичное) дерево (N=2)
• тернарное дерево (N=3)
• квадро-дерево (N=4)
16.04.2014
44
44
15.04.2014
Радиальное подчинение (иллюстрация)
e
d
c
16.04.2014
b
a
корень
f
45
45
15.04.2014
Представление дерева в памяти
• список указателей на детей
• список индексов (в массиве) детей
• “послойно”
• список ребер
• матрица отношений
16.04.2014
46
46
15.04.2014
Список указателей
• узел
корень
– число детей
– указатели на детей
– данные
16.04.2014
47
47
15.04.2014
Послойно
• узел
корень
– указатель на первого
ребенка
– указатель на
брата/родителя
– данные
16.04.2014
48
48
15.04.2014
Список ребер
• узлы храним в массиве
• ребро – пара индексов
<родитель, ребенок>
• ребра храним упорядоченно
(по родителю)
16.04.2014
49
49
15.04.2014
Дерево (операции)
• создание
• уничтожение
• добавление поддерева
• удаление поддерева
• навигация
• изменение корня
16.04.2014
50
50
15.04.2014
Навигация по дереву
• проверить наличие родителя
• перейти к родителю
• проверить наличие детей
• перейти к ребенку
• перейти к брату
• перейти к корню дерева
16.04.2014
51
51
15.04.2014
Обход дерева
• поиск заданного узла в дереве
• получение списка всех узлов
16.04.2014
52
52
1/--страниц
Пожаловаться на содержимое документа