Глава 7. Структурированные типы данных
Под структурой данных типа массив понимают совокупность индексированных упорядоченных однотипных элементов, имеющих общее имя. Массивы используются для хранения однородной по составу информации: элементов таблиц, коэффициентов уравнений, матриц. Элементами массива могут быть данные различных типов, включая структурированные. каждый элемент массива однозначно определяется именем массива и индексом(номером этого элемента в массиве) или индексами, если массив многомерный.
Количество индексных позиций определяет размерность массива (одномерный, двумерный и т.д.). Индексы элементов массива должны принадлежать порядковому типу.
К типовым операциям с массивами относятся:
7.1.1. Одномерный массив Объявление массива.Перед использованием массив, как и любая переменная, должен быть объявлен в разделе объявления переменных. В общем виде объявление массива выглядит так:
Имя: аrrау [нижний индекс ..верхний индекс]ofТип;
где Имя — имя переменной-массива;
аrrау —ключевое слово, обозначающее, что переменная является
нижний_индексиверхний_индекс —целые числа, определяющие диапазон изменения индексов (номеров) элементов массива и, неявно, количество
Тип — тип элементов массива.
Объявление массива осуществляется одним из следующих способов:
a) в разделе описания переменных
a : array [1..5] of byte;
b : array [1..3] of integer;
z : array [‘d’..’g’] of char;
name:array[1..30]of string[25];
б) с помощью типизированной переменной
mar =array[1..5] of byte;
При описании массивов в программе удобно использовать именованные константы как значения верхних границ индексов массива.
Именованная константа объявляется в разделе описания констант, который располагают перед разделом объявления переменных. Начинается раздел объявления констант словом const.
b : array [1..n ] of integer;
temp: array[1..s] of string[25];
Каждая отдельная величина массива называется элементом. Тип элементов может быть любым, принятым в языке Pascal, кроме файлового типа.
Тип элементов называется базовым типом. Вся совокупность элементов определяется одним именем. Для обозначения отдельных элементов массива используется конструкция, называемая переменной с индексом или с индексами: a[5]s[k+1]b[3,5]
Чтобы использовать элемент массива, нужно указать имя массива и индекс элемента. Первый индекс обычно соответствует номеру строки таблицы второй — номеру колонки.
В качестве индекса может быть использовано выражение. Тип индексов может быть только целым, интервальным или перечисляемым b. Индексы интервального типа, для которого базовым является целый тип, могут принимать отрицательные, нулевое и положительные значения.
Ввод массива. Под вводом массива понимается ввод значений элементов массива. Для ввода или вывода массива в список ввода или вывода помещается переменная с индексом, а операторы ввода или вывода выполняются в цикле.
Чтобы пользователь программы знал, ввода какого элемента массива ожидает программа, следует организовать вывод подсказок перед вводом очередного элемента массива. В подсказке обычно указывают индекс элемента массива. 1
1) Ввод элементов одномерного массива с помощью клавиатуры:
for i:=1 to n do
2) Ввод элементов одномерного массива с помощью типизированных констант.
Ввод элементов массива с помощью констант называется еще инициализацией массива.
A1 : array [1..6] of integer = (-5,8,5,0,7,-8);
A2 : array [ 1..3] of char = (‘a’,’b’,’c’);
Dim10= array[1..10] of Real;
raM10:Dim10 = ( 0, 2.1, 4, 5.65, 6.1, 6.7, 7.2, 8, 8.7, 9.3 );
3) Ввод элементов одномерного массива с помощью датчика случайных чисел
for i:=1 to 10 do
В этом случае значениями элементов массива a[i] будут произвольные значения от 0 до 19 .Для того чтобы получились дробные числа нужно в функцииrandomопустить параметр.
Структурированные типы данных
Структурированный тип данных – тип, характеристиками которого являются: множественность элементов, его структура, способ доступа к элементам, тип элементов и операции с данными этого типа. Множество значений такого типа определяется множеством значений его элементов и их количеством. Переменная или константа структурированного типа всегда имеет несколько компонент. Каждая из этих компонент, в свою очередь, может принадлежать структурированному типу, что позволяет говорить о возможной вложенности типов.
В Турбо Паскале пять структурированных типов:
Структурированные типы данных классифицируют по следующим основным признакам: однородная – неоднородная, упорядоченная – неупорядоченная, прямой доступ – последовательный доступ, статическая – динамическая. Эти признаки противостоят друг другу лишь внутри пары, а вне этого могут сочетаться.
Если все элементы, образующие структуру, однотипны (например – целые числа или символы), то структура является однородной; если же в ней «перепутаны» элементы разной природы (например, числа чередуются с символами), то неоднородной.
Структуру называют упорядоченной, если между ее элементами определен порядок следования. Примером упорядоченной математической структуры служит числовая последовательность, в которой у каждого элемента (кроме первого) есть предыдущий и последующий. Наличие индекса в записи элементов структуры уже указывает на ее упорядоченность (хотя индекс для этого не является обязательным признаком).
По способу доступа упорядоченные структуры бывают прямого и последовательного доступа. При прямом доступе каждый элемент структуры доступен пользователю в любой момент независимо от других элементов. Глядя на линейную таблицу чисел, мы можем списать или заменить сразу, допустим, десятый элемент. Однако, если эта таблица не на бумаге, а, скажем, каким-то образом записана на магнитофонную ленту, то сразу десятое число нам недоступно – надо сначала извлечь девять предшествующих. В последнем случае мы имеем дело с последовательным доступом.
Если у структуры размер (длина, количество элементов) не может быть изменен «на ходу», а фиксирован заранее, то такую структуру называют статической. Программные средства информатики иногда позволяют не фиксировать размер структуры, а устанавливать его по ходу решения задачи и менять при необходимости, что бывает очень удобно. Такую структуру называют динамической.
Самым широко известным из структурированных типов данных является массив (иначе называемый регулярным типом) – однородная упорядоченная статическая структура прямого доступа.
Массивом называют однородный набор величин одного и того же типа, называемых компонентами массива, объединенных одним общим именем (идентификатором) и идентифицируемых (адресуемых) вычисляемым индексом. Это определение подчеркивает, что все однотипные компоненты массива имеют одно и то же имя, но различаются по индексам, которые могут иметь характер целых чисел из некоторого диапазона, литер, перечисленных констант. Индексы позволяют адресовать компоненты массива, т.е. получить доступ в произвольный момент времени к любой из них как к одиночной переменной. Обычный прием работы с массивом – выборочное изменение отдельных его компонент.
Вычисляемые индексы позволяют использовать единое обозначение элементов массива для описания массовых однотипных операций в циклических конструкциях программ. Важной особенностью массива является его статичность. Массив должен быть описан в программе (т.е. определены тип и число компонент) и его характеристики не могут быть изменены в ходе выполнения программы.
Компонентами массива могут быть не только простейшие данные, но и структурные, в том числе массивы. В этом случае мы получаем массив массивов – многомерный массив. Для индексации элементарных компонент в этом случае может потребоваться два, три, и более индексов.
Записи, множества, файлы
Обобщением массива является комбинированный тип данных – запись, являющаяся неоднородной упорядоченной статической структурой прямого доступа. Запись – набор именованных компонент – полей (часто разного типа), объединенных одним общим именем и идентифицируемых (адресуемых) с помощью, как имени записи, так и имен полей.
При работе с одной единственной записью (что бывает нечасто), имя поля можно использовать как обычную переменную, т.е. можно изменять значение поля с помощью операции присваивания или любых других операций, доступных над величинами данного типа. Если же данная запись – лишь часть набора данных, то имя поля состоит из двух частей и называется составным именем поля.
Для облегчения работы с полями в различных языках программирования существуют средства, облегчающие их адресацию.
И записи, и массивы обладают одним общим свойством – произвольным доступом к компонентам. Записи более универсальны в том смысле, что для них не требуется идентичности типов их компонент. Массивы обеспечивают большую гибкость – индексы их компонент можно вычислять в отличие от имен полей записей.
Существенно иные возможности дает структура данных, моделирующая свойства математического объекта – множества.
Над множеством могут быть выполнены следующие операции:
1) объединение множеств (операция сложения ‘+’);
2) пересечение множеств (операция умножения ‘*’);
3) теоретико-множественная разность (вычитание множеств ‘-‘);
4) проверка принадлежности элемента множеству.
Различия между множеством и массивом очень существенны – размер множества заранее не оговаривается (хотя и ограничен компьютерной реализацией, например, 255), не существует иного способа доступа к элементам множества, кроме как проверкой принадлежности множеству.
Более сложной, чем рассмотренные выше, из предусмотренных в современных системах программирования структур данных является очередь (файл).
Понятие «файл» при всей своей привычности употребляется в информатике в нескольких не совсем совпадающих смыслах. Здесь мы остановимся лишь на представлении о файле как однородной упорядоченной динамической структуре последовательного доступа – очереди.
Очередь – это линейно упорядоченный набор следующих друг за другом компонент, доступ к которым происходит по следующим правилам:
1) новые компоненты могут добавляться лишь в «хвост» очереди;
2) значения компонент могут читаться (извлекаться) лишь в порядке следования компонент от «головы» к «хвосту» очереди.
Размер очереди заранее не оговаривается и теоретически может считаться бесконечным. Для запоминания (хранения) компонент очереди часто используют внешние запоминающие устройства большой емкости – магнитные диски и ленты. Отсюда другое название очереди – файл (в английском языке это слово имеет несколько значений, в том числе «картотека», «шеренга», «очередь»).
Исторически слово «файл» стало впервые применяться в информатике для обозначения последовательного набора каких-либо данных или команд (программа), хранящихся на внешнем запоминающем устройстве. Несколько позже были осознаны абстрактные, не зависящие от магнитных дисков и лент, свойства очереди как структуры данных, полезные при решении многих задач обработки информации. Такой принцип извлечения и добавления компонент к очереди часто называется «первым вошел – первым вышел» (английская аббревиатура -«FIFO»)
В языках программирования существуют и такие разновидности файлов, которые не подчиняются условию последовательности доступа к его компонентам (так называемые, файлы прямого доступа). Они уже не являются очередями.
Тест.Понятие алгоритма
- Выберите один из вариантов в каждом из 5 вопросов;
- Нажмите на кнопку «Показать результат»;
- Скрипт не покажет результат, пока Вы не ответите на все вопросы;
- Загляните в окно рядом с номером задания. Если ответ правильный, то там (+). Если Вы ошиблись, там (-).
- За каждый правильный ответ начисляется 1 балл;
- Оценки: менее 2.5 баллов — НЕУДОВЛЕТВОРИТЕЛЬНО, от 2.5 но менее 3.75 — УДОВЛЕТВОРИТЕЛЬНО, 3.75 и менее 5 — ХОРОШО, 5 — ОТЛИЧНО;
- Чтобы сбросить результат тестирования, нажать кнопку «Сбросить ответы»;