5. Алгоритмы и структуры данных. Массивы

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



TYPE T = ARRAY n OF T0

TYPE Row = ARRAY 4 OF REAL
TYPE Card = ARRAY 80 OF CHAR
TYPE Name = ARRAY 32 OF CHAR

Конкретное значение переменной
VAR x: Row

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

Мощность структурированного типа, то есть количество значений, принадлежащих этому типу, равна произведению мощностей его компонент. Поскольку все компоненты массивового типа T имеют одинаковый базовый тип T0, то получаем
card(T) = card(T0)n

Переменная-массив, у которой все компоненты - тоже массивы, называется матрицей. Например,
M: ARRAY 10 OF Row

Селекторы могут приписываться один за другим, так что Mij и M[i][j] обозначают j-ю компоненту строки Mi, которая, в свою очередь, является i-й компонентой матрицы M. Обычно используют сокращенную запись M[i,j], и аналогично для объявления
M: ARRAY 10 OF ARRAY 4 OF REAL
можно использовать сокращенную запись
M: ARRAY 10, 4 OF REAL

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



ADruS14

Interface

DEFINITION ADruS14;

    PROCEDURE DoPower;
    PROCEDURE For;

END ADruS14.

Source

MODULE  ADruS14; 

    IMPORT  Log := StdLog,  In := i21sysIn,  Texts := ADruS174_Texts;
    
    PROCEDURE For*;
        CONST  N = 100;
        VAR a: ARRAY N OF INTEGER;
            sum, max, i, k: INTEGER;
    BEGIN
        FOR  i := 0  TO  N - 1  DO
            a[ i ] := 10*i - i*i
        END;
        
        (*******************************************)
        sum := 0;
        FOR i := 0 TO N-1 DO  sum := a[i] + sum  END;
        k := 0;  max := a[0];
        FOR i := 1 TO N-1 DO
            IF  max < a[i]  THEN  k := i;  max := a[k]  END;
        END;
        (****************************************************)
        
        (* вывод в рабочий журнал: *)
        Log.Int( sum );  Log.Ln;
        Log.Int( k );  Log.Int( max );  Log.Ln;
    END For;
    
    
    (*******************************************)

    PROCEDURE Power ( VAR W: Texts.Writer;  N: INTEGER );
        (* вычислить десятичное представление отрицательных степеней числа 2 *)
        VAR i, k, r: INTEGER;
            d: POINTER TO ARRAY OF INTEGER;
    BEGIN
        NEW( d, N );
        
        FOR k := 0 TO N-1 DO
            Texts.Write(W, "."); r := 0;
            FOR i := 0 TO k-1 DO
                r := 10*r + d[i]; d[i] := r DIV 2; r := r MOD 2;
                Texts.Write(W, CHR(d[i] + ORD("0")))
            END;
            d[k] := 5; Texts.Write(W, "5"); Texts.WriteLn(W)
        END
    END Power;

    (****************************************************)
    
    PROCEDURE DoPower*; (* управляющая процедура для Power *)
        VAR  w: Texts.Writer;  N: INTEGER;
    BEGIN
        (* ввод N: *)
        In.Open;  In.Int( N );  ASSERT( In.done & ( N > 0 ) );
        
        (* подготовка w к печати в рабочий журнал (Log): *)
        Texts.OpenWriter( w, Texts.log, Texts.Length( Texts.log ) );
        
        Power( w, N );
        
    END DoPower;

END  ADruS14.


Теги: