Полустатические структуры

Определения этих структур данных основаны на понятии списка или списковой структуры.

Списком называется линейно-упорядоченная последовательность элементов данных E(1),E(2)…E(n), где n>0,причем каждый элемент E(i) характеризуется одним и тем же набором полей. Такой список называют линейным списком из-за линейной упорядоченности элементов. Упорядоченность элементов списка может быть задана неявно путем последовательного расположения его элементов как в логической структуре, так и в памяти ЭВМ (т.е физической структуре данных). Список с таким неявным заданием упорядоченности в логической и физической структурах называют еще последовательным линейным списком. С другой стороны, упорядоченность может задаваться явно путем помещения в каждом элементе E(i) указателей или связок, в которых помещается адрес последующего или предыдущего элемента списка. Такие списки называют связными списками и о них мы буде мы говорить позже.

При n=const и соответствующем выборе элемента данных, последовательный линейный список сводится к вектору, к массиву, записи или таблице. Так, вектор может быть определен как последовательный линейный список, в котором каждый элемент-скаляр одного и того же типа.

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

Полустатические структуры данных- это последовательные линейные списки с переменной длиной, ограниченной фиксированной максимальной величиной и с ограниченным доступом. К таким структурам относятся стеки и очереди. Есть еще деки, но они менее распространены и на них останавливаться не будем.

Стек - такой последовательный линейный список с переменной длиной, включение и исключение элементов из которого выполняется только с одного конца списка. Известно и другое название стека – магазин. Иногда стек называют еще очередью, функционирующей по принципу LIFO (Last- In-First- Out –последним пришел – первым вышел).

E_max

E_n

E_n-1

…

E₁

Верхняя граница стека  

	Свободные слоты

Рис.1 Логическая структура стека  

Нижняя граница стека  

Вершина стека, с ней связан указатель стека = адрес последнего занятого элемента стека  

Физическая структура стека может быть изображена следующим образом:

ST – имя стека

Адрес верхней границы

Указатель вершины

Адрес нижней границы

Описание элемента

Рис.2 Физическая структура стека  

Ячейки оперативной памяти ЭВМ  

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

Другими операциями над стеком, кроме включения и исключения элемента является очистка стека и проверка объема стека, т.е. числа элементов в стеке.

Для хранения стека в памяти ЭВМ отводится сплошная область памяти ограниченного объема. Если в процессе заполнения стека указатель выходит за отведенные границы стека, то происходит переполнение стека и включение нового элемента становится невозможным.

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

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

Function answer(n: word): longint;

Fact: longint:

begin

if n>1 then fact: = n* answer (n-1) else fact: = 1;

answer: = fact;

end;

Допустим, фрагмент программы:

m:=3:

Factorial:=answer(m);

next: следующий оператор.

Выполнение действий в такой программе может быть проиллюстрировано рисунком 5 и таблицей 1.

Стековая память используется при трансляции входных языков и обмене между программными компонентами процессора.

Рисунок 4 - Выполнение рекурсивной функции с использованием стека

Таблица 1 – Описание действий и содержимого стека при выполнении рекурсивной функции

Вход  

Результаты    

Следующие действия

Первый

Адрес метки NEXT

1. Выполняется пролог

Стек: Указатель

2. Выполнение тела:

N=N–1; N=2

Обращение процедуры самой к себе CALL FACT(N)

Второй

	Адрес метки A
	Адрес метки NEXT

1. Выполнение пролога

Стек: Указатель

2. Выполнение тела:

N:=N–1; N=1

Обращение процедуры самой к себе CALL FACT(N)

Третий

	Адрес A
	Адрес A
	Адрес NEXT

1. Выполнение пролога:

Стек: указатель

2. Выполнение тела:

ANSWER=1

3. Выполнение эпилога (первое):

	Адрес A
	Адрес NEXT

Стек: указатель

ANSWER=1*1=1

Адрес NEXT

4. Выполнение эпилога (второе):

Стек: указатель

ANSWER=2

5. Выполнение эпилога

Стек – пуст

ANSWER=6

  Первое обращение к метке A     Первый возврат на метку A     Второй возврат на метку A   Возврат на метку NEXT

Очередь – такой последовательный список с переменной длиной, включение элементов в который происходит с одной стороны, а исключение с другой стороны списка.

Очередь функционирует по принципу – FIFO (First-In-First-Out-первым пришел, первым вышел).

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

A1

A2

Amax

Указатель P1  

Из схемы следует: для очереди выделяется фиксированный участок памяти ЭВМ, в котором, как правило, заняты в каждый момент времени лишь некоторые слоты. Указатель P1 является адресом первого (начального), слота очереди, P2 – адресом первого свободного слота очереди.

При включении в очередь вносится по адресу P2, затем значение указателя P2 изменяется (передвигается на 1 элемент очереди), т.е. значение P2 увеличивается на длину элемента очереди.

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

Возможны и другие операции с очередью: очистка и проверка длины.

Очевидно, что в процессе включения элементов неизбежно возникнет состояние переполнения очереди - выход указателя P2 за lim Amax. Такой недостаток схемы, может быть устранен, если после достижения указателем P2, значение Amax переводить указатель P2 на адрес A1, если слот A1 пуст. Организованная таким образом очередь называется кольцевой. В ней возможны любые соотношения указателей P1 и P2: P1>P2, P1=P2, P1<P2. P1=P2 – очередь пуста. Используется при обмене данными между устройствами ЭВМ.

Дата добавления: 2015-12-08