Файл: СПОСОБЫ ПРЕДСТАВЛЕНИЯ ДАННЫХ В ИНФОРМАЦИОННЫХ СИСТЕМАХ (Данные и модели данных).pdf

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

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

Термин "структура данных" может иметь несколько похожих, но разных значений:

* Абстрактный тип данных;

* Реализация абстрактного типа данных;

* Экземпляр типа данных, например определенный список;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Меркурий*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 разделитель, начнется нужный элемент. Он закончится, когда будет встречен любой очередной разделитель.

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

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

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

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

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

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

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

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

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

Глава 2 Представление данных в системах обработки данных

Уровни представления данных. СОД хранения и обработки информации - информация об объектах реального мира. Некоторый набор информации, ОПИ- конкретный объект называется логической записью или просто записью . Коллекция записей, охватывающих множество объектов определенного типа класс, называемый информационным массивом.

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

На логическом уровне работают с логическими структурами данных,

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

Логическая структура данных должна исчерпывающе характеризовать

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

На логическом уровне представления данных не учитывается техническое и математическое обеспечение системы (тип ЭВМ, типы памяти, язык программирования, операционная система).

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

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

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