Cтраница 1
Базовые структуры данных, которые обсуждались в главе 3, предоставляют множество различных возможностей для реализации очередей по приоритетам. Программа 9.2 демонстрирует реализацию, которая в качестве ба зовой структуры данных использует неупорядоченный массив. Операция найти наибольший элемент реализуется следующей последовательностью действий: сначала производится просмотр массива с целью обнаружения наибольшего элемента, затем осуществляется замена наибольшего элемента на последний элемент с последующим уменьшением размера очереди на единицу. На рис. 9.1 показано содержимое массива для тестовой последовательности операций. Базовая реализация соответствует тем реализациям, которые можно было бы видеть в главе 4 для стеков и очередей небольших размеров ( см. программы 4.7 и 4.15) и полезны при работе с очередями небольших размеров. Основные различия между ними связаны с их производительностью. [1]
Как использовать список в качестве базовой структуры данных, понятно. [2]
Разработайте реализацию АТД первого класса для стека из упражнения 4.73, которая в качестве базовой структуры данных использует массив. [3]
Разработайте реализацию АТД первого класса для стека из упражнения 4.73, которая в качестве базовой структуры данных использует связный список. [4]
Напишите реализацию основного интерфейса очереди по приоритетам, который использует упорядоченный массив в качестве базовой структуры данных. [5]
Создайте АТД Неупорядоченная очередь ( напишите интерфейс и реализацию), в котором в качестве базовой структуры данных используется связный список. Напишите как можно более эффективные реализации операций insert и remove и проанализируйте связанные с ними издержки для наихудшего случая их выполнения. [6]
Разработайте реализацию АТД первого класса для стека ю упражнения 4 73, когорт я качестве базовой структуры данных использует связный список. [7]
Создайте АТД Неупорядоченная очередь ( напишите интерфейс и реализацию), в котором в качестве базовой структуры данных используется массив. [8]
Напишите реализацию для приведенного в тексте АТД Полином ( программа 4.24), в которой в качестве базовой структуры данных используются связные списки. Списки не должны содержать узлов, соответствующих членам с нулевыми коэффициентами. [9]
Если главный интерес представляет последовательный перебор набора элементов, их можно организовать в виде связного списка - базовой структуры данных, в которой каждый элемент содержит информацию, необходимую для получения следующего элемента. Основное преимущество связных списков перед массивами заключается в возможности эффективного изменения расположения элементов. За эту гибкость приходится жертвовать скоростью доступа к произвольному элементу списка, поскольку единственный способ получения элемента состоит в отслеживании связей от начала списка. [10]
Для приведенного в тексте интерфейса очереди FIFO ( программа 4.13) запишите реализацию, в которой в качестве базовой структуры данных используется циклический список. [11]
Согните ЛТЛ Неупорядоченная очередь ( напишите интерфейс и реал и за - цию), а котором в качестве базовой структуры данных используется мясе ив. [12]
Разработайте реализацию данного в тексте АТД первого класса Очередь FIFO ( программа 4.21), в которой в качестве базовой структуры данных используется массив. [13]
Хотя по причине фундаментальной взаимосвязи между стеками и рекурсивными программами ( см. главу 5), со стеками приходится сталкиваться чаще, чем с очередями FIFO, будут также встречаться и алгоритмы, для которых очереди являются естественными базовыми структурами данных. Как уже отмечалось, очереди и стеки используются в вычислительных приложениях чаще всего для того, чтобы отложить выполнение того или иного процесса. Хотя многие приложения, использующие очередь отложенных задач, работают корректно вне зависимости от того, какие правила удаления элементов задействуются в операциях удалить, общее время выполнения программы или использования ресурсов, может зависеть от применяемой дисциплины. Когда в подобных приложениях встречается большое количество операций вставить или удалить, выполняемых над структурами данных с большим числом элементов, различия в производительности обретают первостепенную важность. Поэтому в настоящей книге столь существенное внимание уделяется таким АТД. Если бы производительность программ не интересовала, можно было бы создать один единственный АДТ с операциями вставить и удалить, однако производительность является предельно важным показателем, поэтому каждое правило, в сущности, соответствует своему АТД. В заключение данного раздела описываются несколько таких АТД, которые будут рассматриваться подробно в следующих главах. [14]
Хотя к данному классу могут принадлежать алгоритмически-универсальные языки, например подмножество АПЛ или Лиспа, в котором нет аппарата описания функций и базовых операций, позволяющих интерпретировать данные ( тексты или списки) как программы входного языка, использование их становится непрактичным как только структура данных, необходимая для решения задачи, не совпадает с базовой структурой данных языка. [15]