Алгоритмизации

• Название: Алгоритмизации
• Дата: 27.09.2022
• Размер: 1.15 Mb.
• Имя файла: 12_100229_1_124427 (1).docx
• Тип: Документы; #700459
• страница: 28 из 67

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

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

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

struct Stack →

Шаблон структуры рекомендуется описывать глобально: 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 → →} begin= NULL

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

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

begin(A1) →

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

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


t = new Stack;

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

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

а) формирование информационной части: t -> info = i2;

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

t -> Next = begin;

t(A2) →

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

begin = t;

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

begin(A2) → →
Обратите внимание, что действия 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);