Для более эффективного использования памяти компьютера (для исключения мусора, то есть неиспользуемых элементов) при работе его со списками создается свободный список, имеющий тот же формат полей, что и у функциональных списков.
Если у функциональных списков разный формат, то надо создавать свободный список каждого функционального списка.
Количество элементов в свободном списке должно быть определено задачей, которую решает программа. Как правило, свободный список создается в памяти машины как стек. При этом создание (GetNode) нового элемента эквивалентно выборке элемента свободного стека, а операция FreeNode — добавлению в свободный стек освободившегося элемента.
Пусть нам необходимо создать пустой список по типу стека (рис. 3.6) с указателем начала списка — AVAIL. Разработаем процедуры, которые позволят нам создавать пустой элемент списка и освобождать элемент из списка.
3.3.1 Операция GetNode
Разработаем процедуру, которая будет создавать пустой элемент списка с указателем Р.
Для реализации операции GetNode необходимо указателю сгенерированного элемента присвоить значение указателя начала свободного списка, а указатель начала перенести к следующему элементу.
P = Avail
Avail = Ptr(Avail)
Перед этим надо проверить, есть ли элементы в списке. Пустота свободного списка (Avail = Nil), эквивалентна переполнению функционального списка.
If Avail = Nil then Print “Переполнение” Stop
Else
P = Avail
Avail = Ptr(Avail)
Endif
3.3.2 Операция FreeNode
При освобождении элемента Nod(P) из функционального списка операцией FreeNode(P), он заносится в свободный список.
Ptr(P) = Avail
Avail = P
3.3.3 Утилизация освободившихся элементов в многосвязных списках
Стандартные операции возвращения освободившегося элемента списка в пул свободных элементов не всегда дают эффект, если используются нелинейные многосвязные списки.
Первый способ утилизации — метод счетчиков. В каждый элемент многосвязного списка вставляется поле счетчика, который считает количество ссылок на данный элемент. Когда счетчик элемента оказывается в нулевом состоянии, а поля указателей элемента находятся в состоянии nil, этот элемент может быть возвращен в пул свободных элементов.
Второй способ — метод сборки мусора (метод маркера). Если с каким-то элементом установлена связь, то однобитовое поле элемента (маркер) устанавливается в “1”, иначе — в “0”. По сигналу переполнения ищутся элементы, у которых маркер установлен в ноль, т. е. включается программа сборки мусора, которая просматривает всю отведенную память и возвращает в список свободных элементов все элементы, не помеченные маркером.
3.4 Односвязный список, как самостоятельная структура данных
Структуры и алгоритмы обработки данных
Для более эффективного использования памяти компьютера (для исключения мусора, то есть неиспользуемых элементов) при работе его со списками создается свободный список, имеющий тот же формат полей, что и у функциональных списков.
Если у функциональных списков разный формат, то надо создавать свободный список каждого функционального списка.
Количество элементов в свободном списке должно быть определено задачей, которую решает программа. Как правило, свободный список создается в памяти машины как стек. При этом создание (GetNode) нового элемента эквивалентно выборке элемента свободного стека, а операция FreeNode — добавлению в свободный стек освободившегося элемента.
Пусть нам необходимо создать пустой список по типу стека (рис. 3.6) с указателем начала списка — AVAIL. Разработаем процедуры, которые позволят нам создавать пустой элемент списка и освобождать элемент из списка.
3.3.1 Операция GetNode
Разработаем процедуру, которая будет создавать пустой элемент списка с указателем Р.
Для реализации операции GetNode необходимо указателю сгенерированного элемента присвоить значение указателя начала свободного списка, а указатель начала перенести к следующему элементу.
P = Avail
Avail = Ptr(Avail)
Перед этим надо проверить, есть ли элементы в списке. Пустота свободного списка (Avail = Nil), эквивалентна переполнению функционального списка.
If Avail = Nil then Print “Переполнение” Stop
Else
P = Avail
Avail = Ptr(Avail)
Endif
3.3.2 Операция FreeNode
При освобождении элемента Nod(P) из функционального списка операцией FreeNode(P), он заносится в свободный список.
Ptr(P) = Avail
Avail = P
3.3.3 Утилизация освободившихся элементов в многосвязных списках
Стандартные операции возвращения освободившегося элемента списка в пул свободных элементов не всегда дают эффект, если используются нелинейные многосвязные списки.
Первый способ утилизации — метод счетчиков. В каждый элемент многосвязного списка вставляется поле счетчика, который считает количество ссылок на данный элемент. Когда счетчик элемента оказывается в нулевом состоянии, а поля указателей элемента находятся в состоянии nil, этот элемент может быть возвращен в пул свободных элементов.
Второй способ — метод сборки мусора (метод маркера). Если с каким-то элементом установлена связь, то однобитовое поле элемента (маркер) устанавливается в “1”, иначе — в “0”. По сигналу переполнения ищутся элементы, у которых маркер установлен в ноль, т. е. включается программа сборки мусора, которая просматривает всю отведенную память и возвращает в список свободных элементов все элементы, не помеченные маркером.
3.4 Односвязный список, как самостоятельная структура данных
Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84