Основы программирования. Указатели. Динамические структуры данных. Абстрактные типы данных. Классы - 23 стр.

UptoLike

ВУЗ: 

ЮФУ | Ростов-на-Дону

Составители: 

Рубрика: 

25
procedure SortedListAdd(p: PNode; x: integer);
begin
while (p<>nil) and (p^.next^.data<=x) do
p:=p^.next;
p^.next:=NewNode(x,p^.next);
end;
3 5 7
p
4
Отметим, что наш алгоритм осуществляет добавление после элемента, на ко-
торый указывает p, поэтому он не может добавить в начало списка. Для решения
указанной проблемы поместим в начало списка барьерный элемент, поле данных
которого содержит самое маленькое число (-MaxInt). Список при этом сохранит
свою упорядоченность, и теперь любой элемент будет
добавляться после барьер-
ного. Например, вот как выглядит заполнение упорядоченного списка n случай-
ными числами с последующим его выводом:
readln(n);
p:=NewNode(-MaxInt,nil); // барьер
for i:=1 to n do
SortedListAdd(p,Random(1000));
t:=p;
while t<>nil do
begin
write(t^.data);
t:=t^.next;
end;
По существу, приведенный код реализует алгоритм сортировки вставками. По-
скольку при вставке одного элемента в список длины n может потребоваться
n
операций (в случае прохода по всему списку), то для вставки n элементов требуе-
мое количество операций пропорционально
2
n .
2.3 Сравнение списков и массивов
Сравним производительность различных операций для списков с массивами.
Основное преимущество массивов – возможность обратиться к произвольному
элементу по его индексу. Для списка подобная операция потребует просмотра
всех предшествующих элементов. Однако добавление в начало и середину масси-
ва, а также удаление из начала и середины требует сдвига всех элементов масси-
ва, расположенных после
вставляемого (удаляемого). Для списка же производи-
тельность операций добавления и удаления не зависит ни от длины списка, ни от

Страницы