Структура данных

Кодирование символьной информации осуществляется на основе двоичных кодов, первоначально для нужд телеграфной  связи. Этот двоичный код называется ASCII (American Standard Code for Information Interchange). Оба эти кода совпадают по первым 128 позициям. Это фактически есть неизменяемая часть любого кода для ЭВМ.

Коды от 128 до 255 - для национальных алфавитов и специальных символов. Поскольку между символьными  величинами и их двоичными кодами существует взаимнооднозначное соответствие, то над символьными величинами определены операции сравнения.

В настоящее время широко распространен BCD - Binary Coded Decimal - каждая десятичная цифра записывается четырехбитовым двоичным эквивалентом.

Теоретической базой обработки  логической информации является Булева алгебра логики. Эта двузначная алгебра  была разработана для формального  описания логических построений задолго  до появления первых ЭВМ. Элементы этой алгебры могут иметь одно из двух значений: истина и ложь. Распространенной формой задания логических функций  являются таблицы истинности. Базовыми функциями булевой алгебры являются отрицание, конъюнкция, дизъюнкция. Для  упрощения логических функций используются тождества алгебры логики.

В АЛУ ЭВМ имеется набор элементарных логических устройств, соответствующих основным логическим операциям. На входы логических устройств подаются двоичные коды, которые рассматриваются как логические переменные, а выход зависит от таблицы истинности. Логическому значению "истина" соответствует 1, а значению "ложь" - 0.

Для обработки текстовой  информации на компьютере необходимо представить ее в двоичной знаковой системе. Для кодирования каждого  знака требуется количество информации, равное 8 битам, т. е. длина двоичного  кода знака составляет восемь двоичных знаков. Каждому знаку необходимо поставить в соответствие уникальный двоичный код из интервала от 00000000 до 11111111 (в десятичном коде от 0 до 255).

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

 

Формы представления чисел в  ЭВМ

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

• естественная форма или форма с фиксированной запятой (точкой);
• нормальная форма или форма с плавающей запятой (точкой);

Пример:

(естественная форма) 452,34 = 452340*10^-3 = 0,0045234*10⁵ = 0,45234*10³(нормальная форма)

Всякое десятичное число, прежде чем  оно попадает в память компьютера, преобразуется по схеме:

X₁₀ → X₂ = M₁ × [10₂]^r

После этого осуществляется ещё  одна важная процедура:

• мантисса с её знаком заменяется кодом мантиссы с её знаком;
• порядок числа с его знаком заменяется кодом порядка с его знаком.

Указанные коды двоичных чисел - это  образы чисел, которые и воспринимают вычислительные устройства. Каждому  двоичному числу можно поставить  в соответствие несколько видов  кодов.

Существуют следующие коды двоичных чисел:

• Прямой код;
• Обратный код;
• Дополнительный код.

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

 

Содержание  [убрать] 1 Естественная форма 2 Нормальная форма 3 Прямой код 4 Обратный код 5 Дополнительный код 6 Литература

Естественная форма

В форме с фиксированной запятой  в разрядной сетке выделяется строго определенное число разрядов для целой и для дробной  частей числа. Левый (старший) разряд хранит признак знака (0 – "+", 1 – "-") и для записи числа не используется.

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

A = [A] · K^А,

где А – произвольное число, [A] – машинное изображение числа в разрядной сетке, K^А - масштабный коэффициент.

Естественная форма числа в  неявном, условном виде реализуется  формулой:

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

С фиксированной запятой числа  изображаются в виде последовательности цифр с постоянным для всех чисел  положением запятой, отделяющей целую  часть от дробной(например, 32,54; 0,0036; –108,2). Форма представления чисел с фиксированной запятой упрощает аппаратную реализацию ЭВМ, уменьшает время выполнения машинных операций, однако при решении задач на машине необходимо постоянно следить за тем, чтобы все исходные данные, промежуточные и окончательные результаты находились в допустимом диапазоне представления. Если этого не соблюдать, то возможно переполнение разрядной сетки, и результат вычислений будет неверным. От этих недостатков в значительной степени свободны ЭВМ, использующие форму представления чисел с плавающей точкой, или нормальную форму. В современных компьютерах форма представления чисел с фиксированной запятой используется только для целых чисел.

Нормальная форма

С плавающей запятой (ПЛЗ) числа  изображаются в виде:

X = ± M×P ^±r,

где M - мантисса числа (правильная дробь  в пределах 0,1 ≤ M < 1), r - порядок числа (целое), P - основание системы счисления. Например, приведенные выше числа с фиксированной запятой можно преобразовать в числа с плавающей запятой так: 0,3254×10², 0,36×10^-2, –0,1082×10³.

Нормализованная экспоненциальная запись числа - это запись вида a= m*P^q, где q - целое число (положительное, отрицательное или ноль), а m - P-ичная дробь, у которой целая часть состоит из одной цифры. При этом m - мантиссa числа, q - порядк числа.

Tо есть нормальная форма реализуется формулой: 

Нормальная форма представления  имеет огромный диапазон чисел и  является основной в современных  ЭВМ.

При представлении чисел с плавающей  запятой часть разрядов ячейки отводится  для записи порядка числа, остальные  разряды - для записи мантиссы. По одному разряду в каждой группе отводится  для изображения знака порядка  и знака мантиссы. Для того, чтобы не хранить знак порядка, используется так называемый смещённый порядок, который рассчитывается по формуле 2^(a-1) + ИП, где a - количество разрядов, отводимых под порядок, ИП - истинный порядок.

В конкретной ЭВМ диапазон представления  чисел с плавающей запятой  зависит от основания системы  и числа разрядов для представления  порядка. При этом у одинаковых по длине форматов чисел с плавающей запятой с увеличением основания системы счисления существенно расширяется диапазон представляемых чисел. Точность вычислений при использовании формата с плавающей запятой определяется числом разрядов мантиссы. Она увеличивается с увеличением числа разрядов.

Алгоритм представления  числа с плавающей запятой:

1. перевести число из p-ичной системы счисления в двоичную;
2. представить двоичное число в нормализованной экспоненциальной форме;
3. рассчитать смещённый порядок числа;
4. разместить знак, порядок и мантиссу в соответствующие разряды сетки.

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

Прямой код

Представление числа в привычной  форме "знак"-"величина", при которой старший разряд ячейки отводится под знак, а остальные - под запись числа в двоичной системе, называется прямым кодом двоичного числа. Например, прямой код двоичных чисел 1001 и -1001 для 8-разрядной ячейки равен 00001001 и 10001001 соответственно.

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

Например,

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

Прямой код  двоичного числа(а это либо мантисса, либо порядок) образуется по такому алгоритму:

1. Определить данное двоичное число - оно либо целое (порядок), либо правильная дробь (мантисса).
2. Если это дробь, то цифры после запятой можно рассматривать как целое число.
3. Если это целое и положительное двоичное число, то вместе с добавлением 0 в старший разряд число превращается в код. Для отрицательного двоичного числа перед ним ставится единица.

Например, 

Обратный код

Обратный код положительного двоичного  числа совпадает с прямым кодом.Для отрицательного числа все цифры числа заменяются на противоположные (1 на 0, 0 на 1), а в знаковый разряд заносится единица.

Например, 

Дополнительный код

Дополнительный код положительного числа равен прямому коду этого  числа. Дополнительный код отрицательного числа m равен 2^k - |m|, где k - количество разрядов в ячейке.Также дополнительный код отрицательного числа образуется путём прибавления 1 к обратному коду.

При представлении целых чисел  со знаком старший (левый) разряд отводится  под знак числа, и под собственно число остаётся на один разряд меньше.

Алгоритм получения  дополнительного кода отрицательного числа:

1. модуль отрицательного числа представить прямым кодом в k двоичных разрядах;
2. значение всех бит инвертировать:все нули заменить на единицы, а единицы на нули(таким образом, #получается k-разрядный обратный код исходного числа);
3. к полученному обратному коду прибавить единицу.

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

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

Например, 

 

ЧТО ТАКОЕ БАЗЫ ДАННЫХ?

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

Реляционные базы данных