Cтраница 1
Входной список I во время сортировки как бы состоит из двух частей: Is - упорядоченной и 1и - неупорядоченной. [1]
Если входной список не пуст и головой его является п, а хвостом rest, то требуемое дерево может быть построено путем образования дерева из остатка входных данных и последующей упорядоченной вставкой п в результирующее дерево. Для удобства определим вспомогательную функцию Insert, вставляющую число в дерево таким образом, чтобы была сохранена упорядоченность. [2]
При просмотре входного списка ребер v - ребро ( у /, у /) заносится в РСДС только при i /, благодаря чему каждое ребро заносится в РСДС лишь однажды. Чтобы осуществить это, мы должны определить местоположение ( а /, VH) в РСДС. [3]
Здесь на каждом шаге итерации из входного списка эффективным образом удаляется некоторый новый элемент, который переносится в начало еще одного списка, где накапливаются уже удаленные элементы. [4]
Сортировка вставкой является алгоритмом сортировки, который из входного списка порождает отсортированный путем повторной вставки элементов исходного списка на правильные позиции в частично отсортированный список. [5]
Программа присоед основывается на неестественной до некоторой степени конструкции - представлении входного списка ( А, В, С) как результата вычеркивания какого-то неопределенного хвостового фрагмента w из конца списка C. Эта программа, возможно, более эффективна, чем предыдущая, но в то же время ее гораздо труднее понять. Для других задач, таких как изменение порядка элементов произвольного списка на обратный, по-видимому, нет никаких методов решения, в которых требовалось бы только одно обращение к процедуре. [6]
Интерпретатор L4 расщепляет каждый блок графических данных на входную таблицу сообщений и входной список данных. После окончания блока управление передается декодировщику L4, последовательно обрабатывающему каждую из команд L4 во входной таблице сообщений. Если команда относится к группе I или группе II ( см. табл. 9.2), вызывается менеджер дисплейного файла, который обновляет программу дисплейного процессора или корреляционную таблицу. Если встретилась команда из группы III, вызывается соответствующая диалоговая программа. [7]
Эти процедуры эффективным образом объединяют отдельные вызовы э из программы 20, вследствие чего разложение входного списка выполняется не два раза, а один. [8]
Метод отбора и обмена подобен простому отбору, за исключением того, что в результате переупорядочивается входной список. [9]
На первом этапе с переключателем в состоянии ВВЕРХ используется только первая итеративная процедура пик для осуществления процесса просмотра входного списка. Эта процедура эффективным образом выключается ( больше не вызывается), как только в результате обнаружения первой убывающей пары 8 6 переключатель переходит в состояние ВНИЗ. Затем включается вторая итеративная процедура пик, которая используется для завершения процесса просмотра. [10]
В рекурсивном состоянии мы начинаем строить выходной список с помощью прогрессирующей подстановки, констатируя, что Н, голова первого входного списка, должна быть первым элементом выходного списка. [11]
Дугами в этой сети являются бесконечные списки целых чисел ( часто называемые потоками), а вершиной IncList - процесс, увеличивающий отдельные компоненты входного списка. Циклическое соединение в сети появляется из-за рекурсивной сущности функции Ints. Интересной особенностью сети является то, что каждую вершину можно рассматривать как статический процесс. Например, хотя последовательность вычислений, представленная выше, показывает, что работа Ints заключается в выполнении рекурсивных вызовов самой себя, ее можно рассматривать как статическую часть программы с одним входным буфером и одним выходным, где каждый выходной элемент на единицу больше соответствующего входного элемента. [12]
При исполнении этой программы весь подсчет числа различных элементов откладывается до тех пор, пока не будет завершена операция фильтрации, которая удаляет все дубликаты из входного списка. Задания, связанные с фильтрацией и подсчетом, выполняются последовательно благодаря стандартной стратегии управления, согласно которой вызов процедуры длина остается латентным до тех пор, пока не будет решен вызов процедуры фильтр. [13]
На этой диаграмме показан один шаг сортировки выбором связного списка. Входной список просматривается с таким расчетом, чтобы max показывал на узел, предшествующий ( a tуказывал на) узлу, содержащему максимальный элемент. С течением процесса, в конечном итоге, исчерпывается весь входной список, а в выходном списке элементы размещаются в заданном порядке. [14]
Сортировка выбором связного списка достаточно проста, но несколько отличается от сортировки массива тем же методом, поскольку размещение элемента в начале списка - более простая операция. Когда входной список не пуст, он просматривается с целью нахождения максимального элемента, который затем удаляется из входного и помещается в начало выходного списка. [15]