Представление структур в памяти ЭВМ

Как же реально представить в памяти структуру данных того или иного типа? Обычно для однородных массивов по­стоянной длины используют последовательное представление. В этом случае логически смежные элементы массива разме­щаются в физически смежных ячейках памяти. Последо­вательное представление нетрудно распространить и на массивы более высокой размерности, располагая в последова­тельных ячейках памяти элементы массива в лексикографи­ческом порядке индексов (i₁,i₂,..., i_k). Например, если в случае двумерного массива через i₁ обозначим номер строки, а через i₂—номер столбца, то массив окажется расположен­ным в памяти по строкам.

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

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

Если для представления стеков и очередей использовать массивы с малым числом элементов, то очень велика вероят­ность их переполнения. Увеличение длины массивов не только ухудшает использование памяти, но и не гарантирует от пе­реполнения. Если использовать массивы такой длины, чтобы исключить возможность их переполнения, то часть памяти, действительно занятая данными, окажется совсем небольшой. Еще большим недостатком является то, что обработка будет прекращена, как только переполнится хотя бы один массив, отведенный под стек, несмотря на наличие достаточного объема свободной памяти в других массивах. Естественно, возникают вопросы: нельзя ли всю незанятую память, отве­денную для представления массивов переменной длины, ис­пользовать как общую; как это скажется на эффективности использования памяти?

Рис. 2.3. Представление кольца и очереди с использованием указателей (представление в связанной памяти):

а — кольцо; б — исключение из кольца (включение в кольцо). При исклю­чении сплошная стрелка заменяется на пунктирную, а при включении — пунктирная на сплошную; в — двусторонняя очередь

Эту проблему можно решить путем придания памяти определенной структуры, связав между собой отдельные бло­ки (узлы) памяти с помощью указателей. Рис. 2.3а иллю­стрирует идею связанного представления на примере кольца. Прямоугольниками на рисунке показаны узлы памяти. Каж­дый узел состоит из двух полей. Одно поле содержит эле­мент или более сложную структуру данных, а другое — ука­затель на следующий узел. Стрелки на рисунке соответствуют значениям указателей. Если последовательность представ­лена в связанной памяти, то операции включения и исклю­чения элементов в последовательность выполняются так, как показано на рис. 2.3.б. Обе операции используют список свободной памяти—при включении память занимается, а при исключении возвращается в этот список. В любом случае происходит изменение трех указателей. При этом из схемы на рис. 2.3.б следует, что при заданном указателе на узел, содер­жащий данное S, операции включения и исключения возможны только «справа от S» и невозможны «слева от S». Операция «исключить S» также невозможна. Одним из способов, позво­ляющих преодолеть эти ограничения, является использование в каждом узле двух указателей, что будет рассмотрено ниже. В этом случае станет возможным производить включение и исключение справа и слева от S. Возможен и другой техни­чески простой прием. При необходимости «исключить узел S» перепишем в него данные узла, находящегося справа от S (данное Т), а затем исключим узел справа (фактически бу­дет исключен узел, следующий за S, — узел, первоначально содержавший данное Т). Аналогично может быть выполнена и операция «включить слева от S». Для этого вначале вклю­чим новый узел справа от S и перепишем в него данное S, затем запишем новое данное в узел, который прежде зани­мало данное S, и, наконец, передвинем указатель доступа к структуре на узел, который теперь содержит данное S.

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

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

Основной смысл применения указателей заключается не столько в повышении эффективности обработки, сколько в возможности представления более сложных структур. Ис­пользование указателей позволяет связывать между собой самые разнообразные данные, что является основой представ­ления различных самых сложных структур, механизмов, яв­лений. Среди них особое место занимают сравнительно про­стые, но очень важные древовидные структуры. Например, если для представления узлов бинарного дерева использовать записи с двумя указателями, как показано на рис. 2.4, то можно производить обход дерева начиная от корня в направлении концевых узлов. Операции исключения или включения листа (концевого узла) выполняются очень просто—изменением всего трех указателей.

В математике одним из базовых понятий является множе­ство. В области обработки данных операции над множествами часто также весьма желательны. Однако представление в памяти множества, не имеющего структуры, представляет зна­чительную проблему, и обычно стараются обходиться без них. Пусть, например, в трехмерном пространстве задано ко­нечное множество, состоящее из n точек. Как представить это множество в памяти, чтобы иметь возможность выполнять соответствующие операции? Если число элементов множества постоянно и все элементы заранее известны — перенумеруем их числами от 1 до n. Сами элементы множества—коорди­наты точек (Хi, Yi, Zi) (i= 1,2,..., п)— будем хранить в мат­рице из (nхЗ) элементов. Тогда для представления любого подмножества этого множества можно воспользоваться од­номерным массивом из п битов (p₁, р₂,..., рn ), присваивая P i (i-му биту) значение 1, если точка с номером i принадле­жит подмножеству, и 0, если не принадлежит. Такой логиче­ский массив обычно называют битовой картой. Операции над множествами в таком случае сводятся к логическим опера­циям над соответствующими логическими массивами.

Рис. 2.4. Представление бинарного дерева с использованием указателей.

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

Дата добавления: 2014-12-16