|
Ортогональный список (или мультисписок) – это структура, каждый элемент которой входит более чем в один список одновременно и имеет соответствующее числу списков количество полей связи. Реализация каждого из списков может быть выполнена как одно- или двусвязного нециклического или циклического. Технология обработки мультисписков ничем не отличается от обработки обычных списков, но так как мультисписок одновременно содержит несколько списков, каждую операцию следует выполнить отдельно для каждого списка.
Ортогональный список позволяет на множестве одних и тех же атрибутов, содержащих информацию, организовать различные списки, упорядоченные по различным признакам. Рассмотрим список студентов, каждый узел которого содержит следующие информационные поля: фамилия_ имя_отчество, средний балл, дата рождения, адрес, номер зачетки и т.п. Пусть необходимо упорядочить список студентов по двум признакам: в алфавитном порядке по фамилии и в соответствии со средним баллом. Этого можно достичь, если построить два отдельных списка, но элементы хранения информационных полей в этом случае продублируются, что приведет к неэффективному использованию оперативной памяти, особенно, если количество информационных полей велико. Более рациональным решением является использование мультисписка, содержащего два списка, каждый из которых организован, например, в виде двусвязного циклического списка: по алфавиту элементы списка упорядочены с помощью атрибутов связи fnext и fprev, а по среднему баллу те же самые элементы упорядочены с помощью атрибутов связи bnext и bprev. Для удобства обработки мультисписок содержит головной элемент, на который установлен указатель.
|
