Алгоритм формирования стека
Рассмотрим данный алгоритм для первых двух элементов.
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);
Дата добавления: 2014-12-30; просмотров: 1266;