close

Вход

Забыли?

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

код для вставкиСкачать
23.04.2014
Программирование
(структурное, процедурное,
объектно-ориентированное)
с использованием C++/C#
Полевой Дмитрий Валерьевич
к.т.н., доцент КиК
e-mail: [email protected]
1
23.04.2014
АТД “cтек”
• динамическая структура данных
• упорядоченный набор элементов
• LIFO (Last In First Out) – добавление и
удаление элементов с одного конца,
называемого вершиной стека
23.04.2014
2
2
23.04.2014
Стек (схема работы)
вершина
push
getTop
pop
isEmpty
23.04.2014
3
3
23.04.2014
Стек – операции
• создание
• уничтожение
• добавление элемента
• удаление элемента
• проверка на пустоту
• получение значение верхнего элемента
23.04.2014
4
4
23.04.2014
Стек – реализация
• динамический массив
• линейный список
23.04.2014
5
5
23.04.2014
Стек (динамический массив)
вершина
• физический и логический размер
•
•
•
•
добавление «в конец»
удаление «из конца»
проверка логического размера
доступ к последнему элементу
23.04.2014
6
6
23.04.2014
Стек (линейный список)
«голова»
•
•
•
•
добавление «в голову»
удаление «из головы»
проверка наличия элементов
доступ к голове
23.04.2014
7
7
23.04.2014
АТД “очередь”
• динамическая структура данных
• упорядоченный набор элементов
• FIFO (First In First Out) – добавление
элементов с одного конца (хвост) и
удаление с другого конца (голова)
23.04.2014
8
8
23.04.2014
Очередь - операции
• создание
• уничтожение
• добавление элемента
• удаление элемента
• проверка на пустоту
• получение значение верхнего элемента
23.04.2014
9
9
23.04.2014
Очередь (схема работы)
«голова»
getTop
pop
push
«хвост»
23.04.2014
10
10
23.04.2014
Очередь – реализация
• динамический массив
(вставка и извлечение с концов)
• динамический массив
(подвижные концы)
• список
23.04.2014
11
11
23.04.2014
Очередь (подвижные концы)
iTail = (iTail + 1) % size; // push
iHead = (iHead + 1) % size; // pop
size – размер массива
iHead
iTail
23.04.2014
12
12
23.04.2014
Очередь (линейный список)
«голова»
«хвост»
•
•
•
•
добавление «в голову»
удаление «из хвоста»
проверка наличия элементов
доступ «к хвосту»
23.04.2014
13
13
23.04.2014
Дэк (двусвязная очередь)
• добавление и извлечение элементов
возможна с обоих концов
pushBack
popBack
pushFront
popFront
• реализация аналогична очереди
23.04.2014
14
14
23.04.2014
Очередь с приоритетом
• пара <ключ, данные>
• порядок извлечения элементов
определяется ключом, а не порядком
добавления элементов в очередь
23.04.2014
15
15
23.04.2014
Очередь с приоритетом
(реализация)
• список (сортировка при вставке)
• дерево (сортирующее)
• массив (сортировка при вставке)
• …
23.04.2014
16
16
23.04.2014
Матрица (в математике)
Ма́трица — математический объект,
записываемый в виде прямоугольной таблицы
чисел и допускающий алгебраические
операции (сложение, вычитание, умножение)
между ним и другими подобными объектами.
Обычно матрицы представляются двумерными
(прямоугольными) таблицами.
(0,0)
(1,0)
(1,1)
(2,0)
23.04.2014
17
17
23.04.2014
АТД “матрица”
• создание
• уничтожение
• получение доступа к элементу
по индексу (i, j)
• получение размера по измерению
23.04.2014
18
18
23.04.2014
Алгебраические операции
• умножение на число
• сложение двух матриц
• умножение двух матриц
23.04.2014
19
19
23.04.2014
Дополнительные операции
• изменение размера по измерению
• транспонирование
• вставка/удаление столбца/строки
• перестановка двух строк/столбцов
• умножение на число строки/столбца
23.04.2014
20
20
23.04.2014
Способ представления
• приведенный индекс
– размеры
– массив элементов
(i,j) → i * nCol + j
или
• массив строк/столбцов
23.04.2014
21
21
23.04.2014
АТД “полином”
F(x)=a0·x0 + a1·x1 +…+ aN·xN
ai – коэффициент
i – показатель степени
(неотрицательное целое)
x
– переменная
степень многочлена – максимальный показатель
степени (для 0 не определен)
23.04.2014
22
22
23.04.2014
Операции с полиномом
• создание (одночлен)
• уничтожение
• сложение полиномов
• умножение полиномов
(в т.ч. умножение на число)
23.04.2014
23
23
23.04.2014
Дополнительные операции
• получение коэффициента при заданном
показателе степени
• вычисление значения
23.04.2014
24
24
23.04.2014
Представление полинома
• массив an,
n=0,N
• массив пар {n,an}
• список пар {n,an}
23.04.2014
25
25
23.04.2014
Оптимизация
• выбор способа хранения в зависимости от
разреженности и размерности
• для разреженных – хранение в
упорядоченном виде (поддержание
упорядоченности при вставке членов)
23.04.2014
26
26
23.04.2014
АТД “ассоциативный массив”
• динамическая структура данных
• набор уникальных пар <ключ, значение>
• «быстрый» поиск значения по ключу
23.04.2014
27
27
23.04.2014
Ассоциативный массив – операции
• создание
• уничтожение
•
•
•
•
добавление элемента
удаление элемента
проверка на пустоту
получение значения по ключу
23.04.2014
28
28
23.04.2014
Ассоциативный массив – реализация
•
•
•
•
•
дерево
хеш-таблица
динамический массив (сортированный)
список (сортированный)
…
23.04.2014
29
29
23.04.2014
АТД “множество”
• динамическая структура данных
• набор уникальных элементов
• «быстрая» проверка наличия значения
23.04.2014
30
30
23.04.2014
Множество – операции
• создание
• уничтожение
•
•
•
•
добавление элемента
удаление элемента
проверка на пустоту
проверка элемента на вхождение
• получение размера
23.04.2014
31
31
23.04.2014
Множество – операции
• объединение множеств
• пересечение множеств
• дополнение можеств
23.04.2014
32
32
23.04.2014
Множество – реализация
•
•
•
•
•
•
дерево
хеш-таблица
битовый массив
динамический массив (сортированный)
список (сортированный)
…
23.04.2014
33
33
23.04.2014
Хеширование
• детерминированный алгоритм
• преобразование данных в битовую строку
фиксированной длины
• хеш – битовая строка
• коллизия – одинаковый хеш для разных
данных
23.04.2014
34
34
23.04.2014
Применение хеширования
• криптография
• контроль (целостности) данных
• ускорение поиска
23.04.2014
35
35
23.04.2014
Хеш-таблица
• структура данных
• хранение и поиск пар вида
<ключ,значение>
• основная идея
– сравнивать хеш-ключи быстрее, чем исходные
объекты
– коллизии редки
23.04.2014
36
36
23.04.2014
System.Collections
• нетипизированные элементы коллекций
• хранятся ссылки на System.Object
• основные классы
ArrayList – динамический массив
Queue – очередь
SortedList – очередь с приоритетом
Stack – стек
Hashtable – ассоциативный массив
23.04.2014
37
37
23.04.2014
Недостатки
нетипизированных коллекций
• отсутствие проверки типов при компиляции
– писать больше кода
– писать больше тестов
– больше « молиться» при работе
• накладные расходы на хранение/обработку
23.04.2014
38
38
23.04.2014
System.Collections.Generic
• типизированные элементы коллекций
• основные классы
List<T> – динамический массив
LinkedList<T> – дек
Queue<T> – очередь
SortedList<TKey, TValue> – очередь с
приоритетом
Stack<T> – стек
23.04.2014
39
39
23.04.2014
System.Collections.Generic
• ассоциативный массив
Dictionary<TKey, TValue>
SortedDictionary<TKey, TValue>
• множество
HashSet<T>
SortedSet<T>
23.04.2014
40
40
23.04.2014
List<T>
• основные операции
– через индексы
– на концах
23.04.2014
41
41
23.04.2014
Обработка списков
• LinkedListNode<T> - элемент списка
• свойства
List
Next
Previous
Value
• null – отсутствие узла
23.04.2014
42
42
23.04.2014
23.04.2014
43
43
23.04.2014
• Count – число элементов (свойство)
• Any – проверка наличия элементов
• Contains – проверка наличия элемента
23.04.2014
44
44
23.04.2014
• CopyTo – скопировать в массив
• ToArray – скопировать в новый массив
23.04.2014
45
45
1/--страниц
Пожаловаться на содержимое документа