Недопустимый идентификатор
Идентификатор Metodicheskie-materialy/Nelineinye-dinamicheskie-struktury-dannyh-v-C-Derevya-Elektronnyi-resurs-metod-ukazaniya-70945/1/Симонова Е.В. Линейные динамические структуры данных в С не соответствует правильному Файл архива электронных ресурсов. Это могло произойти по одной из следующих причин:
- URL текущей страницы неверен. Если Вы попали сюда извне архива электронных ресурсов, то, возможно, адрес набран неправильно или поврежден.
- Вы ввели недопустимый ID в форму — пожалуйста, повторите попытку.
Если у Вас возникли проблемы или Вы считаете, что ID должен работать, то свяжитесь с администраторами сайта.
Перечислите узлы которые являются потомками узла а
Дерево — это нелинейная динамическая структура данных, представленных в виде иерархии элементов, называемых узлами . Схематично дерево можно изобразить так, как показано на рисунке ниже:
На самом верхнем уровне такой иерархии всегда имеется только один узел, называемый корнем дерева . У нас это узел A . Каждый узел, кроме корневого, связан только с одним узлом более высокого уровня, называемым узлом-предком . Например, для узла D предком является узел A , предок для узла G — это D и т.д. При этом каждый элемент дерева может быть связан с помощью ветвей ( ребер ) с одним или несколькими узлами более низкого уровня. Они для данного узла являются дочерними узлами ( узлами-потомками ). Так, для узла A потомками будут B , C и D , для узла B — E и F и т.д. Элементы, расположенные в конце ветвей и не имеющие дочерних узлов, называют листьями . На рисунке выше листьями являются узлы E , F , C , G , J и I .
От корня до любого узла всегда существует только один путь. Максимальная длина пути от корня до листьев называется высотой дерева . У нас максимально длинный путь образует цепочка узлов A , D , H и J , т.е. высота дерева равна 3 .
Любой узел дерева с его потомками также образует дерево, называемое поддеревом (относительно исходного дерева). Например, можно рассматривать поддерево, начинающееся с узла D (это узлы D , G , H , I , J ).
Число поддеревьев для данного узла образует степень узла . Для узлов A и D степень равна 3 , степень узла B равна 2 , узел H имеет степень 1 , а у листьев (узлы E , F , C , G , J и I ) степень равна 0 . Максимальное значение среди степеней всех узлов определяет степень дерева . Если максимальная степень узлов в каком-то дереве равна n , то его называют n -арным деревом . Наше дерево имеет степень 3 (из-за узлов A и D ), и его можно называть триарным .
Дерево степени 2 называется бинарным . Бинарные деревья наиболее просты с точки зрения сложности реализации алгоритмов работы с деревьями, поэтому именно бинарные деревья применяются там, где требуется динамическая структура типа дерево. Если формально требуется дерево степени большей, чем 2 , например, 5 -й степени, то, сформировав такое дерево, его можно преобразовать в бинарное, а далее работать как с бинарным деревом.
Как правило, в дереве всегда задают какой-либо принцип упорядоченности, например, по возрастанию какого-то параметра (ключа). То есть, для каждого узла ключи наследников располагаются слева направо по возрастанию. В бинарном дереве для каждого узла значение ключа левого наследника будет меньше значения ключа узла, в свою очередь значение ключа в узле меньше значения ключа в правом наследнике.
Типовые операции с двоичными деревьями
Для работы с двоичными деревьями используем две структуры:
1) Структура, содержащая собственно сами данные . Она может иметь любое количество полей. Одно из полей (или совокупность из нескольких полей) будет ключевым . Именно по нему будет вестись упорядочивание данных. Для рассматриваемой ниже задачи нам достаточно одного поля, которое будет ключом:
2) Структура, определяющая узел дерева :
Узлы устройств и стеки устройств
В Windows устройства представлены узлами устройств в дереве устройств Plug and Play (PnP). Как правило, при отправке запроса ввода-вывода на устройство его обработку помогают несколько драйверов. Каждый из этих драйверов связан с объектом устройства, а объекты устройства расположены в стеке. Последовательность объектов устройства вместе со связанными с ними драйверами называется стеком устройств. Каждый узел устройства имеет собственный стек устройств.
Узлы устройств и дерево устройств Plug and Play
Windows упорядочивает устройства в древовидную структуру, называемую деревом устройств Plug and Play или просто деревом устройств. Как правило, узел в дереве устройств представляет устройство или отдельную функцию на составном устройстве. Однако некоторые узлы представляют программные компоненты, которые не имеют связи с физическими устройствами.
Узел в дереве устройств называется узлом устройства. Корневой узел дерева устройств называется корневым узлом устройства. По соглашению корневой узел устройства рисуется в нижней части дерева устройств, как показано на следующей схеме.
Дерево устройств иллюстрирует связи «родители-потомки», присущие среде PnP. Некоторые узлы в дереве устройств представляют собой шины, к которым подключены дочерние устройства. Например, узел шины PCI представляет физическую шину PCI на системной плате. Во время запуска диспетчер PnP просит водителя шины PCI перечислить устройства, подключенные к шине PCI. Эти устройства представлены дочерними узлами узла шины PCI. На предыдущей схеме узел шины PCI содержит дочерние узлы для нескольких устройств, подключенных к шине PCI, включая хост-контроллеры USB, аудиоустройства и порт PCI Express.
Некоторые устройства, подключенные к шине PCI, сами являются автобусами. Диспетчер PnP просит каждую из этих шин перечислить подключенные к ней устройства. На предыдущей схеме видно, что звуковой контроллер — это шина, к которому подключено звуковое устройство. Мы видим, что порт PCI Express — это шина, к которому подключен видеоадаптер, а видеоадаптер — это шина с одним монитором.
Тип узла, представляющий устройство или шину, зависит от вашей точки зрения. Например, видеоадаптер можно рассматривать как устройство, которое играет ключевую роль при подготовке кадров, отображаемых на экране. Однако адаптер дисплея также можно рассматривать как шину, которая может обнаруживать и перечислять подключенные мониторы.
Объекты устройств и стеки устройств
Объект устройства — это экземпляр структуры DEVICE_OBJECT. Каждый узел устройства в дереве устройств PnP имеет упорядоченный список объектов устройств, и каждый из этих объектов устройства связан с драйвером. Упорядоченный список объектов устройств вместе со связанными с ними драйверами называется стеком устройств для узла устройства.
Стек устройств можно представить несколькими способами. В самом формальном смысле стек устройств — это упорядоченный список пар (объект устройства, драйвер). Однако в некоторых контекстах может быть полезно рассматривать стек устройств как упорядоченный список объектов устройств. В других контекстах может быть полезно рассматривать стек устройств как упорядоченный список драйверов.
По соглашению стек устройств имеет верхнюю и нижнюю части. Первый объект устройства, который будет создан в стеке устройств, находится в нижней части, а последний объект устройства, который будет создан и присоединен к стеку устройств, находится в верхней части.
На следующей схеме узел устройства Proseware Gizmo содержит стек устройств, содержащий три пары (объект устройства, драйвер). Верхний объект устройства связан с драйвером AfterThought.sys, средний объект устройства — с Proseware.sys драйвера, а нижний объект устройства — с Pci.sys драйвера. Узел шины PCI в центре схемы содержит стек устройств, содержащий две пары (объект устройства, драйвер) — объект устройства, связанный с Pci.sys, и объект устройства, связанный с Acpi.sys.
Как создается стек устройств?
Во время запуска диспетчер PnP просит водителя для каждой шины перечислить дочерние устройства, подключенные к шине. Например, диспетчер PnP просит водителя шины PCI (Pci.sys) перечислить устройства, подключенные к шине PCI. В ответ на этот запрос Pci.sys создает объект устройства для каждого устройства, подключенного к шине PCI. Каждый из этих объектов устройства называется физическим объектом устройства (PDO). Вскоре после того, как Pci.sys создаст набор PDO, дерево устройств будет выглядеть так, как показано на следующей схеме.
Диспетчер PnP связывает узел устройства с каждым вновь созданным PDO и ищет в реестре, чтобы определить, какие драйверы должны входить в стек устройств для узла. Стек устройств должен иметь один (и только один) драйвер функции и при необходимости может иметь один или несколько драйверов фильтров. Драйвер функции является драйвером main для стека устройств и отвечает за обработку запросов на чтение, запись и управление устройством. Драйверы фильтров играют вспомогательные роли при обработке запросов на чтение, запись и управление устройствами. При загрузке каждой функции и драйвера фильтра он создает объект устройства и присоединяется к стеку устройств. Объект устройства, созданный драйвером функции, называется объектом функционального устройства (FDO), а объект устройства, созданный драйвером фильтра, называется объектом устройства фильтра (Filter DO). Теперь дерево устройств выглядит примерно так, как на этой схеме.
На схеме обратите внимание, что в одном узле драйвер фильтра находится над драйвером функции, а в другом узле драйвер фильтра находится под драйвером функции. Драйвер фильтра, который находится над драйвером функции в стеке устройств, называется драйвером верхнего фильтра. Драйвер фильтра, который находится под драйвером функции, называется драйвером нижнего фильтра.
PDO всегда является нижним объектом устройства в стеке устройств. Это является результатом создания стека устройств. Сначала создается PDO, и при присоединении дополнительных объектов устройств к стеку они присоединяются к верхней части существующего стека.
Примечание При установке драйверов для устройства установщик использует сведения в файле сведений (INF), чтобы определить, какой драйвер является драйвером функции, а какие — фильтрами. Как правило, INF-файл предоставляется корпорацией Майкрософт или поставщиком оборудования. После установки драйверов для устройства диспетчер PnP может определить функции и фильтровать драйверы для устройства, зайдя в реестр.
Водители автобусов
На предыдущей схеме видно, что Pci.sys драйвера играет две роли. Во-первых, Pci.sys связан с FDO в узле устройства шины PCI. Фактически он создал FDO в узле устройства шины PCI. Таким образом, Pci.sys является драйвером функции для шины PCI. Во-вторых, Pci.sys связана с PDO в каждом дочернем узле шины PCI. Напомним, что она создала PDO для дочерних устройств. Драйвер, который создает PDO для узла устройства, называется драйвером шины для узла.
Если точкой отсчета является шина PCI, то Pci.sys — драйвер функции. Но если вашей точкой отсчета является устройство Proseware Gizmo, то Pci.sys является водителем автобуса. Эта двойная роль является типичной в дереве устройств PnP. Водитель, который служит в качестве водителя-функции для автобуса, также выступает в качестве водителя автобуса для дочернего устройства автобуса.
Стеки устройств в пользовательском режиме
До сих пор мы обсуждали стеки устройств в режиме ядра. То есть драйверы в стеках выполняются в режиме ядра, а объекты устройства сопоставляются с системным пространством, которое является адресным пространством, доступным только для кода, выполняющегося в режиме ядра. Сведения о различиях между режимом ядра и режимом пользователя см. в разделе Режим пользователя и режим ядра.
В некоторых случаях устройство имеет стек устройств в пользовательском режиме в дополнение к стеку устройств в режиме ядра. Драйверы пользовательского режима часто основаны на User-Mode Driver Framework (UMDF), которая является одной из моделей драйверов, предоставляемых платформами драйверов Windows (WDF). В UMDF драйверы представляют собой библиотеки DLL в пользовательском режиме, а объекты устройств — это COM-объекты, реализующие интерфейс IWDFDevice. Объект устройства в стеке устройств UMDF называется объектом устройства WDF (WDF DO).
На следующей схеме показан узел устройства, стек устройств в режиме ядра и стек устройств в пользовательском режиме для устройства USB-FX-2. Драйверы в стеке пользовательского режима и режима ядра участвуют в запросах ввода-вывода, направленных на устройство USB-FX-2.
Дерево (структура данных)
тип данных в информатике / Материал из Википедии — свободной энциклопедии
Уважаемый Wikiwand AI, давайте упростим задачу, просто ответив на эти ключевые вопросы:
Перечислите основные факты и статистические данные о Дерево (структура данных)?
Кратко изложите эту статью для 10-летнего ребёнка
ПОКАЗАТЬ ВСЕ ВОПРОСЫ
Дерево — одна из наиболее широко распространённых структур данных в информатике, эмулирующая древовидную структуру в виде набора связанных узлов. Является связным графом, не содержащим циклы. Большинство источников также добавляет условие на то, что рёбра графа не должны быть ориентированными. В дополнение к этим трём ограничениям, в некоторых источниках указывается, что рёбра графа не должны быть взвешенными.
Oops something went wrong: