Поиск и включение в упорядоченном списке
Если список упорядочен по увеличению ключей, то поиск можно заканчивать, когда будет обнаружен ключ больше нового входного. Вставка элемента в отличии от массива не требует сдвига группы. Поиск в упорядоченном списки предполагает перед первым элементом ключом больше заданного. Для оптимизации работы с таким списком будем иметь две ссылки.
W1,w2 – ссылки w2 отстает на один шаг от w1
Это позволяет определить точно место включения по w1 будет обнаружен больший ключ.
root
Вместо проверки, что список не пустой добавляем в голову списка пустой элемент.
//////////////////////////////////
Type
ptr=^Node;
Node=record
key:integer
next:Ptr;
end;
///////////////////////////////////////
GetMem(root,sizeof(node)); root^.next:=Nil
Гл пр
Процедура поиска Procedure Search(x:integer; var root:ptr); var w1,w2,w3:ptr;
W2:=root w1:=w2^.next
(w1<>nil) and (w1^.key<x)
W2=w1 w1:=w2^.next
W1=nil or (w1^.key>x)
GetMem(w3,sizeof(Node)) w2^.next:=w3; w3^.next:=w1
W1^.count=w1^count+1
Рекомендуется представлять данные в виде связанных списков в тех случаях, когда число элементов меняется относительно мало и нет никаких сведений о частоте их использования. типичный пример таблица имен трансляторов для языков программирования.
Каждое описание приводит к добавлению в список нового имени, а при выходе из области действия — это имя из списка исключается.
Для улучшения доступа. Для текстов программ характерно скопление идентификаторов. За одним проявление идентификатора как правило следует другие. Следовательно, список после каждого обращения надо реализовать следующим образом:
Передвигать найденный элемент в голову списка и тем самым минимизировать его поиск в следующее повторное обращение. Такие списки называют списками самоорганизации.
Топологическая сортировка.
- сортировка элементов для которых определено отношение частичного порядка. Т.е. порядок задан не для всех, а лишь для некоторых пар.
Пр. В толковом словаре слова определяются с помощью другие слов. Если слово w определяется с помощью слова v о это обозначим v<w. Топологическая сортировка означает такое распределение слов в словаре при котором ссылки в перед отсутствуют.
Пр. любой технический проект распадается на ряд подзадач. Выполнения некоторых подзадач только после выполнения других. Топологическая сортировка означает такое распределение работ, при котором каждое из подзадач не начнется, пока не закончатся все подзадачи предшествующие данные. Пр. топологическая сортировка в проекте в программировании обозначает такое распределение в описании процедур в проекте при котором нет ссылок вперед.
Отношение порядка на множестве S(x,y,z э S) отношение порядка обозначается x<y и удовлетворяет 3м аксиомам для Ɐ элементов (x,y,z) этого множества
Транзитивность Если x<y и y<z => x<z
Ассиметричность Если x>y не => y<x
Иррефлективность
X<x не выполняется х меньше х
Пр. Граф отражающий частичную упорядоченность. Вершины – элементы, дуги – отношения порядка.
Цель Т.С. преобразовать частичный в линейный. Графически это означает расположить вершины графа на одной таким образом чтоб все стрелки указывали вправо. 1-2 аксиома гарантирует отсутствие цикла.
Опишем процесс который приводит в окному из возможных Линейных порядков. Начнем выстраивать с элемента у которого нет ни одного предшественника. Этот элмент помещаем в голову списка и вычеркиванием из множества s. Оставшее множество упорядоченно частично, следовательно в нему можно применить тот же алгоритм(предшественник). До тех пор пока множество не останется пустым.
Нужно выбрать структуру множества S и его отношения порядка. Выбор представления диктует операции над ним. Каждый элемент надо представлять в помощью 3х характеристик (идентифицирующий ключ, множество последовательных и счетчик предшественников. Организуем S потому что в заранее S не задано. Следовательно, появится у каждого элемента ссылка на следующей. Ключи целые числа. Множества последователей удобно представлять в виде последователей. В списке последний элемент нужно идентифицировать и связать ссылкой со следующим.
Элементы главного списка называет ведущими leaders. А из списка последователей ведомыми trailers.
Type LPtr=^Leaders; TPtr=^trailers; leaders=record key,count:integer; trail:TPrt; next:LPtr; end;
Trailers=record id:LPtr next:TPtr; end;