Перемещение узла из середины списка в начало в Паскале

Delphi , Базы данных , Сортировка и Фильтр

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

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

pNode = ^Node;
Node = record
    data : data;
    next : pNode;
end;

И мы хотим переместить узел y перед узлом x, если данные узла y меньше данных узла x. Мы можем использовать следующий цикл, чтобы пройти по списку:

while y <> z do begin
    if y^.data < x^.data then begin
      // HERE I WOULD LIKE TO MOVE y IN FRONT OF X
    end;
    y:=y^.next;
end;

Где x - это начало списка (пivot), y - это текущий узел (индекс), а z - это конец списка.

Мы можем определить процедуры insertAfter и insertInstead, чтобы вставить новый узел после или вместо существующего узла соответственно:

procedure List.insertAfter(n : pNode; var what : data);
var
  newn : pNode;
begin
  new(newn);
  newn^.data := what;
  newn^.next := n^.next;
  n^.next := newn;
end;

procedure List.insertInstead(n : pNode; var what : data);
begin
  List.insertAfter(n, n^.data);
  n^.data:=what;
end;

Также нам понадобятся процедуры deleteAfter и delete, чтобы удалить узел после или удалить узел соответственно:

procedure List.deleteAfter(n : pNode);
var
  q : pNode;
begin
  q := n^.next;
  n^.next := n^.next^.next;
  dispose(q);
end;

procedure List.delete(n : pNode);
begin
  if n^.next <> tail then begin
    n^.data := n^.next^.data;
    deleteAfter(n);
  end
  else begin
    dispose(tail);
    tail:=n;
    tail^.next := nil;
  end;
end;

Теперь, если мы хотим переместить узел y перед узлом x, мы можем использовать процедуры insertInstead и delete:

list.insertInstead(x,y^.data);
list.delete(y);

Однако, как оказалось, этот подход не работает, потому что y^.next больше не указывает на тот же узел, что и раньше.

Чтобы решить эту проблему, мы можем использовать подход, предложенный в альтернативном ответе: менять местами значения узлов. Мы можем определить процедуру swapNodes, которая меняет местами данные двух узлов:

procedure List.swapNodes(x, y : pNode);
var
  tmp : data;
begin
  tmp := x^.data;
  x^.data := y^.data;
  y^.data := tmp;
end;

Теперь мы можем использовать эту процедуру в нашем цикле, чтобы переместить узел y перед узлом x:

while y^.next <> z do begin
  if y^.data < x^.data then begin
    List.swapNodes(x, y);
  end;
  y:=y^.next;
end;
if y^.data < x^.data then begin
  List.swapNodes(x, y);
end;

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

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

Создано по материалам из источника по ссылке.

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

Комментарии и вопросы

Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS

:: Главная :: Сортировка и Фильтр ::