АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. XII. ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ
  2. А. Стекание тока в землю через одиночные заземлители
  3. Аграрная политика царизма в Казахстане в конце XIX-начале ХХ вв. Переселение русских, украинских крестьян. Начало формирования многонационального состава населения Казахстана.
  4. Алгоритм
  5. Алгоритм MD4
  6. Алгоритм RC6
  7. Алгоритм RSA
  8. Алгоритм Брезенхема для окружности
  9. Алгоритм Брезенхема.
  10. Алгоритм взятия мазка из носа и зева.
  11. Алгоритм вибіркового методу
  12. Алгоритм вставки элемента в список после элемента с указанным ключом

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

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);

 

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 |


Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.007 сек.)