Тема № 2. Алгоритмы для работы с простыми и структурированными данными

Каждая программа зависит от алгоритмов и структур данных, но редко бывает нужно изобретать новые алгоритмы. Даже в сложной программе, например в компиляторе или Web-браузере, структуры данных по большей части являются массивами, списками, деревьями и хэш-таблицами. Когда программе нужна более изощренная структура, она, скорее всего, будет основываться на этих более простых структурах. Соответственно, задача программиста — знать, какие алгоритмы и структуры доступны, а также понимать, как выбрать среди них нужные. Есть лишь горстка основных алгоритмов, которые применяются практически в каждой программе, — это, прежде всего, поиск и сортировка, и даже эти алгоритмы зачастую включены в библиотеки. Почти все структуры данных также сделаны на основе нескольких фундаментальных структур.

Алгоритм, реализующий решение некоторой конкретной задачи, всегда работает с данными.

Данные – это любая информация, представленная в формализованном виде и пригодная для обработки алгоритмом.

Данные делятся на переменные и константы.

Переменные – это такие данные, которые могут изменять свои значения в процессе выполнения алгоритмов.

Константы – это данные, значения которых не изменяются в процессе работы алгоритма.

С данными тесно связано понятие типа данных. Тип данных характеризует множество значений, к которым относится константа и которые может принимать переменная. Данные представляют реальные объекты, при этом некоторые характеристики объекта игнорируются. Решая конкретную задачу, необходимо выбрать множество данных, способ представления данных, методы и операции обработки данных. Представление данных определяется средствами и возможностями компьютера или его программным обеспечением и другими устройствами.

Типы данных принято делить на простые и структурированные.

В математике принято классифицировать величины в соответствии с их характеристиками: вещественные, целые и т.д. В информатике любая константа, переменная, выражение или функция относится к определенному типу. Тип – определяет множество значений, которые может принимать const, выражение, функция.

С простыми данными выполняются операции: сложение, вычитание, умножение, деление. Логические величины имеют два значения (правда и ложь), их основными операциями являются: дизъюнкция, конъюнкция, инверсия.

Структурированные типы описывают наборы однотипных или разнотипных данных, с которыми алгоритм должен работать, как с одной именованной переменной.

Основным признаком, по которому определяют величину простого типа – “одно имя – одно значение”. Структурированные типы данных представляют собой простые данные, организованные в структуры. Их классифицируют по следующим признакам:

1. однородные и неоднородные структуры.

2. упорядоченные и неупорядоченные.

3. структуры прямого и последовательного доступа.

4. динамические и статические структуры.

Структура называется однородной, если элементы, образующие эту структуру, являются однотипными. Если элементы разной природы, то структура называется неоднородной.

Структура называется упорядоченной, если между ее элементами определен порядок следования. Если четкого порядка нет, то структура неупорядоченная.

Если любой элемент структуры доступен в любой момент независимо от других элементов, она называется структурой прямого доступа. Если каждый элемент просматривается в порядке следования, это структура последовательного доступа.

Если у структуры размер фиксируется заранее, структура называется постоянной или статической. Если во время решения задачи размер структуры требуется изменить, она называется динамической.

Каждая из величин называется компонентом массива. Каждый компонент идентифицируется вычислительным индексом. Массивы бывают: одномерные, двумерные, многомерные.

Массив – это однородная упорядоченная статическая структура прямого доступа.

Одномерный массив – линейная последовательность, записываемая в виде строки или столбца. Двумерный массив – таблица. Многомерный массив – числовая последовательность, адресуемая большим количеством строчек и большим количеством столбцов.

Обобщение массива – комбинированный тип данных – это запись.

Запись - это набор именованных компонентов (полей) объединенных общим именем, адресуемых именем записи и именем поля. При работе с одной записью имя поля используется как отдельная переменная. Если данная запись часть набора данных. Имя поля состоит из 2-х частей и называется составным именем поля.

Запись – это комбинированный тип данных, являющийся неоднородной упорядоченной статической структурой прямого доступа.

Для удобства обработки информация часто сводится в линейные или прямоугольные таблицы. Тогда обработка сводится к поиску в таблице нужного элемента, записи в таблицу новых элементов, изменения порядка элементов в таблице и т. п. Преимущества ЭВМ перед другими исполнителями алгоритма и состоят в том, что ЭВМ может решать задачи по обработке таблиц, содержащих десятки и сотни тысяч элементов, достаточно быстро и тем самым освобождать человека от утомительной и непродуктивной (рутинной) работы.

Табличными называются величины, записанные в виде таблицы. Значением такой величины является содержимое ячейки таблицы. В алгоритмах обязательно указание типа величины и размерности таблицы.

вещтаб А[1:n] – означает задание вещественной линейной таблицы А размерности n.