11340

Кодирование данных

Лекция

Информатика, кибернетика и программирование

Тема 2: Кодирование данных 2.1. Носители данных Данные составляющая часть информации. Они представляют собой зарегистрированные сигналы. При этом физический метод регистрации может быть любым: перемещение физических тел изменение их формы изменение электрических и...

Русский

2013-04-07

335 KB

29 чел.

Тема 2: «Кодирование данных»

2.1. Носители данных

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

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

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

- динамическим диапазоном (отношением  интенсивности амплитуд максимального и минимального регистрируемого сигналов).

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

2.2. Операции с данными

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

Можно выделить следующие основные операции с данными:

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

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

2.3. Системы счисления

Система счисления (СС)– это совокупность приемов наименования и записи чисел. В любой СС для представления чисел используются некоторые числа, которые называются базисными числами, а все остальные числа получают в результате каких-либо операций над базисными числами. В современном мире наиболее распространено представление чисел 0. . .9.

СС различаются выбором базисных чисел и правилами образования из них остальных чисел. Например, в римской СС базисными являются: I (1),V(5), X (10), L (50), C(100), D (500), M (1000), а другие получаются путем сложения и вычитания базисных чисел. В римской СС каждый числовой знак имеет одно и тоже значение, т. е. значение числового знака не зависит от его расположения в записи числа: 146 – CXLVI.

Такая СС является непозиционной. В ней удобно записывать небольшие числа. Но выполнять операции над большими числами неудобно.

2.2.1. Позиционные системы счисления

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

Количество цифр, используемых для изображения чисел в позиционной СС, называется ее основанием, т. е. если используется К цифр, то основание СС равно К. Число в позиционной СС можно представить следующим образом:

Позиции перенумерованные таким образом называют разрядами. Каждая из цифр принимает одно из значений . K используется для количественной оценки каждого разряда числа. Т. е. число в k-ичной СС можно представить в виде полинома:

Примеры позиционных систем счисления:

  1.  Десятичная СС. Используются цифры 0. . 9, тогда любое число может быть представлено как

    Цифры 0. .9 называют базисными.

  2.  Двоичная СС. Используются цифры 0 и1. Число в двоичной СС может быть представлено как

  3.  Восьмеричная СС, в качестве базисных чисел используются цифры 0..7. Число представляется как

  4.  Шестнадцатеричная СС, в качестве базисных чисел используются цифры 0..9, А, B,C, D, E, F . Число представляется как

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

Таблицы сложения и умножения в двоичной СС имеют вид:

0+0=0

0*0=0

0+1=1

0*1=0

1+0=1

1*0=0

1+1=10

1*1=1

Для физического представления чисел необходимы элементы, которые способны находиться в одном из нескольких устойчивых состояний. Число этих состояний должно быть равно основанию принятой СС, тогда каждое состояние будет представлять соответствующую цифру из алфавита данной СС. Для реализации десятичной системы СС потребуются элементы, имеющие 10 устойчивых состояний. Наиболее простыми с точки зрения технической реализации являются двухпозиционные элементы, способные находиться в одном из двух устойчивых состояний, например, электромагнитное реле (состояния «замкнуто»-«разомкнуто»), ферромагнитная поверхность (намагничена – размагничена), транзисторный ключ и т. д. Одно из этих состояний можно обозначить цифрой –0, а другое – 1.

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

Недостатком двоичной СС является большое число разрядов двоичного кода.

2.2.2. Перевод чисел из одной СС в другую

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

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

Пример:

Правила перевода чисел из десятичную в двоичную различны для целой и дробной частей числа.

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

Пример:

11

2

1

5

2

1

2

2

0

1

2

1

0

Таким образом,

Для перевода дробной части числа используется алгоритм последовательного умножения на основание новой СС (на 2), действия производятся в старой СС (в десятичной), целые части чисел, полученные в результате умножения дают запись результата.

Пример:

0

875

х

2

1

75

х

2

1

5

х

2

1

0

Умножение прекращается, либо когда дробная часть становится равна 0, либо, когда будет получена требуемая точность представления числа.

0

7

х

2

1

4

х

2

0

8

х

2

1

6

. . . .

Аналогично переводятся позиционные числа и с другими основаниями СС.

2.2.3. Смешанные СС

В смешанных СС каждая цифра в СС с основанием Р записывается в виде цифры с основанием Q, (Q<P). Чтобы запись числа в смешанной СС была однозначной, для представления  любой цифры исходного числа отводится одно и то же количество разрядов, достаточное для представления любого базисного числа исходной СС.

Пример:

=

1001

0010

(двоично-десятичная СС)

 

9

2

5

Аналогично рассмотренной двоично-десятичной СС можно использовать и другие смешанные СС при различных значениях P и Q (P- старшее основание СС, Q – младшее).

Отдельно рассматривается случай, когда  , где l – целое положительное число. В этом случае запись числа в смешанной СС совпадает с изображением этого числа в СС с основанием Q. Например, , т. е. запись шестнадцатеричного числа в смешанной двоично-шестнадцатеричной СС будет тождественна его записи в двоичной СС. Это свойство широко используется на практике для сокращенной записи чисел заданных в СС с небольшим основанием.

Преобразование чисел из двоичной системы в восьмеричную и шестнадцатеричную

Для представления цифры в 16-чной СС понадобится 4 цифры двоичной СС, для представления цифры в 8-ной СС понадобится 3 цифры двоичной СС. Для перевода 8-чного числа в 2-чную СС надо заменить каждую цифру этого числа ее двоичным эквивалентом. Аналогично переводятся числа из 16-ой СС в двоичную.

Аналогично выполняются обратные преобразования

Таблица эквивалентов

Десятичная,

Восьмеричная (23),

Шестнадцатеричная (24),

Двоичная

0

0000

1

0001

2

0010

3

0011

4

0100

5

0101

6

0110

7

0111

8

1000

9

1001

10 (A)

1010

11 (B)

1011

12 (C)

1100

13 (D)

1101

14 (E)

1110

15 (F)

1111

Примеры.

10

2->8

8

2->16

16

46,5

101 110,1

56,4

0010 0111,1000

2Е,8

21,5

010 101,1

25,4

0001 0101,1000

15,8

Аналогично можно выполнять преобразования чисел и для СС с основаниями 3 и 9, Они также связаны соотношением  (9=32 )

Десятичная,
девятеричная

Троичная

0

00

1

01

2

02

3

10

4

11

5

12

6

20

7

21

8

22

Для представления цифры в 9-ной СС понадобится 2 цифры троичной СС. Для перевода 9-чного числа в 3-чную СС надо заменить каждую цифру этого числа ее троичным эквивалентом.

Пример

9

3

345,3

10 11 12,10

2.3. Внутреннее представление данных в памяти ЭВМ

2.2.1 Понятие о кодировании информации

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

  1.  удобство физической реализации;
  2.  удобство восприятия;
  3.  высокая скорость передачи и обработки;
  4.  уменьшение избыточности сообщений;
  5.  надежность, т. е. защита от случайных искажений;
  6.  сохранность, т. е. защита от несанкционированного доступа.

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

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

2.3.2. Понятие о специальном кодировании

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

  1.  Прямой код

где - значение цифры в i-ом разряде, q –основание системы счисления.

Пример

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

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

  1.  Обратный код

,

где  - инверсия цифры , определяется .  Для двоичной СС инверсией 1 является 0 и наоборот.

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

Пример.

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

Таким образом, для преобразования прямого кода q-ичного отрицательного числа в дополнительный , надо преобразовать его в обратный код и в младший разряд добавить 1.

Пример

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

Пример.

=0.1101 1001

= 0.1101 1001

+

+

=1.1010 0010

= 1.1010 0011

=

=

           10.0111 1011              

            10.0111 1100              

                             +1

отбрасывается

=0.0111 1100

=0.0111 1100

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

Пример 1.

Получить дополнительный код числа х= -1310

  1.  х= -1310= -11012
  2.  1.1101
  3.  =1.0010
  4.  1.0011

Пример 2.

Вычислить, используя дополнительные коды 710-310   

1)

х= 710= 1112

х= -310= -0112

2)

0.111

1.011

1.100

1.101

3)

0.111

+

1.101

=

10.100

4)

х= 1002=410

Пример 3.

Вычислить, используя дополнительные коды 810-1310   

1)

х= 810=10002

х= -1310= -11012

2)

0.1000

1.1101

1.0010

1.0011

3)

0.1000

+

1.0011

=

1.1011

В знаковом разряде стоит 1, следовательно, результат получен в дополнительном коде.

4)

1.1011

1.1011-1=1.1010

1.0101

В знаковом разряде стоит 1, следовательно, число отрицательное

5)

х= 1.01012= -510

2.3.3. Способы представления информации в ЭВМ

Информация в ЭВМ записывается в форме цифрового двоичного кода, т. к. элементы из которых строится память, могут находиться в двух устойчивых состояниях 0 и 1. Двоичное кодирование используется для представления как числовой, так и текстовой, графической, звуковой информации. Форматы представления данных в памяти компьютера определяют диапазоны значений, которые эти данные могут принимать, скорость их обработки, объем памяти, который требуется для хранения этих данных.

В ЭВМ используются следующие формы представления данных:

  •  числа с фиксированной точкой;
  •  числа с плавающей точкой;
  •  символы.

2.3.3.1. Числа с фиксированной точкой.

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

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

Все числа, которые хранятся в памяти компьютера, занимают определенное число двоичных разрядов. Это количество определяется форматом числа. Обычно для представления целых чисел используют несколько форматов. В IBM-совместимых ПК поддерживается три формата: байт (8 разрядов), слово (16 разрядов), двойное слово (32 разряда). Целые числа вписываются в разрядную сетку, соответствующую формату. Для целых чисел разрядная сетка имеет вид:

n-1

n-2

n-3

2

1

0

S

. . .

где - разряды двоичной записи целого числа, S - разряд, отведенный для представления знака числа. Для положительных чисел знак кодируется цифрой 0, а для отрицательных – цифрой 1 (прямой код). Разделитель между целой и дробной частью зафиксирован после , дробной части нет. N - количество двоичных разрядов в разрядной сетке. Если количество разрядов в сетке оказывается больше, чем количество цифр в числе, то старшие разряды заполняются нулями. Например, число  в формате байта (8 бит) запишется так:

7

6

5

4

3

2

1

1

0

0

0

0

1

0

1

1

знак

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

2.3.3.2. Числа с плавающей точкой

Для представления вещественных чисел используется форма чисел с плавающей точкой. Такое представление основано на записи числа в экспоненциальном виде:
- нормальная форма. Нормальная форма представления чисел неоднозначна. Например, десятичное число можно представить  Для однозначности используется нормализованная форма, в которой положение точки всегда задается перед первой значащей цифрой мантиссы. При использовании такой формы часть разрядов используется для хранения порядка числа р, а остальные - разряды для хранения мантиссы:

n-1

n-2

. . .

m

m-1

. . .

0

Знак

Порядок

Мантисса

Порядок числа и его мантисса хранятся в двоичном коде. Точность вычислений зависит от длины мантиссы, а порядок числа определяет допустимый диапазон представления действительных чисел. В IBM-совместимых компьютерах используется три формата представления данных в форме с плавающей точкой (32 разряда, 64 разряда и 80 разрядов), позволяющие определить три диапазона для положительных вещественных чисел: от 1,5х10-45 до 3,4х1038, от 5х10-324 до 1,7х10308 и от 1,9х10-4951 до 1,1х104932. Для представления положительных чисел в знаковый разряд записывается 0, а для отрицательных - 1. Порядок и мантисса записываются в разрядную сетку как целые числа.

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

2.3.3.3. Символы

Текстовые данные рассматриваются как последовательность отдельных символов, каждому из которых ставится в соответствие двоичный код некоторого неотрицательного целого числа. Существуют разные способы кодирования символов. Наиболее распространенной до последнего времени была кодировка ASCII (American Standard Code for International Interchange). При использовании этой кодировки для представления символа используется 1 байт (8 разрядов). Таким образом, имеется возможность закодировать 256 различных символов.

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

В системе ASCII закреплены две таблицы кодирования базовая и расширенная. Базовая таблица закрепляет значения кодов от 0 до 127, а расширенная от 128 до 255. Первые 32 кода базовой таблицы, начиная с нулевого, содержат управляющие коды. Они не выводятся на экран, но с их помощью можно управлять выводом других данных. С 32 по 127 код размещены символы английского алфавита, цифры, знаки арифметических операций и т. п. Расширенная часть системы кодирования ASCII содержит национальные системы кодирования, т. е. коды с 128 по 255 будут содержать русский алфавит, а также символы псевдографики.

ASCII позволяет закодировать только 256 символов, но в некоторых языках символов больше, поэтому разрабатываются другие коды. Наиболее перспективным является Unicode. В этом коде каждый символ состоит из 16 битов (2 байта), что позволяет кодировать 65536 различных символов. Для каждого алфавита определены свои кодовые позиции. Например, 0100-017F – европейские латинские символы , 0400-04FF – кириллица и т. д. Около 29000 позиций пока не заняты, но зарезервированы для использования. Таким образом, Unicode допускает обмен данными на разных языках, каждому коду соответствует единственный символ, коды для разных языков не пересекаются.

На Unicode построена ОС Windows NT. У Windows95-98 16-битное наследство, поэтому вся внутренняя работа в этой ОС построена на использовании ANS-строк (ANSIIAmerican National Standard Institute), в которых символ записан в один байт. ANSI-текст (или текст ASCII)  - это текст без форматирования (с ним работает приложение «Блокнот» в Windows 9x).

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

2.3.3.4. Кодирование графической информации

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

Для кодирования цветных графических изображений применяется принцип декомпозиции произвольного цвета на основные составляющие. В качестве таких составляющих используют три цвета: красный (Red, R), зеленый (Green, G), синий (Blue, B). На практике считается, что любой цвет, видимый человеческим глазом, можно получить путем механического смешения этих трех цветов. Такая система кодирования называется системой RGB- по первым буквам основных цветов.

Если для кодирования яркости каждой из основных составляющих использовать по 256 значений (8 двоичных разрядов), то на кодирование одной точки придется затратить 24 разряда, при этом система кодирования обеспечивает однозначное определение 16,5 миллионов различных цветов. Режим  представления цветной графики с использованием 24 разрядов называется полноцветным (True Color).

Каждому из основных цветов можно поставить в соответствие дополнительный цвет, т. е. цвет, дополняющий основной цвет до белого. Нетрудно заметить, что для любого из основных цветов дополнительным будет цвет, образованный суммой пары остальных основных цветов: голубой (Cyan, C), пурпурный (Magenta, M), желтый (Yellow,  Y). Принцип декомпозиции произвольного цвета на составляющие компоненты можно применить не только для основных цветов, но и для дополнительных, т. е. любой цвет можно представить в виде суммы голубой, пурпурной и желтой составляющих. Такой метод кодирования принят в полиграфии, но там используется еще и четвертая краска – черная (Black, К). Поэтому данная система кодирования обозначается четырьмя буквами - CMYK. Для представления цветной графики в этой системе надо иметь 32 двоичных разряда. Такой режим тоже называется полноцветным (True Color).

Если уменьшить количество двоичных разрядов, используемых для кодирования цвета каждой точки, то можно сократить объем данных, но при этом диапазон кодируемых цветов заметно сокращается. Кодирование цветной графики 16-разрядными двоичными числами называется режимом High Color.

2.3.3.5. Кодирование звуковой информации

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

  1.  Метод частотных модуляций FM (Frequency Modulation) основан на том, что практически любой звук можно разложить на последовательность простейших гармонических сигналов разных частот, каждый из которых представляет собой правильную синусоиду, а, следовательно, может быть описан числовыми параметрами, т. е. кодом. В природе звуковые сигналы имеют непрерывный спектр, т. е. являются аналоговыми. Чтобы закодировать звук, его надо дискретизировать. Этот процесс состоит в измерении и запоминании характеристик звуковой волны (амплитуды и периода) в виде двоичного кода. Он  выполняется специальными устройствами, которые называют аналого-цифровыми преобразователями (АЦП), несколько десятков тысяч раз в секунду. Обратное преобразование звука, закодированного числовым кодом, выполняют цифро-аналоговые преобразователи (ЦАП). При таких преобразованиях неизбежны потри информации, связанные с методом кодирования, поэтому качество звукозаписи получается не вполне удовлетворительным. Но это достаточно компактный метод, он начал использоваться, когда ресурсов вычислительной техники было недостаточно.
  2.  Метод таблично-волнового синтеза (Wave-Table) состоит в следующем. Где-то в заранее подготовленных таблицах хранятся образцы звуков для различных музыкальных инструментов. В технике такие образцы называют сэмплами. Числовые коды выражают тип инструмента, номер его модели, высоту тона, продолжительность и интенсивность звука, динамику его изменения, параметры среды, в которой происходит звучание и др. Т .к в качестве образца использовались реальные звуки, то качество звука, полученного в результате синтеза получается достаточно высоким и приближается к качеству звучания реальных музыкальных инструментов.

2.4.  Основные структуры данных

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

  •  линейная,
  •  иерархическая,
  •  табличная.

Основными операциями, которые можно осуществлять над структурами данных являются:

  •  формирование структуры данных;
  •  добавление элемента (в начало, конец, с заданным номером, после  заданного элемента );
  •  удаление элемента (из начала, из конца, с заданным номером, с заданным значением - ключом);
  •  просмотр структуры;
  •  поиск элемента с заданным значением – ключом;
  •  сортировка (упорядочивание элементов структуры в заданном порядке).

Пример:

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

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

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

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

2.4.1. Линейные структуры

Линейные структуры – это списки данных. В списке каждый элемент однозначно определяется своим номером. Номера должны быть уникальными. При создании любой структуры надо решить два вопроса: как разделять данные между собой и как разыскивать нужные элементы.

Пример. Список студентов группы.

  1.  Александров А. А.
    1.  Борисов Б. Б.
    2.  Васильева В. В.
    3.  Гаврилов Г. Г.
    4.  Дмитриева Д. Д.
    5.  . . . . . . .

Каждый элемент списка заносится с новой строки, т. е. разделителем является конец строки. Элементы ищутся по номеру строки.

Разделителем может быть какой-нибудь специальный символ:

Александров А. А.*Борисов Б. Б.*Васильева В. В.*Гаврилов Г. Г.*Дмитриева Д. Д.

В этом случае для поиска нужного элемента надо просмотреть список, начиная с начала и пересчитать разделители. Когда будет отсчитано (n-1) разделителя, начнется нужный элемент. Он закончится, когда встретится следующий разделитель.

Еще проще осуществляются операции в списке, в котором элементы имеют одинаковую длину. В этом случае разделители вообще не нужны. Для поиска надо отсчитать a*(n-1) символ, где а – длина одного элемента. Списки, которые состоят из элементов равной длины, называются векторами данных.

2.4.2.Табличные структуры

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

1.

Александров А. А.

5

2.

Борисов Б. Б.

2

3.

Васильева В. В.

1

4.

Гаврилов Г. Г.

5

5.

Дмитриева Д. Д.

3

будет структура:

1*Александров А. А.*5#2*Борисов Б. Б.*2#3*Васильева В. В.*1#4*Гаврилов Г. Г.*10#5*Дмитриева Д. Д.*3.

Если все элементы таблицы имеют равную длину, то такие таблицы называются матрицами.  Таблицы могут иметь количество измерений больше 2, т. е. быть многомерными.

2.4.3. Иерархические структуры данных

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

Рис. 1. Пример иерархической структуры

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

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

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

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



Жилец
J

Жилец 1

Квартира К

Квартира 1

Дом T

Дом 1

Улица М

Улица 1

Город N

ород 2

Город 1

Страна

Дробная часть

Целая часть


 

А также другие работы, которые могут Вас заинтересовать

80309. Оплата праці на підприємстві 126.5 KB
  Мотивація - це процес формування в людини або групи людей мотивів до діяльності, спрямованої на досягнення індивідуальних і загальних цілей організації, підприємства.
80310. Витрати виробництва і собівартість продукції підприємства 199.5 KB
  Для визначення витрат на підприємстві використовується термін собівартість продукції до якої зараховують поточні витрати на її виробництво та збут виражені у грошовій формі. Витрати підприємства відшкодовуються за рахунок двох власних джерел: собівартості та прибутку. Усі витрати що формують собівартість продукції можна класифікувати за певними ознаками табл.
80311. Ціни та ціноутворення в ринкових умовах 449.5 KB
  Ціни у діяльності промислового підприємства виконують три основні функції: облікововимірювальну стимулюючу розподільчу. Облікововимірювальна функція ціни є засобом обліку й вимірювання витрат суспільної праці на виробництво окремих видів промислової продукції або надання відповідних послуг. Стимулюючу функцію ціни використовують для мотивації підвищення ефективності підприємницької діяльності забезпечення необхідної прибутковості дохідності кожному з учасників процесу товарообміну.
80312. Фінансово-економічні результати й ефективність діяльності 80 KB
  Суть фінансової діяльності підприємства полягає у виникненні грошових відносин, пов’язаних з неперервним кругообігом коштів у формах: витрачання ресурсів, одержання доходів, їх використання, а також із приводу відносин з постачальниками, покупцями продукції, працівниками підприємства, державними органами та ін.
80313. Виробництво, якість і конкурентоспроможність продукції 121.5 KB
  Поняття якості продукції необхідність і значення її підвищення в сучасних умовах Показники і методи оцінювання якості продукції Управління якістю продукції. Стандартизація та сертифікація продукції. Економічна ефективність і шляхи підвищення якості та конкурентоспроможності продукції.
80314. Організаційні основи виробництва 77 KB
  Систематична розробка наукових методів організації виробництва у промисловості почалася наприкінці XIX ст. Особливу роль у розробці наукових основ організації виробництва відіграли роботи Ф.У. Тейлора. Він сформулював принципи організації виробництва і розробив на цій основі систему наукового управління
80315. Впровадження інновацій у сферу виробництва 111 KB
  Процес організації інноваційної діяльності на підприємстві стосується як споживачів інвесторів державних і місцевих органів влади наукових та науковотехнічних організацій постачальників працівників підприємства тощо так і забезпечує вирішення основних завдань підприємства. Сучасне підприємство за певних умов може власними силами розробляти нові вироби здійснювати науководослідні та проектно-конструкторські роботи якщо вони відносно нескладні. Для розробки досить складних виробів проведення довгострокових що потребують значних...
80316. Організація нормування праці 117 KB
  Класифікація витрат робочого часу та склад норми часу. Вивчення затрат робочого часу спостереженням. ЗМІСТ ЛЕКЦІЇ Сутність і завдання нормування праці Необхідною умовою організації праці та виробничих процесів на підприємстві є встановлення точних витрат часу на всі роботи що виконуються на робочих місцях бригад дільниць та цехів. На ефективно працюючих підприємствах норми часу регулюють всі основні технологічні процеси роботи і операції та більшість обслуговуючих.
80317. Організація наукових досліджень та проектних робіт 132 KB
  Планування фінансування і звітність про виконання науководослідних та проектноконструкторських робіт. Види методи й етапи виконання наукових досліджень Основна спрямованість науковотехнічної діяльності одержання нових знань використання їх для створення і вдосконалення засобів знарядь предметів та умов праці й життя людини духовного та культурного розвитку суспільства. Згідно з чинним законодавством держава забезпечує: соціальноекономічні організаційні правові умови для формування та ефективного використання науковотехнічного...