Содержание
- 2. Линейный список - это множество, состоящее из n (n≥0) узлов (элементов) X[1], X[2], … , X[n],
- 3. Операции над линейными списками Получить доступ к k-му элементу списка, проанализировать и/или изменить значения его полей.
- 4. Не все операции нужны одновременно! => Будем различать типы линейных списков по набору главных операций, которые
- 5. Стек - это линейный список, в котором все включения и исключения (и всякий доступ) делаются в
- 6. Очередь - это линейный список, в котором все включения производятся на одном конце списка, все исключения
- 7. Дек (double-ended queue) очередь с двумя концами - это линейный список, в котором все включения и
- 8. Стеки push-down список реверсивная память гнездовая память магазин LIFO (last-in-first-out) список йо-йо
- 9. Операции работы со стеками makenull (S) – делает стек S пустым create(S) – создает стек top
- 10. Реализация стека на си struct list { int data; struct list * next; }; typedef struct
- 11. Реализация стека на си - продолжение void create (Stack *S) { S->top = NULL; } int
- 12. Реализация стека на си - продолжение int pop(Stack *S) { int a; struct list *p; p
- 13. void push(int a, Stack *S) { struct list *p; p = (struct list *) malloc (
- 14. Виды записи выражений Префиксная (операция перед операндами) Инфиксная или скобочная (операция между операндами) Постфиксная или обратная
- 15. Перевод из инфиксной формы в постфиксную Вход: строка, содержащая арифметическое выражение, записанное в инфиксной форме Выход:
- 16. Алгоритм Шаг 0: Взять первый элемент из входной строки и поместить его в X. Выходная строка
- 17. Перевод из инфиксной формы в постфиксную. Пример Входная строка: a + ( f – b *
- 18. Вычисления на стеке Вход: строка, содержащая выражение, записанное в постфиксной форме. Выход: число - значение заданного
- 19. Вычисления на стеке. Пример Входная строка: 5 2 3 * 4 2 / − 4 /
- 20. Очереди FIFO (first-in-first-out) –первый вошел, первый вышел
- 21. Операции работы с очередями makenull (Q) – делает очередь Q пустой create(Q) – создает очередь first
- 23. Скачать презентацию