Модели и структуры данных



         

Реализация операций над связными линейными списками - часть 5


В процедуре перестановки для двухсвязного списка (рис.5.10.) нетрудно учесть и перестановку в начале/конце списка.

Копирование части списка.

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

Рис.5.10. Перестановка соседних элементов 2-связного списка

Копирование для односвязного списка показано в программном примере 5.6.

{==== Программный пример 5.6 ====} { Копирование части 1-связного списка. head - указатель на начало копируемой части; num - число эл-тов. Ф-ция возвращает указатель на список-копию } Function CopySll ( head : sllptr; num : integer) : sllptr; var cur, head2, cur2, prev2 : sllptr; begin if head=nil then { исходный список пуст - копия пуста } CopySll:=nil else begin cur:=head; prev2:=nil; { перебор исходного списка до конца или по счетчику num } while (num>0) and (cur<>nil) do begin { выделение памяти для эл-та выходного списка и запись в него информационной части } New(cur2); cur2^.inf:=cur^.inf; { если 1-й эл-т выходного списка - запоминается указатель на начало, иначе - записывается указатель в предыдущий элемент } if prev2<>nil then prev2^.next:=cur2 else head2:=cur2; prev2:=cur2; { текущий эл-т становится предыдущим } cur:=cur^.next; { продвижение по исходному списку } num:=num-1; { подсчет эл-тов } end; cur2^.next:=nil; { пустой указатель - в последний эл-т выходного списка } CopySll:=head2; { вернуть указатель на начало вых.списка } end; end;

Слияние двух списков.

Операция слияния заключается в формировании из двух списков одного - она аналогична операции сцепления строк. В случае односвязного списка, показанном в примере 5.7, слияние выполняется очень просто.


Содержание  Назад  Вперед