18. Линейный список. Реализация с использованием массивов. Реализация многомерного массива.

 

Одномерные массивы

Одномерный массив — это тип данных с составными значениями. Они составлены из значений простого типа, который называют базовым. Точнее говоря, значениями массива служат последовательности значений базового типа одинаковой длины. Эту длину называют размером массива. Вот как может выглядеть значение массива из пяти целых чисел: (3,8,5,9,4).

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

Переменный массив требует описания:

ARRAY [ тип индекса ] OF базовый тип

тип индекса — любой порядковый тип. Будем задавать тип индекса, указывая начальное и конечное значение отрезка целых чисел. Этот отрезок даст нам необходимое количество номеров для нумерации элементов составного значения, например  отрезок 3. .6 дает номера 3,4,5,6.

Операции над значениями массива — это операции над последовательностями. Разные значения одного массива можно сравнивать и присваивать. Вот несколько результатов сравнения значений массива array [1..5] of integer:

(1,3.5,2,8)  0(1,3,5,2,8)          false

(8,6,3,7,4) < (8,6,4,2,1)          true

(5,2,4,3,9) <= (5,2,1,7,4)        true

(3,5,4,2,1) = (2,6,4.2,1)          false

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

var X: array [0..99] of real.

Тогда Х[0] означает самый первый элемент массива, Х[1] - следующий за ним и т.д. При этом к Х[0], Х[1],„., Х[99] нужно относиться как к отдельным переменным базового типа, в данном случае real. В качестве индекса можно использовать любое выражение со значениями из отрезка 0..99.

                                         ПРИМЕР. Ввод значений в массив М. var М: array [1..10] of integer; i: integer; begin i := 0; repeat i:=i+1; read (M [i]) until i = 10 end.

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

TYPE имя типа = определение типа

Следующие два описания переменной М эквивалентны:

М: ARRAY [1..10] OF INTEGER;

и TYPE ARR = ARRAY [1..10] OF INTEGER;

VAR M: ARR;

Заметим, что все описания должны предшествовать в программе их использованию.

Многомерные массивы

Если элементы массива сами являются массивами, получается структура данных, которая в программировании называется двумерным массивом. Описать ее можно так: ARRAY [тип индекса!] OF ARRAY [тип индекса2] OF тип элементов или ARRAY [тип индекса! ,тип индекса2] OF тип элементов

Обе формы описания равносильны, но вторая употребляется чаще.

Например, VAR M2: ARRAY [-10..10,1..50] OF REAL;

Обращаются к элементам двумерного массива, указывая не один, а два индекса: М2[4] [18] или М2[4,18]. Если в обращении указать только один индекс, это будет расценено как имя одномерного массива. Например, М2[10] означает, массив из 50 вещественных переменных: М2[10,1], М2[10,2],..., М2[10,50].

ПРИМЕР. Вывести на экран элементы двумерного массива вещественных чисел. var М2: array [1.. 10, 1..15] of real; ij: integer; begin i:=1; while i <= 10 do begin j:=1; whitej <= 15 do begin write (M2 [i,j] :5); J:=l+1; end {while}; writeln; I :=i+ 1; end {while}; end.

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