ИГА. Понятие базы данных
 Скачать 0.77 Mb.
|
Основные структуры данных.Работа с большими наборами данных автоматизируется проще, когда данные упорядочены, то есть образуют заданную структуру. Существует три основных типа структур данных: линейная, иерархическая и табличная. Их можно рассмотреть на примере обычной книги. Если разобрать книгу на отдельные листы и перемешать их, книга потеряет свое назначение. Она по-прежнему будет представлять набор данных, но подобрать адекватный метод для получения из нее информации весьма непросто. (Еще хуже дело будет обстоять, если из книги вырезать каждую букву отдельно в этом случае вряд ли вообще найдется адекватный метод для ее прочтения.) Если же собрать все листы книги в правильной последовательности, мы получим простейшую структуру данных линейную. Такую книгу уже можно читать, хотя для поиска нужных данных ее придется прочитать подряд, начиная с самого начала, что не всегда удобно. ^ 1. Линейная структура характеризуется тем, что каждый элемент данных однозначно определяется уникальным номером в массиве. Мы называем номера уникальными потому, что в одной группе не могут быть зарегистрированы два студента с одним и тем же номером. Линейные структуры это хорошо знакомые нам списки. Список это простейшая структура данных, отличающаяся тем, что каждый элемент данных однозначно определяется своим номером в массиве. Проставляя номера на отдельных страницах рассыпанной книги, мы создаем структуру списка. Обычный журнал посещаемости занятий, например, имеет структуру списка, поскольку все студенты группы зарегистрированы в нем под своими уникальными номерами. 2. Если, например, книга была бы разбита на части, разделы, главы, параграфы и т.п., то есть элементы структуры более низкого уровня входят в элементы структуры более высокого уровня (разделы состоят из глав, главы из параграфов и т. д.), то получаем иерархическую структуру. Эта структура характеризуется возможностью быстрого и упрощенного по сравнению с линейной поиска данных. Адрес каждого элемента определяется путем доступа, ведущим от вершины структуры к данному элементу. Например, система почтовых адресов: страна − край − город − улица − дом − квартира − адресат. Недостатком иерархической структуры является увеличенный размер пути доступа. 3.^ Табличные структур�� (таблицы данных, матрицы данных). С таблицами данных мы тоже хорошо знакомы, достаточно вспомнить всем известную таблицу умножения, матрицы. Табличные структуры отличаются от списочных тем, что элементы данных определяются адресом ячейки, который состоит не из одного параметра, как в списках, а из нескольких. Для таблицы умножения, например, адрес ячейки определяется номерами строки и столбца. Нужная ячейка находится на их пересечении, а элемент выбирается из ячейки. Выше мы рассмотрели пример таблицы, имеющей два измерения (строка и столбец), но в жизни нередко приходится иметь дело с таблицами, у которых количество измерений больше. Вот пример таблицы, с помощью которой может быть организован учет учащихся. Номер факультета: 3 Номер курса (на факультете): 2 Номер специальности (на курсе): 2 Номер группы в потоке одной специальности: 1 Номер учащегося в группе: 19 Размерность такой таблицы равна пяти, и для однозначного отыскания данных об учащемся в подобной структуре надо знать все пять параметров (координат). Массивы и их свойства.Начнем с классического понятия в сильно типизированных языках (например, в языке Паскаль). Тип массива в таких языках определяется на основе двух вспомогательных типов: типа элементов массива (базового типа) и типа индекса массива. В языке Паскаль определение типа массива выглядит следующим образом: type T=array [ I] of Т0, где Т0— базовый тип, а I— тип индекса. Т0может быть любым встроенным или ранее определенным типом. Тип индекса Iдолжен состоять из конечного числа перечисляемых значений, т.е. быть уточненным, перечисляемым, символьным или булевским типом. В языках линии Паскаль допускается и неявное определение уточненного типа массива. Например, допустимы следующие определения типа массива: type T=array [1..6] of integer или type T= array [' a ..' e '] of real . Если мощность множества значений типа индекса есть n, то значение типа массива — это регулярная структура, включающая п элементов базового типа. Соответствующим образом устроены и переменные типа массива. Для любого сконструированного типа массива предопределены две операции — операция конструирования значения типа массива и операция выборки элемента массива. Если х — переменная типа массива Т , a i— значение соответствующего типа индекса, то для конструирования значения используется языковое средство х : =Т ( c1, с2 , ..., с n), где c1, с2 , ...,сп—значения базового типа. Для выборки элемента массива используется конструкция x[ i], значением которой является значение i -того элемента массива (вместо i в квадратных скобках может содержаться любое допустимое выражение, значение которого принадлежит множеству значений типа индекса). Эта же конструкция может использоваться в левой части оператора присваивания, т.е. элементы массива могут изменяться индивидуально. Кроме того, при подобной строгой типизации массивов допустимы присваивания значений переменных типа массива, функции, возвращающие значение типа массива и т.п. Базовым типом типа массива может быть любой встроенный или определенный тип, в том числе и тип массива. В последнем случае говорят о многомерных массивах или матрицах. Для работы с многомерными массивами в языках используют сокращенную запись. Например. вместо определенияtype T=array [1..10] of array [1..5] of real можно написать type T=array [1..10], [1..5] of real , а если x— переменная такого типа Т , то для выборки скалярного элемента вместо x[ i][ j] можно написать x[ i,j]. В сильно типизированных языках для любого значения типа массива известно число элементов базового типа. Поэтому в принципе всегда возможен контроль значения индекса, хотя на практике такой контроль обычно отменяется при использовании программы в производственном режиме. Для иллюстрации приемов работы с массивами в слабо типизированных языках используем язык Си В этом языке нет средств определения типов массива, хотя имеется возможность определения «массивных переменных». Число элементов в массивной переменной определяется либо явно, либо с помощью задания списка инициализирующих значений базового типа. Например, массивную переменную с четырьмя элементами целого типа можно определить какint х[4] (неинициализированный вариант) или как int х[] = {0, 2,8, 22} (инициализированная массивная переменная). Доступ к элементам массивной переменной производится с помощью конструкции выбора, по виду аналогичной соответствующей конструкции в сильно типизированных языках x[ i], гдеi—выражение, принимающее целое значение (мы специально отметили внешний характер аналогии, поскольку в отличие от языка Паскаль в языке Си зафиксирована интерпретация операции выбора на основе более примитивных операций адресной арифметики). Однако, в реализациях языка Си в принципе невозможен контроль выхода значения индекса за пределы массива. Кроме того, по аналогичным причинам невозможно присваивание значений массивных переменных и не допускаются функции, вырабатывающие «массивные значения». |