Последний элемент связанного списка не имеет следующего за ним элемента, и значение указателя nex t последнего элемента обычно устанавливается равным специальному значению, обычно NULL, чтобы показать, что этот элемент списка является последним. в определенных случаях последний элемент списка не указывает на специальное значение, а указывает на первый элемент этого же списка. Такой список называется кольцевым связанным списком (circular linked list), поскольку связи образуют топологию кольца. Кольцевые связанные списки могут быть как односвязными, так и двухсвязными. В двухсвязных кольцевых списках указатель pre v первого элемента указывает на последний элемент списка. На рис. А.З и А.4 показаны соответственно односвязные и двухсвязные кольцевые списки.
next next next
Рис.A3. Односвязный кольцевой список
prev next prev next prev next
Рис. А.4. Двухсвязный кольцевой список
Стандартной реализацией связанных списков в ядре Linux является двухсвязный кольцевой список. Такие связанные списки обеспечивают наибольшую гибкость работы.
Перемещение по связанному списку
Перемещение по связанному списку выполняется последовательно (линейно). После того как просмотрен текущий элемент, выполнятся разыменование его указателя next, что позволяет обратиться к следующему за ним элементу и т.д. Это самый простой и наиболее подходящий метод перемещения но связанному списку. Если важна возможность произвольного доступа к любому элементу контейнера, то связанные списки не используются. Связанные списки используются, когда важна возможность динамического добавления и удаления элементов, а также возможность последовательного прохождения по всем элементам списка.
|
|
Часто первый элемент списка представлен с помощью специального указателя, который называется головным элементомили головой (head), что дает возможность быстро и легко обращаться к первому элементу. В некольцевом связанном списке последний элемент отличается тем, что его указатель равен значению NULL. В кольцевом связанном списке последний элемент отличается тем, что указывает на головной элемент. Таким образом прохождение списка можно выполнить линейно, начиная с первого элемента и заканчивая последним. В двухсвязном списке прохождение можно также выполнить и в противоположном направлении, начиная с последнего и заканчивая первым элементом. Конечно, если задан определенный элемент списка, то можно перейти по списку вперед и назад на заданное количество элементов. При этом нет необходимости проходить весь список.
Внешняя сортировка — сортировка данных, расположенных на периферийных устройствах и не вмещающихся в оперативную память, то есть когда применить одну из внутренних сортировок невозможно. Стоит отметить, что внутренняя сортировка значительно эффективней внешней, так как на обращение к оперативной памяти затрачивается намного меньше времени, чем к магнитным дискам, лентам и т. п.
Наиболее часто внешняя сортировка используется в СУБД. Основным понятием при использовании внешней сортировки является понятие отрезка. Отрезком длины {\displaystyle K} 
является последовательность записей {\displaystyle A_{i}} , {\displaystyle A_{i+1}} ,…,{\displaystyle A_{i+k}} , что в ней все записи упорядочены по некоторому ключу. Максимальное количество отрезков в файле {\displaystyle N} (все элементы не упорядочены). Минимальное количество отрезков 1 (все элементы являются упорядоченными).
|
|
Например, в некотором файле А есть одномерный массив:
12 35 65 0 24 36 3 5 84 90 6 2 30
Поделим массив на отрезки:
12 35 65 | 0 24 36 | 3 5 84 90 | 6 | 2 30
Можно сказать, что массив в файле А состоит из 5 отрезков.
Например, в некотором файле B есть одномерный массив:
1 2 3 4 5 6 7 8 9 10
Поделим массив на отрезки:
| 1 2 3 4 5 6 7 8 9 10 |
Можно сказать, что массив в файле B состоит из 1 отрезка.
Например, в некотором файле А есть одномерный массив:
20 17 16 14 13 10 9 8 6 4 3 2 0
Поделим массив на отрезки:
| 20 | 17 | 16 | 14 | 13 | 10 | 9 | 8 | 6 | 4 | 3 | 2 | 0 |
Можно сказать, что массив в файле А состоит из 13 отрезков.
Идея большинства методов заключается в расчленении данных на ряд последовательностей помещающихся в оперативную память. Далее применяется один из методов внутренней сортировки, после чего последовательности сливаются. Чем больше объём оперативной памяти, тем длиннее будут последовательности и, следовательно, тем меньшим окажется их количество, что увеличит скорость сортировки.
Если же объём оперативной памяти мал, то можно разделить исходные данные на несколько последовательностей, после чего непосредственно использовать процедуру слияния.