Файл: СПОСОБЫ ПРЕДОСТАВЛЕНИЯ ДАННЫХ В ИНФОРМАЦИОННЫХ СИСТЕМАХ.pdf

В СОД широкого назначения обычно используется обработка чисел с плавающей точкой, не требующая масштабирования. Представление числа с плавающей точкой в общем случае имеет вид x = sp q, где sp – характеристика числа х; p – порядок; s – основание характеристики; q – мантисса числа х. Мантисса (дробь со знаком) и порядок (целое число со знаком) представляются в системе счисления с основанием, равным s в соответствующей двоично-кодированной форме. Знак числа совпадает со знаком мантиссы. Порядок p, который может быть положительным или отрицательным целым числом, – определяет положение точки в числе х. Пример представления двоичных чисел с плавающей точкой при использовании дополнительного кода приведен в таблице 2 (см.приложение 2)^[24]

При фиксированном числе разрядов мантиссы любая величина представляется с наибольшей возможной точностью нормализованным числом. Число x = sp называется нормализованным, если мантисса q удовлетворяет условию 1 ! V q V 1 ~s, Т.е. старший разряд нормализованной мантиссы в s-ричной системе всегда отличен от нуля. В процессе вычислений могут получаться ненормализованные числа. В этом случае ЭВМ, если это предписано программой, автоматически их нормализует. При обработке чисел с плавающей точкой диапазон их представления зависит от основания системы счисления и числа разрядов, выделенных для представления порядка. Точность вычислений определяется числом разрядов мантиссы. Для хранения целых чисел в десятичной форме каждая десятичная цифра кодируется четырехразрядным двоичным числом. На один байт приходится по две десятичные цифры. Такая форма представления называется упакованной десятичной формой. Под знак числа отводится крайний левый полубайт. Форма представления чисел может быть различной для разных типов ЭВМ. ^[25]

К символьным данным относятся буквы латинского и кириллического алфавита, знаки препинания, десятичные цифры, знаки операций, специальные, управляющие и другие символы. Различные типы ЭВМ работают с различными наборами символов и используют различные символьные коды. Наибольшее распространение получило представление символьной информации с помощью байтов. Один байт позволяет кодировать 256 различных символов. В программах символьной обработки как тип данных чаще используется не отдельный символ, а строка символов , образуемая из отдельных байт-символов с помощью операции конкатенации (сцепления). Над строками возможны определенные операции: конкатенации, отыскания и замены подстроки, проверки тождественности строк и определения длины строки. 46 Символы, образующие строку, запоминаются в последовательно расположенных байтах памяти. Размер строки может быть фиксированным и переменным. Память для представления строки переменной длины выделяется исходя из максимального размера строки, объявленного в программе. Логические данные принимают только два значения: «истинно» и «ложно». Представление логических данных различно для разных языков программирования. Над логическими данными выполняются операции булевой алгебры. В машинной памяти логические данные также представляются поразному, в зависимости от типа транслятора и типа ЭВМ. Для хранения одного логического данного достаточно отвести один бит, значение которого равно 1, если «истинно», и равно 0, если «ложно». Однако в большинстве ЭВМ структуризация памяти обычно не предусматривает доступа к одному биту. В этом случае для одного логического данного используется один байт или машинное слово – как элементарная машинная единица информации. Указатель (связка, ссылка) – это элемент данных фиксированного размера. Он используется для реализации связанного представления данных в машинной памяти. ^[26]

Указатель может быть абсолютным или относительным адресом данного. Относительный указатель содержит значение смещения в области памяти относительно некоторого базового адреса в этой области памяти. Поскольку указатель выступает в качестве адреса данного, то он и хранится в памяти ЭВМ как адрес в виде машинного слова или полуслова. Линейные структуры данных и их хранение Массив. Массив – это линейная структура данных фиксированного размера, реализуемая с использованием последовательного представления данных. Не следует путать два различных понятия: массива как типа структуры данных и информационного массива как совокупности данных, обрабатываемых в СОД. Каждый элемент массива идентифицируется одним или несколькими индексами. Индекс − это целое число, значение которого определяет позицию соответствующего элемента в массиве и используется для осуществления доступа к этому элементу. Отдельные элементы массива могут изменяться, но общее число элементов массива всегда остается неизменным, т.е. для массивов нет операций удаления и добавления. Различают одномерные и многомерные массивы. Одномерный массив называется вектором. Вектор А = {a1, a2, . . . , an} − это последовательность элементов (записей), размещенных в смежных ячейках памяти. Единственный индекс обозначает номер позиции элемента в последовательности. Адрес L0 первого байта, выделенного для первого элемента вектора, называется адресом базы вектора. Вектор в целом определяется адресом базы, размером элементов и их числом или размером элементов и диапазоном изменения индекса (см. приложение 3)

2.2. Последовательное и связанное представление данных

По способу представления данных в памяти СОД различают структуры хранения с последовательным и связанным представлением данных. При последовательном представлении данные в памяти размещаются в соседних последовательно расположенных ячейках. При этом физический порядок следования записей полностью соответствует логическому порядку. Совокупность записей, размещенных в последовательно расположенных ячейках памяти, называется последовательным списком. Для хранения информационного массива в виде последовательного списка в памяти выделяется блок свободных ячеек под максимальный размер массива. Так, массив записей, имеющий логический порядок Запись В Запись А Запись F Запись C . . . . . . . . Запись N разместится в памяти ЭВМ так, как показано на рис. 3.4. При появлении новых записей они будут размещаться в конце блока на свободном участке памяти. Если число новых записей окажется больше чем 37 свободный объем памяти под их размещение, то разместить их не удастся, если меньше – память окажется недоиспользованной. В процессе ведения информационного массива записи добавляются и удаляются. Новые записи пристраиваются в конец списка, удаленные записи образуют свободные участки памяти. ^[27]

Многие приложения СОД требуют непрерывного обновления и корректировки записей, что приводит к большим потерям времени на частую перезапись и – к неэффективному использованию памяти. В таких приложениях последовательное представление неприемлемо и заменяется связанным представлением. При связанном представлении в каждой записи предусматривается дополнительное поле, в котором размещается указатель (ссылка). Физический порядок следования записей в этом случае может не соответствовать логическому порядку. В памяти записи располагаются в любых свободных ячейках и связываются между собой указателями, показывающими место расположения записи, логически следующей за данной записью. Указатель можно интерпретировать как адрес ячейки памяти, в которой хранится следующая запись. Структуры хранения, основанные на связанном представлении данных, называют связанными списками. Если каждая запись содержит лишь один указатель, то список односвязный, при большем числе указателей – список многосвязный. Пусть структура данных имеет следующую логическую последовательность записей: Запись А Запись В Запись С Запись F Записи размещены в ячейках с адресами 01, 05, 03, 10. В поле указателя каждой записи размещается адрес связи (АС), определяющий адрес ячейки с логически следующей записью. Структура хранения такого массива представлена на рис. 3.7. Порядок чтения записей указан стрелками. Связанное представление обеспечивает гибкость структуры хранения.^[28] Ведение списка не требует перезаписи элементов массива, а производится с помощью такой замены указателей, чтобы логический порядок следования записей не нарушался. Однако для размещения указателей требуется дополнительный объем памяти. Головная ячейка.

Рассмотрим процедуру изменения указателей в процессе ведения односвязного списка. При выполнении операции удаления исключаемая запись удаляется из массива вместе со всеми своими полями, в том числе и полем указателя. Для того чтобы цепочка указателей не разрывалась, перед исключением записи в логически предшествующей записи производится замена старого указателя на тот, который был в исключаемой записи. Например, из рассмотренного списка (см. рис. 3.7) исключим запись С, хранящуюся в ячейке с адресом 03 и имеющую адрес связи АС10. Для этого значение указателя предшествующей записи (запись В) изменим на АС10. Теперь доступ к записи С стал невозможен и эта запись оказалась исключенной из списка. Процедуру удаления записи С иллюстрирует рис. 3.8. Существует и другой способ удаления записей, при котором исключаемая запись помечается специальным символом исключения. Такая запись логически удаляется, а физически остается. При этом остается и доступ к полю указателя, цепочка записей не разрывается и замены указателей не требуется.^[29]

Для включения в односвязный список новой записи из списка свободных ячеек берется первая ячейка, в ее информационное поле заносится новая запись, а в поле указателя заносится адрес хранения логически следующей записи. Адрес ячейки с новой записью становится указателем логически предшествующей записи. Для размещения новых записей используются любые свободные ячейки, поэтому список может расти неограниченно в пределах всего пространства памяти. На рис. 3.9 показана процедура включения в связанный список новой записи D, которая должна логически следовать за записью С. Запись D размещается в ячейке с адресом 15. После замены указателей устанавливается порядок следования ячеек памяти 01, 05, 03, 15, 10, обеспечивающий требуемую логическую последовательность записей: А, В, С, D, F Односвязный список может быть организован в виде замкнутого кольца. При этом указателем последней записи будет адрес первой записи. Такой список еще называют циклическим. Просмотр циклического списка можно начинать с любой ячейки. Условием окончания просмотра может быть либо совпадение числа просмотренных записей с общим числом записей в списке, либо совпадение указателя с адресом первой прочитанной ячейки.

3.2. Уровни предоставления данных

Уровни представления данных. СОД хранят и обрабатывают информацию об объектах реального мира. Некоторую совокупность информации, описывающую конкретный объект, называют логической записью или просто записью. Совокупность записей, охватывающих множество объектов определенного класса, называют информационным массивом. Служба Служащий Фирма а С1 С2 С5 С3 С1 Ф3 Ф1 Ф2 б 30 В реальном мире между объектами существуют определенные отношения и взаимосвязи, имеющие различную степень сложности. В процессе разработки в СОД эти отношения выявляются и отображаются путем структуризации записей и информационных массивов. Организация информационного массива, обеспечивающая определенные связи и отношения между данными, называется структурой данных. Любые манипуляции над данными в процессе их обработки на ЭВМ не должны разрушать структуру данных, поэтому ее необходимо все время поддерживать. Существует 3 уровня представления данных: логический уровень, уровень хранения и физический уровень.^[30]

На логическом уровне работают с логическими структурами данных, отражающими реальные отношения между объектами и их характеристиками. При разработке логических структур данных учитывается также информационная потребность пользователей системы и характер задач, для решения которых предназначена СОД. Единицей информации на этом уровне является логическая запись. Каждый объект, описываемый соответствующей логической записью, характеризуется определенными признаками, являющимися атрибутами записи. На логическом уровне устанавливается перечень признаков, полностью характеризующий описываемый класс объектов. Совокупность признаков и их взаимосвязь определяют внутреннюю структуру логической записи. Логическая структура данных должна исчерпывающе характеризовать объекты, сведения о которых обрабатываются СОД, адекватно отражать реальные отношения между объектами и их характеристиками, обеспечивать удовлетворение информационных потребностей пользователей системы и решение задач приложений. На логическом уровне представления данных не учитывается техническое и математическое обеспечение системы (тип ЭВМ, типы памяти, язык программирования, операционная система). На уровне хранения оперируют со структурами хранения − представлениями логической структуры данных в памяти ЭВМ. Структура хранения должна полностью отображать логическую структуру данных и поддерживать Уровни представления данных Логический уровень Уровень хранения Физический уровень 31 ее в процессе функционирования СОД. Единицей информации на этом уровне также является логическая запись. При разработке или выборе структуры хранения должны учитываться особенности организации памяти ЭВМ. При этом устанавливается тип и формат данных, определяется способ поддержания логической структуры.^[31] Известны различные способы представления данных в оперативной памяти и на внешних носителях, причем одна и та же логическая структура данных может быть реализована в памяти ЭВМ различными структурами хранения. Каждая структура хранения предоставляет определенный способ доступа к данным и определенные возможности манипулирования данными. Структура хранения характеризуется объемом памяти, необходимым для размещения данных. От выбора структуры хранения непосредственно зависит эффективность обработки данных. Правильно выбранная структура хранения обеспечивает минимальный расход машинной памяти, быстрый поиск нужных данных, возможность добавления новых и удаления устаревших записей без разрушения логической структуры, а также возможность корректировки записей. Поддержание структуры хранения осуществляется программными средствами. Для реализации структуры хранения требуются определенные языки программирования, возможности которых следует учитывать при разработке или выборе структуры хранения. На физическом уровне представления данных оперируют с физическими структурами данных. На этом уровне решается задача реализации структуры хранения непосредственно в конкретной памяти конкретной ЭВМ. ^[32]

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

Соблюдение принципа независимости данных позволяет использовать особые виды данных: виртуальные и прозрачные. Виртуальные данные существуют только на логическом уровне. Для программиста это как бы реально существующие данные, которыми он оперирует в программах. Каждый раз при обращении к этим данным операционная система определенным образом их генерирует на основании других данных, физически существующих в системе. Объявление некоторых данных виртуальными позволяет экономить машинную память. Структуры хранения логическая независимость изменения Логические структуры данных Прикладные программы логическая независимость изменения Прикладные программы Логические структуры данных 33 Прозрачные данные представляются несуществующими на логическом уровне. Это позволяет скрыть от программиста или от пользователя многие сложные механизмы, используемые при преобразовании логических структур данных в физические, и упростить прикладные программы. Структура данных. СОД имеют многоуровневую структуру данных, которая образуется из отдельных элементов, связанных определенными отношениями. Элементы каждого уровня имеют определенное название. Формирование элементов более высокого уровня осуществляется из элементов нижнего уровня в соответствии с определенными правилами.^[33]