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

Двумерный массив

	1	2	…	j	…	m
1	11	12	…	1j	…	1m	l
2	21	22	…	2j	…	2m
…	…	…	…	…	…	…
i	i1	i2	…	ij	…	im
…	…	…	…	…	…	…
n	n1	n2	…	nj	…	nm

Представление массива в памяти по строкам:

Aij=Am+(i-1)*m*l+(j-1)*l=Am+((i-1)*m+j-1)*l; 1...n

Aij=Am+(i*m+j)*l, 0..n-1

24) Линейные структуры данных. СТЕК

Стек – это структура данных, которая функционирует по принципу FILO (first input, last output).

Для стека определены следующие операции:

• Чтение. Аргумент отсутствует, результат: значение верхнего элемента стека. При чтении верхний элемент удаляется. Операция завершается с ошибкой, если стек пуст.

• Запись. Аргумент: значение, результат: отсутствует. Значение записывается в стек и становиться верхним.

Абстрактный стек безразмерный, операция запись выполняется всегда. В компьютере реализация стека имеет ограничения на ресурсы, поэтому операция может завершиться с ошибкой, если нет места для нового элемента: «переполнение стека».

Стек может быть реализован с помощью массива или динамического списка.

3.6.1 Реализация с помощью массива

Для реализации требуется:

• массив, хранящий значение элементов стека;

• две переменные: S – максимальное число элементов (размерность массива) и С – текущее количество элементов.

Операция запись

1. Проверка состояния стека на наличие свободных элементов, если элементов нет, то ошибка.

2. Запись значения в элемент с индексом С и увеличение С на величину.

Файлы WS:

int WT (char V) { //сначала увеличиваем элемент с номером С

if (C=S) return 1; // затем увеличиваем С на 1

m[C++]=V; //чтобы отдельно не делать С++

return 0; //стек пуст, если С=0

}

3.6.2 Реализация с помощью динамического списка

Стек реализуется с помощью однонаправленного списка. Однонаправленного списка достаточно, т.к. операции чтения и записи выполняются с одной стороны набора данных.

Первый элемент стека – вершина списка. Если в стеке наверх положили элемент, то мы его добавляем перед первым элементом в списке – операция записи в стек.

Операция чтения элемента из стека соответствует выполнению двух операция со списком:

1. Выборка первого элемента.

2. Удаление первого элемента.

Признаком пустого стека является пустой (нулевой) указатель. Признаком полного стека является ошибка при выделении памяти для добавления элемента в список.

25) Линейные структуры данных. Структура «Очередь»

О чередь - это структура, функционирующая по принципу FIFO (first input, first output).

Запись элементов производится с одной стороны, чтение – с другой.

Для очереди определены две операции:

1. Чтение.

2. Запись.

Их описание полностью соответствует операциям для стека, а алгоритмы отличаются в соответствии с правилом FIFO.

Очередь может быть реализована массивом или динамическим списком.

Д ля реализации массивом необходим массив и четыре переменные:

S – максимальное количество элементов очереди.

y – состояние очереди.

f, l -= указатели на i-й и последний элементы очереди.

f будет указывать на 1-й элемент очереди, l – на свободное место после последнего элемента.

При очереди массив закольцован. Процесс записи массивов в очередь можно представить следующим образом (l указывает на свободную переменную).