Непрерывный и ссылочный способы реализации структур данных.

Основная память машины организована в виде отдельных ячеек с последовательно увеличивающимися адресами. Однако часто эти ячейки используются как основа для реализации других способов размещения данных.

Чтобы использовать структуру данных как абстрактный инструмент, необходимо описать способ хранения данных и описать систему операций, выполняемых с этими данными.

х+1

х

Пусть алгоритм работы с показаниями температуры, снимаемыми каждый час в течение суток, написан на ЯП высокого уровня. Программисту, удобно представить эти показания в виде одномерного массива t, так что t[1] – 1-е показание, …, t[24] – последнее. Переход от концептуальной организации в виде одномерного массива к действительной организации данных внутри машинной памяти довольно ясен: данные записаны в виде последовательности из 24 ячеек памяти с последовательно возрастающими номерами. Зная адрес первой ячейки в этой последовательности, транслятор легко сможет преобразовать обращение вида t[4] в соответствующий действительный адрес:

память

t[2]х

t[1]х

массив хранится в ОП, начиная с ячейки с адресом х, поэтому адрес ячейки t[k] будет х + k – 1, 1<=k<=24. В этом примере использован непрерывный способ хранения данных.

Часто данные представляются в виде таблицы

день недели фамилия
1.Агеев
2.Буйнов
3.Валов

Программист организует данные в виде двумерного массива. Однако память организована в виде ячеек с последовательными адресами, а не в виде прямоугольника. Поэтому следует отобразить прямоугольную структуру на линейную. Для этого размер массива не должен меняться при обновлении данных, это позволит заранее определить количество памяти, необходимое для размещения всех элементов массива и зарезервировать непрерывный участок памяти соответствующего размера. Теперь можно выполнить запись данных в массив, последовательно размещая их в памяти, строка за строкой: развертка по строкам (развертка по столбцам).

1-ая строка 2-ая строка 3-ая строка

Как вычислить адрес ячейки, соответствующей элементу массива [3,4]:

х – начало 1-й строки,

х+5 – 1 = х – 4 – конец 1-й строки,

х + 5 - начало 2-й строки,

(х + 5) + 5 – 1 = х+9 - конец 2-й строки,

х + 5*2 - начало 3-й строки,

(х + 5*2) + 4 – 1 = х + 5*(3-1) + (4 – 1) = х + 13 – адрес искомого элемента.

Обобщая, получим, что если двумерный массив хранится в ОП с разверткой по строкам; а c – количество столбцов в массиве, то адрес элемента [i,j] может быть вычислен по формуле:

x + c * (i – 1) + (j – 1),

где х – адрес 1-го элемента 1-й строки.

Таким образом, с двумерным массивом можно работать как с одномерным.

Структура хранения данных в виде последовательности ячеек памяти с возрастающими адресами называется непрерывным списком. Такая структура получается при использовании массивов. Непрерывный список прост в применении, но имеет существенные недостатки: для вставки/удаления элемента в упорядоченный список с сохранением упорядоченности, потребуется достаточно большой объем работ по смещению элементов списка, так называемые массовые операции, затрагивающие значительную часть всех элементов структуры данных,:

Более того, при добавлении элементов может потребоваться выделить другой, больший, непрерывный участок ОП для хранения полученного списка.

Чтобы избежать указанных проблем, можно хранить отдельные элементы списка в различных местах памяти. Для этого требуется хранить каждый элемент в небольшом блоке памяти, включающем указатель на следующий элемент списка и самого элемента. Такая структура называется односвязанным списком:

Операции удаления и вставки элементов в односвязанный список выполняются относительно просто: достаточно изменить одно значение указателя при удалении, а при вставке найти небольшой блок памяти для нового элемента и отредактировать два указателя. Связанный список представляет собой ссылочный способ хранения данных.

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

Если ограничить область применения операций вставки и удаления только концами списка, использование непрерывной структуры может оказаться более удобным. Примером такой структуры является стек – список, в котором все включения и исключения элементов выполняются только на одном конце структуры (структура типа LIFO). Конец стека, на котором выполняется исключения и включения называют вершиной стека, другой конец стека называют основанием стека. Классическим приложением стеков является выполнение вложенных подпрограмм

Основная

программа Подпрограмма А Подпрограмма В

завершение работы вложенных процедур происходит в порядке, обратном порядку их вызова.

Перед вызовом подпрограммы A адрес команды, следующей за командой вызова A, сохраняется в стеке. Это так называемый адресвозврата в программу. В стек помещаются также параметры подпрограммы перед ее вызовом, локальные переменные подпрограммы. По окончании работы подпрограммы А из стека удаляются все локальные переменные и параметры, извлекается адрес возврата и передается управление по этому адресу. Этот механизм гарантирует получение указателя на правильный адрес возврата. Если в схеме В+А с другими параметрами, то описанный процесс соответствует рекурсии.

Концепция стека является абсолютно органичной для любого процесса, связанного с выходом из системы в порядке, обратном порядку входа в нее.

Для реализации стековой структуры в памяти компьютера обычно резервируется блок непрерывно расположенных ячеек памяти, достаточно большой, чтобы он мог разместиться там при расширении. Один из концов этого блока отмечается как основание стека, сюда помещается первый элемент. При вставке и извлечении элементов вершина стека перемещается вперед и назад внутри зарезервированного блока памяти. Адрес элемента, являющегося в текущий момент вершиной стека, записывается в дополнительную ячейку памяти, называемую указателемвершиныстека:

Вся система работает следующим образом:

чтобы вставить элемент в стек надо изменить указатель вершины стека так, чтобы он указывал на следующую свободную позицию в стеке, а затем поместить новый элемент в эту позицию;

чтобы извлечь элемент считываются данные из вершины стека, а затем изменяется текущее значение указателя вершины стека, чтобы оно указывало на ниже расположенный элемент стека.

Для использования стека как абстрактного инструмента следует разработать процедуры вставки, извлечения элементов, проверки не является ли стек пустым или заполненным.

При организации стека в непрерывном блоке ячеек памяти различие между его концептуальной и реальной структурами в ОП невелико (но есть ограничения на размеры блока под стек). Если стек реализован в виде односвязанного списка, то концептуальная структура стека будет значительно отличаться от реальной (велика роль сборщика мусора), зато не будет значительного ограничения размера стека.

Очередь представляет собой такой список, в котором включение элементов выполняется на одном конце, а исключение - на другом. Концепция очереди органична для любой системы, в которой объекты обслуживаются в порядке их поступления (принцип FIFO). Конец, на котором выполняется удаление элементов, называется началом (головой) очереди; конец, на котором выполняется включение, называется концом (хвостом очереди).

Можно реализовать очередь в непрерывном блоке ячеек памяти компьютера. Для этого понадобятся два указателя: указатель начала и указатель конца очереди. Когда очередь пуста оба указателя указывают на один и тот же адрес памяти, по которому не хранится никакой информации.

Каждый раз при включении в очередь новый элемент помещается в позицию, определяемую указателем конца очереди, а затем указатель смещается на следующую свободную позицию. Удаление элемента из очереди означает извлечение элемента, на который указывает указатель начала очереди, а затем этот указатель изменяется так, чтобы он указывал на элемент, следующий за удаленным. Такой способ доступа к элементам очереди приводит к тому, что очередь «ползет» по линейной памяти и при активном ее использовании хвост может дотянуться до конца памяти. Одно из решений состоит в перемещении элементов очереди вперед по мере удаления впередистоящих элементов (как в обычной очереди в магазине люди продвигаются вперед), но это приводит к массовым операциям с элементами списка..

Наиболее распространенное решение – выделить очереди отдельный блок памяти, в котором элементы очереди будут перемещаться в циклическом порядке, т.е. «хвост», достигнув конца блока перемещается в его начало. Таким образом, вместо того, чтобы «бродить» по всей памяти, очередь преследует себя по кругу внутри выделенного ей блока памяти:

действительное расположение концептуальное представление

элементов очереди в памяти очереди, в котором ее последняя

ячейка примыкает к первой

Различие между концептуальной структурой и реальной преодолевается с помощью специального программного обеспечения. Это означает, что помимо выделения набора ячеек памяти под хранение данных, реализация очереди должна включать набор процедур для включения и исключения элементов очереди, а также для определения того, является ли очередь пустой или заполненной до предела.

Если разрешить добавлять элементы в оба конца очереди и забирать их также из обоих концов, то такая структура данных называется " дек ", от англ. Double Ended Queue (queue [kju:] - очередь), т.е. очередь с двумя концами. Дек применяется значительно реже, чем очередь.

Относительно просто реализовать дек с помощью двусвязного циклического списка. В двусвязном циклическом списке в каждом элементе хранятся указатели на следующий и предыдущий элементы. Голова списка хранит только ссылки (указатели) на первый и последний элементы списка, но не хранит данных. Так как список зациклен в кольцо, то следующим за головой списка будет его первый элемент, а предыдущим – последний элемент. Когда список пуст, голова списка зациклена сама на себя.

Использование очереди в программировании почти соответствует ее роли в обычной жизни. Очередь обычно связана с обслуживанием запросов, в случаях, когда они не могут быть выполнены мгновенно. Очередь поддерживает также порядок обслуживания запросов.

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

Дата добавления: 2015-10-30