|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[64] совпадать. При этом разумная реализация гарантирует, что функции Successor и Predecessor обратны, что начав с Minumum(S) и применяя функцию Successor, мы перечислим все элементы множества в неубывающем порядке и т.п. Стоимость операций над множествами обычно оценивается через размер множеств, к которым они применяются. Например, в главе 14 мы описываем структуру данных, которая позволяет выполнить каждую из перечисленных операций за время О (lgra), где га - число элементов множества. Обзор части III В главах 11-15 мы описываем различные структуры данных, предназначенные для работы с динамическими множествами. С помощью этих структур данных можно разработать эффективные алгоритмы для решения многих различных задач. Кстати, с одной важной структурой данных (кучей) мы уже познакомились в главе 7. В главе 11 мы разбираем принципы работы с простейшими структурами данных: стеками, очередями, связанными списками и корневыми деревьями. В этой же главе рассказывается, как реализовать записи и указатели с помощью языков программирования, в которых нет соответствующих типов данных. Большая часть материала этой главы составляет стандартный материал начального курса программирования. В главе 12 мы познакомимся с хеш-таблицами, поддерживающими операции Insert, Delete и Search. В худшем случае поиск в хеш-таблице требует времени О(га), но среднее время, необходимое для выполнения любой из словарных операций с хеш-таблицей, составляет (при некоторых предположениях) лишь 0(1). Анализ хеширования использует теорию вероятностей, но для понимания большей части главы знакомство с этой теорией не обязательно. В главе 13 мы занимаемся деревьями двоичного поиска. Эти деревья поддерживают все перечисленные операции с множествами. В худшем случае стоимость каждой из операций есть в (га), но для случайно построенного дерева математическое ожидание этой стоимости есть О (lgra). На базе деревьев двоичного поиска строятся многие другие структуры данных. Глава 14 посвящена красно-чёрным деревьям. Эта разновидность деревьев двоичного поиска гарантированно работает быстро: время выполнения каждой операции в худшем случае есть О (lgra). Красно-чёрные деревья представляют собой один из вариантов «сбалансированных» деревьев поиска; другой вариант (Б-деревья) обсуждается в главе 19. Алгоритмы для работы с красно-чёрными деревьями устроены довольно хитро. Хотя детали можно опустить при первом чтении, интересно в них разобраться. В главе 15 мы рассматриваем дополнительные структуры на красно-чёрных деревьях, позволяющие выполнять ещё несколько операций (порядковые статистики, операции с деревьями промежутков). 11Элементарные структуры данных В этой главе мы рассматриваем несколько простых структур данных для хранения множеств: стеки, очереди, списки, корневые деревья. Мы покажем, как можно реализовать их с помощью указателей или массивов. 11.1. Стеки и очереди Стеки и очереди - это динамические множества, в которых элемент, удаляемый из множества операцией Delete, не задаётся произвольно, а определяется структурой множества. Именно, из стека (stack) можно удалить только тот элемент, который был в него добавлен последним: стек работает по принципу «последним пришёл - первым ушёл» (last-in, first-out - сокращенно LIFO). Из очереди (queue), напротив, можно удалить только тот элемент, который находился в очереди дольше всего: работает принцип «первым пришёл - первым ушёл» (nrst-in, first-out, сокращенно FIFO). Существует несколько способов эффективно реализовать стеки и очереди. В этом разделе мы расскажем, как реализовать их на базе массива. Стеки Операция добавления элемента в стек часто обозначается Push, а операция удаления верхнего элемента из стека часто обозначается Pop (push в данном контексте означает «запихивать», a pop - «вынимать»). Стек можно уподобить стопке тарелок, из которой можно взять верхнюю и на которую можно положить новую тарелку. [Другое название стека в русской литературе - «магазин» - понятно всякому, кто разбирал автомат Калашникова.] На рис. 11.1 показано, как можно реализовать стек ёмкостью не более п элементов на базе массива S[l. .п]. Наряду с массивом мы храним число topfS*], являющееся индексом последнего добавленного в стек элемента. Стек состоит из элементов S[l.. top[S]], где |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||