Неупорядоченный массив

Cтраница 2

Рассмотрим процедуру внешнего упорядочения в случае предельно ограниченных ресурсов внешней памяти, когда, кроме магнитной ленты с хранящимся на ней неупорядоченным массивом, мы не имеем в нашем распоряжении ни одной ленты. [16]

Метод слияния может быть положен в основу аппаратной реализации алгоритма упорядочения с помощью специализированного устройства, входы которого связаны со всеми элементами неупорядоченного массива, а на выходах вырабатывается упорядоченный массив. Аппаратная реализация алгоритма упорядочения позволяет резко повысить его быстродействие как за счет исключения ряда служебных операций ( выборка команд, формирование промежуточных адресов, проверка условия выхода из цикла и др.), так и за счет совмещения во времени большого числа разных сравнений, что дает наибольший эффект. [17]

Для этого назначается новая выходная лента и в список включаются все ленты, кроме ленты № 1, на которой размещаются элементы неупорядоченного массива, и ленты, назначенной выходной. [18]

Пусть в нашем распоряжении имеется М магнитных лент, часть из которых, не превышающая половины общего количества магнитных лент, занята неупорядоченным массивом. Выделим из числа свободных лент М / 2 ( или ( М-1) / 2, если М - нечетное) лент в качестве входных и равномерно распределим на них сформированные из всего массива начальные участки. [19]

При последовательном выполнении нескольких операторов Ф ( i, j) участки неупорядоченного массива последовательно считываются в ОЗУ в том порядке, в котором они хранились в неупорядоченном массиве. Поэтому перемещение вдоль неупорядоченного массива от его начала к концу осуществляется в одном направлении без потерь времени на поиск зоны. [20]

Укажите количество операций сравнения, необходимое для помещения ключей EASYQUESTIONB первоначально пустую таблицу с использованием АТД, которые реализованы в соответствие с одним из четырех элементарных подходов: упорядоченный или неупорядоченный массив или список. [21]

Эта реализация, которую можно сравнить с реализациями стеков и очередей с использованием массивов, которые рассматривались в главе 4 ( см. программы 4.7 и 4.15), хранит элементы в неупорядоченном массиве. Элементы добавляются в конец массива и удаляются с конца массива, как это имеет место в стеке. [22]

Подпрограммы поиска осуществляют поиск записей как в массиве, если ищутся отдельные записи, так и в записи, если там разыскиваются отдельные элементы. В неупорядоченных массивах поиск осуществляется методом перебора, в упорядоченных - методом дихотомического поиска. [23]

Рассмотрим существенные особенности такой процедуры. Пусть дан исходный неупорядоченный массив объемом в п элементов. На первом этапе он будет разбит на два подмассива по заданному значению JTO оператором, описанным в § 5.2, и на три подмассива ( один из которых содержит лишь единственный опорный элемент) оператором, описанным в § 5.4. В любом случае каждое разбиение порождает не более двух подмассивов, требующих в свою очередь дальнейшего деления. Поскольку результат деления ( число элементов в первом и во втором из подмассивов) случаен, процесс упорядочения можно наглядно представить в виде некоторого случайного двоичного дерева. Действительно, пусть любая вершина этого дерева отображает факт применения оператора разделения. Тогда ребру, входящему в вершину, можно приписать число, соответствующее объему массива до использования оператора, а левому и правому ребру, выходящим из вершины, можно приписать числа, соответствующие количеству элементов в группе младших и в группе старших элементов соответственно. [24]

Если заполнение массива m вынесено из процедуры, то сортировка его все равно происходит в процедуре door. В процедуру берется часть неупорядоченного массива. Кроме того, случайно задается элемент массива т, начиная с которого необходимое количество элементов передаются в процедуру для моделирования. [26]

Частными случаями будут преобразование неупорядоченного массива для двух связанных процедур, преобразование одного частично упорядоченного массива в одной процедуре ( случай, рассматривавшийся в примере), преобразование неупорядоченного массива в одной процедуре. [27]

Наиболее трудоемок поиск в неупорядоченном массиве. Наиболее прост - в полностью упорядоченном массиве или в дереве. Однако упорядочение массива и построение дерева сами по себе требуют больших затрат машинного времени. Если стоит задача минимизации общего времени, затрачиваемого на упорядочение и поиск, то при крайне редких запросах на поиск целесообразным окажется простой перебор, а при очень частых запросах - полное упорядочение или построение дерева, обеспечивающие наиболее экономичный дихотомический поиск. В промежуточных случаях самым эффективным должно быть разумное сочетание дихотомического поиска с простым перебором при частичном упорядочении исходного массива. В данной главе будут рассмотрены некоторые методы организации информации и поиска, обеспечивающие наименьшую суммарную сложность совокупности процедур поиска и упорядочения в фиксированном массиве, а также в массиве с переменным составом элементов. [28]

Базовые структуры данных, которые обсуждались в главе 3, предоставляют множество различных возможностей для реализации очередей по приоритетам. Программа 9.2 демонстрирует реализацию, которая в качестве ба зовой структуры данных использует неупорядоченный массив. Операция найти наибольший элемент реализуется следующей последовательностью действий: сначала производится просмотр массива с целью обнаружения наибольшего элемента, затем осуществляется замена наибольшего элемента на последний элемент с последующим уменьшением размера очереди на единицу. На рис. 9.1 показано содержимое массива для тестовой последовательности операций. Базовая реализация соответствует тем реализациям, которые можно было бы видеть в главе 4 для стеков и очередей небольших размеров ( см. программы 4.7 и 4.15) и полезны при работе с очередями небольших размеров. Основные различия между ними связаны с их производительностью. [29]

Суперпозиционная перфокарта с краевой перфорацией. [30]

Страницы: 1 2 3