Программа 3.11 Сортировка методом вставки в список

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

node heada(0, 0); link а = &heada, t = а; for (int i = 0; i < N; i++)

t = (t->next = new node (rand () % 1000, 0) ) ; node headb(0, 0); link u, x, b = fiheadb; for (t = a->next; t ?= 0; t = u)

u - t->next;

for (x = b; x->next != 0; x = x->next)

if (x->next->item > t->item) break; t->next = x->next; x->next = t;

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

Дублировать цикл for, который обнаруживает наименьший элемент и создает список из одного узла таким же образом, как в программе 3.9.

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

Использовать фиктивный ведущий узел, ссылка которого указывает на первый узел списка, как в данном примере.

Первому варианту не хватает изящества. Он требует дополнительного кода. То же относится и ко второму варианту.

Использование ведущего узла влечет дополнительные затраты памяти (на дополнительный узел). Во множестве типовых приложений без него можно обойтись. Например, в программе 3.10 присутствуют список ввода (исходный) и список вывода (зарезервированный), но нет необходимости использовать ведущий узел, поскольку все вставки выполняются в начало списка вывода. Будут примеры и других приложений, в которых использование фиктивного узла упрощает код эффективнее, нежели применение null-ссылки в хвосте списка. Не существует жестких правил принятия решения об использовании фиктивных узлов - выбор зависит от стиля в комбинации с соображениями быстродействия. Хорошие программисты выбирают соглашение, которое более всего упрощает задачу. На протяжении книги встречается несколько подобных компромиссов.

Ряд вариантов соглашений о связных списках приводится в табл. 3.1 для справочных целей. Остальные рассматриваются в упражнениях. Во всех вариантах табл. 3.1 для ссылки на список используется указатель head и сохраняется положение, при ко-

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

Таблица 3.1 Соглашения о ведущем и завершающем узлах в связных списках

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

Список циклический, никогда не бывает пустым

первая вставка: head->next = head;

вставка t после X. t->next = x->next; x->next = t; удаление после x: x->next = x->next->next; цикл обхода: t = head;

do { ... t = t->next; } while (t != head) ; проверка на наличие лишь одного элемента: if (head->next = head)

Ведущий указатель, null-указатель завершающего узла

инициализация: head = 0;

вставка t после х: if (х == О) {head = t; head->next = 0; }

else { t->next = x->next; x->next = t; } удаление после x: t = x->next; x->next = t->next;

цикл обхода: for (t = head; t != 0; t = t->next)

проверка на пустоту: if (head = 0)

Фиктивный ведущий узел, nuli-указатель завершающего узла

инициализация: head = new node;

head->next = 0; вставка t после x: t->next = x->next; x->next = t; удаление после x: t = x->next; x->next = t->next;

цикл обхода: for (t = head->next; t != 0; t = t->next)

проверка на пустоту: if (head->next = 0)

Фиктивные ведущий и завершающий узлы

инициализация: head = new node;

z - new node;

head->next = z; z->next = z; вставка t после x: t->next = x->next; x->next = t; удаление после x: x->next = x->next->next;

цикл обхода: for (t = head->next; t = z; t = t->next)

проверка на пустоту: if (head->next == z)

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

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

Программа 3.12 Интерфейс обработки списков

в этом коде, который можно сохранить в файле интерфейса llst.h, описаны типы узлов и ссылок, включая операции, выполняемые над ними. Для распределения памяти под узлы списка и ее освобождения объявляются собственные функции. Функция construct применена для удобства реализации. Эти описания позволяют клиентам использовать узлы и связанные с ними операции без зависимости от подробностей реализации. Как будет показано в главе 4, несколько отличный интерфейс, основанный на классах С++, может обеспечить независимость клиентной программы от подробностей реализации.

typedef int I tern;

struct node { Item item; node *next; }; typedef node *link; typedef link Node;

void construct(int) ; Node newNode(int); void deleteNode(Node) ; void insert(Node, Node); Node remove(Node); Node next(Node); Item item(Node);

Программа 3.12 объявляет набор функций черного ящика , которые реализуют базовый список операций. Это позволяет избегать повторения кода и зависимости от деталей реализации. Программа 3.13 реализует выбор Иосифа (см. программу 3.9), преобразованный в клиентскую программу, которая использует этот интерфейс. Идентификация важных операций, используемых в вычислениях, и описание их в интерфейсе обеспечивают гибкость, которая позволяет рассматривать различные конкретные реализации важных операций и проверять их эффективность. В разделе 3.5 рассматривается реализация операций программы 3.12 (см. программу 3.14), но возможны альтернативные решения, не требующие никаких изменений программы 3.13 (см. упражнение 3.51). Эта тема еще будет неоднократно затрагивать в данной книге. Язык С++ включает несколько механизмов, специально предназначенных для упрощения разработки инкапсулированных реализаций; речь об этом пойдет в главе 4.

Программа 3.13 Организация списка для задачи Иосифа

Эта программа решения задачи Иосифа служит примером клиентской программы, использующей примитивы обработки списков, которые объявлены в программе 3.12 и реализованы в программе 3.14.