Негативные последствия использования структур с последовательным хранением данных для представления списков, стеков, очередей сводятся к тому, что стеку или очереди отводится неизменяемый фиксированный объем памяти, даже если структура использует не весь этот объем, или в большинстве случаев не использует большей его части. Невозможность расширить ранее отведенный объем создает либо вероятность переполнения, либо требует избыточного резервирования памяти. В этом смысле более эффективным является связанное представление списков.
Если записи списка упорядочены так, что каждый элемент содержит внутри себя адрес следующего элемента, то такая структура хранения называется линейным связанным списком.
Каждая запись такого списка состоит из информационной части (info) и адресного поля: которое содержит указатель на следующий элемент списка. Доступ ко всему связанному списку осуществляется через внешний указатель (Pfirst), который указывает на первый элемент списка. Адресное поле последнего элемента списка содержит некоторый недопустимый (нулевой) указатель (NULL). Список, не содержащий элементов, называется пустым списком, значение внешнего указателя Pfirst для него – NULL.
Синтез использования последовательной структуры хранения для записей списка и реализации идеи связанного списка с заменой адресных указателей на индексы соответствующего массива приводит к понятию связанных списков на основе области свободных узлов. Такой подход сохраняет в случае работы с множеством списков с идентичной структурой хранения и динамично меняющимися размерами списков все свойства полезные при работе со связанными списками и обладает следующими достоинствами:
- не требуется использовать инструментарий операционной системы по работе с динамической памятью:
- записи множества списков естественным образом могут быть сохранены в виде последовательного файла, а затем достаточно просто восстановлены в оперативной памяти как система последовательных списков.
Записи массива, соответствующего области свободных узлов
В качестве аналога пула при работе с динамической памятью ЭВМ при создании области свободных узлов резервируется массив записей с индексами от 1 до n. Каждая запись содержит информационную часть и целочисленное поле nxt содержащее индекс записи следующей за данной в соответствующем списке. В общем случае в этом массиве одновременно располагается несколько списков с структурой соответствующей информационной части записей ОСУ и список свободных узлов. В начальный момент список свободных узлов совпадает с ОСУ, на последующих шагах из него извлекаются или в него возвращаются элементы содержательных списков. Очевидно в этом случае заголовки списков хранящихся в ОСУ содержат в качестве ссылок на начало списков не адреса а целочисленные индексы записей ОСУ. Использование ОСУ предполагает создание и использование процедур или функций по получению и возврату узлов ОСУ в список свободных узлов.
С точки зрения классификации с точки зрения связанных структур данных можно выделить:
- односвязные и двусвязные списки,
- циклическиесписки,
- списки с заголовками.
Связанное представление не позволяет достаточно прямолинейно реализовать многие методы выполнения операций поиска и сортировки, которые используются для последовательных структур, например, метод бинарного поиска, метод Шелла и так далее.
Описание структуры списка дает возможность быстрого доступа к записи по поисковому признаку, соответствующему ключу списка. Однако для многих практических задач необходимо иметь доступ к записям по другим поисковым признакам
Рис.7.1
В примере, представленном на рис.7.1 естественно для ускорения доступа к данным по специальностям иметь дополнительный список, структура которого представлена на рис.7.2. В этом случае говорят о создании инвертированного списка или индексного файла. Инвертированным списком называется упорядоченный набор значений неключевого поля записей списка, обеспечивающий быстрый поиск записей по соответствующему поисковому признаку. Так как для связанных структур данных создание такого рода файлов повышаетскорость доступа к данным и позволяет использовать идею массива локатора для поддержки упорядоченного списка без фактического упорядочения записей, то эта идея распространяется и на поиск по ключу списка и тогда о соответствующем инвертированном списке говорят как о первичном индексе.
Иногда бывает желательно держать один и тот же элемент в нескольких списках, не повторяя его при этом в нескольких ячейках памяти. Ярким и достаточно простым примером такой структуры является разреженные матрицы, часто используемые при реализации математических моделей численными методами.
Рисунок 7.2
В примере на рис.7.2 в матрице из 1000 строк и 1000 столбцов отличны от нуля только 3000 элементов. В то же время при использовании соответствующего двумерного массива для представления матрицы требуется резервировать в 330 раз больше элементов. Естественным решением для рационального представления такой разреженной матрицы является использование связанного списка со структурой записи, представленной на рис.7.3.
Рисунок 7.3
Естественно, этот список можно упорядочить по строкам, а внутри строк по столбцам. Однако операция умножения матриц требует от второго операнда другого упорядочения: по столбцам, а внутри по строкам. В этом случае можно использовать два указателя, поддерживая тем самым в одном списке одновременно два связанных сортированных по соответствующим полям списка.
Мультисписок (multilist) – способ организации списковых структур, основанный на объединении упорядоченного по ключу связанного списка и инвертированных списков.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.