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

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

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. Ввод информации (например, i1);

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

t -> info = i1;

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

t -> Next = begin;

t ® info = i1 Next ® begin = NULL

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

begin = t;

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

begin (A1) ® info = i1 NULL

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

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

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

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

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

t -> info = i2;

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

t -> Next = begin;

t (A2) ® info = i2 Next = A1  

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

begin = t;

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

begin (A2) ® info = i2 Next = A1 ® info = i1 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);

 

 








Дата добавления: 2016-01-09; просмотров: 1048;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.006 сек.