3.26 Для данных указателей х и t узлов циклического списка написать фрагмент кода, который перемещает узел, следующий после t, в позицию списка, которая следует после узла х.

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

3.28 Определить время выполнения программы 3.9 как функцию от Л/и N.

3.29 Использовать программу 3.9 с целью определения значения функции Иосифа для Л/= 2, 3, 5, 10 и Л= 10, 10, 10 и 10

3.30 Использовать программу 3.9 с целью построения графика зависимости функции Иосифа от 7V для М = 10 и 7V от 2 до 1000.

о 3.31 Воспроизвести таблицу на рис. 3,6, когда элемент i занимает в массиве исходную позицию N-i.

3.32 Разработать версию программы 3.9, в которой для реализации связного списка используется массив индексов (см. рис. 3.6).

3.4 Обработка простых списков

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

При использовании массивов возможны ошибки программы, связанные с попыткой доступа к данным вне допустимого диапазона. Для связных списков наиболее часто встречается подобная ошибка - ссылка на неопределенный указатель. Другая распространенная ошибка - использование указателя, который изменен неизвестным образом. Одна из причин возникновения упомянутой проблемы состоит в возможном присутствии нескольких указателей на один и тот же узел, что программист может не осознавать. В программе 3.9 несколько подобных проблем устраняется за счет использования циклического списка, который никогда не бывает пустым. При этом каждая ссылка всегда указывает на однозначно определенный узел. Кроме того, каждая ссылка может интерпретироваться как ссылка на список.

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

Как указывалось в разделе 3.3, для первого и последнего указателей списка применяется ряд различных соглашений. Некоторые из них рассматриваются в этом разделе, хотя мы взяли за правило резервировать термин связные списки для описания простейших ситуаций.

Определение 3.3 Связный список содержит либо null-ссылки, либо ссылки на узлы, которые содержат элемент и ссылку на связный список.

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

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

for (link t = х; t = 0; t = t->next) visit(t->item) ;

Этот цикл (либо его эквивалентная форма while) является универсальным для профамм обработки списков, подобно циклу for (int i = 0; i < N; i++) для программ обработки массивов.

Профамма 3.10 служит реализацией простой задачи обработки списка, состоящей в изменении на обратный порядка следования узлов. Она принимает связный список в качестве аргумента и возвращает связный список, состоящий из тех же узлов, но расположенных в обратном порядке. На рис. 3.7 показано изменение, выполняемое функцией в своем главном цикле для каждого узла. Эта диаграмма упрощает проверку каждого оператора программы на правильность изменения ссылок. Программисты обычно используют подобные диаграммы для осмысления операций обработки списков.

Программа 3.10 Обращение порядка следования элементов списка

Эта функция обращает порядок следования ссылок в списке, возвращая указатель последнего узла, который затем указывает на предпоследний узел и т.д. При этом для ссылки в первом узле исходного списка устанавливается значение О (null-указатель). Для выполнения этой задачи необходимо сохранять ссылки на три последовательных узла списка.

link reverse(link х) { link t, у = X, г = 0; while (у != 0) { t = y->next; y->next = r; r = y; У = t; } return r;

РИСУНОК 3.7 ОБРАЩЕНИЕ СПИСКА

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

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

Списки в программе 3.11 иллюстрируют еще одно часто используемое соглашение: в начале каждого списка содержится фиктивный узел, называемый ведущим (head node). Поле элемента ведущего узла игнорируется, но ссылка узла сохраняется в качестве указателя узла, содержащего первый элемент списка. В программе используется два списка: один для сбора вводимых случайных чисел в первом цикле, а другой для сбора сортированного вывода во втором цикле. На рис. 3.8 показаны изменения, вносимые программой 3.11 в течение одной итерации главного цикла. Из списка ввода извлекается следующий узел, вычисляется его позиция в списке вывода, и реализуется ссылка на эту позицию.

РИСУНОК 3.8 СОРТИРОВКА СВЯЗНОГО

СПИСКА. Г1Е-j==Ft-i

Приведенная диаграмма отражает один / s-JTseUI

шаг преобразования неупорядоченного ,-1-. -ЧшЩ

связного списка (заданного указателем а) в / -Hioil упорядоченный связный список (заданный езб

указателем Ь) с использованием сортировки

вставками. Сначала берется первый узел i-j-i

неупорядоченного списка и указатель на / -Нвз!

него сохраняется в t (верхняя диаграмма). * *lltJ

Затем выполняется поиск в Ъ для нахождения первого узла х, для которого справедливо условие х- >next- >item > 1->item (или х- >next = NULL) и t вставляется в список после х (средняя диаграмма). Эти операции уменьшают на один узел размеры списка а и увеличивают г--r-i

на один узел размеры списка Ь, сохраняя -W ioi

список b упорядоченным (нижняя ь V-вПЕЙ-р-,

диаграмма). По прошествии цикла список а --НШЕЙ

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

1838