Презентация Линейные списки: стеки, очереди, деки. Лекция 3 онлайн
Оцените презентацию от 1 до 5 баллов!
Тип файла:
ppt / pptx (powerpoint)
Всего слайдов:
22 слайда
Для класса:
1,2,3,4,5,6,7,8,9,10,11
Размер файла:
98.75 kB
Просмотров:
84
Скачиваний:
0
Автор:
неизвестен
Слайды и текст к этой презентации:
№1 слайд![Линейные списки стеки,](/documents_6/3d685b42ee46981916bfa0dffe6e57ec/img0.jpg)
Содержание слайда: Линейные списки:
стеки, очереди, деки
Лекция 3
№2 слайд![Линейный список - это](/documents_6/3d685b42ee46981916bfa0dffe6e57ec/img1.jpg)
Содержание слайда: Линейный список
- это множество, состоящее из n (n≥0) узлов (элементов) X[1], X[2], … , X[n], структурные свойства которого ограничены линейным (одномерным) относительным положением узлов (элементов), т.е. следующими условиями:
если n > 0, то X[1] – первый узел;
если 1 < k < n,
то k-му узлу X[k] предшествует узел X[k-1],
а за узлом X[k] следует узел X[k+1];
X[n] – последний узел.
№3 слайд![Операции над линейными](/documents_6/3d685b42ee46981916bfa0dffe6e57ec/img2.jpg)
Содержание слайда: Операции над линейными списками
Получить доступ к k-му элементу списка, проанализировать и/или изменить значения его полей.
Включить новый узел перед k- м.
Исключить k-й узел.
Объединить два или более линейных списков в один.
Разбить линейный список на два или более линейных списков.
Сделать копию линейного списка.
Определить количество узлов.
Выполнить сортировку в возрастающем порядке по некоторым значениям полей в узлах.
Найти в списке узел с заданным значением в некотором поле.
… и т.д.
№4 слайд![Не все операции нужны](/documents_6/3d685b42ee46981916bfa0dffe6e57ec/img3.jpg)
Содержание слайда: Не все операции нужны одновременно!
=>
Будем различать типы линейных списков по набору главных операций, которые над ними выполняются.
№5 слайд![Стек - это линейный список, в](/documents_6/3d685b42ee46981916bfa0dffe6e57ec/img4.jpg)
Содержание слайда: Стек
- это линейный список, в котором все включения и исключения (и всякий доступ) делаются в одном конце списка
№6 слайд![Очередь - это линейный](/documents_6/3d685b42ee46981916bfa0dffe6e57ec/img5.jpg)
Содержание слайда: Очередь
- это линейный список, в котором все включения производятся на одном конце списка, все исключения – на другом его конце.
№7 слайд![Дек double-ended queue](/documents_6/3d685b42ee46981916bfa0dffe6e57ec/img6.jpg)
Содержание слайда: Дек (double-ended queue)
очередь с двумя концами
- это линейный список, в котором все включения и исключения производятся на обоих концах списка
№8 слайд![Стеки push-down список](/documents_6/3d685b42ee46981916bfa0dffe6e57ec/img7.jpg)
Содержание слайда: Стеки
push-down список
реверсивная память
гнездовая память
магазин
LIFO (last-in-first-out)
список йо-йо
№9 слайд![Операции работы со стеками](/documents_6/3d685b42ee46981916bfa0dffe6e57ec/img8.jpg)
Содержание слайда: Операции работы со стеками
makenull (S) – делает стек S пустым
create(S) – создает стек
top (S) – выдает значение верхнего элемента стека, не удаляя его
pop(S) – выдает значение верхнего элемента стека и удаляет его из стека
push(x, S) – помещает в стек S новый элемент со значением x
empty (S) - если стек пуст, то функция возвращает 1 (истина), иначе – 0 (ложь).
№10 слайд![Реализация стека на си struct](/documents_6/3d685b42ee46981916bfa0dffe6e57ec/img9.jpg)
Содержание слайда: Реализация стека на си
struct list {
int data;
struct list * next;
};
typedef struct stack { struct list *top; } Stack;
void makenull (Stack *S)
{ struct list *p;
while (S->top)
{
p = S->top;
S->top = p->next;
free(p);
}
}
№11 слайд![Реализация стека на си -](/documents_6/3d685b42ee46981916bfa0dffe6e57ec/img10.jpg)
Содержание слайда: Реализация стека на си - продолжение
void create (Stack *S)
{
S->top = NULL;
}
int top (Stack *S)
{
if (S->top)
return (S->top->data);
else
return 0; //здесь может быть реакция на //ошибку – обращение к пустому стеку
}
№12 слайд![Реализация стека на си -](/documents_6/3d685b42ee46981916bfa0dffe6e57ec/img11.jpg)
Содержание слайда: Реализация стека на си - продолжение
int pop(Stack *S)
{
int a;
struct list *p;
p = S->top;
a = p->data;
S-> top = p->next;
free(p);
return a;
}
№13 слайд![Реализация стека на си -](/documents_6/3d685b42ee46981916bfa0dffe6e57ec/img12.jpg)
Содержание слайда: Реализация стека на си - продолжение
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 ;
}
int empty (Stack *S)
{
return (S->top == NULL);
}
№14 слайд![Виды записи выражений](/documents_6/3d685b42ee46981916bfa0dffe6e57ec/img13.jpg)
Содержание слайда: Виды записи выражений
Префиксная (операция перед операндами)
Инфиксная или скобочная (операция между операндами)
Постфиксная или обратная польская (операция после операндов)
Примеры:
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 – / + - постфиксная
№15 слайд![Перевод из инфиксной формы в](/documents_6/3d685b42ee46981916bfa0dffe6e57ec/img14.jpg)
Содержание слайда: Перевод из инфиксной формы в постфиксную
Вход: строка, содержащая арифметическое выражение, записанное в инфиксной форме
Выход: строка, содержащая то же выражение, записанное в постфиксной форме (обратной польской записи).
Обозначения:
числа, строки (идентификаторы) – операнды;
№16 слайд![Алгоритм Шаг Взять первый](/documents_6/3d685b42ee46981916bfa0dffe6e57ec/img15.jpg)
Содержание слайда: Алгоритм
Шаг 0:
Взять первый элемент из входной строки и поместить его в X.
Выходная строка и стек пусты.
Шаг 1:
Если X – операнд, то дописать его в конец выходной строки.
Если X = ‘(‘, то поместить его в стек.
Если X = ‘)‘, то вытолкнуть из стека и поместить в конец выходной строки все элементы до первой встреченной открывающей скобки. Эту скобку вытолкнуть из стека.
Если X – знак операции, отличный от скобок, то пока стек не пуст, и верхний элемент стека имеет приоритет, больший либо равный приоритету X, вытолкнуть его из стека и поместить в выходную строку. Затем поместить X в стек.
Шаг 2:
Если входная строка не исчерпана, то поместить в X очередной элемент входной строки и перейти на Шаг 1, иначе
пока стек не пуст, вытолкнуть из стека содержимое в выходную строку.
№17 слайд![Перевод из инфиксной формы в](/documents_6/3d685b42ee46981916bfa0dffe6e57ec/img16.jpg)
Содержание слайда: Перевод из инфиксной формы в постфиксную. Пример
Входная строка:
a + ( f – b * c / ( z – x ) + y ) / ( a * r – k )
№18 слайд![Вычисления на стеке Вход](/documents_6/3d685b42ee46981916bfa0dffe6e57ec/img17.jpg)
Содержание слайда: Вычисления на стеке
Вход: строка, содержащая выражение, записанное в постфиксной форме.
Выход: число - значение заданного выражения.
Алгоритм:
Шаг 0:
Стек пуст.
Взять первый элемент из входной строки и поместить его в X.
Шаг 1:
Если X – операнд, то поместить его в стек.
Если X – знак операции, то вытолкнуть из стека два верхних элемента, применить к ним соответствующую операцию, результат положить в стек.
Шаг 2:
Если входная строка не исчерпана, то поместить в X очередной элемент входной строки и перейти на Шаг 1, иначе вытолкнуть из стека результат вычисления выражения.
№19 слайд![Вычисления на стеке. Пример](/documents_6/3d685b42ee46981916bfa0dffe6e57ec/img18.jpg)
Содержание слайда: Вычисления на стеке. Пример
Входная строка:
5 2 3 * 4 2 / − 4 / + 1 −
№20 слайд![Очереди FIFO](/documents_6/3d685b42ee46981916bfa0dffe6e57ec/img19.jpg)
Содержание слайда: Очереди
FIFO (first-in-first-out) –первый вошел, первый вышел
№21 слайд![Операции работы с очередями](/documents_6/3d685b42ee46981916bfa0dffe6e57ec/img20.jpg)
Содержание слайда: Операции работы с очередями
makenull (Q) – делает очередь Q пустой
create(Q) – создает очередь
first (Q) – выдает значение первого элемента очереди, не удаляя его
dequeue(Q) – выдает значение первого элемента очереди и удаляет его из очереди
inqueue(x, Q) – помещает в конец очереди Q новый элемент со значением x
empty (Q) - если очередь пуста, то функция возвращает 1 (истина), иначе – 0 (ложь).
№22 слайд![Реализация очереди на си](/documents_6/3d685b42ee46981916bfa0dffe6e57ec/img21.jpg)
Содержание слайда: Реализация очереди на си
struct list
{
int data;
struct list * next;
};
typedef struct queue
{
struct list *first;
struct list *end;
} Queue;