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

     ВВЕДЕНИЕ

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

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

     ─ дать общую характеристику данным;

     ─ изучить различные структуры данных;

     ─ проанализировать упорядочение структур данных;

     ─ рассмотреть режимы обработки данных;

     ─ решить практическую задачу с использованием средств MS Exsel.

     Объектом  исследования являются данные. Предметом  исследования служат структуры данных.

     Информационной  базой исследования являются публикации в сети Интернет и учебная литература по изучаемому вопросу.

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

1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

1.1 ОБЩАЯ ХАРАКТЕРИСТИКА  ДАННЫХ

     Данные – это материальные объекты произвольной формы, выступающие в качестве средства представления информации. Преобразование и обработка данных позволяют извлечь информацию, т.е. знание о том или ином предмете, процессе, явлении [2, С.21]. Другими словами данные – диалектическая составная часть информации. Они представляют собой зарегистрированные сигналы. В соответствии с методом регистрации данные могут храниться и транспортироваться на носителях различных видов. Например, на бумаге данные регистрируются путем изменения оптических характеристик ее поверхности. Изменение оптических свойств используется также в устройствах, осуществляющих запись лазерным лучом на пластмассовых носителях с отражающим покрытием (CD-ROM).

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

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

     • сбор данных — накопление информации с целью обеспечения достаточной полноты для принятия решений;

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

     • фильтрация данных — отсеивание «лишних» данных, в которых нет необходимости для принятия решений;

     • сортировка данных — упорядочение данных по заданному признаку с целью удобства использования; повышает доступность информации;

     • архивация данных — организация хранения данных в удобной и легкодоступной форме;

     • защита данных — комплекс мер, направленных на предотвращение утраты, воспроизведения и модификации данных;

     • транспортировка данных — прием и передача (доставка и поставка) данных между удаленными участниками информационного процесса;

     • преобразование данных — перевод данных из одной формы в другую или из одной структуры в другую.

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

1.2 ЛИНЕЙНЫЕ СТРУКТУРЫ  ДАННЫХ

     Линейные  структуры – это хорошо знакомые нам списки. Список – это простейшая структура данных, отличающаяся тем, что каждый элемент данных однозначно определяется своим номером в массиве. Проставляя номера на отдельных страницах рассыпанной книги, мы создаем структуру списка. Обычный журнал посещаемости занятий, например, имеет структуру списка, поскольку все студенты группы зарегистрированы в нем под своими номерами, при этом не могут два студента быть зарегистрированы с одним и тем же номером [3, С.27].

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

     № п/п Фамилия, Имя, Отчество

1. Аистов Александр Алексеевич

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

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

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

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

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

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

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

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

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

1.3 ТАБЛИЧНЫЕ СТРУКТУРЫ  ДАННЫХ

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

     При хранении табличных данных количество разделителей должно быть больше, чем  для данных, имеющих структуру  списка. Например, когда таблицы  печатают в книгах, строки и столбцы  разделяют графическими элементами – линиями вертикальной и горизонтальной разметки (рис.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

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

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

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

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

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

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

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

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

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

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

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

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

     1.4 ИЕРАРХИЧЕСКИЕ СТРУКТУРЫ  ДАННЫХ

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

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

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