2. Списки с двумя связями: их функциональная спецификация, логическое описание и физическое представление. Добавление и удаление элементов

 

Список с двумя связями

 

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

            Каждый элемент списка помимо некоторой содержательной информации должен включать также две ссылки: как на предыдущий элемент, так и на последующий элемент этого списка (рис. 1.5).

            Рис. 1.5.         Цепное представление списка с двумя связями.

            В виде списка с двумя связями могут быть организованы, например, упорядоченный в некотором смысле (скажем, по фамилиям авторов) список книг в библиотеке, список студентов группы. В первом случае содержательная информация может состоять из ФИО автора, названия книги, год издания и т.п., во втором случае – ФИО студента, год рождения, номер группы, оценки и т.п.

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

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

Функциональная спецификация

            Функциональная спецификация списка с двумя связями, содержащего  объекты типа Т, или СДСТ, включает операции:

создание:       создание_СДС – операция создает пустой список;

доступ:           следующий – на входе объект t, СДС;  на выходе: объект, следующий за t  в СДС;

            первый – возвращает первый элемент, если он существует;

модификация:

            вставка – на входе: объекты t и t', СДС; на выходе: новый СДС, в котором объект t вставлен после объекта t' или после всех элементов, если t' не содержится в СДС;

            исключение – на входе: объекты t и t', СДС; на выходе: новый СДС, в котором объект t, следовавший после t', удален из списка.

Логическое описание

            Логическое описание списка с двумя связями включает два объявления вида:

тип СДСт = (ПУСТО или НЕ_ПУСТОЙ_СДСт);

тип НЕ_ПУСТОЙ_СДСт = (начало: Т; продолжение: СДСт).

 

Физическое представление

            Здесь возможность сплошного представления особенно неэффективна, так как при сплошном представлении никаким способом не удается избежать физического перемещения некоторых элементов в реализации вставки. Действительно, чтобы перейти от  списка “A B D E F” к списку “A B C D E F” путем включения нового элемента “C”, следует изменить места, как минимум трех элементов – D, E, F. Аналогично, удаление требует уплотнить список, чтобы “поглотить дыру”, оставленную удаляемым элементом. В силу этих причин при физической реализации таких списков используется только цепное представление данных.

            При формировании списка необходимо учесть, что каждый его элемент должен иметь, как минимум, три поля: одно для данных, и два – для указателей (на соседа слева и на соседа справа).   Пример. На рис. 1.6 представлена процедура удаления элемента из этого списка.

 

 

            {...}
type ptr=^node;  node=record d:char; lp,rp:ptr end;
var  ch:char; left,right,k,q:ptr;
 
{...}
procedure DelDblList(var q,left,right:ptr);
begin
         k:=q;
         if k=left then begin left:=k^.rp; left^.lp:=nil end
         else
          if k=right then begin right:=k^.lp; right^.rp:=nil end
          else
           begin k:=q; q^.lp^.rp:=q^.rp; q^.rp^.lp:=q^.lp end;
           dispose(k)
 end;    {* DelDblList*}

           

Рис. 1.6.