Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

End else. lptr = ^item; { указатель на элемент списка }

Begin

Begin

Type

Begin

Begin

Begin

Begin

Type

lptr = ^item; { указатель на элемент списка }

item = record { элемент списка }

key: Integer; { ключ }

inf: data; { данные }

next: lptr; { указатель на элемент списка }

end;

 

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

Следующий пример демонстрирует сортировку выборкой. Указатель newh является адресом начала выходного списка, исходно пустого. Во входном списке ищется максимальный элемент. Найденный элемент исключается из входного списка и включается в начало выходного списка. Работа алгоритма заканчивается, когда входной список станет пустым.

 

{ Сортировка выборкой на 1-связном списке }

function Sort(head: lptr): lptr;

var newh, max, prev, pmax, cur: lptr;

newh:= nil; { выходной список - пустой }

while head <> nil do { цикл, пока не опустеет входной список }

max:=head;

prev:=head; { нач. максимум - 1-й элемент }

cur:=head^.next; { поиск максимума во входном списке }

while cur <> nil do

if cur^.key > max^.key then

{ запоминается адрес максимума и адрес предыдущего элемента }

max:=cur;

pmax:=prev;

end;

prev:=cur;

cur:=cur^.next; { движение по списку }

end;

{ исключение максимума из входного списка }

if max = head then

head:=head^.next else

pmax^.next:=max^.next;

{ вставка в начало выходного списка }

max^.next:=newh;

newh:=max;

end;

Result:=newh;

end;

 

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

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

В-третьих, обратите внимание на то, что не возникает проблем с пропуском во входном списке тех элементов, которые уже выбраны – они просто исключены из входной структуры данных.

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

 

data = Integer;

 

{ Сортировка вставками на 1-связном списке }

function Sort(head: lptr): lptr;

var newh, cur, sel: lptr;

newh:= nil; { выходной список - пустой }

while head <> nil do

begin { цикл, пока не опустеет входной список }

sel:=head; { элемент, который переносится в выходной список }

head:=head^.next; { продвижение во входном списке }

{ выходной список пустой или элемент меньше 1-го - вставка в начало }

if (newh = nil) or (sel^.key < newh^.key) then

sel^.next:=newh;

newh:=sel;

end;

{ вставка в середину или в конец }

<== предыдущая лекция | следующая лекция ==>
Применение линейных списков | Основные понятия. Нелинейные разветвленные списки
Поделиться с друзьями:


Дата добавления: 2014-01-07; Просмотров: 260; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.009 сек.