Алгоритм формирования стека

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

1. Описание структуры переменной, содержащей информационное и адресное поля:

struct Stack ®

info

Next

Шаблон структуры рекомендуется описывать глобально:

struct Stack {

int info;

Stack *Next;

};

2. Объявление указателей на структуру:

Stack *begin (вершина стека), *t (текущий элемент);

3. Так как первоначально стек пуст: begin = NULL;

4. Захват памяти под первый (текущий) элемент:

t = (Stack*) malloc (sizeof(Stack)); или t = new Stack;

формируется конкретный адрес ОП (обозначим его А 1) для первого элемента, т.е. t равен А 1.

5. Ввод информации (например, i 1);

а) формирование информационной части:

t -> info = i1;

б) формирование адресной части: значение адреса вершины стека записываем в адресную часть текущего элемента (там был NULL)

t -> Next = begin;

t ®

info = i 1

Next

®

begin = NULL

6. Вершина стека переносится на созданный первый элемент:

begin = t;

в результате получается следующее:

begin (A 1) ®

info = i 1

NULL

7. Захват памяти под второй элемент:

t = (Stack*) malloc (sizeof(Stack)); или t = new Stack;

формируется конкретный адрес ОП (A 2) для второго элемента.

8. Ввод информации для второго элемента (i 2);

а) формирование информационной части:

t -> info = i2;

б) в адресную часть записываем значение адреса вершины, т.е. адрес первого (предыдущего) элемента (А 1):

t -> Next = begin;

t (A 2) ®

info = i 2

Next = A 1

9. Вершина стека снимается с первого и устанавливается на новый элемент (A 2):

begin = t;

получается следующая цепочка:

begin (A 2) ®

info = i 2

Next = A 1

®

info = i 1

Next = NULL

Обратите внимание, что действия 7, 8, 9 идентичны действиям 4, 5, 6, т.е. добавление новых элементов в стек можно выполнять в цикле, до тех пор, пока это необходимо.

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

Stack* Create(Stack *begin) {

Stack *t = (Stack*)malloc(sizeof(Stack));

printf(“\n Input Info ”);

scanf(“%d”, &t -> info);

t -> Next = begin;

return t;

}

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

¼

Stack *begin = NULL;

int repeat = 1;

while(repeat) { // repeat =1 – продолжение ввода данных

begin = Create(begin);

printf(“ Stop - 0 ”); // repeat =0 – конец ввода данных

scanf(“%d”, &repeat);

}

¼

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

void Create(Stack **pt) {

Stack *t = new Stack;

printf(“\n Input Info ”);

scanf(“%d”, &t -> info);

t -> Next = *pt;

}

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