3 лекция (1246020)
Текст из файла
«Структуры данных»Лекция №3Цель лекции: : дать основные понятия структур данных.Структура данных – это способ хранения и организации данных,облегчающий доступ к этим данным и их модификацию.Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ruМГТУим. Н.Э.
Баумана«Структуры данных»Лекция №3Элементарные структуры данныхСтек (англ. stack — стопка) — структура данных с методом доступа кэлементам LIFO (англ. Last In — First Out, «последним пришел — первымвышел»). :))Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ruМГТУим. Н.Э. Баумана«Структуры данных»Лекция №3Элементарные структуры данныхОсновные операции:– инициализация (Init)– деструктизация (Destroy)– помещение элемента в стек (Push)– удаление элемента из стека (Pop)– значение верхнего элемента (Top)– проверка на пустоту (isEmpty)– проверка на полноту (isFull)Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ruМГТУим.
Н.Э. Баумана«Структуры данных»Лекция №3Элементарные структуры данныхКафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ruМГТУим. Н.Э. Баумана«Структуры данных»Лекция №3Элементарные структуры данныхОчередь (англ. queue) — структура данных с методом доступа кэлементам по принципу FIFO (First In First Out), «первым пришел —первым вышел»).
:))Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ruМГТУим. Н.Э. Баумана«Структуры данных»Лекция №3Элементарные структуры данныхКафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ruМГТУим. Н.Э. Баумана«Структуры данных»Лекция №3Элементарные структуры данныхОсновные операции:– инициализация (Init)– деструктизация (Destroy)– помещение элемента в очередь (ENQUEUE)– удаление элемента из очереди (DEQUEUE)– значение первого элемента (Head)– значение последнего элемента (Tail)– проверка на пустоту (isEmpty)– проверка на полноту (isFull)Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ruМГТУим.
Н.Э. Баумана«Структуры данных»Лекция №3Элементарные структуры данныхСвязанный список (linked list) — это структура данных, в которой объектырасположены в линейном порядке.Ключ(Указатель)Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ruМГТУим. Н.Э. Баумана«Структуры данных»Элементарные структуры данныхОсновные операцииПоиск в связанном списке LIST_SEARCH(L, k)Лекция №3Вставка в связанный список LIST_INSERT (L, x)Удаление из связанного списка LIST_DELETE (L, x)Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ruМГТУим. Н.Э. Баумана«Структуры данных»Нелинейные структуры данныхЛекция №3Дерево – это структура данных, представляющая собой совокупностьэлементов и отношений, образующих иерархическую структуру этихэлементов .Каждое дерево обладает следующими свойствами:• существует узел, в который не входит ни одной дуги (корень);• в каждую вершину, кроме корня, входит одна дуга.Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ruМГТУим.
Н.Э. Баумана«Структуры данных»Нелинейные структуры данныхЛекция №3Бинарное (двоичное) дерево – это динамическая структура данных,представляющее собой дерево, в котором каждая вершина имеет не болеедвух потомков .Частный случай бинарного дерева –списокКафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ruМГТУим. Н.Э. Баумана«Структуры данных»Нелинейные структуры данныхЛекция №3Основные операции–––––––создание бинарного дерева;печать бинарного дерева;обход бинарного дерева;вставка элемента в бинарное дерево;удаление элемента из бинарного дерева;проверка пустоты бинарного дерева;удаление бинарного дерева.Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ruМГТУим.
Н.Э. Баумана«Структуры данных»Нелинейные структуры данныхЛекция №3Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ruМГТУим. Н.Э. Баумана«Структуры данных»Нелинейные структуры данныхЛекция №3Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ruМГТУим. Н.Э.
Баумана«Структуры данных»Нелинейные структуры данныхЛекция №3Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ruМГТУим. Н.Э. Баумана«Структуры данных»Специальные графыГраф ПетерсонаПлатоновы графыТетраэдрЛекция №3КубОктаэдрКафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ruМГТУим. Н.Э. Баумана«Структуры данных»Специальные графыПлатоновы графыДодекаэдрЛекция №3ИкосаэдрКафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ruМГТУим.
Н.Э. Баумана«Структуры данных»Операции над графами-Граф-СуграфЛекция №3ПодграфКафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ruМГТУим. Н.Э. Баумана«Структуры данных»Операции над графамиЛекция №3-Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ruМГТУим. Н.Э. Баумана«Структуры данных»Маршруты, цепи, циклыЛекция №3Маршрут, в котором нет повторяющихся ребер, называется цепью.Замкнутая цепь называется циклом.Цепь и цикл называются простыми, если нет повторяющихся вершин.Последовательность вершин: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 – простой цикля.Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ruМГТУим.
Н.Э. Баумана«Структуры данных»СвязностьЛекция №3я.Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ruМГТУим. Н.Э. Баумана«Структуры данных»Метрика графаЛекция №3Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ruМГТУим. Н.Э. Баумана«Структуры данных»ДеревьяЛекция №3Связанный граф без циклов называется деревом.ТеоремаДерево, у которого число вершин равно числу вершин графа, из котороговыделено это дерево, называется покрывающим деревом.Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ruМГТУим.
Н.Э. Баумана«Структуры данных»ДеревьяЛекция №3Минимальное остовное дерево (или минимальное покрывающее дерево) всвязанном, взвешенном, неориентированном графе — это покрывающеедерево этого графа, имеющее минимальный возможный вес, где под весомдерева понимается сумма весов входящих в него рёбер.Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ruМГТУим. Н.Э. Баумана«Структуры данных»Цикломатическое число графаЛекция №3Наименьшее число ребер, которое необходимо удалить из графа G, чтобыон стал ациклическим (деревом), называется цикломатическим числомграфа.Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ruМГТУим.
Н.Э. Баумана«Структуры данных»Лекция №3Основные выводы:1.2.Изучены основные понятия структур данных;Рассмотрено применение теории при решении задач конструкторскотехнологической информатики;Кафедра ИУ4 «Проектирование и технология производства ЭА» http://nanotech.iu4.bmstu.ruМГТУим. Н.Э. Баумана.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
