Файл: Способы представления данных в информационных системах.pdf

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

Пусть структура данных отображает следующую логическую последовательность записей: Зап. А, Зап. В, Зап. С, Зап. F. Записи размещены в ячейках памяти с адресами 01, 03, 05, 10. В поле указателя каждой за­писи размещается адрес связи (АС), определяющий адрес ячейки с логи­чески следующей записью. Структура хранения массива представлена на рис. 1.8,a.

На этом рисунке стрелками показан порядок чтения записей.



 

Рис. 1.8. Структура хранения массива

Одна из ячеек – головная – содержит указатель на ячейку с первой записью списка. В соответствии с указателями первым будет прочитано содержимое ячейки 01 (Зап. А), затем содержимое ячеек 05 (Зап. В), 03 (Зап. С), 10 (Зап. F). Символ АС О, помещенный в поле указателя по­следней записи списка, означает конец списка. Вместо символа АС О может быть использован любой другой элемент данных, который не воспримется системой как указатель.

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

Рассмотрим процедуру смены указателей в процессе ведения односвязного списка.

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

Исключим из списка (рис. 1.8,а) запись С, хранящуюся в ячейке с адресом 03 и имеющую адрес связи АС10. Для этого значение указателя предшествующей записи (Зап. В) изменим на АС10. Теперь доступ к записи С стал невозможен и запись С оказалась исключенной из списка (рис. 1.8,б). Освободившаяся ячейка с помощью указателей включается в связанный список свободных ячеек.

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

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

На рис. 1.8, в изображен связанный список с вновь включенной за­писью D, логически следующей за записью С. Запись D размещается в ячейке с адресом 15. После замены указателей устанавливается порядок чтения ячеек памяти 01, 05, 03, 15, 10, обеспечивающий логическую последовательность записей: Зап. А, Зап. В, Зап. С, Зап.D Зап. F.

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

Рис. 1.9. Циклический список

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

Рис. 1.10. Двунаправленный список:

а) исходный список;

б) включение в список новой записи.

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

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

Для реализации связанного представления данных язык программирования должен иметь определенные средства, а именно, иметь данные типа «указатель». При работе с языками программирования, которые не имеют данных «указателя», связанное представление моделируется с использованием структуры массива.

Рис. 1.11. Моделирование связного списка с помощью структуры массива

Пусть структура данных определена как массив М(I). Для определения порядка чтения элементов массива, не совпадающего с физичес­ким порядком их следова­ния, можно организовать вспомогательный вектор указателей N(J), элементы которого — целые числа - определяют порядковые номера (индексы) записей основного массива. На рис. 1.11 изображены два одномерных массива: массив указателей N(J) и основной массив запи­сей М(I), а также моделируемый список. Процедура чтения основного массива организуется с учетом того, что I = N(J). Таким образом, вектор N(J) при изменении значения J от 1 до 4 задает следующий порядок чтения записей основного массива: Зап. А, Зап. В, Зап. С, Зап. D. Можно использовать другой способ моделирования связанного пред­ставления данных с помощью структуры массива. При этом каждый эле­мент массива должен состоять из нескольких (минимум двух) полей. Последнее поле отводится под указатель. Значение этого поля (целое число) представляет собой индекс или номер элемента массива, являю­щегося следующим элементом связанного списка.

1.5 Элементарные данные

Элементарные данные (числа, символы, логические данные, ссылки) имеют конкретное машинное представление и занимают четко определенные единицы компьютерной памяти. Это позволяет рассчитать объем памяти, необходимый для размещения информационных массивов.

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

Целые числа могут быть представлены в двоичном и десятичном виде. При хранении целых чисел в двоичной форме одно машинное слово выделяется для одного числа. Крайний левый бит размещается под знаком. Плюс кодируется 0, минус - 1. Позиции под номером перемещаются справа налево, остальные позиции, не занятые номером, заполняются нулями. Отрицательные числа обычно представлены в дополнительном коде.

При хранении целых чисел в десятичной форме каждая десятичная цифра числа кодируется четырехзначным двоичным кодом, то есть две десятичные цифры хранятся в байте. Эта форма хранения называется упакованной десятичной формой. Самый правый клев зарезервирован для знака, плюс имеет код 1100, минус - 1101. Например, число +9613, представленное в упакованном десятичном виде, записывается следующим образом: 1001 0110 0001 0011 1100.

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

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


 

Рис. 1.13. Машинное представление чисел с плавающей точкой

Символьные данные включают буквы латинского и кириллического алфавита, строчные и заглавные буквы, цифры, знаки операций и специальные символы, управляющие символы. Латинские и русские буквы, цифры, знаки операций и специальные символы используются для выполнения задач обработки данных, формирования текста, написания программ. Управляющие символы используются для структурирования данных, передачи информации, организации файлов.

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

Логические данные принимают только два значения: «истина» или «ложь». Над логическими данными выполняются различные операции булевой алгебры: OR, AND, N0T - инверсия и т. д.

Представление логических значений в машинной памяти зависит от переводчика, обрабатывающего программу, и от типа компьютера. Для хранения логических данных можно использовать один бит, значение которого равно 1, если истина, и 0, если ложно, но большинство машин не имеют доступа к одному биту памяти. В другом способе хранения машинное слово выделяется для представления логического элемента. В этом случае значения -TRUE- и -FALSE- представлены восемью одиночными и восемью нулевыми битами, соответственно, в крайнем левом байте машинного слова. Этот способ представления логических значений неэффективно использует компьютерную память. Однако это обеспечивает быстрый доступ к логической информации, поскольку при выполнении машинных инструкций машинное слово является основной единицей обмена между OP и процессором.

1 байт может использоваться для представления логического значения. Значение «истина» кодируется последовательностью битов, состоящей из нулей и одной единицы в крайнем правом бите. Значение «ложь» кодируется последовательностью битов, состоящей из нулей. Такая презентация наиболее эффективна, поскольку обеспечивает быстрый доступ и экономно использует машинную память.

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

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