Линейные списки. Структура данных очередь

Сентябрь 3, 2022

Главная
Информатика
Линейные списки. Структура данных очередь

Содержание

2. Простой пример – очередь в кассу, если очереди нет, обслуживаешься сразу, иначе, становишься в ее конец.
3. Односвязный список (очередь) Шаблон структуры, информационная часть (ИЧ) которого – целое число: struct Spis1 { //
4. При создании очереди организуется структура следующего вида: Каждый элемент очереди имеет информацион-ную infо (ИЧ1, …, ИЧn)
5. Основные операции с очередью: – формирование очереди; – добавление нового элемента в конец очереди; – удаление
6. Формирование очереди состоит из двух этапов: создание первого элемента, добавление нового элемента в конец. Создание первого
7. 3. Формирование информационной части: t -> info = i; (обозначим i1 ) 4. В адресную часть
8. Добавление элемента в очередь Рассмотрим добавление только для второго элемента. 1. Ввод информации для текущего (второго)
9. 5. Элемент добавляется в конец, поэтому в адресную часть бывшего последнего элемента end заносим адрес созданного:
10. В результате получим Для добавления в очередь любого количества элементов организуется цикл, включающий пункты 1 –
11. Обобщив оба этапа, функция формирования оче-реди может иметь следующий вид (b – начало, e – конец,
12. // Иначе добавляем элемент в конец else { (*e) -> next = t; *e = t;
13. Эту функцию можно реализовать иначе: Spis1* Create (Spis1 **b, Spis1 *e, int in) { Spis1 *t
14. В функцию передаются: адрес указателя на начало списка, чтобы при его изменении обеспечить возврат в точку
15. Удаление первого элемента из очереди аналогично извлечению элемента из Стека… Пусть очередь создана (begin не равен
16. 4. Освобождаем память, занятую бывшим пер-вым: delete t; Алгоритмы просмотра и освобождения памя-ти аналогичны рассмотренным ранее
17. Очередь может быть организована и в виде двухсвязного (двунаправленного) списка, в каждом элементе которого два указателя:
18. Графически такой список выглядит следующим образом: Адреса begin -> prev (предыдущий у первого) и end ->
19. Формирование двунаправленного списка проводится в два этапа – формирование первого элемента и добавление нового, причем доба-вление
20. Создание первого элемента 1. Захват памяти: t = new Spis2; формируется конкретный адрес в ОП. 2.
21. Получили первый элемент списка:
22. Добавление элемента Захват памяти и формирование ИЧ аналогичны рассмотренным пунктам 1 – 2. Добавление в начало
23. Схема добавления элемента в начало
24. Добавление в конец списка 3.2. Формирование адресных частей: а) следующего нет: t -> next = NULL;
25. Схема добавления элемента в конец
26. Алгоритм просмотра списка
27. Алгоритм поиска по ключу Ключом может быть любое поле структуры, обычно это значение должно быть уникаль-ным
28. 4. Начало цикла (выполняем пока t != NULL). 5. Сравниваем ИЧ текущего элемента t с i_key.
29. Алгоритм удаления ОДНОГО элемента по ключу Удалить из списка элемент, ИЧ (ключ) которого совпадает с введенным
30. Удаление 1. Если удаляемый элемент находится в начале списка, т.е. key = begin, то первым элементом
31. Схема удаления элемента key из начала списка:
32. 2. Иначе, если удаляемый элемент в конце списка (key = end), то последним элементом в списке
33. Схема удаления элемента key из конца списка:
34. 3. Иначе, если элемент key находится в середине списка, нужно обеспечить связь предыдущего key -> prev
35. Схема удаления key из середины списка:
36. Алгоритм вставки элемента после элемента с указанным ключом Вставить в список элемент после элемента, значение ИЧ
37. Этап второй – вставка Найден адрес элемента key, после которого вставляем новый. 1. Захватываем память под
38. 5. Связываем предыдущий элемент с новым key -> next = t; 6. Если элемент добавляется не
39. Общая схема вставки элемента:
41. Скачать презентацию

Слайд 2

Простой пример – очередь в кассу, если очереди нет, обслуживаешься сразу,

иначе, становишься в ее конец.
Последовательно обслуживаются стоящие в на-чале очереди.
В течение дня очередь то увеличивается, то уменьшается и может отсутствовать.
Очереди организуются в виде односвязных или двухсвязных списков, в зависимости от коли-чества связей (указателей) в адресной части элемента структуры.

Слайд 3

Односвязный список (очередь)
Шаблон структуры, информационная часть (ИЧ) которого – целое число:
struct

Spis1 { // Или TList1
int info;
Spis1 *next;
};
При организации очереди обычно используют два указателя
Spis1 *begin, *end;
begin и end – указатели на начало и конец.

Слайд 4

При создании очереди организуется структура следующего вида:
Каждый элемент очереди имеет информацион-ную

infо (ИЧ1, …, ИЧn) и адресную next (A2, A3, ..., AN) части.
Адресная часть последнего элемента равна NULL.

Слайд 5

Основные операции с очередью:
– формирование очереди;
– добавление нового элемента в конец

очереди;
– удаление элемента из начала очереди;
– обработка элементов (просмотр, поиск и др.);
– освобождение памяти, занятой очередью.

Слайд 6

Формирование очереди состоит из двух этапов: создание первого элемента, добавление нового

элемента в конец.
Создание первого элемента
1. Ввод информации для первого элемента (например, целое число i );
2. Захват памяти, используя текущий указатель:
t = new Spis1;
формируется конкретный адрес (А1) для первого элемента;

Слайд 7

3. Формирование информационной части:
t -> info = i; (обозначим i1 )
4. В

адресную часть записываем NULL:
t -> next = NULL;
5. Указатели начала и конца очереди устанавли-ваем на созданный элемент t :
begin = end = t;
На этом этапе получим следующее:

Слайд 8

Добавление элемента в очередь
Рассмотрим добавление только для второго элемента.
1. Ввод информации

для текущего (второго) элемента – значение i .
2. Захват памяти под текущий элемент:
t = new Spis1; (адрес A2)
3. Формирование информационной части (i2):
t -> info = i;
4. В адресную часть заносим NULL, т.к. этот элемент становится последним:
t -> next = NULL;

Слайд 9

5. Элемент добавляется в конец, поэтому в адресную часть бывшего последнего

элемента end заносим адрес созданного:
end -> next = t;
бывший последний элемент становится пред-последним.
6. Переставляем указатель end последнего элемента на добавленный:
end = t;
Обратите внимание, что пункты 1 – 4 обоих этапов идентичны.

Слайд 10

В результате получим
Для добавления в очередь любого количества элементов организуется цикл,

включающий пункты 1 – 6 рассмотренного алгоритма.
Завершение цикла реализуется в зависимости от поставленной задачи.

Слайд 11

Обобщив оба этапа, функция формирования оче-реди может иметь следующий вид (b

– начало, e – конец, in – введенная ранее информация):
void Create (Spis1 **b, Spis1 **e, int in) {
Spis1 *t = new Spis1; // Захват памяти
t -> info = in; // Формирование ИЧ
t -> next = NULL; // Формирование АЧ
// Если указатель на начало равен NULL, то
// формируем первый элемент
if ( *b == NULL )
*b = *e = t;

Слайд 12

// Иначе добавляем элемент в конец
else { (e) -> next = t;
e

= t;
}
}
В функцию передаются адреса указателей, чтобы при изменении обеспечить их возврат в точку вызова.
Обращение к данной функции
Create (&begin, &end, in);

Слайд 13

Эту функцию можно реализовать иначе:
Spis1* Create (Spis1 **b, Spis1 *e, int

in) {
Spis1 *t = new Spis1;
t -> info = in;
t -> next = NULL;
if ( *b == NULL )
*b = e = t;
else { e -> next = t;
e = t;
}
return e;
}

Слайд 14

В функцию передаются:
адрес указателя на начало списка, чтобы при его изменении

обеспечить возврат в точку вызова;
значение указателя на конец списка, измененное значение которого возвращается в точку вызо-ва оператором return e ;
значение ранее введенной ИЧ in.
Обращение к функции в этом случае :
end = Create (&begin, end, in);

Слайд 15

Удаление первого элемента из очереди аналогично извлечению элемента из Стека…
Пусть

очередь создана (begin не равен NULL, рекомендуется организовать эту проверку).
1. Устанавливаем текущий указатель t на начало:
t = begin;
2. Обрабатываем ИЧ первого элемента (напри-мер, выводим на экран).
3. Указатель начала переставляем на следую-щий (2-й) элемент
begin = begin -> next;

Слайд 16

4. Освобождаем память, занятую бывшим пер-вым:
delete t;
Алгоритмы просмотра и освобождения

памя-ти аналогичны рассмотренным ранее для Стека.
В функциях просмотра View и освобождения памяти Del_All, реализующих эти алгоритмы, необходимо только изменить типы данных (вместо Stack пишем Spis1).

Слайд 17

Очередь может быть организована и в виде двухсвязного (двунаправленного) списка, в

каждом элементе которого два указателя: на предыдущий (prev) и следующий (next).
Шаблон такой структуры будет иметь вид:
struct Spis2 { // Или TList2
Информационная часть
Spis2 *prev, *next; – Адресная часть
} ;
Для работы с такими списками обычно исполь-зуются указатели на начало begin и на конец end списка.

Слайд 18

Графически такой список выглядит следующим образом:
Адреса begin -> prev (предыдущий

у первого) и end -> next (следующий за последним) равны NULL.

Слайд 19

Формирование двунаправленного списка
проводится в два этапа – формирование первого элемента

и добавление нового, причем доба-вление может выполняться как в начало, так и в конец списка.
Введем структуру, информационной частью info которой будут целые числа:
struct Spis2 { // Или TList2
int info;
Spis2 *prev, *next;
} ;

Слайд 20

Создание первого элемента
1. Захват памяти: t = new Spis2;
формируется конкретный адрес

в ОП.
2. Ввод переменной i и формирование ИЧ:
t -> info = i;
3. Формирование адресных частей (для первого элемента – это NULL):
t -> next = t -> prev = NULL;
4. Установка указателей начала и конца списка на созданный первый элемент:
begin = end = t;

Слайд 21

Получили первый элемент списка:

Слайд 22

Добавление элемента
Захват памяти и формирование ИЧ аналогичны рассмотренным пунктам 1 –

2.
Добавление в начало списка
3.1. Формирование адресных частей:
а) предыдущего нет: t -> prev = NULL;
б) связываем новый элемент с первым
t -> next = begin;
4.1. Изменяем адреса:
а) изменяем адрес prev бывшего первого
begin -> prev = t;
б) переставляем указатель begin на новый
begin = t;

Слайд 23

Схема добавления элемента в начало

Слайд 24

Добавление в конец списка
3.2. Формирование адресных частей:
а) следующего нет: t

-> next = NULL;
б) связываем новый элемент с последним
t -> prev = end;
4.2. Изменяем адреса:
а) изменяем адрес next бывшего последнего
end -> next = t;
б) переставляем указатель end на новый
end = t;
Внимание, включив пункты 1 – 4 в цикл, можно добавить нужное количество элементов.

Слайд 25

Схема добавления элемента в конец

Слайд 26

Алгоритм просмотра списка

Слайд 27

Алгоритм поиска по ключу
Ключом может быть любое поле структуры, обычно это

значение должно быть уникаль-ным (не повторяться). В нашем случае найдем в списке элемент, информационная часть (ключ) которого совпадает с введенным с кла-виатуры значением (i_key ).
1. Введем дополнительный указатель:
Spis2 *key = NULL;
2. Введем значение искомого ключа i_key.
3. Установим текущий указатель на начало:
t = begin;

Слайд 28

4. Начало цикла (выполняем пока t != NULL).
5. Сравниваем ИЧ текущего

элемента t с i_key.
5.1. Если они совпадают (t -> info = i_key):
а) запоминаем адрес найденного элемента:
key = t; (выводим key -> info на экран)
б) т.к. ключи уникальны, завершаем поиск
(выход из цикла break).
5.2. Иначе, переставляем текущий указатель t:
t = t -> next;
6. Конец цикла.
7. Если key = NULL, т.е. искомый элемент не найден, то выводим сообщение о неудаче.

Слайд 29

Алгоритм удаления ОДНОГО элемента по ключу
Удалить из списка элемент, ИЧ (ключ)

которого совпадает с введенным значением.
Решение задачи проводим в два этапа – поиск и удаление.
Первый этап «Поиск» рассмотрен ранее.
Второй этап «Удаление» выполняем, если элемент для удаления найден (key ≠ NULL).
Удаление выполняем в зависимости от распо-ложения элемента с адресом key в списке.

Слайд 30

Удаление
1. Если удаляемый элемент находится в начале списка, т.е. key

= begin, то первым элементом списка должен стать второй:
а) указатель на начало переставляем на сле-дующий (второй) элемент:
begin = begin -> next;
б) адрес prev элемента, который был вторым, а теперь становится первым в NULL, т.е. преды-дущего нет, причем исключаем ситуацию, если begin остался один, т.е. если begin != NULL
begin -> prev = NULL;

Слайд 31

Схема удаления элемента key из начала списка:

Слайд 32

2. Иначе, если удаляемый элемент в конце списка (key = end),

то последним элементом в списке должен стать предпоследний:
а) указатель конца списка переставляем на предыдущий элемент, адрес которого в поле рrev последнего end элемента:
end = end -> prev;
б) обнуляем адрес next нового последнего элемента
end -> next = NULL;

Слайд 33

Схема удаления элемента key из конца списка:

Слайд 34

3. Иначе, если элемент key находится в середине списка, нужно обеспечить

связь предыдущего key -> prev и следующего key->next элементов:
а) адрес next предыдущего элемента key -> prev переставим на следующий элемент key -> next:
(key -> prev) -> next = key -> next;
б) и наоборот, адрес prev следующего элемента key -> next переставим на предыдущий key -> prev:
(key -> next) -> prev = key -> prev;
4. Освобождаем память, занятую удаленным элементом delete key;

Слайд 35

Схема удаления key из середины списка:

Слайд 36

Алгоритм вставки элемента после элемента с указанным ключом
Вставить в список элемент

после элемента, значение ИЧ (ключ) которого совпадает с введенным.
Решение данной задачи проводится в два этапа – поиск и вставка.
Поиск аналогичен рассмотренному в алгоритме удаления.
Вставку выполняем, если искомый элемент най-ден, т.е. указатель key не равен NULL.

Слайд 37

Этап второй – вставка
Найден адрес элемента key, после которого вставляем новый.
1.

Захватываем память под новый элемент
t = new Spis2;
2. Формируем ИЧ (t -> info).
3. Связываем новый элемент с предыдущим
t -> prev = key;
4. Связываем новый элемент со следующим t -> next = key -> next;
если key = end, то t -> next = key -> next = NULL.

Слайд 38

5. Связываем предыдущий элемент с новым
key -> next = t;
6. Если

элемент добавляется не в конец списка (как показано на рисунке), т.е. key не равен end, то
( t -> next ) -> prev = t;
7. Иначе (key = end), то указатель key -> next равен NULL (см п. 4) и новым последним становится t :
end = t;

Слайд 39

Линейные списки. Структура данных очередь

Содержание

Простой пример – очередь в кассу, если очереди нет, обслуживаешься сразу,

Односвязный список (очередь)Шаблон структуры, информационная часть (ИЧ) которого – целое число: struct

При создании очереди организуется структура следующего вида: Каждый элемент очереди имеет информацион-ную

Основные операции с очередью: – формирование очереди; – добавление нового элемента в конец

Формирование очереди состоит из двух этапов: создание первого элемента, добавление нового

3. Формирование информационной части: t -> info = i; (обозначим i1 )4. В

Добавление элемента в очередьРассмотрим добавление только для второго элемента.1. Ввод информации

5. Элемент добавляется в конец, поэтому в адресную часть бывшего последнего

В результате получимДля добавления в очередь любого количества элементов организуется цикл,

Обобщив оба этапа, функция формирования оче-реди может иметь следующий вид (b

// Иначе добавляем элемент в конец else { (*e) -> next = t; *e

Эту функцию можно реализовать иначе: Spis1* Create (Spis1 **b, Spis1 *e, int

В функцию передаются:адрес указателя на начало списка, чтобы при его изменении

Удаление первого элемента из очереди аналогично извлечению элемента из Стека…Пусть

4. Освобождаем память, занятую бывшим пер-вым: delete t;Алгоритмы просмотра и освобождения