Файл: Информация в материальном мире (Понятие информация в материальном мире).pdf

Глава 3. Основные структуры данных

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

Линейные структуры (списки данных, векторы данных)

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

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

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

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

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

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

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

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

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

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

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

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

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

Программное обеспечение

Системные программы

Служебные программы

Прикладные программы

Системы управле­ния базами данных

Векторные редакторы

Растровые редакторы

Adobe Illustrator 8.0

Corel DRAW 9.0

Macromedia Freehand 8.01

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

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

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

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

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

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

Информационное обеспечение

Прикладные программы

Неприкладные программы

Графические редакторы

Неграфические редакторы

Текстовые процессоры

Нетекстовые процессоры

Текстовый процессор WordPad

Текстовый процессор Word 2000

Рис. 1.6. Пример, поясняющий принцип действия метода дихотомии

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

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

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

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

Заключение

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

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

Свойства информации:

- достоверность;

- полнота;

- ценность;

- своевременность;

- понятность;

- доступность;

- краткость;

- и др.

Информация может существовать в самых разнообразных формах:

- в виде текстов, рисунков, чертежей, фотографий;

- в виде световых или звуковых сигналов;

- в виде радиоволн;

- в виде электрических и нервных импульсов;

- в виде магнитных записей;

- в виде жестов и мимики;

- в виде запахов и вкусовых ощущений;

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

Создателем общей теории информации и основоположником цифровой связи считается Клод Шеннон (Claude Shannon). Всемирную известность ему принес фундаментальный труд 1948 года — «Математическая теория связи» (A Mathematical Theory of Communication), в котором впервые обосновывается возможность применения двоичного кода для передачи информации.

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

Библиографический список

Специальная, научная и учебная литература

Варфоломеев В.И., «Програмные средства офисного назначения. Практикум», М., МГУК, 2001.

Информатика. Базовый курс // Под ред. С.В. Симоновича, СПб., 2000.

Леонтьев В.П. Новейшая энциклопедия персонального компьютера 2003. – М.: Олма-пресс, 2003.

Перри Г., «Освой самостоятельно Microsoft Office 2000 за 24 часа».- М: «Вильямс» 2000 г.

Фигурнов В.Э. IBM PC для пользователей. 7е изд., прераб. И доп. – М.: ИНФА – М, 2002.

Хелворсон М., Янг М., «Эффективная работа с Microsoft Office 2000», М., «Питер», 2001.

Каймин В.А. Информатика: Учебник. - М.: ИНФРА-М, 2000. - 232 с.

Громов Г.Р. Очерки информационной технологии. - М.: Инфоарт, 2002.