Иллюстрированный самоучитель по Perl



         

Ассоциативные массивы - часть 5


Это только простейший пример, который может навести читателя на более плодотворные идеи применения хеш-массивов, одну из которых нам хотелось бы сейчас наметить: создание связанного списка.

Связанный список —

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

Рис 3.1. Графическое представление связанного списка

С помощью хеш-массивов связанный список реализуется просто. Для этого следует значение элемента задать в качестве ключа для следующего за ним элемента списка, определив таким образом указатель на следующий элемент. Значением последнего элемента в хеш-массиве (с ключом, равным значению последнего элемента связанного списка) будет пустая строка "". Переменная-заголовок должна иметь значение, равное ключу первого элемента списка. В примере 3.8 показана реализация связанного списка, а также добавление нового элемента.

%linked_list = ( "начало" => "первый", "первый" => "третий",

"третий" => ""

);

$header = "начало";

# Добавление элемента со значением "второй"

# после элемента со значением "первый".

$temp = $linked_lis.t{ "первый"};

# Запомнили старый, указатель ., $linked_list{"второй"} = $temp;

# Добавили новый элемент. $linked_list{"первый"} = "второй";




Содержание  Назад  Вперед