Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
Лекция 10
5.2. Очереди и их реализация. Примеры применения стеков и очередей
Очередь — это динамическая структура данных, добавление элементов в которую выполняется в один конец, а выборка — из другого конца. При выборке элемент исключается из очереди. Говорят, что очередь реализует принцип обслуживания FIFO (first in — first out, первым пришел — первым обслужен). В программировании очереди применяются очень широко — например, при моделировании, буферизованном вводе-выводе или диспетчеризации задач в операционной системе.
Очереди могут иметь векторную и списковую структуру хранения, причем векторная структура может занимать статическую или динамическую память. Очередь векторной структуры из-за ограничения элементов имеет свойство переполнения, когда хвост очереди достигнет конца вектора. В этом случае добавление элементов становится невозможным, даже если в начальной части вектора будут свободные элементы из-под выбранных элементов. Для устранения этого требуются кольцевые очереди. При достижении конца вектора новые элементы добавляются в свободные элементы с начала вектора. Однако все равно возможно переполнение, когда хвост догонит голову. Если же голова догонит хвост, то очередь оказывается пустой.
Очереди применяются в операционных системах (очереди задач, буферы ввода-вывода, буфер ввода с клавиатуры, очередь в сетях ЭВМ) и при моделировании реальных процессов. Области применения стеков: передача параметров в функцию; трансляция; реализация рекурсии в программах; реализация управления динамической памятью.
Дек — это разновидность очереди, в которой включение и выборка элементов возможны с обоих концов. Разновидности дека: дек с ограниченным входом и дек с ограниченным выходом. Первый допускает включение элементов только на одном конце, а второй — выборку элементов только с одного конца.
6.1. Представление регулярных деревьев в массиве. Ссылочные представления деревьев
Граф — это совокупность непустого множества вершин и множества пар вершин (связей между вершинами). Объекты представляются как вершины, или узлы графа, а связи — как дуги, или ребра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или ребрах.
Многие структуры, представляющие практический интерес в информатике, могут быть представлены графами.
Ориентированный граф — это граф, все ребра которого имеют направление. Такие направленные ребра называются дугами. Дуги соединяют две неравноправные вершины: одна из них называется началом дуги (та, из которой дуга исходит), другая — концом дуги (дуга входит в нее). Двигаться по ориентированному графу можно только в направлениях, заданными дугами. Любое ребро — это пара дуг, направленных навстречу друг другу. Если в графе присутствуют и ребра и дуги, он называется смешанным.
Степень вершин в ориентированном графе — это пара чисел: первое характеризует количество исходящих из вершины дуг, а второе — количество входящих дуг.
Регулярный граф — такой граф, степени вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей. Степень регулярности является инвариантом графа. Регулярные графы представляют особую сложность для многих алгоритмов. Регулярный граф с вершинами степени k называется k-регулярным или регулярным графом степени k.
Сильно регулярный граф — это регулярный граф, у которого каждая пара смежных вершин имеет одинаковое количество общих соседей, и каждая пара несмежных вершин имеет одинаковое количество общих соседей.
Дерево — это связный ациклический граф. Связность означает наличие путей между любой парой вершин, ацикличность — отсутствие циклов и то, что между парами вершин имеется только по одному пути.
Ориентированное дерево — такое, в котором между двумя вершинами существует не более одного пути.
Корневое дерево — это ориентированное дерево, в котором можно выделить вершины трех видов: корень, листья (терминальные вершины) и остальные вершины (нетерминальные). Для такого дерева выполняются два обязательных условия:
Одним из распространенных способов хранения деревьев является массив списков. Это одномерный массив размерности n (количество узлов дерева). Каждый элемент этого массива — это упорядоченный или неупорядоченный список ближайших потомков этого предка.
|
| <== предыдущая | | | следующая ==> |
| Мнемонические шкалы | | | Лекция 10: Частотные методы определения устойчивости |
Date: 2015-08-15; view: 396; Нарушение авторских прав; Помощь в написании работы --> СЮДА... |