16. Структурированные типы данных (массивы, записи, множества, файлы)

Суть всех алгоритмов и комп-х программ состоит в том, что они описы­вают преобр-ние нек. начальных данных в конечные. Какие-то данные алгоритм м. использовать как промежуточные. Тип данных (data type) - множество величин, объединенных опреде­ленной совокупностью допустимых операций. Т.Д. разделены на 2 важные группы: простые и структурированные. переменная простого типа м. хранить единственное значение. Структ-нный набор данных – это Т.д., который строится, исходя из конечного набора базовых типов с помощью операций.Массив (array) – поименованная совокупность однотипных элементов, упорядоченных по индексам, определяющим положение элемента в М-е. Обычный прием работы с М.- выборочное изменение отдельных его компонент. Важной особенностью М-а является его статичность. М. д.б. описан в программе и его характеристики не м.б. из­менены в ходе выполнения программы. Компонентами М-а м.б. не только простейшие данные, но и структурные, в том числе М-ы. Можно представить три способа отведения памяти под элементы. Первый способ заключается в том, что кол-во элементов М-а и способ их индексации фиксируются еще в момент написания прог-­мы. Тогда объекты типа М-а всегда будут занимать одно и то же место в памяти. Второй способ отведе­ния памяти заключается в том, что память под элементы М-а отво­дится индивидуально для каждого объекта типа М-а, причем кол-во элем-ов М-а м.б. вычислено непосредственно пе­ред отведением памяти. В этом случае говорят о динамическом М-е. Третий способ заключается в том, что размер отводимой под М. памяти вообще не фиксируется и может изменяться по ходу работы прог-мы. Такие М-ы м. наз-ть М-ми с гибки­ми границами. Работа с ними требует постоянного перераспределения памяти под уже сущ-щие элементы либо хранения всех эл-­тов отдельно друг от друга, что приводит к сильному замедлению ра­боты при индексации. Для М-а Т определены следующие операции:-создание М-а Т, имеющего N элементов, значения кот-х еще не определены;-"чтение" элемента с заданным индексом i=l,2,....N, результатом кот-го явл-ся элемент T(i), имеющий этот индекс, а также исх­ный М Т;-"замена" элемента, массива с данным индексом i на данный элемент G в результате кот-ой получается новый М, отличающийся от исх-го наличием элемента G на i-ом месте (T(i)=G). Главной особенностью алгоритмов обработки одномерных М-ов явся то, что обработка М-ов д. производиться поэле­ментно. Записи. Запись (record) - это структура данных, состоящая из фиксированного числа разнотипных компонент, называемых полями З-и. Поле (field) - часть З-и, имеющая функционально самостоятельное знач-е и обрабатываемая в программе как отдельный элемент дан­ных. Тип данных З используется для объединения в единый объект разнородной инф-ции. Доступ к любому полю З осуществляется по его имени. Над этим типом данных опр-ется единственная операция - выборка поля. При работе с одной единственной З (что бывает не часто) имя поля м. исп-ть как обычную "переменную, т.е. м. изменять значение поля с помощью операции :=. Если же данная З - лишь часть набора данных, то имя поля состоит из двух частей и называется составным именем поля. И З, и М обладаю общим свойством - произвольным доступом к компонентам. Множество (set) – совок-ть к.-либо объектов, однородных элементов, объединенных общим признаком и представляемых как единое целое. Основ. Операц-ми над МН являются:1.Проверка принадлежности МН-у.2Добавление элемента.3.Исключение элемента. Для МНва резервируется в памяти блок примерно так же как это делается для стека или очереди. Однако вместо того, чтобы хранить элементы МНва в последовательных ячейках внутри бло­ка, они случайным образом рассеиваются по всему блоку. Файлы. Ф - это структура данных, обладающая двумя особенными св-вами: 1. обычно она располагается на к.-нибудь внешнем устрой­стве хранения, и, следовательно, ее размер м.б. значительно больше, чем размеры других типов структур данных; 2. ее время жизни может значительно превышать время выполнения программы, создавшей ее. Наиболее распространенным типом Фов яв-ся последо­вательные Ф, но во многих языках также используются Ф прямого доступа и индексно-последовательные Ф. Две основ­ные задачи, кот-е выполняют Ф, достаточно очевидны - это ввод и вывод инф-ции, Для ввода и вывода данные обычно пред­ст-ся в символьном виде. Компонентами Фов в таком слу­чае становятся отдельные символы, а сам Ф называется тексто­вым Ф. Основные операции над послед. Фми.1. Открытие. Операция открытия получает в качестве параметров имя Ф и режим доступа. Операция открытая запрашивает у операционной системы информацию о расположении и свойствах Ф, отводит требуемый объем памяти для буферов и устанавливает указатель текущей позиции перед первым компонен­том Ф.2.Чтение. Операция чтения передает содержимое текущего ком­понента Ф в определенную переменную программы.3.Запись. Операция записи создает новый компонент в текущей позиции Ф и передает содержимое про­граммной переменной этому новому компоненту.4.Проверка конца Ф. Операция чтения не м.б. выпол­нена, если указатель текущей позиции достиг конца Ф. Посколь­ку длина Ф не фиксирована, требуется проводить явную провер­ку на достижение конца Ф, чтобы программа могла предпринять соответствующие действия в этом случае. 5. Закрытие Ф. Когда обработка Ф завершена, его требует­ся закрыть. Обычно эта операция приводит к передаче сообщения операционной системе о том, что Ф следует отсоединить от про­граммы и возможно, освободить область памяти, которая использовалась для обработки файла. Ф прямого доступа организован так, что возможен доступ к произвольному компоненту Ф так же, как, например, осуществ­ляется доступ к элементам масс-ов или записей. Индекс, исполь­зуемый для доступа к компоненту, обычно называется ключом и м.б. или целым числом, или каким-нибудь идентификатором. Индексно-последовательный Ф похож на Ф прямого дос­тупа, с тем лишь отличием, что для него предусмотрена дополни­тельная возможность последовательного доступа к компонентам, на­чиная с произвольно выбранного. Обычно под графом понимают множество точек, называемых вершинами графа. Дерево – граф в котором каждый узел, кроме корневого, связан не более чем с одним элементом вышестоящего уровня. Вершины представляют данные, ребра – связи между данными.

***

a1 b2 a2 b1

a2 b1 a2 b2

ОБЪЕДИНЕНИЕ. Выполняется для таблиц с одинаковым составом столбцов. В итоговую таблицу с тем же составом столбцов выделяются строки, имеющиеся хотя бы в одной из исходных таблицах. пример: Для таблицы ... и таблицы ... объединением будет таблица

p1 p2 p1 p2 p1 p2

a1 b1 a1 b3 a1 b1

a1 b2 a2 b1 a1 b2

a2 b1 a2 b2 a2 b1

a2 b3 a1 b3

a2 b2

a2 b3

РАЗНОСТЬ. Выполняется для таблиц с одинаковым составом столбцов. В итоговую таблицу с тем же составом столбцов выделяются строки, имеющиеся в первой из исходных таблиц, но не имеющиеся во второй. пример: Для таблицы ... и таблицы ... разностью будет таблица

p1 p2 p1 p2 p1 p2

a1 b1 a1 b3 a1 b1

a1 b2 a2 b1 a1 b2

a2 b1 a2 b2

a2 b3