Структуры данных

В повседневной практике обработки информации мы часто имеем дело с естественно организованными (объединенными) представлениями информации: текстами, списками, таблицами, анкетами. Такие организованные (структурированные) данные во многом облегчают их восприятие и обработку.

Естественная организация данных эффективно отражается в современных языках программирования понятием структур данных.

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

Отличительной особенность хорошо написанных программ является то, что данные в них организованы в определенные, наиболее подходящие для их хранения и обработки структуры, а сами программы являются лишь средством обработки этих структур независимо от их информационного содержания. Проектирование подходящих структур данных для их эффективной обработки программой столь же важно, и занятие это, возможно, более сложное, чем написание собственно операторов программы в соответствии с выбранным алгоритмом их обработки. Хорошо спроектированные структуры данных облегчают и ускоряют их обработку, улучшают понимание самой программы.

К базовым структурамданных в Паскале относятся:

• переменные,

• массивы,

• строки,

• множества,

• записи,

• файлы.

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

Понятие переменныхбыло введено раньше – это структура данных, состоящая из отдельных элементов, каждый из которых имеет имя, тип и конкретное значение.

Массивы

В программировании часто встречаются задачи, связанные с хранением и обработкой большого количества однотипных данных. Например, требуется ввести оценки по информатике для 25 студентов группы ИС-09и определить средний балл. Для решения этой задачи опишем 25 переменных:is09_1, is09_2,is09_3, …, is09_25:

Var is09_1, is09_2, is09_3, …, is09_25: 2..5;

Каждая из них будет соответствовать одному студенту. После этого используем 25 операторов для ввода оценок:

ReadLn(is09_1);

ReadLn(is09_2);

ReadLn(is09_3);

. . . . . . . . . . . . .

ReadLn(is09_25);

И, наконец, определим средний балл:

sr_ball:=(is09_1+is09_2+is09_3+ . . . +is09_25)/25.0;

А что произойдет, если нужно будет решить эту задачу для всего университета? Вводить несколько тысяч переменных?

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

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

Таким образом, массив представляет собой структуру данных, определяемую на основе следующих своих свойств:

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

2. число элементов массива строго фиксировано,

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

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

5. число элементов массива совпадает с общим количеством возможных значений его индексов,

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

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

Массивы можно определить и через понятия математики.

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

МатрицейA_nmназывается таблица чисел, состоящая изn строк иm столбцов.

Каждый элементматрицыa_ijполностью определяется своимииндексами– номерами строки iи столбца j, в которых он расположен.

Количество индексов определяет размерностьматрицы: одномерная (вектор), двумерная, трехмерная и т.д.

Максимальное значение каждого индекса определяет размерматрицы.

В качестве аналога матриц в программировании выступают массивы.

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

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

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

a₁₁ a₁₂ a₁₃ …

a₂₁ a₂₂ a₂₃ …

a₃₁ a₃₂ a₃₃ …

……………………..

Таким образом, двумерный массив полностью соответствует понятию матрицы. В оперативной памяти элементы двумерного массива расположены последовательно, строка за строкой: сначала элементы первой строки, затем второй и так далее: a₁₁, a₁₂, a₁₃,…, a₂₁, a₂₂, a₂₃,…, a₃₁, a₃₂, a₃₃,…Значит, быстрее изменяетсявторойиндекс (номер столбца), чемпервый(номер строки).

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

Массив как структура данных характеризуется тем, что с помощью индексов обеспечивается прямой(непосредственный) доступ к каждому его элементу: чтение или запись любого элемента массива не зависит от того, прочитаны или записаны предшествующие ему элементы.

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

Индексы элементов массива могут быть не только целыми положительными числами, но и данными любого упорядоченноготипа (интервального, перечисляемого, символьного, строкового).

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

Пусть имеется целочисленный массив A₂₃, состоящий из следующих элементов:

-5 8 0

9 -1 4

Описание массива можно произвести несколькими способами:

а)в разделе описания переменных: