Реализация упорядоченного списка¶
Перед тем, как начать реализовывать упорядоченный список, мы должны вспомнить, что положение элементов относительно друг друга основываются на некой базовой характеристике. Упорядоченный список целых чисел, представленный выше (17, 26, 31, 77 и 93), может быть выражен связанной структурой, показанной на Рисунке 15. Опять же, узел и ссылка идеально подходят для представления взаимного расположения элементов.
Рисунок 15: Упорядоченный связанный список
Для реализации класса OrderedList мы будем использовать ту же технику, что и для неупорядоченного списка. Пустой список вновь будет обозначаться ссылкой head на None (см. Листинг 8).
Листинг 8
Рассматривая операции для упорядоченного списка, стоит отметить, что методы isEmpty и size могут быть реализованы аналогично неупорядоченному списку, поскольку имеют дело только с количеством узлов безотносительно их содержимого. Также хорошо будет работать метод remove , потому что нам по-прежнему надо искать элемент, а затем окружающие узел ссылки, чтобы удалить его. Два оставшихся метода — search и add — потребуют некоторой модификации.
Поиск в неупорядоченном списке требует, чтобы мы обходили узлы по одному за раз, пока не найдём искомый элемент или не выйдем за пределы списка ( None ). Такой подход будет работать и для упорядоченного списка. В том случае, когда элемент найдётся, — он будет тем, что нам нужен. Однако, в случае, когда элемент не содержится в списке, мы можем воспользоваться преимуществом упорядочения, чтобы остановить поиск как можно раньше.
Например, Рисунок 16 показывает упорядоченный связанный список, в котором ищется значение 45. В процессе обхода мы начинаем с головы списка и сначала проверяем на соответствие 17. Поскольку 17 — не то, что мы ищем, то смещаемся к следующему узлу — 26. Это снова не то, и мы перемещаемся к 31, а затем к 54. В этот момент кое-что изменилось. Поскольку 54 не тот элемент, что мы ищем, наша предыдущая стратегия должна заключаться в продвижении вперёд. Однако, с учётом того факта, что список упорядочен, в этом больше нет необходимости. Раз значение в узле больше, чем искомое, значит поиск можно останавливать и возвращать False . Не существует способа значению оказаться среди остатка упорядоченного списка.
Рисунок 16: Поиск в упорядоченном списке
Листинг 9 показывает законченный метод search . Новое условие, обсуждаемое выше, можно вставить очень легко: добавить ещё одну булеву переменную — stop — и инициализировать её False (строка 4). Пока stop равно `False` мы можем продолжать поиск в списке (строка 5). Если в любом из узлов обнаружится значение больше искомого, то мы установим stop в True (строки 9-10). Оставшиеся строки идентичны поиску в неупорядоченном списке.
Листинг 9
Наиболее значительная модификация затронет метод add . Напомним, что в неупорядоченных списках он просто помещал новый элемент в голову списка — самую доступную точку. К сожалению, с упорядоченным списком это больше не сработает. Теперь нам надо искать специальное место, где будет размещаться новый элемент среди уже существующих в упорядоченном списке.
Предположим, что у нас есть упорядоченный список из 17, 26, 54, 77 и 93, и мы хотим добавить в него значение 31. Метод add должен решить, что новый элемент следует расположить между 26 и 54. Рисунок 17 показывает необходимую вставку. Как мы объясняли ранее, нам нужно обойти связанный список в поисках места, куда будет вставлен новый элемент. Мы знаем, что место найдено, если мы или вышли за пределы списка ( current равно None ), или значение текущего узла стало больше, чем добавляемый элемент. В нашем примере нас вынудит остановится появление значения 54.
Рисунок 17: Добавление элемента в упорядоченный связанный список
Как мы уже видели для неупорядоченных списков, здесь понадобится дополнительная ссылка ( previous ), поскольку current не сможет предоставить доступ к узлу, который нужно будет изменить. Листинг 10 показывает законченный метод add . Строки 2-3 устанавливают две внешние ссылки, а строки 9-10 вновь позволяют previous следовать на один узел после current во время каждой итерации. Условие в строке 5 разрешает итерациям продолжаться до тех пор, пока остаются непросмотренные узлы и значение текущего не превышает искомое. Противный случай — когда итерация терпит неудачу — означает, что мы нашли место для нового узла.
Остаток метода завершает двухшаговый процесс, показанный на Рисунке 17. Поскольку для элемента был создан новый узел, то остаётся единственный вопрос: куда он будет добавлен — в начало или в середину связанного списка? Для ответа на него вновь используется previous == None .
Листинг 10
Класс `OrderedList` с реализованными на данный момент методами можно найти в ActiveCode 4.
Оставшиеся операции мы оставляем в качестве упражнения. Вам следует внимательно рассмотреть, когда неупорядоченная реализация будет работать как следует с учётом того, что теперь список упорядочен.
Упорядоченные и неупорядоченные списки
Существует три типа списков: упорядоченные, неупорядоченные и списки определений. Здесь мы рассмотрим первые два вида списков, а о списках определений вы узнаете позже.
Упорядоченные и неупорядоченные списки работают одинаково, за исключением того, что последние используются для представления непоследовательных списков, элементы которых обычно маркируются крупной черной точкой (буллитом), а первые используются для представления последовательных списков, которые обычно имеют вид элементов пронумерованных в возрастающем порядке.
Для определения неупорядоченных списков используется тег <ul>, а для определения упорядоченных списков – тег <ol>. Внутри списков для определения каждого отдельного элемента списка используется тег <li>.
Измените свою веб-страницу следующим образом:
Если посмотреть эту веб-страницу в браузере, то увидите список, маркированный буллитами. Замените тег <ul> на тег <ol>, и вы увидите, что список стал нумерованным.
Кроме всего прочего можно включать одни списки в другие, формируя тем самым структурированную иерархию элементов.
Замените код списка из предыдущего примера следующим:
И вот у нас список внутри списка. А ведь можно поместить еще один список внутри этого вложенного списка. И еще один. И так далее до бесконечности.
Сортировка И Слияние Списков
При работе со списками очень часто возникает необходимость перестановки элементов списка в определенном порядке. Такая задача называется сортировкой списка и для ее решения существуют различные методы. Рассмотрим некоторые из них.
2.2.1. Пузырьковая сортировка
Задача сортировки заключается в следующем: задан список целых чисел (простейший случай) В=. Требуется переставить элементы списка В так, чтобы получить упорядоченный список B’=, в котором для любого 1При обменной сортировке упорядоченный список В’ получается из В систематическим обменом пары рядом стоящих элементов, не отвечающих требуемому порядку, пока такие пары существуют.
Наиболее простой метод систематического обмена соседних элементов с неправильным порядком при просмотре всего списка слева на право определяет пузырьковую сортировку: максимальные элементы как бы всплывают в конце списка.
В последующих примерах будем считать, что сортируется одномерный массив (либо его часть от индекса n до индекса m) в порядке возрастания элементов.
Нижеприведенная функция bubble сортирует входной массив методом пузырьковой сортировки.
Функция insert реализует сортировку вставкой.
Здесь оба списка В и В’ размещаются в массиве s, причем список В занимает часть s c индексами от i до n, а B’ — часть s c индексами от m до i-1 (см. рис.26).
При сортировке вставкой требуется Q=(n-m)*(n-m) сравнений и не требуется дополнительной памяти.
Рис.26. Схема движения индексов при сортировке вставкой.
2.2.3. Сортировка посредством выбора
Упорядоченный список В’ получается из В многократным применением выборки из В минимального элемента, удалением этого элемента из В и добавлением его в конец списка В’, который первоначально должен быть пустым.
Функция select упорядочивает массив s сортировкой посредством выбора.
Здесь, как и в предыдущем примере оба списка В и В’ размещаются в разных частях массива s (см. рис.27). При сортировке посредством выбора требуется Q=(n-m)*(n-m) действий и не требуется дополнительной памяти.
Рис.27. Схема движения индексов при сортировке выбором.
Сортировка квадратичной выборкой. Исходный список В из N элементов делится на М подсписков В1,В2. Вm, где М равно квадратному корню из N, и в каждом В1 находится минимальный элемент G1. Наименьший элемент всего списка В определяется как минимальный элемент Gj в списке , и выбранный элемент Gj заменяется новым наименьшим из списка Bj. Количество действий, требуемое для сортировки квадратичной выборкой, несколько меньше, чем в предыдущих методах Q= N*N, но требуется дополнительная память для хранения списка G.
2.2.4. Слияние списков
Упорядоченные списки А и В длин М и N сливаются в один упорядоченный список С длины М+N, если каждый элемент из А и В входит в С точно один раз. Так, слияние списков А= и В= из 5 и 4 элементов дает в качестве результата список С= из 9 элементов.
Для слияния списков А и В список С сначала полагается пустым, а затем к нему последовательно приписывается первый узел из А или В, оказавшийся меньшим и отсутствующий в С.
Составим функцию для слияния двух упорядоченных, расположенных рядом частей массива s. Параметром этой функции будет исходный массив s с выделенными в нем двумя расположенными рядом упорядоченными подмассивами: первый с индекса low до индекса low+l, второй с индекса low+l+1 до индекса up, где переменные low, l, up указывают месторасположения подмассивов. Функция merge осуществляет слияние этих подмассивов, образуя на их месте упорядоченный массив с индексами от low до up (см. рис.28).
Рис.28. Схема движения индексов при слиянии списков.
2.2.5. Сортировка списков путем слияния
Для получения упорядоченного списка B’ последовательность значений В=<K1,K2. Kn> разделяют на N списков В1=<K1>, B2=<K2>. Bn=<Kn>, длина каждого из которых 1. Затем осуществляется функция прохода, при которой М>=2 упорядоченных списков B1,B2. Bm заменяется на М/2 (или (М+1)/2) упорядоченных списков, B(2i-1)-oго и B(2i)-ого ( 2iПриведем пример сортировки списка путем использования слияния, отделяя последовательности косой чертой, а элементы запятой.
Количество действий, требуемое для сортировки слиянием, равно Q=N*log2(N), так как за один проход выполняется N сравнений, а всего необходимо осуществить log2(N) проходов. Сортировка слиянием является очень эффективной и часто применяется для больших N, даже при использовании внешней памяти.
Функция smerge упорядочивает массив s сортировкой слиянием, используя описанную ранее функцию merge.
2.2.6. Быстрая и распределяющая сортировки
Быстрая сортировка состоит в том, что список В= реорганизуется в список B’,,B», где В’ — подсписок В с элементами, не большими К1, а В» — подсписок В с элементами, большими К1. В списке B’,,B» элемент К1 расположен на месте, на котором он должен быть в результирующем отсортированном списке. Далее к спискам B’ и В» снова применяется упорядочивание быстрой сортировкой. Приведем в качестве примера сортировку списка, отделяя упорядоченные элементы косой чертой, а элементы Ki знаками .
Время работы по сортировке списка методом быстрой сортировки зависит от упорядоченности списка. Оно будет минимальным, если на каждом шаге разбиения получаются подсписки B’ и В» приблизительно равной длины, и тогда требуется около N*log2(N) шагов. Если список близок к упорядоченному, то требуется около (N*N)/2 шагов.
Рекурсивная функция quick упорядочивает участок массива s быстрой сортировкой.
Количество действий, необходимых для сортировки N T-цифровых чисел, определяется как Q(N*T). Недостатком этого метода является необходимость использования дополнительной памяти под карманы.
Однако можно исходный список представить как связанный и сортировку организовать так, чтобы для карманов В0,В1. В9 не использовать дополнительной памяти, элементы списка не перемещать, а с помощью перестановки указателей присоединять их к тому или иному карману.
В представленной ниже программе функция pocket реализует распределяющую сортировку связанного линейного списка (указатель q), в котором содержатся Т-разрядные десятичные положительные числа, без использования дополнительной памяти; в функции a[i], b[i] указывают соответственно на первый и на последний элементы кармана Bi.
На рис.31 показана схема включения очередного элемента списка в К-й карман.
Рис.31. Схема включения очередного элемента списка в карман.
Разновидностью распределяющей сортировки является битовая сортировка. В ней элементы списка интерпретируются как двоичные числа, и D(j,n) обозначает j-ю справа двоичную цифру числа n. При этой сортировке в процессе РАСПРЕДЕЛЕНИЕ требуются только два вспомогательных кармана В0 и В1; их можно разместить в одном массиве, двигая списки В0 и В1 навстречу друг другу и отмечая точку встречи. Для осуществления СБОРКИ нужно за списком В0 написать инвертированный список В1.
Так как выделение j-го бита требует только операций сдвига, то битовая сортировка хорошо подходит для внешней сортировки на магнитных лентах и дисках.
Разновидностью битовой сортировки является бинарная сортировка. Здесь из всех элементов списка B= выделяются его минимальный и максимальный элементы и находится их среднее арифметическое m=(MIN+MAX)/2. Список В разбивается на подсписки В1 и В2, причем в В1 попадают элементы, не большие m, а в список В2 — элементы, большие m. Потом для непустых подсписков В1 и В2 сортировка продолжается рекурсивно.