Списки магазинного типа

1. Списки магазинного типа

ОАиП

2. Стеки

• Стек - список магазинного типа, в котором все
включения и исключения звеньев делаются в
одном конце списка.

3. Стеки

• Стек (англ. stack – стопка) – это структура
данных, в которой новый элемент всегда
записывается в ее начало (вершину) и
очередной читаемый элемент также всегда
выбирается из ее начала. В стеках используется
метод доступа к элементам LIFO ( Last Input –
First Output, "последним пришел – первым
вышел").

4. Стеки

• Стек – это список, у которого доступен
один элемент (одна позиция). Этот
элемент называется вершиной стека.
Взять элемент можно только из
вершины стека, добавить элемент
можно только в вершину стека.
Например, если записаны в стек числа
1, 2, 3, то при последующем извлечении
получим 3,2,1.

5. Стеки

6. Описание стека

• Описание
стека
выглядит
образом:
• struct имя_типа {
информационное поле;
адресное поле;
};
следующим

7. Описание стека

• где информационное поле – это поле любого
ранее объявленного или стандартного типа;
• адресное поле – это указатель на объект того
же типа, что и определяемая структура, в него
записывается адрес следующего элемента
стека.

8. Основные операции, производимые со стеком

• Основные
операции,
производимые
стеком:
создание стека;
печать (просмотр) стека;
добавление элемента в вершину стека;
извлечение элемента из вершины стека;
проверка пустоты стека;
очистка стека.
со

9. Формирование стека

• Вначале стек пуст:
• stk = NULL;

10. Формирование стека

• Содержимое
стека
будем
вводить
клавиатуры, ввод заканчивается нулем:
• cin>>Элем;
• t = new (node); (*t).elem = Элем;
• (*t).sled = stk;
с

11. Формирование стека

• "Настраиваем" указатель стека на созданный
элемент:
• stk = t;

12. Формирование стека

• В результате в стек будет помещено первое
звено:

13. Формирование стека

• Продолжим заполнение стека:
• cin>>Элем1;
• t = new (node);
• (*t).elem = Элем1;
• (*t).sled = stk;

14. Формирование стека

• "Настраиваем" указатель стека на созданный
элемент:
• stk = t;

15. Формирование стека

• Теперь стек содержит уже два звена:

16. Формирование стека

• void POSTROENIE (node **stk)
• //Построение стека, заданного указателем
*stk с клавиатуры.
• {
• node *t;
• int el;
• *stk = NULL;
• cin>>el;

17. Формирование стека

• while (el!=0)
• {
• }
t = new (node);
(*t).elem = el;
(*t).sled = *stk;
*stk = t;
cin>>el; }

18. Включение звена в стек

• Исходное состояние стека:

19. Включение звена в стек

• Создаем новый элемент:
• q = new (node);
• (*q).elem = Элем;

20. Включение звена в стек

• Включаем элемент в начало стека:
• (*q).sled = stk;

21. Включение звена в стек

• "Настроим" указатель вершины стека:
• stk = q;

22. Включение звена в стек

• void W_S (node **stk, int el)
• //Включение звена с элементом el в стек,
• // заданный указателем *stk.
• {
• }
node *q;
q = new (node);
(*q).elem = el;
(*q).sled = *stk;
*stk = q;

23. Включение звена в стек

• void POSTROENIE (node **stk)
• // Построение стека, заданного указателем
*stk с клавиатуры.
• {
• int el;
• *stk = NULL;
• cin>>el;

24. Включение звена в стек

• while (el!=0)
• {
• W_S (stk,el);
• cin>>el;
• }
• }

25. Удаление элемента из стека

• Перед удалением звена из стека проверяем,
пуст ли стек.
• Пусть стек не пуст.

26. Удаление элемента из стека

• Тогда приступаем к удалению.
• Сохраняем удаляемый элемент:
• klad = (*stk).elem;

27. Удаление элемента из стека

• "Перенастраиваем"
указатель
стека
сохраняем адрес удаляемого элемента:
• q = stk;
• stk = (*stk).sled;
и

28. Удаление элемента из стека

• Возвращаем память в кучу:
• delete q;

29. Удаление элемента из стека

• void YDALENIE (node **stk, int klad)
• // Удаление звена из стека, заданного
указателем *stk, и
• // помещение значения информационного
поля удаленного звена
• // в параметр klad.
• { node *q;

30. Удаление элемента из стека

• if (*stk==NULL)
• cout<<"Стек пуст!\n";
• else
• {
• *klad = (**stk).elem;
• q = *stk; *stk = (**stk).sled;
• delete q;} }

31. Очереди

• Каждый новый элемент размещается в конце
очереди; элемент, стоящий в начале очереди,
выбирается из нее первым.
• В очереди используется принцип доступа к
элементам FIFO ( First Input – First Output,
"первый пришёл – первый вышел«).

32. Очереди

33. Описание очереди

• Описание очереди выглядит следующим
образом:
• struct имя_типа {
информационное поле;
адресное поле1;
адресное поле2;
};

34. Описание очереди

• где информационное поле – это поле любого,
ранее объявленного или стандартного, типа;
• адресное поле1, адресное поле2 – это
указатели на объекты того же типа, что и
определяемая структура, в них записываются
адреса первого и последнего элементов
очереди.

35. Основные операции, производимые с очередью

• Выделим типовые операции над очередями:
• добавление элемента в очередь (помещение в
хвост);
• удаление элемента из очереди (удаление из
головы);
• проверка, пуста ли очередь;
• очистка очереди.

36. Формирование очереди

• алгоритм формирования очереди:
• r = new (node);
• (*r).elem = Элем;
• (*r).sled = NULL;

37. Формирование очереди

no = r; ko = r;

38. Формирование очереди

Продолжим заполнение очереди:
r = new (node);
(*r).elem = Элем1;
(*r).sled = NULL;

39. Формирование очереди

Настроим указатель на конец очереди:
(*ko).sled = r;
ko = r;

40. Формирование очереди

void POSTROENIE (node **no, node **ko)
//
Построение
однонаправленного
очереди
на
// линейного списка без заглавного звена:
// *no - указатель на начало очереди,
// *ko - указатель на конец очереди.
{
node *r; int el;
базе

41. Формирование очереди

cin>>el;
if (el!=0)
{
r = new (node);
(*r).elem = el;
(*r).sled = NULL;
*no = r; *ko = r;
cin>> el;

42. Формирование очереди

while (el!=0)
{
r = new (node);
(*r).elem = el;
(*r).sled = NULL;
(**ko).sled = r;
*ko = r;

43. Формирование очереди

cin>>el;
}
}
else
{
r = NULL;
*no = r;
*ko = r;
}
}

44. Вывод очереди

45. Добавление звена к очереди

Вначале построим добавляемое звено:
r = new (node);
(*r).elem = Элем;
(*r).sled = NULL;

46. Добавление звена к очереди

Присоединяем звено к очереди:
(*ko).sled = r;

47. Добавление звена к очереди

"Настраиваем" указатель ko на конец очереди:
ko = r;

48. Добавление звена к очереди

49. Удаление элемента из очереди

Сохраним удаляемый элемент:
klad = (*no).elem;

50. Удаление элемента из очереди

Сохраним указатель на удаляемый элемент и
"перенастроим" указатель на начало очереди:
q = no;
no = (*no).sled;

51. Удаление элемента из очереди

Теперь необходимо включить в список
свободной памяти удаленное из очереди звено с
помощью вызова функции:
delete q;

52. Удаление элемента из очереди