Вставка элемента в список Вставка элемента в середину односвязного списка показана на рис.1 и в примере 2. Рис. 1: Вставка элемента в середину 1-связного списка {==== Программный пример 2 ====} { Вставка элемента в середину 1-связного списка } Procedure InsertSll(prev : sllptr; inf : data); { prev - адрес предыдущего эл-та; inf - данные нового эл-та } var cur : sllptr; { адрес нового эл-та } begin { выделение памяти для нового эл-та и запись в его инф.часть } New(cur); cur^.inf:=inf; cur^.next:=prev^.next; { эл-т, следовавший за предыдущим теперь будет следовать за новым } prev^.next:=cur; { новый эл-т следует за предыдущим } end; Рисунок 2 представляет вставку в двухсвязный список. Рис. 2: Вставка элемента в середину 2-связного списка Приведенные примеры обеспечивают вставку в середину списка, но не могут быть применены для вставки в начало списка. При последней должен модифицироваться указатель на начало списка, как показано на рис. 3. Рис. 3: Вставка элемента в начало 1-связного списка Программный пример 3 представляет процедуру, выполняющую вставку элемента в любое место односвязного списка. {==== Программный пример 3 ====} { Вставка элемента в любое место 1-связного списка } Procedure InsertSll var head : sllptr; { указатель на начало списка, может измениться в процедуре, если head=nil - список пустой } prev : sllptr; { указатель на эл-т, после к-рого делается вставка, если prev-nil - вставка перед 1-ым эл-том } inf : data { - данные нового эл-та } var cur : sllptr; { адрес нового эл-та } begin { выделение памяти для нового эл-та и запись в его инф.часть } New(cur); cur^.inf:=inf; if prev <> nil then begin { если есть предыдущий эл-т - вставка в середину списка, см. прим. 2 } cur^.next:=prev^.next; prev^.next:=cur; end else begin { вставка в начало списка } cur^.next:=head; { новый эл-т указывает на бывший 1-й эл-т списка; если head=nil, то новый эл-т будет и последним эл-том списка } head:=cur; { новый эл-т становится 1-ым в списке, указатель на начало теперь указывает на него } end; end; Удаление элемента из списка Удаление элемента из односвязного списка показано на рис. 4. Рис. 4: Удаление элемента из 1-связного списка Очевидно, что процедуру удаления легко выполнить, если известен адрес элемента, предшествующего удаляемому (prev на рис.4.а). Мы, однако, на рис. 4 и в примере 1 приводим процедуру для случая, когда удаляемый элемент задается своим адресом (del на рис.4). Процедура обеспечивает удаления как из середины, так и из начала списка. {==== Программный пример 1 ====} { Удаление элемента из любого места 1-связного списка } Procedure DeleteSll( var head : sllptr; { указатель на начало списка, может измениться в процедуре } del : sllptr { указатель на эл-т, к-рый удаляется } ); var prev : sllptr; { адрес предыдущего эл-та } begin if head=nil then begin { попытка удаления из пустого списка асценивается как ошибка (в последующих примерах этот случай учитываться на будет) } Writeln('Ошибка!'); Halt; end; if del=head then { если удаляемый эл-т - 1-й в списке, то следующий за ним становится первым } head:=del^.next else begin { удаление из середины списка } { приходится искать эл-т, предшествующий удаляемому; поиск производится перебором списка с самого его начала, пока не будет найдет эл-т, поле next к-рого совпадает с адресом удаляемого элемента. } prev:=head^.next; while (prev^.next<>del) and (prev^.next<>nil) do prev:=prev^.next; if prev^.next=nil then begin { это случай, когда перебран весь список, но эл-т не найден, он отсутствует в списке; расценивается как ошибка (в последующих примерах этот случай учитываться на будет) Writeln('Ошибка!'); Halt; end; prev^.next:=del^.next; { предыдущий эл-т теперь указывает на следующий за удаляемым } end; { элемент исключен из списка, теперь можно освободить занимаемую им память } Dispose(del); end; На практике в односвязных списках используется преимущественно операция удаления элемента, следующего за данным, так как проход по всему списку - слишком дорогостоящая операция. Получается, также, что мы не можем быстро удалить текущий элемент. Такую операцию допускает лишь двусвязный список. Удаление элемента из двухсвязного списка показано на рис.5. Рис. 5: Удаление элемента из 2-связного списка Процедуру удаления элемента из двухсвязного списка окажется даже проще, чем для односвязного, так как в ней не нужен поиск предыдущего элемента, он выбирается по указателю назад. <<<  Назад Вперед  >>>  1  2  3  4  5   8  Комментарии к статье  8 8  Обсудить в чате