Контрольные вопросы

1. Какие объекты помещаются в программный стек при входе в функцию?

2. Как изменяется указатель программного стека при выходе из функции?

3. Что происходит с программным стеком при рекурсивном обращении функции к самой себе?

4. Напишите обратную польскую запись для выражения

5. Напишите послед овательность операций и состояние стека в процессе вычисления значения выражения, представленного польской записью из предыдущего примера.

3. Очередь

Очередью называют одномерную структуру данных с дисци­плиной обслуживания "первый пришел – первый ушел". Такую дисциплину обслу­живания также называют FIFO (First In – First Out), что озна­чает то же самое. Все включения в очередь делаются на одном конце, а все исключения – на другом. Очередь может быть пред­став­лена массивом или списком. В этом разделе рассматривается представление очереди массивом (рис 1).

Рис 2. Очередь в массиве

Простейшее решение состоит в том, чтобы иметь два указателя для начала и конца очереди - F и R. F указывает место на начало очереди; R указывает на последний элемент очереди.

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

/* Поместить в очередь */ R=R+1; X[R]=Y;

/* Взять из очереди */ F=F+1; Y=X[F];

Заметим, что в процессе выполнения серии включений и исключений, очередь будет ”ползти” вдоль памяти, так как F и R непрерывно увеличиваются. Это означает чрезвычайно расточительное использование памяти. Проблему можно решить, отводя под очередь M позиций и неявно замыкая её в кольцо, так, что за последней позицией следует первая. Пусть очередь представлена структурой:

#define M 8 // длина массива, отводимого под очередь

struct QUEUE{

int Q[M]; // массив, используемый для хранения очереди

int F; // ИНДЕКС первого элемента очереди

int L; // ИНДЕКС ПОСЛЕДНЕГО

bool IsEmpty; // признак пустой очереди

};

QUEUE T; // экземпляр очереди над которой выполняются операции

Тогда включение и исключение примут вид:

/* Поместить в очередь */

T.L=(T.L==M-1) ? 0 : T.L+1;

if(!T.IsEmpty && T.F==T.L){

Переполнение();

}

T.Q[T.L]=x;

T.IsEmpty=false;

// взять из очереди

int z;

bool fl=T.F==T.L;

if(!T.IsEmpty){

z=T.Q[T.F];

T.F=T.F==M-1 ? 0 : T.F+1;

T.IsEmpty=fl;

} else {

Пусто();

}

// z – извлеченное из очереди значение

Здесь Переполнение и Пусто – подпрограммы, обрабатывающие соответствующие ситуации. Ситуация Пусто не является аварийной. В ситуации Переполнение программа должна либо перераспределить память под очередь, либо прекратить работу.

Контрольные вопросы

1. По каким правилам элементы помещаются в очередь и удаляются из очереди?

2. Как избежать перемещения очереди по памяти?

3. Вычислите значение U_1000000, если U_n=U_n-1+2U_n-2-3U_n-3 и U₀=U₁=U₂=U₃=1

4. Массивы

4.1. Размещение прямоугольных массивов в последовательной памяти

В качестве примера рассмотрим трёх­мерный прямоугольный массив (3 слоя по 4 строки по 5 элементов в строке). Такой массив можно представить в виде паралле­лепи­педа (рис 3.). Предположим, что элементы массива следуют в памяти в лексико­графическом порядке, то есть так, что первым изменяется последний индекс. Такой порядок используется в большинстве алгоритмических языков, но есть и исключения, например, Фортран. Порядковый номер элемента массива A[i][j][k] можно вычислить по формуле:

i

*

Объем слоя

+

j

*

Длина строки

+

k

В общем случае описание массива может иметь вид:

A[i₁:j₁][i₂:j₂]…[i_n:j_n]

где i_m, j_{m –} нижняя и верхняя граница индекса в m-м измерении. Каждый раз, когда программа обращается к элементу массива, она должна вычислить его адрес по заданным индексам k₁,k₂…k_n. Функция упорядочения, которая это делает, имеет вид:

где L – искомый адрес; b – начальный адрес массива (адрес его 1-го элемента); D_m – объем m-го сечения массива (слоя, строки…) в байтах. В общем случае функцию упорядочения можно записать в виде:

, где

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

Пример: для массива с границами индексов 3:5,1:4,0:1 имеем:

D₃=1

D₂₌(j₃-i₃+1)*D₃=2

D₁₌(j₂-i₂+1)*D₂=8

с=b-(i₁*D₁+i₂*D₂+i₃*D₃)=26*(b-1)

И функция упорядочения имеет вид:

L=25*(b-1)+8*k₁+2*k₂+k₃

Функция упорядочения строится компиляторами автоматически. Исходные данные о массиве представляются обычно в виде информационного вектора массива:

I_A=(n, число элементов, C, D₁, D₂,…D_n, i_1, j₁, i₂, j₂,…i_n, j_n)