ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.03.2021
Просмотров: 6597
Скачиваний: 50
66
Таблица 1.9 Таблица истинности для логических операций
А
В
«и»
«или»
«не»
(A and В)
(A and В)
(not А)
И
И
И
И
Л
И
Л
Л
И
Л
Л
И
Л
И
И
Л
Л
И
Л
И
Часто при решении задач оказываются полезными определенные разработчиком типы дан-
ных, представляющие собой перечисление некоторых констант или ограниченный с обеих сторон
диапазон определенных ранее данных. Например, создается тип данных из двух символов
'а'
и '
b
'
или из целых чисел в диапазоне от 1 до 100 и т. д.
9.3. СТРУКТУРИРОВАННЫЕ ТИПЫ ДАННЫХ
Описанные выше типы данных называют простыми. Основной признак, по которому мож-
но определить величину простого типа, таков: одно имя - одно значение.
Значительно большие возможности заключают в себе структурированные данные, опреде-
ляемые разработчиком программы (в пределах возможностей используемого им языка програм-
мирования), К структурированию данных разработчика программы толкает как логика прикладной
задачи, так и чисто утилитарное соображение: при наличии в задаче большого количества вход-
ных и выходных данных отдельное именование каждого из них может оказаться практически не-
возможным.
Разумеется, действия разработчика алгоритма и программы ограничены возможностями то-
го языка программирования, на который он ориентируется. В разных языках возможности струк-
туризации переменных на уровне сложных структур не совпадают, но многие структуры давно
стали традиционными и реализованы в большинстве практически используемых языков програм-
мирования.
Структурированные типы данных классифицируют по следующим основным признакам:
однородная - неоднородная, упорядоченная - неупорядоченная, прямой доступ - последователь-
ный доступ, статическая - динамическая. Эти признаки противостоят друг другу лишь внутри па-
ры, а вне этого могут сочетаться.
Если все элементы, образующие структуру, однотипны (например - целые числа или сим-
волы), то структура является однородной; если же в ней «перепутаны» элементы разной природы
(например, числа чередуются с символами), то неоднородной.
Структуру называют
упорядоченной,
если, между ее элементами определен порядок сле-
дования. Примером упорядоченной математической структуры служит числовая последователь-
ность, в которой у каждого элемента (кроме первого) есть предыдущий и последующий. Наличие
индекса в записи элементов структуры уже указывает на ее упорядоченность (хотя индекс для это-
го не является обязательным признаком).
По способу доступа упорядоченные структуры бывают прямого и последовательного дос-
тупа. При прямом доступе каждый элемент структуры доступен пользователю в любой момент
независимо от других элементов. Глядя на линейную таблицу чисел мы можем списать или заме-
нить сразу, допустим, десятый элемент. Однако, если эта таблица не на бумаге, а, скажем, каким-
то образом записана на магнитофонную ленту, то сразу десятое число нам недоступно - надо сна-
чала извлечь девять предшествующих. В последнем случае мы имеем дело с последовательным
доступом.
Если у структуры размер (длина, количество элементов) не может быть изменен «на ходу»,
а фиксирован заранее, то такую структуру называют статической. Программные средства инфор-
матики иногда позволяют не фиксировать размер структуры, а устанавливать его по ходу решения
задачи и менять при необходимости, что бывает очень удобно. Такую структуру называют дина-
мической. Например, при описании закономерностей движения очереди в магазине мы не знаем
заранее, сколько человек в ней будет в тот или иной момент, и соответствующую структуру дан-
67
ных (например, список фамилий участников очереди) лучше представлять динамической.
Массивы
Самым традиционным и широко известным из структурированных типов данных является
массив
(иначе называемый регулярным типом) - однородная упорядоченная статическая структу-
ра прямого доступа.
Массивом называют однородный набор величин одного и того же типа, называемых ком-
понентами массива, объединенных одним общим именем (
идентификатором
) и идентифицируе-
мых (адресуемых) вычисляемым
индексом.
Это определение подчеркивает, что все однотипные
компоненты массива имеют одно и то же имя, но различаются по индексам, которые могут иметь
характер целых чисел из некоторого диапазона, литер, перечисленных констант. Индексы позво-
ляют адресовать компоненты массива, т.е. получить доступ в произвольный момент времени к
любой из них как к одиночной переменной (рис. 1.32). Обычный прием работы с массивом - выбо-
рочное изменение отдельных его компоневт.
Вычисляемые индексы позволяют использовать единое обозначение элементов массива для
описания массовых однотипных операций в циклических конструкциях программ. Важной осо-
бенностью массива является его статичность. Массив должен быть описан в программе (т.е. опре-
делены тип и число компонент) и его характеристики не могут быть изменены в ходе выполнения
программы.
Рис. 1.32.
Одномерный массив - набор элементов (компонентов)
Компонентами массива могут быть не только простейшие данные, но и структурные, в том
числе массивы. В этом случае мы получаем массив массивов - многомерный
массив.
Для индек-
сации элементарных компонент в этом случае может потребоваться два, три и более индексов.
В некоторых системах программирования существуют специальные виды массивов. На-
пример, массив литер (символов) определяется как строка.
Данные, хранящиеся в массивах, находятся в оперативной памяти компьютера. Это, с од-
ной стороны, ускоряет доступ к ним в ходе решения задачи, а с другой -налагает ограничения на
объем возможной информации, организованной в виде массивов. Не следует поэтому, без крайней
необходимости, создавать новые массивы для перемещения данных из уже существующих масси-
вов.
Рассмотрим в качестве примера задачу сортировки набора некоторых данных, для которых
имеют смысл отношения «больше» или «меньше». Представьте себе, что надо карточки в картоте-
ке разместить в порядке возрастания записанных на них чисел. Используем для сортировки набора
чисел (т.е. записи их в порядке возрастания) одномерный (линейный) массив. Дадим ему
имя
А,
тогда
a
1
, a
2
,
a
3
,...,
а
n
-
компоненты массива.
Существует огромное число методов сортировки массивов. Рассмотрим один из самых про-
стых (но не самых быстрых) - метод выбора.
В начале процесса имеем заполненный числами массив (неотсортированный). Процесс сор-
тировки строится по индукции. Допустим, мы уже отсортировали часть массива и имеем упорядо-
ченную последовательность
a
1
<
a
2
< … <
a
i-l
и оставшуюся неотсортированной последовательность
a
i
, a
i+1
,… a
N
.
68
При каждом шаге, начиная с
i =
1, из неотсортированной части последовательности извле-
кается наименьший элемент
х
=
a
i
, и меняется местами с
i
-м элементом. Затем этот процесс повто-
ряется для
i
= 2,
i
= 3 и т.д., до тех пор пока не останется один, самый большой элемент.
Этот алгоритм потребует многократного нахождения наименьшего элемента массива. Этот
«вспомогательный» алгоритм поиска наименьшего среди
а
i
, ... , а
N
может быть следующим:
1) фиксируется в качестве значения вспомогательной переменной
т
первый слева элемент
массива:
т = а
i
(в конце процесса
т
будет иметь значение наименьшего элемента);
2) выполняется сравнение
т с
элементом массива
a
j
, (начиная с номера
j = i + 1
) и, если
a
j
<
т,
то
т
заменяется на
а
j
;
3) далее выполняется сравнение
т
с очередным элементом массива, т.е.
j
увеличивается на
единицу и шаги 2, 3 выполняются снова, до тех пор пока у не достигнет максимального значения
индекса элемента массива.
После выполнения этих предписаний переменная
т
будет соответствовать наименьшему
элементу массива.
Двумерный массив визуально представляется плоской таблицей, табл. 1.10. При наличии
одного имени (идентификатора) для всех компонентов каждый из них фиксируется значениями
двух индексов, указывающих номер строки и номер столбца, на пересечении которых находится
эта компонента.
Рассмотрим пример обработки данных, хранящихся в двумерном массиве. Допустим, что
на некоторой территории (например, страны) «квадратно-гнездовым» способом расставлены тем-
пературные датчики, и их показания обраны в одном центре (что вполне близко к реальной дея-
тельности метеослужбы). Тогда в таблицу - двумерный массив - попадут значения температуры
t
ij
в сответствующих точках. Требуется, просматривая таблицу построчно, найти те точки (т.е. ин-
дексы узлов), между которыми температура принимает некоторое заданное значение
Т.
Таблица 1.10 Графический образ двумерного массива
i j
1
2
3
4
…
1
a
11
a
12
a
13
a
14
…
2
a
21
a
22
a
23
a
24
…
3
a
31
a
32
a
33
a
34
…
4
a
41
a
42
a
43
a
44
…
…
…
…
…
...
…
Пусть в таблице
п
строк и
т
столбцов. Вспомогательным алгоритмом в данной задаче мо-
жет быть алгоритм поиска нужных узлов в одной строке. Пусть эта строка имеет номер
k.
Алго-
ритмы записаны без комментариев для самостоятельного разбора.
Вспомогательный алгоритм (k):
1) положить
j
= 1;
2) если
t
k,j
< T < t
k.j+1
, то см. п. 2;
3) увеличить
j
на 1,
4) если
j
<
m,
то вернуться к п. 2;
5) задача решена, ответ:
(k,j), (k,j
+ 1);
6)конец.
Основной алгоритм:
1) положить
k=
1;
2) выполнить вспомогательный алгоритм (
K
);
3) увеличить
k
на 1;
4) если
k > n,
то вернуться к п.2;
5)конец.
69
Записи, множества, файлы
Обобщением массива является комбинированный тип данных -
запись
, являющаяся неод-
нородной упорядоченной статической структурой прямого доступа. Запись есть набор именован-
ных компонент -
полей
(часто разного типа), объединенных одним общим именем и идентифици-
руемых (адресуемых) с помощью как имени записи, так и имен полей, рис. 1.33.
Рис. 1.33.
Иллюстрация «записи».
Запись
В
состоит из трех полей, имеющих последовательно типы «текст», «целое число»,
«вещественное число»: 1-е поле - название детали, 2-е - условный номер по каталогу, 3-е - длина.
При работе с одной единственной записью (что бывает нечасто), имя поля можно использовать
как обычную переменную, т.е. можно изменять значение поля с помощью операции присваивания
или любых других операций, доступных над величинами данного типа. Если же данная запись -
лишь часть набора данных, то имя поля состоит из двух частей и называется
составным именем
поля
(на рис. 1.33 составные имена В. name, В. number, В. length).
Для облегчения работы с полями в различных языках программирования существуют сред-
ства, облегчающие их адресацию.
И записи, и массивы обладают одним общим свойством - произвольным доступом к компо-
нентам. Записи более универсальны в том смысле, что для них не требуется идентичности типов
их компонент. Массивы обеспечивают большую гибкость -индексы их компонент можно вычис-
лять в отличие от имен полей записей.
Существенно иные возможности дает структура данных, моделирующая свойства
мате
ма-
тического объекта - множества.
Над множеством могут быть выполнены следующие операции:
1) объединение множеств (операция сложения '+');
2) пересечение множеств (операция умножения '*');
3) теоретико-множественная разность (вычитание множеств '-');
4) проверка принадлежности элемента множеству.
Различия между множеством и массивом очень существенны: размер множества заранее не
оговаривается (хотя и ограничен компьютерной реализацией, например, 255), не существует иного
способа доступа к элементам множества, кроме как проверкой принадлежности множеству.
Более сложной, чем рассмотренные выше из предусмотренных в современных системах
программирования структур данных, является очередь (
файл
).
Понятие «файл» при всей своей привычности употребляется в информатике в нескольких
не совсем совпадающих смыслах. Здесь мы остановимся лишь на представлении о файле как од-
нородной упорядоченной динамической структуре последовательного доступа - очереди.
Очередь
есть линейно упорядоченный набор следующих друг за другом компонент, доступ
к которым происходит по следующим правилам:
1) новые компоненты могут добавляться лишь в хвост очереди;
2) значения компонент могут читаться (извлекаться) лишь в порядке следования компонент
от головы к хвосту очереди.
Размер очереди заранее не оговаривается и теоретически может считаться бесконечным.
Для запоминания (хранения) компонент очереди часто используют внешние запоминающие уст-
ройства большой емкости - магнитные диски и ленты. Отсюда другое название очереди - файл (по
английски это слово имеет ряд значений, в том числе «картотека», «шеренга», «очередь»).
Исторически слово «файл» стало впервые применяться в информатике для обозначения по-
70
следовательного набора каких-либо данных или команд (программа), хранящихся на внешнем за-
поминающем устройстве. Несколько позже были осознаны абстрактные, не зависящие от магнит-
ных дисков и лент, свойства очереди как структуры данных, полезные при решении многих задач
обработки - информации. Такой принцип извлечения и добавления компонент к очереди часто
;
называется «первым вошел - первым вышел» (английская аббревиатура - «FIFO»), рис. 1.34.
Рис. 1.34.
Иллюстрация «очереди»
В языках программирования существуют и такие разновидности файлов, которые не под-
чиняются условию последовательности доступа к его компонентам (так называемые, файлы пря-
мого доступа). Они уже не являются очередями.
Суперпозиция структур данных
Из рассмотренных структур данных можно создавать различные суперпозиции (вопрос о
допустимости той или иной суперпозиции в конкретном языке программирования следует искать
в его описании).
Рассмотрим в качестве примера такую часто используемую суперпозицию как
файл запи-
сей
-
обычную, например, при создании баз данных. Итак, имеется файл по имени F, содержащий
некоторое количество таких записей, как на рис. 1.30. Составим алгоритм подсчета количества
болтов, у которых длина (length) заключена в пределах от 3 до 40:
1) положить
k =
0 (в конце работы
k -
число искомых болтов);
2) прочесть первую запись из файла;
3) если В.name = 'болт' и 30 < B.lenght < 40, то увеличить
k
на 1;
4) если файл уже опустел, то идти к п. 7, иначе - к п. 5;
5) прочесть следующую запись из файла;
6) идти к п.З;
7) конец работы;
k -
число
искомых болтов.
Стек
Существует (и часто используется) и другая структура данных, в которой тот элемент, ко-
торый первый в нее помещался, выходит последним и, наоборот, тот, который последним входит,
выходит первым (английская аббревиатура «LIFO»). Такая структура получила название
стек
(или
магазин - по сходству с магазином стрелкового оружия), рис. 1.35.
Рис. 1 35.
Иллюстрация «стека»
Стеки и принцип LIFO находят очень широкое применение в информатике. Рассмотрим в
качестве примера использование стека при вычислении значения арифметического выражения.
Вычисление значения выражения требует соблюдения старшинства операций. Операции по
старшинству при вычислении значений математических выражений располагаются в следующем
порядке: вычисление значений функций (включая возведения в степень), умножения и деления,
сложения и вычитания. Изменить такой «естественный» порядок операций можно с помощью