Файл: Способы представления данных в информационных системах..pdf

2. Данные.

2.1 Типы данных.

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

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

Существуют различные классификации типов данных и правил их назначения. Типы данных делят на скалярные и нескалярные. Значение нескалярного типа имеет множество видимых пользователю компонентов, а значение скалярного типа не имеет такового. Примерами нескалярного типа являются массивы, списки, а примеры скалярного типа – целые, логические.

Рассмотрим распространенные типы данных.

Логически тип данных, или булевый тип – примитивный тип данных в информатике, принимающий два возможных значения, называемых – истиной (true) и ложью (false). Булев тип данных может быть реализован и храниться в памяти с использованием только одного бита.

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

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

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

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

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

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

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

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

Самые основные операции в связанном списке включают добавление элемента в список, удаление элемента из списка и поиск в списке для элемента.

Стек – базовая структура данных, в которой можно только вставлять или удалять элементы в начале стека. Он напоминает стопку книг. Если захотеть взглянуть на книгу в середине стека, то с начало необходимо взять книги, лежащие сверху. Это означает, что последний элемент, который добавлен в стек, это первый элемент, который из него выходит.

Существует три основных операции, которые могут выполняться в стеках: вставка элемента в стек (push), удаление элемента из стека (pop) и отображение содержимого стека (pip).

Очередь. Стоящий первым будет обслужен первым.

Это означает, что после добавления нового элемента, все элементы, которые были добавлены до этого, должны быть удалены до того, как новы элемент будет удален. В очереди есть две основные операции: добавление элемента (enqueuer) в конец очереди и удаление элемента (dequeuer).

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

Union (объединение). Объединяет все элементы из двух разных множеств и возвращает результат, как новый набор без дубликатов.

Intersection (пересечение). Если заданы два множества, эта функция вернет другое множество, содержащее элементы, которые имеются и в первом и во втором множестве.

Difference (разница). Вернет список элементов, которые находятся в одном множестве, но не повторяются в другом.

Subset (подмножество) – возвращает булево значение, показывающее, содержит ли оно множество все элементы другого множества.

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

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

- добавление пары в коллекции;

- удаление пары из коллекции;

- изменение существующей пары;

- Поиск значения, связанного с определенным ключом.

Хеш-таблица – это структура данных, реализующая интерфейс map, который позволяет хранить пары ключ/значение. Она использует хеш-функцию для вычисления индекса в массиве, по которым можно найти желаемое значение.

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

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

Двоичное дерево поиска.

Дерево – это структура данных, состоящая из узлов. Она имеет следующие характеристики:

- каждое дерево имеет корневой узел (вверху);

- корневой узел имеет ноль или более дочерних узлов;

- каждый дочерний узел имеет ноль или более дочерних узлов.

Двоичное дерево поиска имеет еще две характеристики:

- каждый узел имеет до двух детей (потомков);

- для каждого узла его левые потомки меньше текущего узла, что меньше, чем у правых потомков.

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

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

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

Графы представляют собой совокупность узлов (вершина графа) и связей (ребро графа) между ними.

Одним из примеров графов, может служить социальная сеть. Узлы – это люди, а ребра – это связь между людьми или дружба.

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

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

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

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

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

3. Системы обработки данных.

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

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

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

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

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

Информационные массивы размещаются в памяти ЭВМ. От того, насколько правильно выбраны устройства памяти, способы размещения и выборки массивов, зависят показатели качества функционирования системы обработки и хранения информации и всей СОД вцелом.

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

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

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