Если в функцию Сreate указатель на вершину передавать по адресу и использовать для захвата памяти операцию new, то она может иметь следующий вид:

void Create(Stack **pt) { Stack *t = new Stack; printf(“\n Input Info ”); scanf(“%d”, &t -> info); t -> Next = *pt;

}

Р

Обращение к ней в данном случае будет: Create(&begin);

15.2.2. Алгоритм извлечения элемента из стека

И

В данном алгоритме вершина begin не сдвигается.

1. Устанавливаем текущий указатель на вершину стека: t = begin;

2. Обрабатываем информационную часть текущегоУэлемента (t ->info),

например, выводим на экран.

Г

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

адрес которого находится в адресной ч сти текущего:

t = t->Next;

Б

а

15.2.3. Просмотр стека

к

1. Устанавливаем текущий указат ль на вершину t = begin.

2. Проверяем, если

begin рав н NULL, то стек пуст, выводим

е

сообщение и либо завершаем работу, либо переходим на формирование

стека.

3.

Если стек

не пу

, начинаем

выполнять

цикл до тех пор, пока

текущий

указате

ст

т.е. пока не обработаем последний

t не равен NULL,

о

элемент, в адресной части которого находится значение NULL.

4. Выводимина экран информационную часть текущего элемента:

printf(“\n Элемент: %d”, t -> info); или

cout << t->info;

ль

5. Переставляем текущий указатель на следующий элемент:

б

и

t = t -> Next;

Б

6. Конец цикла.

Функция просмотра стека без сдвига его вершины может выглядеть следующим образом:

void View(Stack *begin)

{

Stack *t = begin; if(begin == NULL) {

puts(“ Стек пуст! ”); return;

132

}

while( t != NULL) {

printf(“ %d \n”, t->info); t = t -> Next;

}

}

Обращение к этой функции: View(begin);

15.2.4. Алгоритм освобождения памяти, занятой стеком

1. Начинаем цикл, выполняющийся пока begin не станет равным NULL.
2. Устанавливаем текущий указатель на вершину стека: t = begin;
3. Вершину стека переставляем на следующий элемент: begin = t->Next;
									Р
4. Уничтожаем текущий (бывшую вершину) элемент, т.е. освобождаем
занятую под него память free(t);								И
Функция освобождения памяти, занятой стеком, будет выглядеть
следующим образом:							У
void Delete_Stack(Stack **begin) {
						Г
Stack *t;
						Б
while( *begin != NULL) {
	t = *begin;
	*begin = (*begin) -> Next;
	free(t);				а
}				к
}				е
Параметром данной функции является указатель на указатель, так как
			о
значение вершины стека передае ся в функцию и должно быть возвращено
		и
из нее. Тогда обращен е к функциитDelete_Stack с контролем ее выполнения
будет следующим:
	л
Delete		Stack(&begin);
if(begin == NULL)
и	puts(“ Free! ”);
. . .
Б

15.2.5.бАлгоритм проверки правильности расстановки скобок

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

При реализации алгоритма анализа исходное выражение просматривается слева направо.

1. Если в выражении обнаружена открывающаяся скобка, то анализируем содержимое стека:

133

а) если стек пуст или не пуст, но в вершине находится тоже открывающая скобка, то записываем ее в стек;

б) если стек не пуст и в вершине находится закрывающая скобка, то обе скобки выбрасываем из рассмотрения (находящуюся в стеке удаляем).

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

3.Просмотрев все выражение, проверяем стек и, если он не пуст, то баланс скобок нарушен и выражение составлено неверно, выводим

сообщение об этом и завершаем работу.

По такому принципу работают все компиляторы, проверяяРбаланс круглых скобок в выражениях, баланс фигурных скобок во вложенных блоках, вложенные циклы и т.п. ИУ

котором в отличие от стека извлечение данныхГпроисходит из начала цепочки, а добавление данных – в конец этой Бцепочки.

Очередь также называют структурой данных, организованной по

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

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

выполнять заказы только посл довательно один за другим. Если при

поступлении нового заказа данное устройство свободно, оно немедленно приступит к выполнению э го заказа, если же оно выполняет какой-то ранее полученный заказ, то н вый заказ поступает в конец очереди из других ранее

Пример очереди – некоторый м ханизм обслуживания, который может

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

еще два указателя, первый указатель устанавливается на начало очереди, а второй – на ее конец.

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

struct Spis { int info;

Spis *Next;

};

При организации очереди обычно используют два указателя

134

Spis *begin, *end;

где begin и end – указатели на начало и конец очереди соответственно, т.е. при создании очереди мы организуем структуру данных следующего вида:

begin

. . .

end

info1

A1

info2

A2

infoN

NULL

каждый элемент которой имеет информационную infо и адресную Next (A1, A2, ...) части.

Основные операции с очередью следующие:

– формирование очереди;		ИР
– добавление нового элемента в конец очереди;
– удаление элемента из начала очереди.
15.3.1. Формирование очереди		У
	Г
Формирование очереди состоит из двух этапов: создание первого
	Б
элемента, добавление нового элемента в конец очереди.

Создание первого элемента очереди

Этот этап заключается в создании первого элемента, для которого адресная часть должна быть нулевой (NULL). Для этого нужно:

1)

ввести информацию для первого элемента (целое число i);

2)

е

захватить память, используя т ущийауказатель:

t = (Spis*) malloc(sizeof(Spis));к

или t = new Spis;

ти

в результате формируется конкр

ный адрес (А1) для первого элемента;

3)

сформировать инф мационную часть:

ор

t -> info = i; ( бозначим i1 )

4)

и

NULL:

в адресную часть занес

л

t -> Next = NULL;

5)

указате ям на начало и конец очереди присвоить значение t:

б

begin = end = t;

На этом этапе по учим следующее:

и

begin

infо = i1

Next = NULL

end

БДобавление элемента в очередь

Рассмотрим алгоритм добавления только для второго элемента.

1.Ввод информации для текущего (второго) элемента – значение i .

2.Захватываем память под текущий элемент:

t = (Spis*) malloc (sizeof(Spis)); или t = new Spis; 3. Формируем информационную часть (обозначим i2):

t -> info = i;

135

4. В адресную часть созданного элемента (текущего) заносим NULL, т.к. этот элемент становится последним:

t -> Next = NULL;

5. Элемент добавляется в конец очереди, поэтому в адресную часть бывшего последнего элемента end заносим адрес созданного:

end -> Next = t;

бывший последний элемент становится предпоследним.

6. Переставляем указатель последнего элемента на добавленный: end = t;

В результате получим

			t
begin	i1	Next = t	i2	Next = NULL
			end		Р
Для добавления в очередь любого количества элементовИорганизуется
цикл, включающий	пункты	1– 6 рассмотренного		алгоритма. Завершение
				У

цикла реализуется в зависимости от поставленнойГзадачи.

Обобщим рассмотренные этапы, тогда функция формирования очереди

из данных объявленного типа с добавлением новых элементов в конец может
иметь следующий вид:					Б
void Create(Spis **begin, Spis **end)					{
	Spis *t = (Spis*) malloc(sizeof(Spis));а
	printf(“\n Input Info ”); к
	scanf(“%d”,		т
			&t -> info);
	t -> Next = NULL; е
		о		// Формирование первого элемента
	if(*begin == NULL)
	и
	else {	*begin = *end = t;
	л			// Добавление в конец
		(*end) -> Next = t;
		*end = t;
и	}
}
Б			обращением	к	функции Create для добавление
Участокбпрограммы с

необход мого количества элементов в очередь может иметь следующий вид:

¼
Spis *begin = NULL, *end;
int repeat = 1;
while(repeat) {	// repeat=1 – продолжение ввода данных
Create(&begin, &end);
printf(“ Stop - 0 ”);	// repeat=0 – конец ввода данных
scanf(“%d”, &repeat);
}
¼
136