4

Списки
Список — структура данных, представляющая собой конечную последовательность связанных элементов.
Элемент списка:
Семинар 10. Стеки, очереди, деки
Данные
Связь

Односвязные списки
Односвязный список — список, у элементов которого существует связь, указывающая на следующий элемент (односторонняя связь).
Семинар 10. Стеки, очереди, деки
Голова
Хвост

Односвязные списки
struct list {
int data;
struct list *next;
};
struct list *head = NULL, *p, *t;
Семинар 10. Стеки, очереди, деки

Циклические списки
Циклический список — список,
в котором связь указывает
на первый или один из других элементов списка.
Семинар 10. Стеки, очереди, деки
head

Двусвязные списки
Двусвязный список — список, элементы которого имеют по две связи, указывающие на предыдущий и следующий элементы.
Семинар 10. Стеки, очереди, деки
head
NULL

Двусвязные списки
struct List {
int data;
struct list *prev;
struct list *next;
};
Семинар 10. Стеки, очереди, деки

Иерархические списки
Иерархический список — список, значениями элементов которого являются указатели на другие списки (подсписки).
Семинар 10. Стеки, очереди, деки
head
NULL

Операции над линейными списками
1. Получить доступ к некоторому элементу списка, проанализировать и / или изменить значения его полей.
2. Вставить новый элемент перед заданным.
3. Удалить заданный элемент.
4. Объединить два или более списков в один.
5. Разделить список на два или более.
6. Сделать копию списка.
7. Определить количество элементов.
8. Выполнить сортировку элементов по значениям определённых полей.
9. Найти элемент с заданным значением в некотором поле.
…и другие
Семинар 10. Стеки, очереди, деки

Операции над линейными списками
Не все операции нужны одновременно.
Будем различать типы линейных списков по набору главных операций, которые над ними выполняются.
Семинар 10. Стеки, очереди, деки

Стек
Стек (от англ. stack — штабель, стопка) — линейный список, в котором все вставки, удаления и любой доступ производятся в одном конце списка.
Семинар 10. Стеки, очереди, деки
Вершина:
вставить
или
удалить
2-й сверху
Низ

Очередь
Очередь (англ. queue) — это линейный список, в котором все вставки производятся на одном конце, а все удаления — на другом.
Семинар 10. Стеки, очереди, деки
Начало:
удалить
2-й
3-й
4-й
Конец:
вставить

Дек
Дек (от англ. deque — double-ended queue — двусторонняя очередь) — это линейный список, в котором все вставки и удаления производятся на обоих концах.
Семинар 10. Стеки, очереди, деки
Левый конец:
вставить или
удалить
2-й слева
3-й слева
или справа
2-й справа
Правый конец:
вставить или
удалить

Стеки
Push-down список
Реверсивная память
Гнездовая память
Магазин
LIFO: last in first out
Список йо-йо
Семинар 10. Стеки, очереди, деки

Операции со стеками
1. Опустошение.
2. Создание.
3. Получение значения вершины без удаления.
4. Получение значения вершины с удалением.
5. Добавление нового элемента.
6. Проверка пустоты.
Семинар 10. Стеки, очереди, деки

Реализация стека на Си
struct list {
int data;
struct list *next;
};
typedef struct stack {struct list *top;} Stack;
Семинар 10. Стеки, очереди, деки

Опустошение стека
void makenull(Stack *S)
{
struct list *p;
while (S -> top) {
p = S -> top;
S -> top = p -> next;
free(p);
}
}
Семинар 10. Стеки, очереди, деки

Создание стека
Stack *create()
{
Stack *S;
S = (Stack *) malloc(sizeof(Stack));
S -> top = NULL;
return S;
}
Семинар 10. Стеки, очереди, деки

Получение значения вершины без удаления
int top(Stack *S)
{
if (S -> top)
return (S -> top -> data);
else
return 0; /* или иная реакция на ошибку */
}
Семинар 10. Стеки, очереди, деки

Получение значения вершины c удалением
int pop(Stack *S)
{
int a;
struct list *p;
p = S -> top;
a = p -> data;
S -> top = p -> next;
free(p);
return a;
}
Семинар 10. Стеки, очереди, деки

Добавление нового элемента
void push(int a, Stack *S)
{
struct list *p;
p = (struct list *) malloc(sizeof(struct list));
p -> data = a;
p -> next = S -> top;
S -> top = p;
}
Семинар 10. Стеки, очереди, деки

Проверка пустоты
int empty(Stack *S)
{
return (S -> top == NULL);
}
Семинар 10. Стеки, очереди, деки

Виды записи выражений
Префиксная: операция перед операндами.
Инфиксная (скобочная): операция между операндами.
Постфиксная (обратная польская): операция после операндов.
Семинар 10. Стеки, очереди, деки

Виды записи выражений
a + (f – b * c / (z – x) + y) / (a * r – k)
+ a / + – f / * b c – z x y – * a r k
a f b c * z x – / – y + a r * k – / +
Семинар 10. Стеки, очереди, деки

Перевод из инфиксной формы в постфиксную
Вход: строка, содержащая арифметическое выражение, записанное в инфиксной форме.
Выход: строка, содержащая то же выражение, записанное в постфиксной форме (обратной польской записи).
Обозначения:
числа, строки (идентификаторы) — операнды.
Семинар 10. Стеки, очереди, деки

Перевод из инфиксной формы в постфиксную
Алгоритм:
Шаг 0:
Взять первый элемент из входной строки и поместить его в X.
Выходная строка и стек пусты.
Шаг 1:
Если X — операнд, то дописать его в конец выходной строки.
Если X = '(', то поместить его в стек.
Если X = ')', то вытолкнуть из стека и поместить в конец выходной строки все
элементы до первой встреченной открывающей скобки.
Эту скобку вытолкнуть из стека.
Если X — знак операции, отличный от скобок, то пока стек не пуст, и верхний элемент стека имеет приоритет, больший либо равный приоритету X,
вытолкнуть его из стека и поместить в выходную строку.
Затем поместить X в стек.
Шаг 2:
Если входная строка не исчерпана, то поместить в X очередной элемент входной
строки и перейти на Шаг 1, иначе
пока стек не пуст, вытолкнуть из стека содержимое в выходную строку.
Семинар 10. Стеки, очереди, деки

Пример
Входная строка:
a + ( f – b * c / ( z – x ) + y ) / ( a * r – k )
Выходная строка:
Стек:
a
+
(
f
–
b
*
c
/
(
z
–
x
)
+
y
)
/
(
a
*
r
–
k
)
X =
Семинар 10. Стеки, очереди, деки

Вычисления на стеке
Вход: строка, содержащая выражение, записанное в постфиксной форме.
Выход: число — значение заданного выражения.
Алгоритм:
Шаг 0:
Стек пуст.
Взять первый элемент из входной строки и поместить его в X.
Шаг 1:
Если X — операнд, то поместить его в стек.
Если X — знак операции, то вытолкнуть из стека два верхних элемента,
применить к ним соответствующую операцию, результат положить
в стек.
Шаг 2:
Если входная строка не исчерпана, то поместить в X очередной элемент
входной строки и перейти на Шаг 1, иначе вытолкнуть из стека
результат вычисления выражения.
Семинар 10. Стеки, очереди, деки

Пример
Входная строка:
5 2 3 * 4 2 / − 4 / + 1 −
Стек:
5
2
*
2
3
4
−
/
−
1
+
/
4
=
6
2
4
1
6
5
Семинар 10. Стеки, очереди, деки

Очереди
FIFO: first in first out
Семинар 10. Стеки, очереди, деки

Операции с очередями
1. Опустошение.
2. Создание.
3. Получение значения начала без удаления.
4. Получение значения начала с удалением.
5. Добавление нового элемента.
6. Проверка пустоты.
Семинар 10. Стеки, очереди, деки

Реализация очереди на Си
struct list {
int data;
struct list *next;
};
typedef struct queue {
struct list *first;
struct list *last;
} Queue;
Семинар 10. Стеки, очереди, деки

Опустошение очереди
void makenull(Queue *Q)
{
struct list *p;
while (Q -> first) {
p = Q -> first;
Q -> first = p -> next;
free(p);
}
}
Семинар 10. Стеки, очереди, деки

Создание очереди
Queue *create()
{
Queue *Q;
Q = (Queue *) malloc(sizeof(Queue));
Q -> first = Q -> last = NULL;
return Q;
}
Семинар 10. Стеки, очереди, деки

Получение значения начала без удаления
int first(Queue *Q)
{
if (Q -> first)
return (Q -> first -> data);
else
return 0; /* или иная реакция на ошибку */
}
Семинар 10. Стеки, очереди, деки

Получение значения начала c удалением
int outqueue(Queue *Q)
{
int a;
struct list *p;
p = Q -> first;
a = p -> data;
Q -> first = p -> next;
free(p);
return a;
}
Семинар 10. Стеки, очереди, деки

Добавление нового элемента
void inqueue(int a, Queue *Q)
{
struct list *p;
p = (struct list *) malloc(sizeof(struct list));
p -> data = a;
Q -> last -> next = p;
p -> next = NULL;
Q -> last = p;
}
Семинар 10. Стеки, очереди, деки