Сложные типы данных (структуры, объединения, файлы и работа с ними)

Введение
Любая программа, так или иначе, выполняет обработку информации. Информация – это какие-либо данные.Рассмотрим основные сложные типы данных:Массив - это набор из нескольких элементов, которые имеют простой тип данных. Строки. Этот тип данных может хранить только один символ в одной переменной. А чтобы работать сразу с целой строкой, используются строковые типы данных. По сути, строка - это массив символов. Множества, является множеством всевозможных сочетаний объектов исходного порядкового типа.Записи - это набор элементов разных типов. Использование записей - это первый шаг на пути объектно-ориентированного программирования. Файлы используются для хранения данных.Цель работы рассмотреть подробно сложные типы файлов.Исходя из цели были поставлены следующие задачи: 1. Классификация структур данных2. Сложные типы данных в Си63. Сложные типы данных: записи и файлы94. Файлы. Работа с ними.111. Классификация структур данныхНезависимо от содержания и сложности любые данные в памяти ЭВМ представляются последовательностью двоичных разрядов, или битов, а их значениями являются соответствующие двоичные числа. Данные, представленные в таком виде, имеют очень простую организацию или, другими словами, слабо структурированы. Для человека описывать и исследовать сложные данные в терминах последовательностей битов весьма неудобно. Более крупные и содержательные, нежели бит, «строительные блоки» для организации данных получают на основе понятия «структуры данного». Под структурой данных в общем случае понимают множество элементов данных и множество связей между ними. При этом различают физическую и абстрактную структуры данных. Понятие физическая структура данных отражает способ физического представления данных в памяти машины и называется еще структурой хранения, внутренней структурой или структурой памяти. Рассмотрение структуры данных без учета ее представления в машинной памяти называется абстрактной или логической структурой. Рисунок 1 – Классификация структур данныхРазличаются простые (базовые) структуры данных и сложные (интегрированные). Простыми называются такие структуры данных, которые не могут быть расчленены на составные части, большие, чем биты. Сложными называются такие структуры данных, составными частями которых являются другие структуры данных - простые или в свою очередь сложные. Сложные структуры данных конструируются программистом с использованием средств интеграции данных, предоставляемых языками программирования. Одним из важных признак структуры данных является ее изменчивость - изменение числа элементов и (или) связей между элементами структуры. По признаку изменчивости различают структуры статические, полустатические, динамические.В зависимости от отсутствия или наличия явно заданных связей между элементами данных следует различать несвязные структуры (векторы, массивы, строки, стеки, очереди) и связные структуры (связные списки). Важный признак структуры данных - характер упорядоченности ее элементов. По этому признаку структуры можно делить на линейные и нелинейные структуры. В зависимости от характера взаимного расположения элементов в памяти линейные структуры можно разделить на структуры с последовательным распределением элементов в памяти (векторы, строки, массивы, стеки, очереди) и структуры с произвольным связным распределением элементов в памяти (односвязные, двусвязные списки). Пример нелинейных структур - многосвязные списки, деревья, графы. Базовые структуры данных, статические, полустатические и динамические характерны для оперативной памяти и часто называются оперативными структурами.2. Сложные типы данных в СиСтруктура — это объединение нескольких объектов, возможно, различного типа под одним именем, которое является типом структуры. В качестве объектов могут выступать переменные, массивы, указатели и другие структуры.Структуры позволяют трактовать группу связанных между собой объектов не как множество отдельных элементов, а как единое целое. Структура представляет собой сложный тип данных, составленный из простых типов.Рисунок 2 – Общая форма объявления структурыПосле закрывающей фигурной скобки } в объявлении структуры обязательно ставится точка с запятой.Рисунок 3 - Пример объявления структурыПри объявлении структур, их разрешается вкладывать одну в другую.Инициализация полей структуры может осуществляться двумя способами:- присвоение значений элементам структуры в процессе объявления переменной, относящейся к типу структуры;-присвоение начальных значений элементам структуры с использованием функций ввода-вывода (например, printf() и scanf()).В первом способе инициализация осуществляется по следующей форме:struct ИмяСтруктуры ИмяПеременной={ЗначениеЭлемента1, ЗначениеЭлемента_2, . . . , ЗначениеЭлементаn};Имя элемента структуры является составным. Для обращения к элементу структуры нужно указать имя структуры и имя самого элемента. Они разделяются точкой.Второй способ инициализации объектов языка Си с использованием функций ввода-вывода.Имя структурной переменной может быть указано при объявлении структуры. В этом случае оно размещается после закрывающей фигурной скобки }. Область видимости такой структурной переменной будет определяться местом описания структуры.Поля приведенной структурной переменной: number.real, number.imag .ОбъединенияОбъединениями называют сложный тип данных, позволяющий размещать в одном и том же месте оперативной памяти данные различных типов.Размер оперативной памяти, требуемый для хранения объединений, определяется размером памяти, необходимым для размещения данных того типа, который требует максимального количества байт.Когда используется элемент меньшей длины, чем наиболее длинный элемент объединения, то этот элемент использует только часть отведенной памяти. Все элементы объединения хранятся в одной и той же области памяти, начиная с одного адреса.Объединения применяются для следующих целей:- для инициализации объекта, если в каждый момент времени только один из многих объектов является активным;- для интерпретации представления одного типа данных в виде другого типа.Например, удобно использовать объединения, когда необходимо вещественное число типа float представить в виде совокупности байтов.Используя структуры, можно упаковать целочисленные компоненты еще более плотно, чем это было сделано с использованием массива.Набор разрядов целого числа можно разбить на битовые поля, каждое из которых выделяется для определенной переменной. При работе с битовыми полями количество битов, выделяемое для хранения каждого поля отделяется от имени двоеточием.При работе с битовыми полями нужно внимательно следить за тем, чтобы значение переменной не потребовало памяти больше, чем под неё выделено.3. Сложные типы данных: записи и файлыЗначениями так называемого комбинированного типа данных являются записи. Комби­нированный тип задает образ структуры объекта - данного этого типа, каждая часть кото­рой (поле) может иметь совершенно различные характеристики.Таким образом, запись - это набор разнотипных данных, объединенных общим именем. Более формально, запись содержит определенное число компонент, называемых полями.В определении типа записи задается имя и тип каждого поля записи:<комбинированный тип>::= Record < список описаний полей > End<список полей>::= <фиксир. часть> | <фиксир. часть>;<вариант. часть> | <вариант. часть><фиксированная часть>::= <секция записи> {,<секция записи>}< секция записи >::= <имя поля>{,<имя поля>}:< тип > <пусто>Синтаксис записей, содержащих вариантную часть - записей с вариантами - мы опреде­лим ниже. Соответствующие синтаксические диаграммы записей с вариантами:- Комбинированный тип;- Фиксированная секция часть записи.Синтаксис комбинированного типа включает и вариантную часть, предполагающую, что можно определить тип, содержащий определения нескольких вариантов структуры.Синтаксис вариантной части:<вариантная часть >::= case <поле признака> <имя типа> of < вариант >{;<вариант>}<вариант>::=<список меток варианта>:(<список полей>) _ <пусто><список меток варианта>::=<метка варианта>{;<метка варианта>}<метка варианта>::=<константа><поле признака>::=<имя>:<пусто>Соответствующие синтаксические диаграммы:Рисунок 4 – синтаксические диаграммыЕсли A - переменная типа Student из примера 1, ee значение можно изменить группой операторов:A.F1 := 'Иванов '; A.F2 := 'Илья '; A.F3 := 'Иннокентьевич ';A.Day := 14; A.Month := 9; A.Year := 1976;A.StudDoc := 123;Приведенные выше обозначения можно сократить с помощью оператора присоединения. Заголовок этого оператора открывает область действия "внутренних" имен полей записи, которые могут быть использованы как имена переменных. Оператор присоединения имеет вид:With <переменная-запись> {,<переменная-запись>} do <оператор>Значением строкового типа данных являются строки. Стандарт языка предусматривает использование строк только как констант, используемых в операторах вывода Write, Writeln. В расширении языка Turbo-Pascal строковый тип данных определен гораздо полнее.Определение строкового типа следует диаграмме:Здесь целое принадлежит диапазону 1..255 и означает максимальное количество символов в строке этого типа. Если описание типа String используется без указания максимального количества символов, это (по умолчанию) означает, что под этот тип резервируется 255 символов.4. Файлы. Работа с ними.Программа, написанная на языке Pascal, должна каким-то образом обмениваться данными с внешними устройствами (получать данные с клавиатуры, магнитного диска, выводить данные на экран, принтер и т.д.) Для работы с внешними устройствами используются файлы. Файлы - это значения файлового типа данных - еще одного стандартного сложного типа в языке.(Последовательный) файл - это последовательность однотипных компонент, снабженная признаком конца и обрабатываемая последовательно - от начала к концу.Порядок компонент определяется самой последовательностью, подобно тому, как порядок следования очередного кадра кинофильма определяется его расположением на кинопленке. В любой момент времени доступен только один элемент файла (кадр кинофильма). Другие компоненты доступны только путем последовательного продвижения по файлу.В результате выполнения программы происходит преобразование одного текстового файла (называемого Input) в другой текстовый файл (называемый Output). Оба эти файла являются стандартными и служат для ввода/вывода данных.Над файлами можно выполнять два явных вида действий:1.Просмотр (чтение) файла.2.Создание (запись) файла - выполняется путем добавления новых компонент в конец первоначально пустого файла.Файлы, с которыми работает программа, должны быть описаны в программе. Часть фай­лов (представляющих собой физические устройства) имеет в операционной системе стандартные имена. Например, для чтения данных с клавиатуры и вывода результатов на экран мони­тора мы пользуемся стандартными файлами Input и Output. Файл - принтер имеет имя Prn:Имена нестандартных файлов, используемых в программе, необходимо описывать в разделе переменных. Описание файлового типа соответствует диаграмме:Файл, компоненты которого являются символами, называется текстовым и имеет стандартный тип Text:Type Text = File of Char;Для работы с нестандартными файлами имя файла должно быть отождествлено с реально существующим объектом - внешним устройством. Именно, если нам необходимо обработать данные из файла, находящегося на магнитном диске и имеющего (внешнее) имя D:\ExtName.dat, мы должны сообщить системе, что работая с файлом IntName (читая из него данные или записывая в него данные), мы работаем с файлом ExtName.dat, находящимся на диске D:.Для отождествления внутреннего имени файла со внешним именем используется процедура Assign(< внутреннее имя >, < 'внешнее имя'>).После того, как имя файла описано и определено, можно приступить к работе с файлом. При использoвании нестандартных файлов следует помнить, что перед работой необходимо открыть их, т.е. сделать доступными из программы. Для этого нужно применить одну из двух следующих процедур:Процедура Rewrite(<имя файла>) - открывает файл для записи. Если файл ранее существовал, все данные, хранившиеся в нем, уничтожаются. Файл готов для записи первой компоненты.Процедура Reset(<имя файла>) - открывает файл для чтения. Файл готов для чтения из него первой компоненты.По окончании работы с файлом (на запись) он должен быть закрыт. Для этого используется процедура Close(<имя файла>). Эта процедура выполняет все необходимые машинные манипуляции, обеспечивающие хранение данных в файле.Для обмена данными с файлами используют процедуры Read и Writе.Процедура Read(<имя файла>, <список ввода>) читает данные из файла (по умолчанию имя файла - Input). Список ввода - это список переменных.Процедура Write(<имя файла>, <список вывода>) записывает данные в файл (по умолчанию имя файла - Output). Список вывода - это список выражений.Если F - файл типа Text, то в списке ввода/вывода допустимы переменные/выражения типа Integer, Real, Char, String[N]. В других случаях типы всех компонент списка должны совпадать с типом компоненты файла.При работе с файлами применяют стандартные логические функции:Eof(F) (end of file) - стандартная функция - признак конца файла. Если файла F исчерпан, то Eof(F) = True, в противном случае Eof(F) = False.Eoln(F) (End of line) - стандартная функция - признак конца строки текстового файла. Если строка текстового файла F исчерпана, то Eoln(F) = True, в противном случае Eoln(F) = False. Функция Eoln определена только для файлов типа Text. Обычно в программах используют либо текстовые файлы, либо файлы, компонентами которых являются структурированные данные (например, записи).Следует помнить, что данные файловых типов нельзя использовать в качестве компонент других структур данных. Например, нельзя определить массив, компонентами которого являются файлы, запись, полем которой является файл.Специфика файлового типа, связанная с последовательным доступом к компонентам и расположением файлов на внешних носителях, накладывает жесткие ограничения на способы решения задач обработки файлов. Рассмотрим некоторые такие задачи. Для определенности будем считать, что все файлы имеют тип OurFile из примера 3 и упорядочены по значению ключевого поля Key (ключу).Задача 1. Добавление элемента к файлу. Дан файл F и элемент X типа Component. Расширить F, включив в него компоненту X с сохранением упорядоченности.Возможное решение:Переписывать покомпонентно F в новый файл G до тех пор, пока F^.Key < X.Key ;Записать X в G;Переписать "хвост" файла F в G;Переименовать G в F.Задача 2. Удаление элемента из файла. Дан файл F и число K - значение ключа удаляемых элементов. Сократить F, удалив из него все компоненты с ключом K.Решение аналогично решению задачи 1:Переписывать покомпонентно F в новый файл G до тех пор, пока F^.Key < X.Key ;Пока F^.Key = K читать F;Переписать "хвост" файла F в G;Переименовать G в F.Отметим, что:- Решения этих задач потребовали последовательного поиска места элемента X как компоненты файла. Эффективное решение задачи поиска (например, бинарный поиск) невозможно.- В качестве выходного используется новый файл, поскольку чтение/запись в один и тот же файл невозможно.Упорядоченность компонент файла по одному или нескольким ключевым полям - одно из основных условий эффективной реализации задач обработки файлов. Так, задача распечатки файла в определенном порядке следования компонент, если файл не упорядочен соответствующим образом, решается с помощью многократных просмотров (прогонов) файла. Количество прогонов при этом пропорционально количеству компонент.Отсутствие прямого доступа к компонентам приводит к тому, что рассмотренные выше алгоритмы сортировок массива невозможно эффективно адаптировать для сортировки файла. В отличие от массивов, основные критерии эффективности алгоритма сортировки файла - коли­чес­тво прогонов файлов и количество промежуточных файлов.Так, например, алгоритм сортировки простыми обменами требует N прогонов сортируемо­го файла (N - количество компонент файла). Алгоритм быстрой сортировки вообще не имеет смысла рассматривать, поскольку при его реализации необходимо было бы читать файл от конца к началу!Рассмотрим поэтому новый для нас алгоритм - алгоритм сортировки слиянием, который наиболее эффективен при сортировке файлов и относится к быстрым алгоритмам при сортировке массивов, хотя и требует дополнительной памяти.Пусть сортируемая последовательность F = { f1, ..., fN } представлена в виде двух уже отсортированных половин - F1 и F2. Тогда для сортировки F достаточно слить (т.е. применить аналог алгоритма слияния FileMerge) последовательности F1 и F2 в выходную последовательность G. Поскольку упорядоченные половинки F1 и F2 можно получить с помощью тех же действий, мы можем описать алгоритм сортировки слияниями рекурсивно. При этом, очевидно, необходимо использовать оптимальное количество промежуточных файлов. Поскольку слияния нужно начинать с однокомпонентных файлов, точная реализация описанного алгоритма потребует 2N дополнительных файлов, что, конечно, неприемлемо. Поэтому мы должны использовать один файл для хранения нескольких сливаемых под последовательностей. Задача корректировки файла является одной из основных задач обработки файлов. Рассмотрим ее формулировку:Исходные данные задачи - корректируемый файл F, файл корректировок G. Результат - откорректированный файл H. Будем считать, что файл F имеет тип OurFile. Тогда файл H имеет тот же тип. Файл корректировок G состоит из записей с вариантами:TypeCorСomponent = recordKey: Integer;job: (Include, Change, Exclude); {включить, изменить, исключить}Case job ofInclude, Change: Data: String[20]; Exclude: ()endEnd;CorFile = File of CorComponent;Var G : CorFile;Это означает, что файл корректировок содержит компоненты, которые нужно включить в основной файл, компоненты, которые нужно исключить из файла и компоненты, содержание которых нужно изменить (с учетом содержания как основного файла, так и файла корректировок).Файл F предполагается упорядоченным (по ключу), а файл G, вообще говоря, нет. Результатом должен быть упорядоченный откорректированный файл H.В заключение заметим, что современные ЭВМ редко активно используют внешние носители с последовательным доступом в решениях задач управления базами данных, поэтому структуры данных, в которых хранится информация, как правило, более сложны, чем последовательные файлы.
Заключение
Сложный (составной, композитный) тип - тип данных, объекты (переменные или постоянные) которого имеют внутреннюю структуру, доступную программисту.В разных языках программирования набор базовых сложных типов может несколько отличаться (чаще по названию и деталям реализации).Массив - элементы только однотипные, доступ произвольный;Запись - элементы возможно разных типов, доступ произвольный;Файл - элементы однотипные, доступ последовательный (примечание: не путать с дисковым файлом!).Разумеется, этот список не включает даже всех предопределённых в языках типов, но он отражает большинство моделируемых программистами структур данных.Очень важной идеей, также родившейся на границе 60-70-х годов XX века, является возможность произвольного конструирования нужных структур из небольшого набора предопределённых типов. Чем адекватнее программист смоделировал обрабатываемые данные в рамках такого «конструктора», тем безошибочное и долговечнее будет разработанная программа.
Список использованных источников
1. Балдин, К.В. Информатика для ВУЗов: Учебник / К.В. Балдин, В.Б. Уткин. - М.: Дашков и К, 2016. - 395 c.2. Васильков, А.В. Информатика: Учебное пособие / А.В. Васильков, А.А. Васильков, И.А. Васильков. - М.: Форум, 2017. - 528 c.3. Кузнецов, С. Д. Основы баз данных / С.Д. Кузнецов. - М.: Бином. Лаборатория знаний, Интернет-университет информационных технологий, 2017. - 488 c.4. Остроух, А. В. Ввод и обработка цифровой информации / А.В. Остроух. - М.: Академия, 2016. - 288 c.5. Свиридова, М. Ю. Система управления базами данных Access / М.Ю. Свиридова. - М.: Академия, 2016. - 192 c.6. Фуфаев, Э. В. Базы данных / Э.В. Фуфаев, Д.Э. Фуфаев. - М.: Академия, 2016. - 320 c.7. Хомоненко, А. Работа с базами данных в C++ BUILDER / А. Хомоненко. - М.: Книга по Требованию, 2017. - 488 c.