Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow Алгоритмы и структуры данных. Новая версия для Оберона

4.3. Линейные списки

4.3.1. Основные операции

Простейший способ связать набор элементов - выстроить их в простой список (list) или очередь. Ибо в этом случае каждому элементу нужен единственный указатель на элемент, следующий за ним.

Пусть типы Node (узел) и NodeDesc (dese от descriptor) определены, как показано ниже. Каждая переменная типа NodeDesc содержит три компоненты, а именно идентифицирующий ключ key, указатель на следующий элемент next и, возможно, другую информацию. Для дальнейшего нам понадобятся только key и next:

TYPE Node = POINTER ТО NodeDesc;

TYPE NodeDesc = RECORD key: INTEGER; next: Node; data: ... END;

VAR p, q: Node (‘указательные переменные*)

На рис. 4.6 показан список узлов, причем указатель на его первый элемент хранится в переменной р. Вероятно, простейшая операция со списком, показанным на рис. 4.6, - это вставка элемента в голову списка. Сначала размещается элемент типа NodeDesc, при этом ссылка (указатель) на него записывается во вспомогательную переменную, скажем q. Затем простые присваивания указателей завершают операцию. Отметим, что порядок этих трех операторов менять нельзя.

NEW(q); q.next := р; р := q

Пример связного списка

Рис. 4.6. Пример связного списка

Операция вставки элемента в голову списка сразу подсказывает, как такой список можно создать: начиная с пустого списка, нужно повторно добавлять в голову новые элементы. Процесс создания списка показан в следующем программном фрагменте; здесь п - число элементов, которые нужно связать в список:

р := NIL; (‘начинаем с пустого списка*)

WHILE п > О DO

NEW(q); q.next := р; р := q; q.key := n; DEC(n)

END

Это простейший способ создания списка. Однако здесь получается, что элементы стоят в обратном порядке по сравнению с порядком их добавления в список. В некоторых задачах это нежелательлно, и поэтому новые элементы должны присоединяться в конце, а не в начале списка. Хотя конец списка легко найти простым просмотром, такой наивный подход приводит к вычислительным затратам, которых можно избежать, используя второй указатель, скажем q, который всегда указывает на последний элемент. Этот метод применяется, например, в программе CrossRef (раздел 4.4.3), где создаются перекрестные ссылки для некоторого текста. Его недостаток - в том, что первый элемент должен вставляться по-другому, чем все остальные.

Явное наличие указателей сильно упрощает некоторые операции, которые в п- ротивном случае оказываются громоздкими. Среди элементарных операций со списками - вставка и удаление элементов (частичное изменение списка), а также, разумеется, проход по списку. Мы сначала рассмотрим вставку (insertion) в список.

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

q.next := p.next; p.next := q

Вставка после р

Рис. 4.7. Вставка после рЛ

Если нужна вставка перед указанным элементом рЛ, а не после него, то, казалось бы, возникает затруднение, так как в однонаправленной цепочке ссылок нет никакого пути от элемента к его предшественникам. Однако здесь может выручить простой прием. Он проиллюстрирован на рис. 4.8. Предполагается, что ключ нового элемента равен 8.

NEW(q); q^ := рл; p.key := k; p.next := q

Вставка перед р

Рис. 4.8. Вставка перед рл

Очевидно, трюк состоит в том, чтобы вставить новую компоненту после рЛ, а потом произвести обмен значениями между новым элементом и рЛ.

Теперь рассмотрим удаление из списка (list deletion). Нетрудно удалить элемент, стоящий сразу за рЛ. Эта операция показана здесь вместе с повторной вставкой удаленного элемента в начало другого списка (обозначенного переменной q). Ситуация показана на рис. 4.9, из которого видно, что имеет место циклический обмен значений трех указателей.

г := p.next; p.next := r.next; г.next := q; q := r

Удаление и повторная вставка

Рис. 4.9. Удаление и повторная вставка

Удаление самого элемента, на который указывает ссылка (а не следующего), труднее, так как здесь возникает та же проблема, что и со вставкой: невозможно просто так перейти назад от элемента к предшествующему. Но удаление следующего элемента после копирования его значения вперед - довольно очевидное и простое решение. Его можно применить, когда за рЛ стоит некоторый элемент, то есть рЛ не является последним элементом в списке. Однако необходимо гарантировать, что нет других переменных, ссылающихся на удаляемый элемент.

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

WHILE список, на который ссылается р, не пуст DO выполнить операцию Р; перейти к следующему элементу

END

Детали этой операции выглядят следующим образом:

WHILE р # NIL DO Р(р); Р := p.next

END

Из определения оператора while и структуры связей следует, что Р применяется ко всем элементам списка и ни к каким другим.

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

WHILE (р # NIL) & (р.key # х) DO р := p.next END

Равенство р = NIL означает, что записи рл не существует, так что выражение р.кеу # х не определено. Поэтому порядок двух термов важен.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >
 

Популярные страницы