[ЗМІСТ] [Далі] [Назад] [Початок розділу]

7.6. Масиви

Цей розділ присвячений вивченню структури даних, що займає особливе місце в практиці застосування ЕОМ, - це масиви які безпосередньо пов'язані з принципом лінійної адресованої пам'яті: одним з знаменитих принципів Дж.фон Неймана (1903-1957).

Характерними особливостями масиву є:

1) всі його компоненти одного типу;

2) кожний елемент масиву може бути позначений явно і до нього є прямий доступ;

3) число компонент масиву визначається при його описі і в подальшому не змінюється.

Зазначимо, що і масиви, і записи мають одну загальну властивість - випадковий доступ до компонентів. Записи більш універсальні в тому розумінні, що для них не потрібно ідентичності типів всіх полів. У той же час масиви забезпечують велику гнучкість - селектори компонент можна обчислювати (це вирази) на відміну від селекторів для компонент запису, які описуються у визначенні типу запис.

Масиви призначені для позначення табличної відповідності.

Наприклад, найпростіша одновимірна таблиця

----------------------

¦ c ¦ c ¦. .. ¦ c ¦

¦ 1 ¦ 2 ¦ ¦ n ¦

----------------------

¦ А ¦ А ¦. .. ¦ А ¦

¦ 1 ¦ 2 ¦ ¦ n ¦

----------------------

задає відповідність значень А₁, А₂, ..., А_n індексам c₁, c₂, ..., c_n, тобто функцію

А: {c, c, ..., c } -> {А, А, ..., А }.

1 2 n 1 2 n

Якщо розглянути, наприклад, двовимірну таблицю, рядки якї позначені величинами r₁, r₂, ..., r_n; а стовпчики - величинами c₁, c₂, ..., c_m; то вміст її клітинок також можна вважати значеннями двомісної функції А, що дає за парою (r_k, c_i) значення А_ki

c c c

1 2 m

-------------------------

r ¦ А ¦ А ¦. .. ¦ А ¦

1 ¦ 11 ¦ 12 ¦ ¦ 1m ¦

-------------------------

r ¦ А ¦ А ¦. .. ¦ А ¦

2 ¦ 21 ¦ 22 ¦ ¦ 2m ¦

-------------------------

¦ ..................... ¦

-------------------------

r ¦ А ¦ А ¦. .. ¦ А ¦

n ¦ n1 ¦ n2 ¦ ¦ nm ¦

-------------------------

А: {r, r, ..., r } * {c, c, ..., c } -> {А, А, ..., А }.

1 2 n 1 2 m 11 12 nm

Будемо розглядати тільки такі таблиці, області визначення яких являють собою діапазони {r₁, r₂, ..., r_n } = r₁..r_n та {c₁, c₂, ..., c_m} = c₁..c_m або типи перерахування {r₁, r₂, ..., r_n} = (r₁, r₂, ..., r_n ) та {c₁, c₂, ..., c_m} = (c₁, c₂, ..., c_m), що дозволить легко обчислювати номер наступного (попереднього) стовпчика (рядка), використовуючи функції слідування (передування):

r = succ(r ) (k=2,..., n);

k k-1

c = succ(c ) (k=2,..., m);

k k-1

r = pred(r ) (k=1,..., n-1);

k k+1

c = pred(c ) (k=1,..., m-1).

k k+1

Розглянемо загальний випадок.

Нехай t - тип, t₁, ..., t_n - типи перерахування; D_t, D_t1,..., D_tn - їх області. Через {D_t1 *... * D_tn -> D_t} визначимо множину всіх функцій з декартова добутку D_t1 *... * D_tn в область D_t.

Масивом А з елементів типу t при типах індексів t₁, ..., t_n назвемо тип даних t_m,

------------------------------------

¦ тип t = масив [t, ..., t ] із t, ¦

¦ m 1 n ¦

L-----------------------------------

областю якого служить D_tm = {D_t1 *... * D_tn -> D_t}.

Таким чином, масив - це відповідність, що співставляє кожному набору індексів (i₁,..., i_n ) типів t₁, ..., t_n значення А[i₁, ..., i_n] типу t.

Масиви називають також табличним або регулярним типом.

Твердження 7.5. Якщо ¦D_t1 *... * D_tn¦ = r і ¦D_t¦ = k, то ¦D_tm¦ = k^r.¦

Визначимо операції та інструкції над масивами.

Нехай t_m = масив [t₁, ..., t_n ] із t, А – масив типу t_m, Е - вираз

типу t_m, е - вираз типу t. Послідовність t₁, ..., t_n позначимо через t_i.

1. Операції:

- обчислення значення масиву А по індексах (i₁, ..., i_n)

_ [ _ ]: t, t -> t.

m i

Позначення: А[i, ..., i ].

1 n

2. Інструкції:

- присвоєння А <- Е; тип інструкції присвоєння звичайний - t_m -> t_m; вираз Е - аргумент, змінна А - результат;

- зміна значення масиву А в точці (i₁, ..., i_n) на величиу е типу t

А[i, ..., i ] <- е. (7.4)

1 n

Тип останньої інструкції t_m, t_i, t -> t_m: за масивом А, індексами (i₁, ..., i_n) та виразу е отримуємо новий масив, що присвоюється тій же змінній A. Отже А є параметром-змінною інструкції (7.4).

Отримали табличний виконавець Tab(t₁, ..., t_n -> t).

Зверніть увагу на відсутність стандартного набору відношень серед можливостей табличного виконавця. Їх визначають з допомогою програмованих функцій окремо для кожного табличного типу.

Для скорочення позначень назвемо тип масив [1..n] із дійсн вектором довжини n або просто вектором, якщо n мається на увазі.

Визначимо підпрограму перевірки рівності двох векторів

А, В: масив [1..n] із дійсн.

Для цього розглянемо бульову послідовність Q_k, задану співвідношеннями:

Q = Іст;

0

Q = Q & (А[k] = В[k]), k=1,..., n. (7.5)

k k-1

Очевидно, що А=В тоді і тільки тоді, коли Q_n = Іст.

Відмітимо, що послідовність Q₀, Q₁, ..., Q_n - стаціонарна: або всі Q_k = Іст, або знайдеться таке i, що Q₀ = Q₁ =...= Q_i-1 = Іст, а Q_i = Q_i+1 =...=Q_n = Хиб.

Зроблене зауваження дозволяє спростити стандартний цикл обчислення співвідношення (7.5)

Q <- Іст;

для k=1 до n повт

Q <- Q & (А[k] = В[k])

кц

в цикл, що завершується при першому ж хибному Q_k

Q <- Іст; k <- 1;

поки (k<=n) & Q повт

Q <- А[k] = В[k]; k <- k+1

кц.

Остаточно отримуємо функцію

функція Рівні (А, В: масив [1..n] із дійсн): бул це

змін Q: бул; k: нат;

поч

Q <- Іст; k <- 1;

поки (k<=n) & Q повт

Q <- А[k] = В[k]; k <- k+1

кц;

Рівні <- Q

кф.

--

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

Приклад 7.9. Визначити функцію для обчислення суми компонент дійсного вектора.

Розв’язок. Користуючись відомим рекурентним співвідношенням для обчислення суми s_n чисел а₁, а₂,..., а_n

s = 0;

0

s = s + а, i = 1,..., n

i i-1 i

і вважаючи а_i = А[i], отримаємо підпрограму

функція Сума (А: масив [1..n] із дійсн): дійсн це

змін S: дійсн; I: ціл;

поч

S <- 0;

для I<-1 до n повт

S <- S+А[i]

кц;

Сума <- S

кф.

Приклад 7.10. Визначити функцію обчислення значення многочлена

n n-1

Р (х) = а *х + а *х +. .. + а *х + а

n 0 1 n-1 n

в заданій точці х.

Розв’язок. Розставимо у виразі для Р_n(х) дужки наступним чином

Р (х) = (...(а *х + а )*х +...+ а )*х + а,

n 0 1 n-1 n

що дозволить записати співвідношення

Р = а,

0 0

Р = Р *х + а, i=1,..., n.

i i-1 i

Тепер, припустивши, що коефіцієнти многочлена зібрані в таблиці А, отримаємо

функція Многочлен (А: масив [0..n] із дійсн; х: дійсн): дійсн це

змін Р: дійсн; I: ціл;

поч

Р <- А[0];

для I<-1 до n повт

Р <- Р*х + А[i]

кц;

Многочлен <- Р

кф.

До другого типу відносяться задачі обчислення табличних функцій.

Приклад 7.11. Добуток матриць.

n

Розв’язок. Оскільки c = S а *b, то обчислення кожного з c_il

il j=1 ij jl

має вигляд циклу

s <- 0;

для j<-1 до n повт

s <- s+А[i,j]*В[j,l]

кц.

Тепер отриманий цикл необхідно повторити для всіх i=1,..., m та l=1,..., k. Остаточно отримуємо

функція Добуток (А: масив [1..m, 1..n] із дійсн;

B: масив [1..n, 1..k] із дійсн):

масив [1..m, 1..k] із дійсн це

змін i, j, l: ціл; s: дійсн;

С: масив [1..m, 1..k] із дійсн;

поч

для i<-1 до m повт

для l<-1 до k повт

s <- 0;

для j<-1 до n повт

s <- s + А[i,j]*В[j,l]

кц;

C[i,l] <- s

кц

кц;

Добуток <- С

кф.

Задачі третього типу - це задачі пошуку деякої компоненти або сукупності компонент в таблиці.

Приклад 7.12. Пошук у лінійній таблиці. Скласти програму пошуку компоненти, рівної х, у векторі А.

процедура Пошук (арг А: масив [1..n] із дійсн, х: дійсн;

рез k: 1..n,. той: бул) це

змін i: нат;

поч

той <- Хиб; i <- 0;

поки ( Ø той) & (i<n) повт

i <- i+1; той <- х=А[i];

кц;

якщо той то k <-i kр

кп.

7.7. Масиви у мовах програмування

У мові Паскаль тип даних масив описується таким чином

type t = array [t ] of t;

m i

var А: t,

m

де t_m - ім'я типу масиву, t_i - типи індексів, t - тип компонент, А - ім'я масиву.

У якості типу індексу може використовуватися будь-який скалярний тип (існує обмеження на розмір масиву у 64Kb).

Приклад опису:

type ZNAK = array [1..255] of char;

VECT = array [1..4] of integer;

MATR = array [1..5] of VECT;

var M1: ZNAK;

M2, M4: MATR;

M3: array [1..5,1..4] of integer.

Зазначимо, що масиви M2 та M3 мають однаковий опис, але належать до різних типів.

Елементи масиву розташовуються в пам'яті послідовно. Компоненти з меншими значеннями індексу зберігаються в більш низьких адресах пам'яті. Багатовимірні масиви розташовуються таким чином, що найбільш правий індекс зростає першим.

Контроль правильності значень індексів масиву може проводитись за допомогою директиви компілятора {R+} або встановленням опції компілятора “Range checking”.

Дії над масивами.

Масив може брати участь тільки в операторі присвоєння. Масиви, що беруть участь у присвоєнні, повинні належати до одного типу.

Наприклад, для наших масивів M2 та M3 не можна записати M2:=M3, оскільки вони належать до різних типів. Але можна написати M2:= M4 (всі значення елементів масиву M4 присвоюються відповідним елементам масиву M2).

Дії над елементами масиву.

Після опису масиву кожний його елемент можна обробити, вказавши ідентифікатор (ім'я) масиву та індекс елемента в квадратних дужках. Наприклад, запис M1[10] дозволяє звернутися до десятого елементу масиву M1. При роботі з двомірним масивом вказується два індекси, наприклад, M2[3,2] або M2[3][2]; з n- вимірним масивом - n індексів.

Індексовані елементи масиву називаються індексованими змінними і можуть бути використані так само, як і прості змінні.

Мова Паскаль не має засобів введення-виведення масиву відразу, тому введення і виведення проводиться поелементно (див. приклади нижче).

Розглянемо деякі приклади використання масивів.

Приклад 4P. Сума елементів дійсного вектора (задача 7.9).

program SumVect;

const N = 10;

type MAS = array [1..N] of real;

var A: MAS;

I: integer;

function SUM (A: MAS): real;

var S: real; K: byte;

begin

S:= 0.0;

for K:=1 to N do S:= S+A[K];

SUM:= S

end;

begin

writeln('Задайте ', N:1,'елементів масиву');

for I:=1 to N do

read(A[I]);

writeln;

writeln('Сума елементів масиву A дорівнює ', SUM(A))

end.

У цьому прикладі, як і в наступних, в якості параметрів підпрограм можна вказувати тільки імена типів масивів, наприклад, A: MAS;.

Приклад 5P. Добуток прямокутних матриць (задача 7.11).

program ProdMatr;

const N = 3; M = 2; K = 4;

type MAS= array [1..N] of real;

MAS1= array [1..K] of real;

AMAS= array [1..M] of MAS;

BMAS= array [1..N] of MAS1;

CMAS= array [1..M] of MAS1;

var A: AMAS; B: BMAS; C: CMAS;

I, J, L: integer;

procedure PROD (A: AMAS; B: BMAS; var C: CMAS);

var I, J, L: byte; S: real;

begin

for I:=1 to M do

for L:=1 to K do begin

S:= 0.0;

for J:=1 to N do S:= S+A[I,J]*B[J,L];

C[I,L]:= S

end

end;

begin

writeln('Задайте елементи масиву A');

for J:=1 to M do

for I:=1 to N do begin

write('A[', J:3,', ', I:3,'] ='); readln(A[J, I])

end;

writeln('Задайте елементи масиву B');

for I:=1 to N do

for J:=1 to K do begin

write('B[', I:3,', ', J:3,'] ='); readln(B[I, J])

end;

PROD (A, B, C); L:= 0;

writeln('Масив C: ');

for I:=1 to M do

for J:=1 to K do begin

L:= L+1; write(C[I, J]:10:3,' ');

if L mod 4= 0 then writeln

end

end.

Приклад 6P. Пошук у векторі (задача 7.12).

program SearchVect;

const N = 10;

type NAT = 1..N;

MAS = array [NAT] of real;

var A: MAS; X: real; K: NAT;

I: integer; T: boolean;

procedure SEARCH(A: MAS; X: real; var K: NAT; var T: boolean);

var I: byte;

begin

T:= false; I:= 0;

while (not T) and (I<N) do begin

I:= I+1; T:= X=A[I];

end;

if T then K:= I

end;

begin

write('число Х = '); readln(X);

writeln('задайте елементи масиву');

for I:=1 to N do begin

write(' A[', I:3,'] ='); readln(A[I])

end;

SEARCH (A, X, K, T);

if T then begin

write('Компонента, що дорівнює зразку, є: ');

writeln(' A[', K:3,'] = ', X)

end

else writeln('В масиві немає компоненти, що дорівнює ', X)

end.

У мові Сі масиви описують таким чином

t a[n];

де t - тип компонент, a - ім'я масиву, n – кількість елементів масиву.

Індекси елементів масиву завжди є відрізками цілого типу з нижньою границею 0. Отже, індекс змінюється від 0 до n-1. Для опису багатовимірного масиву кількість елементів по кожному індексу вказують у дужках [n_i].

Приклад опису:

char m1[255];

int m2[5][4], m3[5][4];

Елементи масиву розташовуються в пам'яті послідовно. Компоненти з меншими значеннями індексу зберігаються в більш низьких адресах пам'яті. Багатовимірні масиви розташовуються таким чином, що найбільш правий індекс зростає першим.

Дії над масивами не передбачені. Обробка масивів проводиться поелементно.

Дії над елементами масиву.

Після опису масиву кожний його елемент можна обробити, вказавши ідентифікатор (ім'я) масиву та індекс елемента в квадратних дужках. Наприклад, запис m1[10] дозволяє звернутися до одинадцятого елементу масиву m1. При роботі з двомірним масивом вказується два індекси, наприклад, m2[3][2]; з n- вимірним масивом - n індексів.

Індексовані елементи масиву називаються індексованими змінними і можуть бути використані так само, як і прості змінні.

Мова Сі, як і Паскаль, не має засобів введення-виведення масиву відразу, тому введення і виведення проводиться поелементно (див. приклади нижче).

Розглянемо деякі приклади використання масивів.

Приклад 4C. Сума елементів дійсного вектора (задача 7.9).

#include <stdio.h>

/* SumVect */

#define n 10

double sum (double a[])

{

double s;

unsigned k;

s = 0.0;

for (k=0; k<n; k++)

s += a[k];

return s;

}

main()

{

double a[n];

int i;

printf(“Задайте %u елементів масиву\n”, n);

for (i=0; i<n; i++)

scanf(“%lf”, &a[i]);

printf(“Сума елементів масиву A дорівнює %lf\n”, sum(a));

}

Розглянемо на прикладі цієї програми правила передачі масивів як параметрів підпрограм. У Сі масиви, як і рядки, є вказівниками на початок елементів масиву у пам’яті. Отже, для передачі масивів як аргументів, модифікованих параметрів або результатів достатньо вказати ім’я масиву та дужки, наприклад a[]. Для багатовимірних масивів треба явно вказувати всі розміри (кількість елементів) для всіх індексів окрім першого, наприклад b[][5].

Приклад 5C. Добуток прямокутних матриць (задача 7.11).

#include <stdio.h>

/* ProdMatr */

#define n 3

#define m 2

#define k 4

prod (double a[][n], double b[][k], double c[][k])

{

unsigned i, j, l;

double s;

for (i=0; i<m; i++)

for (l=0; l<k; l++)

{

s = 0.0;

for (j=0; j<n; j++)

s += a[i][j]*b[j][l];

c[i][l] = s;

}

}

main()

{

double a[m][n], b[n][k], c[m][k];

unsigned i, j, l;

printf("Задайте елементи масиву A\n");

for (j=0; j<m; j++)

for (i=0; i<n; i++)

{

printf("A[%u,%u] =", j, i);

scanf("%lf", &a[j][i]);

}

printf("Задайте елементи масиву B\n");

for (i=0; i<n; i++)

for (j=0; j<k; j++)

{

printf("B[%u,%u] =", i, j);

scanf("%lf", &b[i][j]);

}

prod (a, b, c);

l = 0;

printf("Масив C:\n");

for (i=0; i<m; i++)

for (j=0; j<k; j++)

{

l++; printf("%lf ", c[i][j]);

if (l % 4 == 0) printf("\n");

}

}

Приклад 6C. Пошук у векторі (задача 7.12).

#include <stdio.h>

/* SearchVect */

#define n 10

#define FALSE 0

search(double a[], double x, unsigned *pk, int *pt)

{

int i;

*pt = FALSE; i = -1;

while (!*pt && i<n-1)

{

i++; *pt = x==a[i];

}

if (*pt) *pk = i;

}

main()

{

double a[n], x;

unsigned i, k;

int t;

printf(“число Х = ”); scanf(“%lf”, &x);

printf(“задайте елементи масиву\n”);

for (i=0; i<n; i++)

{

printf(“A[%u] = ”, i); scanf(“%lf”, &a[i]);

}

search (a, x, &k, &t);

if (t)

{

printf(“Компонента, що дорівнює зразку, є: ”);

printf(“A[%u] = %lf\n”, k, x);

}

else printf(“В масиві немає компоненти, що дорівнює %lf\n”, x);

}

[ЗМІСТ] [Далі] [Назад] [Початок розділу]