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

Лекция 2

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

 

Компьютер может обрабатывать информацию, представленную только в цифровом виде, поэтому вся другая информация (тексты, звуки, графические изображения и т.д.) должна быть приведена к числовой форме. С помощью специальных программ можно выполнить процедуру преобразования информации любого вида к числовому, а после ее компьютерной обработки – обратно к первоначальному. Для перевода информации к числовому виду обычно используется прием кодирования, т.е. выражение данных одного типа через данные другого типа. {Естественные человеческие языки – это не что иное как системы кодирования понятий для выражения мыслей посредством речи; АЗБУКИ – системы кодирования компонентов языка с помощью графических символов. (Примеры: азбука Морзе, морская флажковая азбука, система сигналов регулировщика, система Брайля для слепых}.

Своя система существует и в вычислительной технике – она называется двоичным кодированием и основана на представлении данных двумя знаками :0 и 1, которые называются двоичными цифрами (binary digit) или битами (bit). То есть один бит может принимать одно из двух значений 0 или 1 (да или нет, истина или ложь). Если количество битов увеличить до двух, то можно выразить уже четыре различных понятия:

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

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

N = 2^m , где

N – количество кодируемых значений

m – разрядность двоичного кодирования

 

Кодирование целых и действительных чисел

 

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

15:2=7+1

7:2=3+1

3:2=1+1

Получили 15₁₀=1111₂

Проверим себя:

2⁰+2¹+2²+2³ =15

Переведите из десятичной в двоичную систему счисления числа 19, 25, 5

(1011, 11001, 101)

Таким образом для кодирования целых чисел от 0 до 255 достаточно иметь 8 разрядов двоичного кода (8 бит). Шестнадцать бит позволяют закодировать целые числа от 0 до 65535, а 24 бита – уже более 16,5 миллионов разных значений.

Для кодирования действительных чисел, используют 80 – разрядное кодирование. При этом предварительно число приводят в нормализованную форму:

3,145 = 0,3145*10¹

300000 = 0,3*10⁶

0,0005 = 0,5*10^-3

Первая часть числа называется мантиссой, вторая – характеристикой. Большую часть из 80 бит отводят для хранения мантиссы (вместе со знаком), и некоторое фиксированное число разрядов для характеристики (со знаком).

 

Кодирование текстовых данных

 

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

Все эти 256 символов собраны в так называемую таблицу ASCII – кодов, предложенную Институтом стандартизации США, которая и стала международным стандартом. {Систем кодирования предлагалось множество, в России были созданы свои системы кодирования, многие из них используются}.

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

 

Кодирование графических данных

 

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

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

Режим представления цветной графики с использованием 24 или 32 двоичных разрядов называется полноцветным (True Color). Кодирование 16-разрядными двоичными числами называется режимом High Color.

 

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

 

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

Метод FM основан на том, что теоретически любой сложный звук можно разложить на последовательность гармонических сигналов разных частот, каждый из которых может быть описан числовыми параметрами, т.е. кодом. В природе звуковые сигналы являются аналоговыми, их представление в виде дискретных цифровых сигналов выполняют специальные устройства – аналого-цифровые преобразователи (АЦП). Обратное преобразование для воспроизведения звука выполняют цифро – аналоговые преобразователи. При таких преобразованиях неизбежны потери информации, поэтому качество звукозаписи получается не очень удовлетворительным и соответствует звучанию электронной музыки. Но такой метод обеспечивает компактный код и при малых ресурсах техники вполне применим.

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

 

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

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

1. Линейные структуры (списки данных, векторы данных) – это простейшая структура данных, где каждый элемент однозначно определяется своим номером в массиве. { На бумаге мы представляем списки, обычно пронумерованные, где каждый элемент располагается на отдельной строке и однозначно определяется его порядковым номером}. Автоматизированные данные отделяются какими-либо разделителями или все элементы списка имеют равную длину. Последние называются векторами данных.

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

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

 

Единицы измерения данных

 

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

Сколько байт занимает предложение «Я – студент ИНЭКА!»?

Представьте некоторые десятичные числа в виде байта.

Более крупной единицей является килобайт.

1 Кбайт = 2¹⁰ = 1024 байт

1 Мбайт = 2²⁰ = 1024 Кбайт

1 Гбайт = 2³⁰ = 1024 Мбайт

Еще более крупной единице является терабайт.