node(Item х) { item = х; next =0; }

typedef node *link; link randlist(int); link scanlist(intS); void showlist(link) ; link sortlist(link);

Программа 6.15 задает интерфейс типа данных linked-list (связный список), подобный используемому в программе 6.7. В условиях программы 6.15 драйвер, соответствующий профамме 6.6, умещается в одной строке:

main(int argc, char *argv[])

{showlist(sortlist(scanlist(atoi(argv[l])))); }

Большая часть работы (включая и распределение памяти) ложится на реализации связного списка и функции sort. Так же как и в случае драйвера для массива, этот список должен инициализироваться (из стандартного ввода либо случайными значениями), необходимо уметь отобразить его содержимое и, разумеется, отсортировать его. Как обычно, в качестве типа данных сортируемых элементов используется Item, что предпринималось в разделе 6.7. Программный код, реализующий интерфейс подобного рода, является стандартным для связных списков и аналогичен коду, который подробно исследовался в главе 3; ниже приводится соответствующее упражнение.

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

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

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

Не особенно сложно приспособить сортировку вставками, выбором и пузырьковую сортировку для работы со связными списками, но в каждом конкретном случае возникают занятные проблемы. Сортировка выбором достаточно проста: имеется входной список (в котором в исходном положении хранятся данные) и выходной список (в котором фиксируются результаты сортировки); входной список просматривается с целью обнаружения максимального элемента, который затем удаляется из списка и помещается в начало выходного списка (см. рис. 6.16). Реализация этой операции представляет собой одну из простейших манипуляций над связными списками и является полезным методом сортировки коротких списков. Реализация показана в программе 6.16. Другие методы сортировки оставляются в качестве упражнений для самостоятельной проработки.

Программа 6.16. Сортировка выбором связного списка

max /г У ll !

н(Г27

7 5?

РИСУНОК 6.16. СОРТИРОВКА ВЫБОРОМ СВЯЗНОГО СПИСКА

На этой диаграмме показан один шаг сортировки выбором связного списка. Мы поддерживаем входной список с указателем h- >next и выходной список с указателем out (вверху). Входной список просматриёается с таким расчетом, чтобы max показывал на узел, предшествующий (а tуказывал на) узлу, содержащему максимальный элемент. Таковыми являются указатели, которые необходимы для того, чтобы исключить t из входного списка (уменьшив его длину на 1) и поместить его в начало выходного списка (увеличивая его длину на 1), сохраняя в выходном списке заданный порядок (внизу). С течением процесса, в конечном итоге, исчерпывается весь входной список, а в выходном списке элементы размещаются в заданном порядке.

Сортировка выбором связного списка достаточно проста, но несколько отличается от сортировки массива тем же методом, поскольку размещение элемента в начале списка - более простая операция. Поддерживаются входной список (указатель h->next) и выходной список (указатель out). Когда входной список не пуст, он просматривается с целью нахождения максимального элемента, который затем удаляется из входного и помещается в начало выходного списка. Реализация использует вспомогательную программу findmax, которая возвращает связь узла, связь которого указывает на максимальный элемент в списке (см. упражнение 3.34).

link listselection(link h) { node diimmy (0) ; link head = &d\iinmy, out = 0; head->next = h; while (head->next != 0)

{ link max = findmax (head) , t = max->next; max->next = t->next; t->next = out; out = t;

return out;

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

Упражнения

> 6.64. Показать содержимое входного и выходного списков при условии, что сортировка ключей ASORTINGEXAMPLE выполняется с использованием программы 6.15.

6.65. Разработать реализацию интерфейса связного списка, заданного в программе 6.15.

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

6.67. Разработать ATD первого класса для связных списков (см. раздел 4.8), который включает конструктор для инициализации случайными значениями, конструктор для инициализации через перегруженную операцию operator , вывод данных через перегруженную операцию operator>>, деструктор, конструктор копий и функцию-член sort. Воспользоваться сортировкой выбором для реализации функции sort, при этом findmax рассматривается как приватная функция-член.

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

> 6.69. Включить в программу 3.11 модуль сортировки вставками таким образом, чтобы он обладал такими же функциональными возможностями, что и программа 6.16.

6.70. Вариант сортировки вставками, использованный в программе 3.11, выполняет сортировку связных списков значительно медленнее, чем сортировку массивов на некоторых входных файлах. Дайте описание одного из таких файлов и объясните, в чем заключается проблема.

6.71. Построить программную реализацию варианта сортировки методом Шелла, ориентированного на связные списки, который не требует существенно большего объема памяти и времени для сортировки случайно упорядоченного файла, нежели вариант, предназначенный для сортировки массивов. Совет: воспользоваться пузырьковой сортировкой.

6.72. Реализовать ATD для последовательностей, которые позволили бы использовать одну и ту же клиентскую программу для отладки программных реализаций сортировки как связных списков, так и массивов. Иначе говоря, клиентские про-