После описания массива к нему можно обращаться по заданному имени. А к отдельным элементам массива можно обращаться с помощью целых чисел, которые называются индексами (indices). Они определяют строку и ряд, в котором находится элемент массива. Однако диапазон индексов меняется от языка к языку. Например, в языке Си (и его производных Cи++, Java и Си#) индексы начинаются с 0. То есть элемент, находящийся во второй строке и четвертом столбце массива Scores, можно обозначить с помощью выражения Scores [1] [3], а элемент, расположенный в первой строке и первом столбце, будет обозначаться как Scores [0] [0]. Напротив, в языке FORTRAN индексы начинаются с 1, поэтому элемент, расположенный во второй строке и четвертом столбце, будет обозначаться как Scores (2,4) (рис. 2).
Некоторые языки программирования предоставляют программисту свободу в выборе интервала индексов для однородного массива. Например, выражение Scores: array [3..4. 12..20] of integer:
Рисунок 1 – Двумерный массив, состоящий из двух строк и девяти столбцов
в языке Pascal описывает такой же двумерный массив целых чисел Scores, как и приведенный выше, за исключением того, что строки здесь определены значениями 3 и 4, а столбцы пронумерованы от 12 до 20. Поэтому элемент, расположенный во втором ряду и четвертом столбце, будет обозначаться выражением Scores [4,15].
В отличие от однородного массива, в котором элементы данных относятся к одному типу, неоднородный массив (heterogeneous array) может содержать данные разных типов. Например, совокупность данных о сотруднике компании может состоять из элемента символьного типа Name, элемента целочисленного типа Аgе и элемента вещественного типа Ski11Rating. В языках Pascal и Си (рис. 2) такой тип массива называется соответственно записью (record) и структурой (structure).
Описание неоднородного массива в Pascal
Var
Employee: record
Name: packed array [1..8] of char;
Age: integer;
SkillRating: real
end
Описание неоднородного массива в Си
Struct
{ char Name [8];
int Age:
float SkillRating;
} Employee:
К компоненту неоднородного массива обычно обращаются по имени массива, после которого ставится точка и затем указывается имя этого компонента. Например, к компоненту Age массива Employee (см. рис. 2) можно обратиться с помощью выражения Employee.Age.
Далее мы рассмотрим, как абстрактные структуры, такие как массивы, реализуются в машине. В частности, мы покажем, что данные, которые содержит массив, могут быть разбросаны по оперативной памяти или по запоминающему устройству. Именно поэтому мы рассматриваем структуры
Рисунок 2 – Описание неоднородного массива в языках Pascal и Си
данных, как концептуальную форму упорядочивания данных. На самом деле, расположение данных в запоминающем устройстве машины может совершенно отличаться от их абстрактной структуры.
Оперативная память компьютера организована в виде отдельных ячеек с последовательными адресами. Однако часто бывает удобно представлять эти ячейки в виде других структур данных. Например, записи о продажах за неделю удобно просматривать в табличной форме, где продажи различных элементов в разные дни организованы в набор строк и столбцов. Мы рассмотрим, как создаются подобные абстрактные представления данных. Наша Цель лекции — научиться думать об информации в терминах абстрактной организации, а не сосредотачиваться на фактической структуре данных в оперативной памяти машины.
В изучении структур данных есть три основных аспекта: абстракция, разделение статических и динамических структур и концепция указателей.
Опять абстракция.Конечно, мы уже много раз встречались с понятием абстракции. Но необходимо еще раз обратить внимание на этот момент, так как, говоря о данных, мы говорим об инструментах обобщения. Действительно, структуры данных — это способы ограждения пользователя от деталей фактического устройства данных (ячеек памяти и адресов), чтобы он мог обращаться с информацией так, как если бы она была организована в наиболее удобной для него форме.
Слово пользователь в этом контексте не всегда обозначает человека; значение этого термина зависит от того, с чьей точки зрения мы смотрим на данные. Если представить себя человеком, который хранит в компьютере рекорды лиги боулинга, тогда пользователем будет именно человек. В этом случае приложение, в котором мы работаем, должно уметь представлять данные в абстрактной удобной для человека форме — например, в виде набора таблиц. Если думать о сервере в Интернете, тогда пользователем может быть другой компьютер, играющий роль клиента. Тогда сервер должен представлять данные в абстрактной форме, удобной для этого клиента. В случае же модульной структуры программы мы может считать пользователем отдельный модуль, которому требуется обратиться к данным. В этом случае модуль, содержащий данные, отвечает за представление данных в абстрактной форме, удобной другим модулям.
Общим во всех этих ситуациях является то, что пользователю, независимо от того, кем или чем он на самом деле является, дана привилегия доступа к данным как к абстрактному инструменту. Как сконструированы эти инструменты — это и есть вопрос структуры данных.
