Информационное обеспечение систем управления

       

Списковые структуры


В системах обработки данных в качестве данных выступают описания (представления) фактов и понятий рассматриваемой предметной области на точном и формализованном входном языке системы - языке описания данных [17]. С помощью входного языка при описании фактов и понятий ПО между элементами данных конструируются логические структурные отношения. В качестве логических структур (см. гл.2) используют либо таблицы, представляющие собой двумерный или re-мерный массив данных, либо древовидные иерархически структуры, либо сетевые структуры, представляющие собой сложную многосвязную структуру с большим количеством взаимных соединений и т.п. Чтобы правильно использовать вычислительную машину, необходимо хорошо представлять себе структурные отношения между данными, знать способы представления таких структур в памяти машины и методы работы с ними. Структура данных и представление этой структуры в памяти ЭВМ – два важных, но Различных между собой понятия [17]. Так, например, некоторая логическая структура данных типа «дерево» может быть представлена в памяти ЭВМ несколькими различными способами.

Таким образом, любое представление структуры данных в памяти ЭВМ должно включать в себя как сами данные, так и задаваемые взаимосвязи, которые и определяют логическое структурирование.

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

Наиболее простой формой хранения данных в памяти ЭВМ является одномерный линейный список.


Линейный список – это множество n>0 объектов (узлов) Х[1], Х[2], ..., Х[п], структурные свойства которого связаны только с линейным (одномерным) относительным расположением узлов. Если п>0, то Х[1] является первым узлом; для 1<i<n узел Х[i-1] предшествует узлу X[i], а узел X[i+l] следует за ним, Х[п] является последним узлом, т.е. линейный список реализует структуру, которую можно определить как линейное упорядочение элементов данных [17].

Линейный список X рассматривают как последовательность Х[1], Х[2], ..., Х[i], ..., Х[п], компоненты которой идентифицированы порядковым номером, указывающим их относительное расположение в X.

Одномерный линейный список, используемый для хранения данных в памяти машины, называют еще вектором данных или физической структурой хранения данных. Использование линейного списка в качестве физической структуры хранения данных определяется свойствами памяти вычислительной машины. Так, оперативная память ЭВМ представляет вектор, в котором байты упорядочены по возрастанию их адресов от 0 до наивысшего, т.е. проидентифицирова-ны адресом.

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

При реализации адресной функции используют два основных метода [17]:

– последовательное распределение памяти;

–       в связанное распределение памяти.


Содержание раздела