В программных системах, обрабатывающих объекты сложной
структуры, могут решаться разные подзадачи, каждая из которых
требует, возможно, обработки не всего множества объектов, а лишь
какого-то его подмножества. Так, например, в автоматизированной
системе учета лиц, пострадавших вследствие аварии на ЧАЭС, каждая
запись об одном пострадавшем содержит более 50 полей в своей ин-
формационной части. Решаемые же автоматизированной системой зада-
чи могут потребовать выборки, например:
- участников ликвидации аварии;
- переселенцев из зараженной зоны;
- лиц, состоящих на квартирном учете;
- лиц с заболеваниями щитовидной железы;
- и т.д., и т.п.
дескриптор ┌───┬─>┬>┬────>┌──────┐ ┌>┌────────>┌──────┐
общего └───┘ │ │ │данные│ │ │ │данные│
списка │ │ ├──────┤ │ │ ├──────┤
│ │ │ ┼─┐ │ │ │ ┼─┐
│ │ ├──────┤ │ │ │ ├──────┤ │
│ │ ┌───┼ │ │ │ │ │ │ │
дескриптор ┌───┬──┘ │ │ ├──────┤ │ │ │ ├──────┤ │
списка └───┘ │ │ │ ┼─┼─┘ │ ┌─────┼ │ │
ликвидаторов │ │ └──────┘ │ │ │ └──────┘ │
│ │ ┌──────────┘ │ │ ┌──────────┘
│ │ │ │ │ │
│ │ └>┌──────┐ │ ┌─┼──>└>┌──────┐
дескриптор ┌───┬──┐ │ │ │данные│ │ │ │ │данные│
списка └───┘ │ │ │ ├──────┤ │ │ │ ├──────┤
кварт.учета │ │ │ │ ┼─┐ │ │ │ │ ┼─┐
│ │ │ ├──────┤ │ │ │ │ ├──────┤ │
│ │ │ │ │ │ │ │ │ ┌───┼ │ │
│ │ │ ├──────┤ │ │ │ │ │ ├──────┤ │
│ │ │ │ │ │ │ │ │ │ │ │ │
│ │ │ └──────┘ │ │ │ │ │ └──────┘ │
│ │ │ ┌──────────┘ │ │ │ │ ┌──────────┘
│ │ │ │ │ │ │ │ │
└─┼>└>└>┌──────┐ │ │ │ └>└>┌──────┐
│ │данные│ │ │ │ │данные│
│ ├──────┤ │ │ │ ├──────┤
│ │ ┼─────┘ │ │ │ ┼─┐
│ ├──────┤ │ │ ├──────┤ │
│ │ ┼───────┘ │ ┌─┼ │ │
│ ├──────┤ │ │ ├──────┤ │
└─────┼ │ │ │ │ │ │
└──────┘ | | └──────┘ |
Рис.5.11. Пример мультисписка
Для того, чтобы при выборке каждого подмножества не выпол-
нять полный просмотр с отсеиванием записей, к требуемому подмно-
жеству не относящихся, в каждую запись включаются дополнительные
поля ссылок, каждое из которых связывает в линейный список эле-
менты соответствующего подмножества. В результате получается мно-
госвязный список или мультисписок, каждый элемент которого может
входить одновременно в несколько односвязных списков. Пример та-
кого мультисписка для названной нами автоматизированной системы
показан на рис.5.11.
К достоинствам мультисписков помимо экономии памяти (при
множестве списков информационная часть существует в единственном
экземпляре) следует отнести также целостность данных - в том
смысле, что все подзадачи работают с одной и той же версией ин-
формационной части и изменения в данных, сделанные одной подзада-
чей немедленно становятся доступными для другой подзадачи.
Каждая подзадача работает со своим подмножеством как с ли-
нейным списком, используя для этого определенное поле связок.
Специфика мультисписка проявляется только в операции исключения
элемента из списка. Исключение элемента из какого-либо одного
списка еще не означает необходимости удаления элемента из памяти,
так как элемент может оставаться в составе других списков. Память
должна освобождаться только в том случае, когда элемент уже не
входит ни в один из частных списков мультисписка. Обычно задача
удаления упрощается тем, что один из частных списков является
главным - в него обязательно входят все имеющиеся элементы. Тогда
исключение элемента из любого неглавного списка состоит только в
переопределении указателей, но не в освобождении памяти. Исключе-
ние же из главного списка требует не только освобождения памяти,
но и переопределения указателей как в главном списке, так и во
всех неглавных списках, в которые удаляемый элемент входил.