Связанное представление

Cтраница 2

Для очередей используются как после-довательное, так и связанное представления. Как и в случае стеков последовательное представление требует резервирования блока памяти, внутри которого очередь может расти и сокращаться. Очередь растет циклически внутризарезерви рованного блока; когда указатель конца очереди достигает конца блока, он перебрасывается на начало блока. [16]

Злементы стека могут занимать произвольные позиции в памяти) 3.12. Связанное представление стека в памяти. [17]

Время, расходуемое на доступ к произвольному элементу А [ /, / г ], остается в разумных пределах, если в каждой строке или столбце встречается совсем немного элементов; кроме того, поскольку в большинстве матричных алгоритмов используется не доступ к произвольным элементам, а производится последовательное прохождение матрицы, то связанное представление приводит к незначительной потере скорости работы. [18]

Матрица называется разреженной, если большинство ее элементов нулевые. Постройте связанное представление для разреженной матрицы, в которое входят только ненулевые элементы. [19]

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

Некоторые возможные структуры памяти для представления целочек. [21]

Чаще всего длина цепочки хранится в двоичном виде как первая литера в цепочке, а далее в цепочке используется обычное аппаратное представление. В случае цепочек неограниченной длины применяется также связанное представление. [22]

Довольно легко перейти от линейных массивов переменного размера к многомерным структурам, если допустить, что элемент массива может служить указателем на другой массив. А это обычно допускается, когда для линейных массивов используется связанное представление. [23]

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

Можно использовать один зарезервированный блок для по-следовательного представления двух стеков, если заставить их расти навстречу друг другу с противоположных концов блока. Конечно, таким способом можно представить большее число стеков, отводя по одному блоку памяти на каждую пару стеков, однако количество напрасно резервируемой памяти и трудности обработки ситуации, когда один стек переполняется, обычно приводят к тому, что выбирается связанное представление. [25]

Здесь каждый элемент связанного списка состоит из двух полей. В поле DATA размещен сам элемент последовательности, а в поле NEXT - указатель на следующий за ним элемент. Связанное представление последовательностей облегчает операции включения и удаления элементов из списка. [26]

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

Существует два способа построения схемы разрешения коллизий. Первый базируется на последовательном распределении списков и называется методом открытой адресации. Второй базируется на связанном представлении списков и называется методом цепочек. [28]

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

Ледгард [1971] в своем обзоре проблем конструирования языка рассматривает и вопросы структурирования данных. Империо [1969] принадлежит обзор по структурам данных, базирующихся на связанные представления, при этом особое внимание уделяется структуре памяти. Галлер и Перлис [1970] в ходе более общего исследования, посвященного понятиям языков программирования, затрагивают и структуры данных. [30]

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