ASD_Lecture03
.pdf
Рішення 2
#include <stdio.h>
void trueSwap(int* a, int* b)
{
int tmp;
tmp = *a; *a = *b; *b = tmp;
}
int main()
{
int x = 1, y = 2;
trueSwap(&x, &y); printf(“%d %d\n”, x, y);
x:
2 0x2000
y:
1 0x2010
31
}
Лекція 3
Базові структури даних
• Стеки
•Черги
•Списки
32
Лекція 3
Базові структури даних
•Що таке стек?
•Операції із стеками
•IsEmpty(S) – Повертає true якщо стек порожній
•Push(S,x) – Додає x у вершину стека
•Pop(S) – Видаляє елемент з вершини стека
33
Лекція 3
Стек |
Вершина |
Елементи |
стеку |
34 |
Лекція 3 |
Вставляння (Push)
|
|
Вер- |
|
|
шина |
|
Вершина |
|
До |
Після |
35 |
Лекція 3 |
|
|
Видаляння (Pop)
Вер- |
|
|
шина |
Видаляється зі стеку |
|
|
|
Вер- |
|
|
шина |
До |
Після |
36 |
Лекція 3 |
|
|
Операції
•Ініціалізація стека.
•Видалити елемент з вершини стека.
•Вставити елемент у вершину стека.
•Чи є стек порожній?
•Чи є стек повний?
•Очистити стек.
•Визначити розмір стека.
37
Лекція 3
Властивості стека
•Послідовність елементів, де вставляння і видаляння відбувається на вершині.
•Головними операціями є pop і push.
•Last-In First Out (LIFO).
•Використовується при виклику функцій.
•Використовується при реалізації рекурсій.
38
Лекція 3
Базові структури даних
• Стеки
• Черги
• Списки
39
Лекція 3
До |
Вставляння |
|
|
|
|
|
Вершина |
Хвіст |
Після |
|
|
Лекція 3 |
Вершина |
Хвіст40 |
|
|
|