Структуры данных. Лекция №3

Содержание

Слайд 2

«Структуры данных» Лекция №3 Кафедра ИУ4 «Проектирование и технология производства ЭА»

«Структуры данных»
Лекция №3

Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ru

Элементарные структуры

данных
Стек (англ. stack — стопка) — структура данных с методом доступа к элементам LIFO (англ. Last In — First Out, «последним пришел — первым вышел»). :))
Слайд 3

«Структуры данных» Лекция №3 Кафедра ИУ4 «Проектирование и технология производства ЭА»

«Структуры данных»
Лекция №3

Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ru

Элементарные структуры

данных
Основные операции:
– инициализация (Init) – деструктизация (Destroy) – помещение элемента в стек (Push) – удаление элемента из стека (Pop) – значение верхнего элемента (Top) – проверка на пустоту (isEmpty) – проверка на полноту (isFull)
Слайд 4

«Структуры данных» Лекция №3 Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ru Элементарные структуры данных

«Структуры данных»
Лекция №3

Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ru

Элементарные структуры

данных
Слайд 5

«Структуры данных» Лекция №3 Кафедра ИУ4 «Проектирование и технология производства ЭА»

«Структуры данных»
Лекция №3

Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ru

Элементарные структуры

данных
Очередь (англ. queue) — структура данных с методом доступа к элементам по принципу FIFO (First In First Out), «первым пришел — первым вышел»). :))
Слайд 6

«Структуры данных» Лекция №3 Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ru Элементарные структуры данных

«Структуры данных»
Лекция №3

Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ru

Элементарные структуры

данных
Слайд 7

«Структуры данных» Лекция №3 Кафедра ИУ4 «Проектирование и технология производства ЭА»

«Структуры данных»
Лекция №3

Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ru

Основные операции:
–

инициализация (Init) – деструктизация (Destroy) – помещение элемента в очередь (ENQUEUE) – удаление элемента из очереди (DEQUEUE) – значение первого элемента (Head) – значение последнего элемента (Tail) – проверка на пустоту (isEmpty) – проверка на полноту (isFull)

Элементарные структуры данных

Слайд 8

«Структуры данных» Лекция №3 Кафедра ИУ4 «Проектирование и технология производства ЭА»

«Структуры данных»
Лекция №3

Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ru

Элементарные структуры

данных
Связанный список (linked list) — это структура данных, в которой объекты расположены в линейном порядке.

Ключ
(Указатель)

Слайд 9

«Структуры данных» Лекция №3 Кафедра ИУ4 «Проектирование и технология производства ЭА»

«Структуры данных»
Лекция №3

Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ru

Элементарные структуры

данных
Основные операции
Поиск в связанном списке LIST_SEARCH(L, k)
Вставка в связанный список LIST_INSERT (L, x)
Удаление из связанного списка LIST_DELETE (L, x)
Слайд 10

«Структуры данных» Лекция №3 Кафедра ИУ4 «Проектирование и технология производства ЭА»

«Структуры данных»
Лекция №3

Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ru

Нелинейные структуры

данных
Дерево – это структура данных, представляющая собой совокупность элементов и отношений, образующих иерархическую структуру этих элементов .

Каждое дерево обладает следующими свойствами:
существует узел, в который не входит ни одной дуги (корень);
в каждую вершину, кроме корня, входит одна дуга.

Слайд 11

«Структуры данных» Лекция №3 Кафедра ИУ4 «Проектирование и технология производства ЭА»

«Структуры данных»
Лекция №3

Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ru

Нелинейные структуры

данных
Бинарное (двоичное) дерево – это динамическая структура данных, представляющее собой дерево, в котором каждая вершина имеет не более двух потомков .
Частный случай бинарного дерева –
список
Слайд 12

«Структуры данных» Лекция №3 Кафедра ИУ4 «Проектирование и технология производства ЭА»

«Структуры данных»
Лекция №3

Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ru

Нелинейные структуры

данных

Основные операции
создание бинарного дерева;
печать бинарного дерева;
обход бинарного дерева;
вставка элемента в бинарное дерево;
удаление элемента из бинарного дерева;
проверка пустоты бинарного дерева;
удаление бинарного дерева.

Слайд 13

«Структуры данных» Лекция №3 Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ru Нелинейные структуры данных

«Структуры данных»
Лекция №3

Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ru

Нелинейные структуры

данных
Слайд 14

«Структуры данных» Лекция №3 Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ru Нелинейные структуры данных

«Структуры данных»
Лекция №3

Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ru

Нелинейные структуры

данных
Слайд 15

«Структуры данных» Лекция №3 Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ru Нелинейные структуры данных

«Структуры данных»
Лекция №3

Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ru

Нелинейные структуры

данных
Слайд 16

«Структуры данных» Лекция №3 Кафедра ИУ4 «Проектирование и технология производства ЭА»

«Структуры данных»
Лекция №3

Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ru

Специальные графы
Граф

Петерсона
Платоновы графы
Тетраэдр Куб Октаэдр
Слайд 17

«Структуры данных» Лекция №3 Кафедра ИУ4 «Проектирование и технология производства ЭА»

«Структуры данных»
Лекция №3

Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ru

Специальные графы
Платоновы

графы
Додекаэдр Икосаэдр
Слайд 18

Операции над графами Локальные Граф Подграф Суграф «Структуры данных» Лекция №3

Операции над графами
Локальные
Граф Подграф
Суграф

«Структуры данных»
Лекция №3

Кафедра ИУ4 «Проектирование и технология производства

ЭА» http://nanotech.iu4.bmstu.ru
Слайд 19

«Структуры данных» Лекция №3 Кафедра ИУ4 «Проектирование и технология производства ЭА»

«Структуры данных»
Лекция №3

Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ru

Операции над

графами
- алгебраические
Слайд 20

«Структуры данных» Лекция №3 Кафедра ИУ4 «Проектирование и технология производства ЭА»

«Структуры данных»
Лекция №3

Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ru

Маршруты, цепи,

циклы
Маршрут, в котором нет повторяющихся ребер, называется цепью.
Замкнутая цепь называется циклом.
Цепь и цикл называются простыми, если нет повторяющихся вершин.
Последовательность вершин:
2, 3, 5, 4 – не маршрут
2, 3, 4, 5, 1, 4, 3 – маршрут, но не цепь
3, 1, 4, 5, 1, 2- цепь, но не простая
2, 3, 1, 4, 3, 1, 2 – маршрут, но не цикл
2, 3, 1, 4, 5, 1, 2 – цикл, но не простой
2, 3, 4, 5, 1, 2 – простой цикл
я.
Слайд 21

«Структуры данных» Лекция №3 Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ru Связность я.

«Структуры данных»
Лекция №3

Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ru

Связность
я.

Слайд 22

«Структуры данных» Лекция №3 Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ru Метрика графа

«Структуры данных»
Лекция №3

Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ru

Метрика графа

Слайд 23

Деревья Связанный граф без циклов называется деревом. Теорема Дерево, у которого

Деревья
Связанный граф без циклов называется деревом.
Теорема
Дерево, у которого число вершин равно

числу вершин графа, из которого выделено это дерево, называется покрывающим деревом.

«Структуры данных»
Лекция №3

Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ru

Слайд 24

Деревья Минимальное остовное дерево (или минимальное покрывающее дерево) в связанном, взвешенном,

Деревья
Минимальное остовное дерево (или минимальное покрывающее дерево) в связанном, взвешенном, неориентированном графе — это покрывающее дерево этого

графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.

«Структуры данных»
Лекция №3

Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ru

Слайд 25

Цикломатическое число графа Наименьшее число ребер, которое необходимо удалить из графа

Цикломатическое число графа
Наименьшее число ребер, которое необходимо удалить из графа G,

чтобы он стал ациклическим (деревом), называется цикломатическим числом графа.

«Структуры данных»
Лекция №3

Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ru

- Предыдущая
Антипаттерны: хардкодинг, софткодинг
Следующая -
Введение в программирование на языке C#

Похожие презентации

Презентация "Андрей Матвеев" - скачать презентации по МХК
Die Zeit
. Экомониторинг
Հայկազուն-Երվանդունիների թագավորություն (6)
German Customs and Traditions
Ноябрь – зиме родной брат
Леонард Эйлер. Круги Эйлера
Шағын бизнес
Концепция подготовки спортивного резерва в РФ до 2025
Презентация "Государственное регулирование цен" - скачать презентации по Экономике
Mitsubishi Galant VIII - история автомобиля
Католическая церковь
Презентация Дальневосточное Таможенное управление
Третейское разбирательство. Нотариат в Российской Федерации
ТЕРМОРЕГУЛЯЦИЯ
Меры социальной поддержки по ЖКУ. Субсидии
Этапы создания текста перевода
Взаимоотношения с риелторскими службами
Оборудование плавильного участка
Микробиология сальмонеллезов
Вибрационные методы
Пампа Моняк
Культура и поведение
Туристский клуб «Белки». Первый сплав по Берди - «Первооткрыватель»
Cyber Spying in world today
OptoGaN Enabling bulb-like brightness for LEDs
Виды отклонений от языковой нормы и их передача
Отделение электроники. Лидский колледж
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть