Списки. Лекция 6

Июль 31, 2022

Главная
Информатика
Списки. Лекция 6

Содержание

2. Мем
3. Что такое список Список – структура данных, которая предоставляет место для хранения однотипных данных в памяти.
4. Типы поведения списка Для каждого списка требуется прописать его поведение для операции. Например, куда добавлять новый
5. Односвязный список Узел списка struct node { int data; node *next; }; Организация списка
6. Двусвязный список Узел списка struct node { int data; node *next; node *prev; }; Организация списка
7. Кольцевой список Узел списка struct node { int data; node *next; node *prev; }; Организация списка
8. Стек Стек - список элементов, организованных по принципу LIFO (англ. last in — first out, «последним
9. Очередь Очередь - список с дисциплиной доступа к элементам «первый пришёл — первый вышел» (FIFO, First
10. Двусторонняя очередь Дек – список, в который элементы можно добавлять и удалять как в начало, так
11. Основные операции, реализуемые над списком Опрос размера списка Добавление элемента Удаление элемента Вставка элемента Поиск Сортировка
12. Разберем пример: односвязный список
13. Добавление узла в начало списка
14. Вставка по позиции
15. Удаление по позиции
16. Показ всего списка и поиск
18. Скачать презентацию

Слайд 2

Мем

Слайд 3

Что такое список
Список – структура данных, которая предоставляет место для хранения

однотипных данных в памяти. В отличие от массива, список ограничен только памятью компьютера, но плох в плане доступа к элементу по индексу и по используемой памяти. Алгоритмы добавления и удаления работают эффективнее, но некоторые алгоритмы, такие как поиск и доступ к элементу, работают медленнее. Также на элемент списка нужно больше памяти.

Слайд 4

Типы поведения списка
Для каждого списка требуется прописать его поведение для операции.

Например, куда добавлять новый элемент, как связывать списки, как удалять элемент, доступ к данным, обход списка и так далее.
Различаются списки по связям:
Односвязный список
Двусвязный список
Кольцевой односвязный/двусвязный
Развернутый связный

Слайд 5

Односвязный список
Узел списка
struct node
{
int data;
node *next;
};
Организация списка

Слайд 6

Двусвязный список
Узел списка
struct node
{
int data;
node next;
node prev;
};
Организация списка

Слайд 7

Кольцевой список
Узел списка
struct node
{
int data;
node next;
node prev;
};
Организация списка

Слайд 8

Стек
Стек - список элементов, организованных по принципу LIFO (англ. last in

— first out, «последним пришёл — первым вышел»).
У стека только есть только один конец для работы. В него заносятся элементы и из него же они удаляются. Таким образом, для стека должны быть определены 2 операции: push и pop

Слайд 9

Очередь
Очередь - список с дисциплиной доступа к элементам «первый пришёл —

первый вышел» (FIFO, First In — First Out). Добавление элемента возможно лишь в конец очереди, выборка — только из начала очереди при этом выбранный элемент из очереди удаляется.

Слайд 10

Двусторонняя очередь
Дек – список, в который элементы можно добавлять и удалять

как в начало, так и в конец, то есть дисциплинами обслуживания являются одновременно FIFO и LIFO.

Слайд 11

Основные операции, реализуемые над списком
Опрос размера списка
Добавление элемента
Удаление элемента
Вставка элемента
Поиск
Сортировка
Выведение всего

списка
Очистка списка

Слайд 12

Разберем пример: односвязный список

Слайд 13

Добавление узла в начало списка

Слайд 14

Вставка по позиции

Слайд 15

Удаление по позиции

Слайд 16

Списки. Лекция 6

Содержание

Мем

Что такое списокСписок – структура данных, которая предоставляет место для хранения

Типы поведения спискаДля каждого списка требуется прописать его поведение для операции.

Односвязный списокУзел спискаstruct node{int data;node *next;};Организация списка

Двусвязный списокУзел спискаstruct node{int data;node *next;node *prev;};Организация списка

Кольцевой списокУзел спискаstruct node{int data;node *next;node *prev;};Организация списка

СтекСтек - список элементов, организованных по принципу LIFO (англ. last in

ОчередьОчередь - список с дисциплиной доступа к элементам «первый пришёл —

Двусторонняя очередьДек – список, в который элементы можно добавлять и удалять

Основные операции, реализуемые над спискомОпрос размера спискаДобавление элементаУдаление элементаВставка элементаПоискСортировкаВыведение всего