Мультисписки

В программных системах, обрабатывающих объекты сложной

структуры, могут решаться разные подзадачи, каждая из которых

требует, возможно, обработки не всего множества объектов, а лишь

какого-то его подмножества. Так, например, в автоматизированной

системе учета лиц, пострадавших вследствие аварии на ЧАЭС, каждая

запись об одном пострадавшем содержит более 50 полей в своей ин-

формационной части. Решаемые же автоматизированной системой зада-

чи могут потребовать выборки, например:

- участников ликвидации аварии;

- переселенцев из зараженной зоны;

- лиц, состоящих на квартирном учете;

- лиц с заболеваниями щитовидной железы;

- и т.д., и т.п.

дескриптор ┌───┬─>┬>┬────>┌──────┐ ┌>┌────────>┌──────┐

общего └───┘ │ │ │данные│ │ │ │данные│

списка │ │ ├──────┤ │ │ ├──────┤

│ │ │ ┼─┐ │ │ │ ┼─┐

│ │ ├──────┤ │ │ │ ├──────┤ │

│ │ ┌───┼ │ │ │ │ │ │ │

дескриптор ┌───┬──┘ │ │ ├──────┤ │ │ │ ├──────┤ │

списка └───┘ │ │ │ ┼─┼─┘ │ ┌─────┼ │ │

ликвидаторов │ │ └──────┘ │ │ │ └──────┘ │

│ │ ┌──────────┘ │ │ ┌──────────┘

│ │ │ │ │ │

│ │ └>┌──────┐ │ ┌─┼──>└>┌──────┐

дескриптор ┌───┬──┐ │ │ │данные│ │ │ │ │данные│

списка └───┘ │ │ │ ├──────┤ │ │ │ ├──────┤

кварт.учета │ │ │ │ ┼─┐ │ │ │ │ ┼─┐

│ │ │ ├──────┤ │ │ │ │ ├──────┤ │

│ │ │ │ │ │ │ │ │ ┌───┼ │ │

│ │ │ ├──────┤ │ │ │ │ │ ├──────┤ │

│ │ │ │ │ │ │ │ │ │ │ │ │

│ │ │ └──────┘ │ │ │ │ │ └──────┘ │

│ │ │ ┌──────────┘ │ │ │ │ ┌──────────┘

│ │ │ │ │ │ │ │ │

└─┼>└>└>┌──────┐ │ │ │ └>└>┌──────┐

│ │данные│ │ │ │ │данные│

│ ├──────┤ │ │ │ ├──────┤

│ │ ┼─────┘ │ │ │ ┼─┐

│ ├──────┤ │ │ ├──────┤ │

│ │ ┼───────┘ │ ┌─┼ │ │

│ ├──────┤ │ │ ├──────┤ │

└─────┼ │ │ │ │ │ │

└──────┘ | | └──────┘ |

Рис.5.11. Пример мультисписка

Для того, чтобы при выборке каждого подмножества не выпол-

нять полный просмотр с отсеиванием записей, к требуемому подмно-

жеству не относящихся, в каждую запись включаются дополнительные

поля ссылок, каждое из которых связывает в линейный список эле-

менты соответствующего подмножества. В результате получается мно-

госвязный список или мультисписок, каждый элемент которого может

входить одновременно в несколько односвязных списков. Пример та-

кого мультисписка для названной нами автоматизированной системы

показан на рис.5.11.

К достоинствам мультисписков помимо экономии памяти (при

множестве списков информационная часть существует в единственном

экземпляре) следует отнести также целостность данных - в том

смысле, что все подзадачи работают с одной и той же версией ин-

формационной части и изменения в данных, сделанные одной подзада-

чей немедленно становятся доступными для другой подзадачи.

Каждая подзадача работает со своим подмножеством как с ли-

нейным списком, используя для этого определенное поле связок.

Специфика мультисписка проявляется только в операции исключения

элемента из списка. Исключение элемента из какого-либо одного

списка еще не означает необходимости удаления элемента из памяти,

так как элемент может оставаться в составе других списков. Память

должна освобождаться только в том случае, когда элемент уже не

входит ни в один из частных списков мультисписка. Обычно задача

удаления упрощается тем, что один из частных списков является

главным - в него обязательно входят все имеющиеся элементы. Тогда

исключение элемента из любого неглавного списка состоит только в

переопределении указателей, но не в освобождении памяти. Исключе-

ние же из главного списка требует не только освобождения памяти,

но и переопределения указателей как в главном списке, так и во

всех неглавных списках, в которые удаляемый элемент входил.