Линейные списки: стеки, очереди, деки. Лекция 3 - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Линейные списки: стеки, очереди, деки. Лекция 3, слайд №1

Линейные списки: стеки, очереди, деки. Лекция 3, слайд №2

Линейные списки: стеки, очереди, деки. Лекция 3, слайд №3

Линейные списки: стеки, очереди, деки. Лекция 3, слайд №4

Линейные списки: стеки, очереди, деки. Лекция 3, слайд №5

Линейные списки: стеки, очереди, деки. Лекция 3, слайд №6

Линейные списки: стеки, очереди, деки. Лекция 3, слайд №7

Линейные списки: стеки, очереди, деки. Лекция 3, слайд №8

Линейные списки: стеки, очереди, деки. Лекция 3, слайд №9

Линейные списки: стеки, очереди, деки. Лекция 3, слайд №10

Линейные списки: стеки, очереди, деки. Лекция 3, слайд №11

Линейные списки: стеки, очереди, деки. Лекция 3, слайд №12

Линейные списки: стеки, очереди, деки. Лекция 3, слайд №13

Линейные списки: стеки, очереди, деки. Лекция 3, слайд №14

Линейные списки: стеки, очереди, деки. Лекция 3, слайд №15

Линейные списки: стеки, очереди, деки. Лекция 3, слайд №16

Линейные списки: стеки, очереди, деки. Лекция 3, слайд №17

Линейные списки: стеки, очереди, деки. Лекция 3, слайд №18

Линейные списки: стеки, очереди, деки. Лекция 3, слайд №19

Линейные списки: стеки, очереди, деки. Лекция 3, слайд №20

Линейные списки: стеки, очереди, деки. Лекция 3, слайд №21

Линейные списки: стеки, очереди, деки. Лекция 3, слайд №22

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Линейные списки: стеки, очереди, деки. Лекция 3. Доклад-сообщение содержит 22 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Линейные списки: стеки, очереди, деки Лекция 3

Слайд 2

Описание слайда:

Линейный список - это множество, состоящее из 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

Описание слайда:

Операции над линейными списками Получить доступ к k-му элементу списка, проанализировать и/или изменить значения его полей. Включить новый узел перед k- м. Исключить k-й узел. Объединить два или более линейных списков в один. Разбить линейный список на два или более линейных списков. Сделать копию линейного списка. Определить количество узлов. Выполнить сортировку в возрастающем порядке по некоторым значениям полей в узлах. Найти в списке узел с заданным значением в некотором поле. … и т.д.

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

Стек - это линейный список, в котором все включения и исключения (и всякий доступ) делаются в одном конце списка

Слайд 6

Описание слайда:

Очередь - это линейный список, в котором все включения производятся на одном конце списка, все исключения – на другом его конце.

Слайд 7

Описание слайда:

Дек (double-ended queue) очередь с двумя концами - это линейный список, в котором все включения и исключения производятся на обоих концах списка

Слайд 8

Описание слайда:

Стеки push-down список реверсивная память гнездовая память магазин LIFO (last-in-first-out) список йо-йо

Слайд 9

Описание слайда:

Операции работы со стеками makenull (S) – делает стек S пустым create(S) – создает стек top (S) – выдает значение верхнего элемента стека, не удаляя его pop(S) – выдает значение верхнего элемента стека и удаляет его из стека push(x, S) – помещает в стек S новый элемент со значением x empty (S) - если стек пуст, то функция возвращает 1 (истина), иначе – 0 (ложь).

Слайд 10

Описание слайда:

Реализация стека на си 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

Описание слайда:

Реализация стека на си - продолжение void create (Stack *S) { S->top = NULL; } int top (Stack *S) { if (S->top) return (S->top->data); else return 0; //здесь может быть реакция на //ошибку – обращение к пустому стеку }

Слайд 12

Описание слайда:

Реализация стека на си - продолжение int pop(Stack *S) { int a; struct list *p; p = S->top; a = p->data; S-> top = p->next; free(p); return a; }

Слайд 13

Описание слайда:

Реализация стека на си - продолжение 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

Описание слайда:

Виды записи выражений Префиксная (операция перед операндами) Инфиксная или скобочная (операция между операндами) Постфиксная или обратная польская (операция после операндов) Примеры: 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

Описание слайда:

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

Слайд 16

Описание слайда:

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

Слайд 17

Описание слайда:

Перевод из инфиксной формы в постфиксную. Пример Входная строка: a + ( f – b * c / ( z – x ) + y ) / ( a * r – k )

Слайд 18

Описание слайда:

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

Слайд 19

Описание слайда:

Вычисления на стеке. Пример Входная строка: 5 2 3 * 4 2 / − 4 / + 1 −

Слайд 20

Описание слайда:

Очереди FIFO (first-in-first-out) –первый вошел, первый вышел

Слайд 21

Описание слайда:

Операции работы с очередями makenull (Q) – делает очередь Q пустой create(Q) – создает очередь first (Q) – выдает значение первого элемента очереди, не удаляя его dequeue(Q) – выдает значение первого элемента очереди и удаляет его из очереди inqueue(x, Q) – помещает в конец очереди Q новый элемент со значением x empty (Q) - если очередь пуста, то функция возвращает 1 (истина), иначе – 0 (ложь).