Информация в материальном мире

2 Бобров Борис Борисович

3. Воробьева Валентина Владиславовна

…      ………………………………………….

27      Сорокин Сергей  Семенович

Разделителем может быть и какой-нибудь специальный символ. Нам хорошо известны  разделители между словами —  это пробелы. В русском и во многих европейских  языках общепринятым разделителем предложении является точка. В рассмотренном  нами классном журнале в качестве разделителя можно использовать любой символ,  который не встречается в самих данных, например символ «*». Тогда наш список  выглядел бы так:

Аистов Александр Алексеевич * Бобров Борис Борисович * Воробьева Валентина  Владиславовна *...* Сорокин Сергей Семенович

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

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

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

 

Табличные структуры (таблицы  данных, матрицы данных)

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

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

Если нужно сохранить таблицу  в виде длинной символьной строки, используют  один символ-разделитель  между элементами, принадлежащими одной  строке, и  другой разделитель для  отделения строк, например так:

Меркурий*0,39*0,056*0#Венера*0,67*0,88*0#Земля*1,0*1,0*1#Марс*1,51*0,1*2#...

Планета	Расстояние  до Солнца, а.е.	Относительная масса	Количество спутников
Меркурий	0,39	0,056	0
Венера	0,67	0,88	0
Земля	1,0       '	1,0	1
Марс	1,51	0,1	2
Юпитер	5,2	318	16

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

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

Еще проще можно действовать, если все элементы таблицы имеют равную длину.  Такие таблицы называют матрицами. В данном случае разделители не нужны,  поскольку все элементы имеют равную длину и количество их известно. Для розыска  элемента с адресом (т, я) в матрице, имеющей М строк и N столбцов, надо про-  смотреть ее с самого начала и отсчитать a [N(m - \) + (п -1)] символ, где а—длина одного элемента. Со следующего символа начнется нужный элемент. Его длина тоже равна а, поэтому его конец определить нетрудно.

Таким образом, табличные структуры данных (матрицы) — это упорядоченные  структуры, в которых адрес элемента определяется номером строки и номером  столбца, на пересечении которых находится ячейка, содержащая искомый элемент.

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

Номер факультета: 3

Номер курса (на факультете): 2

Номер специальности (на курсе): 2

Номер группы в потоке одной специальности: 1

Номер учащегося в группе: 19

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

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

Пуск» Программы > Стандартные > Калькулятор.

 

В иерархической структуре, построенной  методом дихотомии, путь доступа к любому  элементу можно представить как путь через рациональный лабиринт с поворотами  налево (0) или направо (1) и, таким образом, выразить путь доступа в виде компактной двоичной записи. В нашем примере путь доступа к текстовому процессору  Word 2000 выразится следующим двоичным числом: 1010.

Упорядочение структур данных

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

по алфавиту, по возрастанию порядкового номера или по возрастанию какого-либо  параметра.

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

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

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

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

Адресные данные. Если данные хранятся не как попало, а в организованной структуре  (причём любой), то каждый элемент данных приобретает новое свойство (параметр),  который можно назвать адресом. Конечно, работать с упорядоченными данными  удобнее, но за это приходится платить их размножением, поскольку адреса элементов  данных — это тоже данные, и их тоже надо хранить и обрабатывать.

1.3. Файлы и файловая  структура

Единицы представления  данных

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

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

Десятичное число	Двоичное число	Байт
1	1	0000 0001
2	10	0000 0010
...	...	...
255	11111111	1111 1111

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

Выше мы видели, что во многих случаях  целесообразно использовать не восьми-  разрядное кодирование, а 16-разрядное, 24-разрядное, 32-разрядное и более. Группа  из 16 взаимосвязанных бит (двух взаимосвязанных байтов) в информатике называется словом. Соответственно, группы из четырех взаимосвязанных байтов (32 разряда) называются удвоенным словом, а группы из восьми байтов (64 разряда) — учетверенным  словом. Пока, на сегодняшний день, такой системы обозначения достаточно.

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

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

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

Более крупная единица измерения  — килобайт (Кбайт). Условно можно  считать,  что 1 Кбайт примерно равен 1000 байт. Условность связана с тем, что для вычислительной техники, работающей с двоичными числами, более удобно представление чисел  в виде степени двойки, и потому на самом деле 1 Кбайт равен 2¹⁰ байт (1024 байт).  Однако всюду, где это не принципиально, с инженерной погрешностью (до 3 %)  «забывают» о «Лишних» байтах.

В килобайтах измеряют сравнительно небольшие объемы данных. Условно можно  считать, что одна страница неформатированного машинописного текста составляет  около 2 Кбайт.

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

1 Мбайт = 1024 Кбайт * 2²⁰ байт  1 Гбайт = 1024 Мбайт = 2³⁰ байт  1Тбайт =1024 Гбайт =2⁴⁰байт

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

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

При хранении данных решаются две  проблемы: как сохранить данные в  наиболее  компактном виде и как  обеспечить к ним удобный и  быстрый доступ (если доступ  не обеспечен, то это не хранение). Для обеспечения доступа необходимо, чтобы  данные имели упорядоченную структуру, а при этом, как мы уже знаем, образуется  «паразитная нагрузка» в виде адресных данных. Без них нельзя получить доступ к нужным элементам данных, входящих в структуру.