Списки и их разновидности

Связные списки и алгоритмы их обработки

В повседневной жизни под термином «список» (list) подразумевают некий перечень объектов реального мира, например, «список студентов группы» или «список комплектующих деталей на сладе». При этом указанный перечень мо­жет содержать не только наименование объектов, но и их дополнительные атрибуты. В нашем примере к таким атри­бутам можно отнести пол студента, размер сти­пендии и т. д.

С точки зрения организации данных подсписком пони­мают структуруданных, представляющую собой логически связанную последовательность элементов. Элементом спи­ска обычно является запись. Список называется линейным (linear list), если входящие в него элементы e₁ , e₂ ,…,e_n - линейно упорядочены. Упорядоченность элементов линей­ного списка может задаваться неявно путем последова­тельного расположения его элементов как в логической структуре, так и в памятиЭВМ. Такой список называют последовательным (sequential list).Примером последовательного списка является вектор, в котором элементы используются для хранения информации списка. С другой стороны, упорядоченность может задаваться с помощью специаль­ных указателей (ссылок), располагаемых в элементах и дающих возможность для каждого элемента определить его непо­средственных предшественника и последователя. Такой список называется связным (linked) или цепным (chained) списком.

Связные списки относятся к классу динамических структур. Количество элементов в них заранее не фиксируется, оно зависит от потребностей решаемой в текущий момент задачи. Поскольку элемент связного списка может быть создан и уничтожен в любой момент времени, существование связного списка реализуется в куче.

Элемент связного списка называется обычно узлом (node) Каждый узел связного списка состоит из двух различных по назначению видов полей: содержательные (информационные) поля и поля структурных (или логических) указателей. В содержательных полях хранятся данные, ради которых и создавался список. Некоторые содержательные поля могут хранить указатели на данные, по каким либо причинам не вместившиеся в содержательные поля; такие указатели называются дополнительными или вторичными (secondary pointer). Поля логических или структурных указателей (logical pointer) хранят адреса других элементов списка. Пользуясь логическим указателем (адресом), можно получить доступ от элемента, содержащего этот указатель, к тому элементу списка, на который этот указатель направлен.

Определение связного списка отличается от определения массива, в котором следующий элемент находится в памяти рядом с предыдущим. В связном списке элементы могут быть разбросаны по разным местам памяти, а их порядок определяется ссылками.

В связном списке каждый узел является отдельным элементом. И, как правило, распределение памяти под каждый узел выполняется отдельно. При необходимости добавления в список нового элемента под него распределяется слот памяти, а затем на этот слот устанавливается структурная ссылка от элемента списка. При удалении узла нужно всего лишь удалить ссылки, направленные на него от других элементов и освободить память, занимаемую его слотом.

Дата добавления: 2014-01-07